Optimization Based Rate Control for Communication Networks with Inter-Session Network Coding

• Main Authors: Khreishah, A., Chih-Chun Wang, Shroff, N.B.
• Format: Conference Proceeding
• Language: English
• Subjects: Communication networks; Communication system control; Convergence; Distributed algorithms; Distributed control; Galois fields; Lagrangian functions; Network coding; Optimal control; Partial response channels
• ISSN: 0743-166X; 2641-9874
• DOI: 10.1109/INFOCOM.2008.25

In this paper we develop a distributed rate control algorithm for multiple-unicast-sessions when network coding is allowed. Building on our recent flow-based characterization of network coding, we formulate the problem as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where the objective function is the sum of the utilities based on the rates supported by each session. With some manipulation on the Lagrangian of the formulated problem, a distributed algorithm is developed with no interaction between intermediate nodes, and each source having the freedom to choose its own utility function. The only information required by the source is the weighted sum of the queue length updates of each link, which can be piggy-backed on the acknowledgment messages. In addition to the optimal rate control algorithm, we propose a decentralized pairwise random coding scheme (PRC) that is optimal when a sufficiently large finite field is used for network coding. The convergence of the rate control algorithm is proved analytically and verified by extensive simulations. Simulations also demonstrate the advantage of our algorithm over the state-of-the-art in terms of throughput and fairness.