Problem 2: Number of Routings, (K Narayan Kumar, CMI)

It is well known that the routing algorithm used on the Internet is highly non-optimal. A "hop", in Internet jargon, is a pair of nodes that are directly connected - by a cable or a microwave link or whatever. The number of hops that a packet may take in going from one node to another may be far more than the minimum required.

But the routing algorithm used by the Siruseri Network company is worse. Here, a packet sent from one node to another could even go through the same node twice or even traverse the same hop twice before it eventually finds its way to its destination. Sometimes a packet even goes through the destination more than once before it is considered "delivered". Suppose the network in Siruseri consisted of the following nodes and cables: