Algebraic-Topological Formulation and Distributed Control of Packet-Switched Networks of General Topology

Friday, January 21, 2005 - 1:25pm - 3:00pm
Vincent 570
Yiju Chao (Morton Consulting Corporation)
This talk presents a novel algebraic-topological methodology to formulate and design distributed control of traffic flows on packet-switched networks. This formulation is a more natural way to model packet-switched networks than traditional models using the multi-commodity network flow formulation or the queuing network formulation. Using this new framework, we show how the local boundary, coboundary, and Laplacian operators defined for a graph can be used to design distributed control of traffic flows. Our distributed network control design is a two-step paradigm based on the adjoint relation between the node space (0-chains) and the link space (1-chains) of a network. The two-step paradigm includes:

(1) A global outer-loop routing solution that is optimal on the cycle space.

(2) A real-time inner-loop control to load-balance queues formulated on the image of the coboundary operator.

According to the solution in each of these two steps, each network node updates its routing table autonomously based on local information. Even though the algorithm has a distributed implementation, the resulting routing solution is an acyclic flow (no closed loops) that minimizes cost and ensures network stability.