EC310 Lesson 28: Routing Part II objectives
Download 416.85 Kb.
|
- Navigate this page:
- 26 _____ 18 4 35 2 51 3 and the revised LSP without info about router 18: 26 _____
- Router C must be a distance of 6 away from me
- You are Router J
- Example 3 You are Router J
|
(b) After Router G runs Dijkstra's Algorithm, what would be the optimal route from router G to router B, and what would be the total cost of this route? Solution: C. Topology changes. What if a link dies? For instance, in the picture on page 4 above, what if the link connecting Router 18 to Router 26 should die? In link state routing, whenever a router detects a change in the state of its links, it sends a new link state packet. Thus, if the link connecting Router 18 to Router 26 should die, Router 26 will transmit a new LSP with the entries: 26 _____ 35 2
51 3 Note that Router 18 will also detect the loss of a connection to Router 26 and transmit a new LSP as well. These new LSP's will then propagate to all other routers via controlled flooding. You might be wondering: Won't there now be conflicting information in the other routers? For instance, there will now be two pieces of information from Router 26: The old LSP from Router 26 that had info about the link to Router 18: 26 _____ 18 4
35 2 51 3
and the revised LSP without info about router 18: 26 _____ 35 2
51 3 Which of these should another router in the network choose to use to build its network picture and run Dijkstra's Algorithm? To solve this perplexing predicament, yielding a righteous resolution to this difficult dilemma, and thus causing midshipmen merriment, each LSP has a sequence number. That is, a Router stamps its first LSP with sequence number 1, its second LSP with sequence number 2, and so forth. Higher sequence numbers override lower sequence numbers. So, when other routers in the network receive a new LSP from Router 26, they will notice that it has a higher sequence number than the previous LSP, and they will delete the previous (outdated) LSP. Okay…each router has to send LSPs when the router first is connected to the network, and also has to send LSPs whenever the network topology changes. Are there any other times that routers send LSPs? The answer is Yes! All routers also send LSPs periodically, just to make sure all routers are “on the same page.” Where is link state routing used in the Internet? The Internet’s Open Shortest Path First (OSPF) protocol uses link-state routing. (Open refers to the fact that the standard is “open,” i.e., published, non-propriety.) 2. Distance Vector Routing The other routing methodology is Distance Vector Routing (also variously called Bellman - Ford Routing or Ford - Fulkerson Routing) A. Basic Idea. Each router maintains a table: Destination router My guess of best distance Which outgoing line Each router learns its immediate (1-hop) neighbors and the distance to them. Each router shares its knowledge about the entire network with its neighbors. This table is called a vector of distances, or, a distance vector. These tables are exchanged with neighbors only. When a router receives a distance vector from a neighbor, it uses that information to update its own distance vector. Routers send distance vectors periodically, whether or not changes have occurred. To consider how the distance vector algorithm works, let's consider the network shown below. A B C D 2 4 3
A B C D
2 4 3
B 2 A 2 B 4 C 3 C 4 D 3
Now, every router shares its table with its neighbors.
Consider this exchange from Router A's perspective. Router A receives from Router B the distance vector shown above. A B C D
2 4 3
So, Router A changes its routing table to: A B C D 2 4 3
B 2 C 6
Now, consider the matter from Router B's perspective. Router C tells Router B: "Router D is a distance of 3 away from me." Router B then reasons: "Router C is a distance of 4 away from me, and Router D is a distance of 3 away from Router C, so Router D must be a distance of 7 away from me." So, Router B changes its routing table to: A B C D 2 4 3
B 2 A 2 C 6 C 4
D 7 In a like manner, Router C and Router D change their routing tables based on the initial exchange. Thus, after the initial exchange of packets is complete, the distance vectors are: A B C D
2 4 3 B 2 A 2 A 6 B 7 C 6 C 4 B 4 C 3 D 7 D 3
But… matters are not done yet! Now that routers have reconstituted their distance vectors, they exchange them again! Note that distance vectors are exchanged with neighbors only. So, Router B tells Router A: "Router D is 7 away from me." Router A then reasons: "Router D must be 9 away from me." After all Routers reevaluate their distance vectors, we have this: A B C D
2 4 3 B 2 A 2 A 6 A 9 C 6 C 4 B 4 B 7 D 9 D 7 D 3 C 3 Hopefully this example convinces you that even though distance vectors are only exchanged with immediate neighbors, information about the full network will eventually percolate to all routers. But you are likely wondering: Okay… all the routers have distance vectors, but how do they use them for routing? To fill in this last piece of the distance-vector puzzle, let's show a more complex example (taken from the Tanenbaum text).
Consider the network shown on the left below. Further, suppose that for this scenario the weights used in the network represent time delays. Obviously, we would like data to be routed with minimal delay. You are Router J. Notice that you have four neighbors: A, I, H and K. Your delay to A is 8, your delay to I is 10, your delay to H is 12 and your delay to K is 6. You receive the distance vectors shown below on the right (the first column is the received distance vector from Router A, the second is from Router I, the third from Router H and the last column is the received distance vector from Router K. Your goal: Write down your new estimates of distances to all nodes, and annotate your distance vector showing the next router on the best path to each destination. 
From, Tanenbaum, Computer Networks, 3rd ed To see how you would accomplish this, let's focus on how you (Router J) would determine the best way to route a packet to Router F. Your neighbor Router A is 8 away from you. Router A says to you: "I can get to F in 23" Thus, if you use Router A as your next hop to Router F, you will get to Router F with a delay of 31. Your neighbor Router I is 10 away from you. Router I says to you: "I can get to F in 20" Thus, if you use Router I as your next hop to Router F, you will get to Router F with a delay of 30. Your neighbor Router H is 12 away from you. Router H says to you: "I can get to F in 19" Thus, if you use Router H as your next hop to Router F, you will get to Router F with a delay of 31. Your neighbor Router K is 6 away from you. Router K says to you: "I can get to F in 40" Thus, if you use Router K as your next hop to Router F, you will get to Router F with a delay of 46. Comparing these four values, you (Router J) conclude that the best way to route a packet to Router F is to send it to Router I. The total delay from Router J to Router F will be 30. Example 3 You are Router J. Notice that you have four neighbors: A, I, H and K. Your delay to A is 8, your delay to I is 10, your delay to H is 12 and your delay to K is 6. You receive the distance vectors shown below on the right (the first column is the received distance vector from Router A, the second is from Router I, the third from Router H and the last column is the received distance vector from Router K. Write down your new estimates of distances to all nodes, and annotate your distance vector showing the next router on the best path to each destination.
From, Tanenbaum, Computer Networks, 3rd ed Solution: Total Delay Destination Next Hop A B C D E F G H I J K L C. The “Count to Infinity” Problem in Distance Vector Routing Consider the three-node network shown below. Atop Node A and Node B, we show the entry in their routing table for Node X. Node X is a distance of 2 away from Node A. Node X is a distance of 6 away from Node B. All is well. 
Then Node X dies. Node A does not receive a Hello packet and realizes Node X must have died. It adjusts its routing table to show that Node X is unreachable (a distance of infinity away).
Then, something weird happens, and it has nothing to do with the fact that the At Hoc alert announcing the active shooter drill ended at 1046 did not actually get promulgated until 1245. Rather, this happens: Router A receives a distance vector from Router B saying "I can reach Router X in a distance of 6." Then…what do you do as Router A? You know that Router B is a distance of 4 away from you… and he's saying that he can reach X in a distance of 6… You update your routing table!
Then you share your distance vector with B, and she updates her routing entry for X:
This exchange continues back and forth, until the cows come home, or until the cows come home blue in the face, or until the cows come home blue in the face on a cold day in hell.
Forouzan, Data Communications and Networking, McGraw Hill, 2007 How can we limit or mitigate this instability? One proposed solution is to set some Download 416.85 Kb. Share with your friends:
|