DESIGN ALGORITHM FOR PACKET-SWITCHING NETWORKS WITH DIFFERENT CLASSESOF PACKETS - CAPACITY, PRIORITY, AND FLOW ASSIGNMENT UNDER END-TO-ENDPACKET DELAY CONSTRAINT

This paper proposes a design algorithm for packet-switching networks w ith different classes of packets under end-to-end packet delay constra int and a design algorithm for fault-tolerant networks. The former is a heuristic capacity, priority, and flow assignment algorithm which lo cally minimizes the network cost while satisfying a constraint that th e average transmission delay of each class of packets between two arbi trary nodes never exceed a value predetermined for the class. This alg orithm is composed of three subalgorithms and the cost minimization is pursued by iterating these algorithms as long as the constraint is sa tisfied. The latter is a design algorithm for a fault-tolerant network which satisfies the foregoing constraint even if an arbitrary single link fails. With this algorithm, an assignment with relatively large c ost but satisfying the constraint is obtained first. Then a procedure of reducing the capacity of a link whose effect on cost reduction is g reat but whose effect on path delay increase is not so great is iterat ed to reduce the network cost as long as the constraint is satisfied.