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
42 Point-to-Point Protocols and Links Chap.2 output due to the sum of two inputs is simply the sum of the corresponding outputs. As an example of these properties,the output for Fig.2.3(b)can be calculated from the output in Fig.2.3(a).In particular,the response to a negative-amplitude rectangular pulse is the negative of that from a positive-amplitude pulse (property 2),the output from a delayed pulse is delayed from the original output (property 1),and the output from the sum of the pulses is the sum of the outputs for the original pulses (prop- erty 3). Figure 2.3 also illustrates a simple way to map incoming bits into an analog waveform s(t).The virtual channel accepts a new bit from the DLC module each T seconds;the bit value 1 is mapped into a rectangular pulse of amplitude +1,and the value 0 into amplitude-1.Thus,Fig.2.3(b)represents s(t)for the data se- quence 110100.This mapping scheme is often referred to as a nonreturn to zero (NRZ) code.The notation NRZ arises because of an alternative scheme in which the pulses in s(t)have a shorter duration than the bit time T,resulting in s(t)returning to 0 level for some interval between each pulse.The merits of these schemes will become clearer later. Next,consider changing the rate at which bits enter the virtual channel.Figure 2.4 shows the effect of increasing the rate by a factor of 4(i.e.,the signaling interval is reduced from T to T/4).It can be seen that output r(t)is more distorted than before. The problem is that the response to a single pulse lasts much longer than a pulse time,so that the output at a given t depends significantly on the polarity of several input pulses; this phenomenon is called intersymbol interference. From a more general viewpoint,suppose that h(t)is the channel output correspond- ing to an infinitesimally narrow pulse of unit area at time 0.We call h(t)the impulse response of the channel.Think of an arbitrary input waveform s(t)as a superposition of very narrow pulses as shown in Fig.2.5.The pulse from s()to s(T+6)can be viewed as a small impulse of area os()at time T:this gives rise to the output 8s()h(t-T)at 0T/4 0T4 (a) r(t) 3T/2 3T/2 (b) Figure 2.4 Relation of input and output waveforms for the same channel as in Fig.2.3. Here the binary digits enter at 4 times the rate of Fig.2.3,and the rectangular pulses last one-fourth as long.Note that the output r(t)is more distorted and more attenuated than that in Fig.2.3
42 Point-ta-Point Protocols and Links Chap. 2 output due to the sum of two inputs is simply the sum of the corresponding outputs. As an example of these properties, the output for Fig. 2.3(b) can be calculated from the output in Fig. 2.3(a). In particular, the response to a negative-amplitude rectangular pulse is the negative of that from a positive-amplitude pulse (property 2), the output from a delayed pulse is delayed from the original output (property 1), and the output from the sum of the pulses is the sum of the outputs for the original pulses (property 3). Figure 2.3 also illustrates a simple way to map incoming bits into an analog waveform s(t). The virtual channel accepts a new bit from the DLe module each T seconds; the bit value I is mapped into a rectangular pulse of amplitude + I, and the value 0 into amplitude -1. Thus, Fig. 2.3(b) represents s(t) for the data sequence 110100. This mapping scheme is often referred to as a nonreturn to zero (NRZ) code. The notation NRZ arises because of an alternative scheme in which the pulses in s(t) have a shorter duration than the bit time T, resulting in s(t) returning to 0 level for some interval between each pulse. The merits of these schemes will become clearer later. Next, consider changing the rate at which bits enter the virtual channel. Figure 2.4 shows the effect of increasing the rate by a factor of 4 (i.e., the signaling interval is reduced from T to T /4). It can be seen that output r(t) is more distorted than before. The problem is that the response to a single pulse lasts much longer than a pulse time, so that the output at a given t depends significantly on the polarity of several input pulses; this phenomenon is called intersymbol interference. From a more general viewpoint, suppose that h(t) is the channel output corresponding to an infinitesimally narrow pulse of unit area at time O. We call h(t) the impulse response of the channel. Think of an arbitrary input waveform s(t) as a superposition of very narrow pulses as shown in Fig. 2.5. The pulse from S(T) to S(T +6) can be viewed as a small impulse of area 6S(T) at time T; this gives rise to the output IiS(T)h(t - T) at o T/4 r(t) o T/4 (a) 3T/2 o T/2 T~ (b) Figure 2.4 Relation of input and output waveforms for the same channel as in Fig. 2.3. Here the binary digits enter at 4 times the rate of Fig. 2.3. and the rectangular pulses last one-fourth as long. Note that the output r(t) is more distorted and more attenuated than that in Fig. 2.3
Sec.2.2 The Physical Layer:Channels and Modems 43 Area≈5s(T) Area≈islr+6) 5t) T+6 8(r)h(t-r) 6sr+6}ht-T-6) Figure 2.5 Graphical interpretation of the convolution equation.Input s(t)is viewed as the superposition of narrow pulses of width 6.Each such pulse yields an output 6s()h(t-7).The overall output is the sum of these pulse responses. time t.Adding the responses at time t from each of these input pulses and going to the limit6→0 shows that r-Jx s(T)h(t -T)dT (2.1) This formula is called the convolution integral,and r(t)is referred to as the con- volution of s(t)and h(t).Note that this formula asserts that the filtering aspects of a channel are completely characterized by the impulse response h(t);given h(t),the out- put r(t)for any input s(t)can be determined.For the example in Fig.2.3,it has been assumed that h(t)is 0 for t<0 and ae-for t0.where =2/T.Given this,it is easy to calculate the responses in the figure. From Eq.(2.1),note that the output at a given time t depends significantly on the input s(7)over the interval where h(t-T)is significantly nonzero.As a result,if this interval is much larger than the signaling interval T between successive input pulses, significant amounts of intersymbol interference will occur. Physically,a channel cannot respond to an input before the input occurs,and therefore h(t)should be 0 for t <0;thus,the upper limit of integration in Eq.(2.1) could be taken as t.It is often useful,however,to employ a different time reference at the receiver than at the transmitter,thus eliminating the effect of propagation delay.In this case,h(t)could be nonzero for t<0,which is the reason for the infinite upper limit of integration. 2.2.2 Frequency Response To gain more insight into the effects of filtering,it is necessary to look at the frequency domain as well as the time domain;that is,one wants to find the effect of filtering
.... Sec. 2.2 The Physical Layer: Channels and Modems lis(r)h(t - r) ~IiS(r+Ii)h(t -r-li) r r+1i t-- t-- 43 (2.1 ) Figure 2.5 Graphical interpretation of the convolution equation. Input s(t) is viewed as the superposition of narrow pulses of width 6. Each such pulse yields an output 6S(T)h(t - T). The overall output is the sum of these pulse responses. time t. Adding the responses at time t from each of these input pulses and going to the limit {) ---+ 0 shows that T(t) = l:x s(T)h(t - T)dT This fonnula is called the convolution integral, and T(t) is referred to as the convolution of set) and h(t). Note that this fonnula asserts that the filtering aspects of a channel are completely characterized by the impulse response h(t); given h(t), the output ret) for any input set) can be detennined. For the example in Fig. 2.3, it has been assumed that h(t) is 0 for t < 0 and ae- n / for t 2: 0, where a = 21T. Given this, it is easy to calculate the responses in the figure. From Eq. (2.1), note that the output at a given time t depends significantly on the input SeT) over the interval where h(t - T) is significantly nonzero. As a result, if this interval is much larger than the signaling interval T between successive input pulses, significant amounts of intersymbol interference will occur. Physically, a channel cannot respond to an input before the input occurs, and therefore h(t) should be 0 for t < 0; thus, the upper limit of integration in Eq. (2.1) could be taken as t. It is often useful, however, to employ a different time reference at the receiver than at the transmitter, thus eliminating the effect of propagation delay. In this case, h(t) could be nonzero for t < 0, which is the reason for the infinite upper limit of integration. 2.2.2 Frequency Response To gain more insight into the effects of filtering, it is necessary to look at the frequency domain as well as the time domain; that is, one wants to find the effect of filtering
44 Point-to-Point Protocols and Links Chap.2 on sinusoids of different frequencies.It is convenient analytically to take a broader viewpoint here and allow the channel input s(t)to be a complex function of t;that is, s(t)=Rels(t)]+j Im[s(t)],where j=v-1.The actual input to a channel is always real,of course.However,if s(t)is allowed to be complex in Eq.(2.1),r(t)will also be complex,but the output corresponding to Re[s(t)]is simply Relr(t)][assuming that h(t) is reall,and the output corresponding to Im[s(t)]is Imfr(t)].For a given frequency f,let s()in Eq.(2.1)be the complex sinusoid =cos(2f)+j sin(f).Integrating Eq.(2.1)(see Problem 2.3)yields r(t)=H(f)e (2.2) where H0= h(r)e-i2xidr (2.3) Thus,the response to a complex sinusoid of frequency f is a complex sinusoid of the same frequency,scaled by the factor H(f).H(f)is a complex function of the frequency f and is called the frequency response of the channel.It is defined for both positive and negative f.Let H(f)be the magnitude and H(f)the phase of H(f) li.e..H(f)=H The response r(t)to the real sinusoid cos(2ft)is given by the real part of Eq.(2.2),or r1(t)=|H(f)川cos2πft+∠H(f] (2.4) Thus,a real sinusoidal input at frequency f gives rise to a real sinusoidal output at the same freqency:H(f)gives the amplitude and H(f)the phase of that output relative to the phase of the input.As an example of the frequency response,if h(t)=ae-a for t≥0,then integrating Eq.(2.3)yields Hf)= (2.5) a+j2πf Equation(2.3)maps an arbitrary time function h(t)into a frequency function H(f); mathematically,H(f)is the Fourier transform of h(t).It can be shown that the time function h(t)can be recovered from H(f)by the inerse Fourier transform H(edf (2.6) Equation (2.6)has an interesting interpretation;it says that an (essentially)arbi- trary function of time h(t)can be represented as a superposition of an infinite set of infinitesimal complex sinusoids,where the amount of each sinusoid per unit frequency is H(f).as given by Eq.(2.3).Thus.the channel input s(t)(at least over any finite interval)can also be represented as a frequency function by s(= s(t)e-j2r'dt (2.7) stt)-stpezrdr (2.8)
44 Point-to-Point Protocols and Links Chap. 2 on sinusoids of different frequencies. It is convenient analytically to take a broader viewpoint here and allow the channel input set) to be a complex function of t; that is, set) = Re[s(t)] + j Im[s(t)], where j = ;=T. The actual input to a channel is always real, of course. However, if set) is allowed to be complex in Eq. (2.1), ret) will also be complex, but the output corresponding to Rels(t)] is simply Relr(t)] [assuming that h(t) is real], and the output corresponding to Im[s(t)] is Im[r(t)]. For a given frequency f, let s( T) in Eq. (2.1) be the complex sinusoid ej27r j T = cos(2rrf T) +j sin(2rrf T). Integrating Eq. (2.1) (see Problem 2.3) yields r(t) = H(f)ej27rjf (2.2) where (2.3) Thus, the response to a complex sinusoid of frequency f is a complex sinusoid of the same frequency, scaled by the factor H(j). H(j) is a complex function of the frequency f and is called the frequency response of the channel. It is defined for both positive and negative f. Let [H(j)[ be the magnitude and LH(j) the phase of H(f) [i.e., H(j) = [H(f)\ejLH1fl]. The response rl(t) to the real sinusoid cos(2rrft) is given by the real part of Eq. (2.2), or rl (t) = [H(j)[ cos[27rft + UI(j)] (2.4) (2.6) (2.8) (2.7) Thus, a real sinusoidal input at frequency f gives rise to a real sinusoidal output at the same freqency; IH(j)1 gives the amplitude and LH(j) the phase of that output relative to the phase of the input. As an example of the frequency response, if h(t) = ae-of for t 0, then integrating Eq. (2.3) yields n H(j) = +'2 f (2.5) a J rr. Equation (2.3) maps an arbitrary time function h(t) into a frequency function H(j); mathematically, H(j) is the Fourier transform of h(t). It can be shown that the time function h(t) can be recovered from H(f) by the inverse Fourier transform h(t) = .l: H(j)ej27rjf df Equation (2.6) has an interesting interpretation; it says that an (essentially) arbitrary function of time hU) can be represented as a superposition of an infinite set of infinitesimal complex sinusoids, where the amount of each sinusoid per unit frequency is H(f), as given by Eq. (2.3). Thus, the channel input set) (at least over any finite interval) can also be represented as a frequency function by S(f) = .l: S(tje-j 2TC j l dt set) = .l: S(j)ej27rjfdf
Sec.2.2 The Physical Layer:Channels and Modems 45 The channel output r(t)and its frequency function ROf)are related in the same way. Finally,since Eq.(2.2)expresses the output for a unit complex sinusoid at frequency f, and since s(t)is a superposition of complex sinusoids as given by Eq.(2.8),it follows from the linearity of the channel that the response to s(t)is r(t)=H(f)S(f)ej2rf'df (2.9) Since r(t)is also the inverse Fourier transform of R(f),the input-output relation in terms of frequency is simply R(f)=H(f)s(f) (2.10) Thus,the convolution of h(t)and s(t)in the time domain corresponds to the multiplication of H(f)and S(f)in the frequency domain.One sees from Eq.(2.10)why the frequency domain provides insight into filtering. If H(f)=I over some range of frequencies and S(f)is nonzero only over those frequencies,then R(f)=S(f),so that r(t)=s(t).One is not usually so fortunate as to have H(f)=I over a desired range of frequencies,but one could filter the received signal by an additional filter of frequency response (f)over the desired range: this additional filtering would yield a final filtered output satisfying r(t)=s(t).Such filters can be closely approximated in practice subject to additional delay [i.e.,satisfying r(t)=s(t-r).for some delay ]Such filters can even be made to adapt automatically to the actual channel response H(f);filters of this type are usually implemented digitally, operating on a sampled version of the channel output,and are called adaptive equalizers. These filters can and often are used to overcome the effects of intersymbol interference. The question now arises as to what frequency range should be used by the signal s(t):it appears at this point that any frequency range could be used as long as H(f) is nonzero.The difficulty with this argument is that the additive noise that is always present on a channel has been ignored.Noise is added to the signal at various points along the propagation path,including at the receiver.Thus,the noise is not filtered in the channel in the same way as the signal.If H(f)is very small in some interval of frequencies.the signal is greatly attenuated at those frequencies.but typically the noise is not attenuated.Thus.if the received signal is filtered at the receiver by H(f),the signal is restored to its proper level,but the noise is greatly amplified. The conclusion from this argument(assuming that the noise is uniformly distributed over the frequency band)is that the digital data should be mapped into s(t)in such a way that S(f)is large over those frequencies where H(f)is large and S(f)is small (ideally zero)elsewhere.The cutoff point between large and small depends on the noise level and signal level and is not of great relevance here.particularly since the argument above is qualitative and oversimplified.Coming back to the example where h(t)=ae for t>0,the frequency response was given in Eq.(2.5)as H(f)=a/(a+j2f).It is seen that H(f)is approximately I for small f and decreases as 1/f for large f.We shall not attempt to calculate S(f)for the NRZ code of Fig.2.3,partly because s(t)and S(f)depend on the particular data sequence being encoded,but the effect of changing the signaling interval T can easily be found.If T is decreased,then s(t)is compressed
Sec. 2.2 The Physical Layer: Channels and Modems 45 The channel output ret) and its frequency function R(j) are related in the same way. Finally, since Eq. (2.2) expresses the output for a unit complex sinusoid at frequency j, and since s(t) is a superposition of complex sinusoids as given by Eq. (2.8), it follows from the linearity of the channel that the response to s(t) is ret) = I: H(j)S(j)eJ27Cftdj (2.9) Since ret) is also the inverse Fourier transform of R(j), the input-output relation in terms of frequency is simply R(j) = H(j)S(j) (2.10) Thus, the convolution of h(t) and 8(t) in the time domain corresponds to the multiplication of H(j) and S(j) in the frequency domain. One sees from Eq. (2.10) why the frequency domain provides insight into filtering. If H(j) = lover some range of frequencies and S(j) is nonzero only over those frequencies, then R(j) = S(j), so that ret) = s(t). One is not usually so fortunate as to have H(j) = lover a desired range of frequencies, but one could filter the received signal by an additional filter of frequency response H- 1 (j) over the desired range; this additional filtering would yield a final filtered output satisfying r(t) = .s(t). Such filters can be closely approximated in practice subject to additional delay [i.e., satisfying r(t) = 8(t - T), for some delay T]. Such filters can even be made to adapt automatically to the actual channel response H(!); filters of this type are usually implemented digitally, operating on a sampled version of the channel output, and are called adaptive equalizers. These filters can and often are used to overcome the effects of intersymbol interference. The question now arises as to what frequency range should be used by the signal .s(t); it appears at this point that any frequency range could be used as long as H(j) is nonzero. The difficulty with this argument is that the additive noise that is always present on a channel has been ignored. Noise is added to the signal at various points along the propagation path, including at the receiver. Thus, the noise is not filtered in the channel in the same way as the signal. If IH(j)1 is very small in some interval of frequencies, the signal is greatly attenuated at those frequencies, but typically the noise is not attenuated. Thus, if the received signal is filtered at the receiver by H- 1 (j), the signal is restored to its proper level, but the noise is greatly amplified. The conclusion from this argument (assuming that the noise is uniformly distributed over the frequency band) is that the digital data should be mapped into 8(t) in such a way that IS(j)1 is large over those frequencies where IH(j)1 is large and IS(j)1 is small (ideally zero) elsewhere. The cutoff point between large and small depends on the noise level and signal level and is not of great relevance here, particularly since the argument above is qualitative and oversimplified. Coming back to the example where 1I(t) = ae- of for t 2' 0, the frequency response was given in Eq. (2.5) as H(j) = 0:/(0 +j2K!). It is seen that IH(j)1 is approximately I for small/and decreases as l/! for large f. We shall not attempt to calculate S(j) for the NRZ code of Fig. 2.3, partly because .s(t) and S(j) depend on the particular data sequence being encoded, but the effect of changing the signaling interval T can easily be found. If T is decreased, then s(t) is compressed
46 Point-to-Point Protocols and Links Chap.2 in time,and this correspondingly expands S(f)in frequency (see Problem 2.5).The equalization at the receiver would then be required either to equalize H(f)over a broader band of frequencies,thus increasing the noise,or to allow more intersymbol interference. 2.2.3 The Sampling Theorem A more precise way of looking at the question of signaling rates comes from the sampling theorem.This theorem states that if a waveform s(t)is low-pass limited to frequencies at most W [i.e..S(f)=0,for f>Wl,then [assuming that S(f)does not contain an impulse at f =W],s(t)is completely determined by its values each 1/(2W)seconds; in particular, s(t)= 立() sin[2W(t-i/(2W))] (2.11) 2πW[t-i/(2W)] Also,for any choice of sample values at intervals 1/(2W),there is a low-pass waveform, given by Eq.(2.11),with those sample values.Figure 2.6 illustrates this result. The impact of this result,for our purposes,is that incoming digital data can be mapped into sample values at a spacing of 1/(2W)and used to create a waveform of the given sample values that is limited to f<W.If this waveform is then passed through an ideal low-pass filter with H(f)=1 for f<W and H(f)=0 elsewhere, the received waveform will be identical to the transmitted waveform (in the absence of noise);thus,its samples can be used to recreate the original digital data. The NRZ code can be viewed as mapping incoming bits into sample values of s(t), but the samples are sent as rectangular pulses rather than the ideal(sin )/r pulse shape of Eq.(2.11).In a sense,the pulse shape used at the transmitter is not critically important s(0)sin 2mWt 2xWt s(t) 3 2w 2W 2W 2W sin 2xW (t 1 2W 2W 2xW t- 2W Figure 2.6 Sampling theorem,showing a function s(t)that is low-pass limited to frequencies at most W.The function is represented as a superposition of(sin)/z functions.For each sample,there is one such function,centered at the sample and with a scale factor equal to the sample value
46 Point-to-Point Protocols and Links Chap. 2 r in time, and this correspondingly expands S(n in frequency (see Problem 2.5). The equalization at the receiver would then be required either to equalize H(f) over a broader band of frequencies, thus increasing the noise, or to allow more intersymbol interference. 2.2.3 The Sampling Theorem A more precise way of looking at the question of signaling rates comes from the sampling theorem. This theorem states that if a waveform set) is low-pass limited to frequencies at most W [i.e., S(n = 0, for IfI > W], then [assuming that S(n does not contain an impulse at f = W], set) is completely determined by its values each 1/(2W) seconds; in particular, set) = s (_7_') sin[21rW(t - i/(2W))] . 2W 21rW[t - i/(2W)] l=-CXJ (2.11 ) Also, for any choice of sample values at intervals 1/(2W), there is a low-pass waveform, given by Eq. (2.11), with those sample values. Figure 2.6 illustrates this result. The impact of this result, for our purposes, is that incoming digital data can be mapped into sample values at a spacing of 1/(2W) and used to create a waveform of the given sample values that is limited to IfI :::; w. If this waveform is then passed through an ideal low-pass filter with H(f) = 1 for IfI :::; Wand H(f) = ° elsewhere, the received waveform will be identical to the transmitted waveform (in the absence of noise); thus, its samples can be used to recreate the original digital data. The NRZ code can be viewed as mapping incoming bits into sample values of set), but the samples are sent as rectangular pulses rather than the ideal (sinx)/x pulse shape of Eq. (2.11). In a sense, the pulse shape used at the transmitter is not critically important 5(0) sin 21TWt 21TWt 2W sIt) 7 / / / -1'- / -........... ---.r'!!!'::=--::O::"""'/~-::::"---------::'>.~/'<:--'r--~:-----~"'::'--_::':::"-"-'....-==-===-="", t 1----~ '2' o 2W sin 21TW (t - 2W) 21TW (t - 2~ ) Figure 2.6 Sampling theorem, showing a function s(t) that is low-pass limited to frequencies at most W. The function is represented as a superposition of (sin x)/ x functions. For each sample, there is one such function, centered at the sample and with a scale factor equal to the sample value