Computer Networks
`Third Edition
`
`Andrew S. Tanenbaum
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`For book andbookstore information
`
`http://www.prenhall.com
`
`Prentice Hall PTR
`Upper Saddle River, New Jersey 07458
`
`1
`
`SAMSUNG 1012
`
`SAMSUNG 1012
`
`1
`
`

`

`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, Andrew S. 1944-.
`Computer networks / Andrew S. Tanenbaum.-- 3rd ed.
`.
`cm.
`
`Includes bibliographical references and index.
`ISBN 0-13-349945-6
`1.Computer networks.
`TKS5105.5.T36 1996
`004.6--dce20
`
`I. Title.
`
`96-4121
`CIP
`
`Editorial/production manager: Camille Trentacoste
`Interior design and composition: Andrew S. Tanenbaum
`Coverdesign director: Jerry Votta
`Cover designer: Don Martinetti, DM Graphics, Inc.
`Cover concept: Andrew S. Tanenbaum, from an idea by Marilyn Tremaine
`Interior graphics: Hadel Studio
`Manufacturing manager: Alexis R. Heydt
`Acquisitions editor: Mary Franz
`Editorial Assistant: Noreen Regina
`
`
`
`© 1996 by Prentice Hall PTR
`Prentice-Hall, Inc.
`A Simon & Schuster Company
`Upper Saddle River, New Jersey 07458
`
`The publisher offers discounts on this book when ordered in bulk quantities. For more information,
`contact:
`Corporate Sales Department, Prentice Hall PTR, One Lake Street, Upper Saddle River, NJ 07458.
`Phone: (800) 382-3419; Fax: (201) 236-7141. E-mail: corpsales@prenhall.com
`
`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.
`
`All product names mentionedherein are the trademarksoftheir respective owners.
`
`Printed in the United States of America
`100
`9
`8 765 43 2
`«41
`
`ISBN 0-13-349945-6
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall CanadaInc., Toronto
`Prentice-Hall Hispanoamericana, $.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, Ltda., Rio de Janeiro
`
`
`
`2
`
`

`

`XV
`
`1
`
`CONTENTS
`
`PREFACE
`
`INTRODUCTION
`
`1.1 USES OF COMPUTER NETWORKS 3
`1.1.1 Networks for Companies
`3
`1.1.2 Networks for People 4
`1.1.3 Social Issues 6
`
`1.2
`
`L3
`
`1.4
`
`LS
`
`NETWORK HARDWARE 7
`1.2.1 Local Area Networks
`9
`1.2.2 Metropolitan Area Networks
`1.2.3. Wide Area Networks
`11
`1.2.4 Wireless Networks
`1.2.5 Internetworks
`16
`
`13
`
`10
`
`NETWORK SOFTWARE 16
`1.3.1 Protocol Hierarchies
`17
`1.3.2 Design Issues for the Layers 21
`1.3.3.
`Interfaces and Services 22
`1.3.4 Connection-Oriented and Connectionless Services 23
`1.3.5 Service Primitives 25
`1.3.6 The Relationship of Services to Protocols 27
`
`REFERENCE MODELS 28
`1.4.1 The OSI Reference Model 28
`1.4.2 The TCP/IP Reference Model 35
`1.4.3. A Comparison of the OSI and TCP Reference Models 38
`1.4.4 A Critique of the OSI Model and Protocols 40
`1.4.5 A Critique of the TCP/IP Reference Model 43
`
`EXAMPLE NETWORKS 44
`1.5.1 Novell Netware 45
`1.5.2. The ARPANET 47
`1.5.3. NSFNET 50
`1.5.4 The Internet 52
`1.5.5 Gigabit Testbeds 54
`
`vi
`
`
`
`3
`
`

