Unicast Routing Protocols

unicast routing protocols
introduction
an internet is a combination of networks connected by routers. when a datagram goes from a source to a destination, it will probably pass through many routers until it reaches the router attached to the destination network.

cost or metric
a router receives a packet from a network and passes it to another network. a router is usually attached to several networks. when it receives a packet, to which network should it pass the packet? the decision is based on optimization: which of the available pathways is the optimum pathway? what is the definition of the term optimum? one approach is to assign a cost for passing through a network. we call this cost a metric. high cost can be thought of as something bad low cost can be thought of something good. for example, if we want to maximize the throughput in a network, the high throughput means low cost and the low throughput means high cost. as another example, if we want to minimize the delay, low delay is low cost and high delay is high cost.

static versus dynamic routing tables
a routing table can be either static or dynamic. a static table is one with manual entries. a dynamic table, on the other hand, is one that is updatingd automatically when there is a change somewhere in the internet. today, an internet needs dynamic routing tables. the tables need to be updatingd as soon as there is a change in the internet. for instance, they need to be updatingd when a link is down, and they need to be updatingd whenever a better route has been found.

routing protocol
routing protocols have been created in response to the demand for dynamic routing tables. a routing protocol is a combination of rules and procedures that lets routers in the internet inform each other of changes. it allows routers to share whatever they know about the internet or their neighborhood. the sharing of information allows a router in san francisco to know about the failure of a network in texas. the routing protocols also include procedures for combining information received from other routers. routing protocols can be either an interior protocol or an exterior protocol. an
interior protocol handles intradomain routing an exterior protocol handles interdomain routing.

11.2 intra- and inter-domain routing
today, an internet can be so large that one routing protocol cannot handle the task of updating the routing tables of all routers. for this reason, an internet is divided into autonomous systems. an autonomous system (as) is a group of networks and routers under the authority of a single administration. routing inside an autonomous system is referred to as intra-domain routing. routing between autonomous systems is referred to as inter-domain routing. each autonomous system can choose one or more intradomain routing protocols to handle routing inside the autonomous system. however, only one interdomain routing protocol handles routing between autonomous systems. see figure 11.1.

several intra-domain and inter-domain routing protocols are in use. in this lecture, we cover only the most popular ones. we discuss two intra-domain routing protocols: distance vector and link state. we also introduce one inter-domain routing protocol: path vector (see figure 11.2). routing information protocol (rip) is the implementation of the distance vector protocol. open shortest path first (ospf) is the implementation of the link state protocol. border gateway protocol (bgp) is the implementation of the path vector protocol. rip and ospf are interior routing protocols bgp is an exterior routing protocol.


routing information protocol (rip)
it is an intradomain (interior) routing protocol used inside an autonomous system. it is a very simple protocol based on distance vector routing. rip implements distance vector routing directly with some considerations:
1. in an autonomous system, we are dealing with routers and networks (links), what was described as a node.
2. the destination in a routing table is a network, which means the first column defines a network address.
3. the metric used by rip is very simple the distance is defined as the number of links (networks) that have to be used to reach the destination. for this reason, the metric in rip is called a hop count.
4. infinity is defined as 16, which means that any route in an autonomous system using rip cannot have more than 15 hops.
5. the next node column defines the address of the router to which the packet is to be sent to reach its destination.

figure 11.10 shows an autonomous system with seven networks and four routers. the table of each router is also shown. let us look at the routing table for r1. the table has seven entries to show how to reach each network in the autonomous system. router r1 is directly connected to networks 130.10.0.0 and 130.11.0.0, which means that there are no next hop entries for these two networks. to send a packet to one of the three networks at the far left, router r1 needs to deliver the packet to r2. the next node entry for these three networks is the interface of router r2 with ip address 130.10.0.1. to send a packet to the two networks at the far right, router r1 needs to send the packet to the interface of router r4 with ip address 130.11.0.1. the other tables can be explained similarly.


rip message format
the format of the rip message is shown in figure 11.11.

? command. this 8-bit field specifies the type of message: request (1) or response (2).
? version. this 8-bit field defines the version. in this book we use version 1, but at the end of this section, we give some new features of version 2.
? family. this 16-bit field defines the family of the protocol used. for tcp/ip the value is 2.
? network address. the address field defines the address of the destination network. rip has allocated 14 bytes for this field to be applicable to any protocol. however, ip currently uses only 4 bytes. the rest of the address is filled with 0s.
? distance. this 32-bit field defines the hop count (cost) from the advertising router to the destination network.

