|
Summary of Results to Date:
A)
Theory:
Analysis of mixing times and convergence of distributed algorithms in
wireless networks; Analysis of collisions in WiFi; Fluid models of TCP
that capture Ack-clocking; Analysis of impact of uncertainty on protocols;
Impact of heavy tail on content distribution networks; Poisson counter
models for networks with LRD traffic; Analysis of burst attacks;
Stochastic approximation theory for LRD noise.
B)
Designs:
Distributed CSMA algorithms for ad-hoc wireless networks that enable
simple protocols that control the congestion, routing, and MAC to
maximize the utility of the flows; WiFi protocols with higher throughput;
faster-converging power control algorithms for wireless networks; new key
generation algorithms; Methods to mitigate the effect of heavy tails by
file partitioning and by alternate routing.
à
top
Significance to DoD:
The new distributed algorithms for
wireless networks have the potential of revolutionizing Ad Hoc Networks
by enabling the design of simple, robust, and efficient protocols.
The improved WiFi protocols increase the throughput by a significant
factor.
The fundamental theoretical research on LRD will produce new mitigation
methods such as optimal fragmentation and diversity routing.
à
top
Scientific Contributions:
Distributed Algorithms for Wireless Networks: These are
cross-layer protocols that control congestion, routing, and medium access
to maximize the utility of the flows in the network. The previously known algorithms were
the “maximum backpressure” algorithms based on a primal-dual solution of
a utility maximization.
Unfortunately, these algorithms require finding the independent
set with the maximum backpressure and this is a complex step that
requires the exchange of control information and solving a NP-hard
problem. The new algorithms are
based on a different formulation: maximizing the utility minus a multiple
of the distance between the ideal schedule and the current schedule,
parametrized by node backoff parameters.
The gradient algorithm for this problem distributes into decisions
by the nodes based on only local information. These algorithms were then extended to
anycast and mutlicast from a single source using network coding. See
[C9]. The theoretical advance is to show that the actual algorithm that
uses backlogs as a proxy for the actual gradient converges to the optimal
solution and achieves the maximum long-term utility. See [C10] and [C8].
We studied the problem of congestion control and scheduling in ad hoc
wireless networks that have to support a mixture of best-effort and
real-time traffic. Optimization and stochastic network theory have been
successful in designing architectures for fair resource allocation to
meet long-term throughput demands. However, strict packet delay deadlines
were not considered in this framework previously. In [P8], we propose a
model for incorporating the quality of service (QoS) requirements of
packets with deadlines in the optimization framework, building upon a
model introduced by Hou, Borkar and Kumar for an access point-controlled
network. The solution to the problem results in a joint congestion
control and scheduling algorithm which fairly allocates resources to meet
the fairness objectives of both elastic and inelastic flows, and
per-packet delay requirements of inelastic flows.
In [P9], we considered multiuser scheduling in wireless networks with
channel variations and flow-level dynamics. Recently, it has been shown
that the MaxWeight algorithm, which is throughput-optimal in networks
with a fixed number users, fails to achieve the maximum throughput in the
presence of flow-level dynamics. In this paper, we propose a new
algorithm, called workload-based scheduling with learning, which is
provably throughput-optimal, requires no prior knowledge of channels and
user demands, and performs significantly better than previously suggested
algorithms.
à
top
Analysis of Collisions in Wireless Networks. Some wireless
protocols use a form of reservation mini-slots to limit collisions. In [P10], Jian Ni and R. Srikant
developed an algorithm to limit collisions in a wireless network by using
contention mini-slots. The probability that a link becomes active if it
does not hear a conflicting transmission increases with its backlog in a
judicious way. The resulting set of active links is a time-reversible
Markov chain that favors the independent sets with a large sum of
backlogs. They show that this algorithm achieves the maximum throughput.
In [C10], Jiang and Walrand study a protocol where nodes use a short
"RTS-CTS" exchange to indicate whether they want to transmit.
If a node is successful, it transmits a packet with a duration that
increases with the backlog of the node. They prove that this algorithm
achieves maximum throughput.
Utility-Maximizing Protocols for Processing Networks. In a processing network, a task uses
parts and resources to produce new parts.
Examples include logistics management, complex mission scheduling,
hospital resource allocation and intervention scheduling, and assembly
plant management. Multiple
military operations involve such resource allocation and task scheduling
problems. For these networks, a
myopic maximum backpressure algorithm may not achieve the optimal network
utility. We developed in [C7] a
new class of algorithms, called deficit maximum weight, that achieve the
maximum utility. The key idea is to augment the state to add enough
memory and avoid the task starvation that greedy scheduling causes.
à
top
High-Throughput WiFi protocols.
A central problem in WiFi MAC protocols is that packet errors
may be caused either by transmission errors or by collisions. The remedies for these types of loss
are quite different: In case of transmission errors, the nodes should
reduce the transmission rate to reduce the packet error rate; in case of
collisions, the nodes should backoff or increase the packet length but
not reduce the transmission rate.
In this work, the type of collision is identified and the nodes
can take the appropriate corrective action. More specifically, the work developed
three techniques: 1) Estimating the probability of collision to guide the
automatic rate fallback can improve the throughput by 150%; 2) Using
estimates of the SNR can improve the throughput by 625%; 3) Adjusting the
packet size to maximize throughput (with a golden section algorithm)
increases the throughput by 200%-300%.
See [C5] and [C6].
Impact of Uncertainty on Protocols. Protocols that attempt
to maximize some performance metric may be very sensitive of uncertainty
about network characteristics. In
this study, we demonstrate that relaying protocols that attempt to
maximize the worst-case throughput based on the uncertainty about the
knowledge of other relays may perform poorly even as nodes exchange more
and more information to improve their knowledge. We also show that more optimistic
protocols perform better. Thus, an
excess of caution may hurt protocol performance. See [C11].
à
top
Fluid Models of Ack-Clocking in TCP. The sources of TCP connections
synchronize their operations on the acknowledgments that they
receive. Standard TCP fluid models
ignore this effect. We show that
correcting the models to capture ack-clocking enables to characterize the
correct stability region.
UMAss Team Research. The
group at UMass is working on the following three areas:
1) the use of multipath in wireless networks, 2) capturing the effects of
LRD on networks through the use of Poisson Counter driven stochastic
differential equations, 3) characterizing large graphs through sampling.
In the context of multipath we
have developed mathematical results on how how multipath can be used to
reduce the tail behavior of the delay distribution. We consider two scenarios, redundant
routing, where a copy of a file is transmitted over every path till it is
received at the destination, and split routing where the path is split up
between the paths. For general channel models we show that the delay
distribution is characterized by a power law tail and that the choice of
which of redundant or split routing to use depends on the channel statistics. In the context of PCSDE models of LRD,
we have developed an SDE representation of Reed's model for generating a
double Pareto distribution. We
have used PCSDEs to explore the benefits of pacing for reducing
burstiness and improving network performance. Last, we have started an investigation
of different techniques for sampling network graphs and are exploring how
the shape of the distribution affects their performance.
à
top
Content Distribution Networks and Heavy Tails. Barlas Oguz and Venkat Anantharam
have studied the problem of scaling of catalog size with network size in
peer-to-peer (P2P) content distribution systems that use a push-to-peer
architecture (i.e. a server seeds the peers with the content in an
intelligent way prior to the P2P downloads). For demand statistics that
are heavy tailed (which is the case in reality, according to empirical
NetFlix data) they find that the scaling can be proportional to network
size in some regimes, a promising result compared to earlier results in
the area that used less realistic demand models. Future work will focus
on understanding the impact of long-range dependence in data sources on
the delay in compression/decompression algorithms.
Stochastic Approximation Theory for LRD Noise. Vivek Borkar and Venkat Anantharam
have developed a general stochastic approximation (SA) theorem that
applies when the noisy observations are heavy tailed and/or long-range
dependent. This theorem can be used as a tool for analyses of the
behavior of SA-based algorithms when the noisy observations have such
characteristics, thus providing a pathway to a considerable increase in
our understanding of the performance of SA-based algorithms in a wide range of control and networking
scenarios.
à
top
Fisher Information. Venkat
Anantharam has studied Fisher information (a statistical characteristic
of the ability to estimate in parametric models, including heavy-tailed
models) with a view towards developing more widely applicable entropy
power inequalities and determined that certain results published in the
literature are wrong, by giving explicit counterexamples (see [P7]).
Dynamic Control Formulation of Protocols. The Caltech group worked on a
dynamic formulation of protocols.
Protocol layering can be interpreted as optimization decomposition
where different layers jointly solve a global optimization problem when
each layer solves a subproblem using only local information over a subset
of the optimization variables and coordinates with other layers
(subproblems) through functions of primal and dual variables
(interfaces). These optimization
problems define the constraints that deconstrain at the core of the
protocol stack and allow diverse applications and hardware platforms,
giving rise to architectures that are robust and evolvable. For example, network utility
maximization (NUM) has been extended to model the multiple protocol
layers, including transport layer (congestion control), routing,
scheduling and network coding in wireless networks [P5, P6]. These models however are ``static’’ in
the sense that they describe only the equilibrium state and are oblivious
to network dynamics. We have
extended the static NUM model to finite-horizon optimal control models in
[C1] that not only maximizes the aggregate utility at the terminal time, but
also integrates the transient dynamics of congestion control
algorithms. We derive the cost
functions that the transients of the primal and dual algorithms
optimize. This approach allows the
design of congestion control algorithms that are distributed and
automatically stable.
à
top
Mitigation of LRD by Optimal Fragmentation. It has been recently discovered that
heavy-tailed file completion (transfer time can result from protocol
interaction even when file sizes are light-tailed. A key to this
phenomenon is the RESTART feature where if a file transfer is interrupted
before it is completed, the transfer needs to restart from the beginning.
We show in [C13] that independent or bounded fragmentation produces
light-tailed file completion time as long as the file size is
light-tailed, i.e., in this case, heavy-tailed file completion time can
only originate from heavy-tailed file sizes. We prove that if the failure
distribution has non-decreasing failure rate, then constant fragmentation
minimizes expected file completion time. This optimal fragment size is
unique but depends on the file size. We present a simple blind
fragmentation policy where the constant fragment size is independent of
the file size and prove that its expected file completion time is
asymptotically optimal when file size increases. Finally, we show that under both the
optimal and blind fragmentation policies, if the file size is
heavy-tailed, then the file completion time is (necessarily) heavy-tailed
with the same tail parameters.
Optimal
Power Allocation. Maximizing
the minimum weighted SIR, minimizing the weighted sum MSE and maximizing
the weighted sum rate in a multiuser downlink system are three important
performance objectives in joint transceiver and power optimization, where
all the users have a total power constraint. We show in [C12, C14] that, through
connections with the nonlinear Perron-Frobenius theory, jointly
optimizing power and beamformers in the max-min weighted SIR problem can
be solved optimally in a distributed fashion. Then, connecting these
three performance objectives through the arithmetic-geometric mean
inequality and nonnegative matrix theory, we solve the weighted sum MSE
minimization and weighted sum rate maximization optimally in the low to
moderate interference regimes using fast algorithms.
à
top
Annual Meetings Slides
Year One
Review (9/09/2009 - OSU)
The Year One Review was a
joint meeting of the two teams funded by this project. Our team presented
the exciting results obtained so far. This meeting will stimulate further
collaboration among the two groups.
Dr. Harry Chang started the
meeting by re-iterating his hope that these two teams will make
substantial progress on the understanding of LRD in networks and will
contribute improved designs that can be of value to DoD.
ADCN Overview (Jean Walrand)
Heavy
Tails and Long Range Dependence in Networks; Stochastic
Approximations for LRD Noise (Venkat Anantharam; presented by Barlas
Oguz)
Protocols
for Wireless Networks (Jean Walrand)
Throughput
Enhancement in Wireless LANs via Loss Differentiation (Avideh Zakhor,
presented by Michael Krishnan)
Hybrid Q-CSMA: A Distributed Scheduling
Algorithm for Wireless Networks (R. Srikant)
An
SDE Model for Power Law (Don Towsley and Bo Jiang)
Can
Multipath Mitigate Power Law Delays (presented by Wei Wei)
File fragmentation to mitigate
heavy-tailed delay (Low)
Network arch theory
(Doyle)
Nonconvex power
control in ad hoc wireless networks (Tan)
à
top
Publications
Journal Papers -
Accepted:
[P1] C. W. Tan and
A. R. Calderbank, "Multiuser Detection of Alamouti Signals,"
IEEE Transactions on Communications, Vol. 57, No. 7, pp. 2080-2089, Jul.
2009. PDF
[P2] C. W. Tan, D.
P. Palomar and M. Chiang, "Energy-Robustness Tradeoff in Cellular
Network Power Control," IEEE/ACM Transactions on Networking, Vol.
17, No. 3, pp. 912-925, Jun. 2009. PDF
[P3] K. Jacobsson,
L. L. H. Andrew, A. K. Tang, S. H. Low and H. Hjalmarsson, "An
Improved Link Model for Window Flow Control and Its Application to FAST
TCP, " in IEEE Transactions on Automatic Control, March 2009. PDF
[P4] Chen, L., T.
Cui and S. H. Low, " A Game-theoretic Framework for Medium Access
Control," IEEE Journal of Selected Areas in Communications,
26(7):1116-1127, September 2008. PDF
Journal Papers -
Submitted:
[P5] Chen, L., S. H.
Low and J. C. Doyle, "Random Access Game and Medium Access Control
Design," IEEE/ACM Transactions on Networking, submitted 2008. PDF
[P6] Chen, L., T.
Ho, M. Chiang, S. H. Low and J. C. Doyle, "Congestion Control for
Multicast Flows with Network Coding," IEEE Transactions on Information
Theory, submitted 2008.
[P7] Venkat Anantharam,``Counterexamples
to a proposed Stam inequality on finite groups," IEEE Transactions
on Information Theory, submitted August 2009.
Conference
Presentations - Accepted:
[C1] Javad Lavaei,
John Doyle and Steven Low, "Congestion Control Algorithms from Optimal
Control Perspective," IEEE Conference on Decision and Control, Dec
2009. PDF
[C2] K. Jacobsson,
L. L. H. Andrew and A. Tang, "Stability and Robustness Conditions
using Frequency Dependent Half Planes," IEEE Conference on Decision
and Control, Dec 2009. PDF
[C3] M. Wang, C. W.
Tan, A. Tang and S. H. Low, "How Bad is Single Path Routing? "
Proc. IEEE GLOBECOM, Honolulu, Hawaii, Nov 30-Dec 4, 2009. PDF
[C4] C. W. Tan, M.
Chiang and R. Srikant, "Optimal Power Control and Beamforming in
Multiuser Downlink Systems," Proc. Asilomar Conference on Signals,
Systems and Computers, Monterey, CA, Nov 2009.
[C5] W. Song, M.
Krishnan, and A. Zakhor, “Adaptive Packetization for Error-Prone
Transmission over 802.11 WLANs with Hidden Terminals,” IEEE International
Workshop on Multimedia Signal Processing, Rio de Janeiro, Brazil, October
2009. PDF
[C6] M. Krishnan, S.
Pollin and A. Zakhor, "Local Estimation of Collision Probabilities
in 802.11 WLANs With Hidden Terminals," IEEE Globecom 2009 Wireless
Networking Symposium (GC'09-WNS), Honolulu, HI, December 2009. PDF
[C7] Libin Jiang and
Jean Walrand, "Utility-Maximizing Scheduling for Stochastic
Processing Networks," Forty-Seventh Annual Allerton Conference,
Illinois, USA September 2009.PDF
[C8] Libin Jiang and
Jean Walrand, "Convergence and Stability of a Distributed CSMA
Algorithm for Maximal Network Throughput," IEEE Conference on
Decision and Control, Dec 2009. PDF
Conference
Presentations - Presented:
[C9] Libin Jiang and
Jean Walrand, "A Distributed CSMA Algorithm for Throughput and
Utility Maximization in Wireless Networks," Forty-Sixth Annual
Allerton Conference, Illinois, USA September 23-26, 2008. PDF
[C10] Libin Jiang
and Jean Walrand, "Approaching Throughput-Optimality in a
Distributed CSMA Algorithm: Collisions and Stability," Mobihoc 2009,
New Orleans, LA, May 2009. PDF
[C11] Jiwoong Lee
and J. Walrand, "Reliable relaying with uncertain knowledge,"
Game Theory for Networks, vol., no., pp.82-87, 13-15 May 2009. PDF
[C12] C. W. Tan, M.
Chiang and R. Srikant, "Maximizing Sum Rate and Minimizing MSE on
Multiuser Downlink: Optimality, Fast Algorithms, and Equivalence via
Max-min SIR," Proc. IEEE ISIT, Seoul, South Korea, Jun 28-Jul 3,
2009. PDF
[C13] Jayakrishnan
Nair and Steven H Low, "Optimal Job fragmentation (Extended
Abstract)", The Eleventh Workshop on Mathematical Performance
Modeling and Analysis, Seattle, WA, June 2009; Also in Performance
Evaluation Review, 2009. PDF
[C14] C. W. Tan, M.
Chiang and R. Srikant, "Fast Algorithms and Performance Bounds for
Sum Rate Maximization in Wireless Networks," Proc. IEEE INFOCOM, Rio
de Janerio, Brazil, Apr 20-25, 2009. PDF
[C15] M. Suchara, L.
L. H. Andrew, R. Witt, K. Jacobsson, B. P. Wydrowski, and S. H. Low,
"Implementation of Provably Stable MaxNet," in Proc. of
BROADNETS 2008, London, UK, September 2008. PDF
Conference
Presentations - Submitted:
[C16] B. Gauvin, B.
Ribeiro, B. Liu, D. Towsley, J. Wang. "Measurement and Analysis of
Publishing Characteristics on MySpace," submitted to INFOCOM 2010.
[C17] Y. Cai, P.-C.
Lee, W. Gong, D. Towsley. "On the Mitigation of Traffic Correlation
Attacks on Router Queues," submitted to INFOCOM 2010.
[C18] J. J. Jaramillo
and R. Srikant. Optimal Scheduling for Fair Resource Allocation in Ad Hoc
Networks with Elastic and Inelastic Traffic. http://arxiv.org/abs/0907.5402
[C19] S. Liu, L.
Ying and R. Srikant. Throughput-Optimal Opportunistic Scheduling in the
Presence of Flow-Level Dynamics. http://arxiv.org/abs/0907.3977
[C20] Jian Ni, Bo
(Rambo) Tan, R. Srikant, "Q-CSMA: Queue-Length Based CSMA/CA
Algorithms for Achieving Maximum Throughput and Low Delay in Wireless
Networks," Submitted on 15 Jan 2009.
à
top
Acknowledgement
This work is supported by ARO MURI Award
W911NF-08-1-0233.
|
