12 0 0 Time at A一-+ Node A Ack Node 8 Time at B- Packet 0 or 17 Packet O Point-to-Point Protocols and Links 2.1 INTRODUCTION This chapter first provides an introduction to the physical communication links that constitute the building blocks of data networks.The major focus of the chapter is then data link control (i.e.,the point-to-point protocols needed to control the passage of data over a communication link).Finally,a number of point-to-point protocols at the network,transport,and physical layers are discussed.There are many similarities between the point-to-point protocols at these different layers,and it is desirable to discuss them together before addressing the more complex network-wide protocols for routing. flow control,and multiaccess control. The treatment of physical links in Section 2.2 is a brief introduction to a very large topic.The reason for the brevity is not that the subject lacks importance or inherent interest,but rather,that a thorough understanding requires a background in linear system theory,random processes,and modern communication theory.In this section we pro- vide a sufficient overview for those lacking this background and provide a review and perspective for those with more background. 37
2 Node A Node B Packet 0 Point-to-Point Protocols and Links 2.1 INTRODUCTION Time at B --------- This chapter first provides an introduction to the physical communication links that constitute the building blocks of data networks. The major focus of the chapter is then data link control (i.e., the point-to-point protocols needed to control the passage of data over a communication link). Finally, a number of point-to-point protocols at the network, transport, and physical layers are discussed. There are many similarities between the point-to-point protocols at these different layers, and it is desirable to discuss them together before addressing the more complex network-wide protocols for routing, flow control, and multiaccess control. The treatment of physical links in Section 2.2 is a brief introduction to a very large topic. The reason for the brevity is not that the subject lacks importance or inherent interest, but rather, that a thorough understanding requires a background in linear system theory, random processes, and modem communication theory. In this section we provide a sufficient overview for those lacking this background and provide a review and perspective for those with more background. 37
38 Point-to-Point Protocols and Links Chap.2 In dealing with the physical layer in Section 2.2,we discuss both the actual com- munication channels used by the network and whatever interface modules are required at the ends of the channels to transmit and receive digital data (see Fig 2.1).We refer to these modules as modems (digital data modulators and demodulators),although in many cases no modulation or demodulation is required.In sending data,the modem converts the incoming binary data into a signal suitable for the channel.In receiving,the modem converts the received signal back into binary data.To an extent,the combination of mo- dem,physical link,modem can be ignored;one simply recognizes that the combination appears to higher layers as a virtual bit pipe. There are several different types of virtual bit pipes that might be implemented by the physical layer.One is the synchronous bit pipe,where the sending side of the data link control (DLC)module supplies bits to the sending side of the modem at a synchronous rate (i.e.,one bit each T seconds for some fixed T).If the DLC module temporarily has no data to send,it must continue to send dummy bits,called idle fill, until it again has data.The receiving modem recovers these bits synchronously (with delay and occasional errors)and releases the bits,including idle fill,to the corresponding DLC module. The intermittent synchronous bit pipe is another form of bit pipe in which the sending DLC module supplies bits synchronously to the modem when it has data to send,but supplies nothing when it has no data.The sending modem sends no signal during these idle intervals,and the receiving modem detects the idle intervals and releases nothing to the receiving DLC module.This somewhat complicates the receiving modem, since it must distinguish between 0,1,and idle in each time interval,and it must also regain synchronization at the end of an idle period.In Chapter 4 it will be seen that the capability to transmit nothing is very important for multiaccess channels. A final form of virtual bit pipe is the asynchronous character pipe,where the bits within a character are sent at a fixed rate,but successive characters can be separated by Network Network layer layer Packets Data link Data link control control Frames Virtual synchronous unreliable bit pipe Physical Physical interface interface Communication link Figure 2.1 Data link control (DLC)layer with interfaces to adjacent layers
38 Point-to-Point Protocols and Links Chap. 2 In dealing with the physical layer in Section 2.2, we discuss both the actual communication channels used by the network and whatever interface modules are required at the ends of the channels to transmit and receive digital data (see Fig 2.1). We refer to these modules as modems (digital data modulators and demodulators), although in many cases no modulation or demodulation is required. In sending data, the modem converts the incoming binary data into a signal suitable for the channel. In receiving, the modem converts the received signal back into binary data. To an extent, the combination of modem, physical link, modem can be ignored; one simply recognizes that the combination appears to higher layers as a virtual bit pipe. There are several different types of virtual bit pipes that might be implemented by the physical layer. One is the synchronous bit pipe, where the sending side of the data link control (DLC) module supplies bits to the sending side of the modem at a synchronous rate (i.e., one bit each T seconds for some fixed T). If the DLC module temporarily has no data to send, it must continue to send dummy bits, called idle fill, until it again has data. The receiving modem recovers these bits synchronously (with delay and occasional errors) and releases the bits, including idle fill, to the corresponding DLC module. The intermittent synchronous bit pipe is another form of bit pipe in which the sending DLC module supplies bits synchronously to the modem when it has data to send, but supplies nothing when it has no data. The sending modem sends no signal during these idle intervals, and the receiving modem detects the idle intervals and releases nothing to the receiving DLC module. This somewhat complicates the receiving modem, since it must distinguish between 0, 1, and idle in each time interval, and it must also regain synchronization at the end of an idle period. In Chapter 4 it will be seen that the capability to transmit nothing is very important for multiaccess channels. A final form of virtual bit pipe is the asynchronous character pipe, where the bits within a character are sent at a fixed rate, but successive characters can be separated by Packets Frames Virtual synchronous unreliable bit pipe Communication link Figure 2.1 Data link control (DLC) layer with interfaces to adjacent layers
Sec.2.1 Introduction 39 variable delays,subject to a given minimum.As will be seen in the next section,this is used only when high data rates are not an important consideration. In Sections 2.3 to 2.7 we treat the DLC layer,which is the primary focus of this chapter.For each point-to-point link,there are two DLC peer modules,one module at each end of the link.For traffic in a given direction,the sending DLC module receives packets from the network layer module at that node.The peer DLC modules employ a distributed algorithm,or protocol,to transfer these packets to the receiving DLC and thence to the network layer module at that node.In most cases,the objective is to deliver the packets in the order of arrival,with neither repetitions nor errors.In accomplishing this task,the DLC modules make use of the virtual bit pipe (with errors)provided by the physical layer. One major problem in accomplishing the objective above is that of correcting the bit errors that occur on the virtual bit pipe.This objective is generally accomplished by a technique called ARQ (automatic repeat request).In this technique,errors are first detected at the receiving DLC module and then repetitions are requested from the transmitting DLC module.Both the detection of errors and the requests for retransmission require a certain amount of control overhead to be communicated on the bit pipe.This overhead is provided by adding a given number of bits (called a header)to the front of each packet and adding an additional number of bits (called a trailer)to the rear (see Fig.2.2).A packet,extended by this header and trailer,is called a frame.From the standpoint of the DLC,a packet is simply a string of bits provided as a unit by the network layer;examples arise later where single "packets,"in this sense,from the network layer contain pieces of information from many different sessions,but this makes no difference to the DLC layer. Section 2.3 treats the problem of error detection and shows how a set of redun- dant bits in the trailer can be used for error detection.Section 2.4 then deals with retransmission requests.This is not as easy as it appears,first because the requests must be embedded into the data traveling in the opposite direction,and second because the opposite direction is also subject to errors.This provides our first exposure to a real distributed algorithm,which is of particular conceptual interest since it must operate in the presence of errors. In Section 2.5 we discuss framing.The issue here is for the receiving DLC module to detect the beginning and end of each successive frame.For a synchronous bit pipe, the bits within a frame must contain the information to distinguish the end of the frame; also the idle fill between frames must be uniquely recognizable.This problem becomes even more interesting in the presence of errors. A widely accepted standard of data link control is the HDLC protocol.This is discussed in Section 2.6,followed in Section 2.7 by a general discussion of how to initialize and to disconnect DLC protocols.This topic might appear to be trivial,but on closer inspection,it requires careful thought. Frame Figure 2.2 Frame structure.A packet from the network layer is extended in the Header Packet Trailer DLC layer with control bits in front and in back of the packet
Sec. 2.1 Introduction 39 variable delays, subject to a given minimum. As will be seen in the next section, this is used only when high data rates are not an important consideration. In Sections 2.3 to 2.7 we treat the DLC layer, which is the primary focus of this chapter. For each point-to-point link, there are two DLC peer modules, one module at each end of the link. For traffic in a given direction, the sending DLC module receives packets from the network layer module at that node. The peer DLC modules employ a distributed algorithm, or protocol, to transfer these packets to the receiving DLC and thence to the network layer module at that node. In most cases, the objective is to deliver the packets in the order of arrival, with neither repetitions nor errors. In accomplishing this task, the DLC modules make use of the virtual bit pipe (with errors) provided by the physical layer. One major problem in accomplishing the objective above is that of correcting the bit errors that occur on the virtual bit pipe. This objective is generally accomplished by a technique called ARQ (automatic repeat request). In this technique, errors are first detected at the receiving DLC module and then repetitions are requested from the transmitting DLC module. Both the detection of errors and the requests for retransmission require a certain amount of control overhead to be communicated on the bit pipe. This overhead is provided by adding a given number of bits (called a header) to the front of each packet and adding an additional number of bits (called a trailer) to the rear (see Fig. 2.2). A packet, extended by this header and trailer, is called a frame. From the standpoint of the DLC, a packet is simply a string of bits provided as a unit by the network layer; examples arise later where single "packets," in this sense, from the network layer contain pieces of information from many different sessions, but this makes no difference to the DLC layer. Section 2.3 treats the problem of error detection and shows how a set of redundant bits in the trailer can be used for error detection. Section 2.4 then deals with retransmission requests. This is not as easy as it appears, first because the requests must be embedded into the data traveling in the opposite direction, and second because the opposite direction is also subject to errors. This provides our first exposure to a real distributed algorithm, which is of particular conceptual interest since it must operate in the presence of errors. In Section 2.5 we discuss framing. The issue here is for the receiving DLC module to detect the beginning and end of each successive frame. For a synchronous bit pipe, the bits within a frame must contain the information to distinguish the end of the frame; also the idle fill between frames must be uniquely recognizable. This problem becomes even more interesting in the presence of errors. A widely accepted standard of data link control is the HDLC protocol. This is discussed in Section 2.6, followed in Section 2.7 by a general discussion of how to initialize and to disconnect DLC protocols. This topic might appear to be trivial, but on closer inspection, it requires careful thought. 1•.------ Frame ---------<·~I I Header Packet Trailer I Figure 2.2 Frame structure. A packet from the network layer is extended in the DLC layer with control bits in front and in back of the packet
40 Point-to-Point Protocols and Links Chap.2 Section 2.8 then treats a number of network layer issues,starting with addressing. End-to-end error recovery,which can be done at either the network or transport layer,is discussed next,along with a general discussion of why error recovery should or should not be done at more than one layer.The section ends with a discussion first of the X.25 network layer standard and next of the Internet Protocol (IP).IP was originally developed to connect the many local area networks in academic and research institutions to the ARPANET and is now a defacto standard for the internet sublayer. A discussion of the transport layer is then presented in Section 2.9.This focuses on the transport protocol,TCP.used on top of IP.The combined use of TCP and IP (usually called TCP/IP)gives us an opportunity to explore some of the practical consequences of particular choices of protocols. The chapter ends with an introduction to broadband integrated service data net- works.In these networks,the physical layer is being implemented as a packet switching network called ATM,an abbreviation for "asynchronous transfer mode."It is interest- ing to compare how ATM performs its various functions with the traditional layers of conventional data networks. 2.2 THE PHYSICAL LAYER:CHANNELS AND MODEMS As discussed in Section 2.1,the virtual channel seen by the data link control (DLC)layer has the function of transporting bits or characters from the DLC module at one end of the link to the module at the other end (see Fig.2.1).In this section we survey how communication channels can be used to accomplish this function.We focus on point-to- point channels(i.e.,channels that connect just two nodes),and postpone consideration of multiaccess channels (i.e.,channels connecting more than two nodes)to Chapter 4.We also focus on communication in one direction,thus ignoring any potential interference between simultaneous transmission in both directions. There are two broad classes of point-to-point channels:digital channels and analog channels.From a black box point of view,a digital channel is simply a bit pipe,with a bit stream as input and output.An analog channel,on the other hand,accepts a waveform (i.e.,an arbitrary function of time)as input and produces a waveform as output.We discuss analog channels first since digital channels are usually implemented on top of an underlying analog structure. A module is required at the input of an analog channel to map the digital data from the DLC module into the waveform sent over the channel.Similarly,a module is required at the receiver to map the received waveform back into digital data.These modules will be referred to as modems (digital data modulator and demodulator).The term modem is used broadly here,not necessarily implying any modulation but simply referring to the required mapping operations. Let s(t)denote the analog channel input as a function of time:s(t)could represent a voltage or current waveform.Similarly,let r(t)represent the voltage or current waveform at the output of the analog channel.The output r(t)is a distorted,delayed,and attenuated version of s(t),and our objective is to gain some intuitive appreciation of how to map
40 Point-to-Point Protocols and Links Chap. 2 Section 2.8 then treats a number of network layer issues, starting with addressing. End-to-end error recovery, which can be done at either the network or transport layer, is discussed next, along with a general discussion of why error recovery should or should not be done at more than one layer. The section ends with a discussion first of the X.25 network layer standard and next of the Internet Protocol (IP). IP was original1y developed to connect the many local area networks in academic and research institutions to the ARPANET and is now a defacto standard for the internet sublayer. A discussion of the transport layer is then presented in Section 2.9. This focuses on the transport protocol, TCP, used on top of IP. The combined use of TCP and IP (usual1y cal1ed TCP/IP) gives us an opportunity to explore some of the practical consequences of particular choices of protocols. The chapter ends with an introduction to broadband integrated service data networks. In these networks, the physical layer is being implemented as a packet switching network called ATM, an abbreviation for "asynchronous transfer mode." It is interesting to compare how ATM performs its various functions with the traditional layers of conventional data networks. 2.2 THE PHYSICAL LAYER: CHANNELS AND MODEMS As discussed in Section 2.1, the virtual channel seen by the data link control (DLC) layer has the function of transporting bits or characters from the DLC module at one end of the link to the module at the other end (see Fig. 2.1). In this section we survey how communication channels can be used to accomplish this function. We focus on point-topoint channels (i.e., channels that connect just two nodes), and postpone consideration of multiaccess channels (i.e., channels connecting more than two nodes) to Chapter 4. We also focus on communication in one direction, thus ignoring any potential interference between simultaneous transmission in both directions. There are two broad classes of point-to-point channels: digital channels and analog channels. From a black box point of view, a digital channel is simply a bit pipe, with a bit stream as input and output. An analog channel, on the other hand, accepts a waveform (i.e., an arbitrary function of time) as input and produces a waveform as output. We discuss analog channels first since digital channels are usually implemented on top of an underlying analog structure. A module is required at the input of an analog channel to map the digital data from the DLC module into the waveform sent over the channel. Similarly, a module is required at the receiver to map the received waveform back into digital data. These modules wil1 be referred to as modems (digital data modulator and demodulator). The term modem is used broadly here, not necessarily implying any modulation but simply referring to the required mapping operations. Let set) denote the analog channel input as a function of time; set) could represent a .voltage or current waveform. Similarly, let ret) represent the voltage or current waveform at the output of the analog channel. The output ret) is a distorted, delayed, and attenuated version of set), and our objective is to gain some intuitive appreciation of how to map
Sec.2.2 The Physical Layer:Channels and Modems 41 the digital data into s()so as to minimize the deleterious effects of this distortion.Note that a black box viewpoint of the physical channel is taken here,considering the input- output relation rather than the internal details of the analog channel.For example,if an ordinary voice telephone circuit (usually called a voice-grade circuit)is used as the analog channel,the physical path of the channel will typically pass through multiple switches.multiplexers,demultiplexers,modulators,and demodulators.For dial-up lines, this path will change on each subsequent call,although the specification of tolerances on the input-output characterization remain unchanged. 2.2.1 Filtering One of the most important distorting effects on most analog channels is linear time- invariant filtering.Filtering occurs not only from filters inserted by the channel designer but also from the inherent behavior of the propagation medium.One effect of filtering is to "smooth out"the transmitted signal s(t).Figure 2.3 shows two examples in which s(f)is first a single rectangular puise and then a sequence of rectangular pulses.The defining properties of linear time-invariant filters are as follows: 1.If input s(t)yields output r(t).then for any r,input s(t-7)yields output r(t-T). 2.If s(t)yields r(t).then for any real number a,as(t)yields ar(t). 3.If s(t)yields ri(t)and s2(t)yields r2(t),then s(t)+s2(t)yields ri(t)+r2(t). The first property above expresses the time invariance:namely,if an input is de- layed by T,the corresponding output remains the same except for the delay of 7.The second and third properties express the linearity.That is.if an input is scaled by a, the corresponding output remains the same except for being scaled by a.Also,the s(t (al 6 Figure 2.3 Relation of input and output waveforms for a communication channel with filtering.Part (a)shows the response r(t)to an input s(t)consisting of a rectangular pulse,and part (b)shows the response to a sequence of pulses.Part(b)also illustrates the NRZ code in which a sequence of binary inputs (11 0 1 00)is mapped into rectangular pulses.The duration of each pulse is equal to the time between binary inputs
Sec. 2.2 The Physical Layer: Channels and Modems 41 the digital data into s(t) so as to minimize the deleterious effects of this distortion. Note that a black box viewpoint of the physical channel is taken here, considering the inputoutput relation rather than the internal details of the analog channel. For example, if an ordinary voice telephone circuit (usually called a voice-grade circuit) is used as the analog channel, the physical path of the channel will typically pass through multiple switches, multiplexers, demultiplexers, modulators, and demodulators. For dial-up lines, this path will change on each subsequent call, although the specification of tolerances on the input-output characterization remain unchanged. 2.2.1 Filtering One of the most important distorting effects on most analog channels is linear timeinvariant filtering. Filtering occurs not only from filters inserted by the channel designer but also from the inherent behavior of the propagation medium. One effect of filtering is to "smooth out" the transmitted signal set). Figure 2.3 shows two examples in which set) is first a single rectangular pulse and then a sequence of rectangular pulses. The defining properties of linear time-invariant filters are as follows: 1. If input s(t) yields output r(t), then for any T, input set - T) yields output ret - T). 2. If set) yields ret), then for any real number Ct, ns(t) yields ctr(t). 3. If 81 (t) yields 1'1 (t) and se(t) yields re(t), then Sl (t) + se(t) yields rj (t) + re(t). The first property above expresses the time invariance: namely, if an input is delayed by T, the corresponding output remains the same except for the delay of T. The second and third properties express the linearity. That is, if an input is scaled by ct, the corresponding output remains the same except for being scaled by ct. Also, the o __.....Dl..:_(t_)__ o T 1 0 1 0 0 __ 1 _ 1s(t) LDI---__- o T 2T 3T 4T 5T 6T -,U Il..-_I (a) (b) o T 2T Figure 2.3 Relation of input and output waveforms for a communication channel with filtering. Part (a) shows the response r(t) to an input 8(t) consisting of a rectangular pulse, and part (b) shows the response to a sequence of pulses. Part (b) also illustrates the NRZ code in which a sequence of binary inputs (I 1 0 I 00) is mapped into rectangular pulses. The duration of each pulse is equal to the time between binary inputs