# Multicommodity flow and circuit switching

Title | Multicommodity flow and circuit switching |

Publication Type | Conference Papers |

Year of Publication | 1998 |

Authors | Leighton T, Rao S, Srinivasan A |

Conference Name | , Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998 |

Date Published | 1998/01/06/9 |

Publisher | IEEE |

ISBN Number | 0-8186-8255-8 |

Keywords | Application 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 |

Abstract | 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 |

DOI | 10.1109/HICSS.1998.649241 |