Simultaneous routing and resource allocation via dual decomposition

By Lin Xiao, Mikael Johansson, Stephen P. Boyd. IEEE Transactions on Communications, 2004

628 citations recorded by the source corpus.

In wireless data networks, the optimal routing of data depends on the link capacities which, in turn, are determined by the allocation of communications resources (such as transmit powers and bandwidths) to the links. The optimal performance of the network can only be achieved by simultaneous optimization of routing and resource allocation. In this paper, we formulate the simultaneous routing and resource allocation (SRRA) problem, and exploit problem structure to derive efficient solution methods. We use a capacitated multicommodity flow model to describe the data flows in the network. We assume that the capacity of a wireless link is a concave and increasing function of the communications resources allocated to the link, and the communications resources for groups of links are limited. These assumptions allow us to formulate the SRRA problem as a convex optimization problem over the network flow variables and the communications variables. These two sets of variables are coupled only through the link capacity constraints. We exploit this separable structure by dual decomposition. The resulting solution method attains the optimal coordination of data routing in the network layer and resource allocation in the radio control layer via pricing on the link capacities.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/5e5355c2b8ff0cdeae83df7fbeef1d7501176db5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

On the Complexity of Scheduling in Wireless Networks (2006, background): “Most of the above cross-layer optimization problems have been shown to exhibit a mathematical decomposition [2, 8].”
Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes (2015, background): “Distributed optimization has received a renewed attention from the control and machine learning communities due to its wide applications in areas such as formation control [1], resource allocation [2], sensor fusion in wireless sensor networks [3]–[5] and distributed learning [6] and just to name a ”
Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications (2007, background): “The primal–dual solution in Section III-B was first proposed in [19], and that in Section III-C was first proposed in [39].”
Dual methods for nonconvex spectrum optimization of multicarrier systems (2006, methodology): “These methods, for example, were used recently in [23] for a joint routing and resource allocation problem.”
Cross-Layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks (2006, background): “Recent publications along this line of “layering as optimization decomposition” [5] includes [31], [8] for TCP/IP interaction, [34] for routing and resource allocation, [4], [16] for TCP and physical layer, and [3], [17], [18], [32] for joint TCP and media access control or scheduling.”
Minimum-cost multicast over coded packet networks (2005, background): “The rate vectorz, consisting ofziJ , (i, J) ∈ A, is called a subgraph, and we assume that it must lie within a constraint setZ for, if not, the packet queues associated with one or more hyperarcs becomes unstable (for examples of constraint set s Z that pertain specifically to multi-hop wireless net”
A tutorial on cross-layer optimization in wireless networks (2006, background): “• When the data rate of a link is a concave function of its own power assignment [43] (which implies no interference between links).”
Optimal Resource Allocation for MIMO Ad Hoc Cognitive Radio Networks (2008, background): “…of this paper is on any-to-any CR networks , problems similar to (P1) arise naturally when applying dual decomposition to a cross-layer network optimization problem, where the weights play the role of Lagrange multipliers associated with the physical layer link capacity constraints; see e.g., [29].”
Optimal multiuser spectrum balancing for digital subscriber lines (2006, positive): “The dual decomposition has been applied in other communication problems with convex objective functions such as joint routing and resource allocation [18] and power allocation in the vector broadcast channel [19].”
Event-Triggered Feedback in Control, Estimation, and Optimization (2010, background): “This includes estimation [56, 69, 33], source localization [56], data gathering [15, 14], routing [46], control [77], resource allocation [55, 89] in sensor networks, resource allocation in wireless communication networks [86, 16], congestion control in wired communication networks [36, 44], and opt”