Research Projects

Distributed Network Monitoring with Bounded Link Utilization in IP Networks (at Bell Labs.)

Designing optimal measurement infrastructure is a key step for network management. We address the problem of optimizing a scalable distributed polling system. The goal of the optimization is to reduce the cost of deployment of the measurement infrastructure by identifying a minimum poller set subject to bandwidth constraints on the individual links. We show that this problem is NP-hard and propose three different heuristics to obtain a solution. We evaluate our heuristics on both hierarchical and flat topologies with different network sizes under different polling bandwidth constraints. We found that the heuristic of choosing the poller that can poll the maximum number of un-polled nodes was the best approach. Our simulation studies show that the results obtained by our best heuristic is close to the lower bound obtained using LP relaxation.


Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks (at Bell Labs.)

The emerging Multi-Protocol Label Switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic Label Switched Path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of ``backtracking'' to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: (1) no backtracking (D=0), (2) limited backtracking (D=k), and (3) unlimited backtracking (D=¥). We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.


4th Generation Wireless Architecture for HDR (High Data Rate or CDMA 1x-EVDO) Networks (at Bell Labs.)

In 3G data networks, the channel quality of a user is location dependent and time varying. Due to proportional fairness scheduling, users with poor channel quality receive low data rates and therefore bring down the total cell throughput. Existing network architectures for improving cell throughput require new hardware elements and therefore are prohibitively expensive. We propose a highly deployable software-only solution that improves the cell throughput with the simultaneous use of ad hoc networking technology in the 802.11 unlicensed spectrum. We demonstrate the effectiveness of our architecture by enhancements specific to the HDR technology. The average network capacity of HDR downlink channel (about 600 Kbps) is far from the maximum (2.4 Mbps) that it can achieve. Based on our simulations, we have found that our architecture can improve the throughput of a HDR cell by upto 150%.


Throughput and Energy Efficiency in Topology Controlled Ad Hoc Networks (at Bell Labs.)

In ad hoc wireless networks, various topology control algorithms have been proposed to reduce the transmission range of nodes based on local information and yet maintain a connected topology. Topology control can potentially improve network throughput and increase network lifetime by reducing power consumption. We have designed an analytical framework for evaluating the performance of topology control algorithms using overall network throughput, and total energy consumption per packet delivered, as the metrics. The goal of this project was to identify scenarios under which topology control can be used to improve the network performance. Our analysis is supplemented with simulations on the ns2 simulator based on an idealized version of the cone-based topology control algorithm. Based on studies with various traffic patterns and network loads, we have clearly identified scenarios under which network performance of ad hoc networks can be improved by using topology control.


IP Paging for Mobile Hosts (at Bell Labs.)

In wireless networks with fixed infrastructure, mobile hosts must update the network with their current location in order to get packets delivered to them. Paging facilitates efficient power management at the mobile host by allowing the host to update the network less frequently at the cost of providing the network with only approximate location information. The network determines the exact location of a mobile host through paging before delivering packets destined to the mobile host. In current circuit-switched wireless networks, paging is implemented as a special purpose functionality in a centralized component inside the network. Given the emergence of different packet-switched wireless networks, we propose a novel router service called IP paging. This enables one common IP-based infrastructure to support different wireless interfaces such as CDMA, GPRS, Wireless LAN, etc. Our major contributions are the design, implementation, and detailed performance evaluation, using measurements and simulation, of three IP-based paging protocols for mobile hosts.


A Decision Theoretic Approach to Resource Allocation in Wireless Multimedia Networks (at Cornell)

The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless communication. We argue that the problem is best formulated in terms of decision theory. We propose a scheme that takes decision-theoretic concerns (like preferences) into account and discuss the difficulties and subtleties involved in applying standard techniques from the theory of Markov Decision Processes (MDPs) in constructing an algorithm that is decision-theoretically optimal. As an example of the proposed framework, we construct such an algorithm under some simplifying assumptions. Additionally, we present analysis and simulation results that show that our algorithm meets its design goals. Finally, we investigate how far from optimal one well-known heuristic is. The main contribution of our results is in providing insight and guidance for the design of near-optimal admission-control policies.


Gossip Based Ad Hoc Routing (at Cornell)

Due to the changing and high variability nature of ad hoc networks, routing traffic can be a significant overhead and impediment to application performance. Many ad hoc routing protocols are based on (some variant of) flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach to reduce the overhead of the routing protocols. Our major findings are as follows. In large networks, there is a threshold effect: in almost every execution of the gossiping protocol, almost every node gets the message or almost no node does. The fraction of executions in which almost every node gets the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, our simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Our simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. The improvement should be even more significant in larger networks.


Analysis of a Cone-Based Distributed Topology Control Algorithm for Ad Hoc Networks (at Microsoft Research)

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. We propose a cone-based distributed topology control algorithm. This algorithm does not assume that nodes have GPS information available; rather it depends only on directional information. basic idea of the algorithm is that a node u transmits with the minimum power p_u,a required to ensure that in every cone of degree a around u, there is some node that u can reach with power p_u,a. We show that taking a=5p/6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from s to t when every node communicates at maximum power then, if a £ 5p/6, there is still a path in the smallest symmetric graph G_a containing all edges (u,v) such that u can communicate with v using power p_u,a. On the other hand, if a>5p/6, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Our simulation results demonstrate the effectiveness of the algorithm and the optimizations.


High-Performance Distributed Objects over System Area Networks (at Microsoft Research)

Just as the advent of high-speed networks shifts the performance bottleneck to the protocol stacks, the availability of commercial user-level networking shifts the bottleneck to the distributed object infrastructures. We propose an approach to building high-performance, commercial distributed object systems over system area networks (SANs) with user-level networking. The specific platforms that we use in the study are the Virtual Interface Architecture (VIA) and Microsoft's Distributed Component Object Model (DCOM). The target application environments are physically secure server clusters consisting of homogeneous machines connected by high-speed system area network. Our goal is to implement a set of software modules that can be integrated into existing DCOM infrastructure. These modules will be loaded for inter-server communications within a cluster, while client machines outside the cluster still contact the server machines through traditional protocol stacks running over traditional networks. We give a detailed functional and performance analysis of DCOM and apply optimizations at several layers to take full advantage of modern high-speed networks, while preserving the full set of DCOM features including security and different threading models. Through extensive runtime and transport optimization, our system achieves a round-trip latency of 72 microseconds for null DCOM calls, more than 5 times faster than current implementation on the same network. By eliminating buffer copying at the marshaling layer, our system achieves an application bandwidth of 86.1 megabytes per second, more than 7 times improvement over current implementation.