Communication Nets: Stochastic Message Flow and Delay

by Leonard Kleinrock

Overview

Considerable research has been devoted to the formulation and solution of problems involving flow within connected networks. Independent of these surveys, an extensive body of knowledge has accumulated on the subject of queues, particularly in regard to stochastic flow through single-node servicing facilities. This text combines studies of connected networks with those of stochastic flow, providing a basis for understanding the general behavior and operation of communication networks in realistic situations.
Author Leonard Kleinrock of the Computer Science Department at UCLA created the basic principle of packet switching, the technology underpinning the Internet. In this text, he develops a queuing theory model of communications nets. Its networks are channel-capacity limited; consequently, the measure of performance is taken to be the average delay encountered by a message in passing through the net. Topics include questions pertaining to optimal channel capacity assignment, effect of priority and other queue disciplines, choice of routine procedure, fixed-cost restraint, and design of topological structures. Many separate facets are brought into focus in the concluding discussion of the simulation of communication nets, and six appendices offer valuable supplementary information.

Product Details

ISBN-13:	9780486151113
Publisher:	Dover Publications
Publication date:	06/10/2014
Sold by:	Barnes & Noble
Format:	eBook
Pages:	224
File size:	12 MB
Note:	This product may take a few minutes to download.

Table of Contents

Preface     v
Preface to the 2007 Dover Edition     vii
Introduction     1
Systems of Flow: Examples     1
A Closer Look     4
The Emphasis     9
Elementary Concepts     10
An Existing Store-and-Forward Communication Net     12
The Model: Assumptions     14
Notation and Further Definitions     16
The Precise Problem Statement     17
Summary of results     19
Analytic Results     19
Experimental Results     26
The problems of an exact mathematical solution to the general communication net     35
Discussion of the General Problem     35
The Tandem Net     40
The Two-node Tandem Net     45
The Independence Assumption     49
The Effect of the Independence Assumption     50
Summary     56
Some new results for multiple-channel systems     57
A Canonical Representation for the Utilization Factor     58
Optimum Number of Channels for a Single-node Facihty     59
Trading Relations among Rate, Capacity, and Message Delay     61
Optimum Assignment of Channel Capacity     63
Conclusions and Extensions     67
Waiting times for certain queue disciplines     71
Priority Queueing     72
A Conservation Law     81
Time-shared Service     84
Conclusions and Extensions     91
Random routing procedures     95
Markov Model: Circulant Transition Matrices     96
The Average Path Length     98
Examples of Nets Included by the Model     100
The K-connected Communication Network     102
Conclusions     104
Simulation of communication nets     107
Specific Network Descriptions     108
Simulation Results     117
Additional Theorems on Alternate Routing Procedures     125
Conclusions     127
Conclusion     129
Summary     129
Suggestions for Further Investigation     130
Appendixes
A Review of Simple Queueing Systems     133
Theorems and Proofs for Chapter 4     141
Theorems and Proofs for Chapter 5     149
Theorems and Proofs for Chapter 6     175
An Operational Description of the Sinmlation Program     189
Alternate Routing Theorems and Their Proofs      195
Bibliography     301
Index     206