A COMPUTER COMMUNICATION NETWORK DESIGN ALGORITHM FOR DIFFERENT CLASSES OF PACKETS
Original Publication Date: 1976-Dec-21
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Maruyama, K.: AUTHOR [+4]
XC 6333 (127207) 1 2 2 1 j 7 6 Communications 29 ?ages
XC 6333 (127207) 1 2 / 2 1 j 7 6
Communications 29 ?ages
A COMPUTER COMMUNICATION NETWORK DESIGN ALGORITHM FOR DIFFER- ENT CLASSES OF PACKETS
K. Maruyama, L. Fratta* and D.T. Tang
Computer Sciences Department
IBM Thomas J. Watson Research Center Yorktown Heights, New York 10598 Typed by Linda P. Rubin on CMC (KM.958)
ABSTRACT: A typical operating environment of a packet switching (store-and-forward) computer communication network is that it is shared by many users with different types of classes of packets. Thus, a well-designed network must provide accesses and performance assurance to all packet classes. Packets may be classified in a very general fashion by types of users, messages, applications, transactions, response time requirements, packet parameters such as packet rate and length, and by network parameters such as source-destination and path length.
The main goal of this paper is to present an algorithm for designing such a communication network. The algorithm presented consists of heuristic algorithms for discrete link capacity assignment, priority assignment and flow assignment problems with the additional feature which allows one to alter network topology interactively. Sample results of the overall network design are also given.
LISlITED DISTRIBUTION NOTICE
This report has been submitted for publication elsewhere and has been issued as a Research Report for early dissemination of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.
Copies may be requested from:
IBh1 Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights. Xew York 10598
Since 1969, when ARPANET Project emerged as the first major experimental store-and- forward packet switching network, many other computer communication networks have been built and are now in operation [l - 41. In the meanwhile a great deal of research effort has been devoted to study store-and-forward packet switching networks from various points of view including application environment, protocols, flow control, and performance analysis [5 -
101. Although the networking technology is still evolving, the basic notion of packet switching is certainly quite cost-effective in a wide range of computer communication network applica- tions.
To evaluate the effectiveness of a communication network, two cost-performance parameters have been widely used : the total cost of the network, D, and the average
packet delay, Z, which is the average time experienced by a packet travelling from its source to destination. With those two parameters, a general network design problem may be formulated to determine optimum values...