In this tutorial, you will learn about Distance Vector Routing and Link State Routing. After reading this tutorial, you will understand the differences between Distance Vector Routing and Link State Routing, how routing tables are created in a DVR, and how link-state packets are created and distributed in link-state routing.
Contents:
- Routing Algorithms
- Distance Vector Routing
- Delay in DVR
- The Count-to-Infinity Problem
- Link State Routing
- Learning about the Neighbors
- Setting Link Cost & Building Link State Packets
- Distributing the Link State Packets
- Distance Vector Routing Vs Link State Routing
Routing Algorithms
Routing the packets from sender to receiver machine is one of the responsibilities of the network layer. Here, routing creates problems when the sender and receiver are not on the same segment. Hence routing algorithms are used to decide the best path to send the packets.
- In datagram networks, the routing algorithm has to make decisions each time a packet arrives because the best route may change from the previous one, whereas in virtual-circuit networks, routing algorithms make decisions only when a new virtual circuit is created.
- There are two processes taking place during the transmission of packets. The first is to forward packets, and the second is to update the routing table.
- Routing algorithms ensure correctness, simplicity, robustness, consistency, fairness, and efficiency when a route is chosen to send packets.
- Several routing protocols are used to make routing decisions. In this, we will study two dynamic routing algorithms, distance vector routing, and link-state routing.
Distance Vector Routing (DVR)
Distance vector routing is one of the most popular dynamic algorithms, which is also known as the Bellman-Ford routing algorithm.
- The distance vector routing algorithm is used to maintain a router’s routing table, return the best-known distance to each destination, and find the best route.
- In a DVR, the routing table is known as a vector. Each router knows the best route to reach each destination.
- In the DVR algorithm, the routing table has two entries, the outgoing line used for the destination and the estimated distance to the destination.
- Distance in DVR can be measured as a number of hops or other metric values.
- If the DVR uses hops as a metric, the distance is one hop. If the metric is the propagation delay, then the distance is the timestamp.
Delay in DVR
Now, assume that the DVR is using the delay metric, and each router knows the delay it takes to reach each of its neighbors. Each router sends a list of its estimated delays to each destination after every t milli-second. Based on the delay, the router finds the best path to send packets.
The diagram below shows how the router creates the delay table in the DVR.
- As shown in the figure, Router-A has 10 msec, 23 msec, 38 msec, etc., respectively, the delay in Router-B, Router-C, Router-D, etc.
- Now, Router-J measured the delay in its neighbors Router-A, Router-I, Router-H, and Router-K, which are 6, 8, 10, and 4 msec, respectively.
- Router-J wants to communicate with Router-G. Therefore, it has to create a new route for Router-G. Since router-J knows the delays of A, I, H, and K, it tries to find a path through the available router delays.
- So, Router-A claims it reaches G in 16 msec, and Router-J reaches Router-A in 6 msec, so Router-J reaches Router-G in (16+6) 22 msec.
- Similarly, Router-J through Router-I, Router-H, and Router-K calculates the delays in Router-G as (29 + 8) 37, (4 + 10) 14, and (29 + 4) 33 msec, respectively.
- The best and optimal route from Router-J to Router-G is 14, so Router-J makes an entry in its routing table that the delay of G through Router-H is 14 msec.
The Count-to-Infinity Problem
Using DVR, routers find the shortest path to send packets. But in practice, it has a serious drawback that slows down the network.
The figure below explains the count-to-infinity problem.
- As shown in the figure, initially, the distance of Router-B, Router-C, Router-D, and Router-E from Router-A is 2, 3, 4, and 5 hops, respectively.
- Suddenly, the link between A and B goes down for a short while. When the first exchange of packets occurs, B hears nothing from A because the link between A and B is down.
- Fortunately, B communicates with C and C says that I have a path to reach A, which is of length 3. Therefore, B will first think that C’s path runs through B and that C may have more links with different paths to A of length 2. Router-B will update the table and thinks it can reach A through C with a path length of 4 (1+3).
- On the other hand, Router-D and Router-E do not update their tables for A on the first exchange.
- On the second exchange, C learns the neighbor table and notices that each of its neighbors claims it has a path of length 4. C chooses a path at random from the available paths of the other router’s routing table and builds its new distance to router-A, which is 5.
- This process continues and reaches an infinite state, causing network congestion.
- We can prevent the count-to-infinity problem by adding a sequence number to the routing table.
Link State Routing
The count-to-infinity problem often takes a long time to converge once the network topology is changed. Consequently, the DVR algorithm is replaced by link-state routing.
In link-state routing, each router performs the following steps on the network.
- Finds neighbors on a network and learns their addresses.
- Updates the routing table by setting a distance metric for each of its neighbors.
- Creates a packet and uses all the information received from another router or device to send the packet.
- Sending packets and receiving packets from other routers.
- Finds the optimal and shortest path to every other router.
Learning about the Neighbors
The main function of a router is to know about its neighbors on the network. It sends HELLO packets to each point-to-point line. When other routers receive the HELLO packet, they send back a reply giving its name. Router names are globally unique. The situation becomes more complicated when two or more routers are connected to a broadcast link.
The figure below explains the broadcast LAN status in a network.
- Routers A, C, and F are directly connected, as shown in the figure. They are all connected to one or more additional routers.
- If we model the LAN as multiple point-to-point links, it increases the size of the network topology and increases the number of useless messages. To prevent this, the topology must be treated as a node itself, as shown in the right-side figure.
- Routers A, C, and F are connected to artificial node N, which prevents loss of bandwidth.
Setting Link Cost & Building Link State Packets
Determining link cost and generating link-state packets are the two main functionalities of link-state routing.
Setting Link Costs: In a network, each link has a distance or cost metric for finding the shortest path. The cost of reaching neighboring routers is manually configured by the network operator or is set automatically.
- In link-state routing, the cost is proposed inversely to the bandwidth of the network. For example, a 1-Gbps Ethernet cable costs 1, and a 100-Mbps Ethernet cable costs 10.
- If the network is geographically spread, a delay is a significant factor. Delay affects the cost of the link so that paths on shorter links are the better choice.
- Using the ping tool, the delay is measured by sending ECHO packets to other routers. The router estimates the delay by measuring the round-trip time and dividing it by two.
Building Link State Packets: After receiving all the information necessary to exchange packets, the router creates a packet containing all the data. Routers have an identifier to identify packets, followed by a sequence number and age of a packet.
The diagram below explains the link state packets for the network.
- As shown in the figure, there are six routers connected to a network. Each router has a sequence number and the age of the packets.
- Each router on the network creates a table. In the table, the sequence number and age of the packets are written.
- It is difficult to decide at what point in time the link-state packet should be create. One possibility is to build up periodic link-state packets or build them up when a critical event occurs, such as a broken link or a neighboring router going down or coming back appreciably again.
Distributing the Link State Packets
Distributing link-state packets is the tricky part of the link-state routing algorithm because all routers have to receive all link-state packets quickly and reliably. If routers in the network are using different topology versions, there may be issues with loops, unreachable machines, etc.
- Flooding is used to distribute link-state packets to all the routers present on a network. Each packet has a sequence number.
- Routers keep track of all the (source router, sequence number) pairs they receive. If the received pair is new, it forwards it to all its outgoing links.
- If the router detects the pair as a duplicate, it will discard it. If the sequence number of a received packet is less than the sequence number of the previously received packets, the router rejects it.
Problems with a Link State Routing Algorithm:
- First, if the router crashes during transmission over the network, it loses track of its sequence number. If the sequence number starts from 0 again, the next packet sent by the sender will be considered as a duplicate at the receiver.
- Second, if the sequence number on a link is corrupted, it will be rejected as obsolete.
- The above problem can be solved by including the age of each packet after the sequence number, with the age decrementing once per second. As soon as age becomes zero, the information stored on the router is discarded.
The figure below explains the packet buffer of Router B in Figure 4.
- As shown in the figure, Source, Sequence Number, Age, Flags, and Data are the columns of the table.
- The table shows where the packet originated, its serial number, age, flags, and data.
- Here the send flag means that the packet should be sent on the indicated link and the acknowledge flag means that it has been accepted there.
- As you can see in the diagram, the packet comes from Router-A. It should be sent to Router-C and Router-F and acknowledged to A, as indicated by flag bits.
- Similarly, Router-F must forward the packet to Router-A and Router-C and acknowledged to Router-F.
- Router-E packets are to be sent only to Router-C but must be acknowledged for both Router-A and Router-F, as indicated by bits.
Distance Vector Routing Vs Link State Routing
Here is a comparison of Distance Vector Routing and Link State Routing based on various parameters:
Parameter | Distance Vector Routing | Link State Routing |
---|---|---|
Routing Information | Routers share their routing tables with their neighbors. | Routers share information about the entire network topology. |
Convergence | Slower convergence. | Faster convergence. |
Updates | Periodic updates are sent to neighboring routers. | Updates are triggered by changes in the network topology. |
Algorithm | Uses the Bellman-Ford algorithm. | Uses Dijkstra’s algorithm. |
Information Storage | Stores only the best path to each destination. | Stores the entire network topology. |
Resource Utilization | Lower memory and CPU usage. | Higher memory and CPU usage due to detailed information. |
Complexity | Simpler to implement. | More complex to implement. |
Scalability | Less scalable due to slow convergence and routing loops. | Highly scalable with faster convergence and no routing loops. |
Network Overhead | Can generate more overhead due to frequent updates. | Generally generates less overhead with event-triggered updates. |
Routing Loops | Susceptible to routing loops. | Less susceptible to routing loops due to global view. |
Example Protocols | RIP (Routing Information Protocol), IGRP (Interior Gateway Routing Protocol). | OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System). |
Key Points to Remember
Here is the list of key points we need to remember about “Distance Vector Routing & Link State Routing”.
- Routing algorithms ensure correctness, simplicity, robustness, consistency, fairness, and efficiency when a route is chosen to send packets.
- Several routing protocols are used to make routing decisions. In this, we have seen two dynamic routing algorithms, distance vector routing, and link-state routing.
- In the DVR algorithm, the routing table has two entries, the outgoing line used for the destination and the estimated distance to the destination.
- If the DVR is using the delay metric and each router knows the delay it takes to reach each of its neighbors, each router sends a list of its estimated delays to each destination after every t milli-second. Based on the delay, the router finds the best path to send packets.
- The count-to-infinity problem often takes a long time to converge once the network topology is changed. Consequently, the DVR algorithm is replaced by link-state routing.
- The link-state routing algorithm performs the four steps as follows:
- Learning about the neighbors
- Setting Link Costs
- Building Link State Packets
- Distributing the Link State Packets