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 the recent years, many studies have employed NUM framework to propose efficient protocols and algorithms for network applications under different types of traffics, assumptions, and constraints (see @cite_13 and the references therein). In particular, by extending the basic single-period version of NUM framework, a number of studies have incorporated end-to-end delay @cite_3 @cite_12 @cite_6 @cite_8 @cite_14 @cite_0 @cite_5 @cite_9 to address the requirements of the delay-sensitive traffic and applications. In these works, end-to-end delay either is included in the objective function of NUM (e.g., @cite_12 @cite_5 @cite_9 @cite_18 ) or is augmented as constraints to the underlying optimization problem (e.g., @cite_3 @cite_8 @cite_14 ).
@cite_18 @cite_14 @cite_8 @cite_9 @cite_3 @cite_6 @cite_0 @cite_5 @cite_13 @cite_12
2130339513 2075343554 2054629214 2097878592 2951024449 2171028981 2077252365 2158893758 2018446679
TCP IP can be interpreted as a distributed primal-dual algorithm to maximize aggregate utility over source rates. It has recently been shown that an equilibrium of TCP IP, if it exists, maximizes the same delay-insensitive utility over both source rates and routes, provided pure congestion prices are used as link costs in the shortest-path calculation of IP. In practice, however, pure dynamic routing is never used and link costs are weighted sums of both static as well as dynamic components. In this paper, we introduce delay-sensitive utility functions and identify a class of utility functions that such a TCP IP equilibrium optimizes. We exhibit some counter-intuitive properties that any class of delay-sensitive utility functions optimized by TCP IP necessarily possess. We prove a sufficient condition for global stability of routing updates for general networks. We construct example networks that defy conventional wisdom on the effect of link cost parameters on network stability and utility. 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. 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. A fluid model of multi-class flows with priority packet scheduling is considered for controlling the flow rates, their end-to-end delays and their packet losses. We derive a globally stable distributed rate and delay combined control when no information time lags are present. By properly sizing the router buffers, the stable rates attain the end-to- end delay requirements without any packet loss. By further enhancing the network with bandwidth reservation and admission control, we also show that minimum rate is guaranteed. The stability properties of the discrete time version of our control are also derived when no information time lags are present. The stability in the presence of information time lags is studied numerically by computing the delay and rate trajectories for a real test-bed network. This paper studies the problem of utility maximization for clients with delay based QoS requirements in wireless networks. We adopt a model used in a previous work that characterizes the QoS requirements of clients by their delay constraints, channel reliabilities, and delivery ratio requirements. In this work, we assume that the utility of a client is a function of the delivery ratio it obtains. We treat the delivery ratio for a client as a tunable parameter by the access point (AP), instead of a given value as in the previous work. We then study how the AP should assign delivery ratios to clients so that the total utility of all clients is maximized. We apply the techniques introduced in two previous papers to decompose the utility maximization problem into two simpler problems, a CLIENT problem and an ACCESS-POINT problem. We show that this decomposition actually describes a bidding game, where clients bid for the service time from the AP. We prove that although all clients behave selfishly in this game, the resulting equilibrium point of the game maximizes the total utility. In addition, we also establish an efficient scheduling policy for the AP to reach the optimal point of the ACCESS-POINT problem. We prove that the policy not only approaches the optimal point but also achieves some forms of fairness among clients. Finally, simulation results show that our proposed policy does achieve higher utility than all other compared policies. We investigate the problem of designing delay-aware joint flow control, routing, and scheduling algorithms in general multi-hop networks for maximizing network utilization. Since the end-to-end delay performance has a complex dependence on the high-order statistics of cross-layer algorithms, earlier optimization-based design methodologies that optimize the long term network utilization are not immediately well-suited for delay-aware design. This motivates us in this work to develop a novel design framework and alternative methods that take advantage of several unexploited design choices in the routing and the scheduling strategy spaces. In particular, we reveal and exploit a crucial characteristic of back pressure-type controllers that enables us to develop a novel link rate allocation strategy that not only optimizes long-term network utilization, but also yields loop free multi-path routes between each source-destination pair. Moreover, we propose a regulated scheduling strategy, based on a token-based service discipline, for shaping the per-hop delay distribution to obtain highly desirable end-to-end delay performance. We establish that our joint flow control, routing, and scheduling algorithm achieves loop-free routes and optimal network utilization. Our extensive numerical studies support our theoretical results, and further show that our joint design leads to substantial end-to-end delay performance improvements in multi-hop networks compared to earlier solutions. Wired and wireless data networks have witnessed a rapid proliferation of multimedia applications such as Internet video streaming, video conferencing, etc. A desirable key feature for multimedia transmission over multiuser environments is the ability of adapting rate and quality of video stream to different QoS conditions. The most efficient approach to address the scalability of multimedia applications is to encode video streams in compliance with the scalable video coding (SVC) standard, which is proposed as an extension to H.264 AVC standard. This paper addresses the rate control and bandwidth sharing for multimedia applications that are relying on SVC-encoded video streams. In previous studies, idealistic utility functions, mainly in the form of a staircase function, were used to cast the rate allocation for SVC-encoded streams as an optimization problem. These utility functions make the optimization problem non-convex and even non-differentiable, for which achieving optimality through dual-based approaches proves quite challenging. Towards this goal, we introduce an accurate analytical model of the utility function for SVC-encoded video streams. Using the abovementioned utility model and adopting the utility-proportional optimization approach, we come up with a convex formulation and propose a dual-based distributed algorithm for rate allocation of SVC-encoded streams. To the best of our knowledge, this is the first work that focuses on an accurate utility function modeling for SVC-encoded streams. Simulation experiments show that the proposed algorithm is quite efficient in achieving the convergence towards the global optimality. Network protocols in layered architectures have historically been obtained on an ad hoc basis, and many of the recent cross-layer designs are also conducted through piecemeal approaches. Network protocol stacks may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems. This paper presents a survey of the recent efforts towards a systematic understanding of layering as optimization decomposition, where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. There can be many alternative decompositions, leading to a choice of different layering architectures. This paper surveys the current status of horizontal decomposition into distributed computation, and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and channel coding. Key messages and methods arising from many recent works are summarized, and open issues discussed. Through case studies, it is illustrated how layering as Optimization Decomposition provides a common language to think about modularization in the face of complex, networked interactions, a unifying, top-down approach to design protocol stacks, and a mathematical theory of network architectures We consider congestion control in a network with delay sensitive insensitive traffic, modelled by adding explicit delay terms to the utility function measuring user's happiness on the Quality of Service (QoS). A new Network Utility Maximization (NUM) problem is formulated and solved in a decentralized way via appropriate algorithms implemented at the users (primal) and or links (dual). For the dual algorithm, delay-independent and delay-dependent stability conditions are derived when propagation delays are taken into account. A system with voice and data traffic is considered as example and the properties of the congestion control algorithm are assessed.