Context-based Routing: Techniques, Applications and Experience

Routing protocols in multi-hop networks are typically based on finding low cost paths by modeling the cost of a path as the sum of the costs on the constituting links. However, the insufficiency of this approach becomes more apparent as new lower layer technologies are incorporated. For instance, to maximize the benefit of multiple radios, ideally we should use routes that contain low interference among the constituting links. Similarly, to maximize the benefit of network coding, we should ideally use routes that create more coding opportunities. Both of these are difficult to accomplish within the conventional routing framework because therein the links are examined in isolation of each other, whereas the nature of the problem involves interdependencies among the links.

This paper aims at revealing a unifying framework for routing in the presence of inherent link interdependencies, which we call “context-based routing”. Through the case studies of two concrete application scenarios, network coding–aware routing and self-interference aware routing in multi-radio systems, we highlight the common key pillars for context-based routing and their interplay: a context-based path metric and a route selection method. We implement context-based routing protocols in Windows XP and Linux and evaluate them in detail. Experiments conducted at 2 testbeds demonstrate significant throughput gains.