We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are ‘close’, i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually ‘close’ to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.
展开▼
