Computer and Communication Networks (paperback)

7.3. Non- Least-Cost- Path Routing

Our networking infrastructure deploys a variety of procedures, algorithms, and protocols for routing packets, depending on the applications, their significance, and the budget for building a network. Besides the least-cost-path algorithms that effectively identify the best possible paths, some nonoptimal algorithms can be used for applications that may not need complex and expensive routing protocols. Two examples of such non-least-cost routing algorithms are flood routing and deflection routing .

7.3.1. Flood Routing

Flood routing is a very simple routing strategy involving less hardware setup. The essence of this routing method is that a packet received from a node is copied and transmitted on all outgoing links of that node except for the link that the packet arrived from. After the first transmission, all the routers within one hop receive the packet. After the second transmission, all the routers within two hops receive the packet, and so on. Unless a mechanism stops the transmission, the process continues; as a result, the volume of traffic increases with time, as shown in Figure 7.3.

In this figure, three packets arrive at node A from a source. The first packet is copied to both nodes B and C. At nodes B and C, the copies of the packet are copied to their neighboring nodes. This method has the deficiency of packet reflection: a node can receive an unwanted copy of a packet. Although this problem can be fixed by dropping unwanted packets at any time, the network does not function effectively, owing to increased unnecessary traffic. One way to prevent packet duplication is to set up memory for each node to remember the identity of those packets that have already been retransmitted for blocking them.

7.3.2. Deflection Routing

In deflection routing , or hot-potato routing , a packet is sent to a destination determined at each router. At each step of the routing, a packet is examined with respect to its destination. If the requested link is free, the packet is sent on that link; otherwise , the packet is deflected onto another link, selected at random. The deflected packet is given an increment on its priority field. This increment gives the packet a better chance to win the contention with others in future contentions. For the deflected packet, if a new contention occurs with another packet in its next hop, the packet with the higher priority gets the desired link, and the other one is deflected with, of course, an increment in its priority field. In Figure 7.4, a packet is deflected at node B but eventually gets to node C, with a total of one additional hop and a total cost difference of 3, using node B.