FIFTH EDITION
`
`DATA AND
`(COMPUTER
`COMMUNICATIONS
`
`WILLIAM STALLINGS
`
`
`
`=<)
`
`PRENTICE HALL
`Upper SADDLE RIVER, NEW JERSEY 07458
`
`1
`
`SAMSUNG 1014
`
`SAMSUNG 1014
`
`1
`
`

`

`Library of Congress Cataloging-in-Publication Data
`Stallings, William.
`Data and computer communications / William Stallings. —Sth ed.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN(invalid) 0-02-415425-3
`1. Data transmission systems.
`TKS5105.S73
`1996
`004.6—dc20
`
`2. Computer networks.
`
`I. Title.
`96-24419
`CIP
`
`Publisher: Alan Apt
`Editor-in-Chief: Marcia Horton
`Production Manager: Bayani Mendoza de Leon
`Production Editor: Mona Pompili
`Managing Editor: Laura Steele
`Design Director: Amy Rosen
`
`Designer: Judy Matz-Coniglio
`Cover Designer: Tom Nery
`CoverIllustrator: Wendy Grossman
`Copy Editor: Chip Lee
`Manufacturing Buyer: DonnaSullivan
`Editorial Assistant: Shirley McGuire
`
`= © 1997 by Prentice-Hall, Inc.
`
`Simon & Schuster / A Viacom Company
`Upper Saddle River, New Jersey 07458
`
`Theauthor and publisherof this book have used their best efforts in preparing this book. These efforts
`include the development,research, and testing of the theories and programsto determine their
`effectiveness. The author and publishershall not beliable in any event for incidental or consequential
`damagesin connection with, or arising out of, the furnishing, performance,or use of these programs.
`
`All rights reserved. No part of this book may be reproduced, in any form or by any means, without
`permission in writing from the publisher.
`
`Printed in the United States of America
`
`10098765 432 1
`
`ISBN QO-O2-415425-3
`
`PRENTICE-HALL INTERNATIONAL (UK) LIMITED, London
`PRENTICE-HALL OF AUSTRALIA PTy. LIMITED, Sydney
`PRENTICE-HALL CANADA,INC., Toronto
`PRENTICE-HALL HISPANOAMERICANA,S.A., Mexico
`PRENTICE-HALL OF INDIA PRIVATE LIMITED, New Delhi
`PRENTICE-HALL OF JAPAN, INC., Tokyo
`SIMON & SCHUSTER ASIA PTE. LTD., Singapore
`EDITORA PRENTICE-HALL DO BRASIL, LrDA., Rio de Janeiro
`
`
`
`2
`
`

`

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

`

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

`

`CONTENTS XV
`
`PART TWO
`Wide-Area Networks 229
`
`CHAPTER 8
`CIRCUIT SWITCHING 229
`
`8.1
`8.2.
`8.3.
`8.4
`8.5
`8.6
`8.7.
`
`231
`
`230
`Switched Networks
`Circuit-Switching Networks
`Switching Concepts
`234
`Routing in Circuit-Switched Networks
`Control Signaling
`244
`Recommended Reading 252
`Problems
`252
`
`240
`
`CHAPTER 9
`PACKET SWITCHING 253
`
`253
`
`9.1
`Packet-Switching Principles
`9.22
`Routing
`264
`9.3
`Congestion Control
`94
`X25
`282
`9.5
`Recommended Reading
`9.6
`Problems
`291
`APPENDIX 9A Least-CostT ALGORITHMS
`
`278
`
`291
`
`296
`
`304
`
`CHAPTER 10
`FRAME RELAY 301
`
`302
`10.1. Background
`10.2
`Frame Relay Protocol Architecture
`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
`10.8
`Problems
`325
`
`325
`
`CHAPTER 1 1
`ASYNCHRONOUS TRANSFER MODE (ATM) 327
`11.1.
`Protocol Architecture
`328
`11.2 ATM Logical Connections
`113 ATMCells
`334
`11.4 Transmission of ATM Cells
`
`329
`
`338
`
`5
`
`

`

