• Scale. As the number of routers becomes large, the overhead involved in computing, storing, and communicating the routing table information (for example, link-state updates or least-cost path changes) becomes prohibitive. Today's public Internet consists of millions of interconnected routers and more than 50 million hosts. Storing routing table entries to each of these hosts and routers would clearly require enormous amounts of memory. The overhead required to broadcast link state updates among millions of routers would leave no bandwidth left for sending data packets! A distance vector algorithm that iterated among millions of routers would surely never converge! Clearly, something must be done to reduce the complexity of route computation in networks as large as the public Internet. 
• Administrative autonomy. Although engineers tend to ignore issues such as a company's desire to run its routers as it pleases (for example, to run whatever routing algorithm it chooses), or to "hide" aspects of the networks' internal organization from the outside, these are important considerations. Ideally, an organization should be able to run and administer its network as it wishes, while still being able to connect its network to other "outside" networks.

In summary, the problems of scale and administrative authority are solved by defining autonomous systems. Within an AS, all routers run the same intra-autonomous system routing protocol. Special gateway routers in the various ASs run an inter-autonomous system routing protocol that determines routing paths among the ASs. The problem of scale is solved since an intra-AS router need only know about routers within its AS and the gateway router(s) in its AS. The problem of administrative authority is solved since an organization can run whatever intra-AS routing protocol it chooses, as long as the AS's gateway(s) is able to run an inter-AS routing protocol that can connect the AS to other ASs. 

Figure 4.12 illustrates this scenario. Here, there are three routing ASs, A, B, and C. Autonomous system A has four routers, A.a, A.b, A.c, and A.d, which run the intra-AS routing protocol used within autonomous system A. These four routers have complete information about routing paths within autonomous system A. Similarly, autonomous systems B and C have three and two routers, respectively. Note that the intra-AS routing protocols running in A, B, and C need not be the same. The gateway routers are A.a, A.c, B.a, and C.b. In addition to running the intra-AS routing protocol in conjunction with other routers in their ASs, these four routers run an inter-AS routing protocol among themselves. The topological view they use for their inter-AS routing protocol is shown at the higher level, with "links" shown in blue. Note that a "link" at the higher layer may be an actual physical link, for example, the link connection A.c and B.a, or a logical link, such as the link connecting A.c and A.a. Figure 4.12 also illustrates that the gateway router A.c must run an intra-AS routing protocol with its neighbors A.b and A.d, as well as an inter-AS protocol with gateway router B.a. 

Suppose now that a host h1 attached to router A.d needs to route a packet to destination h2 in autonomous system B, as shown in Figure 4.13. Assuming that A.d's routing table indicates that router A.c is responsible for routing its (A.d's) packets outside the AS, the packet is first routed from A.d to A.c using A's intra-AS routing protocol. It is important to note that router A.d does not know about the internal structure of autonomous systems B and C and indeed need not even know about the topology connecting autonomous systems A, B, and C. Router A.c will receive the packet and see that it is destined to an autonomous system outside of A. A.c's routing table for the inter-AS protocol would indicate that a packet destined to autonomous system B should be routed along the A.c to B.a link. When the packet arrives at B.a, B.a's inter-AS routing sees that the packet is destined for autonomous system B. The packet is then "handed over" to the intra-AS routing protocol within B, which routes the packet to its final destination, h2. In Figure 4.13, the portion of the path routed using A's intra-AS protocol is shown on the lower plane with a dotted line, the portion using the inter-AS routing protocol is shown in the upper plane as a solid line, and the portion of the path routed using B's intra-AS protocol is shown on the lower plane with a dotted line. We will examine specific inter-AS and intra-AS routing protocols used in the Internet in Section 4.5.