Routing in the Internet

Routing in the Internet

After studying Internet addressing and the IP protocol, we now turn our attention to the Internet's routing protocols; their job is to determine the path taken by a datagram between source and destination. We'll see that the Internet's routing protocols embody many of the principles we learned earlier in this section. The link-state and distance-vector approaches studied in "The Link-State (LS) Routing Algorithms" and "The Distance-Vector (DV) Routing Algorithm" and the notion of an autonomous system considered in "Hierarchical Routing" are all central to how routing is done in today's Internet.

Remember we studied in "Hierarchical Routing" that an autonomous system (AS) is a collection of routers under the same administrative and technical control, and that all run the same routing protocol among themselves. Each AS, in turn, usually includes many subnets (where we use the term subnet in the precise, addressing sense in "IPv4 Addressing").

Intra-AS Routing in the Internet: RIP

An intra-AS routing protocol is used to determine how routing is carried out within an autonomous system (AS). Intra-AS routing protocols are also known as interior gateway protocols. Historically, two routing protocols have been used mostly for routing within an autonomous system in the Internet: the Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). A routing protocol closely related to OSPF is the IS-IS protocol. We first discuss RIP and then look at OSPF.

RIP was one of the earliest intra-AS Internet routing protocols and is still in extensive use today. It traces its origins and its name to the Xerox Network Systems (XNS) architecture. The widespread deployment of RlP was due in great part to its inclusion in 1982 in the Berkeley Software Distribution (BSD) version of UNIX supporting TCP/IP.

RIP is a distance-vector protocol that operates in a manner very close to the idealized DV protocol we studied in "The Distance-Vector (DV) Routing Algorithm". The RIP uses hop count as a cost metric; that is, each link has a cost of 1. In the DV algorithm in "The Distance-Vector (DV) Routing Algorithm", for simplicity, costs were defined between pairs of routers. In RIP (and also in OSPF), costs are actually from source router to a destination subnet. RIP uses the term hop, which is the number of subnets traversed along the shortest path from source router to destination subnet, including the destination subnet. Figure 1 shows an AS with six leaf subnets, The table in the figure indicates the number of hops from the source A to each of the leaf subnets.

The maximum cost of a path is limited to 15, therefore limiting the use of RIP to autonomous systems that are fewer than 15 hops in diameter. Remember that in DV protocols, neighboring routers exchange distance vectors with each other. The distance vector for any one router is the current estimate of the shortest path distances from that router to the subnets in the AS. In RIP, routing updates are exchanged between neighbors approximately every 30 seconds using a RlP response message. The response message sent by a router or host holds a list of up to 25 destination subnets within the AS, as well as the sender's distance to each of those subnets. Response messages are also known as RIP advertisements.

Number of hops from source router A to various subnets

Let's take a look at a simple example of how RIP advertisements work. Examine the portion of an AS illustrated in Figure 2. In this figure, lines connecting the routers indicate subnets. Only selected routers (A, B, C, and D) and subnets (w, x, y, and z) are labeled. Dotted lines indicate that the AS continues on; thus this autonomous system has many more routers and links than are shown. Each router maintains a RIP table known as a routing table. A router's routing table contains both the router's distance vector and the  router's forwarding table. Figure 3 illustrates the routing table for router D. Note that the routing table has three columns. The first column is for the destination subnet, the second column indicates the identity of the next router along the shortest path to the destination subnet, and the third column indicates the number of hops (that is, the number of subnets that have to be traversed, including the destination subnet) to get to the destination subnet along the shortest path. For this example, the table indicates that to send a datagram from router D to destination subnet w, the datagram should first be forwarded to neighboring router A; the table also indicates that destination subnet w is two hops away along the shortest path. Likewise, the table indicates that subnet

A portion of an autonomous system

Routing table in router D before receiving advertisement from router A

z is seven hops away via router B. In principle, a routing table will have one row for each subnet in the AS, although RIP version 2 allows subnet entries to be aggregated using route aggregation techniques similar to those we studied in "The Internet Protocol (IP)". The table in Figure 3, and the subsequent tables to come, are only partially complete.

Now assume that 30 seconds later, router D receives from router A the advertisement shown in Figure 4. Note that this advertisement is nothing other than the routing table information from router A. This information indicates, in particular, that subnet z is only four hops away from router A. Router D, upon receiving this advertisement, merges the advertisement (Figure 4) with the old routing table (Figure 3). In particular, router D learns that there is now a path through router A to subnet z that is shorter than the path through router B. In this way, router D updates its routing table to account for the shorter shortest path, as shown in Figure 5. How is it, you might ask, that the shortest path to subnet z has become shorter? Possibly, the decentralized distance-vector algorithm is still in the process of converging (see "The Distance-Vector (DV) Routing Algorithm"), or perhaps new links and/or routers were added to the AS, thus changing the shortest paths in the AS.

Let's next look at a few of the implementation aspects of RIP. Remember that RIP routers exchange advertisements approximately every 30 seconds. If a router does not   

Advertisement from router A

Routing table in router D after receiving advertisement from router A

hear from its neighbor at least once every 180 seconds, that neighbor is considered to be no longer reachable; that is, either the neighbor has died or the connecting link has gone down. When this happens, RIP modifies the local routing table and then propagates this information by sending 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 segment is carried between routers in a standard IP datagram. 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 6 sketches how RIP is normally implemented in a UNlX system, for instance, a UNIX workstation serving as a router. A process called routed (pronounced "route dee") performs RIP, that is, maintains routing information and exchanges messages with routed processes running in neighboring routers. Because RIP is

Implementation of RIP as the routed daemon

implemented as an application-layer process (although a very special one that is able to manipulate the routing tables within the UNlX kernel), it can send and receive messages over a standard socket and use a standard transport protocol. As shown, RIP is implemented as an application-layer protocol (see "Application Layer") running over UDP.


Tags

internet addressing, routing protocol, interior gateway protocols, rip response message, routing table,

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.