Communication Nets: Stochastic Message Flow and Delay

By Leonard Kleinrock

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.

• Language: English
• Publisher: Dover Publications
• Release date: Jun 10, 2014
• ISBN: 9780486151113

Book preview

Communication Nets

Stochastic Message Flow and Delay

Leonard Kleinrock

Professor of Computer Science

University of California at Los Angeles

Dover Publications, Inc.

Mineola, New York

to my parents,

Anne and Bernard Kleinrock

Copyright

Copyright © 1964, 1992, 2007 by Leonard Kleinrock

All rights reserved.

Bibliographical Note

This Dover edition, first published in 1972 and reissued in 2007, is an unabridged republication of the work originally published in 1964 by the McGraw-Hill Book Company, New York. This 2007 edition contains a new preface by the author.

Library of Congress Cataloging-in-Publication Data

Kleinrock, Leonard.

Communication nets : stochastic message flow and delay / Leonard Kleinrock.

p. cm.

Includes bibliographical references and index.

eISBN-13: 978-0-486-15111-3

1. Telecommunication—Traffic—Mathematics. 2. Statistical communication theory. 3. Stochastic analysis. I. Title.

TK5101.K48 2007

621.382′1—dc22

2006102958

www.doverpublications.com

Preface

The purpose of this monograph is to consider the stochastic flow of message traffic in connected networks of communication centers. The networks considered are channel-capacity limited, and consequently the measure of performance is taken to be the average delay encountered by a message in passing through the net. Questions pertaining to the assignment of channel capacities, effect of priority discipline, choice of routing procedure, and design of topological structure are considered.

For some years, there has been considerable research effort devoted to the formulation and solution of problems concerned with the flow of goods, people, water, etc., in connected networks. The emphasis has been on the study of constant deterministic flow through these nets. Quite aside from this, a large body of knowledge has been accumulating on the subject of queues; the emphasis there has been on stochastic flow through single-node servicing facilities. In our investigation, we combine the connected networks of the first study with the stochastic flow of the second study, emphasizing the operational rather than the combinatorial aspects of the system. Furthermore, owing to the intense interest in communication theory (which has come a long way in developing a general theory of message transmission between two communication centers), we direct our attention to connected networks of communication centers. Our intent is to provide a basis for understanding the general behavior and operation of such communication nets.

In Chapter 1 we discuss the large class of flow and transportation networks and distill from that class the particular form of communication net which is to be considered. In Chapter 2 we summarize the results obtained. The extreme complexity involved in obtaining exact solutions to the problem is demonstrated in Chapter 3, and an assumption necessary to the analysis is introduced and justified. The optimum channel capacity assignment for nets is presented in Chapter 4. Certain questions of queue discipline are considered in Chapter 5, and Chapter 6 deals with a class of random routing procedures. Finally, many of the separate facets of the problem are brought into focus simultaneously in Chapter 7, where the simulation of communication nets is discussed. In the concluding chapter we outline a number of extensions of the work which are worthy of investigation. An extensive set of appendixes is included which contains the details of proof for the various theorems presented in the main text.

This monograph is based upon a doctoral thesis submitted to the Department of Electrical Engineering of M.I.T. in December, 1962. Since the material is presented from first principles, the monograph is self-contained; Appendix A has been included for the reader unfamiliar with queueing theory. It is assumed that the reader is conversant with calculus and elementary probability theory.

I am happy to have this opportunity to express my sincere appreciation to Prof. Edward Arthurs for his encouragement and guidance in the supervision of the thesis upon which this monograph is based. I am also indebted to Dr. Herbert P. Galliher, Jr., whose work in the M.I.T. Operations Research Center was supported in part by the Army Research Office (Durham), and to Professor Claude E. Shannon, Donner Professor of Science at M.I.T., for their suggestions and ideas, which proved invaluable. In addition, I wish to express my thanks to the M.I.T. Lincoln Laboratory¹ for the interest and encouragement offered to me as a Staff Associate and for the use of the TX-2 digital computer. The informative discussions with numerous members of the M.I.T. and Lincoln Laboratory communities were extremely useful and are deeply appreciated.

Leonard Kleinrock

---

¹ Operated with support from the U.S. Air Force.

Preface to the 2007 Dover Edition

