NR: Routing Overhead In Variable Topology Networks - A Theoretical Framework With Practical Implications

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

The goal of this project is to develop rigorous analysis leading to fundamental understanding of the performance limits and design principles of routing protocols in variable topology networks, in particular related to the routing overhead as a key parameter of interest. For ad-hoc networks with frequent topology changes, such overhead may become a significant limit on the scalability and effective capacity. This research proposes to treat a variable topology network as a physical system that exhibits random (topology) changes. The minimum routing overhead is related to the minimum amount of information needed to identify the current state of the system (i.e. the current network topology). The distribution of topology changes is derived from the probability distributions describing the individual node mobility. Thus, the routing overhead can be related to the entropy rate of the system. Further, it is differentiated between different types of routing protocols based on the subset of changes that are relevant to the specific class of protocols under study. For example, proactive protocols keep track of any topology change, while reactive protocols track only the subset of the topology changes that affect nodes/links actively participating in routing packets. In contrast to the previous work in the ad-hoc networks routing area, this work develops a new analytic, rather than simulative, study of routing overhead in variable topology networks and, a general treatment that provides reference curves against which the routing overhead of different competing protocols can be compared. The key new approach is the concept of information theoretic characterization of network topology variation.