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