In December, 1962,1 filed my MIT PhD dissertation and was delighted to learn that it was to be published by McGraw Hill in their MIT Lincoln Laboratory Series. The book was published in 1964, was translated into a number of other languages, demand for it rapidly increased and was sold out in a short time. Some years later, Dover saw a need to republish the out-of-print book, and did so in 1972. Soon, it, too, was sold out and for the second time it went out of print. Since then, it has become a collector’s item due to its importance in developing the foundational technology of the Internet. Consequently, it could not be more appropriate that Dover has, once again, chosen to reprint this current volume as the latest of its scientific classic works.

This book provided the mathematical theory of data networks nearly a decade before the Internet was born. It is gratifying to look back at my work reported in 1962 and identify how it anticipated so many of the elements that we find in today’s Internet technology. My stated focus at that time was to … direct our attention to connected networks of communication centers with the intent "… to provide a basis for understanding the general behavior and operation of such communication nets. "

It may interest the reader to understand what motivated me to undertake the research contained in this book and the approach to research that I followed. As a graduate student at MIT in the late 50s/early 60s, I found that most of my classmates were involved with solving problems of Information Theory. Most of the important problems had already been solved and what remained were of lesser consequence. I preferred to work in an area that was far less developed and with a large potential for making important contributions. I also found myself surrounded by computers and it was clear to me that it would not be long before they would need to communicate with each other. At that time, the existing networking solution, namely, circuit switching, was hopelessly inadequate for data communication among computers. Here was an important field of research that was just waiting to be investigated. So I launched on a study of data networks. This work was directly motivated by a desire to study how these data networks could be designed, and to uncover the fundamental principles of their behavior. I did then, and still do, approach a problem with the goal of exposing its underlying structure—what makes a system work well or poorly, what are the basic tradeoffs, are there principles to be found that explain the behavior and results.

I introduced the use of queueing theory as the principal tool for analyzing the behavior and generating the design of these systems. This approach has spawned many generations of analysts across the world who systematically use the tools of queueing theory for the performance evaluation and design of computer and networking systems. The theory allows one to evaluate throughput, response time, buffering, loss, efficiency, etc., namely, many of the system level metrics that determine the performance of data networks. People sometimes get the story backwards and erroneously think that queueing theory led me to data networks; it was quite the other way around. As a result, I was forced to extend the theory of queues in ways that would allow its application to computer networks.

Since my focus, from the beginning, was on large data networks (the title of my 1961 thesis prospectus was, Information Flow in Large Communication Networks), I developed solutions that would allow the networks to scale up to large numbers of nodes. This naturally led me to introduce distributed design technologies and distributed routing algorithms which have been the key elements of the approach taken by the Internet.

The model that resulted from the above considerations led me to develop analytical performance evaluation methods and optimal design procedures for these data networks. Critical to doing the analysis was my introduction of a key assumption, the Independence Assumption, without which the analysis (then and at present) was intractable. With that assumption, I was able to develop the exact equation for mean transit delay, namely, Equation (4.17), which allowed me to solve both the performance analysis as well as the optimal design problems. I introduced the notion of demand access, whereby a user would gain access to networking resources only when needed, rather than on a semi-permanent basis, as was the case for circuit-switching, the networking technology back then. I introduced the concept of breaking messages into fixed length blocks and serving them independently (this later came to be known as packetization). I analytically showed the advantage enjoyed by these short packets in that they could avoid being heavily delayed by long messages in front of them. I coupled demand access with packetization and showed the gains to be had by doing so; this anticipated the technology of packet switching, the main technology for moving data across today’s Internet. A major theme that emerged from the results was that large shared systems had enormous performance advantages. In the domain of distributed routing, I showed that random routing provided resilience to net work failures and disruptions; I also showed that distributed alternate routing provided the ability of the network to adapt the traffic flow to meet the dynamic networking and traffic conditions. In all of this, it was necessary to prove the effectiveness of the model and its assumptions, and to this end, I developed perhaps the first large-scale simulation experiments for data networks which were invaluable in establishing the validity of my work.

I must emphasize that the totality of understanding the full picture (and not just the issue of packetization) had to be developed and elucidated before a convincing body of knowledge could be amassed to prove the case for data networks which would eventually lead to the Internet technology. In my mind, there are three concepts that made the case and which were necessary to render the data networking technology so powerful (they are not referred to by these names in this book, but the basic concepts are to be found there), namely:

A. The key concept of demand access.

