[Paper] Joint Network-and-Server Congestion in Multi-Source Traffic Allocation: A Convex Formulation and Price-Based Decentralization

Source: arXiv - 2602.03246v1

Overview

The paper tackles a classic yet increasingly relevant problem: how to split traffic from many sources to many service nodes when both the network links and the servers they reach become slower as they get busier. By formulating this joint congestion issue as a convex optimization problem, the authors derive a globally optimal traffic allocation and propose a lightweight, price‑based protocol that can be run in a fully distributed fashion.

Key Contributions

• Convex formulation of joint network‑and‑server congestion – proves that minimizing the weighted end‑to‑end delay across all source‑node pairs is a convex program, guaranteeing a unique global optimum.
• KKT‑based optimality condition – shows that at optimum the total marginal cost (access‑path delay derivative + server congestion price) is equalized across all routes used by a source (Wardrop‑type equilibrium).
• Decentralized pricing algorithm – each server broadcasts a single scalar “congestion price” derived from its current load; sources independently solve tiny convex sub‑problems to update their traffic splits.
• Proof of convergence – the iterative price‑update scheme provably converges to the same solution as the centralized convex optimizer.
• Numerical validation – simulations illustrate fast convergence and reveal how jointly modeling access‑path and server delays changes optimal routing decisions compared to treating them separately.

Methodology

1. System model

   • Sources (s) generate a fixed total traffic demand (D_s).
   • Routes (r) connect a source to a service node; each route has a convex, rate‑dependent access delay (a_r(x_r)) (e.g., queuing on a bottleneck link).
   • Each service node (i) experiences a load‑dependent service delay (q_i!\big(\sum_{r\in i} x_r\big)) (e.g., CPU or disk queue).

2. Objective – Minimize the sum over all sources of the flow‑weighted end‑to‑end delay:

[ \min_{x\ge 0};\sum_{s}\sum_{r\in s} x_r\big[ a_r(x_r) + q_{i(r)}!\big(\sum_{r’\in i(r)} x_{r’}\big)\big] ]

subject to (\sum_{r\in s} x_r = D_s).

3. Convexity proof – Both (a_r(\cdot)) and (q_i(\cdot)) are convex and non‑decreasing, and the objective is a sum of convex functions of linear combinations of the decision variables, thus the whole problem is convex.

4. KKT analysis – Deriving the Karush‑Kuhn‑Tucker conditions yields the marginal cost equality: for any source (s),

[ a’r(x_r) + \lambda{i(r)} = \mu_s \quad\text{if } x_r>0, ]

where (\lambda_i) is the congestion price of node (i) (the derivative of its service delay) and (\mu_s) is the Lagrange multiplier for source (s)’s demand constraint.

5. Decentralized algorithm
   • Each node (i) measures its aggregate incoming rate (L_i) and computes (\lambda_i = q’_i(L_i)). It then broadcasts (\lambda_i) to all sources.
   • Each source solves a separable convex sub‑problem: allocate its demand (D_s) among routes by minimizing (a_r(x_r) + \lambda_{i(r)} x_r). Because the sub‑problem is one‑dimensional per route, it can be solved analytically or with a few Newton steps.
   • Iterate: updated rates change (L_i), which updates prices, and the cycle repeats until convergence.

Results & Findings

• Convergence: The price updates form a contraction mapping under mild assumptions, guaranteeing that the distributed iteration reaches the global optimum.
• Trade‑off insight: When access‑path congestion dominates, traffic prefers shorter routes even if the server is busy; when server congestion dominates, sources shift to less‑loaded servers despite longer network hops. This nuanced behavior disappears in models that ignore one side of the congestion.

Practical Implications

• Edge & Cloud Load Balancing – Service providers can embed a tiny price broadcast (e.g., a scalar in a health‑check API) into their load‑balancers. Edge devices then autonomously decide how much traffic to send to each cloud region, balancing both network latency and server queueing.
• Micro‑service orchestration – In Kubernetes or service‑mesh environments, each pod or node could expose a “congestion price” derived from CPU/IO queues, enabling client services to perform traffic steering without a central controller.
• IoT gateways – Low‑power gateways can compute a simple price from their buffer occupancy and let constrained sensors allocate their uplink traffic efficiently, extending battery life and reducing latency.
• SDN/NFV integration – The algorithm fits naturally into Software‑Defined Networking: the controller can disseminate node prices as part of the control plane, while switches (or VNFs) locally adjust flow tables based on source‑side optimization.

Overall, the approach offers a scalable, low‑overhead alternative to heavyweight centralized schedulers, while still achieving system‑wide optimality.

Limitations & Future Work

• Static demand assumption – The model assumes steady‑state, fixed source demands. Real traffic bursts would require a dynamic extension or predictive control.
• Convex delay functions – The convexity proof hinges on monotone, convex access and service delay models; highly non‑linear or discontinuous behaviors (e.g., TCP congestion control dynamics) are not captured.
• Single scalar price per node – While lightweight, a single price may be insufficient when a node hosts heterogeneous services with different QoS requirements.
• Future directions suggested by the authors include:
  1. Extending the framework to time‑varying demands using online convex optimization.
  2. Incorporating stochastic service times and network variability.
  3. Prototyping the protocol in real SDN testbeds to evaluate overhead and robustness.

Authors

• Tamoghna Sarkar
• Bhaskar Krishnamachari

Paper Information

• arXiv ID: 2602.03246v1
• Categories: cs.DC, cs.NI, eess.SY, math.OC
• Published: February 3, 2026
• PDF: Download PDF