Source-linked AI summary
Optimal Scheduling for Fair Resource Allocation in Ad Hoc Networks with Elastic and Inelastic Traffic
Juan Jose Jaramillo, R. Srikant
TL;DR
Prior wireless resource-allocation frameworks did not incorporate strict per-packet delay deadlines. This paper uses a frame-based optimization model and dual decomposition to jointly schedule elastic and inelastic traffic. The resulting algorithm provides fair resource allocation, meets inelastic QoS constraints, and stabilizes the network.
Problem
Optimization-based wireless resource-allocation frameworks addressed long-term throughput but did not account for strict per-packet delay bounds.
Source: §I · p. 1Method
A frame-based optimization model and dual decomposition yield a joint congestion-control and scheduling algorithm using deficit counters for inelastic service.
Source: §I · p. 1, §VIII · p. 7Results
The algorithm converges in an appropriate stochastic sense, keeps the network stable, and fulfills inelastic flows’ QoS constraints.
Source: §I · p. 1, B. Convergence Results · p. 5, §VIII · p. 7Takeaways & Limitations
Deficit counters, interpreted as Lagrange multipliers, place elastic and inelastic scheduling in a common framework.
Source: A. Scheduler and Congestion Controller · p. 4, §VIII · p. 7
Abstract
from arXiv · showhide
This paper studies 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, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality of service (QoS) requirements of packets with deadlines in the optimization framework. 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.
I. INTRODUCTION
Existing optimization frameworks for wireless resource allocation do not account for strict per-packet delay bounds. This paper extends the framework to jointly allocate resources to elastic and inelastic flows while meeting inelastic packet deadlines.
I. INTRODUCTION
- Optimization-based approaches for best-effort wireless traffic had not incorporated strict per-packet delay bounds.The cited prior frameworks address long-term throughput and QoS requirements such as minimum bandwidth, but not strict deadlines.Source: §I · p. 1
- The paper builds on inelastic-flow scheduling work for collocated networks, where all links interfere, and extends the modeling paradigm to ad hoc networks.Earlier strict-deadline scheduling papers – provided approximate solutions.Source: §I · p. 1
- A frame-based model incorporates packet deadlines into optimization and supports a common framework for elastic and inelastic flows.Packets arrive at a frame’s start and must be served by its end.Source: §I · p. 1
- The proposed framework jointly schedules best-effort and deadline-constrained flows, meeting fairness objectives and required on-time delivery fractions for inelastic flows.It integrates both traffic types into a common max-weight scheduling framework and proves stochastic convergence and network stability.Source: §I · p. 1
II. NETWORK MODEL
The network model represents ad hoc communication as directional links and distinguishes elastic traffic from flows with per-packet deadlines. It models arrivals and channels over fixed-duration frames, with channel information either available at the frame’s start or only after transmission.
II. NETWORK MODEL
- The network is a directed graph whose links represent transmissions from one node to another.A link exists from n1 to n2 when n1 can transmit to n2.Source: §II · p. 1
- Inelastic flows have maximum per-packet delay requirements, whereas elastic flows have no such requirements.Source: §II · p. 1
- Time is divided into frames of T slots; inelastic packets arrive at frame beginnings, have deadlines of T slots, and face a per-link deadline-loss limit p_l.Packets missing their deadlines are discarded.Source: §II · p. 1
- Arrivals and channel states are modeled across frames, with channel states independent between frames and of arrivals.Inelastic arrivals are independent between frames; their stated zero- and one-arrival probabilities support the later Markov-chain analysis.Source: §II · p. 2
- The model covers known channel states at frame beginnings and unknown states revealed after transmission, with Bernoulli channel capacity in the latter case.Known-state capacity is a non-negative random variable; unknown-state feedback permits at most one packet per link per slot.Source: §II · p. 2
III. PROBLEM FORMULATION
The formulation chooses feasible schedules and elastic traffic injections to maximize network utility while meeting inelastic deadline-loss requirements. Schedules must respect link capacities and interference constraints.
III. PROBLEM FORMULATION
- A feasible schedule assigns inelastic and elastic transmissions across links and slots while respecting interference and per-link channel capacity.Simultaneously transmitting links must not interfere; total scheduled packets at a link cannot exceed its capacity in a slot.Source: §III · p. 2
- At each frame’s start, the decision is how to schedule links and how many elastic packets to inject, subject to inelastic deadline-loss limits and stable elastic queues.Source: §III · p. 2
- The formulation uses expected inelastic and elastic service under each arrival and channel state, subject to QoS and capacity constraints.Source: §III · p. 2
- The objective includes a weight vector that can allocate additional bandwidth fairly to inelastic flows beyond their QoS needs.The formulation assumes arrivals and loss-probability requirements are feasible.Source: §III · pp. 2–3
IV. SOLUTION USING DUAL DECOMPOSITION
The dual-decomposition approach separates the optimization into scheduling and congestion-control decisions, then updates dual variables iteratively. Those variables can be interpreted as virtual queues for service deficits and elastic backlog.
IV. SOLUTION USING DUAL DECOMPOSITION
- The dual function is used to derive the decomposed optimization problem.Source: §IV · p. 3
- For fixed arrivals and channel state, the linear objective and convex-combination service bounds allow the optimization to decompose into subproblems.Source: §IV · p. 3
- An iterative algorithm updates the Lagrange multipliers using a fixed step size and a nonnegative projection.The passage specifies a fixed parameter Xmax greater than the optimal elastic rate.Source: §IV · pp. 3–4
- The deficit variable can be interpreted as a virtual queue tracking service shortfall against the inelastic loss target, while the elastic variable tracks elastic queue size.The deficit-counter interpretation connects the algorithm to dual decomposition.Source: §IV · p. 4
A. Scheduler and Congestion Controller
The online scheduler uses inelastic arrivals and channel state, alongside link queues, to make scheduling decisions. A virtual deficit queue tracks whether each link is meeting its inelastic service target.
A. Scheduler and Congestion Controller
- Elastic arrivals are randomized with mean ˜x∗ l (k) and variance bounded by σ2 e; positive probabilities of zero and one arrivals ensure an irreducible, aperiodic Markov chain.The passage notes that similar assumptions could replace these two probability conditions.Source: A. Scheduler and Congestion Controller · p. 4
- For each inelastic packet arrival, a coin with heads probability 1 −pl determines whether one is added to the deficit counter.Equivalently, ˜ail(k) is binomial with parameters ail(k) and 1 −pl.Source: A. Scheduler and Congestion Controller · p. 4
- The virtual queue d_l(k) tracks link l’s service deficit against the target loss probability for deadline-expired packets.The paper relates this deficit queue to a Lagrange multiplier in the dual-decomposition approach.Source: A. Scheduler and Congestion Controller · p. 4
- The scheduler’s inputs include inelastic arrivals and channel state, while elastic queue lengths are also tracked.For fixed ǫ and w, the optimal scheduler is a function of ai(k), c(k), d(k), and q(k).Source: A. Scheduler and Congestion Controller · p. 4
B. Convergence Results
The online algorithm is within O(ε) of the optimal value, while its stability analysis bounds queues and service deficits and establishes fulfillment of inelastic constraints.
B. Convergence Results
- Bounding expected Lyapunov drift for the deficit-counter and queue state establishes positive recurrence and an O(1/ε) bound on total service deficit and queue length.The state (d(k), q(k)) is treated as an irreducible and aperiodic Markov chain.Source: B. Convergence Results · p. 5
- The scheduling and congestion-control algorithm fulfills all links’ inelastic requirements.The result is stated as fulfillment of all inelastic constraints.Source: B. Convergence Results · p. 5
- For every link, the arrival rate into its deficit counter is no greater than the counter’s departure rate.The paper identifies this rate relation as the corollary’s meaning.Source: B. Convergence Results · p. 5
- The online algorithm is within O(ε) of the optimal value, with smaller ε trading reduced optimality gap for larger service deficits and aggregate queues.The result is stated for the online algorithm relative to the optimal value of the static problem.Source: B. Convergence Results · p. 5
VI. UNKNOWN CHANNEL STATE
The unknown-channel formulation retains the joint treatment of elastic and inelastic traffic while making scheduling decisions using expected channel state. Its algorithm meets inelastic QoS constraints, bounds service deficits and queues by O(1/ε), and keeps the objective within O(ε) of optimal.
VI. UNKNOWN CHANNEL STATE
- The model defines feasible schedules by interference constraints and a limit of one packet per link per time slot.The optimization is formulated similarly to the known-channel case; the scheduling algorithm is the stated difference.Source: §VI · pp. 5–6
- The scheduling problem chooses a distribution over feasible schedules, subject to per-link deadline-loss limits, while elastic traffic seeks utility-maximizing rates with stable queues.Expected mixed-traffic service accounts for channel success probability and both elastic and inelastic scheduling.Source: §VI · pp. 5–6
- The unknown-channel algorithm meets inelastic QoS constraints, bounds expected service deficits and queue lengths by O(1/ε), and keeps the mean objective within O(ε) of optimal.Scheduling decisions use the expected channel state, which the network must know or estimate.Source: §VI · p. 6
VII. SIMULATIONS
The simulations examine how ε and link weights affect the algorithm and whether a greedy scheduler approaches optimal scheduling. The reported rates are quite close across schedulers, while dropping probabilities remain below the requirement.
VII. SIMULATIONS
- The simulation uses a 10-link network with three time slots per frame, a 0.1 deadline-loss requirement, and a channel state revealed at each frame’s start.Link arrivals are Bernoulli with mean 0.6 packets per frame, channel states are Bernoulli with mean 0.96, and utility is logarithmic.Source: §VII · p. 6
- The greedy heuristic orders links by weight, schedules the heaviest remaining link, removes interfering links, and repeats until no more links can be scheduled.It is explored as a lower-search alternative to the exhaustive search required by the max-weight scheduler.Source: §VII · p. 6
- The plotted deficit counters and queues compare their evolution under optimal and greedy scheduling for different link weights.The figures cover wl values of 0, 3, and 6.Source: §VII · p. 6, Figure 2 · p. 7, Figure 3 · p. 7
- For real-time traffic, the authors recommend choosing wl an order of magnitude larger than ε to maintain small deficits and avoid large variations in service that could affect perceived quality.The simulations examine deficit and queue behavior at wl values of 0, 3, and 6.Source: §VII · p. 7, Figure 2 · p. 7, Figure 3 · p. 7
- The two schedulers achieve quite close rates in simulations while keeping dropping probabilities below the requirement.The comparison is reported for the average-service figures and the dropping-probability figures.Source: §VII · p. 7, Figure 5 · p. 7
VIII. CONCLUSIONS
The paper presents an optimization framework and online algorithm for congestion control and scheduling of elastic and inelastic traffic under general interference, arrivals, and time-varying channels. It reports stability and QoS guarantees, a common deficit-counter framework, and a trade-off controlled by ε.
VIII. CONCLUSIONS
- The framework covers general interference graphs, arrival processes, and time-varying channels, and decomposes into an online algorithm that makes optimal decisions while maintaining stability and inelastic QoS constraints.The algorithm jointly addresses congestion control and scheduling for elastic and inelastic traffic.Source: §VIII · p. 7
- Deficit counters let the scheduling problem for elastic and inelastic flows use a common framework and have an interpretation as Lagrange multipliers.The paper attributes the deficit-counter interpretation to –[14].Source: §VIII · p. 7
- The simulations show that ε controls a trade-off: smaller values approach the optimum more closely while increasing service deficits and aggregate queue length.The conclusion also notes that performance depends on ε in allocating resources to both traffic types.Source: §VIII · p. 7, Figure 6 · p. 8, Figure 7 · p. 8
- For the unknown-channel case, the paper does not consider channel feedback at the end of each time slot, leaving that issue for future work.Source: §VIII · p. 7
APPENDIX A PROOF OF LEMMA 1
The appendix proves Lemma 1 using auxiliary lemmas and a linear-objective fact about optimization over a convex hull. It then derives a time-averaged bound under a finite initial Lyapunov-function expectation.
APPENDIX A PROOF OF LEMMA 1
- Two conditional lemmas introduce bounds involving non-negative B6 and positive B7, with the latter comparing solutions to (3) and (5).Both lemmas condition on d(k)=d and q(k)=q.Source: Appendix A · pp. 8–9
- A linear objective allows optimization over the convex hull of S(ai(k), c(k)) because an optimal point lies in S(ai(k), c(k)).The fact is used to justify the optimization step in (6).Source: Appendix A · p. 9
- The proof defines fixed-state capacity regions and overall network capacity through expected inelastic and elastic rates.The overall capacity definition averages rates over arrival and channel states.Source: Appendix A · p. 9
APPENDIX B PROOF OF THEOREM 1
- Summing the inequalities over frames and dividing by K yields a limit expression when the initial expected Lyapunov function is finite.The argument uses the non-negativity of V.Source: Appendix B · p. 10