System and method for increasing the speed of distributed single and multi-commodity flow using second order methods

摘要

A system and method for increasing the speed of flow of a quantity of data or of a plurality of data types through a communication system. The communication system comprises a plurality of switches including a source and a sink, each of the switches connected to a neighboring switch by a communication link having a capacity, each of the links having a pair of queue buffers, and one queue buffer of each pair of queue buffers is located at each switch connected by a link. For a single data type, a flow is computed for each link as a function of a last previous amount of flow across the same link. In the multi-data type case, a weighted queue difference is computed as a function of a last previous amount of flow between the same pair of queues and an amount of flow f_i of said data type i is routed across each said link such that &Sgr;_1≦i≦Kf_i (&Dgr;′_i(e)−f_i) is maximized. In other embodiments of the invention, the system and method resolves the contention between different data types for the capacity of a communication link with and without a normalization factor, and adjusts flow so as not to exceed the capacity of a communication link or the amount of a data available to be routed by the sending queue buffer.