The inefficiencies of circuit switching could not be tolerated in data networks. So the concept of demand access, where you only use the resource when you need it (i.e., you actually have data to send), was an underlying idea I had to develop for data networks. Examples of demand access technologies include polling, message switching, packet switching, Ethernet, and asynchronous TDMA. It is important to note that packetization by itself did not by itself lead to the underlying technology that supports the Internet; it helps, and is part of today’s networking technology, but the principles I am here elucidating tell the full story of what contributes to the efficiency of networks. For sure, early and crude store-and- forward networks based on demand access already existed, but no one had elucidated the principles underlying the need for such structures. Moreover, no one had produced a model, much less an analysis of how they performed under stochastic loads. Lastly, there existed no optimal design procedures for laying out the topology, choosing the channel speeds and selecting the routing procedure and routes.

B. The key concept of large shared systems.

Using queueing theory, I was able to examine the trading relations among delay, capacity and load and to show that the larger the channel capacity, at constant load, the smaller the mean delay. In fact the relationship is linear: k times the capacity leads to a reduction in mean delay by a factor of k. Large systems are more efficient.

C. The key concept of distributed control.

Distributed control is essential in the deployment of large data networks. It was important to analyze the behavior of different distributed routing algorithms (alternate routing, random routing, etc.), and to simulate them as well. This exposed the benefits and pitfalls of providing dynamic alternate paths.

One would have thought after this book was widely circulated, that the commercial world of networking would have embraced the new technology. On the contrary, no one cared! In fact AT&T, the largest networking company in the world, alleged that it would never work and, if in fact it did work, they wanted nothing to do with it. That lack of vision on their part was a contributing factor in their demise some years later. Meanwhile, the idea of creating a computer network was spawned at the US Department of Defense Advanced Research Projects Agency (ARPA) when, in the mid-60’s, they realized that an efficient data network was essential to connect together the many research groups they were supporting in computer science. It was not until 1969 that the network actually came to life, and the first node of this network was established in my UCLA laboratory (where I was, by then, a tenured professor). Earlier that year, Neil Armstrong became the first man to walk on the Moon. That and some other major events in 1969 were widely reported around the world. But the birth of the Internet was hardly noticed. Ironically, the most significant among those events turned out to be the Internet. This network was initially called the ARPANET, and it evolved into the Internet as time progressed. Many people contributed to the establishment and growth of the Internet (see for example, The Past and Future History of the Internet, www.isoc.org/internet/history/brief.shtml), and it is heartwarming to see the effect that this current book has had on its development.

The impact of the Internet since its birth in 1969 has been phenomenal. It has dramatically changed some fundamentals of our existence in that it has reduced the barrier of distance, increased the reach of an individual, increased the number of people with whom you can interact, increased the speed of that interaction, increased the level of anonymity, reduced the cost of communication, and greatly expanded the quantity of accessible information. It has dramatically reduced the barriers to interaction such as economic, political, social, cultural, and racial. One’s physical handicaps or appearance are no longer an issue, as illustrated so well in Peter Steiner’s famous 1993 cartoon of a large dog, sitting at a computer, and saying to a small dog, On the Internet, no one knows you’re a dog. The Internet creates communities, provides access to vast stores of knowledge, amplifies one’s power to affect things, facilitates accountability, and enables event reporting to travel the globe at the speed of light. At the same time there is a dark side of the Internet which is cause for considerable concern; this includes pornography, pedophilia, spam, viruses, denial of service, fraud, identity theft, etc. On balance, though, the Internet has provided enormous good and is likely to do so for some time to come.

Author’s Biography

DR. LEONARD KLEINROCK developed the mathematical theory of packet networks, the technology underpinning the Internet, while a graduate student at MIT. This was in the period 1960–1962, nearly a decade before the birth of the Internet which occurred in his laboratory when his Host computer at UCLA became the first node of the Internet in September 1969. He wrote the first paper and published the first book on the subject; he also directed the transmission of the first message ever to pass over the Internet. He was listed by the Los Angeles Times in 1999 as among the 50 People Who Most Influenced Business This Century. He was also listed as among the 33 most influential living Americans in the December 2006 Atlantic Monthly.

Leonard Kleinrock received his Ph.D. from MIT in 1963. He has served as a Professor of Computer Science at the University of California, Los Angeles since then, serving as Chairman of the department from 1991–1995. He received his B.E.E degree from CCNY in 1957 and his M.S. degree from MIT in 1959. He also received Honorary Doctorates from CCNY in 1997, from the University of Massachusetts, Amherst in 2000,