Time: Wednesday, March 16, 2011, 12:00pm-1:00pm
Title: Network Congestion Control with Markovian Multipath Routing
Speaker: Cristóbal Guzmán, Georgia Tech ACO program
Location: ISyE executive classroom
Abstract:
Routing and congestion control are basic components of packet-switched communication networks. While routing is responsible for determining efficient paths along which the sources communicate to their corresponding receivers, congestion control manages the transmission rate of each source in order to keep network congestion within reasonable limits.
Mathematical modeling in network engineering copes with both of these problems, but usually in a separate manner, i.e., solving one problem when the variables of the other are fixed. One of the main models for rate control is the so called Network Utility Maximization (NUM), which is a convex optimization formulation for steady state flows. On the other hand, there has been some progress in the last 10 years in the design of distributed routing protocols for large networks, even for the multipath case.
In this work, we present a model that combines rate control and multipath routing, where rate control is based on the NUM model, and routing is based on discrete choice distribution models that lead to a Markovian Traffic Equilibrium. The combination of these models leads to a system of equations that corresponds to the optimality conditions of a strictly convex unconstrained program of low dimension, where the variables are link congestion prices. This characterization allows to establish existence and uniqueness of equilibria.
If time allows, we will show an algorithm (the Method of Succesive Averages) that solves this problem. Moreover, we show how this algorithm can be implemented in a distributed fashion by slight modifications on current internet protocols.
This is a joint work with Roberto Cominetti (Universidad de Chile).
No comments:
Post a Comment