Transcript Distributed Rate Assignments for Broadband CDMA Networks

Distributed Rate Assignments for
Broadband CDMA Networks
Tara Javidi
Electrical & Computer Engineering
University of California, San Diego
Multi-Cell Single Hop CDMA
Motivation
• Wideband CDMA
network with variable
rates
• Mobiles communicate
directly with the base
station
• Base stations are
connected directly to
the traditional IP
network
Rate Assignment Problem
• Limited by congestion constraints in the wired
network
• Limited by interference constraints in the
wireless network
• Objective: Maximize the global network utility
in a distributed adaptive manner
Philosophically Related Works
Wired Networks
[1] F. Kelly. Mathematical Modeling of the Internet. B. Enquist and W. Schmid, editors.
Mathematics Unlimited – 2001 and Beyond, pages 685-702. Springer-Verlaq, 2001.
[2] J. Mo and J. Walrand. Fair End-to-End Window-Based Congestion Control.
IEEE/ACM Transactions on Networking, 8(5):555-567, 2000.
[3]S.H. Low and D.E. Lapsley. Optimization Flow Control I: Basic Algorithm and
Convergence. IEEE/ACM Transactions on Networking, 7(6):861-874, 1999.
Wireless Networks
[3] T. Javidi Distributed Rate Assignment in Multi-sector CDMA. Global
Telecommunications Conference, 2003.
[4] M. Chiang and R. Man. Jointly Optimal Congestion Control and Power Control in
Wireless Multihop Networks. Global Telecommunications Conference, 2003.
[5] X. Lin and N.B. Shroff. The Impact of Imperfect Scheduling on Cross-Layer Rate
Control in Wireless Networks. INFOCOM 2005.
Cross-Layer Design: One-Shot
• One-shot and joint design of a rate assignment
protocol (merging MAC and transport layers)
• Wireless and wired networks generate feedback
based on their respective system constraints
• This feedback allows for dynamic adaptation to
slowly varying network conditions
Iterative Methods and Convergence
Theorem:
If the Lagrange
Givenmultipliers
an appropriate
are computed
choice ofusing
step- a
size,
gradient
the distributed
projection system
method,will
theconverge
rate assignment
to the
becomes
solutionantoiterative
the primal
algorithm
problem
that
(cross-layer
uses feedback
from
optimal)
the network
Related Work
•
[1] X. Lin and N.B. Shroff. Joint rate control and scheduling in multihop wireless networks. CDC’04
•
[2] M. Neely, E. Modiano, and C. Li. Fairness and Optimal Stochastic
Control for Heterogeneous Networks. Infocom’05
+ Due to structure of the problem, we get truly
distributed solutions (little overhead comm)
-
Such solutions require a fundamental re-doing of
the protocol stack in general and transport layer
in particular
Cross-Layer Design: Modular
• MAC and transport layer protocols are separate
• MAC chooses rate using feedback from wireless
• The transport layer chooses rate based on end-end
feedback following a dual controller
• Can this be optimal in a cross-layer sense?
• If no wired core, the answer is yes:
• [1] A. Eryilmaz and R. Srikant. Fair Resource Allocation in Wireless Using
Queue-based Scheduling and Congestion Control
Outline
• Motivation and Overview
• One-Shot Rate Assignments
• Modular Rate Assignments
• The Problem with Dual Methods
• Practical Implementation & Cross-Layer
Coordination
• Observations, Conclusions, & Future
Work
Notation
• CDMA uplink
• dynamic power and spreading gain control
(distributed)
• Network Parameters
• M: number of nodes: N of them wireless
• L: number of sectors
J: number of (wired) links
• Cj: capacity of link j
 ij: routing function