`

`CONTENTS
`
`Vii
`
`1.6
`
`EXAMPLE DATA COMMUNICATION SERVICES 56
`1.6.1 SMDS—Switched Multimegabit Data Service 57
`1.6.2 X.25 Networks 59
`1.6.3 Frame Relay 60
`1.6.4 Broadband ISDN and ATM 61
`1.6.5 Comparison of Services 66
`
`1.7
`
`NETWORK STANDARDIZATION 66
`1.7.1. Who’s Who in the Telecommunications World 67
`1.7.2. Who’s Whoin the International Standards World 69
`1.7.3. Who’s Whoin the Internet Standards World 70
`
`1.8
`
`OUTLINE OF THE REST OF THE BOOK 72
`
`1.9,
`
`SUMMARY 73
`
`THE PHYSICAL LAYER
`
`77
`
`2.1
`
`2.2
`
`2.3
`
`2.4
`
`THE THEORETICAL BASIS FOR DATA COMMUNICATION 77
`2.1.1 Fourier Analysis 78
`2.1.2 Bandwidth-Limited Signals 78
`2.1.3. The Maximum Data Rate of a Channel
`
`81
`
`TRANSMISSION MEDIA 82
`2.2.1 Magnetic Media 82
`2.2.2 Twisted Pair 83
`2.2.3 Baseband Coaxial Cable 84
`2.2.4 Broadband Coaxial Cable 85
`2.2.5 Fiber Optics
`87
`
`WIRELESS TRANSMISSION 94
`2.3.1 The Electromagnetic Spectrum 94
`2.3.2 Radio Transmission 97
`2.3.3. Microwave Transmission 98
`2.3.4 Infrared and Millimeter Waves
`2.3.5 Lightwave Transmission 100
`
`100
`
`THE TELEPHONE SYSTEM 102
`2.4.1 Structure of the Telephone System 103
`2.4.2 The Politics of Telephones
`106
`2.4.3 The Local Loop 108
`2.4.4 Trunks and Multiplexing 118
`2.4.5 Switching 130
`
`
`
`4
`
`

`

`viii
`
`CONTENTS
`
`2
`
`2.6
`
`2.1
`
`NARROWBAND ISDN 139
`2.5.1
`ISDN Services
`140
`2.5.2 ISDN System Architecture
`2.5.3. The ISDN Interface
`142
`2.5.4 Perspective on N-ISDN 143
`
`140
`
`BROADBAND ISDN AND ATM 144
`2.6.1 Virtual Circuits versus Circuit Switching 145
`2.6.2 Transmission in ATM Networks
`146
`2.6.3 ATM Switches
`147
`
`CELLULAR RADIO 155
`2.7.1 Paging Systems
`155
`157
`2.7.2 Cordless Telephones
`157
`2.7.3 Analog Cellular Telephones
`162
`2.7.4 Digital Cellular Telephones
`2.7.5 Personal Communications Services
`
`162
`
`2.8
`
`COMMUNICATION SATELLITES 163
`2.8.1 GeosynchronousSatellites
`164
`2.8.2 Low-Orbit Satellites
`167
`2.8.3 Satellites versus Fiber 168
`
`29
`
`SUMMARY 170
`
`THE DATA LINK LAYER
`
`175
`
`3.1
`
`DATA LINK LAYER DESIGN ISSUES 176
`3.1.1 Services Provided to the Network Layer 176
`3.1.2 Framing 179
`3.1.3. Error Control
`3.1.4 Flow Control
`
`182
`183
`
`
`
`32 ERROR DETECTION AND CORRECTION§183
`3.2.1 Error-Correcting Codes
`184
`3.2.2 Error-Detecting Codes
`186
`
`5.3
`
`ELEMENTARY DATA LINK PROTOCOLS 190
`3.3.1 An Unrestricted Simplex Protocol
`195
`3.3.2 A Simplex Stop-and-Wait Protocol
`195
`3.3.3 A Simplex Protocol for a Noisy Channel
`
`197
`
`
`
`5
`
`

`

`CONTENTS
`
`ix
`
`3.4
`
`a
`
`3.6
`
`SLIDING WINDOW PROTOCOLS 202
`3.4.1 A One Bit Sliding Window Protocol 206
`3.4.2 A Protocol Using Go Back n 207
`3.4.3 A Protocol Using Selective Repeat 213
`
`PROTOCOL SPECIFICATION AND VERIFICATION 219
`3.5.1 Finite State Machine Models 219
`3.5.2 Petri Net Models 223
`
`EXAMPLE DATA LINK PROTOCOLS 225
`3.6.1 HDLC—High-level Data Link Control 225
`3.6.2 The Data Link Layerin the Internet 229
`3.6.3 The Data Link Layer in ATM 235
`
`Orhs
`
`SUMMARY 239
`
`THE MEDIUM ACCESS SUBLAYER
`
`243
`
`4.1
`
`4.2
`
`4.3
`
`THE CHANNEL ALLOCATION PROBLEM 244
`4.1.1 Static Channel Allocation in LANs and MANs 244
`4.1.2 Dynamic Channel Allocation in LANs and MANs_ 245
`
`MULTIPLE ACCESS PROTOCOLS 246
`4.2.1 ALOHA 246
`4.2.2 Carrier Sense Multiple Access Protocols 250
`4.2.3, Collision-Free Protocols 254
`4.2.4 Limited-Contention Protocols 256
`4.2.5 Wavelength Division Multiple Access Protocols 260
`4.2.6 Wireless LAN Protocols 262
`4.2.7 Digital Cellular Radio 266
`
`IEEE STANDARD 802 FOR LANS AND MANS 275
`4.3.1 TEEE Standard 802.3 and Ethernet 276
`4.3.2 JEEE Standard 802.4: Token Bus 287
`4.3.3 IEEE Standard 802.5: Token Ring 292
`4.3.4 Comparison of 802.3, 802.4, and 802.5 299
`4.3.5 IEEE Standard 802.6: Distributed Queue Dual Bus 301
`4.3.6 IEEE Standard 802.2: Logical Link Control 302
`
`
`
`6
`
`

`

