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 numberSec. 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