Bi-Path Networks and Multicommodity Flows

Abstract

This paper considers the feasibility of simultaneous multicommodity flows with specified values in a capacity-limited communication network. A class of “bi-path networks” is defined and some basic topological properties of such networks are derived. It is shown that a bi-path network B satisfies a requirement matrix R if, and only if, the value of each simple cutset in B is no smaller than the corresponding cutset value in the “requirement network” R. This result can be readily extended to the case with time-varying requirements. The optimal synthesis can be solved using linear programming techniques if linear cost can be assumed. © 1964, IEEE. All rights reserved.