`CONTENTS
`
`4.4
`
`BRIDGES 304
`4.4.1 Bridges from 802.x to 802.y 307
`4.4.2 Transparent Bridges 310
`4.4.3 Source Routing Bridges 314
`4.4.4 Comparison of 802 Bridges 316
`4.4.5 Remote Bridges 317
`
`4.5
`
`HIGH-SPEED LANS 318
`4.5.1 FDDI 319
`
`4.5.2 Fast Ethernet 322
`4.5.3 HIPPI—High-PerformanceParallel Interface 325
`4.5.4 Fibre Channel 326
`
`4.6
`
`SATELLITE NETWORKS 327
`4.6.1 Polling 328
`4.6.2 ALOHA 329
`4.6.3 FDM 330
`
`4.6.4 TDM 330
`
`4.6.5 CDMA 333
`
`4.7
`
`SUMMARY 333
`
`THE NETWORK LAYER
`
`339
`
`5.1
`
`a2
`
`NETWORK LAYER DESIGN ISSUES 339
`5.1.1 Services Provided to the Transport Layer 340
`5.1.2 Internal Organization of the Network Layer 342
`5.1.3. Comparison of Virtual Circitiit and Datagram Subnets 344
`
`ROUTING ALGORITHMS 345
`5.2.1 The Optimality Principle 347
`5.2.2 Shortest Path Routing 349
`5.2.3 Flooding 351
`5.2.4 Flow-Based Routing 353
`5.2.5 Distance Vector Routing 355
`5.2.6 Link State Routing 359
`5.2.7 Hierarchical Routing 365
`5.2.8 Routing for Mobile Hosts 367
`5.2.9 Broadcast Routing 370
`5.2.10 Multicast Routing 372
`
`
`
`7
`
`

`

`CONTENTS
`
`5.3 CONGESTION CONTROL ALGORITHMS 374
`5.3.1 General Principles of Congestion Control 376
`5.3.2 Congestion Prevention Policies 378
`5.3.3 Traffic Shaping 379
`5.3.4 Flow Specifications 384
`5.3.5 Congestion Control in Virtual Circuit Subnets 386
`5.3.6 Choke Packets 387
`5.3.7 Load Shedding 390
`5.3.8 Jitter Control 392
`5.3.9 Congestion Control for Multicasting 393
`
`5.4 INTERNETWORKING 396
`5.4.1 How Networks Differ 399
`5.4.2 Concatenated Virtual Circuits 401
`5.4.3 Connectionless Internetworking 402
`5.4.4 Tunneling 404
`5.4.5 Internetwork Routing 405
`5.4.6 Fragmentation 406
`5.4.7 Firewalls 410
`
`5.5 THE NETWORK LAYER IN THE INTERNET 412
`5.5.1 The IP Protocol 413
`5.5.2 IP Addresses 416
`5.5.3 Subnets 417
`5.5.4 Internet Control Protocols 419
`5.5.5 The Interior Gateway Routing Protocol: OSPF 424
`5.5.6 The Exterior Gateway Routing Protocol: BGP 429
`5.5.7 Internet Multicasting 431
`5.5.8 Mobile IP 432
`5.5.9 CIDR—Classless InterDomain Routing 434
`5.5.10 IPv6 437
`
`5.6 THE NETWORK LAYER IN ATM NETWORKS 449
`5.6.1 Cell Formats 450
`5.6.2 Connection Setup 452
`5.6.3 Routing and Switching 455
`5.6.4 Service Categories 458
`5.6.5 Quality of Service 460
`5.6.6 Traffic Shaping and Policing 463
`5.6.7 Congestion Control 467
`5.6.8 ATMLANs 471
`
`5.7 SUMMARY 473
`
`
`
`8
`
`

`

