Flooding & Distance Vector Routing

flooding
when a routing algorithm is implemented, each router must make decisions based on local knowledge, not the complete picture of the network. a simple local technique is flooding, in which every incoming packet is sent out on every outgoing line except the one it arrived on.
flooding obviously generates vast numbers of duplicate packets, in fact, an infinite number unless some measures are taken to damp the process. one such measure is to have a hop counter contained in the header of each packet that is decremented at each hop, with the packet being discarded when the counter reaches zero. ideally, the hop counter should be initialized to the length of the path from source to destination. if the sender does not know how long the path is, it can initialize the counter to the worst case, namely, the full diameter of the network.
flooding with a hop count can produce an exponential number of duplicate packets as the hop count grows and routers duplicate packets they have seen before. a better technique for damming the flood is to have routers keep track of which packets have been flooded, to avoid sending them out a second time. one way to achieve this goal is to have the source router put a sequence number in each packet it receives from its hosts. each router then needs a list per source router telling which sequence numbers originating at that source have already been seen. if an incoming packet is on the list, it is not flooded.
to prevent the list from growing without bound, each list should be augmented by a counter k, meaning that all sequence numbers through k have been seen. when a packet comes in, it is easy to check if the packet has already been flooded (by comparing its sequence number to k if so, it is discarded. furthermore, the full list below k is not needed, since k effectively summarizes it.
flooding is not practical for sending most packets, but it does have some important uses. first, it ensures that a packet is delivered to every node in the network.
this may be wasteful if there is a single destination that needs the packet, but it is effective for broadcasting information. in wireless networks, all messages transmitted by a station can be received by all other stations within its radio range, which is, in fact, flooding, and some algorithms utilize this property. second, flooding is tremendously robust. even if large numbers of routers are blown to bits (e.g., in a military network located in a war zone), flooding will find a path if one exists, to get a packet to its destination. flooding also requires little in the way of setup. the routers only need to know their neighbors. this means that flooding can be used as a building block for other routing algorithms that are more efficient but need more in the way of setup. flooding can also be used as a metric against which other routing algorithms can be compared. flooding always chooses the shortest path because it chooses every possible path in parallel. consequently, no other algorithm can produce a shorter delay (if we ignore the overhead generated by the flooding process itself).

distance vector routing
in distance vector routing, the least-cost route between any two nodes is the route with minimum distance. in this protocol, as the name implies, each node maintains a vector (table) of minimum distances to every node. the table at each node also guides the packets to the desired node by showing the next stop in the route (next-hop routing). we can think of nodes as the cities in an area and the lines as the roads connecting them. a table can show a tourist the minimum distance between cities. in figure below, we show a system of five nodes with their corresponding tables.

initialization
the tables in figure above are stable each node knows how to reach any other node and the cost. at the beginning, however, this is not the case. each node can know only the distance between itself and its immediate neighbors, those directly connected to it. so for the moment, we assume that each node can send a message to the immediate neighbors and find the distance between itself and these neighbors. figure below shows the initial tables for each node. the distance for any entry that is not a neighbor is marked as infinite (unreachable).

sharing
the whole idea of distance vector routing is the sharing of information between neighbors. although node a does not know about node e, node c does. so if node c shares its routing table with a, node a can also know how to reach node e. on the other hand, node c does not know how to reach node d, but node a does. if node a shares its routing table with node c, node c also knows how to reach node d. in other words, nodes a and c, as immediate neighbors, can improve their routing tables if they help each other.
there is only one problem. how much of the table must be shared with each neighbor? a node is not aware of a neighbor s table. the best solution for each node is to send its entire table to the neighbor and let the neighbor decide what part to use and what part to discard. however, the third column of a table (next stop) is not useful for the neighbor. when the neighbor receives a table, this column needs to be replaced with the sender s name. if any of the rows can be used, the next node is the sender of the table. a node therefore can send only the first two columns of its table to any neighbor. in other words, sharing here means sharing only the first two columns.

updating
when a node receives a two-column table from a neighbor, it needs to updating its routing table. updating takes three steps:
1. the receiving node needs to add the cost between itself and the sending node to each value in the second column. the logic is clear. if node c claims that its distance to a destination is x mi, and the distance between a and c is y mi, then the distance between a and that destination, via c, is x + y mi.
2. the receiving node needs to add the name of the sending node to each row as the third column if the receiving node uses information from any row. the sending node is the next node in the route.
3. the receiving node needs to compare each row of its old table with the corresponding row of the modified version of the received table.
a. if the next-node entry is different, the receiving node chooses the row with the smaller cost. if there is a tie, the old one is kept.
b. if the next-node entry is the same, the receiving node chooses the new row. for example, suppose node c has previously advertised a route to node x with distance
3. suppose that now there is no path between c and x node c now advertises this route with a distance of infinity. node a must not ignore this value even though its old entry is smaller. the old route does not exist any more. the new route has a distance of infinity.
figure below shows how node a updatings its routing table after receiving the partial table from node c

there are several points we need to emphasize here. first, as we know from mathematics, when we add any number to infinity, the result is still infinity. second, the modified table shows how to reach a from a via c. if a needs to reach itself via c, it needs to go to c and come back, a distance of 4. third, the only benefit from this updating of node a is the last entry, how to reach e. previously, node a did not know how to reach e (distance of infinity) now it knows that the cost is 6 via c.
each node can updating its table by using the tables received from other nodes. in a short time, if there is no change in the network itself, such as a failure in a link, each node reaches a stable condition in which the contents of its table remains the same.

when to share: the question now is, when does a node send its partial routing table (only two columns) to all its immediate neighbors? the table is sent both periodically and when there is a change in the table. periodic updating a node sends its routing table, normally every 30 s, in a periodic updating. the period depends on the protocol that is using distance vector routing. triggered updating a node sends its two-column routing table to its neighbors anytime there is a change in its routing table. this is called a triggered updating. the change can result from the following:
1. a node receives a table from a neighbor, resulting in changes in its own table after updating.
2. a node detects some failure in the neighboring links which results in a distance change to infinity.

two-node loop instability
a problem with distance vector routing is instability, which means that a network using this protocol can become unstable. to understand the problem, let us look at the scenario depicted in figure below which shows a system with three nodes. we have shown only the portions of the routing table needed for our discussion. at the beginning, both nodes a and b know how to reach node x. but suddenly, the link between a and x fails. node a changes its table. if a can send its table to b immediately, everything is fine. however, the system becomes unstable if b sends its routing table to a before receiving a s routing table.
node a receives the updating and, assuming that b has found a way to reach x, immediately updatings its routing table. based on the triggered updating strategy, a sends its new updating to b. now b thinks that something has been changed around a and updatings its routing table. the cost of reaching x increases gradually until it reaches infinity. at this moment, both a and b know that x cannot be reached. however, during this time the system is not stable. node a thinks that the route to x is via b node b thinks that the route to x is via a. if a receives a packet destined for x, it goes to b and then comes back to a. similarly, if b receives a packet destined for x, it goes to a and comes back to b. packets bounce between a and b, creating a two-node loop problem. a few solutions have been proposed for instability of this kind.



defining infinity the first obvious solution is to redefine infinity to a smaller number, such as 100. for our previous scenario, the system will be stable in less than 20 updatings. as a matter of fact, most implementations of the distance vector protocol define the distance between each node to be 1 and define 16 as infinity. however, this means that the distance vector routing cannot be used in large systems. the size of the network, in each direction, can’t exceed 15 hops.

split horizon another solution is called split horizon. in this strategy, instead of flooding the table through each interface, each node sends only part of its table through each interface. if, according to its table, node b thinks that the optimum route to reach x is via a, it does not need to advertise this piece of information to a the information has corne from a (a already knows). taking information from node a, modifying it, and sending it back to node a creates the confusion. in our scenario, node b eliminates the last line of its routing table before it sends it to a. in this case, node a keeps the value of infinity as the distance to x. later when node a sends its routing table to b, node b also corrects its routing table. the system becomes stable after the first updating: both node a and b know that x is not reachable.

split horizon and poison reverse using the split horizon strategy has one drawback. normally, the distance vector protocol uses a timer, and if there is no news about a route, the node deletings the route from its table. when node b in the previous scenario eliminates the route to x from its advertisement to a, node a cannot guess that this is due to the split horizon strategy (the source of information was a) or because b has not received any news about x recently. the split horizon strategy can be combined with the poison reverse strategy. node b can still advertise the value for x, but if the source of information is a, it can replace the distance with infinity as a warning: "do not use this value what i know about this route comes from you."





example:

(a) a network.
(b) input from a, i, h, k, and the new routing table for j.