FIFTH EDITION
`
`DATA AND
`COMPUTER
`COMMUNICATIONS
`
`WILLIAM STALLINGS
`
`PRENTICE HALL
`UPPER SADDLE RIVER, N EW J ERSEY 07458
`
`Ex.1013
`APPLE INC. / Page 1 of 23
`
`

`

`lilttllry (>£ Cm1gress Catato,gblg-fD.hblic.fic1ft D11t11
`Stallu1~ Wiltiatn.
`Uata IU'ld rotnptltct eonunimiqti,,.1.~ I William StaJh.ug .. - 5th o:<l.
`p. Clll.
`(l)dUdCS biblioyopb.kal refooo~• ,,nil iu<l('.X.
`ISB'N (hwalid) O-OZ..-15425-3
`1. Uata transmi'ssioJl $)'Stem$, 1. <:ompul~r m-1.,....,rt.li.
`I K!IIO:S.S73 1996
`IXJ.l.6-dc-20
`
`L •1ilk:.
`96-2•H19
`CH!
`
`Publisher: Alart Alli
`Editor-in-Chief: Mama 110110n
`Pr(lduc:1iM Ma,1ae,cr: Ba)·ani Mendoza de Leon
`Production l:.t.litor: :Mona Pompili
`Manttt.inr, Editor: Laura Steele
`Design Duee10,: A01y R<isen
`
`~sjg(ler: Judy \ 1at1-{'..oni.~lio
`CO\·cr Desi&'Uer: Tom Nery
`O..\·ec UJu~utttor. Wendy Grossman
`Copf Editor: Chip Lee
`M.in1.1foc1u,-il'lg_ AU)'Cr: Donna Sullivan
`Editorial Assi.staot: Shirley McGui,-e
`
`e 19'r. by Pr~111ic,e H3U. Inc.
`Simon & Schuster I A Viacom Compaoy
`Upper Saddle Ri"er. New Jersey 07458
`
`Th..: aull,<ir .·rnd puhli~hc,· of this book have used their best c.fforLs in prepanag ,hi.s book. 11,ese effo11(;
`include the developmeol. research • .1mJ 1es1i11g (If 1J1e 1hcMi~ :ln<I proir:im~ 10 dc1crminc their
`etrec1i,,en~. The aut hor a!ld puhlishcr shall not be liable in any e.,.cot for int.tdeota.1 or oon~ql11.rntfal
`damages in coonoctioo w1th. or ar~ng out o f, lhe ru~l'listii,,g. pc1fn11n:lm:\-:, Muse of these programs.
`
`AIJ right~ ,c~,'\-Cd. Ko part of thL-. book may be reproduced. in any form or by aoy me.an::., without
`permission tn wnting from tht pubfu.h..:r.
`
`Printed in the United Stales of America
`
`10 9 8 7 6 5 4 3 2
`
`l
`
`ISBN 0-02-415425-3
`
`rR.ci,.,ici:.-IIALL lITTFRNATIO ... .\I, (UK) l,l\trll::O, f.omfon
`PRFt,.*l'I CF · HAU. Of• AUSIKAU,\ PTY. LIMfTl!D.Syd11ey
`PR.Ci,. 11CE•J l:\J.L C\.°'4AOA. lNC'., TQr(lll!Q
`PRFl>,*rt(E HAI.I. HISl'A-.(MMl'KU:,\',t,\, S.A .. Mexico
`PRCl'-TICE·H:\.LL OF l~OIA PRJ\'ATE LL\tlTED. NC'w D<:fh1
`P l~ ft,.'TLCE· HA IJ.. Of JAl'A.._, IN<:., Tt1k)'O
`S IMO ... & SCHl :STP.k ASI.'\ Pm . LTD .• Si11gapun·
`EorroRA f'llE.'fflC'F •HA11 IX> R1~"--"". l .m,,., Rio d~ .laneim
`
`
`
`Ex.1013
`APPLE INC. / Page 2 of 23
`
`

`

`C ONTEN
`
`CHAPTER 1
`INTRODUCTION 1
`1.1 A Communications Model 2
`1.2 Data Communications 5
`1.3 Data Communications Networking 7
`Protocols and Protocol Architecture 11
`1.4
`1.5
`Standards 21
`1.6 Outline of the Book 22
`A PPENDIX 1A STANDARDS ORGANIZATIONS 27
`INTERNET RESOURCES 31
`A PPENDIX 1B
`
`PART ONE
`Data Communications 33
`
`CHAPTER 2
`DATA TRANSMISSION 33
`Concepts and Terminology 34
`2.1
`2.2 Analog and Digital Data Transmission 45
`2.3
`Transmission Impairments 55
`Recommended Reading 64
`2.4
`2.5
`Problems 64
`APPENDIX 2A FOURIER ANALYSIS 67
`APPENDIX 2 B DECIBELS AND SIGNAL STRENGTH 71
`
`CHAPTER 3
`TRANSMISSION MEDIA 7 3
`3.1 Guided Transmission Media 75
`3.2 Wireless Transmission 85
`
`Xlll
`
`
`
`Ex.1013
`APPLE INC. / Page 3 of 23
`
`

`

`xiv C O NTENTS
`
`3.3
`3.4
`
`Recommended Reading 93
`Problems 93
`
`CHAPTER 4
`DATA ENCODING 95
`4.1 Digital Data, Digital Signals 97
`4.2 Digital Data, Analog Signals 107
`Analog Data, Digital Signals 115
`4.3
`4.4 Analog Data, Analog Signals 121
`Spread Spectrum 128
`4.5
`4.6
`R ecommended Reading 132
`Problems 132
`4.7
`APPENDIX 4A PROOF OF THE SAMPLING THEOREM 136
`
`CHAPTER 5
`THE DATA COMMUNICATION INTERFACE 139
`5.1 Asynchronous and Synchronous Transmission 140
`Line Configurations 144
`5.2
`Interfacing 145
`5.3
`Recommended Reading 156
`5.4
`Problems 156
`5.5
`
`CHAPTER 6
`DATA LINK CONTRL 157
`6.1
`Flow Control 159
`Error Detection 164
`6.2
`6.3
`Error Control 171
`6.4
`High-Level Data Link Control (HDLC) 176
`6.5 Other Data Link Control Protocols 184
`6.6
`Recommended Reading 186
`Problems 187
`6.7
`APPENDIX 6A PERFORMANCE I SSUES 190
`
`CHAPTER 7
`MULTIPLEXING 197
`Frequency-Division Multiplexing 199
`7.1
`Synchronous Time-Division Multiplexing 205
`7.2
`Statistical Time-Division Multiplexing 219
`7.3
`Recommended Reading 226
`7.4
`Problems 226
`7.5
`
`Ex.1013
`APPLE INC. / Page 4 of 23
`
`

`

`PART TWO
`Wide-Area Networks 229
`
`C O NTENTS XV
`
`CHAPTER 8
`CIRCUIT SWITCHING 229
`Switched Networks 230
`8.1
`Circuit-Switching Networks 231
`8.2
`Switching Concepts 234
`8.3
`Routing in Circuit-Switched Networks 240
`8.4
`Control Signaling 244
`8.5
`Recommended Reading 252
`8.6
`Problems 252
`8.7
`
`CHAPTER 9
`PACKET SWITCHING 253
`Packet-Switching Principles 253
`9.1
`Routing 264
`9.2
`Congestion Control 278
`9.3
`9.4 X.25 282
`Recommended Reading 291
`9.5
`9.6
`Problems 291
`APPENDIX 9A LEAST-COST ALGORITHMS 296
`
`CHAPTER 10
`FRAME RELAY 301
`10.1 Background 302
`10.2 Frame Relay Protocol Architecture 304
`10.3 Frame Relay Call Control 307
`10.4 User Data Transfer 313
`10.5 Network Function 315
`10.6 Congestion Control 316
`10.7 Recommended Reading 325
`10.8 Problems 325
`
`CHAPTER 11
`ASYNCHRONOUS TRANSFER MODE (ATM) 327
`11.1 Protocol Architecture 328
`11.2 ATM Logical Connections 329
`11.3 ATM Cells 334
`11.4 Transmission of ATM Cells 338
`
`Ex.1013
`APPLE INC. / Page 5 of 23
`
`

`

`XVI CONTENTS
`
`11.5 ATM Adaptation Layer 342
`11.6 Traffic and Congestion Control 347
`11.7 Recommended Reading 359
`11.8 Problems 360
`
`PART THREE
`Local Area Networks 363
`
`,CHAPTER 12
`LAN TECHNOLOGY 363
`12.1 LAN Architecture 364
`12.2 Bus/Tree LANs 337
`12.3 Ring LAN s 385
`12.4 Star LANs 389
`12.5 Wireless LANs 393
`12.6 Recommended Reading 399
`12.7 Problems 399
`
`CHAPTER 13
`LAN S YSTEMS 401
`13.1 Ethernet and Fast Ethernet (CSMA/CD) 402
`13.2 Token Ring and FDDI 413
`lO0VG-AnyLAN 427
`13.3
`13.4 ATM LANs 431
`13.5 Fibre Channel 435
`13.6 Wireless LANs 442
`13.7 Recommended Reading 447
`13.8 Problems 448
`APPENDIX 13A DIGITAL SIGNAL ENCODING FOR LANs 451
`APPENDIX 13B PERFORMANCE ISSUES 458
`
`CHAPTER 14
`B RIDGES 465
`14.1 Bridge Operation 466
`14.2 Routing with Bridges 470
`14.3 ATM LAN Emulation 487
`14.4 Recommended Reading 495
`14.5 Problems 495
`
`Ex.1013
`APPLE INC. / Page 6 of 23
`
`

`

`C ONTENTS XVII
`
`PART FOUR
`Communications Architecture and
`Protocols 497
`
`CHAPTER 15
`PROTOCOLS AND ARCHITECTURE 497
`15.1 Protocols 498
`15.2 OSI 510
`15.3 TCP/IP Protocol Suite 520
`15.4 Recommended Reading 526
`15.5 Problems 526
`
`CHAPTER 16
`I NTERNETWORKING 527
`16.1 Principles of Internetworking 529
`16.2 Connectionless Intemetworking 534
`16.3 The Internet Protocol 541
`16.4 Routing Protocol 549
`16.5 1Pv6 (IPng) 559
`16.6
`ICMPv6 578
`16.7 Recommended Reading 582
`16.8 Problems 582
`
`CHAPTER 17
`TRANSPORT PROTOCOLS 585
`17.1 Transport Services 586
`17.2 Protocol Mechanisms 591
`17.3 TCP 610
`17.4 UDP 619
`17.5 Recommended Reading 619
`17.8 Problems 620
`
`CHAPTER 18
`N ETWORK SECURITY 623
`18.1 Security Requirements and Attacks 624
`18.2 Privacy with Conventional Encryption 627
`18.3 Message Authentication and Hash Functions 638
`18.4 Public-Key Encryption and Digital Signatures 649
`
`Ex.1013
`APPLE INC. / Page 7 of 23
`
`

`

`XVlll CONTENTS
`
`18.5 1Pv4 and 1Pv6 Security 659
`18.6 Recommended Reading 664
`18.8 Problems 665
`
`CHAPTER 19
`DISTRIBUTED APPLICATIONS 667
`19.1 Abstract Syntax Notation One (ASN.l) 668
`19.2 Network Management-SNMPV2 685
`19.3 Electronic Mail- SMTP and MIME 697
`19.4 Uniform Resource Locators (URL) and Universal Resource Identifiers
`(URI) 712
`19.5 Hypertext Transfer Protocol (HTTP) 719
`19.6 Recommended Reading 736
`19.7 Problems 737
`
`APPENDIX A
`ISDN AND BROADBAND ISDN 739
`A.1 Overview of ISDN 740
`ISDN Channels 747
`A.2
`A.3 User Access 750
`ISDN Protocols 752
`A.4
`A.5 Broadband ISDN 764
`A.6 Recommended Reading 768
`A.7 Problems 768
`
`APPENDIX B
`RFCs CITED IN THIS BooK 771
`
`GLOSSARY 773
`
`REFERENCES 78 5
`
`INDEX 791
`
`Ex.1013
`APPLE INC. / Page 8 of 23
`
`

`

`Wide-Area Networks
`
`CHAPTERS
`
`CIRCUIT S-W-ITCHING
`
`8.1 Switching Networks
`8.2 Circuit-Switching Networks
`8.3 Switching Concepts
`8.4 Routing in Circuit-Switched Networks
`8.5 Control Signaling
`8. 6 Recommended Reading
`8. 7 Problems
`
`
`
`Ex.1013
`APPLE INC. / Page 9 of 23
`
`

`

`230 CHAPTER 8 / CIR CUIT SWITCH IN G
`
`Since the invention of the telephone, circuit switching has been the dominant
`
`technology for voice communications, and it will remain so well into the
`ISDN era. This chapter begins with an introduction to the concept of a
`switched communications network and then looks at the key characteristics of a
`circuit-switching network.
`
`8.1 SWITCIIlNG NETWORKS
`
`For transmission of data1 beyond a local area, communication is typically achieved
`by transmitting data from source to destination through a network of intermediate
`switching nodes; this switched-network design is sometimes used to implement
`LANs and MANs as well. The switching nodes are not concerned with the content
`of the data; rather, their purpose is to provide a switching facility that will move the
`data from node to node until they reach their destination. Figure 8.1 illustrates a
`simple network. The end devices that wish to communicate may be referred to as
`stations. The stations may be computers, terminals, telephones, or other communi(cid:173)
`cating devices. We will refer to the switching devices whose purpose is to provide
`communication as nodes, which are connected to each other in some topology by
`transmission links. Each station attaches to a node, and the collection of nodes is
`referred to as a communications network.
`
`L EGEND
`
`D = End station
`Q = Communication network node
`FIGURE 8.1 Simple switching network.
`
`1 We use this term here in a very general sense to include voice, image, and video, as well as ordinary
`data (e.g., numerical, text).
`
`Ex.1013
`APPLE INC. / Page 10 of 23
`
`

`

`8.2 / CIRCUIT-SWITCHING NETWORKS 231
`
`The types of networks that are discussed in this and the next three chapters
`are referred to as switched communication networks. Data entering the network
`from a station are routed to the destination by being switched from node to node.
`For example, in Figure 8.1, data from station A intended for station F are sent to
`node 4. They may then be routed via nodes 5 and 6 or nodes 7 and 6 to the desti(cid:173)
`nation. Several observations are in order:
`
`1. Some nodes connect only to other nodes ( e.g., 5 and 7). Their sole task is the
`internal (to the network) switching of data. Other nodes have one or more sta(cid:173)
`tions attached as well; in addition to their switching functions, such nodes
`accept data from and deliver data to the attached stations.
`2. Node-node links are usually multiplexed, using either frequency-division
`multiplexing (FDM) or time-division multiplexing (TDM).
`3. Usually, the network is not fully connected; that is, there is not a direct link
`between every possible pair of nodes. However, it is always desirable to have
`more than one possible path through the network for each pair of stations; this
`enhances the reliability of the network.
`
`Two quite different technologies are used in wide-area switched networks: cir(cid:173)
`cuit switching and packet switching. These two technologies differ in the way the
`nodes switch information from one link to another on the way from source to des(cid:173)
`tination. In this chapter, we look at the details of circuit switching; packet switching
`is pursued in Chapter 9. Two approaches that evolved from packet switching,
`namely frame relay and ATM, are explored in Chapters 10 and 11, respectively.
`
`8.2 CIRCUIT-SWITCHING NETWORKS
`
`Communication via circuit switching implies that there is a dedicated communica(cid:173)
`tion path between two stations. That path is a connected sequence of links between
`network nodes. On each physical link, a logical channel is dedicated to the connec(cid:173)
`tion. Communication via circuit switching involves three phases, which can be
`explained with reference to Figure 8.1.
`
`L Circuit establishment. Before any signals can be transmitted, an end-to-end
`(station-to-station) circuit must be established. For example, station A sends
`a request to node 4 requesting a connection to station E . Typically, the link
`from A to 4 is a dedicated line, so that part of the connection already exists.
`Node 4 must find the next leg in a route leading to node 6. Based on routing
`information and measures of availability and, perhaps, cost, node 4 selects the
`link to node 5, allocates a free channel (using frequency-division multiplexing,
`FDM, or time-division multiplexing, TDM) on that link and sends a message
`requesting connection to E. So far, a dedicated path has been established from
`A through 4 to 5. Because a number of stations may attach to 4, it must be able
`to establish internal paths from multiple stations to multiple nodes. The
`remainder of the process proceeds similarly. Node 5 dedicates a channel to
`node 6 and internally ties that channel to the channel from node 4. Node 6
`
`Ex.1013
`APPLE INC. / Page 11 of 23
`
`

`

`232 C HAPTER 8 / C IRCU IT SWITCHING
`completes the connection to E. In completing the connection, a test is made to
`determine if Eis busy or is prepared to accept the connection.
`2. Data transfer. Information can now be transmitted from A through the net(cid:173)
`work to E. The data may be analog or digital, depending on the nature of the
`network. As the carriers evolve to fully integrated digital networks, the use of
`digital (binary) transmission for both voice and data is becoming the dominant
`method. The path is A-4 link, internal switching through 4, 4-5 channel, inter(cid:173)
`nal switching through 5, 5-6 channel, and internal switching through 6, 6-E
`link. Generally, the connection is full-duplex.
`3. Circuit disconnect. After some period of data transfer, the connection is ter(cid:173)
`minated, usually by the action of one of the two stations. Signals must be prop(cid:173)
`agated to nodes 4, 5, and 6 to deallocate the dedicated resources.
`Note that the connection path is established before data transmission begins.
`Thus, channel capacity must be reserved between each pair of nodes in the path,
`and each node must have available internal switching capacity to handle the
`requested connection. The switches must have the intelligence to make these allo(cid:173)
`cations and to devise a route through the network.
`Circuit switching can be rathe r inefficient. Channel capacity is dedicated for
`the duration of a connection, even if no data are being transferred. For a voice con(cid:173)
`nection, utilization may be rather high, but it still does not approach 100 percent.
`For a terminal-to-computer connection, the capacity may be idle during most of the
`time of the connection. In terms of performance, there is a delay prior to signal
`transfer for call establishment. However, once the circuit is established, the network
`is effectively transparent to the users. Information is transmitted at a fixed data rate
`with no delay other than that required for propagation through the transmission
`links. The delay at each node is negligible.
`Circuit switching was developed to handle voice traffic but is now also used
`for data traffic. The best-known example of a circuit-switching network is the pub(cid:173)
`lic telephone network (Figure 8.2); this is actually a collection of national networks
`interconnected to form the international service. Although originally designed
`and implemented to service analog telephone subscribers, the network handles
`substantial data traffic via modem and is gradually being converted to a digital
`network. Another well-known application of circuit switching is the private branch
`exchange (PBX), used to interconnect telephones within a building or office. Cir(cid:173)
`cuit switching is also used in private networks-corporations or other large organi(cid:173)
`zations interconnecting their various sites; these usually consist of PBX systems at
`each site interconnected by dedicated, leased lines obtained from one of the carri(cid:173)
`ers, such as AT&T. A final common example of the application of circuit switching
`is the data switch. The data switch is similar to the PBX but is designed to inter(cid:173)
`connect digital data-processing devices, such as terminals and computers.
`A public telecommunications network can be described using four generic
`architectural components:
`• Subscribers: The devices that attach to the network. It is still the case that
`most subscriber devices to public telecommunications networks are tele(cid:173)
`phones, but the percentage of data traffic increases year by year.
`
`Ex.1013
`APPLE INC. / Page 12 of 23
`
`

`

`8.2 / CIRCUIT-SWITCHING NETWORKS 233
`
`Long-distance
`office
`0
`0
`0
`
`Long-distance
`office
`
`End office
`
`.
`·-------•
`
`I
`I
`
`I
`I
`
`Subscriber loop
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`•-------• •-------•
`
`Connecting trunk
`
`Intercity trunk
`
`FIGURE 8.2 Public circuit-switching network.
`
`• Local loop: The link between the subscriber and the network, also referred to
`as the subscriber loop. Almost all local loop connections used twisted-pair
`wire. The length of a local loop is typically in a range from a few kilometers
`to a few tens of kilometers.
`• Exchanges: The switching centers in the network. A switching center that
`directly supports subscribers is known as an end office. Typically, an end office
`will support many thousands of subscribers in a localized area. There are over
`19,000 end offices in the United States, so it is clearly impractical for each end
`office to have a direct link to each of the other end offices; this would require
`on the order of 2 X 108 links. Rather, intermediate switching nodes are used.
`• Trunks: The branches between exchanges. Trunks carry multiple voice(cid:173)
`frequency circuits using either FDM or synchronous TDM. Earlier, these
`were referred to as carrier systems.
`
`Subscribers connect directly to an end office, which switches traffic between
`subscribers and between a subscriber and other exchanges. The other exchanges are
`responsible for routing and switching traffic between end offices; this distinction is
`shown in Figure 8.3. To connect two subscribers attached to the same end office, a
`circuit is set up between them in the same fashion as described before. If two sub(cid:173)
`scribers connect to different end offices, a circuit between them consists of a chain
`of circuits through one or more intermediate offices. In the figure, a connection is
`established between lines a and b by simply setting up the connection through the
`end office. The connection between c and d is more complex. In e's end office, a
`connection is established between line c and one channel on a TDM trunk to the
`intermediate switch. In the intermediate switch, that channel is connected to a chan(cid:173)
`nel on a TDM trunk to d's end office. In that end office, the channel is connected
`to lined.
`Circuit-switching technology has been driven by those applications that han(cid:173)
`dle voice traffic. One of the key requirements for voice traffic is that there must be
`
`Ex.1013
`APPLE INC. / Page 13 of 23
`
`

`

`234 C H APTER 8 / C IRCUIT SWITC HING
`
`' '
`a
`b ~-----11- ✓
`
`End
`office
`
`C
`
`Tlll!l -- - - --1- -
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`- - - - - Trunk
`
`' I Intermediate
`----1i- ✓ exchange
`Trunk
`
`d
`
`1------1- ---------1---~
`
`End
`office
`
`FIGU RE 8.3 Circuit establishment.
`
`virtually no transmission delay and certainly no variation in delay. A constant sig(cid:173)
`nal transmission rate must be maintained, as transmission and reception occur at
`the same signal rate. These requirements are necessary to allow normal human con(cid:173)
`versation. Further, the quality of the received signal must be sufficiently high to pro(cid:173)
`vide, at a minimum, intelligibility.
`Circuit switching achieved its widespread, dominant position because it is well
`suited to the analog transmission of voice signals; in today's digital world, its ineffi(cid:173)
`ciencies are more apparent. However, despite the inefficiency, circuit switching will
`remain an attractive choice for both local-area and wide-area networking. One of
`its key strengths is that it is transparent. Once a circuit is established, it appears as
`a direct connection to the two attached stations; no special networking logic is
`needed at either point.
`
`8.3 SWITCHING CONCEPTS
`
`The technology of circuit switching is best approached by examining the operation
`of a single circuit-switched node. A network built around a single circuit-switching
`node consists of a collection of stations attached to a central switching unit. The cen(cid:173)
`tral switch establishes a dedicated path between any two devices that wish to com(cid:173)
`municate. Figure 8.4 depicts the major elements of such a one-node network. The
`dotted lines inside the switch symbolize the connections that are currently active.
`The heart of a modern system is a digital switch. The function of the digital
`switch is to provide a transparent signal path between any pair of attached devices.
`The path is transparent in that it appears to the attached pair of devices that there
`is a direct connection between them. Typically, the connection must allow full(cid:173)
`duplex transmission.
`The network-interface element represents the functions and hardware needed
`to connect digital devices, such as data processing devices and digital telephones, to
`
`Ex.1013
`APPLE INC. / Page 14 of 23
`
`

`

`CHAPTER9
`
`PACKET S"W"ITCHING
`
`8
`
`5
`
`9.1 Packet-Switching Principles
`9.2 Routing
`9.3 Congestion Control
`9.4 X.25
`9.5 Recommended Reading
`9.6 Problems
`Appendix 9A Least-Cost Algorithms
`
`Ex.1013
`APPLE INC. / Page 15 of 23
`
`

`

`254 CHAPTER 9 / PACKET SWITCHING
`
`A round 1970, research began on a new form of architecture for long-distance
`
`digital data communications: packet switching. Although the technology of
`packet switching has evolved substantially since that time, it is remarkable
`that (1) the basic technology of packet switching is fundamentally the same today
`as it was in the early-1970s networks, and (2) packet switching remains one of the
`few effective technologies for long-distance data communications.
`This chapter provides an overview of packet-switching technology. We will
`see that many of the advantages of packet switching (flexibility, resource sharing,
`robustness, responsiveness) come with a cost. The packet-switching network is a
`distributed collection of packet-switching nodes. Ideally, all packet-switching nodes
`would always know the state of the entire network. Unfortunately, because the
`nodes are distributed, there is always a time delay between a change in status in one
`portion of the network and the knowledge of that change elsewhere. Furthermore,
`there is overhead involved in communicating status information. As a result, a
`packet-switching network can never perform "perfectly," and so elaborate algo(cid:173)
`rithms are used to cope with the time delay and overhead penalties of network
`operation. These same issues will appear again when we discuss internetworking in
`Part IV.
`The chapter begins with an introduction to packet-switching network princi(cid:173)
`ples. Next, we look at the internal operation of these networks, introducing the con(cid:173)
`cepts of virtual circuits and datagrams. Following this, the key technologies of
`routing and congestion control are examined. The chapter concludes with an intro(cid:173)
`duction to X.25, which is the standard interface between an end system and a
`packet-switching network.
`
`PACKET-SWITCHING PRINCIPLES
`
`The long-haul circuit-switching telecommunications network was orginally de(cid:173)
`signed to handle voice traffic, and the majority of traffic on these networks con(cid:173)
`tinues to be voice. A key characteristic of circuit-switching networks is that
`resources within the network are dedicated to a particular call. For voice connec(cid:173)
`tions, the resulting circuit will enjoy a high percentage of utilization because, most
`of the time, one party or the other is talking. However, as the circuit-switching net(cid:173)
`work began to be used increasingly for data connections, two shortcomings became
`apparent:
`
`• In a typical user/host data connection (e.g., personal computer user logged on
`to a database server), much of the time the line is idle. Thus, with data con(cid:173)
`nections, a circuit-switching approach is inefficient.
`• In a circuit-switching network, the connection provides for transmission
`at constant data rate. Thus, each of the two devices that are connected
`must transmit and receive at the same data rate as the other; this limits the
`utility of the network in interconnecting a variety of host computers and
`terminals.
`
`
`
`Ex.1013
`APPLE INC. / Page 16 of 23
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 255
`To understand how packet switching addresses these problems, let us briefly
`summarize packet-switching operation. Data are transmitted in short packets. A
`typical upper bound on packet length is 1000 octets (bytes). If a source has a longer
`message to send, the message is broken up into a series of packets (Figure 9.1). Each
`packet contains a portion ( or all for a short message) of the user's data plus some
`control information. The control information, at a minimum, includes the informa(cid:173)
`tion that the network requires in order to be able to route the packet through the
`network and deliver it to the intended destination. At each node en route, the
`packet is received, stored briefly, and passed on to the next node.
`Let us return to Figure 8.1, but now assume that it depicts a simple packet(cid:173)
`switching network. Consider a packet to be sent from station A to station E. The
`packet will include control information that indicates that the intended destination
`is E. The packet is sent from A to node 4. Node 4 stores the packet, determines the
`next leg of the route (say 5), and queues the packet to go out on that link (the 4-5
`link). When the link is available, the packet is transmitted to node 5, which will for(cid:173)
`ward the packet to node 6, and finally to £ . This approach has a number of advan(cid:173)
`tages over circuit switching:
`
`• Line efficiency is greater, as a single node-to-node link can be dynamically
`shared by many packets over time. The packets are queued up and transmit(cid:173)
`ted as rapidly as possible over the link. By contrast, with circuit switching,
`time on a node-to-node link is preallocated using synchronous time-division
`multiplexing. Much of the time, such a link may be idle because a portion of
`its time is dedicated to a connection which is idle.
`• A packet-switching network can perform data-rate conversion. Two stations
`of different data rates can exchange packets because each connects to its node
`at its proper data rate.
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`User data
`
`A
`I\
`I \
`I
`\
`I
`\
`I
`\
`I
`\
`I
`\
`I
`\
`I
`\
`
`~ I (
`_
`
`___ . (
`
`.___.__I] _
`
`~
`\\
`\ \
`\ \
`\
`\
`\
`\
`\
`\
`
`\
`
`___.j
`
`'--v-'
`Control information
`(packet header)
`
`Packet
`
`FIGURE 9.1 Packets.
`
`\
`\
`
`\
`\
`
`\
`
`\
`\
`
`\
`\
`
`\
`
`\
`\
`\
`\
`\
`
`\1 _,1
`
`.___.__I
`
`
`
`Ex.1013
`APPLE INC. / Page 17 of 23
`
`

`

`256 CHAPTER 9 / PACKET SWITCHING
`
`• When traffic becomes heavy on a circuit-switching network, some calls are
`blocked; that is, the network refuses to accept additional connection requests
`until the load on the network decreases. On a packet-switching network,
`packets are still accepted, but delivery delay increases.
`• Priorities can be used. Thus, if a node has a number of packets queued for
`transmission, it can transmit the higher-priority packets first. These packets
`will therefore experience less delay than lower-priority packets.
`
`Switching Technique
`
`A station has a message to send through a packet-switching network that is of
`length greater than the maximum packet size. It therefore breaks the message up
`into packets and sends these packets, one at a time, to the network. A question
`arises as to how the network will handle this stream of packets as it attempts to
`route them through the network and deliver them to the intended destination; there
`are two approaches that are used in contemporary networks: datagram and virtual
`circuit.
`In the datagram approach, each packet is treated independently, with no ref(cid:173)
`erence to packets that have gone before. Let us consider the implication of this
`approach. Suppose that station A in Figure 8.1 has a three-packet message to send
`to E. It transmits the packets, 1-2-3, to node 4. On each packet, node 4 must make
`a routing decision. Packet 1 arrives for delivery to E. Node 4 could plausibly for(cid:173)
`ward this packet to either node 5 or node 7 as the next step in the route. In this case,
`node 4 determines that its queue of packets for node 5 is shorter than for node 7, so
`it queues the packet for node 5. Ditto for packet 2. But for packet 3, node 4 finds
`that its queue for node 7 is now shorter and so queues packet 3 for that node. So the
`packets, each with the same destination address, do not all follow the same route.
`As a result, it is possible that packet 3 will beat packet 2 to node 6. Thus, it is also
`possible that the packets will be delivered to E in a different sequence from the one
`in which they were sent. It is up to E to figure out how to reorder them. Also, it is
`possible for a packet to be destroyed in the network. For example, if a packet(cid:173)
`switching node crashes momentarily, all of its queued packets may be lost. If this
`were to happen to one of the packets in our example, node 6 has no way of know(cid:173)
`ing that one of the packets in the sequence of packets has been lost. Again, it is up
`to E to detect the loss of a packet and figure out how to recover it. In this technique,
`each packet, treated independently, is referred to as a datagram.
`In the virtual-circuit approach, a preplanned route is established before any
`packets are sent. For example, suppose that A has one or more messages to send to
`E. It first sends a special control packet, referred to as a Call-Request packet, to 4,
`requesting a logical connection to E. Node 4 decides to route the request and all
`subsequent packets to 5, which decides to route the request and all subsequent
`packets to 6, which finally delivers the Call-Request packet to E. If Eis prepared to
`accept the connection, it sends a Call-Accept packet to 6. This packet is passed back
`through nodes 5 and 4 to A. Stations A and E may now exch,mge data over the
`route that has been established. Because the route is fixed for the duration of the
`logical connection, it is somewhat similar to a circuit in a circuit-switching network,
`and is referred to as a virtual circuit. Each packet now contains a virtual-circuit
`identifier as well as data. Each node on the preestablished route knows where to
`
`Ex.1013
`APPLE INC. / Page 18 of 23
`
`

`

`9. 1 I PACKET-SWITCHING PRINCIPLES 257
`
`direct such packets; no routing decisions are required. Thus, every data packet from
`A intended for E traverses nodes 4, 5, and 6; every data packet from E intended for
`A traverses nodes 6, 5, and 4. Eventually, one of the stations terminates the con(cid:173)
`nection with a Clear-Request packet. At any time, each station can have more than
`one virtual circuit to any other station and can have virtual circuits to more than one
`station.
`So, the main characteristic of the virtual-circuit technique is that a route
`between stations is set up prior to data transfer. Note that this does not mean that
`this is a dedicated path, as in circuit switching. A packet is still buffered at each
`node, and queued for output over a line. The difference from the datagram
`approach is that, with virtual circuits, the node need not make a routing decision for
`each packet; it is made only once for all packets using that virtual circuit.
`If two stations wish to exchange data over an extended period of time, there
`are certain advantages to virtual circuits. First, the network may provide services
`related to the virtual circuit, including sequencing and error control. Sequencing
`refers to the fact that, because all packets follow the same route, they arrive in the
`original order. Error control is a service that assures not only that packets arrive in
`proper sequence, but that all packets arrive correctly. For example, if a packet in a
`sequence from node 4 to node 6 fails to arrive at node 6, or arrives with an error,
`node 6 can request a retransmission of that packet from node 4. Another advantage
`is that packets should transit the network more rapidly with a virtual circuit; it is not
`necessary to make a routing decision for each packet at each node.
`One advantage of the datagram approach is that the call se