21.10 ROUTING PROTOCOLS

< Day Day Up >

When a packet arrives at a router, the router has to make a decision as to which node/router the packet has to be sent to. This is done using the routing protocols.

When a router receives a packet, the header information has to be analyzed to find the destination address, and the packet has to be forwarded toward the destination. The router does this job with the help of the routing tables.

Each end system and router maintains a routing table. The routing table can be static or dynamic. In static routing, each system maintains a routing table that does not change often. In dynamic routing, the routing table is upgraded periodically. Recording of the route taken by a packet can be supported—each router appends its IP address to the datagram. This is used mainly for testing and debugging of the network. While routing the packet, the decision has to be made with the following issues in mind.

Datagram lifetime
Segmentation and reassembly
Error control
Flow control

Datagram lifetime: If dynamic routing is used, the possibility for a datagram to loop indefinitely through the Internet exists. To avoid this, each datagram can be marked with a lifetime—a hop count. When a datagram is passed through a router, the count is decreased. Alternatively, a true measure of time can be used, which requires a global clocking mechanism. When a datagram is received by a router with a hop count of zero, then the datagram is discarded.

If there is congestion in the network, the router may forward the packet through an alternate route. However, if source routing is specified in the packet, then the packet has to be routed according to these instructions.

Segmentation and reassembly: When a router receives a datagram and if it has to be routed to a network that supports a smaller packet size, the datagram has to be broken into small fragments, which is known as segmentation. Segmentation is done by routers. Reassembly is done by end systems and not routers because a large buffer is required at the router and all datagrams must pass through the same router, in which case dynamic routing is not possible.

Error control: Datagrams may be discarded by a router due to lifetime expiration, congestion, or error in the datagram. Hence, IP does not guarantee successful delivery of datagrams.

Flow control: If a router receives datagrams at a very fast rate and cannot process the datagrams at that rate, the router may send flow control packets requesting reduced data flow.

Consider an internet in which a number of networks are interconnected through routers. When a datagram has to be sent from one node on one network to a node on another network, the path to be taken by the datagram is decided by the routing algorithms. Each router receives the datagram and makes a decision as to the next hop. This is a complicated mechanism because:

If the IP datagram specifies the option for source routing, the datagram has to be routed per the instructions.
The datagram length may vary and, based on the length, the datagram may need to be forwarded to different routers because not all routers may be able to handle large datagrams. (Though they can fragment it, it may result in too much delay, or the do-not-fragment bit may have been set.)
The network may get congested, and some routes may be experiencing traffic jams. In such cases, to ensure no packet loss, alternate routes may need to be chosen.
The path to be chosen has to be the shortest, to reduce load on the network and the delay.

In this section, we will study the routing protocols. Note that, though routing is the function of a router, hosts also may be involved in routing under special circumstances. For instance, a network may have two routers that provide connections to other networks. A host on this network can forward the datagram to one of the routers. (Which router is the issue.) Similarly, multihomed hosts are involved in routing decisions. In the following subsections, we will discuss routing as applied to the routers.

21.10.1 Direct Delivery

Consider a LAN running TCP/IP protocol suite. Delivering an IP datagram to a node is straightforward; it does not involve any routers. Because the IP address has the network ID as a field, and the source and the destination have the same network ID, the datagram is delivered directly to the destination. This is known as direct delivery.

If the source and the destination have the same network ID, the datagram is directly delivered to the destination. This is known as direct delivery.

Consider a case in which a LAN is connected to the Internet through a router. After the datagram travels across the Internet and reaches the final destination's router, the direct delivery mechanism is used for handing over the datagram to the destination.

21.10.2 Indirect Delivery

On the Internet, between the source and the destination, there are many routers. Each router has to get the datagram and forward it to the next router toward the destination. This is known as indirect delivery. The routing has to be such that finally there should be one router that will deliver the datagram to the destination using the direct delivery mechanism.

In indirect delivery, between the source and the destination, there may be a number of routers. In such a case, each router has to forward the datagram to another router. This is known as indirect delivery.

There are a number of mechanisms for indirect routing.

Routing Tables and Next-Hop Routing

Each router and host can have a table, known as the routing table, that contains the destination network address (not the host address) and the router to which the datagram has to be forwarded. When a datagram arrives, the network ID portion is examined, and the routing table is consulted to find the next router to which the datagram is to be forwarded. This mechanism reduces the size of the routing table because we need not store the destination host addresses; only the network addresses are required. Each entry in a routing table is in the format.

Destination network IP address: IP address of the next router to which datagram is to be forwarded.

The next router is called the next-hop router, and routing based on this type of routing tables is called next-hop routing. If the routing table does not contain an entry for a destination network address, the datagram is sent to a default router.

Each entry in a routing table will be in the format, destination network IP address: IP address of the next router to which the datagram is to be forwarded.

Adaptive Routing

In this routing mechanism, the routing of packets is based on information about failure of links and congestion. The advantages of this mechanism are improved performance of the network and less congestion. However, the disadvantages are processing burden on routers and traffic burden on network to send routing information and network status. Information about the failure of links and congestion is shared between routers passing the necessary messages.

In adaptive routing, the routing tables are periodically updated based on the traffic information. The routers need to exchange this traffic information periodically.

First generation Internet (ARPAnet) implemented an adaptive algorithm using estimated delay as the criterion. Each node sends to all the neighbors the estimated delay (or the queue length). The line speed is not considered, and so it is not an accurate algorithm. The routing algorithm was subsequently modified in the second generation Internet, and an adaptive algorithm based on actual delay was implemented. Instead of queue length, delay is measured. When a packet arrives, it is timestamped, and when it is retransmitted the time is noted. Hence, delay is calculated exactly. The average delay is calculated every 10 seconds and sent to all neighboring nodes (known as flooding). The disadvantage with this routing algorithm is that every node tries to get the best route. Subsequently, the routing algorithm has been further refined. The algorithms uses a line utilization parameter for the adaptive algorithm. Instead of the best route, a threshold value is used so that every node will not try to get the best route.

For the routing algorithms, the concept of autonomous systems is important. An internet connected by homogeneous routers, with all routers under the administrative control of a single entity, is called an autonomous system. An autonomous system can use a routing protocol of its choice, but when autonomous systems are interconnected (as in the Internet), a well-defined protocol is a must.

< Day Day Up >