Routing with a Markovian Metric to Promote Local Mixing

Routing protocols have traditionally been based on finding shortest paths under certain cost metrics. A conventional routing metric models the cost of a path as the sum of the costs on the constituting links. This paper introduces the concept of a Markovian metric, which models the cost of a path as the cost of the first hop plus the cost of the second hop conditioned on the first hop, and so on. The notion of the Markovian metric is fairly general. It is potentially applicable to scenarios where the cost of sending a packet (or a stream of packets) over a link may depend on the previous hop of the packet (or the stream). Such scenario arises, for instance, in a wireless mesh network equipped with local mixing, a recent link layer advance. This scenario is examined as a case study for the Markovian metric. The local mixing engine sits between the routing and MAC layers. It maintains information about the packets each neighbor has, and identifies opportunities to mix the outgoing packets via network coding to reduce the transmissions in the air. We use a Markovian metric to model the reduction of channel resource consumption due to local mixing. This leads to routing decisions that can better take advantage of local mixing. We have implemented a system that incorporates local mixing and source routing using a Markovian metric in Qualnet. The experimental results demonstrate significant throughput gain and resource saving.