Computationally efficient cross-layer algorithm for fair Dynamic Bandwidth Allocation

The problem of Dynamic Bandwidth Allocation (DBA) is inherent to systems that employ Bandwidth on Demand (BoD). An important issue in such systems is to be able to react efficiently to the always-changing traffic requests of users. Moreover, it is realistic to assume large populations sharing system resources and thus efficient methods to distribute bandwidth are mandatory. Further desirable system features include guarantees on fairness and on Quality of Service (QoS). Actual trends propose to reach convergence among networks at IP-level. This encourages the design of algorithms that sustain IP-defined QoS (e.g. in DiffServ) and forces to exchange information between layers. We talk then about cross-layer designs. In this paper, we propose a novel method to compute the allocation accomplishing the previous requirements of fairness, QoS and time efficiency. Our work departs from known results on decomposition techniques (primal and dual) and combines these in a novel, interleaved and coupled fashion. In the dual decomposition technique, the subgradient method is typically used to adpatively compute the price the resource is charging to the users. In our approach, the price is selected taking into account the value that users are willing to pay, which comes from the primal decomposition. The method is compared to the well-known bisection one and results effectively demonstrate superior performance in terms of convergence speed and computational complexity.