Second Edition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL,Englewood Cliffs,New Jersey 07632
Second Ed ition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL, Englewood Cliffs, New Jersey 07632
4 Busy-- 口口题口口口口圈口@黑 Idle and busy--◆ ---Requests 口口口题圆 Multiaccess Communication 4.1 INTRODUCTION The subnetworks considered thus far have consisted of nodes joined by point-to-point communication links.Each such link might consist physically of a pair of twisted wires.a coaxial cable.an optical fiber.a microwave radio link.and so on.The implicit assumption about point-to-point links.however.is that the received signal on each link depends only on the transmitted signal and noise on that link. There are many widely used communication media,such as satellite systems.radio broadcast,multidrop telephone lines.and multitap bus systems.for which the received signal at one node depends on the transmitted signal at two or more other nodes.Typ- ically,such a received signal is the sum of attenuated transmitted signals from a set of other nodes,corrupted by distortion.delay,and noise.Such media,called multiac- cess media,form the basis for local area networks (LANs),metropolitan area networks (MANs).satellite networks.and radio networks. The layering discussed in Chapters I and 2 is not quite appropriate for multiaccess media.One needs an additional sublayer.often called the meditm access control(MAC) sublayer,beween the data link control(DLC)layer and the modem or physical layer.The 271
4 Busy ---- Multiaccess Communication 4.1 INTRODUCTION The subnetworks considered thus far have consisted of nodes joined by point-to-point communication links. Each such link might consist physically of a pair of twisted wires. a coaxial cable. an optical fiber. a microwave radio link. and so on. The implicit assumption about point-to-point links. however. is that the received signal on each link depends only on the transmitted signal and noise on that link. There are many widely used communication media. such as satellite systems. radio broadcast. multidrop telephone lines. and multitap bus systems. for which the received signal at one node depends on the transmitted signal at two or more other nodes. Typically. such a received signal is the sum of attenuated transmitted signals from a set of other nodes. corrupted by distortion. delay. and noise. Such media. called multiaccess media. form the basis for local area networks (LANs). metropolitan area networks (MANs), satellite networks. and radio networks. The layering discussed in Chapters I and 2 is not quite appropriate for multiaccess media. One needs an additional sublayer, often called the medium access control (MAC) sublayer. beween the data link control (DLC) layer and the modem or physical layer. The 271
272 Multiaccess Communication Chap.4 purpose of this extra sublayer is to allocate the multiaccess medium among the various nodes.As we study this allocation issue.we shall see that the separation of functions between layers is not as clean as it is with point-to-point links.For example.feedback about transmission errors is part of the ARQ function of the DLC layer.but is often also central to the problem of allocation and thus flow control.Similarly,much of the function of routing is automatically implemented by the broadcast nature of multiaccess channels. Conceptually.we can view multiaccess communication in queueing terms.Each node has a queue of packets to be transmitted and the multiaccess channel is a common server.Ideally,the server should view all the waiting packets as one combined queue to be served by the appropriate queueing discipline.Unfortunately,the server does not know which nodes contain packets:similarly.nodes are unaware of packets at other nodes.Thus.the interesting part of the problem is that knowledge about the state of the queue is distributed. There are two extremes among the many strategies that have been developed for this generic problem.One is the "free-for-all"approach in which nodes normally send new packets immediately.hoping for no interference from other nodes.The interesting question here is when and how packets are retransmitted when collisions (i.e..interfer- ence)occur.The other extreme is the "perfectly scheduled"approach in which there is some order (round robin,for example)in which nodes receive reserved intervals for channel use.The interesting questions here are:(1)what determines the scheduling order (it could be dynamic).(2)how long can a reserved interval last,and(3)how are nodes informed of their turns? Sections 4.2 and 4.3 explore the free-for-all approach in a simple idealized envi- ronment that allows us to focus on strategies for retransmitting collided packets.Succes- sively more sophisticated algorithms are developed that reduce delay.increase available throughput.and maintain stable operation.In later sections.these algorithms are adapted to take advantage of special channel characteristics so as to reduce delay and increase throughput even further.The more casual reader can omit Sections 4.2.3 and 4.3. Section 4.4 explores carrier sense multiple access (CSMA).Here the free-for-all approach is modified:a packet transmission is not allowed to start if the channel is sensed to be busy.We shall find that this set of strategies is a relatively straightforward extension of the ideas in Sections 4.2 and 4.3.The value of these strategies is critically dependent on the ratio of propagation delay to packet transmission time,a parameter called 3. If 31,CSMA can decrease delay and increase throughput significantly over the techniques of Sections 4.2 and 4.3.The casual reader can omit Sections 4.4.2 and 4.4.4. Section 4.5 deals with scheduling.or reserving.the channel in response to the dynamic requirements of the individual nodes.We start with satellite channels in Section 4.5.1:here the interesting feature is dealing with 1.Next.Sections 4.5.2 to 4.5.4 treat the major approaches to LANs and MANs.These approaches can be viewed as reservation systems and differ in whether the reservations are scheduled in a free-for-all manner or in a round-robin manner.LANs are usually designed for the assumption that is small.and Section 4.5.5 explores systems with higher speed or greater geographical coverage for which 3 is large
272 Multiaccess Communication Chap. 4 purpose of this extra sublayer is to allocate the multiaccess medium among the various nodes. As we study this allocation issue. we shall see that the separation of functions between layers is not as clean as it is with point-to-point links. For example. feedback about transmission errors is part of the ARQ function of the DLC layer. but is often also central to the problem of allocation and thus flow control. Similarly, much of the function of routing is automatically implemented by the broadcast nature of multiaccess channels. Conceptually. we can view multiaccess communication in queueing terms. Each node has a queue of packets to be transmitted and the multiaccess channel is a common server. Ideally, the server should view all the waiting packets as one combined queue to be served by the appropriate queueing discipline. Unfortunately, the server does not know which nodes contain packets; similarly. nodes are unaware of packets at other nodes. Thus. the interesting part of the problem is that knowledge about the state of the queue is distributed. There are two extremes among the many strategies that have been developed for this generic problem. One is the "free-for-all" approach in which nodes normally send new packets immediately, hoping for no interference from other nodes. The interesting question here is when and how packets are retransmitted when collisions (i.e .. interference) occur. The other extreme is the "perfectly scheduled" approach in which there is some order (round robin, for example) in which nodes receive reserved intervals for channel use. The interesting questions here are: (I) what determines the scheduling order (it could be dynamic). (2) how long can a reserved interval last, and (3) how are nodes informed of their turns'? Sections 4.2 and 4.3 explore the free-for-all approach in a simple idealized environment that allows us to focus on strategies for retransmitting collided packets. Successively more sophisticated algorithms are developed that reduce delay. increase available throughput. and maintain stable operation. In later sections. these algorithms are adapted to take advantage of special channel characteristics so as to reduce delay and increase throughput even further. The more casual reader can omit Sections 4.2.3 and 4.3. Section 4.4 explores carrier sense multiple access (CSMA). Here the free-for-all approach is modified; a packet transmission is not allowed to start if the channel is sensed to be busy. We shall find that this set of strategies is a relatively straightforward extension of the ideas in Sections 4.2 and 4.3. The value of these strategies is critically dependent on the ratio of propagation delay to packet transmission time. a parameter called), If 3 « I, CSMA can decrease delay and increase throughput significantly over the techniques of Sections 4.2 and 4.3. The casual reader can omit Sections 4.4.2 and 4.4.4. Section 4.5 deals with scheduling. or reserving. the channel in response to the dynamic requirements of the individual nodes. We start with satellite channels in Section 4.5.1; here the interesting feature is dealing with-J » I. Next. Sections 4.5.2 to 4.5.4 treat the major approaches to LANs and MANs. These approaches can be viewed as reservation systems and differ in whether the reservations are scheduled in a free-for-all manner or in a round-robin manner. LANs are usually designed for the assumption that -J is smaIL and Section 4.5.5 explores systems with higher speed or greater geographical coverage for which .3 is large
Sec.4.1 Introduction 273 Finally.Section 4.6 explores packet radio.Here the interesting issue is that each node interferes only with a limited subset of other nodes:thus.multiple nodes can transmit simultaneously without interference. Before going into any of the topics above in detail,we briefly discuss some of the most widely used multiaccess media. 4.1.1 Satellite Channels In a typical geosynchronous communication satellite system,many ground stations can transmit to a common satellite receiver,with the received messages being relayed to the ground stations (see Fig.4.1).Such satellites often have separate antenna beams for different geographical areas.allowing independent reception and relaying between areas. Also.FDM (or TDM)can be used,permitting different earth stations within the region covered by a single antenna beam to be independently received. It is thus possible to use a satellite channel as a collection of virtual point-to-point links.with two virtual links being separated either by antenna beam or multiplexing.The potential difficulty with this approach is the same as the difficulty with using FDM or Satellite Ground stations (a)Satellite multiaccess channel Primary Secondaries (b)Multidrop telephone line Figure 4.1 Common multiaccess (c)Multitap bus channels
Sec. 4.1 Introduction 273 Finally, Section 4.6 explores packet radio. Here the interesting issue is that each node interferes only with a limited subset of other nodes: thus, multiple nodes can transmit simultaneously without interference. Before going into any of the topics above in detail, we briefly discuss some of the most widely used multiaccess media. 4.1.1 Satellite Channels In a typical geosynchronous communication satellite system, many ground stations can transmit to a common satellite receiver, with the received messages being relayed to the ground stations (see Fig. 4.1). Such satellites often have separate antenna beams for different geographical areas, allowing independent reception and relaying between areas. Also, FDM (or TDM) can be used, permitting different earth stations within the region covered by a single antenna beam to be independently received. It is thus possible to use a satellite channel as a collection of virtual point-to-point links, with two virtual links being separated either by antenna beam or multiplexing. The potential difficulty with this approach is the same as the difficulty with using FDM or Satellite o o Ground stations o o Primary (a) Satellite multiaccess channel Secondaries (b) Multidrop telephone line (c) Multitap bus Figure 4.1 Common multiaccess channels
274 Multiaccess Communication Chap.4 TDM for multiple sessions on a single point-to-point link,namely increased delay and underutilization of the medium. In Section 4.5.I we shall find that delay can be reduced and utilization increased by sharing the medium on a demand basis.This is more difficult than demand sharing (i.e.,statistical multiplexing)on a point-to-point link because the earth stations are not aware of the instantaneous traffic requirements of other earth stations.If several stations transmit at the same time (and in the same frequency band),their signals are garbled and incorrectly received. 4.1.2 Multidrop Telephone Lines Another example of a multiaccess channel is a multidrop telephone line.Such lines connect one primary node with a number of secondary nodes:the signal transmitted by the primary node goes over one pair of wires and is received by all the secondary nodes. Similarly,there is a return pair of wires which carries the sum of the transmitted signals from all the secondary nodes to the primary node.Conceptually,this is like a satellite channel.The secondary nodes,or earth stations,share the path to the primary node,or satellite.whereas the primary node,or satellite.broadcasts to all the secondary nodes. or earth stations.Most communication on a multidrop phone line is intended to go from primary to secondary.or vice versa,whereas most communication on a satellite channel is relayed by the satellite from one earth station to another.Conceptually,this difference is not very important,since the major problem is that of sharing the channel from the secondary nodes to the primary,and it makes little difference whether the messages are removed at the primary node or broadcast back to all the secondary nodes. The traditional mode of operation for multidrop telephone lines is for the primary node to poll (i.e..request information from)each secondary node in some order.Each secondary node responds to its poll either by sending data back to the primary station or by indicating that it has no data to send.This strategy avoids interference between the secondary nodes,since nodes are polled one at a time,but there is a certain amount of inefficiency involved,both in the time to send a poll and the time to wait for a response from a node with no data. 4.1.3 Multitapped Bus A third example of a multiaccess channel is a bus with multiple taps.In this case,each node can receive the signal sent by each other node,but again,if multiple nodes transmit at the same time.the received signal is garbled.We shall discuss this example later in the context of Ethernet.but for now.we observe that conceptually this channel is very similar to a satellite channel.Each node can communicate with each other node,but if nodes transmit simultaneously.the received signal cannot be correctly detected.The fact that nodes can hear each other directly here,as opposed to hearing each other via relay from the satellite.has some important practical consequences.but we will ignore this for now
274 Multiaccess Communication Chap. 4 TDM for multiple sessions on a single point-to-point link, namely increased delay and underutilization of the medium. In Section 4.5.1 we shall find that delay can be reduced and utilization increased by sharing the medium on a demand basis. This is more difficult than demand sharing (i.e., statistical multiplexing) on a point-to-point link because the earth stations are not aware of the instantaneous traffic requirements of other earth stations. If several stations transmit at the same time (and in the same frequency band), their signals are garbled and incorrectly received. 4.1.2 Multidrop Telephone Lines Another example of a multiaccess channel is a multidrop telephone line. Such lines connect one primary node with a number of secondary nodes; the signal transmitted by the primary node goes over one pair of wires and is received by all the secondary nodes. Similarly, there is a return pair of wires which carries the sum of the transmitted signals from all the secondary nodes to the primary node. Conceptually, this is like a satellite channel. The secondary nodes, or earth stations, share the path to the primary node, or satellite, whereas the primary node, or satellite. broadcasts to all the secondary nodes, or earth stations. Most communication on a multidrop phone line is intended to go from primary to secondary, or vice versa, whereas most communication on a satellite channel is relayed by the satellite from one earth station to another. Conceptually, this difference is not very important, since the major problem is that of sharing the channel from the secondary nodes to the primary, and it makes little difference whether the messages are removed at the primary node or broadcast back to all the secondary nodes. The traditional mode of operation for multidrop telephone lines is for the primary node to poll (i.e .. request information from) each secondary node in some order. Each secondary node responds to its poll either by sending data back to the primary station or by indicating that it has no data to send. This strategy avoids interference between the secondary nodes, since nodes are polled one at a time, but there is a certain amount of inefficiency involved, both in the time to send a poll and the time to wait for a response from a node with no data. 4.1.3 Multitapped Bus A third example of a multiaccess channel is a bus with multiple taps. In this case. each node can receive the signal sent by each other node, but again, if multiple nodes transmit at the same time. the received signal is garbled. We shall discuss this example later in the context of Ethernet. but for now, we observe that conceptually this channel is very similar to a satellite channel. Each node can communicate with each other node, but if nodes transmit simultaneously. the received signal cannot be correctly detected. The fact that nodes can hear each other directly here, as opposed to hearing each other via relay from the satellite. has some important practical consequences. but we will ignore this for now
Sec.4.2 Slotted Multiaccess and the Aloha System 275 4.1.4 Packet Radio Networks A fourth example of multiaccess communication is that of a packet radio network.Here each node is in reception range of some subset of other nodes.Thus,if only one node in the subset is transmitting,the given node can receive the transmission,whereas if multiple nodes are transmitting simultaneously in the same band,the reception will be garbled.Similarly,what one node transmits will be heard by a subset of the other nodes. In general,because of different noise conditions at the nodes,the subset of nodes from which a given node can receive is different from the subset to which the given node can transmit.The fact that each receiver hears a subset of transmitters rather than all transmitters makes packet radio far more complex than the other examples discussed.In the next four sections,we study multiaccess channels in which a receiver can hear all transmitters,and then in Section 4.6.we discuss packet radio networks in more detail. 4.2 SLOTTED MULTIACCESS AND THE ALOHA SYSTEM Satellite channels,multidrop telephone lines,and multitap bus systems all share the feature of a set of nodes sharing a communication channel.If two or more nodes transmit simultaneously,the reception is garbled,and if none transmit,the channel is unused.The problem is somehow to coordinate the use of the channel so that exactly one node is transmitting for an appreciable fraction of the time.We start by looking at a highly idealized model.We shall see later that multiaccess channels can often be used in practice with much higher utilization than is possible in this idealized model,but we shall also see that these practical extensions can be understood more clearly in terms of our idealization. 4.2.1 Idealized Slotted Multiaccess Model The idealized model to be developed allows us to focus on the problem of dealing with the contention that occurs when multiple nodes attempt to use the channel simultaneously. Conceptually.we view the system as in Fig.4.1(a).with i transmitting nodes and one receiver. It will be observed that aside from some questions of propagation delay.this same model can be applied with m nodes that can all hear each other (i.e.,the situation with a multitap bus).We first list the assumptions of the model and then discuss their implications. 1.Slotted svstemt.Assume that all transmitted packets have the same length and that each packet requires one time unit (called a slot)for transmission.All transmitters are synchronized so that the reception of each packet starts at an integer time and ends before the next integer time. 2.Poisson arrivals.Assume that packets arrive for transmission at each of the m transmitting nodes according to independent Poisson processes.Let A be the overall arrival rate to the system,and let A/m be the arrival rate at each transmitting node
Sec. 42 Slotted Multiaccess and the Aloha System 275 4.1.4 Packet Radio Networks A fourth example of multiaccess communication is that of a packet radio network. Here each node is in reception range of some subset of other nodes. Thus. if only one node in the subset is transmitting, the given node can receive the transmission. whereas if multiple nodes are transmitting simultaneously in the same band, the reception will be garbled. Similarly. what one node transmits will be heard by a subset of the other nodes. In general, because of different noise conditions at the nodes, the subset of nodes from which a given node can receive is different from the subset to which the given node can transmit. The fact that each receiver hears a subset of transmitters rather than all transmitters makes packet radio far more complex than the other examples discussed. In the next four sections, we study multiaccess channels in which a receiver can hear all transmitters, and then in Section 4.6, we discuss packet radio networks in more detail. 4.2 SLOTTED MULTIACCESS AND THE ALOHA SYSTEM Satellite channels, multidrop telephone lines, and multitap bus systems all share the feature of a set of nodes sharing a communication channel. If two or more nodes transmit simultaneously, the reception is garbled, and if none transmit, the channel is unused. The problem is somehow to coordinate the use of the channel so that exactly one node is transmitting for an appreciable fraction of the time. We start by looking at a highly idealized model. We shall see later that multiaccess channels can often be used in practice with much higher utilization than is possible in this idealized model, but we shall also see that these practical extensions can be understood more clearly in terms of our idealization. 4.2.1 Idealized Slotted Multiaccess Model The idealized model to be developed allows us to focus on the problem of dealing with the contention that occurs when multiple nodes attempt to use the channel simultaneously. Conceptually. we view the system as in Fig. 4.1 (a), with III transmitting nodes and one receiver. It will be observed that aside from some questions of propagation delay. this same model can be applied with III nodes that can all hear each other (i.e., the situation with a multitap bus). We first list the assumptions of the model and then discuss their implications. 1. Slotted system. Assume that all transmitted packets have the same length and that each packet requires one time unit (called a slot) for transmission. All transmitters are synchronized so that the reception of each packet starts at an integer time and ends before the next integer time. 2. Poisson arrimls. Assume that packets arrive for transmission at each of the Tn transmitting nodes according to independent Poisson processes. Let A be the overall arrival rate to the system. and let AIm be the arrival rate at each transmitting node
276 Multiaccess Communication Chap.4 3.Collision or perfect receprion.Assume that if two or more nodes send a packet in a given time slot.then there is a collision and the receiver obtains no information about the contents or source of the transmitted packets.If just one node sends a packet in a given slot.the packet is correctly received. 4.0.1.e Immiediate feedhack.Assume that at the end of each slot.each node obtains feedback from the receiver specifying whether 0 packets.I packet.or more than one packet for error)were transmitted in that slot. 5.Retransmission of collisions.Assume that each packet involved in a collision must be retransmitted in some later slot.with further such retransmissions until the packet is successfully received.A node with a packet that must be retransmitted is said to be hacklogged. 6a.No buffering.If one packet at a node is currently waiting for transmission or colliding with another packet during transmission.new arrivals at that node are discarded and never transmitted.An alternative to this assumption is the following. 6b.Infinite set of nodes (m=x).The system has an infinite set of nodes and each newly arriving packet arrives at a new node. Discussion of assumptions.The slotted system assumption (1)has two ef- fects.The first is to turn the system into a discrete-time system.thus simplifying analysis. The second is to preclude,for the moment,the possibility of carrier sensing or early col- lision detection.Carrier sensing is treated in Section 4.4 and early collision detection is treated in Section 4.5.Both allow much more efficient use of the multiaccess channel, but can be understood more clearly as an extension of the present model.Synchronizing the transmitters for slotted arrival at the receiver is not entirely trivial.but may be ac- complished with relatively stable clocks.a small amount of feedback from the receiver, and some guard time between the end of a packet transmission and the beginning of the next slot. The assumption of Poisson arrivals (2)is unrealistic for the case of multipacket messages.We discuss this issue in Section 4.5 in terms of nodes making reservations for use of the channel. The assumption of collision or perfect reception(3)ignores the possibility of errors due to noise and also ignores the possibility of"capture"techniques.by which a receiver can sometimes capture one transmission in the presence of multiple transmissions. The assumption of immediate feedback (4)is quite unrealistic.particularly in the case of satellite channels.It is made to simplify the analysis.and we shall see later that delayed feedback complicates multiaccess algorithms but causes no fundamental problems.We also discuss the effects of more limited types of feedback later. The assumption that colliding packets must be retransmitted (5)is certainly reason- able in providing reliable communication.In light of this assumption.the no-buffering assumption (6a)appears rather peculiar.since new arrivals to backlogged nodes are thrown away with impunity.but packets once transmitted must be retransmitted until successful.In practice,one generally provides some buffering along with some form of flow control to ensure that not too many packets back up at a node.Our interest in this section.however.is in multiaccess channels with a large number of nodes.a relatively
276 Multiaccess Communication Chap. 4 3. Collision or perfect reception. Assume that if two or more nodes send a packet in a given time slot, then there is a collision and the receiver obtains no information about the contents or source of the transmitted packets. If just one node sends a packet in a given slot. the packet is correctly received. 4. O./.e Immediate feedhack. Assume that at the end of each slot, each node obtains feedback from the receiver specifying whether 0 packets. I packet. or more than one packet (c for error) were transmitted in that slot. S. Retransmission of collisions. Assume that each packet involved in a collision must be retransmitted in some later slot. with further such retransmissions until the packet is successfully received. A node with a packet that must be retransmitted is said to be hacklogged. 6a. No huffering. If one packet at a node is currently waiting for transmission or colliding with another packet during transmission. new arrivals at that node are discarded and never transmitted. An alternative to this assumption is the following. 6b. Infinite set of nodes (m = x). The system has an infinite set of nodes and each newly arriving packet arrives at a new node. Discussion of assumptions. The slotted system assumption (I) has two effects. The first is to turn the system into a discrete-time system, thus simplifying analysis. The second is to preclude, for the moment, the possibility of carrier sensing or early collision detection. Carrier sensing is treated in Section 4.4 and early collision detection is treated in Section 4.5. Both allow much more efficient use of the multiaccess channel, but can be understood more clearly as an extension of the present model. Synchronizing the transmitters for slotted arrival at the receiver is not entirely trivial, but may be accomplished with relatively stable clocks. a small amount of feedback from the receiver, and some guard time between the end of a packet transmission and the beginning of the next slot. The assumption of Poisson arrivals (2) is unrealistic for the case of multi packet messages. We discuss this issue in Section 4.5 in tenns of nodes making reservations for use of the channel. The assumption of collision or perfect reception (3) ignores the possibility of errors due to noise and also ignores the possibility of "capture" techniques. by which a receiver can sometimes capture one transmission in the presence of multiple transmissions. The assumption of immediate feedback (4) is quite unrealistic. particularly in the case of satellite channels. It is made to simplify the analysis. and we shall see later that delayed feedback complicates multiaccess algorithms but causes no fundamental problems. We also discuss the effects of more limited types of feedback later. The assumption that colliding packets must be retransmitted (5) is certainly reasonable in providing reliable communication. In light of this assumption. the no-buffering assumption (6a) appears rather peculiar, since new arrivals to backlogged nodes are thrown away with impunity. but packets once transmitted must be retransmitted until successful. In practice, one generally provides some buffering along with some form of flow control to ensure that not too many packets back up at a node. Our interest in this section, however. is in multiaccess channels with a large number of nodes. a relatively
Sec.4.2 Slotted Multiaccess and the Aloha System 277 small arrival rate A.and small required delay (i.e..the conditions under which TDM does not suffice).Under these conditions,the fraction of backlogged nodes is typically small.and new arrivals at backlogged nodes are almost negligible.Thus.the delay for a system without buffering should be relatively close to that with buffering.Also,the delay for the unbuffered system provides a lower bound to the delay for a wide variety of systems with buffering and flow control. The infinite-node assumption (6b)alternatively provides us with an upper bound to the delay that can be achieved with a finite number of nodes.In particular.given any multiaccess algorithm (i.c..any rule that each node employs for selecting packet transmission times).each of a finite set of nodes can regard itself as a set of virtual nodes. one for each arriving packet.With the application of the given algorithm independently for each such packet,the situation is equivalent to that with an infinite set of nodes (i.e..assumption 6b).In this approach.a node with several backlogged packets will sometimes send multiple packets in one slot.causing a sure collision.Thus.it appears that by avoiding such sure collisions and knowing the number of buffered packets at a node.a system with a finite number of nodes and buffering could achieve smaller delays than with n=x:in any case,however.the m x delay can always be achieved. If the performance using assumption 6a is similar to that using 6b.then we are assured that we have a good approximation to the performance of a system with arbitrary assumptions about buffering.From a theoretical standpoint.assumption 6b captures the essence of multiaccess communication much better than 6a.We use 6a initially.however. because it is less abstract and it provides some important insights about the relationship between TDM and other algorithms. 4.2.2 Slotted Aloha The Aloha network [Abr70]was developed around 1970 to provide radio communication between the central computer and various data terminals at the campuses of the University of Hawaii.This multiaccess approach will be described in Section 4.2.4,but first we discuss an improvement called slotted Aloha [Rob72.The basic idea of this algorithm is that each unbacklogged node simply transmits a newly arriving packet in the first slot after the packet arrival.thus risking occasional collisions but achieving very small delay if collisions are rare.This approach should be contrasted with TDM.in which,with m nodes.an arriving packet would have to wait for an average of in/2 slots for its turn to transmit.Thus.slotted Aloha transmits packets almost immediately with occasional collisions.whereas TDM avoids collisions at the expense of large delays. When a collision occurs in slotted Aloha.each node sending one of the colliding packets discovers the collision at the end of the slot and becomes backlogged.If each backlogged node were simply to retransmit in the next slot after being involved in a collision.then another collision would surely occur.Instead.such nodes wait for some random number of slots before retransmitting. To gain some initial intuitive understanding of slotted Aloha,we start with an instructive but flawed analysis.With the infinite-node assumption (i.e..6b).the number
Sec. 4.2 Slotted Multiaccess and the Aloha System 277 small arrival rate A. and small required delay (i.e .• the conditions under which TOM does not suffice). Under these conditions, the fraction of backlogged nodes is typically small. and new arrivals at backlogged nodes are almost negligible. Thus. the delay for a system without buffering should be relatively close to that with buffering. Also. the delay for the unbuffered system provides a lower bound to the delay for a wide variety of systems with buffering and flow control. The infinite-node assumption (6b) alternatively provides us with an upper bound to the delay that can be achieved with a finite number of nodes. In particular. given any multiaccess algorithm (i.c .. any rule that each node employs for selecting packet transmission times). each of a finite set of nodes can regard itself as a set of virtual nodes. one for each arriving packet. With the application of the given algorithm independently for each such packet. the situation is equivalent to that with an infinite set of nodes (i.c .. assumption 6b). In this approach. a node with several backlogged packets will sometimes send multiple packets in one slot. causing a sure collision. Thus. it appears that by avoiding such sure collisions and knowing the number of buffered packets at a node. a system with a finite number of nodes and buffering could achieve smaller delays than with III = x; in any case. however. the III = x delay can always be achieved. If the performance using assumption 6a is similar to that using 6b. then we are assured that we have a good approximation to thc performance of a system with arbitrary assumptions about buffering. From a theoretical standpoint. assumption 6b captures the essence of multiaccess communication much better than 6a. We use 6a initially. however. because it is less abstract and it provides some important insights about the relationship between TOM and other algorithms. 4.2.2 Slotted Aloha The Aloha network [Abr70] was developed around 1970 to provide radio communication between the central computer and various data terminals at the campuses of the University of Hawaii. This multiaccess approach will be described in Section 4.2.4. but first we discuss an improvement called slotted Aloha [Robn]. The basic idea of this algorithm is that each un backlogged node simply transmits a newly arriving packet in the first slot after the packet arrival. thus risking occasional collisions but achieving very small delay if collisions are rare. This approach should be contrasted with TOM. in which. with In nodes. an arriving packet would have to wait for an average of III /2 slots for its turn to transmit. Thus. slotted Aloha transmits packets almost immediately with occasional collisions, whereas TOM avoids collisions at the expense of large delays. When a collision occurs in slottcd Aloha. each node sending one of the colliding packets discovers the collision at the end of the slot and becomes backlogged. If each backlogged node were simply to retransmit in the next slot after being involved in a collision. then another collision would surely occur. Instead. such nodes wait for some random number of slots before retransmitting. To gain some initial intuitive understanding of slotted Aloha. we start with an instructive but flawed analysis. With the infinite-node assumption (i.c .. 6b). the number
278 Multiaccess Communication Chap.4 of new arrivals transmitted in a slot is a Poisson random variable with parameter A.If the retransmissions from backlogged nodes are sufficiently randomized.it is plausible to approximate the total number of retransmissions and new transmissions in a given slot as a Poisson random variable with some parameter G>A.With this approximation. the probability of a successful transmission in a slot is Ge-C.Finally,in equilibrium. the arrival rate.A.to the system should be the same as the departure rate.Ge-C.This relationship is illustrated in Fig.4.2. We see that the maximum possible departure rate (according to the argument above) occurs at G =I and is 1/e 0.368.We also note,somewhat suspiciously.that for any arrival rate less than l/e,there are two values of G for which the arrival rate equals the departure rate.The problem with this elementary approach is that it provides no insight into the dynamics of the system.As the number of backlogged packets changes. the parameter G will change:this leads to a feedback effect,generating further changes in the number of backlogged packets.To understand these dynamics.we will have to analyze the system somewhat more carefully.The simple picture below,however, correctly identifies the maximum throughput rate of slotted Aloha as 1/e and also shows that G.the mean number of attempted transmissions per slot,should be on the order of 1 to achieve a throughput close to 1/e.If G1.too many collisions are generated. To construct a more precise model.assume that each backlogged node retransmits with some fixed probability gr in each successive slot until a successful transmission occurs.In other words.the number of slots from a collision until a given node involved in the collision retransmits is a geometric random variable having value iI with probability (I-g).The original version of slotted Aloha employed a uniform distribution for retransmission,but this is more difficult to analyze and has no identifiable Departure rate Ge-G Arrival rate Equilibrium G=0 G=1 Figure 4.2 Departure rate as a function of attempted transmission rate G for slotted Aloha.Ignoring the dynamic behavior of G.departures (successful transmissions)occur at a rate G-,and arrivals occur at a rate A.leading to a hypothesized equilibrium point as shown
278 Multiaccess Communication Chap. 4 of new arrivals transmitted in a slot is a Poisson random variable with parameter A. If the retransmissions from backlogged nodes are sufficiently randomized, it is plausible to approximate the total number of retransmissions and new transmissions in a given slot as a Poisson random variable with some parameter G > A. With this approximation. the probability of a successful transmission in a slot is Gc- G . Finally. in equilibrium, the arrival rate. A. to the system should be the same as the departure rate. Gc- G . This relationship is illustrated in Fig. 4.2. We see that the maximum possible departure rate (according to the argument above) occurs at G = I and is 1/e 0.368. We also note, somewhat suspiciously, that for any arrival rate less than lie. there are two values of G for which the arrival rate equals the departure rate. The problem with this elementary approach is that it provides no insight into the dynamics of the system. As the number of backlogged packets changes. the parameter G will change; this leads to a feedback effect, generating further changes in the number of backlogged packets. To understand these dynamics. we will have to analyze the system somewhat more carefully. The simple picture below, however. correctly identifies the maximum throughput rate of slotted Aloha as IIe and also shows that G. the mean number of attempted transmissions per slot. should be on the order of I to achieve a throughput close to IIe. If G I, too many collisions are generated. To construct a more precise model, assume that each backlogged node retransmits with some fixed probability (jr in each successive slot until a successful transmission occurs. In other words, the number of slots from a collision until a given node involved in the collision retransmits is a geometric random variable having value i 2> I with probability (jr(1 - (jr )i-I. The original version of slotted Aloha employed a uniform distribution for retransmission, but this is more difficult to analyze and has no identifiable : Arrival rate I I I I I I I G = 1 Figure 4.2 Departure rate as a function of attempted transmission rate G for slotted Aloha. Ignoring the dynamic behavior of G. departures (successful transmissions) occur at a rate Gr- c;. and arrivals occur at a rate A. leading to a hypothesized equilibrium point as shown
Sec.4.2 Slotted Multiaccess and the Aloha System 279 advantages over the geometric distribution.We will use the no-buffering assumption(6a) and switch later to the infinite node assumption (6b). The behavior of slotted Aloha can now be described as a discrete-time Markov chain.Let n be the number of backlogged nodes at the beginning of a given slot.Each of these nodes will transmit a packet in the given slot.independently of each other.with probability g,.Each of the m-n other nodes will transmit a packet in the given slot if one (or more)such packets arrived during the previous slot.Since such arrivals are Poisson distributed with meanA/m.the probability of no arrivals is:thus,the probability that an unbacklogged node transmits a packet in the given slot is =1-e-/.Let Q(i.n)be the probability that i unbacklogged nodes transmit packets in a given slot, and let Q,(i.n)be the probability that i backlogged nodes transmit. Qo(i.n)= (m -n -qa"-n-' (4.1) Q(i.)= ()1-g-g (4.2) Note that from one slot to the next.the state (i.e..the number of backlogged packets)increases by the number of new arrivals transmitted by unbacklogged nodes. less one if a packet is transmitted successfully.A packet is transmitted successfully, however.only if one new arrival and no backlogged packet.or no new arrival and one backlogged packet is transmitted.Thus,the state transition probability of going from state n to n+i is given by Qu(i.n). 2≤i≤(m-n) Q(1.n11-Q(0.)1. i=1 P.n+= (4.3) Q(1.m)Q(0.n)-Q(0.n1-2(1.nl.i=0 Q(0.n)Q(1.n). i=-1 Figure 4.3 illustrates this Markov chain.Note that the state can decrease by at most I in a single transition.and this makes it easy to calculate the steady-state probabilities P 02 P22 P33 Figure 4.3 Markov chain for slotted Aloha.The state (i.e..backlog)can decreasc by at most onc per transition.but can increase by an arbitrary amount
Sec. 4.2 Slotted Multiaccess and the Aloha System 279 advantages over the geometric distribution. We will use the no-buffering assumption (6a) and switch later to the infinite node assumption (6b). The behavior of slotted Aloha can now be described as a discrete-time Markov chain. Let n be the number of backlogged nodes at the beginning of a given slot. Each of these nodes will transmit a packet in the given slot, independently of each other. with probability I}I' Each of the TIl - n other nodes will transmit a packet in the given slot if one (or more) such packets arrived during the previous slot. Since such arrivals are Poisson distributed with mean A/m, the probability of no arrivals is C A/ III ; thus, the probability that an unbacklogged node transmits a packet in the given slot is Iju = I - e- A/ Ill • Let Qu(i.II) be the probability that i unbacklogged nodes transmit packets in a given slot, and let Qr(i. n) be the probability that i backlogged nodes transmit, (4.1 ) Qr(i· II) = C) (I - IJ,)II-I q;. (4.2) Note that from one slot to the next, the state (i.e., the number of backlogged packets) increases by the number of new arrivals transmitted by unbacklogged nodes. less one if a packet is transmitted successfully. A packet is transmitted successfully, however. only if one new arrival and no backlogged packet. or no new arrival and one backlogged packet is transmitted. Thus, the state transition probability of going from state n to II + i is given by 2:S; i :s; (m - n) Qu(1.II)II-QI(O.n)J. i = 1 QII( I. n)QI(O' n) Qu(O.II)11 - QI( I. n)J. i = 0 QII(O.II)Q,.(l.n). i = ~l (4.3) Figure 4.3 illustrates this Markov chain. Note that the state can decrease by at most in a single transition. and this makes it easy to calculate the steady-state probabilities Figure 4.3 Markov chain for slotted Aloha. The state (i.c.. backlog) can decrease by at most one per transition. but can increase by an arbitrary amount