`xii
`
`6
`
`CONTENTS
`
`THE TRANSPORT LAYER
`
`479
`
`6.1
`
`6.2
`
`6.3
`
`6.4
`
`6.5
`
`THE TRANSPORT SERVICE 479
`6.1.1 Services Provided to the Upper Layers 479
`6.1.2 Quality of Service 481
`6.1.3. Transport Service Primitives 483
`
`ELEMENTS OF TRANSPORT PROTOCOLS 488
`6.2.1 Addressing 489
`6.2.2 Establishing a Connection 493
`6.2.3. Releasing a Connection 498
`6.2.4 Flow Control and Buffering 502
`6.2.5 Multiplexing 506
`6.2.6 Crash Recovery 508
`
`A SIMPLE TRANSPORT PROTOCOL 510
`6.3.1 The Example Service Primitives 510
`6.3.2 The Example Transport Entity 512
`6.3.3. The Example as a Finite State Machine 519
`
`THE INTERNET TRANSPORT PROTOCOLS (TCP AND UDP) 521
`6.4.1 The TCP Service Model 523
`6.4.2 The TCP Protocol 524
`6.4.3 The TCP Segment Header 526
`6.4.4 TCP Connection Management 529
`6.4.5 TCP Transmission Policy 533
`6.4.6 TCP Congestion Control 536
`6.4.7 TCP Timer Management 539
`6.4.8 UDP 542
`6.4.9 Wireless TCP and UDP 543
`
`THE ATM AAL LAYER PROTOCOLS 545
`6.5.1 Structure of the ATM Adaptation Layer 546
`6.5.2 AAL 1 547
`6.5.3 AAL2 549
`6.5.4 AAL 3/4 550
`6.5.5 AAL5 552
`6.5.6 Comparison of AAL Protocols 554
`6.5.7 SSCOP—Service Specific Connection-Oriented Protocol 555
`
`6.6
`
`PERFORMANCEISSUES 555
`6.6.1 Performance Problems in Computer Networks 556
`6.6.2 Measuring Network Performance 559
`
`
`
`9
`
`

`

`CONTENTS
`
`xiii
`
`6.6.3 System Design for Better Performance 561
`6.6.4 Fast TPDU Processing 565
`6.6.5 Protocols for Gigabit Networks 568
`
`6.7
`
`SUMMARY 572
`
`THE APPLICATION LAYER
`
`o77
`
`al
`
`7.2
`
`Te
`
`7.4
`
`NETWORK SECURITY 577
`7.1.1 Traditional Cryptography 580
`7.1.2 Two Fundamental Cryptographic Principles 585
`7.1.3 Secret-Key Algorithms 587
`7.1.4 Public-Key Algorithms 597
`7.1.5 Authentication Protocols 601
`7.1.6 Digital Signatures 613
`7.1.7. Social Issues 620
`
`DNS—DOMAIN NAME SYSTEM 622
`7.2.1 The DNS Name Space 622
`7.2.2. Resource Records 624
`7.2.3, Name Servers 628
`
`SNMP—SIMPLE NETWORK MANAGEMENT PROTOCOL 630
`7.3.1. The SNMP Model 631
`7.3.2. ASN.1—Abstract Syntax Notation 1 633
`7.3.3. SMI—Structure of ManagementInformation 639
`7.3.4 The MIB—ManagementInformation Base 641
`7.3.5 The SNMP Protocol 642
`
`ELECTRONIC MAIL 643
`7.4.1 Architecture and Services 645
`7.4.2 The User Agent 646
`7.4.3, Message Formats 650
`7.4.4 Message Transfer 657
`7.4.5 Email Privacy 663
`
`7.5
`
`USENET NEWS 669
`7.5.1. The User View of USENET 670
`7.5.2 How USENETis Implemented 675
`
`
`
`10
`
`10
`
`

`

`Xiv
`
`CONTENTS
`
`7.6 THE WORLD WIDE WEB 681
`7.6.1 The Client Side 682
`7.6.2 The Server Side 685
`7.6.3. Writing a Web Page in HTML 691
`7.6.4 Java 706
`7.6.5 Locating Information on the Web 720
`
`7.7 MULTIMEDIA 723
`7.7.1. Audio 724
`7.7.2 Video 727
`7.7.3 Data Compression 730
`7.7.4 Video on Demand 744
`7.7.5 MBone—Multicast Backbone 756
`
`7.8 SUMMARY 760
`
`READING LIST AND BIBLIOGRAPHY
`
`767
`
`8.1
`
`SUGGESTIONS FOR FURTHER READING 767
`8.1.1 Introduction and General Works 768
`8.1.2 The Physical Layer 769
`8.1.3 The Data Link Layer 770
`8.1.4 The Medium Access Control Sublayer 770
`8.1.5 The Network Layer 771
`8.1.6 The Transport Layer 772
`8.1.7. The Application Layer 772
`
`8.2 ALPHABETICAL BIBLIOGRAPHY 775
`
`INDEX 795
`
`11
`
`
`
`11
`
`

