Routing on Complex Networks

So far this hour has focused on a single router or single group of routers. In fact, some large networks might contain hundreds of routers. The Internet contains thousands of routers. On very large networks such as the Internet, it is not feasible for all routers to share all the information necessary to support the routing methods described in previous sections. If every router had to compile and process routing information for every other router on the Internet, the volume of router protocol traffic and the size of the routing tables would soon overwhelm the infrastructure. But it isn't really necessary for every router on the Internet to know about every other router. A router in a dentist's office in Istanbul could operate for years without ever having to learn about another router in an office pool at a paint factory in Lima, Peru. If the network is organized efficiently, most routers need to exchange routing protocol information only with other nearby routers.

In the ARPAnet system that led to the Internet, a small group of core routers served as a central backbone for the internetwork, linking individual networks that were configured and managed autonomously. The core routers knew about every network, though they did not have to know about every subnet. As long as any datagram could find a path to a core router, it could reach any point in the system. The routers in the tributary networks beneath the core didn't have to know about every network in the world, they just had to know how to send data among themselves and how to reach the core routers.

This system evolved into the system depicted in Figure 10.5. The core routers in the backbone network pass messages among the networks. Attached to the core are independently managed networks called autonomous systems. An autonomous system might represent a corporate network or, more commonly in recent times, a network associated with an Internet service provider (ISP). The owner of the autonomous system manages the details of configuring individual routers. Interior routers within the autonomous system share information and build fairly complete routing tables that describe the internal design of the network. A message addressed to another network is forwarded to the core. Also important are exterior routers. An exterior router is designated to exchange information with other networks. The volume of internetwork router communication is thus reduced because only the exterior routers communicate routing information across network boundaries.

Each router type uses different protocols and algorithms to build the routing table. You'll learn about some of these routing protocols in later sections. Keep in mind this quick summary of the router types:

• Core routers— Core routers have complete information about other core routers. The routing table is basically a map of where autonomous systems tie into the core. Core routers do not possess detailed information about routes within the autonomous networks. Examples of core router routing protocols include Gateway-to-Gateway Protocol (GGP) and a more recent routing protocol called SPREAD.

• Exterior routers— Exterior routers are non-core routers that communicate routing information between autonomous networks. They maintain routing information about their own and neighboring autonomous networks but do not have a map of the complete internetwork. Exterior routers traditionally have used a protocol called Exterior Gateway Protocol (EGP). The actual EGP protocol is now outdated, but newer routing protocols that serve exterior routers are commonly referred to as EGPs. A popular exterior gateway protocol now in use is Border Gateway Protocol (BGP). Often an exterior router is also participating as an interior router within its autonomous system.

• Interior routers— Routers within an autonomous region that share routing information are called interior gateways. These routers use a class of routing protocols called Interior Gateway Protocols (IGP). Examples of interior routing protocols include Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). You'll learn more about RIP and OSPF later in this hour.

It is important to note that the routers within one of the autonomous networks might also have a hierarchical configuration. A large autonomous system might consist of multiple groups of interior routers with exterior routers passing routing information between the interior groups. Managers of the autonomous network are free to design a router configuration that works for the network and to choose routing protocols accordingly.