19403347
DVSR: a high-performance metro ring protocol
The Resilient Packet Ring (RPR) IEEE 802.17 standard is under development as a new high-speed backbone technology for metropolitan area networks. A key performance objective of RPR is to simultaneously achieve high utilization, spatial reuse, and fairness, an objective not achieved by current technologies such as SONET and Gigabit Ethernet or by legacy ring technologies such as FDDI. The core technical challenge for RPR is the design of a bandwidth allocation algorithm that dynamically achieves these properties. The difficulty is in the distributed nature of the problem, that upstream ring nodes must inject traffic at a rate according to congestion and fairness criteria downstream. Unfortunately, the proposed algorithms in the current draft standards have a number of critical limitations. For example, we show that in a two-flow two-link scenario with unbalanced and constant-rate traffic demand, a draft RPR algorithm will suffer from dramatic bandwidth oscillations within nearly the entire range of the link capacity. Moreover, such oscillations hinder spatial reuse and decrease throughput significantly. We are developing a new dynamic bandwidth allocation algorithm called Distributed Virtual-time Scheduling in Rings (DVSR). The key idea is for nodes to compute a simple lower bound of temporally and spatially aggregated virtual time using per-ingress counters of packet (byte) arrivals. We show that with this information propagated along the ring, each node can remotely approximate the ideal fair rate for its own traffic at each downstream link. Hence, DVSR flows rapidly converge to their ring-wide fair rates while maximizing spatial reuse. To evaluate DVSR, we are using a combination of theoretical analysis, simulation, and implementation, including a proof-of-concept prototype of DVSR on a 1 Gb/sec network processor testbed.
37573411
On Coverage Problems of Directional Sensor Networks
In conventional sensor networks, the sensors often are based on omni-sensing model. However, directional sensing range and sensors are great application chances, typically in video sensor networks. Thus, the directional sensor network also demands novel solutions, especially for deployment policy and sensor’s scheduling. Toward this end, this paper evaluates the requirements of deploying directional sensors for a given coverage probability. Moreover, the paper proposes how to solve the connectivity problem for randomly deployed sensors under the directional communication model. The paper proposes a method for checking and repairing the connectivity of directional sensor networks for two typical cases. We design efficient protocols to implement our idea. A set of experiments are also performed to prove the effectivity of our solution. The results of this paper can be also used to solve the coverage problem of traditional sensor networks as a special case.
6591453
Opportunistic fair scheduling over multiple wireless channels
Emerging spread spectrum high-speed data networks utilize multiple channels via orthogonal codes or frequency-hopping patterns such that multiple users can transmit concurrently. In this paper, we develop a framework for opportunistic scheduling over multiple wireless channels. With a realistic channel model, any subset of users can be selected for data transmission at any time, albeit with different throughputs and system resource requirements. We first transform selection of the best users and rates from a complex general optimization problem into a decoupled and tractable formulation: a multiuser scheduling problem that maximizes total system throughput and a control-update problem that ensures long-term deterministic or probabilistic fairness constraints. We then design and evaluate practical schedulers that approximate these objectives.
16164675
Energy efficient routing with adaptive data fusion in sensor networks
While in-network data fusion can reduce data redundancy and hence curtail network load, the fusion process itself may introduce significant energy consumption for emerging wireless sensor networks with vectorial data. Therefore, fusion-driven routing protocols for sensor networks cannot optimize over communication cost only -- fusion cost must also be accounted for. Towards this end, we design a novel routing algorithm, called Adaptive Fusion Steiner Tree (AFST), for energy efficient data gathering in sensor networks that jointly optimizes over the costs for data transmission and data fusion. Furthermore, AFST evaluates the benefit and cost of data fusion along information routes and adaptively adjusts whether fusion shall be performed. Analytically and experimentally, we show that AFST achieves better performance than existing algorithms including SLT, MFST, and SPT.
10742303
Stability and sensitivity for congestion control in wireless networks with time varying link capacities
While extensive efforts have been devoted to providing optimization based, distributed congestion control schemes for efficient bandwidth utilization and fair allocation in both wireline and wireless networks, a common assumption therein is fixed link capacities. This unfortunately will limit the application scope in multi-hop wireless networks where channels are ever changing. In this paper, we explicitly model link capacities to be time varying and investigate congestion control problems in multi-hop wireless networks. In particular we propose a primal-dual congestion control algorithm which is proved to be trajectory stable in the absence of feedback delay. Different from system stability around a single equilibrium point, trajectory stability Guarantees the system is stable around a time varying reference trajectory. Moreover, we obtain sufficient conditions for the scheme to be locally stable in the presence of delay. Our key technique is to model time variations of capacities as perturbations to a constant link. Furthermore, to study the robustness of the algorithm against capacity variations, we investigate the sensitivity of the control scheme and through simulations to study the tradeoff between stability and sensitivity.
20456243
Energy-Efficient Cooperative Image Processing in Video Sensor Networks
Different from conventional sensor networks, video sensor networks are distinctly characterized by their immense information and directional sensing models. In this paper, we propose an innovative, systematic method for image processing in video sensor networks in order to reduce the workload for individual sensors. Given the severe resource constraints on individual sensor nodes, our approach is to employ the redundancy among sensor nodes by partitioning the sensing task among highly correlated sensors. For an object of interest, each sensor only needs to capture and deliver a fraction of the scene of interests and these partial images can be fused at the sink to reconstruct a composite image. In particular, we detail how the sensing task can be partitioned among the sensors and propose an image fusion algorithms based on epipolar line constraint to fuse the received partial images at the sink. The experimental results show that our approach can achieve satisfactory results and we give detailed discussions on the effects of different system parameters.
206025536
Enumerating near-4-regular maps on the sphere and the torus
In this paper rooted near-4-regular maps on the plane and the torus are counted with formulae with respect to four parameters: the root valency, the number of edges, the inner faces, and nonroot-vertex loops. In particular, the number of rooted near-4-regular maps on those surfaces with exactly k nonroot-vertex loops is investigated.
37778003
Automatic Accurate Cost-Bound Analysis for High-Level Languages
This paper describes a language-based approach for automatic and accurate cost-bound analysis. The approach consists of transformations for building cost-bound functions in the presence of partially known input structures, symbolic evaluation of the cost-bound function based on input size parameters, and optimizations to make the overall analysis efficient as well as accurate, all at the source-language level. The calculated cost bounds are expressed in terms of primitive cost parameters. These parameters can be obtained based on the language implementation or can be measured conservatively or approximately, yielding accurate, conservative, or approximate time or space bounds. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The results helped confirm the accuracy of the analysis.
29049246
Iterative detection for BLAST systems with an arbitrary number of receive antennas
Turbo-coded Vertical Bell Labs Layered Space-Time Architecture (V-BLAST) is a multiple-antenna system employing turbo codes and bit-interleaving to offer flexible rates and high-speed wireless data communications. The conventional detection techniques based on one-shot demodulation and decoding algorithms may suffer poor performance or simply fail when there are fewer receive antennas than transmit antennas or when the multiple-input-multiple-output (MIMO) channel exhibits strong spatial correlations. We propose employing an iterative demodulation and decoding algorithm that solves these problems and greatly extends the applicability of V-BLAST. Simulations demonstrate that iterative V-BLAST offers the best-known performance in a wide range of settings. Through complexity analysis, we show that (a) the incremental computing complexity is small, although additional memory is required, compared with the conventional one-shot maximum likelihood (ML) decoding method, and (b) an iterative algorithm employing generalized sphere decoding will be a low-complexity, memory-reduced, and high-performance solution. We also give extensions to the technique beyond simple V-BLAST. In addition, when feedback from the receiver to the transmitter is available, we illustrate how to adapt code rate, modulation, and the power distribution to take advantage of the channel knowledge. With a combination of the “best in class” receiver performance and the ability to decode V-BLAST transmissions with fewer receive antennas than transmit antennas, the techniques described here can be viewed as key “technology enablers” for BLAST/MIMO in next-generation systems.
10539713
On optimal routing with multiple traffic matrices
Routing optimization is used to find a set of routes that minimizes cost (delay, utilization). Previous work has addressed this problem for the case of a known, static end-to-end traffic matrix. In the Internet, it is difficult to accurately estimate a traffic matrix, and the constantly changing nature of Internet traffic makes it costly to maintain optimal routing by responding to traffic changes. Thus, it is of interest to maintain a set of routes that are "good" for a number of different possible traffic scenarios. In this paper, we explore ways to find an optimal set of routes with multiple traffic matrices to minimize expected cost. We focus on two general approaches, source-destination routing and destination routing. In the case of source-destination routing, we extend existing methods with a single traffic matrix to solve the optimization problem with multiple traffic matrices: we extend the convex optimization solution methods for a single traffic matrix to the multiple traffic matrix case; we also extend the gradient-based solution methods for a single traffic matrix to the multiple traffic matrix case. However, the multiple traffic matrix case requires many more control variables. In the case of destination routing, we encounter many more differences from the single traffic matrix case. The loop-free property, which is valid for the single traffic matrix case, is no longer valid for the multiple traffic matrix case, and it is difficult to extend existing methods for a single traffic matrix to solve the optimization problem with multiple traffic matrices. We show that it is NP-complete even to determine the feasibility of multiple traffic matrices. We thus propose and evaluate a heuristic algorithm for this case.
1409797
On the TCP-Friendliness of VoIP Traffic
Recently, some concerns have been raised regarding whether the rapid growth of the UDP traffic due to the Skype-like applications will throttle down regular TCP users because UDP flows are unresponsive to network congestion, i.e., UDP senders do not reduce their sending rates when congestion occurs in the network. However, most UDP based real time applications, such as Voiceover-IP (VoIP), drop out completely if the user perceived quality becomes unacceptable as the network congestion increases. This user back-off mechanism effectively reduces UDP traffic rate at the aggregated level when the network is congested. In this paper, we investigate the fairness issue between VoIP flows and TCP flows under different network environment. Our study explicitly takes into account both transport layer congestion control mechanism built-into TCP protocol stack and the self-adaptiveness of VoIP users. Various models are developed to characterize VoIP user back-off behaviors in response to call quality degradation resulted from packet loss and delay inside the network. The comparison between VoIP user back-off and TCP rate adaption shows that not only VoIP flows consume much less bandwidth than TCP flows, but also VoIP traffic is indeed very responsive to congestion when the network is overloaded.