Browse Prior Art Database

A COMPUTER COMMUNICATION NETWORK DESIGN ALGORITHM FOR DIFFERENT CLASSES OF PACKETS

IP.com Disclosure Number: IPCOM000148684D
Original Publication Date: 1976-Dec-21
Included in the Prior Art Database: 2007-Mar-30
Document File: 32 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Maruyama, K.: AUTHOR [+4]

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 32

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.

[This page contains 1 picture or other non-text object]

Page 2 of 32

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

[This page contains 1 picture or other non-text object]

Page 3 of 32

Page 1

1. INTRODUCTION

   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 [5]: 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...