`XVi CONTENTS
`
`1L5
`11.6
`11.7
`11.8
`
`342
`ATM Adaptation Layer
`Traffic and Congestion Control
`Recommended Reading
`359
`Problems
`360
`
`347
`
`PART THREE
`Local Area Networks 363
`
`CHAPTER 12
`LAN TECHNOLOGY 363
`
`12.1
`12.2
`12.3
`12.4
`12.5
`12.6
`12.7
`
`364
`LAN Architecture
`Bus/Tree LANs
`337
`Ring LANs
`385
`Star LANs
`389
`393
`Wireless LANs
`Recommended Reading
`Problems
`399
`
`399
`
`CHAPTER 13
`LAN Systems 401
`
`402
`
`13.1
`13.2
`13.3
`13.4
`35
`13.6
`13.7
`13.8
`
`Ethernet and Fast Ethernet (CSMA/CD)
`Token Ring and FDDI
`413
`100VG-AnyLAN 427
`ATMLANs
`431
`Fibre Channel
`435
`Wireless LANs
`442
`Recommended Reading
`Problems
`448
`
`447
`
`APPENDIX 13A_ DiciTat SIGNAL ENCODING FOR LANs
`APPENDIX 13B PERFORMANCE IssuES
`458
`
`451
`
`CHAPTER 14
`BRIDGES 465
`
`14.1
`14.2
`14.3
`14.4
`14.5
`
`466
`Bridge Operation
`Routing with Bridges
`ATM LAN Emulation
`Recommended Reading
`Problems
`495
`
`470
`487
`495
`
`6
`
`

`

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

`

`XVili CONTENTS
`
`IPv4 and IPv6 Security
`18.5
`18.6 Recommended Reading
`18.8
`Problems
`665
`
`659
`664
`
`CHAPTER 1 9
`DISTRIBUTED APPLICATIONS 667
`
`668
`
`19.1. Abstract Syntax Notation One (ASN.1)
`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)
`19.6 Recommended Reading
`736
`19.7.
`Problems
`737
`
`719
`
`APPENDIX A
`ISDN AND BROADBAND ISDN_739
`
`Al Overview of ISDN 740
`A.2
`ISDN Channels
`747
`A.3 User Access
`750
`752
`A.4
`ISDN Protocols
`A.5
` BroadbandISDN 764
`A.6
`Recommended Reading
`A.7
`Problems
`768
`
`768
`
`APPENDIX B
`RFCs CITED IN THIS BOOK 771
`
`GLOSSARY 773
`
`REFERENCES 785
`
`INDEX 791
`
`8
`
`

`

`
`
`6.408 Wide-Area Networks
`
`CHAPTER 8
`
`
`
`CIRCUIT SWITCHING
`
` 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
`
`
`
`
`
`9
`
`

`

`230 CHAPTER 8 / CIRCUIT SWITCHING
`
`
`e the invention of the telephone,circuit switching has been the dominant
`nology for voice communications, and it will remain so well into he
`era. This chapter begins with an introduction to the concept of;
`switched communications network and then looks at the key characteristics of::
`
`circuit-switching network.
`
`
`Fortransmission of data' beyondalocal area, communicationis typically achievall
`by transmitting data from source to destination through a networkof intermediate
`switching nodes; this switched-network design is sometimes used to implement
`LANs and MANsaswell. The switching nodesare not concerned with the contenn
`of the data; rather, their purposeis to provide a switchingfacility that will move he
`data from node to node until they reach their destination. Figure 8.1 illustratesa
`simple network. The end devices that wish to communicate may bereferred toa
`stations. The stations may be computers, terminals, telephones, or other comm ni-
`cating devices. We will refer to the switching devices whose purposeis 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.
`:
`
`
`
`LEGEND
`
`
`LE] = Endstation
`4
`© = Communication network node
`j
`FIGURE 8.1 Simple switching network.
`"Weuse this term here in a very general sense to include voice, image, and video, as well as ord ing
`data(e.g., numerical, text).
`
`
`
`10
`
`10
`
`

`

