Figure 4.5-2: A portion of an autonomous system.
RIP is a distance vector protocol that operates in a manner very close to the idealized protocol we examined in Section 4.2.3. The version of RIP specified in RFC 1058 uses hop count as a cost metric, i.e., each link has a cost of 1, and limits the maximum cost of a path to 15. This limits the use of RIP to autonomous systems that are less than 15 hops in diameter.Recall that in distance vector protocols, neighboring routers exchange routing information with each other. In RIP, the routing tables are exchanged between neighbors every 30 seconds using RIP's. This is done with RIP's so-called response message, with each response message containing that host's routing table entries for up to 25 destination networks. These response messages containing routing tables are also called advertisements.
Let us take a look at a simple example of how RIP advertisements work. Consider the portion of an AS shown in Figure 4.5-2. In this figure, the rectangles denote routers and the lines connecting the rectangles denote networks. Note that the routers are labeled A, B, etc. and the networks are labeled 1, 10, 20, 30, etc. For visual convenience, some of the routers and networks are not labeled. Dotted lines in the figure indicate that the autonomous system continues on and perhaps loops back. Thus this autonomous system has many more routers and links than are shown in the figure.
Figure 4.5-2: A portion of an autonomous system.
Now suppose that the routing table for router D is as shown in Figure
4.5-3. Note that the routing table has three columns. The first column
is for the destination network, the second column indicates the next router
along the shortest path to the destination network, and the third column
indicates the number of hops (i.e., the number of networks that have to
be traversed, including the destination network, to get to the destination
network along the shortest path). For this example, the table indicates
that to send a datagram from router D to destination network 1, the datagram
should be first sent to neighboring router A; moreover, the table indicates
that destination network 1 is two hops away along the shortest path. Also
note that the table indicates that network 30 is seven hops away via router
B. In principle, the routing table should have one row for each network
in the AS. (Although aggregation, a topic beyond the scope of this book,
can be used to aggregate entries.) It should also have at least one row
for networks that are outside of the AS. The table in Figure 4.5-3, and
the subsequent tables to come, are only partially complete.
|
network |
router |
of hops to destination |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Figure 4.5-3: Routing table in router D before receiving advertisement from router A.
Now suppose that 30 seconds later, router D receives from router A the advertisement shown in Figure 4.5-4. Note that this advertisement is nothing other but the routing table in router A! This routing table says, in particular, that network 30 is only 4 hops away from router A.
|
network |
router |
of hops to destination |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Router D, upon receiving this advertisement, merges the advertisement (Figure 4.5-4) with the "old" routing table (Figure 4.5-3). In particular, router D learns that there is now a path through router A to network 30 that is shorter than the path through router B. Thus, router D updates its routing table to account for the "shorter" shortest path, as shown in Figure 4.5-5. How is it, you might ask, that the shortest path to network 30 became shorter. This is because either this decentralized distance vector algorithm was still in the process of converging (see Section 4.2), or new links and/or routers were added to the AS, which changed the actual shortest paths in the network.
|
network |
router |
of hops to destination |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Returning now to the general properties of RIP, if a router does not hear from its neighbor at least once every 180 seconds, that neighbor is considered to be no longer reachable, i.e., either the neighbor has died or the connecting link has gone down. When this happens, RIP modifies its local routing table and then propagates this information by sendind advertisements to its neighboring routers (the ones that are still reachable). A router can also request information about its neighbor's cost to a given destination using RIP's request message. Routers send RIP request and response messages to each other over UDP using port number 520.The UDP packet is carried between routers in a standard IP packet. The fact that RIP uses a transport layer protocol (UDP) on top of a network layer protocol (IP) to implement network layer functionality (a routing algorithm) may seem rather convoluted (it is!). Looking a little deeper at how RIP is implemented will clear this up.
Figure 4.5-6 sketches how RIP is typically implemented in a UNIX system, e.g., for example, a UNIX workstation serving as a router. A process called routed (pronounced "route dee") executes the RIP protocol, i.e., maintains the routing table and exchanges messages with routed processes running in neighboring routers. Because RIP is implemented as an application-layer process (albeit a very special one that is able to manipulate the routing tables within the UNIX kernel), it can send and receive messages over a standard socket and use a standard transport protocol. Thus, RIP is an application-layer protocol (see Chapter 2), running over UDP.
Finally, let us take a quick look at a RIP routing table. The RIP routing table below in Figure 4.5-7 is taken from a UNIX router giroflee.eurecom.fr. If you give a netstat -rn command on a UNIX system, you can view the routing table for that host or router. Performing a netstat on giroflee.eurecom.fr yields the following routing table:
OSPF was conceived as the successor to RIP and as such has a number of advanced features. At its heart, however, OSPF is a link-state protocol that uses flooding of link state information and a Dijkstra least cost path algorithm. With OSPF, a router constructs a complete topological map (i.e., a directed graph) of the entire autonomous system. The router then locally runs Dijkstra's shortest path algorithm to determine a shortest path tree to all networks with itself as the root node. The router's routing table is then obtained from this shortest path tree. Individual link costs are configured by the network administrator.
Let us now contrast and compare the advertisements sent by RIP and OSPF. With OSPF, a router periodically sends routing information to all other routers in the autonomous system, not just to its neighboring routers. This routing information sent by a router has one entry for each of the router's neighbors; the entry gives the distance (i.e., link state) from the router to the neighbor. On the otherhand, a RIP advertisement sent by a router contains information about all the networks in the autonomous system, although this information is only sent to its neighboring routers. In a sense, the advertising techniques of RIP and OSPF are duals of each other.
Some of the advances embodied in OSPF include the following:
Within each area, one of more area border routers are responsible for routing packets outside the area. Exactly one OSPF area in the AS is configured to be the backbone area. The primary role of the backbone area is to route traffic between the other areas in the AS. The backbone always contains all area border routers in the AS and may contain non border routers as well. Inter-area routing within the AS requires that the packet be first routed to an area border router (ntradomain routing), then routed though the backbone to the area border router that is in the destination area, and then routed to the final destination.
A diagram of a hierarchically structured OSPF network is shown in Figure 4.4-5 . We can identify four types of OSPF routers in Figure 4.5-7:
While BGP has the same general flavor as the distance vector protocol that we studied in Section 4.2, it is more appropriately characterized as a path vector protocol. This is because BGP in a router does not propagate cost information (e.g., number of hops to a destination), but instead propagates path information, such as the sequence of ASs on a route to a destination AS. We will examine the path information in detail shortly. We note though that while this information includes the names of the ASs on a route to the destination, they do not contain cost information. Nor does BGP specify how a specific route to a particular destination should be chosen among the routes that have been advertised. That decision is a policy decision that is left up to the domain's administrator. Each domain can thus choose its routes according to whatever criteria it chooses (and need not even inform its neighbors of its policy!) -- allowing a significant degree of autonomy in route selection. In essence, BGP provides the mechanisms to distribute path information among the interconnected autonomous systems, but leaves the policy for making the actual route selections up to the network administrator.
Let's begin with a grossly simplified description of how BGP works. This will help us see the forest through the trees. As discussed in Section 4.3, as far as BGP is concerned, the whole Internet is a graph of ASs, and each AS is identified by an AS number. At any instant of time, a given AS X may, or may not, know of a path of ASs that lead to a given destination AS Z. As an example, suppose X has listed in its BGP table such a path XY1Y2Y3Z from itself to Z. This means that X knows that it can send datagrams to Z through the ASs X, Y1, Y2 and Y3, Z. When X sends updates to its BGP neighbors (i.e., the neighbors in the graph), X actually sends the enitre path information, XY1Y2Y3Z, to its neighbors (as well as other paths to other ASs). If, for example, W is a neighbor of X, and W receives an advertisement that includes the path XY1Y2Y3Z, then W can list a new entry WXY1Y2Y3Z in its BGP table .However, we should keep in mind that W may decide to not create this new entry for one of several reasons. For example, W would not create this entry if W is equal to (say) Y2, thereby creating an undesirable loop in the routing; or if W already has a path to Z in its tables, and this existing path is preferable (with respect to the metric used by BGP at W) to WXY1Y2Y3Z ; or, finally, if W has a policy decision to not forward datagrams through (say) Y2 .
In BGP jargon, the immediate neighbors in the graph of ASs are called peers. BGP information is proprogated through the network by exchanges of BGP messages between peers. The BGP protocol defines the four types of messages: OPEN, UPDATE, NOTIFICATION and KEEPALIVE.
Very often an AS will have muliple gateway routers that provide connections to other ASs. Even though BGP is an inter-AS protocol, it can still be used inside an AS as a pipe to exchange BGP updates among gateway routers belonging to the same AS. BGP connections inside an AS are called Internal BGP (IBGP), whereas BGP connections between ASs are called External BGP (EBGP).
As noted above, BGP, which is the successor to EGP, is becoming the de facto standard for inter-AS routing for the public Internet. BGP is used for example at the major network access points (NAP's) where major Internet carries connect to each other and exchange traffic. To see the contents of today's (less than four hours out of date) BGP routing table (large!) at one of the major NAP's in the US (which include Chicago and San Francisco ), click here.
This completes our brief introduction of BGP. Although BGP is complex, it plays a central role in the Internet. We encourage readers to see the references [Halabi 97] and [Huitema 95] to learn more about BGP.
Having now studied the details of specific inter-AS and intra-AS
routing protocols deployed in today's Internet, let us conclude by considering
perhaps the most fundamental question we could ask about these protocols
in the first place (hopefully, you have been wondering this all along,
and have not lost the forest for the trees!):
[Cisco97] Interior
Gateway Routing Protocol and Enhanced IGRP
[RFC 792] J. Postel, "Internet Control Message
Protocol, " RFC
792, Sep-01-1981.
[RFC 904] D. Mills, "Exterior Gateway Protocol
Formal Specification," RFC
791, April 1984.
[RFC 1058] C.L. Hendrick, "Routing Information
Protocol," RFC
1058, June 1988.
[RFC 1256] S. Deering, "ICMP Router Discovery
Messages," RFC
1256, Sept. 1991.
[RFC 1584] J. Moy, "Multicast Extensions to
OSPF," RFC
1584, March 1994.
[RFC 1723] G. Malkin, RIP Version 2 - Carrying
Additional Information. RFC
1723, November 1994.
[RFC 1771] Y. Rekhter and T. Li, "A Border
Gateway Protocol 4 (BGP-4)," RFC
1771, March 1995.
[RFC 1772] Y. Rekhter and P. Gross, "Application
of the Border Gateway Protocol in the Internet," RFC
1772, March 1995.
[RFC 1773] P. Traina, "Experience with the BGP-4
protocol," RFC
1773, March 1995
[RFC 2002] C. Perkins, "IP Mobility Support,"
RFC
2002, 1996.
[RFC 2178] J. Moy, "Open Shortest Path First
Version 2", RFC
2178, July 1997.
[Halabi 97] B. Halabi, Internet Routing Architectures,
Cisco Systems Publishing, Indianapolis, 1997.
[Huitema 95] C. Huiteman, Routing in the
Internet, Prentice Hall, New Jersey, 1995.
If you are interested in an Internet Draft relating to a certain subject or protocol enter the keyword(s) here.