`

`102
`
`THE PHYSICAL LAYER
`
`CHAP. 2
`
`2.4. THE TELEPHONE SYSTEM
`
`When two computers owned by the same company or organization and
`located close to each other need to communicate, it is often easiest just to run a
`cable between them. LANs work this way. However, when the distances are
`large, or there are many computers, or the cables would have to pass through a
`public road or other public right of way, the costs of running private cables are
`usually prohibitive. Furthermore, in just about every country in the world, string-
`ing private transmission lines across (or underneath) public property is also ille-
`gal. Consequently, the network designers must rely upon the existing telecom-
`munication facilities.
`These facilities, especially the PSTN, (Public Switched Telephone Net-
`work), were usually designed many years ago, with a completely different goal in
`mind: transmitting the human voice in a more or less recognizable form. Their
`suitability for use in computer-computer communication is often marginalatbest,
`but the situation is rapidly changing with the introduction of fiber optics and digi-
`tal technology.
`In any event, the telephone system is so tightly intertwined with
`(wide area) computer networks, thatit is worth devoting considerable time study-
`ingit.
`To see the order of magnitude of the problem, let us make a rough butillustra-
`tive comparison of the properties of a typical computer-computer connection via a
`local cable and via a dial-up telephone line. A cable running between two com-
`puters can transfer data at memory speeds, typically 10’ to 10° bps. The error
`rate is usually so low that it is hard to measure, but one error per day would be
`considered poor at most
`installations. One error per day at these speeds is
`equivalent to one error per 10'* or 10" bits sent.
`In contrast, a dial-up line has a maximum data rate on the order of 10* bps
`and an errorrate of roughly 1 per 10° bits sent, varying somewhatwith the age of
`the telephone switching equipment involved. The combinedbit rate times error
`rate performance of a local cable is thus 11 orders of magnitude better than a
`voice-grade telephone line. To make an analogyin the field of transportation, the
`ratio of the cost of the entire Apollo project, which landed men on the moonto the
`cost of a bus ride downtownis about 11 orders of magnitude (in 1965 dollars: 40
`billion to 0.40).
`The trouble, of course, is that computer systems designers are used to working
`with computer systems, and when suddenly confronted with another system
`whose performance (from their point of view) is 11 orders of magnitude worse,it
`is not surprising that much time and effort have been devoted to trying to figure
`out how to use it efficiently. On the other hand, the telephone companies have
`made massive strides in the past decade in upgrading equipment and improving
`service in certain areas.
`In the following sections we will describe the telephone
`system and show whatit used to be and whereit is going. For additional informa-
`tion about the innards of the telephone system see (Bellamy, 1991).
`
`
`
`12
`
`12
`
`

`

`SEC. 2.4
`
`THE TELEPHONE SYSTEM
`
`103
`
`2.4.1. Structure of the Telephone System
`
`When Alexander Graham Bell patented the telephone in 1876 (just a few
`hours ahead ofhis rival, Elisha Gray), there was an enormous demandfor his new
`invention. The initial market was for the sale of telephones, which came in pairs.
`It was up to the customerto string a single wire between them. The electrons
`returned through the earth.
`If a telephone owner wanted to talk to n other tele-
`phone owners, separate wires hadto be strung to all n houses. Within a year, the
`cities were covered with wires passing over houses and trees in a wild jumble.
`It
`became immediately obvious that the model of connecting every telephone to
`every other telephone, as shownin Fig. 2-14(a) was not going to work.
`
`
`>
`
`RSL
`_3RETESZ
`EHS
`
`PS.
`PAK
`. \Pt RO)
`
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 2-14. (a) Fully interconnected network.
`level hierarchy.
`
`(b) Centralized switch.
`
`(c) Two-
`
`To his credit, Bell saw this and formed the Bell Telephone Company, which
`openedits first switching office (in New Haven, Connecticut) in 1878. The com-
`pany ran a wire to each customer’s house or office. To make a call, the customer
`would crank the phone to make a ringing sound in the telephone companyoffice
`to attract the attention of an operator, who would then manually connect the caller
`to the callee using a jumper cable. The modelof a single switching office is illus-
`trated in Fig. 2-14(b).
`Pretty soon, Bell System switching offices were springing up everywhere and
`people wanted to make long-distance calls between cities, so the Bell system
`began to connect the switching offices. The original problem soon returned:
`to
`connect every switching office to every other switching office by meansof a wire
`between them quickly became unmanageable, so second-level switching offices
`were invented, After a while, multiple second-level offices were needed, as shown
`in Fig. 2-14(c). Eventually, the hierarchy grew to five levels.
`the
`By 1890, the three major parts of the telephone system were in place:
`switching offices, the wires between the customers and the switching offices (by
`now balanced, insulated, twisted pairs instead of open wires with an earth return),
`and the long-distance connections between the switching offices. While there
`
`
`
`13
`
`13
`
`

`

