QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term end-to-end delay constraint while, similar to Dynamic Network Utility Maximization (DNUM), strives to achieve the maximum network utility aggregated over a fixed time interval. Since capturing temporal dynamics in QoS requirements of sources is allowed in our system model, we incorporate a novel time-coupling constraint in which delay-sensitivity of sources is considered such that a certain end-to-end average delay for each source over a pre-specified time interval is satisfied. We propose DA-DNUM algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Through numerical experiments, we show that DA-DNUM gains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay.
In another set of works @cite_3 @cite_8 @cite_14 @cite_22 , the source delay is incorporated as constraints of the optimization problems. By introducing Virtual Link Capacity Margin (VLCM) to characterize source delay as constraint of the problem, the authors in @cite_14 @cite_4 have proposed a joint rate allocation and scheduling scheme in multi-hop wireless networks. By a different approach in @cite_8 , another variant of NUM problem is formulated to address joint power and rate control. Moreover, in @cite_3 , using an elegant fluid model of multi-class flows with different delay requirements, another distributed and stable delay-aware algorithm is proposed. Despite these single-period NUM-based studies, NUM framework is intrinsically incapable of capturing temporal variations in network characteristics especially when these characteristics evolve with time scales comparable to those of the underlying dual-based algorithms. Generally speaking, (single-period) NUM along with delay constraints is subject to limited degrees of freedom, and as a result, one may face a broad range of infeasible problems. We will investigate this phenomenon in details in our experiments in .
@cite_14 @cite_4 @cite_22 @cite_8 @cite_3
2054629214 2075343554 2949886575 2102224707
Allocating limited resources such as bandwidth and power in a multi-hop wireless network can be formulated as a Network Utility Maximization (NUM) problem. In this approach, both transmitting source nodes and relaying link nodes exchange information allowing for the NUM problem to be solved in an iterative distributed manner. Some previous NUM formulations of wireless network problems have considered the parameters of data rate, reliability, and transmitter powers either in the source utility function which measures an application's performance or as constraints. However, delay is also an important factor in the performance of many applications. In this paper, we consider an additional constraint based on the average queueing delay requirements of the sources. In particular, we examine an augmented NUM formulation in which rate and power control in a wireless network are balanced to achieve bounded average queueing delays for sources. With the additional delay constraints, the augmented NUM problem is non-convex. Therefore, we present a change of variable to transform the problem to a convex problem and we develop a solution which results in a distributed rate and power control algorithm tailored to achieving bounded average queueing delays. Simulation results demonstrate the efficacy of the distributed algorithm. This paper investigates the optimal rate allocation problem with end-to-end delay constraints in multi-hop wireless networks. We introduce Virtual Link Capacity Margin (VLCM), which is the gap between the schedulable link capacity and the maximum allowable flow rate over a link, for link delay control. We formulate the problem as a utility maximization framework with two sets of constraints: 1) capacity and schedulability constraints and 2) end-to-end delay constraints. By dual decomposition of the original optimization problem, we present a control algorithm that jointly tunes the flow rates and VLCMs, through a double-price scheme derived with regard to the constraints: the link congestion price reflecting the traffic load of a link, and the flow delay price reflecting the margin between the average packet delay and the delay requirement of a flow. We prove that the algorithm converges to a global optimum where the aggregate network utility defined over the flow rate set is maximized, while the delay constraints are satisfied. A key feature of our algorithm is it does not rely on a specific traffic model. The algorithm is implemented distributedly via joint wireless link scheduling and congestion control. Simulation results show that our algorithm outperforms heuristic rate allocation algorithms while satisfying the end-to-end delay constraints. In this paper, we consider CSMA policies for scheduling of multihop wireless networks with one-hop traffic. The main contribution of this paper is to propose Unlocking CSMA (U-CSMA) policy that enables to obtain high throughput with low (average) packet delay for large wireless networks. In particular, the delay under U-CSMA policy becomes order-optimal. For one-hop traffic, delay is defined to be order-optimal if it is O(1), i.e., it stays bounded, as the network-size increases to infinity. Using mean field theory techniques, we analytically show that for torus (grid-like) interference topologies with one-hop traffic, to achieve a network load of @math , the delay under U-CSMA policy becomes @math as the network-size increases, and hence, delay becomes order optimal. We conduct simulations for general random geometric interference topologies under U-CSMA policy combined with congestion control to maximize a network-wide utility. These simulations confirm that order optimality holds, and that we can use U-CSMA policy jointly with congestion control to operate close to the optimal utility with a low packet delay in arbitrarily large random geometric topologies. To the best of our knowledge, it is for the first time that a simple distributed scheduling policy is proposed that in addition to throughput utility-optimality exhibits delay order-optimality. We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of 5dj (1-ρj), at a factor 5 loss of throughput, where dj is the path length (number of hops) of flow j and ρj is the effective loading along the route of flow j. Clearly, dj is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network. Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network. Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property.