Alhussein Abouzeid Research:

Interests

Systems: Communication Networks; Wireless Ad Hoc and Sensor Networks; Peer-to-Peer Networks.

Applied Theory: Stochastic Processes; Algorithm and Protocol Complexity; Multi-layer Optimization; Information Theory; Queuing Theory.

Project "Limits": Basic Limits on Protocol Information in Variable Topology Computer Networks

NSF Project Link: Routing and Information Theory (2003-2006)

Since routing protocols need to adjust to topology change, an overhead is incurred due to the exchange of routing messages. For variable topology networks, such an overhead may impose a significant limit on scalability and effective capacity. For example, it has been noted from measurement data that in certain modern networks (e.g. a portion of the U.S. Air Force network), such overheads constituted 80% of the total traffic carrying capacity. Thus, it is important to understand how the overhead scales for various protocol-design choices.

We developed an information-theoretic framework for the characterization of bounds on the least overhead incurred by various classes of routing protocols under a uniform traffic pattern. The key departure point of the new framework is to treat the state (e.g. link state, node location, hybrid of both) as a random variable that exhibits random changes. The minimum protocol overhead is related to the minimum amount of information (i.e. effort) needed to identify the current state of the system, possibly within a distortion bound. The various state changes are derived from the probability distribution describing the cause of dynamism, e.g. the nodes mobility pattern. Thus the protocol overhead problem is brought into an information theoretic framework, and terms like entropy rate now yield new practical design guidelines and basic limits on the best possible protocol design. For example, we can now characterize the highest possible effective capacity of a network, by subtracting the lowest capacity deficit among all possible protocol designs.

We have also considered the routing protocol overhead problem from a different angle that has not been considered before in the literature. That is, we took into account the interdependence between the communication pattern, in terms of the distribution of number of hops between source destination pairs, and the routing overhead. Interestingly, it turns out that reactive routing protocols can operate efficiently for asymptotically large networks (even with an infinite number of nodes) if the traffic is sufficiently localized statistically. We have analytically characterized the sufficient conditions and validated them through extensive simulations of realistic protocol implementations.

Presentations:

"Entropy Measures of Routing: Towards a First Law of MANET Info-dynamics," DARPA ITMANET workshop March 7, 2006: .pdf

"Scaling Laws of Variable Topology Networks; Stochastic and Information Theoretic Approaches," Princeton ISS seminar, March 2, 2006 : .pdf, .pps

" Rate-Distortion Bounds on Location-Based Routing Protocol Overheads in Mobile Ad Hoc Networks," Allerton 2006 Conference, September 27 2006: .pdf

Key Publications:

N. Bisnik, A.A. Abouzeid, "Rate-Distortion Bounds on Location-Based Routing Protocol Overheads in Mobile Ad Hoc Networks," Proceedings of Allerton 2006, Sept 27-29, Allerton House, UIUC, Illinois, USA. .pdf

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. (draft)

N. Zhou and A.A. Abouzeid, “Routing in Ad Hoc Networks: A Theoretical Framework with Practical Implications,” IEEE Transactions on Information Theory, submitted April 2004, revised August 2006. (Conference version in IEEE INFOCOM 2005).

N. Zhou, H. Wu and A.A. Abouzeid, “The Impact of Traffic Patterns on the Overhead of Reactive Routing Protocols,” IEEE Journal on Selected Areas in Communications, Special Issue on Mobile Ad-Hoc Networks, vol. 23, no. 3, pp. 547-560, March 2005. (Conference version in MobiCom 2003).

Huaming Wu and A.A. Abouzeid, "Cluster-based Routing Overhead in Networks with Unreliable Nodes", Proceedings of IEEE Wireless Communications and Networking Conference (WCNC 2004), vol. 4, pp. 2557-2562, Atlanta, Georgia, USA, March 21-25, 2004.