• W: chip bandwidth
gil: channel power gain
• K: acceptable interference b(i): mobile i’s sector
• Node Variables
• Pi: transmit power for user i
•  i: transmit rate for user i at MAC
• xi: transmit rate for user i at transport
One-Shot Problem Formulation
Bench Mark: “cross-layer optimal”
Wired Link
Capacity
subject to
ROT-Controlled
Feasible Rate Vector
Iterative Methods and Convergence
Theorem:
If the Lagrange
Givenmultipliers
an appropriate
are computed
choice ofusing
step- a
size,
gradient
the distributed
projection system
method,will
theconverge
rate assignment
to the
becomes
solutionantoiterative
the primal
algorithm
problem
that
(cross-layer
uses feedback
from
optimal)
the network
Modular Problem Formulation
subject to
i
Coordinate MAC and
Transport Layers
i
xi=i
Dual Controller Fails
O Question: What happens when we try to use the
dual controller/gradient projection?
O Answer: The dual controller fails to converge to
solution of the optimization problem
O We need to maximize a function that is strictly
concave over all the primal variables
Modular Utility Functions
if i is a wired user
if i is a wireless user
A New Modular Problem Formulation
subject to
Economic Interpretation of the Dual
Individual Profit
Maximization
(Transport Layer)
Cross-Layer
Price
for Price for
Coordination
Signal l
Link j
Sector
Iterative Methods and Convergence
IfTheorem:
the Lagrange
Given
multipliers
an appropriate
are computed
choice using
of stepa
gradient
size, theprojection
distributedmethod,
system the
willrate
converge
assignment
to the
becomes
solution
an iterative
to the primal
algorithm
problem
that (cross-layer
uses feedback
from the
optimal)
network
Wired Network Prices
• Individual Lagrange multipliers are generated
using gradient projection
if
if
• This has a well known physical interpretation:
queuing delay!
• Aggregate price qi can be interpreted as end-to-end
queuing delay, which can be measured by each user
Wireless Network Prices
• Individual Lagrange multipliers are generated using
gradient projection
• We can construct a signaling mechanism under which the
aggregate price pi becomes closely related to forward link
SINR on the pilot signal
Cross-Layer Coordination Signal
• Again, individual Lagrange multipliers are
generated using gradient projection
if
if
if
if
Each equality
is are
broken
intototwo
••These
equations
similar
theinequalities
equations
• representing
For each inequality
multipliers computed
delay intwo
queues!
Cross Layer Coordination Signal
• Two imaginary queues
whose associated delays
are i+ and i• Queue 1 is our MAClayer buffer, and Queue
2 is our token bucket
• Token bucket is not
used to regulate service
rate, but to keep track
of the mismatch
between transport and
MAC layer rates
The Role of the New Buffers
• Non-zero delay in the MAC-layer buffer
corresponds to a wireless bottleneck
• The “price” from the actual link prevents the transport layer from
out-running the MAC layer
• Non-zero delay in the token bucket corresponds to
a wired bottleneck
• The “price” from the token bucket prevents the MAC layer from
out-running the transport layer
• Generally only one of the queues is nonempty (i.e.
only one of the constraints is active) at a time
• Without the use of a token bucket, the solution will
converge but not to the desired equilibrium when
wired bottle-neck
Transport Layer Profit Maximization
• Information about the interference levels in the
wireless network is now incorporated into the endto-end queuing delay (qi+i+) minus the token
bucket delay (i-)
• Allows the transport layer to take interference
levels into account without any major modification
of current protocols
• add the token bucket delay to the propagation delay
Mac Layer Profit Maximization
• Wireless sources now receive “credit” for long data
queues (i.e. large  i+) and are penalized for long
token buckets (i.e. large  i-)
• Prioritize wireless users based on their backlog
• (De)Prioritize wireless users based on received
service so far
Simulations
Dynamical Behavior
• Convergence
• Since we wish to interpret the Lagrange multipliers as delay, the
step size must be chosen as t/C
• Convergence is dependent upon the step size being “small enough,”
hence the algorithm being run “fast enough”
• Nested Feedback Loops
• Decoupling of the MAC and transport layer allows for the
corresponding feedback loops to be run at different time scales –
aid in convergence and/or robustness?
• Interaction of three separate feedback loops (MAC, transport, and
power control) plays a significant role in dynamic situations
• Choice of parameters  and K play an important role
Future Work
• Provide a stability analysis
• Use the concept of Markov chain stability for queue
lengths
• Understand the impact of realistic arrival statistics
on the system
• How does statistical multiplexing impact the transient
behavior of the system?
• Determine whether these results can be extended to
other MAC protocols
• Does the addition of the MAC-layer queue and token
bucket provide sufficient coordination for other MAC
schemes?