I came across this explanation for count to infinity problementer image description here

However, i don't understand that after the BC link broke, followed by which B erroneously updated the path to C at a cost of 3; Now why will A update the cost to C as 4 (after getting updates from B) since its current cost to C is 2 which is lesser than that advertised by B?

  • $\begingroup$ I guess because $A$ knows that in order to get to $C$ it needs to go through $B$, so when it receive the updated value from $B$ it updates itself. $\endgroup$ – Marcelo Fornet Jan 17 '18 at 21:51
  • $\begingroup$ You might be right but I have seen the algorithm for Routing Information Protocol used to update the routing table. It doesn't take into account the factor you mentioned and is concerned only with the least cost path. $\endgroup$ – virmis_007 Jan 18 '18 at 4:14
  • $\begingroup$ Wikipedia gives a more detailed example. Does this answer your question? $\endgroup$ – Derek Elkins left SE Jan 18 '18 at 5:45
  • $\begingroup$ No, because my doubt is based on the assumption (which i read somewhere) that routers update their existing entries only when a lesser cost path is found. In the cited example, before A went down, B knew that it's distance to A is 1; so why would B update its distance as dist(C,A)+1 because dist(C,A) +1 = 3 which is greater than 1? $\endgroup$ – virmis_007 Jan 18 '18 at 5:56
  • $\begingroup$ $C$ goes down, not $A$, but assuming that was a typo, when $B$ notices that $C$ is unreachable, $B$ updates its distance to $C$ to $\infty$ (or, equivalently, just forgets about $C$). If it then gets an update from $A$ which says $A$ has a route to $C$, $B$ then updates because it doesn't realize that $A$'s route goes through $B$. This is why split horizon resolves this particular scenario. $\endgroup$ – Derek Elkins left SE Jan 18 '18 at 19:06

I'll describe what happens, and then describe why each router made the decisions that it made using the scenario from the question.

The starting situation is a steady-state where the routers $A$, $B$, and $C$ have the connectivity $$A\stackrel{1}{\to} B\stackrel{1}{\to} C$$ $B$ is connected to $C$ in one hop, $A$ is connected to $B$ in one hop, and $A$ knows that it is connected to $C$ via $B$ in two hops.

  1. The connection from $B$ to $C$ goes down.
  2. $B$ notices this and updates its distance information from $1$ to $\infty$.
  3. Before $B$ notifies $A$ of the change, $A$ broadcasts an update saying that it has a route to $C$ in $2$ hops.
  4. $B$ updates its routing table to record its belief that it can reach $C$ in $3$ hops via $A$.
  5. $B$ broadcasts an update saying that it has a route to $C$ in $3$ hops.
  6. $A$ updates its routing table to record its belief that it can reach $C$ in $4$ hops via $B$.
  7. Et cetera.

From the comments, your issue is with step $6$. If $A$ already has a route to $C$ in $3$ hops, why wouldn't it just ignore the worse route via $B$ in $4$ hops and stay at $3$ hops? Well, the purpose of a router is to route messages. If I give $A$ a message to send to $C$, it needs to know who to send it to so that it eventually reaches $C$. $A$ knows that it will need to send to the message to $B$ for it to most efficiently reach $C$. In particular, $A$ knows that its distance estimate for a route to $C$ is based on the distance estimate of $B$. So if $B$ says that the distance has increased, $A$ knows that the distance has also increased for it (unless it can find a better route).

Of course, this is exactly what we want. Given the following connectivity diagram, if the connection marked by $(*)$ goes down, we want $A$ to start routing via $D$ ($3$ hops) rather than $B$ ($4$ hops) to send messages to $F$. That $B$ had a $2$ hop path in the past shouldn't matter. If $B$ loses all connectivity to $F$ (e.g. the connection between $B$ and $C$ also goes down), we certainly don't want to keep trying to route through $B$ just because it was the best route in the past. $$\require{AMScd} \begin{CD} A @>>> @>>> B @>>> C \\ @VVV @. @V(*)VV @VVV \\ D @>>> E @>>> F @<<< G \end{CD}$$

To put it a different way, we're talking about a dynamic version of the Bellman-Ford algorithm where edges can be added or removed in an online manner. Removing edges, in particular, makes the updates no longer monotonic. That is, we can no longer only keep the "best" routes we've ever heard, and we instead have to deal with potential "retractions".

Returning the the original, simpler scenario, the issue is when $B$ receives an update from $A$ that $A$ has a $2$ hop route to $C$, $B$ doesn't know that this information is dependent on $B$'s route to $C$. If $A$ had said that its route to $C$ was via $B$, then $B$ would have realized that this route was no longer useful and would not have updated its routing table in step 4. The split horizon modification solves this particular scenario by simply not having $A$ inform $B$ about any routes that $A$ can only reach (directly) through $B$, so step 3 never occurs as far as $B$ is concerned.

  • $\begingroup$ Thanks for the great reply. Just one final thing; so my previous assumption that routers update only when they have a better path available is incomplete; It should be actually that routers update when they have a lesser cost path available or when some other immediate router on which their path depends issues a change in costs involved, isn't it? $\endgroup$ – virmis_007 Jan 19 '18 at 8:30
  • $\begingroup$ Yes, and you can see how this may cause problems. In my more elaborate example in the answer, when the $(*)$ edge goes down, $A$ is stuck routing to $F$ through $B$ until it gets a reminder from $D$ that $D$ has a better route. One of the benefits (and costs) of link-state protocols is they maintain a full picture of the connectivity, so when $A$ hears about $(*)$ going down, $A$ can immediately switch to $D$ for routing to $F$. $\endgroup$ – Derek Elkins left SE Jan 19 '18 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.