`104
`
`THE PHYSICAL LAYER
`
`CHAP. 2
`
`have been improvementsin all three areas since then, the basic Bell System model
`has remainedessentially intact for over 100 years. For a short technical history of
`the telephone system, see (Hawley, 1991).
`At present,
`the telephone system is organized as a highly redundant, mul-
`tilevel hierarchy. The following description is highly simplified but gives the
`essential flavor nevertheless. Each telephone has two copper wires coming out of
`it that go directly to the telephone company’s nearest end office (also called a
`local central office). The distance is typically 1 to 10 km, being smallerin cities
`than in rural areas.
`In the United States alone there are about 19,000 end offices. The concatena-
`tion of the area code andthefirst three digits of the telephone number uniquely
`specify an end office, which is why the rate structure uses this information. The
`two-wire connections between each subscriber’s telephone andthe end office are
`knowninthetrade as the local loop. If the world’s local loops were stretched out
`end to end, they would extend to the moon and back 1000 times.
`At one time, 80 percent of AT&T’s capital value was the copperin the local
`loops. AT&T wasthen, in effect, the world’s largest copper mine. Fortunately,
`this fact was not widely known in the investment community. Had it been known,
`some corporate raider might have bought AT&T,terminated all telephone service
`in the United States, ripped outall the wire, and sold the wire to a copper refiner
`to get a quick payback.
`If a subscriber attached to a given end office calls another subscriber attached
`to the same endoffice, the switching mechanism within the office sets up a direct
`electrical connection between the two local loops. This connection remains intact
`for the duration ofthe call.
`If the called telephone is attached to another end office, a different procedure
`has to be used. Each end office has a number of outgoing lines to one or more
`nearby switching centers, called toll offices (or if they are within the same local
`area, tandem offices). These lines are called toll connecting trunks. If both the
`caller’s and callee’s end offices happen to haveatoll connecting trunk to the same
`toll office (a likely occurrenceif they are relatively close by), the connection may
`be established within the toll office. A telephone network consisting only oftele-
`phones (the small dots), end offices (the large dots) and toll offices (the squares)
`is shownin Fig. 2-14(c).
`If the caller and callee do not havea toll office in common,the path will have
`to be established somewhere higher up in the hierarchy. There are primary, sec-
`tional, and regional offices that form a network by whichthetoll offices are con-
`nected. The toll, primary, sectional, and regional exchanges communicate with
`each other via high bandwidth intertoll trunks(also called interoffice trunks).
`The numberofdifferent kinds of switching centers andtheir topology (e.g., may
`two sectional offices have a direct connection or must they go through a regional
`office?) varies from country to country dependingonits telephone density. Figure
`2-15 shows how a medium-distance connection might berouted.
`
`
`
`14
`
`14
`
`

`

`SEC. 2.4
`
`THE TELEPHONE SYSTEM
`
`105
`
`Intermediate
`Telephone
`End
`Toll
`switching
`Toll
`End
`Telephone
`
`
`
`
`i—="5office officei—office office(s) office
`
`eeieiineteese a
`
`Local
`loop
`
`Toll
`;
`connecting
`trunk
`
`\
`
`high/
`"9
`Vail:
`bandwidth
`:
`intertoll
`trunks
`
`Toll
`2
`connecting
`trunk
`
`Local
`loop
`
`Fig. 2-15. Typical circuit route for a medium-distancecall.
`
`A variety of transmission media are used for telecommunication. Local loops
`consist of twisted pairs nowadays, although in the early days of telephony, uninsu-
`lated wires spaced 25 cm apart on telephone poles were common. Between
`switching offices, coaxial cables, microwaves, and especially fiber optics are
`widely used.
`In the past, signaling throughout the telephone system was analog, with the
`actual voice signal being transmitted as an electrical voltage from source to desti-
`nation. With the advent of digital electronics and computers, digital signaling has
`become possible.
`In this system, only two voltages are allowed, for example —5
`volts and +5 volts.
`This scheme has a number of advantages over analog signaling. First is that
`although the attenuation and distortion are more severe when sending two-level
`signals than when using modems,it is easy to calculate how far a signal can prop-
`agate and still be recognizable. A digital regenerator can beinserted into the line
`there, to restore the signalto its original value, since there are only two possibili-
`ties. A digital signal can pass through an arbitrary number of regenerators with no
`loss in signal and thustravel long distances with no information loss.
`In contrast,
`analog signals always suffer some information loss when amplified, and this loss
`is cumulative. The net result is that digital transmission can be made to have a
`low errorrate.
`A second advantage of digital transmission is that voice, data, music, and
`images (e.g., television, fax, and video) can be interspersed to make more effi-
`cient use of the circuits and equipment. Another advantage is that much higher
`data rates are possible using existing lines.
`A third advantage is that digital transmission is much cheaper than analog
`transmission,
`since it
`is not necessary to accurately reproduce an analog
`waveform after it has passed through potentially hundreds of amplifiers on a tran-
`scontinental call. Being able to correctly distinguish a 0 from a 1| is enough.
`Finally, maintenance of a digital system is easier than maintenance of an ana-
`log one. A transmitted bit is either received correctly or not, making it simpler to
`track down problems.
`Consequently, all the long-distance trunks within the telephone system are
`
`
`
`15
`
`15
`
`

`