note that part of the message is repeated for each destination network. we refer to this as an entry.

requests and responses
rip has two types of messages: request and response.
request
a request message is sent by a router that has just come up or by a router that has some time-out entries. a request can ask about specific entries or all entries (see figure 11.12).


response
a response can be either solicited or unsolicited. a solicited response is sent only in answer to a request. it contains information about the destination specified in the corresponding request. an unsolicited response, on the other hand, is sent periodically, every 30 seconds or when there is a change in the routing table. the response is sometimes called an updating packet. figure 11.11 shows the response message format.

example 11.4
figure 11.13 shows the updating message sent from router r1 to router r2 in figure 11.10. the message is sent out of interface 130.10.0.2. the message is prepared. router r1 has obtained information about networks 195.2.4.0, 195.2.5.0, and 195.2.6.0 from router r2. when r1 sends an updating message to r2, it replaces the actual value of the hop counts for these three networks with 16 (infinity) to prevent any confusion for r2. the figure also
shows the table extracted from the message. router r2 uses the source address of the ip datagram carrying the rip message from r1 (130.10.02) as the next hop address. router r2 also increments each hop count by 1 because the values in the message are relative to r1, not r2.
timers in rip
rip uses three timers to support its operation (see figure 11.14). the periodic timer controls the sending of messages, the expiration timer governs the validity of a route, and the garbage collection timer advertises the failure of a route.

periodic timer
the periodic timer controls the advertising of regular updating messages. although the protocol specifies that this timer must be set to 30 s, the working model uses a random number between 25 and 35 s. this is to prevent any possible synchronization and therefore overload on an internet if routers updating simultaneously. each router has one periodic timer that is randomly set to a number between 25 and 35. it counts down when zero is reached, the updating message is sent, and the timer is randomly set once again.

expiration timer
the expiration timer governs the validity of a route. when a router receives updating information for a route, the expiration timer is set to 180 s for that particular route. every time a new updating for the route is received, the timer is reset. in normal situations this occurs every 30 s. however, if there is a problem on an internet and no updating is received within the allotted 180 s, the route is considered expired and the hop count of the route is set to 16, which means the destination is unreachable. every route has its own expiration timer.

garbage collection timer
when the information about a route becomes invalid, the router does not immediately purge that route from its table. instead, it continues to advertise the route with a metric value of 16. at the same time, a timer called the garbage collection timer is set to 120 s for that route. when the count reaches zero, the route is purged from the table. this timer allows neighbors to become aware of the invalidity of a route prior to purging.

example 11.5
a routing table has 20 entries. it does not receive information about five routes for 200 s. how many timers are running at this time?
solution
the 21 timers are listed below:
periodic timer: 1
expiration timer: 20 - 5 = 15
garbage collection timer: 5

rip version 2
rip version 2 was designed to overcome some of the shortcomings of version 1. the designers of version 2 have not augmented the length of the message for each entry. they have only replaced those fields in version 1 that were filled with 0s for the tcp/ip protocol with some new fields.

message format
figure 11.15 shows the format of a rip version 2 message. the new fields of this message are as follows:
? route tag. this field carries information such as the autonomous system number. it can be used to enable rip to receive information from an interdomain routing protocol.
? subnet mask. this is a 4-byte field that carries the subnet mask (or prefix). this means that rip2 supports classless addressing and cidr.
? next-hop address. this field shows the address of the next hop. this is particularly useful if two autonomous systems share a network (a backbone, for example). then the message can define the router, in the same autonomous system or another autonomous system, to which the packet next goes.


classless addressing
probably the most important difference between the two versions of rip is classfulversus classless addressing. ripv1 uses classful addressing. the only entry in the message format is the network address (with a default mask). ripv2 adds one field for the subnet mask, which can be used to define a network prefix length. this means that in this version, we can use classless addressing.

multicasting
version 1 of rip uses broadcasting to send rip messages to every neighbor. in this way, all the routers on the network receive the packets, as well as the hosts. rip version 2, on the other hand, uses the all-router multicast address to send the rip messages only to rip routers in the network.