Bell Labs Researchers Push The Limits of Mobile Computing

In a paper called, "Network Deformation: Traffic-Aware Algorithms for Dynamically Reducing End-to-End Delay in Multi-hop Wireless Networks," the authors describe a method for estimating in real time the mean end-to-end transit time of packets through the network based only upon the size of the queues at the network nodes and the network layout. This estimate allows the researchers to develop a class of "topology modification algorithms" to dynamically reconfigure nodes, thereby creating new links and also changing the capacities of existing links. According to the researchers, these algorithms alleviate network congestion and improve overall routing performance because the maximum load that the network can carry, before the end-to-end transit time starts to increase without bound, is significantly increased as a consequence of the changes to network connectivity.

"Adding new connections to alleviate congestion and to speed the flow of traffic in a data network is not unlike building new roads or tunnels to do the same in the physical world," said Sayandev Mukherjee, a researcher in Bell Labs' Wireless Research Laboratory. "Our algorithms indicate that building additional connections between nodes upstream - before traffic even reaches a bottleneck link - will reduce the end-to-end transit time resulting in greatly improved routing performance. This makes more sense than simply enhancing the capacity of the bottleneck links themselves."

Other members of the research team include Sharad Ramanathan, a researcher in Bell Labs' Physical Sciences Laboratory; Anindya Basu, formerly of Bell Labs, and now working at Morgan Stanley; and Brian Boshes, a student at the University of California, Berkeley, who is also an alumni of Lucent's Global Science Scholars Program.

In the other paper being presented this week, "Fairness and Load Balancing in Wireless LANs Using Association Control," a new method for balancing the traffic load in WLANs based on the IEEE 802.11 specification is described. WLANs enable a person with a wireless-enabled computer or personal digital assistant to connect to the Internet by moving within, for example, 15 meters of an access point, called a "hotspot." Recent studies on operational WLANs have shown that user load is often unevenly distributed among wireless access points resulting in unfair bandwidth allocation among users. To rectify this imbalance, the researchers have developed an algorithm that can intelligently and efficiently shift users from heavily loaded to lightly loaded access points - which guarantees near optimal bandwidth allocation for all users. According to lab simulations, these techniques outperform commonly used heuristic approaches, and they could be used as the foundation of a practical network management system.

"In the presence of hotspots, our algorithms provide fair service to all users accessing the network, while also maximizing the amount of bandwidth they receive," said Yigal Bejerano, a researcher in Bell Labs' Internet Management Lab. Bejarano continued, "Typically our algorithms also yield higher network utilization than the most commonly used 'strongest signal approach, while today's approaches tend to focus on overall throughput when allocating network resources. We believe that understanding the correlation between fairness and load-balancing are critical in order to maximize bandwidth for all users."

Bejerano's collaborators include Seung-Jae Han of the Wireless Research Lab, and Li Li of the Networking Research Lab - a testament to the multi-disciplinary nature of the collaborations happening at Bell Labs.

MobiCom is a highly selective conference - with less than an eight percent acceptance rate for papers to be presented - focusing on all issues in mobile computing and wireless and mobile networking at the link layer and above. The conference regularly attracts over 500 of the world's top researchers, practitioners, students, and executives, who are active in bringing about the future of mobile computing and networking.