Routing Overhead in Variable Topology Networks

Routing Overhead in Variable Topology Networks

Funding: NSF

Synopsis of the Project:

This project is developing mathematical 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.

We have developed mathematical models of proactive routing protocols in mobile ad-hoc networks. Treating the topology as a physical system exhibiting random (topology) changes induced by the underlying mobility model, we relate the routing overhead to the entropy rate of the system. The results thus far apply to the class of proactive routing protocols. Results for other classes of protocols are being developed, by differentiating between the subset of changes that are relevant to each.

We have also derived a scalability result for reactive routing protocols overhead in unreliable networks, by first quantifying the relation between the routing overhead and the route-request/reply patterns, and hence finding the conditions for infinite scalability (i.e. overhead grows as O(1) with the size of the network).

Students:

Nianjun Zhou
Huaming Wu
Nabhendra Bisnik

Publications:

N. Bisnik, A.A. Abouzeid, “Capacity Deficit in Mobile Ad Hoc Networks Due to Geographic Routing Overheads,” to appear, Proceedings of 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, Alaska, USA, May 6-12, 2007.

· N. Zhou and A. Abouzeid, “Routing in Ad-Hoc Networks: A Theoretical Framework with Practical Implications,” Proceedings of 24th IEEE International Conference on Computer Communications (Infocom2005), Miami, FL, 13-17 March 2005.

· N. Zhou, H. Wu and A. Abouzeid, “The Impact of Traffic Patterns on the Overhead of Reactive Routing Protocols,” IEEE Journal on Selected Areas in Communications, Special Issue on Wireless Ad Hoc Networks, January 2005.

· N. Zhou, H. Wu and A. Abouzeid, “Reactive Routing Overhead in Networks with Unreliable Nodes,” Proceedings of Ninth Annual International Conference on Mobile Computing and Networking (MobiCom’03), San Diego, CA, USA, September, 2003.

· N. Zhou and A. Abouzeid, “Information-Theoretic Lower Bounds on the Routing Overhead in Mobile Ad-hoc Networks,” Proceedings of IEEE International Symposium on Information Theory (ISIT03), Yokohama, Japan, June 2003.

· N. Zhou and A. Abouzeid, “Information-Theoretic Bounds for Mobile Ad-hoc Networks Routing Protocols,” Proceedings of International Conference on Networks (ICOIN03), Jeju Island, Korea, February 2003. (Selected as One of the Best Papers in ICOIN2003).

· Huaming Wu and Alhussein Abouzeid, "Cluster-based Routing Overhead in Networks with Unreliable Nodes", To appear in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC 2004), Atlanta, Georgia, USA, 2004.