`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 nodeto node.
`For example, in Figure 8.1, data from station A intendedfor station F are sent to
`node 4. They may then be routed via nodes 5 and 6 or nodes 7 and6 tothe desti-
`nation. Several observationsare 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 oneor moresta-
`tions attached as well; in addition to their switching functions, such nodes
`accept data from anddeliver data to the attachedstations.
`2. Node-node links are usually multiplexed, using either frequency-division
`multiplexing (FDM)or time-division multiplexing (TDM).
`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 onepossible path through the networkfor eachpair ofstations; this
`enhancesthereliability of the network.
`
`3
`
`Two quite different technologies are used in wide-area switched networks:cir-
`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 sourceto des-
`tination. In this chapter, we look atthe 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 and11, respectively.
`
`
`
`Communication via circuit switching implies that there is a dedicated communica-
`tion path betweentwostations. That path is a connected sequence of links between
`network nodes. On each physicallink, a logical channel is dedicated to the connec-
`tion. Communication via circuit switching involves three phases, which can be
`explained with reference to Figure 8.1.
`
`1. 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 EF. Typically, the link
`from A to4is a dedicated line, so that part of the connection already exists.
`Node 4 mustfind the next leg in a route leading to node 6, Based on routing
`information and measuresof availability and, perhaps,cost, node 4 selects the
`link to node5, allocates a free channel (using frequency-division multiplexing,
`FDM,ortime-division multiplexing, TDM) onthatlink and sends a message
`requesting connectionto E.So far, a dedicated path has been established from
`A through4 to 5. Because a numberofstations 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
`
`11
`
`11
`
`

`

`232 CHAPTER 8 / CIRCUIT SWITCHING
`completes the connectionto E. In completing the connection,a test is made to
`determineif E is busy or is prepared to accept the connection.
`2. Data transfer. Information can now be transmitted from A through the net-
`work to E. The data maybe analog ordigital, 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. Thepath is A-4 link, internal switching through 4, 4-5 channel,inter-
`nal switching through 5, 5-6 channel, and internal switching through 6, 6-E
`link. Generally, the connectionis full-duplex.
`3. Circuit disconnect. After some period of data transfer, the connectionis ter-
`minated, usually by the action of one of the two stations. Signals must be prop-
`agated to nodes4,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 makethese allo-
`cations and to devise a route through the network.
`Circuit switching can be ratherinefficient. Channel capacity is dedicated for
`the duration of a connection, evenif no data are being transferred. For a voice con-
`nection,utilization maybe rather high, butit still does not approach 100 percent.
`For a terminal-to-computer connection, the capacity may be idle during mostof 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 transparentto the users. Informationis transmitted ata fixed datarate
`with no delay other than that required for propagation through the transmission
`links. The delay at each nodeis negligible.
`Circuit switching was developed to handle voice traffic but is now also used
`for data traffic. The best-known exampleof a circuit-switching network is the pub-
`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 andis gradually being converted to a digital
`network. Another well-known application ofcircuit switching is the private branch —
`exchange (PBX), used to interconnect telephones within a building or office. Cir-
`cuit switchingis also used in private networks—corporationsor otherlarge organi-
`zations interconnecting their various sites; these usually consist of PBX systemsat
`each site interconnected by dedicated, leased lines obtained from one of the carri-
`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
`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
`phones, but the percentage of data traffic increases year by year.
`
`—
`—
`
`—
`
`|
`
`12
`
`12
`
`

`

`8.2 / CIRCUIT-SWITCHING NETWORKS 233
`
`Long-distance
`office
`
`Long-distance
`
`office
`
`S|OO00000000bOO
`==10000004000
`
`
`
`
`Subscriber loop
`
`
`Connecting trunk
`
`Intercity trunk
`
`End office
`
`FIGURE 8.2 Public circuit-switching network.
`
`° Local loop: Thelink 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 loopis 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 thousandsofsubscribersin a localized area. There are over
`19,000 endoffices in the UnitedStates,soit 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 10® links. Rather, intermediate switching nodesare used.
`° Trunks: The branches between exchanges. Trunks carry multiple voice-
`frequency circuits using either FDM or synchronous TDM. Earlier, these
`were referred to ascarrier systems.
`
`Subscribers connect directly to an endoffice, which switches traffic between
`subscribers and betweena subscriber and other exchanges. The other exchangesare
`responsible for routing and switching traffic between endoffices; this distinction is
`shownin 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-
`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 connectionis
`established betweenlines a andb by simply setting up the connection through the
`end office. The connection between c and d is more complex. In c’s endoffice, a
`connection is established between line c and one channel on a TDM trunk to the
`intermediate switch. In the intermediate switch, that channelis connected to a chan-
`nel on a TDMtrunk to d’s endoffice. In that end office, the channel is connected
`to line d.
`Circuit-switching technology has been driven by those applications that han-
`dle voice traffic. One of the key requirements for voicetraffic is that there must be
`
`13
`
`13
`
`

`

`
`
`234 CHAPTER 8 / CIRCUIT SWITCHING
`
` End
`office
`
`
`
`
`
`
`.
`1 Intermediate
`exchange
`
`FIGURE8.3 Circuit establishment.
`
`virtually no transmission delay and certainly no variation in delay. A constantsig-
`nal transmission rate must be maintained, as transmission and reception occur at
`the samesignal rate. These requirements are necessary to allow normal humancon-
`versation. Further, the quality of the received signal must be sufficiently high to pro-
`vide, at a minimum,intelligibility.
`Circuit switching achieved its widespread, dominant position becauseit is well
`suited to the analog transmission of voice signals; in today’s digital world,its ineffi-
`ciencies are more apparent. However,despite the inefficiency, circuit switching will
`remain an attractive choice for both local-area and wide-area networking. Oneof
`its key strengthsis that it is transparent. Once a circuit is established, it appears asa
`a direct connection to the two attached stations; no special networking logic is
`neededat either point.
`
`8.3
`
`SWITCHING CONCEPTS
`
`4
`
`The technologyof circuit switching is best approached by examining the operation
`of a single circuit-switched node. A network built arounda single circuit-switching
`nodeconsists of a collection of stations attached to a central switching unit. The cen-
`tral switch establishes a dedicated path between any two devices that wish to com
`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 modernsystem is a digital switch. The function of the digital
`switch is to providea transparentsignal path between any pair of attached devices.
`Thepath is transparentin that it appears to the attached pair of devices that thet :
`
`is a direct connection between them. Typically, the connection must allow full-
`duplex transmission.
`:
`
`The network-interface element represents the functions and hardware need
` ctif
`to connect digital devices, such as data processing devices and digital telephones,
`
`14
`
`14
`
`

`

`cavern
`
`PACKET SWITCHING
`
`
`
`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
`
`15
`
`

`

`254 CHAPTER 9 / PACKET SWITCHING
`
`m round 1970, research began on a new form ofarchitecture for long-distance
`
`digital data communications: packet switching. Although the technology of
`> = yacket 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 remainsoneofthe
`few effective technologies for long-distance data communications.
`This chapter provides an overview of packet-switching technology. Wewill
`see that many of the advantages of packet switching (flexibility, resource sharing,
`robustness, responsiveness) come with a cost. The packet-switching networkis a
`distributed collection of packet-switching nodes. Ideally,all packet-switching nodes
`would always know the state of the entire network. Unfortunately, because the
`nodesare distributed, there is always a time delay between a changein status in one
`portion of the network and the knowledge of that change elsewhere. Furthermore,
`there is overhead involved in communicating status information. Asa result, a
`packet-switching network can never perform “perfectly,” and so elaborate algo-
`rithms are used to cope with the time delay and overhead penalties of network
`operation. These sameissues will appear again when wediscuss internetworking in
`Part IV.
`The chapter begins with an introduction to packet-switching network princi-
`ples. Next, we lookat the internal operation of these networks, introducing the con-
`cepts of virtual circuits and datagrams. Following this, the key technologies of
`routing and congestion control are examined. The chapter concludes with an intro-
`duction to X.25, which is the standard interface between an end system and a
`packet-switching network.
`
`
`The long-haul circuit-switching telecommunications network was orginally de-
`signed to handle voice traffic, and the majority of traffic on these networks con-
`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-
`tions, the resulting circuit will enjoy a high percentage ofutilization because, most
`of the time, oneparty orthe otheris talking. However,as the circuit-switching neta
`work beganto be usedincreasingly for data connections, two shortcomings became
`apparent:
`
`e Ina typical user/host data connection (e.g., personal computer user logged on
`to a database server), much of the timethe line is idle. Thus, with data con-—
`nections, a circuit-switching approachisinefficient.
`|
`e 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.
`
`
`
`16
`
`16
`
`

`

`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 packetlength is 1000 octets (bytes). If a source has a longer
`messageto send,the message is broken upintoa 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-
`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
`packetis 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-
`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 packetis sent from A to node 4. Node 4 stores the packet, determines the
`nextleg of the route (say 5), and queuesthe packet to go outon that link (the 4-5
`link). When the link is available, the packet is transmitted to node 5, whichwill for-
`ward the packet to node6, and finally to E. This approach has a numberof advan-
`tages overcircuit switching:
`
`e Line efficiency is greater, as a single node-to-node link can be dynamically
`shared by manypackets over time. The packets are queued up and transmit-
`ted as rapidly as possible over the link. By contrast, with circuit switching,
`time on a node-to-nodelink is preallocated using synchronous time-division
`multiplexing. Muchofthe time, such a link may be idle because a portion of
`its time is dedicated to a connection whichisidle.
`e A packet-switching network can perform data-rate conversion. Twostations
`of different data rates can exchange packets because each connectsto its node
`at its proper datarate.
`
`!
`
`\
`
`\\
`
`\
`
`!
`
`4
`
`j
`
`hy
`
`Control information
`(packet header)
`SSS
`
`Packet
`
`FIGURE 9.1 Packets.
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`.
`
`17
`
`
`
`17
`
`

`

`256 CHAPTER 9 / PACKET SWITCHING
`
`e Whentraffic becomes heavy ona circuit-switching network, somecalls are
`blocked;that is, the network refuses to accept additional connection requests
`until the load on the network decreases. On a packet-switching network,
`packetsarestill accepted, but delivery delay increases.
`e 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 thatis of
`length greater than the maximum packetsize. 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 networkanddeliver them to the intendeddestination; there
`are two approachesthat are used in contemporary networks: datagram andvirtual
`circuit.
`In the datagram approach, each packetis treated independently,with noref-
`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-
`wardthis packetto either node 5 or node7 as the nextstepin the route. In this case,
`node 4 determinesthat its queue of packets for node 5 is shorter than for node7, 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 packet3 for that node. So the
`packets, each with the samedestination address, do notall follow the same route.
`Asa 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 weresent. 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-
`switching node crashes momentarily, all of its queued packets may belost. If this
`were to happen to one of the packets in our example, node 6 has no way of know-
`ing that one of the packets in the sequence of packets has beenlost. Again,it is up
`to E to detect the loss of a packet andfigure out how to recoverit. 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 t0_
`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 andall
`subsequent packets to 5, which decides to route the request and all subsequent
`packets to 6, whichfinally delivers the Call-Request packetto E. If E is 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 exchangedata over the
`route that has been established. Because the route is fixed for the duration of the
`logical connection,it is somewhatsimilarto 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
`
`18
`
`18
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 257
`
`direct such packets; no routing decisions are required. Thus, every data packet from
`A intendedfor E traverses nodes4, 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-
`nection with a Clear-Request packet. At any time, each station can have more than
`onevirtual circuit to any otherstation and can have virtualcircuits to more than one
`station.
`So, the main characteristic of the virtual-circuit technique is that a route
`betweenstations is set up prior to data transfer. Note that this does not meanthat
`this is a dedicated path, as in circuit switching. A packetis still buffered at each
`node, and queued for output over a line. The difference from the datagram
`approachis that, with virtualcircuits, the node need not make a routing decision for
`each packet; it is made only onceforall packets using thatvirtual circuit.
`If two stations wish to exchange data over an extended period of time, there
`are certain advantages to virtualcircuits. 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 controlis a service that assures not only that packets arrive in
`proper sequence,butthatall packets arrive correctly. For example,if a packet in a
`sequence from node 4 to node6fails to arrive at node6, or arrives with an error,
`node6 can request a retransmission ofthat packet from node 4, Another advantage
`is that packets should transit the network morerapidly with a virtualcircuit;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 setup phase is
`avoided. Thus,if a station wishes to send only oneora few packets, datagram deliv-
`ery will be quicker. Another advantage of the datagram service is that, becauseit is
`more primitive, it is more flexible. For example, if congestion develops in one part
`of the network, incoming datagrams can be routed away from the congestion. With
`the use ofvirtual circuits, packets follow a predefined route, andit is thus more dif-
`ficult for the network to adapt to congestion. A third advantage is that datagram
`delivery is inherently morereliable. With the use of virtual circuits, if a node fails,
`all virtual circuits that pass through that nodeare lost. With datagram delivery,if a
`node fails, subsequent packets mayfind an alternate route that bypasses that node.
`Most currently available packet-switching networks make use of virtualcir-
`cuits for their internal operation. To some degree, this reflects a historical motiva-
`tion to provide a network that presentsa service as reliable (in terms of sequencing)
`as a circuit-switching network. There are, however, several providers of private
`packet-switching networks that make use of datagram operation. From the user’s
`point of view, there should be verylittle difference in the external behavior based
`on the use of datagramsorvirtualcircuits. If a manageris faced with a choice, other
`factors such as cost and performance should probably take precedence over
`whether the internal network operation is datagram or virtual-circuit. Finally, it
`should be noted that a datagram-style of operation is common in internetworks
`(discussed in Part IV).
`
`Packet Size
`
`One importantdesign issue is the packet size to be used in the network. Thereis a
`significant relationship between packet size and transmission time,as illustrated in
`
`19
`
`19
`
`

`

`258 CHAPTER 9 / PACKET SWITCHING 2-packet message
`
`10-packet message
`
`1-packet message
`
`FIGURE 9.2 Effect of packet size on transmission time.
`
`Figure 9.2. In this example, it is assumed thatthereis a virtual circuit from station —
`X through nodesa and b to station Y. The message to be sent comprises 30 octets,
`|
`and each packet contains 3 octets of control information, which is placed at the |
`
`20
`
`20
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 259
`
`beginning of each packetandis referredto as a header.If the entire message is sent
`as a single packet of 33 octets (3 octe