Packet-Switched Network Design with Constraints on the Circuit Discreteness.

The packet-switched network design problem can be formulated as a capacity and flow assignment problem (CFAP). The CFAP of an elementary network consisting of one tandem switch (TS) and n local switches (LSs) has been analyzed, and economical configurations shown in previous papers. This paper extends the study to include cases in which there are constraints on circuit discreteness. A large-scale network usually employs a hierarchical structure with elementary networks used as structural units. In addition, the most economical structure of an elementary network in a hierarchical network is ascertained. The first assumption is that circuit speed is restricted to a predetermined discrete number (multiple of unit speed), and either one or no circuit can be installed per link. When the elementary network represents the entire small-scaled network, economical regions of star, mesh and combined star/mesh are complicated. This is because effective traffic packing to a discrete capacity circuit sometimes yields more economical network configurations. When the elementary network is a structural unit in a large-scale network, star occupies most of the economical region because a tandem circuit is always installed for carrying external traffic. The second assumption is that circuit speed is fixed. If a number of circuits can take real numbers, combined star/mesh is always the minimum cost topology in which internal traffic is assigned co the direct circuit, and external traffic through a tandem switch is assigned to the tandem circuit. When the number of circuits is a natural number, it is more economical in some cases to assign some part of the traffic to a tandem circuit because of the integrity of the number of circuits. [ABSTRACT FROM AUTHOR]