`106
`
`THE PHYSICAL LAYER
`
`CHAP. 2
`
`rapidly being converted to digital. The old system used analog transmission over
`copperwires; the new oneuses digital transmission overopticalfibers.
`In summary, the telephone system consists of three major components:
`1. Local loops (twisted pairs, analog signaling).
`2. Trunks (fiber optics or microwave, mostly digital).
`3. Switching offices.
`After a short digression onthe politics of telephones, we will come back to each
`of these three components in some detail. For the local loop, we will be con-
`cerned with how to send digital data overit (quick answer: use a modem). For the
`long-haul trunks, the main issue is how to collect multiple calls together and send
`them together. This subject is called multiplexing, and wewill study three dif-
`ferent ways to do it. Finally, there are two fundamentally different ways of doing
`switching, so we will look at both of these.
`
`2.4.2. The Politics of Telephones
`
`For decades prior to 1984, the Bell System provided both local and long dis-
`tance service throughout most of the United States. In the 1970s, the U.S. govern-
`ment came to believe that this was an illegal monopoly and sued to break it up.
`The government won, and on Jan. 1, 1984, AT&T was broken up into AT&T
`Long Lines, 23 BOCs(Bell Operating Companies), and a few other pieces. The
`23 BOCs were grouped together into seven regional BOCs (RBOCs) to make
`them economically viable. The entire nature of telecommunication in the United
`States was changed overnight by court order (not by an act of Congress).
`The exact details of the divestiture were described in the so-called MFJ
`(Modified Final Judgment), an oxymoron if ever there was one (if the judgment
`could be modified, it clearly was not final). This event led to increased competi-
`tion, better service, and lower prices to consumers and businesses. Many other
`countries are now considering introducing competition along similar lines.
`To make it clear who could do what, the United States was divided up into
`about 160 LATAs(Local Access and Transport Areas). Very roughly, a LATA
`is about as big as the area covered by one area code. Within a LATA,there is
`normally one LEC (Local Exchange Carrier) that has a monopoly ontraditional
`telephone service within the LATA. The most important LECs are the BOCs,
`although some LATAscontain one or more of the 1500 independent telephone
`companies operating as LECs.
`In geographically large LATAs (mostly in the
`West), the LEC may handle long distance calls within its own LATA but may not
`handlecalls going to a different LATA.
`All inter-LATAtraffic is handled by a different kind of company, an IXC
`(IntereXchange Carrier). Originally, AT&T Long Lines was the only serious
`IXC, but now MCIand Sprint are well-established competitors in the IXC
`
`
`
`16
`
`16
`
`

