Optimizing multi-linear Product form networks using Dinkelbach’s algorithm

# 8


We aim to obtain analytical solutions to the optimal rate setting problem for product form queueing networks. We model the network as a multi-linear product form Markov network and use Lagrange dual optimization technique which enables us to decompose the global optimization problem into a local optimization problem at each of the transmitter buffers. We then use Dinkelbach algorithm and gradient-based optimization to obtain analytical solutions for the rate setting problem. We have already established the existence of strong duality for the case of M/M/1 queuing systems which established the feasibility of minimizing the Lagrange dual function. We extend the same solution approach to solve the average cost minimization problem for a cache-enabled wireless system modeled as a two-phase birth-death process. Since optimizing this system in the original form is intractable, we modify the network by introducing auxiliary transitions which reduces the complexity of the system and helps us obtain analytical solutions for optimal transmission rates. Our method has the advantage of approximating the original two-phase system asymptotically. In addition, due to the structure of the two phase network, the solutions obtained from the system with auxiliary transitions can be shown to be the optimal solutions for the original system for vanishing values of the auxiliary admission rate parameters. We then extend the analysis for the rate setting problem for G-network, which are multilinear networks with non-linear traffi c equations. We will conclude by introducing applications of G-networks for content discovery in P2P networks and Energy Sensor networks.

Rahul R

Rahul R is a PhD student at the Department of ECE, IISc. He is a member of the Network Engineering Lab under the guidance of Prof. Utpal Mukherji. His research interest is on optimal resource allocation in communication networks.