Maxflow Based Routing for Traffic Engineering and Sustained High Bitrate Applications

We present a data routing mechanism based on graph- theoretic maximum flow algorithms. The goal is to maximize data flow between source and destination pairs. Though multiple paths are used for data transmission, the goal of this mechanism is primarily to maximize throughput rather than provide fault-tolerance or quality-of-service as with other multipath mechanisms. Challenges relating to selecting participating links and routers are identified and addressed. Implementation aspects of traditional maximum flow algorithm categories; path augmentation and preflow- push are discussed and the choice of preflow-push is motivated. Simulations give insight into the effect of the reported power-law growth of connectivity on maximum flow algorithms by showing that strict power-law growth in detrimental to throughput. Growth by addition of random links gives better overall throughput than power-law growth. Finally, we show that though packet reordering is extensive in a maximum flow session, the reordering is deterministic leading to the possibility of designing transport algorithms that can use this predictability in minimizing the effect on reordering sensitive applications.