`

`SEC. 2.4
`
`THE TELEPHONE SYSTEM
`
`107
`
`business. One of the concerns at the breakup was to ensure that all the [IXCs
`would be treated equally in termsof line quality, tariffs, and the numberofdigits
`their customers would have to dial to use them. The waythis is handled is illus-
`trated in Fig. 2-16. Here we see three example LATAs, each with several end
`offices. LATAs 2 and 3 also have a small hierarchy with tandem offices (intra-
`LATAtoll offices).
`
`IXC #1’s
`toll office
`
`IXC #1’s
`toll office
`
`To local loops
`
`Tanden
`office
`
`End
`office
`
`LATA 1
`
`LATA 2
`
`LATA 3
`
`Fig. 2-16. The relationship of LATAs, LECs, and IXCs. All the circles are
`LECswitching offices. Each hexagon belongsto the IXC whose numberisinit.
`
`Any IXC that wishes to handle calls originating in a LATA can build a
`switching office called a POP (Point of Presence) there. The LEC is required to
`connect each IXC to every end office, either directly, as in LATAs 1 and 3, or
`indirectly, as in LATA 2. Furthermore, the terms of the connection, both techni-
`cal andfinancial, must be identical for all IXCs. In this way, a subscriber in, say,
`LATA1, can choose which IXCto use forcalling subscribers in LATA 3.
`Aspart of the MFJ, the IXCs were forbidden to offer local telephone service
`and the LECs were forbidden to offer inter-LATA telephone service, although
`both were free to enter other businesses, such as operating fried chicken restau-
`rants.
`In 1984, that was a fairly unambiguous statement. Unfortunately, technol-
`ogy has a way of making the law obsolete. Neither cable television nor cellular
`phones were covered by the agreement. Ascabletelevision went from one way to
`two way, andcellular phones exploded in popularity, both LECs and IXCs began
`buying up or merging with cable and cellular operators.
`By 1995, Congress saw that trying to maintain a distinction between the vari-
`ous kinds of companies wasno longer tenable anddrafted a bill to allow cable TV
`
`
`
`17
`
`17
`
`

`

`108
`
`THE PHYSICAL LAYER
`
`CHAP. 2
`
`companies, local telephone companies, long distance carriers, and cellular opera-
`tors to enter one another’s businesses. The idea was that any company could then
`offer its customers a single integrated package containing cable TV, telephone,
`and information services, and that different companies would compete on service
`and price. The bill was enacted into law in February 1996. As a result, the U.S.
`telecommunications landscape is currently undergoing a radical restructuring.
`
`2.4.3. The Local Loop
`
`For the past 100 years, analog transmission has dominated all communication.
`In particular, the telephone system wasoriginally based entirely on analog signal-
`ing. While the long-distance trunks are now largely digital in the more advanced
`countries, the local loops are still analog and are likely to remain so forat least a
`decade or two, due to the enormouscost of converting them. Consequently, when
`a computer wishes to send digital data over a dial-up line, the data mustfirst be
`converted to analog form by a modem for transmission over the local loop, then
`converted to digital form for transmission over the long-haul trunks, then back to
`analog over the local loop at the receiving end, and finally back to digital by
`another modem for storage in the destination computer. This arrangement
`is
`shownin Fig. 2-17.
`
`Customer premises
`equipment
`
`Customer premises
`equipment
`
`Digital
`(telephone
`company
`trunks)
`
`
`
`Digital
`(short cable)
`
`office
`
`Toll
`office
`
`office
`
`Digital
`(short cable)
`
`Fig. 2-17. The use of both analog and digital transmission for a computer to
`computer call. Conversion is done by the modems and codecs.
`
`While this situation is not exactly ideal, such is life for the time being, and
`students of networking should have some understanding of both analog and digital
`transmission, as well as how the conversions back and forth work. For leased
`linesit is possible to go digital from start to finish, but these are expensive and are
`only useful for building intracompany private networks.
`In the following sections we will look briefly at what is wrong with analog
`
`
`
`18
`
`18
`
`

`

`SEC. 2.4
`
`THE TELEPHONE SYSTEM
`
`109
`
`transmission and examine how modems makeit possible to transmit digital data
`over analog circuits. We will also look at two common modem interfaces, RS-
`232-C and RS-449.
`
`Transmission Impairments
`
`Analog signaling consists of varying a voltage with time to represent an infor-
`mation stream.
`If transmission media were perfect,
`the receiver would receive
`exactly the same signal that the transmitter sent. Unfortunately, media are not
`perfect, so the received signal is not the same asthe transmitted signal. For digi-
`tal data, this difference can leadto errors.
`Transmission lines suffer from three major problems: attenuation, delay dis-
`tortion, and noise. Attenuationis the loss of energy as the signal propagates out-
`ward. On guided media(e.g., wires and optical fibers), the signal falls off loga-
`rithmically with the distance. The loss is expressed in decibels per kilometer.
`The amountofenergy lost depends onthe frequency. To see the effect of this fre-
`quency dependence, imagine a signal notas a simple waveform, but asa series of
`Fourier components. Each componentis attenuated by a different amount, which
`results in a different Fourier spectrum at the receiver, and hence a different signal.
`If the attenuation is too much,the receiver may notbeable to detect the signal
`at all, or the signal may fall below the noise level.
`In manycases, the attenuation
`properties of a medium are known,so amplifiers can be put in to try to compen-
`sate for the frequency-dependent attenuation. The approach helps but can never
`restore the signal exactly back to its original shape.
`It is caused by the
`The second transmission impairmentis delay distortion.
`fact that different Fourier componentstravel at different speeds. For digital data,
`fast components from one bit may catch up and overtake slow components from
`the bit ahead, mixing the two bits and increasing the probability of incorrect
`reception.
`The third impairment is noise, which is unwanted energy from sources other
`than the transmitter. Thermal noise is caused by the random motion of the elec-
`trons in a wire and is unavoidable. Cross talk is caused by inductive coupling
`between two wires that are close to each other. Sometimes when talking on the
`telephone, you can hear another conversation in the background. That is cross
`talk. Finally, there is impulse noise, caused by spikes on the power line or other
`causes. For digital data, impulse noise can wipe out one or morebits.
`
`Modems
`
`Dueto the problems just discussed, especially the fact that both