ABSTRACT: In the distributed processing environment characteristic of the management information systems of today, a need to superimpose an additional information flow onto an existing computer communication network arises frequently. The situation may result from a company's expanding needs for communication over its private or a shared network, or because a new user company is joining an existing shared network. In order to accommodate the new information flow without negatively affecting the waiting times for the previously contracted communications, network capacity may have to be expanded. We present an algorithmic method for least-cost capacity expansion of a set of network paths preselected to carry the incremental information flows. Owing to the insights gained as a result of extensive computational experiments, we then provide a simplified technique applicable to a broad class of cases. Polynomial time complexity of the algorithms included in the presented methodology points to its practicality.
Key words and phrases: distributed information systems, computer communication networks, network capacity expansion, multi-path networks