2011-05-16
final review problem 1 -- James, Brian Ho and Miao.
Originally Posted By: miao
1. Give an example of a situation where the count to infinity problem occurs when distance vector routing is used. Explain your example. Show, with this same example, that using split horizon would solve this problem.
Example: in a linear network where A comes alive at some time t, and then at some time later, A goes down. It takes a significant amount of time for all machines to get the correct distance to A.
ABCD
...Init
1..1 exchange
2.2 exchange
33 exchange
A goes down
BCD
123
323
343
545
565
767
A goes down, C then advertises to B that it is 2 hops away from A.
B updates its distance to A to 3 hops, and then B advertises its distance to A back to C.
C updates its distance to A to 4 hops.
This goes on forever.
B and C end up count to infinity problem.
Split horizon prevents count to infinity by preventing sending routes learned from neighbors back to senders. So B never learns about C’s distance to A and would not update its path from C.
Example: in a linear network where A comes alive at some time t, and then at some time later, A goes down. It takes a significant amount of time for all machines to get the correct distance to A.
ABCD
...Init
1..1 exchange
2.2 exchange
33 exchange
A goes down
BCD
123
323
343
545
565
767
A goes down, C then advertises to B that it is 2 hops away from A.
B updates its distance to A to 3 hops, and then B advertises its distance to A back to C.
C updates its distance to A to 4 hops.
This goes on forever.
B and C end up count to infinity problem.
Split horizon prevents count to infinity by preventing sending routes learned from neighbors back to senders. So B never learns about C’s distance to A and would not update its path from C.
'''Originally Posted By: miao'''
1. Give an example of a situation where the count to infinity problem occurs when distance vector routing is used. Explain your example. Show, with this same example, that using split horizon would solve this problem.<br><br>Example: in a linear network where A comes alive at some time t, and then at some time later, A goes down. It takes a significant amount of time for all machines to get the correct distance to A.<br><br>ABCD<br>...Init<br>1..1 exchange<br>2.2 exchange<br>33 exchange<br><br>A goes down<br>BCD<br>123<br>323<br>343<br>545<br>565<br>767<br><br>A goes down, C then advertises to B that it is 2 hops away from A. <br>B updates its distance to A to 3 hops, and then B advertises its distance to A back to C. <br>C updates its distance to A to 4 hops.<br>This goes on forever.<br>B and C end up count to infinity problem. <br><br>Split horizon prevents count to infinity by preventing sending routes learned from neighbors back to senders. So B never learns about C’s distance to A and would not update its path from C.
2011-05-21
Originally Posted By: eturkov
Here is another way of looking at the problem.
Let's assume we we define each node in our linear network as follows [A-Z]/[0-9] where the letter represents the node name and the number represents that node's cost to reach the internet, where it is possible to simply replace the internet with another node. Note that in the below diagram, it can be assumed the the cost between any directly connected node is 1.
So take the following network configuration: A/3 --> B/2 --> C/1 --> INTERNET
In this configuration, A uses B and B uses C to reach Internet, with costs to reach the internet from a node being 3,2,1 respectively.
A/3 ---> B/2 C/3 xxx INTERNET
C's internet link breaks and C erroneously switches to B, increasing its own internet cost based on B's cost to reach the internet. ie, B.internet.cost + C.initial.cost = 3.
A/3 --> B/4 C/3 xxx INTERNET
B's internet reach cost must change now, since C's just changed. A hasn't realized what has happened yet.
A/5 --> B/4 C/5 xxx INTERNET
A now learns that B's internet reach cost has changed from 2 to 4, so A has to set its new internet reach cost to 1(initial A cost) + 4(cost to go through B). A's and C's cost are now B's + 1 = 5
A/5 --> B/6 C/5 xxx INTERNET
B's path cost is now C's + 1 = 6 cycle repeats while counting to infinity. Packets are caught between the B & C loop.
If split horizon would be used here, then B would not advertise reachability to C since B would have to go through C itself to reach the internet.
Let's assume we we define each node in our linear network as follows [A-Z]/[0-9] where the letter represents the node name and the number represents that node's cost to reach the internet, where it is possible to simply replace the internet with another node. Note that in the below diagram, it can be assumed the the cost between any directly connected node is 1.
So take the following network configuration: A/3 --> B/2 --> C/1 --> INTERNET
In this configuration, A uses B and B uses C to reach Internet, with costs to reach the internet from a node being 3,2,1 respectively.
A/3 ---> B/2 C/3 xxx INTERNET
C's internet link breaks and C erroneously switches to B, increasing its own internet cost based on B's cost to reach the internet. ie, B.internet.cost + C.initial.cost = 3.
A/3 --> B/4 C/3 xxx INTERNET
B's internet reach cost must change now, since C's just changed. A hasn't realized what has happened yet.
A/5 --> B/4 C/5 xxx INTERNET
A now learns that B's internet reach cost has changed from 2 to 4, so A has to set its new internet reach cost to 1(initial A cost) + 4(cost to go through B). A's and C's cost are now B's + 1 = 5
A/5 --> B/6 C/5 xxx INTERNET
B's path cost is now C's + 1 = 6 cycle repeats while counting to infinity. Packets are caught between the B & C loop.
If split horizon would be used here, then B would not advertise reachability to C since B would have to go through C itself to reach the internet.
'''Originally Posted By: eturkov'''
Here is another way of looking at the problem.<br><br>Let's assume we we define each node in our linear network as follows [A-Z]/[0-9] where the letter represents the node name and the number represents that node's cost to reach the internet, where it is possible to simply replace the internet with another node. Note that in the below diagram, it can be assumed the the cost between any directly connected node is 1.<br><br>So take the following network configuration: A/3 --> B/2 --> C/1 --> INTERNET<br>In this configuration, A uses B and B uses C to reach Internet, with costs to reach the internet from a node being 3,2,1 respectively. <br><br>A/3 ---> B/2 C/3 xxx INTERNET<br>C's internet link breaks and C erroneously switches to B, increasing its own internet cost based on B's cost to reach the internet. ie, B.internet.cost + C.initial.cost = 3.<br><br>A/3 --> B/4 C/3 xxx INTERNET<br>B's internet reach cost must change now, since C's just changed. A hasn't realized what has happened yet.<br><br>A/5 --> B/4 C/5 xxx INTERNET<br>A now learns that B's internet reach cost has changed from 2 to 4, so A has to set its new internet reach cost to 1(initial A cost) + 4(cost to go through B). A's and C's cost are now B's + 1 = 5<br><br>A/5 --> B/6 C/5 xxx INTERNET<br>B's path cost is now C's + 1 = 6 cycle repeats while counting to infinity. Packets are caught between the B & C loop.<br><br>If split horizon would be used here, then B would not advertise reachability to C since B would have to go through C itself to reach the internet.
(c) 2024 Yioop - PHP Search Engine