Preface Xv comfortable.Along with routing itself,which is treated in greater depth than elsewhere in the literature,further insights are gained into distributed algorithms.There is also a treatment of topological design and a section on recovery from link failures. Chapter 6 deals with flow control (or congestion control as it is sometimes called).The first three sections are primarily descriptive,describing first the objectives and the problems in achieving these objectives,second,some general approaches,and finally,the ways that flow control is handled in several existing networks.The last section is more advanced and analytical,treating recent work in the area. A topic that is not treated in any depth in the book is that of higher-layer protocols,namely the various processes required in the computers and devices using the network to communicate meaningfully with each other given the capability of reliable transport of packets through the network provided by the lower layers.This topic is different in nature than the other topics covered and would have doubled the size of the book if treated in depth. We apologize in advance for the amount of acronyms and jargon in the book.We felt it was necessary to include at least the most commonly used acronyms in the field,both to allow readers to converse with other workers in the field and also for the reference value of being able to find out what these acronyms mean. An extensive set of problems are given at the end of each chapter except the first.They range from simple exercises to gain familiarity with the basic concepts and techniques to advanced problems extending the results in the text. Solutions of the problems are given in a manual available to instructors from Prentice-Hall. Each chapter contains also a brief section of sources and suggestions for further reading.Again,we apologize in advance to the many authors whose contributions have not been mentioned.The literature in the data network field is vast,and we limited ourselves to references that we found most useful,or that contain material supplementing the text. The stimulating teaching and research environment at M.I.T.has been an ideal setting for the development of this book.In particular we are indebted to the many students who have used this material in courses.Their comments have helped greatly in clarifying the topics.We are equally indebted to the many colleagues and advanced graduate students who have provided detailed critiques of the various chapters.Special thanks go to our colleague Pierre Humblet whose advice,knowledge,and deep insight have been invaluable.In addition, Erdal Arikan,David Castanon,Robert Cooper,Tony Ephremides.Eli Gafni. Marianne Gardner,Paul Green,Ellen Hahne,Bruce Hajek.Robert Kennedy. John Spinelli,and John Tsitsiklis have all been very helpful.We are also grateful to Nancy Young for typing the many revisions and to Amy Hendrikson for computer typesetting the book using the TEX system.Our editors at Prentice-
Preface comfortable. Along with routing itself, which is treated in greater depth than elsewhere in the literature, further insights are gained into distributed algorithms. There is also a treatment of topological design and a section on recovery from link failures. Chapter 6 deals with flow control (or congestion control as it is sometimes called). The first three sections are primarily descriptive, describing first the objectives and the problems in achieving these objectives, second, some general approaches, and finally, the ways that flow control is handled in several existing networks. The last section is more advanced and analytical, treating recent work in the area. A topic that is not treated in any depth in the book is that of higher-layer protocols, namely the various processes required in the computers and devices using the network to communicate meaningfully with each other given the capability of reliable transport of packets through the network provided by the lower layers. This topic is different in nature than the other topics covered and would have doubled the size of the book if treated in depth. We apologize in advance for the amount of acronyms and jargon in the book. We felt it was necessary to include at least the most commonly used acronyms in the field, both to allow readers to converse with other workers in the field and also for the reference value of being able to find out what these acronyms mean. An extensive set of problems are given at the end of each chapter except the first. They range from simple exercises to gain familiarity with the basic concepts and techniques to advanced problems extending the results in the text. Solutions of the problems are given in a manual available to instructors from Prentice-Hall. Each chapter contains also a brief section of sources and suggestions for further reading. Again, we apologize in advance to the many authors whose contributions have not been mentioned. The literature in the data network field is vast, and we limited ourselves to references that we found most useful, or that contain material supplementing the text. The stimulating teaching and research environmient at M.I.T. has been an ideal setting for the development of this book. In particular we are indebted to the many students who have used this material in courses. Their comments have helped greatly in clarifying the topics. We are equally indebted to the many colleagues and advanced graduate students who have provided detailed critiques of the various chapters. Special thanks go to our colleague Pierre Humblet whose advice, knowledge, and deep insight have been invaluable. In addition, Erdal Arikan, David Castanon, Robert Cooper, Tony Ephremides, Eli Gafni, Marianne Gardner, Paul Green, Ellen Hahne, Bruce Hajek. Robert Kennedy, John Spinelli, and John Tsitsiklis have all been very helpful. We are also grateful to Nancy Young for typing the many revisions and to Amv Hendrikson for computer typesetting the book using the TEX system. Our editors at Prentice-
xvi Preface Hall have also been very helpful and cooperative in producing the final text under a very tight schedule.Finally we wish to acknowledge the research sup- port of DARPA under grant ONR-N00014-84-K-0357,NSF under grants ECS-8310698,and ECS-8217668,and ARO under grant DAAG 29-84-K-000. Dimitri Bertsekas Robert Gallager
xvi Preface Hall have also been very helpful and cooperative in producing the final text under a very tight schedule. Finally we wish to acknowledge the research support of DARPA under grant ONR-N00014-84-K-0357, NSF under grants ECS-8310698, and ECS-8217668, and ARO under grant DAAG 29-84-K-000. Dimitri Bertsekas Robert Gallager
3 Delay Models in Data Networks 3.1 INTRODUCTION One of the most important performance measures of a data network is the average delay required to deliver a packet from origin to destination.Furthermore,delay considerations strongly influence the choice and performance of network algorithms, such as routing and fow control.For these reasons,it is important to understand the nature and mechanism of delay,and the manner in which it depends on the characteristics of the network. Queueing theory is the primary methodological framework for analyzing net- work delay.Its use often requires simplifying assumptions since,unfortunately, more realistic assumptions make meaningful analysis extremely difficult.For this reason,it is sometimes impossible to obtain accurate quantitative delay predictions on the basis of queueing models.Nevertheless,these models often provide a ba- sis for adequate delay approximations,as well as valuable qualitative results and worthwhile insights. In what follows,we will focus on packet delay within the communication sub- net (i.e.,the network layer).This delay is the sum of delays on each subnet link traversed by the packet.Each link delay in turn consists of four components. 1.The processing delay between the time the packet is correctly received at the head node of the link and the time the packet is assigned to an outgoing link 111
Delay Models in Data Networks 3.1 INTRODUCTION One of the most important performance measures of a data network is the average delay required to deliver a packet from origin to destination. Furthermore, delay considerations strongly influence the choice and performance of network algorithms, such as routing and flow control. For these reasons, it is important to understand the nature and mechanism of delay, and the manner in which it depends on the characteristics of the network. Queueing theory is the primary methodological framework for analyzing network delay. Its use often requires simplifying assumptions since, unfortunately, more realistic assumptions make meaningful analysis extremely difficult. For this reason, it is sometimes impossible to obtain accurate quantitative delay predictions on the basis of queueing models. Nevertheless, these models often provide a basis for adequate delay approximations, as well as valuable qualitative results and worthwhile insights. In what follows, we will focus on packet delay within the communication subnet (i.e., the network layer). This delay is the sum of delays on each subnet link traversed by the packet. Each link delay in turn consists of four components. 1. The processing delay between the time the packet is correctly received at the head node of the link and the time the packet is assigned to an outgoing link
112 Delay Models in Data Networks Chap.3 queue for transmission.(In some systems,we must add to this delay some additional processing time at the DLC and physical layers.) 2.The queueing delay between the time the packet is assigned to a queue for transmission and the time it starts being transmitted.During this time,the packet waits while other packets in the transmission queue are transmitted. 3.The transmission delay between the times that the first and last bits of the packet are transmitted. 4. The propagation delay from the time the last bit is transmitted at the head node of the link until the time it is received at the tail node.This is pro- portional to the physical distance between transmitter and receiver and is ordinarily small except in the case of a satellite link. This accounting neglects the possibility that a packet may require retransmis- sion on a link due to transmission errors or various other causes.For most links in practice,other than multiaccess links to be considered in Chapter 4,retrans- missions are rare and will be neglected.The propagation delay depends on the physical characteristics of the link and is independent of the traffic carried by the link.The processing delay is also independent of the amount of traffic handled by the corresponding node if computation power is not a limiting resource.This will be assumed in our discussion.Otherwise,a separate processing queue must be in- troduced prior to the transmission queues.Most of our subsequent analysis focuses on the queueing and transmission delays.We first consider a single transmission line and analyze some classical queueing models.We then take up the network case and discuss the type of approximations involved in deriving analytical delay models. While our primary emphasis is on packet-switched network models,some of the models developed are useful in a circuit-switched network context.Indeed, queueing theory was extensively developed in response to the need for performance models in telephony. 3.1.1 Multlplexing of Traffc on a Communication Link The communication link considered is viewed as a bit pipe over which a given num- ber of bits per second can be transmitted.This number is called the transmission capacity of the link.It depends both on the physical channel and the interface (e.g.,modems),and is simply the rate at which the interface accepts bits.The link capacity may serve several traffic streams(e.g.,virtual circuits or groups of virtual circuits)multiplexed on the link.The manner of allocation of capacity among these traffic streams has a profound effect on packet delay. In the most common scheme,statistical multiplezing,the packets of all traffic streams are merged into a single queue and transmitted on a first-come first-serve basis.A variation of this scheme,which has roughly the same average delay per packet,maintains a separate queue for each traffic stream and serves the queues in
Delay Models in Data Networks queue for transmission. (In some systems, we must add to this delay some additional processing time at the DLC and physical layers.) 2. The queueing delay between the time the packet is assigned to a queue for transmission and the time it starts being transmitted. During this time, the packet waits while other packets in the transmission queue are transmitted. 3. The transmission delay between the times that the first and last bits of the packet are transmitted. 4. The propagation delay from the time the last bit is transmitted at the head node of the link until the time it is received at the tail node. This is proportional to the physical distance between transmitter and receiver and is ordinarily small except in the case of a satellite link. This accounting neglects the possibility that a packet may require retransmission on a link due to transmission errors or various other causes. For most links in practice, other than multiaccess links to be considered in Chapter 4, retransmissions are rare and will be neglected. The propagation delay depends on the physical characteristics of the link and is independent of the traffic carried by the link. The processing delay is also independent of the amount of traffic handled by the corresponding node if computation power is not a limiting resource. This will be assumed in our discussion. Otherwise, a separate processing queue must be introduced prior to the transmission queues. Most of our subsequent analysis focuses on the queueing and transmission delays. We first consider a single transmission line and analyze some classical queueing models. We then take up the network case and discuss the type of approximations involved in deriving analytical delay models. While our primary emphasis is on packet-switched network models, some of the models developed are useful in a circuit-switched network context. Indeed, queueing theory was extensively developed in response to the need for performance models in telephony. 3.1.1 Multiplexing of Traffic on a Communication Link The communication link considered is viewed as a bit pipe over which a given number of bits per second can be transmitted. This number is called the transmission capacity of the link. It depends both on the physical channel and the interface (e.g., modems), and is simply the rate at which the interface accepts bits. The link capacity may serve several traffic streams (e.g., virtual circuits or groups of virtual circuits) multiplexed on the link. The manner of allocation of capacity among these traffic streams has a profound effect on packet delay. In the most common scheme, statistical multiplexing, the packets of all traffic streams are merged into a single queue and transmitted on a first-come first-serve basis. A variation of this scheme, which has roughly the same average delay per packet, maintains a separate queue for each traffic stream and serves the queues in _1_11__ Chap. 3
Sec.3.2 Queueing Models-Little's Theorem 113 sequence one packet at a time.However,if the queue of a traffic stream is empty, the next traffic stream is served and no communication resource is wasted.Since the entire transmission capacity C(bits/sec)is allocated to a single packet at a time,it takes L/C sec to transmit a packet that is L bits long. In time-division (TDM)and frequency-division multiplering(FDM)with m traffic streams,the link capacity is essentially subdivided into m portions-one per traffic stream.In FDM,the channel bandwidth W is subdivided into m channels each with bandwidth W/m (actually slightly less because of the need for guard bands between channels).The transmission capacity of each channel is roughly C/m,where C is the capacity that would be obtained if the entire bandwidth was allocated to a single channel.The transmission time of a packet that is L bits long is Lm/C,or m times longer than in the corresponding statistical multiplexing scheme.In TDM,allocation is done by dividing the time axis into slots of fixed length (e.g.,one bit or one byte long,or perhaps one packet long for fixed length packets).Again,conceptually,we may view the communication link as consisting of m separate links with capacity C/m.In the case where the slots are short relative to packet length,we may again regard the transmission time of a packet L bits long as Lm/C.In the case where the slots are of packet length,the transmission time of an L bit packet is L/C,but there is a wait of (m-1)packet transmission times between packets of the same stream. One of the themes that will emerge from our queueing analysis is that statis- tical multiplexing has smaller average delay per packet than either TDM or FDM. This is particularly true when the traffic streams multiplexed have a relatively low duty cycle.The main reason for the poor delay performance of TDM and FDM is that communication resources are wasted when allocated to a traffic stream with a momentarily empty queue,while other traffic streams have packets waiting in their queue.For a traffic analogy,consider an m-lane highway and two cases.In one case,cars are not allowed to cross over to other lanes (this corresponds to TDM or FDM),while in the other case,cars can change lanes (this corresponds roughly to statistical multiplexing).Restricting crossover increases travel time for the same reason that the delay characteristics of TDM or FDM are poor,namely some sys- tem resources (highway lanes or communication channels)may not be utilized while others are momentarily stressed. Under certain circumstances,TDM or FDM may have an advantage.Suppose that each traffic stream has a "regular"character,i.e.,all packets arrive sufficiently apart so that no packet has to wait while the preceding packet is transmitted.If these traffic streams are merged into a single queue,it can be shown that the average delay per packet will decrease,but the variance of waiting time in queue will generally become positive (for an illustration see Prob.3.7).Therefore,if maintaining small variability of delay is more important than decreasing delay,it may be preferable to use TDM or FDM.Another advantage of TDM and FDM is that there is no need to include identification of the traffic stream on each packet, thereby saving some overhead
Sec. 3.2 Queueing Models-Little's Theorem sequence one packet at a time. However, if the queue of a traffic stream is empty, the next traffic stream is served and no communication resource is wasted. Since the entire transmission capacity C (bits/sec) is allocated to a single packet at a time, it takes LIC sec to transmit a packet that is L bits long. In time-division (TDM) and frequency-division multiplexing (FDM) with m traffic streams, the link capacity is essentially subdivided into m portions-one per traffic stream. In FDM, the channel bandwidth W is subdivided into m channels each with bandwidth W/m (actually slightly less because of the need for guard bands between channels). The transmission capacity of each channel is roughly C/m, where C is the capacity that would be obtained if the entire bandwidth was allocated to a single channel. The transmission time of a packet that is L bits long is Lm/C, or m times longer than in the corresponding statistical multiplexing scheme. In TDM, allocation is done by dividing the time axis into slots of fixed length (e.g., one bit or one byte long, or perhaps one packet long for fixed length packets). Again, conceptually, we may view the communication link as consisting of m separate links with capacity C/rnm. In the case where the slots are short relative to packet length, we may again regard the transmission time of a packet L bits long as Lm/C. In the case where the slots are of packet length, the transmission time of an L bit packet is LIC, but there is a wait of (m - 1) packet transmission times between packets of the same stream. One of the themes that will emerge from our queueing analysis is that statistical multiplexing has smaller average delay per packet than either TDM or FDM. This is particularly true when the traffic streams multiplexed have a relatively low duty cycle. The main reason for the poor delay performance of TDM and FDM is that communication resources are wasted when allocated to a traffic stream with a momentarily empty queue, while other traffic streams have packets waiting in their queue. For a traffic analogy, consider an m-lane highway and two cases. In one case, cars are not allowed to cross over to other lanes (this corresponds to TDM or FDM), while in the other case, cars can change lanes (this corresponds roughly to statistical multiplexing). Restricting crossover increases travel time for the same reason that the delay characteristics of TDM or FDM are poor, namely some system resources (highway lanes or communication channels) may not be utilized while others are momentarily stressed. Under certain circumstances, TDM or FDM may have an advantage. Suppose that each traffic stream has a "regular" character, i.e., all packets arrive sufficiently apart so that no packet has to wait while the preceding packet is transmitted. If these traffic streams are merged into a single queue, it can be shown that the average delay per packet will decrease, but the variance of waiting time in queue will generally become positive (for an illustration see Prob. 3.7). Therefore, if maintaining small variability of delay is more important than decreasing delay, it may be preferable to use TDM or FDM. Another advantage of TDM and FDM is that there is no need to include identification of the traffic stream on each packet, thereby saving some overhead