Multicommodity flow and circuit switching

TitleMulticommodity flow and circuit switching
Publication TypeConference Papers
Year of Publication1998
AuthorsLeighton T, Rao S, Srinivasan A
Conference Name, Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998
Date Published1998/01/06/9
ISBN Number0-8186-8255-8
KeywordsApplication software, Bandwidth, circuit switching, Computer science, constant-degree expanders, graph theory, High speed integrated circuits, Integrated circuit technology, Laboratories, low congestion, MATHEMATICS, multicommodity flow, National electric code, network routing, path selections, Routing, short flow paths, Switching circuits, switching theory, undirected graphs, virtual circuit routing

Given a set of request pairs in a network, the problem of routing virtual circuits with low congestion is to connect each pair by a path so that few paths use the same link in the network. We build on an earlier multicommodity flow based approach of Leighton and Rao (1996) to show that short flow paths lead to path selections with low congestion. This shows that such good path selections exist for constant-degree expanders with strong expansion, generalizing a result of (Broder et al., 1994). We also show, for infinitely many n, n-vertex undirected graphs Gn along with a set T of connection requests, such that: T is fractionally realizable using flow-paths that impose a (fractional) congestion of at most 1; but any rounding of such a flow to the given set of flow-paths, leads to a congestion of Ω(log n/log log n). This is progress on a long-standing open problem