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 .. 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: (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 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), 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