Step 6. Count to Infinity Problem (Two-node Loop Instability)¶

Goals¶

We will demonstrate the count to infinity problem of the distance-vector routing algorithm used by RIP.

The distance-vector algorithm has many advantages. For example, it is very easy to implement and responds to topology changes rapidly. However, if there are routing loops in the topology, the algorithm may take a very long time to stabilize, and during this transient period (which can be quite long) some parts of the network will remain inaccessible. There are only partial solutions to this problem (e.g. split horizon).

Network Configuration¶

Our network topology for this exercise is defined by the RipNetworkB.ned file:

TODO screenshot

The configuration in omnetpp.ini is the following:

[Config Step6]
description = "Count to infinity (two-node loop instability)"
network = RipNetworkB

# adding default routes in all hosts
*.configurator.config = xml("<config> \
<autoroute sourceHosts='host*'/> \
</config>")

# RIP parameters on routers
*.router*.hasRip = true
*.router*.rip.startupTime = uniform(0s,1s)
# disable advanced features for now!
*.router*.rip.ripConfig = xml("<config> <interface hosts='router*' mode='NoSplitHorizon' /> </config>")
*.router*.rip.triggeredUpdate = false

# turning on global ARP to focus on the RIP messages
#*.*.ipv4.arp.typename = "GlobalArp"  # TODO: for some reasons GlobalArp does not work

*.scenarioManager.script = xml("<scenario> \
<disconnect t='50' src-module='router1' dest-module='switch1' /> \
</scenario>")

# Visualizer settings
*.visualizer.interfaceTableVisualizer[0].displayInterfaceTables = true

*.visualizer.routingTableVisualizer[*].nodeFilter = "router* or host0 or host3"
*.visualizer.routingTableVisualizer[0].destinationFilter = "host0"
*.visualizer.routingTableVisualizer[1].destinationFilter = "host3"

# to solve the count to infinity problem (two-node instability), you can:

# 1) enable 'split horizon'
#*.router*.rip.ripConfig = xml("<config> <interface hosts='router*' mode='SplitHorizon' /> </config>")

# 2) or enable 'split horizon with poison reverse'
#*.router*.rip.ripConfig = xml("<config> <interface hosts='router*' mode='SplitHorizonPoisonedReverse' /> </config>")

# 3) activating triggered update is not a definite solution, because
# it might get canceled due to the regular update timer being fired very soon!
#*.router*.rip.triggeredUpdate = true

# enable ping app to see ping packets bouncing back and forth between the two routers

## Application parameters
#*.host0.numApps = 1
#*.host0.app[0].typename = "PingApp"
#*.host0.app[0].startTime = 35s
##*.host0.app[0].stopTime = 90s
#*.host0.app[0].sendInterval = 15s
#*.host0.app[0].hopLimit = 8
#
#*.visualizer.packetDropVisualizer[0].displayPacketDrops = true

**.arp.typename = "GlobalArp"


At t = 50s, the link connecting router1 to switch1 is cut. Then, router0 advertises a route hosts 3, 4 and 5 to router1. Even though this route is a “phantom” one, router1 does not know this, increments the hop count, adds it to its routing table, and advertises it to router0. This cycle keeps going until the hop count reaches a big number (default is 16).

TODO move above para to different place?

Experiments¶

Demonstration of the problem¶

[Config Step6] demonstrates the problem: RIP convergence takes 220 seconds (from the link break at t = 50 s to no routes to host3 at 270 s). Note the increasing hop count (indicated on the route in parentheses).

TODO screenshot?

Observe how ping packets go back and forth between the two routers, indicating the presence of a routing loop. The ping packets time out after 8 hops, and are dropped.

Count to Infinity is a classical race condition issue¶

In [Config Step6DifferentTimings] we demonstrate that depending on the time in which router informs the other one, the problem may or may not appear.

[Config Step6DifferentTimings]
extends = Step6
description = "Count to infinity: Using different timers, the problem does not surface"

# what happens if router 1 sends the update first ? -> no count to infinity

*.router1.rip.startupTime = 0.5s
*.router0.rip.startupTime = 1s


TODO Rip start, link break, counting to infinity, ping packets:

In [Config Step6Solution3] we demonstrate that triggered updates do not solve the problem.

[Config Step6TriggeredUpdates]
extends = Step6
description = "Count to infinity: Triggered updates is not a solution"

*.router*.rip.triggeredUpdate = true


Solution 1: Split horizon¶

[Config Step6Solution1] shows how the addition of split horizon solves the count to infinity problem. Here, when a router sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.

[Config Step6Solution1]
extends = Step6
description = "Solution to count to infinity problem: Split horizon"

*.router*.rip.ripConfig = xml("<config> <interface hosts='router*' mode='SplitHorizon' /> </config>")


Solution 2: Split horizon with poison reverse¶

In [Config Step6Solution2] we demonstrate a stronger version of split horizon, called split horizon with poison reverse. In this variation of split horizon, when a router sends a routing update to its neighbors, it sends those routes it learned from each neighbor back to that neighbor with infinite cost information to make sure that the neighbour does not use that route.

[Config Step6Solution2]
extends = Step6
description = "Solution to count to infinity problem: Split horizon with poison reverse"

*.router*.rip.ripConfig = xml("<config> <interface hosts='router*' mode='SplitHorizonPoisonedReverse' /> </config>")