For a vast majority of networks connected to the global Internet, routing is not a big issue. They have just a single uplink to their service providers and so a simple static setup is all they need. However, as we move upstream towards the Internet core, the network topology becomes more complex and the routers must have more information in order to be able to forward datagrams to appropriate next hops. This information is usually collected and managed dynamically by means of routing protocols.

We will see in the following sections that individual routing protocols differ in many aspects, yet the basic idea is common to all of them: Every router advertises itself to its neighbours as a candidate next hop for a certain set of network prefixes. The neighbours process this information and pass it in a properly modified form to their own neighbours, and so on.

Unlike traditional voice networks, Internet has no centralised control. The routing advertisements thus cannot be propagated and trusted too far from their origin since otherwise the network would be vulnerable to misconfigurations and malicious attacks. Therefore, the globally routable Internet is divided into manageable chunks called Autonomous Systems (also known as routing domains). An autonomous system must appear to the rest of the Internet as a well behaved unit with a consistent routing policy. It is also important that this policy be sufficiently distinct from the neighbouring autonomous systems. For example, single connected networks of any size have no space for their own routing policy and must be integrated into an upstream AS.

Note

This need not always be true for IPv6 since most networks use the same autonomous system for both IPv4 and IPv6 and their IPv6 setup and routing policy is often much less sophisticated.

With autonomous systems in place, all globally reachable IP routers are organised in a two-tier hierarchy illustrated in Figure 6-2.

In the top tier, the routable Internet is represented as a general graph whose nodes are autonomous systems and edges correspond to existing physical or logical links between autonomous systems.

Note

Historically, due to the limitations of the older EGP routing protocol, this top-tier topology had to be a tree (loop free). All traffic from a peripheral AS had to go first upstream to the root AS (so-called core routers) and then downstream to the destination AS. The BGP protocol that is now universally used throughout the Internet imposes no such restriction – the top-tier topology may contain loops.

Routing in the top tier (inter-domain routing) determines the optimal next hop for a given prefix by comparing the lengths of alternative AS paths (sequences of autonomous systems that have to be traversed before the destination AS is reached) – the shortest AS path is always preferred.

In the bottom tier, the scope of the routing task is essentially limited to a single autonomous system, as illustrated by the expanded view of AS5 in Figure 6-2. The interior routers exchange information about the topology of the local AS by means of intra-domain routing protocols. This enables them to deliver datagrams directly to any destination inside their autonomous system. For external destinations, intra-domain routing procedures only have to select an appropriate exit point (border router) and deliver the datagram to it. Intra-domain routing protocols mostly use finer grained metrics than just a number of hops for selecting the best next hop.

The autonomous system border routers (ASBR) are depicted in Figure 6-2 as “connectors” between pairs of autonomous systems. Their role is important in that they glue together the two tiers of the routing hierarchy and mediate relevant routing data in both directions. than just a number of hops for selecting the best next hop.

Currently, inter-domain routing for both IPv4 and IPv6 is absolutely dominated by a single routing protocol: BGP version 4. The choice for intra-domain routing is richer, with at least four commonly used protocols – RIP, OSPF, IS-IS and Cisco-proprietary EIGRP – all of them now available for IPv6 as well.