Routing by Rumor

Figure 4.3 shows a distance vector algorithm in action. In this example, the metric is hop count. At time t0, routers A through D have just become active. Looking at the route tables across the top row, at t0 the only information any of the four routers has is its own directly connected networks. The tables identify these networks and indicate that they are directly connected by having no next-hop router and by having a hop count of 0. Each of the four routers will broadcast this information on all links.

Figure 4.3. Distance vector protocols converge hop-by-hop.

Figure 4.3. Distance vector protocols converge hop-by-hop.

At time t1, the first updates have been received and processed by the routers. Look at router A's table at t1. Router B's update to router A said that router B can reach networks 10.1.2.0 and 10.1.3.0, both 0 hops away. If the networks are 0 hops from B, they must be 1 hop from A. Router A incremented the hop count by 1 and then examined its route table. It already knew about 10.1.2.0, and the hop count (0) was less than the hop count B advertised, (1), so A disregarded that information.

Network 10.1.3.0 was new information, however, so A entered this in the route table. The source address of the update packet was router B's interface (10.1.2.2) so that information is entered along with the calculated hop count.

Notice that the other routers performed similar operations at the same time t1. Router C, for instance, disregarded the information about 10.1.3.0 from B and 10.1.4.0 from C but entered information about 10.1.2.0, reachable via B's interface address 10.1.3.1, and 10.1.5.0, reachable via C's interface 10.1.4.2. Both networks were calculated as 1 hop away.

At time t2, the update period has again expired and another set of updates has been broadcast. Router B sent its latest table; router A again incremented B's advertised hop counts by 1 and compared. The information about 10.1.2.0 is again discarded for the same reason as before. 10.1.3.0 is already known, and the hop count hasn't changed, so that information is also discarded. 10.1.4.0 is new information and is entered into the route table.

The network is converged at time t3. Every router knows about every network, the address of the next-hop router for every network, and the distance in hops to every network.

Time for an analogy. You are wandering in the Sangre de Cristo mountains of northern New Mexico—a wonderful place to wander if you aren't lost. But you are lost. You come upon a fork in the trail and a sign pointing west, reading "Taos, 15 miles." You have no choice but to trust the sign. You have no clue what the terrain is like over that 15 miles; you don't know whether there is a better route or even whether the sign is correct. Someone could have turned it around, in which case you will travel deeper into the forest instead of to safety!

Distance vector algorithms provide road signs to networks.151 They provide the direction and the distance, but no details about what lies along the route. And like the sign at the fork in the trail, they are vulnerable to accidental or intentional misdirection. Following are some of the difficulties and refinements associated with distance vector algorithms.

[51 The road sign analogy is commonly used. You can find a good presentation in Radia Perlman's Interconnections, pp. 205-210.

0 0

Post a comment