The Internet is made up of component networks that are owned and run by many different authorities. Some of these authorities may have rules about what, if any, traffic they will permit to cross. Indeed some networks may disallow any through, or transit traffic, permitting only local traffic destined for, or sourced by, an internal host. As a rule transit traffic is only an issue for networks which have at least two connections to the rest of the Internet.
Routing on the Internet is hierarchical. The Internet is divided into regions called autonomous systems(ASs) or, sometimes, routing domains, each of which is controlled by a single routing authority and will typically consist of a number of interconnected networks (as AS is itself, therefore, an internetwork). Within a single AS, routers use an interior gateway protocol or IGP to exchange routing information in order to allow them to update their routing tables. Routers at the interface, or border, between two ASs are known as boundary routers and use an exterior gateway protocol (EGP) to control routing between ASs. IGPs and EGPs are similar in character but while IGPs attempt to identify optimal routes across an AS, EGPs concentrate only on reachability. This hierarchy of inter-AS and intra-AS routing reduces the size of the tables required at any given router and allows for differences in the way different ASs handle traffic to be taken into account.
Over the history of the Internet many different approaches to computing routing tables have been tried. In small to medium AS's, such as those consisting of groups of LANs interconnected by routers (as opposed to switches) the Routing Information Protocol (RIP) is commonly used. RIPv1 (RFC 1058) was introduced in 1988 and is still used in some areas, but it has very limited support for classless addressing because when it sends routing information it does not include masks. This shortcoming was rectified in RIP v2 (RFC 1723). The principle behind both versions of RIP is to allow each router to advertise its routes including their lengths in hops, to its neighbours which then use the information to improve their own routes and to expand the list of reachable destination networks. The algorithm on which RIP is based is known as distance vector routing.
The RIP messages, essentially just lists of routes (see Figure 1), are carried in UDP PDUs and are sent around every 30 seconds. When a router, A, receives an RIP message from a neighbour B, it updates its own routing tables if B can offer a better route than the one A is currently storing to some destination network. B assigns a distance of 0 to each network it can reach directly, 1 to each network which is one router away and so on up to a maximum of 15 for an unreachable network. Each of these values is incremented by 1 when B includes it in in a RIP message, because, of course, any route it offers to A will involve the additional hop (A®B) between them. RIP v2 also improves on RIP v1 by using multicasts (to address 224.0.0.9) instead of broadcasts and by providing a mechanism for authentication. The latter prevents a malicious user from deliberately advertising false routing information, something to which RIP v1 is vulnerable.
Open Shortest Path First or OSPF (OSPF v2 is defined in RFC 2328), which was intended to become an Internet standard for AS's of all sizes. OSPF allows a large AS to be divided into numbered areas, as shown in Figure 2, which may be networks or groups of neighbouring networks. Some routers may not belong to any area. Each AS has a backbone area, numbered 0, to which every other area must be connected.
Figure 2 Structure of an AS
Unlike an RIP router which simply compares its routes with its neighbours, OSPF routers cooperate with each other to build a complete database of link costs within their area. This database, known as the Link State Database (LSDB) is composed of units called Link State Advertisements (LSAs). Each router generates an LSA for itself which gives a list of the costs it perceives to reach each router which it considers to be a neighbour. LSAs are also generated for broadcast networks (these are prepared by one router attached to the network in question which has been elected Designated Router, or DR, for that network) indicating which routers are currently attached to the network. Finally area border routers and AS boundary routers feed in other LSAs giving costs to reach other areas and other AS's The costs may be in any suitable metric including hops, bandwidth, delay etc (in fact OSPF can use more than one metric simultaneously to provide different routes for IP packets with different TOS fields).
All routers in an OSPF area must synchronise their LSDBs, which they do by exchanging LSAs with their neighbours. OSPF involves regular checks by routers that neighbours remain accessible—this is done by exchange of OSPF Hello packets. If a router detects a change in the accessibility of a neighbour or detects a new neighbour, it must ensure that the new LSA is reaches all routers in the area. The process is called flooding and essentially is achieved by each router passing on the new information, as soon as it receives it, to its own neighbours. Once a consistent LSDB has been compiled, each router uses a so-called link state algorithm to compute least cost paths to all other routers and networks in the area. The set of all such paths forms a tree (rooted at the router in question) of best routes called a shortest path first or SPF tree from which forwarding tables can be derived.
OSPF uses a number of packet types to support initialisation, exchange of LSAs and even exchanges of entire LSDBs. All are carried directly over IP (OSPF is protocol number 89).
The commonest EGP in use today is Border Gateway Protocol v4 (BGP) defined in RFC 1771, which directs traffic between AS boundary routers. As far as BGP is concerned, any two boundary routers which share a common AS are connected and there is no use for cost metrics. Unlike an IGP, BGP must take into account restrictions imposed by certain AS's for security reasons. AS's are dived into three categories:
a stub AS has only a single connection to the outside world;
a multi-homed A, has multiple connections to the outside world, but will only permit local traffic to cross its boundaries;
a transit AS allows traffic to pass through from one of its bordering ASes to another.
Transit AS's are typically either service provider backbone networks or smaller consumer ISPs. They can apply transit policies which can restrict the traffic that may be carried, or apply charges to the traffic that is. These policies must be taken into account whenever routing between AS's. Backbone routers must be able to route any packet destined for any network and therefore require very large routing tables (tens of thousands of entries). These tables are ultimately computed using information garnered from BGP as follows.
Usually for each AS boundary router there is a BGP speaker. This need not in fact be a boundary router itself but we will assume, here for simplicity that they are the same. The BGP speaker communicates with BGP speakers in other connected AS's as well as with other BGP speakers within its own AS, using TCP connections to transfer BGP PDUs. BGP speakers advertise complete paths to destination networks as opposed to just next hops (as with an IGP). New paths received are compared against those already known taking transit policies into account. to build a routing database. Existing paths can also be withdrawn if, for example, a link or router fails. Once paths have been established, the BGP speaker must communicate this information to the AS's own routers. There are actually several ways of doing this but the most obvious is to let the boundary routers inject the routes into the IGP. See RFC 1772 for more details.
Exercise: (requires administrative access to a Windows 2000 Server acting as a router). A Windows 2000 Server with multiple network interfaces can act as an IP router between those interfaces. The router is administered using the "Routing and Remote Access" snap-in of the Microsoft Management Console (MMC). Launch the MMC and use it to examine the routing table. The Routing and Remote Access Service allows the router to exchange information with neighbouring routers using RIPv2 or OSPF, It also supports NAT and multicast routing.