We first discuss distance vector routing. This method sees an AS, with all routers and networks, as a graph, a set of nodes and lines (edges) connecting the nodes. A router can normally be represented by a node and a network by a link connecting two nodes, although other representations are also possible.
The graph theory used an algorithm called Bellman-Ford (also called Ford-Fulkerson) for a while to find the shortest path between nodes in a graph given the distance between nodes. We first discuss this algorithm before we see how it can be modified to be used for updating routing tables in a distance vector routing.
Bellman Ford Algorithm
Let us briefly discuss the Bellman-Ford algorithm. The algorithm can be used in many applications in graph theory. If we know the cost between each pair of nodes, we can use the algorithm to find the least cost (shortest path) between any two nodes.
Figure shows a map with nodes and lines. The cost of each line is given over the line; the algorithm can find the least cost between any two nodes. For example, if the nodes represent cities and the lines represent roads connecting them, the graph can find the shortest distance between any two cities.
The algorithm is based on the fact that if all neighbors of node i know the shortest distance to node j, then the shortest distance between node i and j can be found by adding the distance between node i and each neighbor to the neighbor’s shortest distance to node j and then select the minimum, as shown in figure.
Although the principle of the Bellman-Ford algorithm is very simple and intuitive, the algorithm itself looks circular. How have the neighbors calculated the shortest path to the destination? To solve the problem, we use iteration. We create a shortest distance table (vector) for each node using the following steps:
- The shortest distance and the cost between a node and itself is initialized to 0.
- The shortest distance between a node and any other node is set to infinity. The cost between a node and any other node should be given (can be infinity if the nodes are not connected).
- The algorithm repeat as shown in figure until there is no more change in the shortest distance vector.
Table shows the algorithm in pseudocode.
1 Bellman_Ford ( )
2 {
3 // Initialization
4 for (i = 1 to N; for j = 1 to N)
5 {
6 if(i == j) Dij = 0 Cij = 0
7 else Dij = ∞ Cij = cost between i and j
8 }
9 // Updating
10 repeat
11 {
12 for (i = 1 to N; for j = 1 to N)
13 {
14 Dij ← minimum [(Ci1 + D1j) ... (CiN + DNj)]
15 } // end for
16 } until (there was no change in previous iteration)
17 } // end Bellman-Ford
Distance Vector Routing Algorithm
The Bellman-Ford algorithm can be very well applied to a map of roads between cities because we can have all of the initial information about each node at the same place. We can enter this information into the computer and let the computer hold the intermediate results and create the final vectors for each node to be printed.
In other words, the algorithm is designed to create the result synchronously. If we want to use the algorithm for creating the routing table for routers in an AS, we need to change the algorithm:
- In distance vector routing, the cost is normally hop counts (how many networks are passed before reaching the destination). So the cost between any two neighbors is set to 1.
- Each router needs to update its routing table asynchronously, whenever it has received some information from its neighbors. In other words, each router executes part of the whole algorithm in the Bellman-Ford algorithm. Processing is distributive.
- After a router has updated its routing table, it should send the result to its neighbors so that they can also update their routing table.
- Each router should keep at least three pieces of information for each route: destination network, the cost, and the next hop. We refer to the whole routing table as Table, to the row i in the table as Tablei, to the three columns in row i as Tablei.dest, Tablei.cost, and Tablei.next.
- We refer to information about each route received from a neighbor as R (record), which has only two pieces of information: R.dest and R.cost. The next hop is not included in the received record because it is the source address of the sender.
Table shows the algorithm in pseudocode.
1 Distance_Vector_Algorithm ( )
2 {
3 // At startup
4 for (i = 1 to N) // N is number of ports
5 {
6 Tablei.dest = address of the attached network
7 Tablei.cost = 1
8 Tablei.next = — // Means at home
9 Send a record R about each row to each neighbor
10 } // end for loop
11
12 // Updating
13 repeat (forever)
14 {
15 Wait for arrival of a record R from a neighbor
16 Update (R, T) // Call update module
17 for (i = 1 to N) // N is the current table size
18 {
19 Send a record R about each row to each neighbor
20 }
21 } // end repeat
22
23 } // end Distance_Vector
24 Update (R, T) // Update module
25 {
26 Search T for a destination matching the one in R
27 if (destination is found in row i)
28 {
29 if (R.cost + 1 < Ti.cost or R.next == Ti.next)
30 {
31 Ti.cost = R.cost + 1
32 Ti.next = Address of sending router
33 }
34 else discard the record // No change is needed
35 }
36 else
37 // Insert the new router
38 {
39 TN +1.dest = R.dest
40 TN +1.cost = R.cost + 1
41 TN +1.next = Address of sending router
42 Sort the table according to destination address
43 }
44 } // end of Update module
Lines 4 to 10 show the initialization at the start-up. The router creates a preliminary routing table that can only be used to route packets to the networks directly attached to its interfaces. For each entry in the routing table, it sends a record with only two fields: destination address and the cost to each neighbor.
The router updates itself whenever it receives a record from a neighbor. After each update, the route sends a record for each entry in the routing table to its neighbors to let them also update themselves.
Lines 23 to 47 give the details of updating process. When a record arrives, the router searches for the destination address in the routing table.
- If the corresponding entry is found, two cases need to be checked and the route information should be changed.
- If the record cost plus 1 is smaller than the corresponding cost in the table, it means the neighbors have found a better route to that destination.
- If the next hop is the same, it means some change has happened in some part of the network. For example, suppose a neighbor has previously advertised a route to a destination with cost 3, but now there is no path between this neighbor and that destination. The neighbor advertises this destination with cost value infinity. The receiving router must not ignore this value even though its old entry is smaller. The old route does not exist any more.
- If the entry is not in the table, the router adds it to the table and sorts the table according to the destination address.
| Read More Topics |
| Intra – and Inter Domain Routing System |
| Two level addressing in IPv4 |
| Glossary for computer network |
