Computer networks Andrew S. Tanenbaum

1 INTRODUCTION
1.1 USES OF COMPUTER NETWORKS
1.1.1 Business Applications
1.1.2 Home Applications
1.1.3 Mobile Users
1.1.4 Social Issues
1.2 NETWORK HARDWARE
1.2.1 Local Area Networks
1.2.2 Metropolitan Area Networks i
1.2.3 Wide Area Networks
1.2.4 Wireless Networks
1.2.5 Home Networks
1.2.6 Internetworks
1.3 NETWORK SOFTWARE
1.3.1 Protocol Hierarchies :
1.3.2 Design Issues for the Layers
1.3.3 Connection-Oriented and Connectionless Services
1.3.4 Service Primitives
1.3.5 The Relationship of Services to Protocols
1.4 REFERENCE MODELS 37
1.4.1 The OSl Reference Model 37
1.4.2 The TCP/IP Reference Model 41
1.4.3 A Comparison of the OSl and TCP/IP Reference Models 44
1.4.4 A Critique of the OSl Model and Protocols 46
1.4.5 A Critique of the TCP/IP Reference Model 48
1.5 EXAMPLE NETWORKS 49
1.5.1 The Internet 50
1.5.2 Connection-Oriented Networks: X.25, Frame Relay, and ATM 59
1.5.3 Ethernet 65
1.5.4 Wireless LANs: 802.11 68
1.6 NETWORK STANDARDIZATION 71
1.6.1 Who's Who in the Telecommunications World 71
1.6.2 Who's Who in the International Standards World 74
1.6.3 Who's Who in the Internet Standards World 75
1.7 METRIC UNITS 77
1.8 OUTLINE OF THE REST OF THE BOOK 78
1.9 SUMMARY 79
2 THE PHYSICAL LAYER
2.1 THE THEORETICAL BASIS FOR DATA COMMUNICATION
2.1.1 Fourier Analysis 86
2.1.2 Bandwidth-Limited Signals 86
2.1.3 The Maximum Data Rate of a Channel 89
2.2 GUIDED TRANSMISSION MEDIA 90
2.2.1 Magnetic Media 90
2.2.2 Twisted Pair 91
2.2.3 Coaxial Cable 92
2.2.4 Fiber Optics 93
2.3 WIRELESS TRAI^SMISSION 100
2.3.1 The Electromagnetic Spectrum 100
2.3.2 Radio Transmission 103
2.3.3 Microwave Transmission 104
2.3.4 Infrared and Millimeter Waves 106
2.3.5 Lightwave Transmission 107
2.4 COMMUNICATION SATELLITES 109
2.4.1 Geostationary Satellites 109
2.4.2 Medium-Earth Orbit Satellites 113
2.4.3 Low-Earth Orbit Satellites 114
2.4.4 Satellites versus Fiber 117
2.5 THE PUBLIC SWITCHED TELEPHONE NETWORK 118
2.5.1 Structure of the Telephone System 119
2.5.2 The Politics of Telephones 122
2.5.3 The Local Loop: Modems, ADSL, and Wireless 124
2.5.4 Trunks and Multiplexing 137
2.5.5 Switching 146
2.6 THE MOBILE TELEPHONE SYSTEM 152
2.6.1 First-Generation Mobile Phones: Analog Voice 153
2.6.2 Second-Generation Mobile Phones: Digital Voice 157
2.6.3 Third-Generation Mobile Phones: Digital Voice and Data 166
2.7 CABLE TELEVISION 169
2.7.1 Community Antenna Television 169 /
2.7.2 Internet over Cable 170
2.7.3 Spectrum Allocation 172
2.7.4 Cable Modems 173
2.7.5 ADSL versus Cable 175
2.8 SUMMARY 177
3 THE DATA LIHK LAYER
3.1 DATA LINK LAYER DESIGN ISSUES 184
3.1.1 Services Provided to the Network Layer 184
3.1.2 Framing 187
3.1.3 Error Control 191
3.1.4 Flow Control 192
3.2 ERROR DETECTION AND CORRECTION 192
3.2.1 Error-Correcting Codes 193
3.2.2 Error-Detecting Codes 196
3.3 ELEMENTARY DATA LINK PROTOCOLS 200
3.3.1 An Unrestricted Simplex Protocol 204
3.3.2 A Simplex Stop-and-Wait Protocol 206
3.3.3 A Simplex Protocol for a Noisy Channel 208
3.4 SLIDING WINDOW PROTOCOLS 211
3.4.1 A One-Bit Sliding Window Protocol 214
3.4.2 A Protocol Using Go Back N 216
3.4.3 A Protocol Using Selective Repeat 223
3.5 PROTOCOL VERIFICATION 229
3.5.1 Finite State Machine Models 229
3.5.2 Petri Net Models 232
3.6 EXAMPLE DATA LINK PROTOCOLS 234
3.6.1 HDLC—High-Level Data Link Control 234
3.6.2 The Data Link Layer in the Internet 237
3.7 SUMMARY 242
4 THE MEDIUM ACCESS CONTROL SUBLAYER
4.1 THE CHANNEL ALLOCATION PROBLEM 248
4.1.1 Static Channel Allocation in LANs and MANs 248
4.1.2 Dynamic Channel Allocation in LANs and MANs 249
4.2 MULTIPLE ACCESS PROTOCOLS 251
4.2.1 ALOHA 251
4.2.2 Carrier Sense Multiple Access Protocols 255
4.2.3 Collision-Free Protocols 259
4.2.4 Limited-Contention Protocols 261
4.2.5 Wavelength Division Multiple Access Protocols 265
4.2.6 Wireless LAN Protocols 267
4.3 ETHERNET 271
4.3.1 Ethernet Cabling 271
4.3.2 Manchester Encoding 274
4.3.3 The Ethernet MAC Sublayer Protocol 275
4.3.4 The Binary Exponential Backoff Algorithm 278
4.3.5 Ethernet Performance 279
4.3.6 Switched Ethernet 281
4.3.7 Fast Ethernet 283
4.3.8 Gigabit Ethernet 286
4.3.9 IEEE 802.2: Logical Link Control 290
4.3.10 Retrospective on Ethernet 291
4.4 WIRELESS LANS 292
4.4.1 The 802.11 Protocol Stack 292
4.4.2 The 802.11 Physical Layer 293
4.4.3 The 802.11 MAC Sublayer Protocol 295
4.4.4 The 802.11 Frame Structure 299
4.4.5 Services 3-1
4.5 BROADBAND WIRELESS 302
4.5.1 Comparison of 802.11 with 802.16 303
4.5.2 The 802.16 Protocol Stack 305
4.5.3 The 802.16 Physical Layer 306
4.5.4 The 802.16 MAC Sublayer Protocol 307
4.5.5 The 802.16 Frame Structure 309
4.6 BLUETOOTH 310
4.6.1 Bluetooth Architecture 311
4.6.2 Bluetooth Applications 312
4.6.3 The Bluetooth Protocol Stack 313
4.6.4 The Bluetooth Radio Layer 315
4.6.5 The Bluetooth Baseband Layer 315
4.6.6 The Bluetooth L2CAP Layer 316
4.6.7 The Bluetooth Frame Structure 316
4.7 DATA LINK LAYER SWITCHING 318
4.7.1 Bridges from 802.x to 802.y 320
4.7.2 Local Internetworking 322
4.7.3 Spanning Tree Bridges 324
4.7.4 Remote Bridges 325
4.7.5 Repeaters, Hubs, Bridges, Switches, Routers, and Gateways
4.7.6 Virtual LANs 329
5 THE NETWORK LAYER
5.1 NETWORK LAYER DESIGN ISSUES 343
5.1.1 Store-and-Forward Packet Switching 344
5.1.2 Services Provided to the Transport Layer 344
5.1.3 Implementation of Connectionless Service 345
5.1.4 Implementation of Connection-Oriented Service 347
5.1.5 Comparison of Virtual-Circuit and Datagram Subnets 348
5.2 ROUTING ALGORITHMS 350
5.2.1 The Optimality Principle 352
5.2.2 Shortest Path Routing 353
5.2.3 Flooding 355
5.2.4 Distance Vector Routing 357
5.2.5 Link State Routing 360
5.2.6 Hierarchical Routing 366
5.2.7 Broadcast Routing 368
5.2.8 Multicast Routing 370
5.2.9 Routing for Mobile Hosts 372
5.2.10 Routing in Ad Hoc Networks 373
5.2.11 Node Lookup in Peer-to-Peer Networks 380
5.3 CONGESTION CONTROL ALGORITHMS 384
5.3.1 General Principles of Congestion Control 386
5.3.2 Congestion Prevention Policies 388
5.3.3 Congestion Control in Virtual-Circuit Subnets 389
5.3.4 Congestion Control in Datagram Subnets 391
5.3.5 Load Shedding 394
5.3.6 Jitter Control 395
5.4 QUALITY OF SERVICE 397
5.4.1 Requirements 397
5.4.2 Techniques for Achieving Good Quality of Service 398
5.4.3 Integrated Services 409
5.4.4 Differentiated Services 412
5.4.5 Label Switching and MPLS 415
5.5 INTERNETWORKING 418
5.5.1 How Networks Differ 419
5.5.2 How Networks Can Be Connected 420
5.5.3 Concatenated Virtual Circuits 422
5.5.4 Connectionless Internetworking 423
5.5.5 Tunneling 425
5.5.6 Internetwork Routing 426
5.5.7 Fragmentation 427
5.6 THE NETWORK LAYER IN THE INTERNET- 431
5.6.1 The IP Protocol 433
5.6.2 IP Addresses 436
5.6.3 Internet Control Protocols 449
5.6.4 OSPF—The Interior Gateway Routing Protocol 454
5.6.5 BOP—^The Exterior Gateway Routing Protocol 459
5.6.6 Internet Multicasting 461
5.6J Mobile IP 462
5.6.8 IPv6 464
5.7 SUMMARY 473
6 THE TRANSPORT LAYER
6.1 THE TRANSPORT SERVICE 481
6.1.1 Services Provided to the Upper Layers 481
6.1.2 Transport Service Primitives 483
6.1.3 Berkeley Sockets 487
6.1.4 An Example of Socket Programming: An Internet File Server 488
6.2 ELEMENTS OF TRANSPORT PROTOCOLS 492
6.2.1 Addressing 493
6.2.2 Connection Establishment 496
6.2.3 Connection Release 502
6.2.4 Flow Control and Buffering 506
6.2.5 Multiplexing 510
6.2.6 Crash Recovery 511
6.3 A SIMPLE TRANSPORT PROTOCOL 513
6.3.1 The Example Service Primitives 513
6.3.2 The Example Transport Entity 515
6.3.3 The Example as a Finite State Machine 522
6.4 THE INTERNET TRANSPORT PROTOCOLS: UDP 524
6.4.1 Introduction to UDP 525
6.4.2 Remote Procedure Call 526
6.4.3 The Real-Time Transport Protocol 529
XIV
6.5 THE INTERNET TRANSPORT PROTOCOLS: TCP 532
6.5.1 Introduction to TCP 532
6.5.2 The TCP Service Model 533
6.5.3 The TCP Protocol 535
6.5.4 The TCP Segment Header 536
6.5.5 TCP Connection Establishment 539
6.5.6 TCP Connection Release 541
6.5.7 Modeling TCP Connection Management 541
6.5.8 TCP Transmission Policy 543
6.5.9 TCP Congestion Control 547
6.5.10 TCP Timer Management 550
6.5.11 Wireless TCP and UDP 553
6.5.12 Transactional TCP 555
6.6 PERFORMANCE ISSUES 557
6.6.1 Performance Problems in Computer Networks 557
6.6.2 Network Performance Measurement 560
6.6.3 System Design for Better Performance 562
6.6.4 Fast TPDU Processing 566
6.6.5 Protocols for Gigabit Networks 569
6.7 SUMMARY 573
7 THE APPLICATION LAYER
7.1 DNS—THE DOMAIN NAME SYSTEM 579
7.1.1 The DNS Name Space 580
7.1.2 Resource Records 582
7.1.3 Name Servers 586
7.2 ELECTRONIC MAIL 588
7.2.1 Architecture and Services 59.0
7.2.2 The User Agent 591
7.2.3 Message Formats 594
7.2.4 Message Transfer 602
7.2.5 Final Delivery 605
7.3 THE WORLD WIDE WEB 611
7.3.1 Architectural Overview" 612
7.3.2 Static Web Documents 629
7.3.3 Dynamic Web Documents 643
7.3.4 HTTP—The HyperText Transfer Protocol 651
7.3.5 Performance Enhancements 656
7.3.6 The Wireless Web 662
7.4 MULTIMEDIA 674
7.4.1 Introduction to Digital Audio 674
7.4.2 Audio Compression 676
7.4.3 Streaming Audio 679
7.4.4 Internet Radio 683
7.4.5 Voice over IP 685
7.4.6 Introduction to Video 692
7.4.7 Video Compression 696
7.4.8 Video on Demand 704
7.4.9 The MBone—The Multicast Backbone 711
7.5 SUMMARY 714
8 NETWORK SECURITY
8.1 CRYPTOGRAPHY 724
8.1.1 Introduction to Cryptography 725
8.1.2 Substitution Ciphers 727
8.1.3 Transposition Ciphers 729
8.1.4 One-Time Pads 730
8.1.5 Two Fundamental Cryptographic Principles 735
8.2 SYMMETRIC-KEY ALGORITHMS 737
8.2.1 DES—The Data Encryption Standard 738
8.2.2 AES—The Advanced Encryption Standard 741
8.2.3 Cipher Modes 745
8.2.4 Other Ciphers 750
8.2.5 Cryptanalysis 750
8.3 PUBLIC-KEY ALGORITHMS 752
8.3.1 RSA 753
8.3.2 Other Public-Key Algorithms 755
8.4 DIGITAL SIGNATURES 755
8.4.1 Symmetric-Key Signatures 756
8.4.2 Public-Key Signatures 757
8.4.3 Message Digests 759
8.4.4 The Birthday Attack 763
8.5 MANAGEMENT OF PUBLIC KEYS 765
8.5.1 Certificates 765
8.5.2 X.509 767
8.5.3 Public Key Infrastructures 768
8.6 COMMUNICATION SECURITY 772
8.6.1 IPsec 772
8.6.2 Firewalls 776
8.6.3 Virtual Private Networks 779
8.6.4 Wireless Security 780
8.7 AUTHENTICATION PROTOCOLS 785
8.7.1 Authentication Based on a Shared Secret Key 786
8.7.2 Establishing a Shared Key: The Diffie-Hellman Key Exchange 19
8.7.3 Authentication Using a Key Distribution Center 793
8.7.4 Authentication Using Kerberos 796
8.7.5 Authentication Using Public-Key Cryptography 798
8.8 E-MAIL SECURITY 799
8.8.1 PGP—Pretty Good Privacy 799
8.8.2 PEM—^Privacy Enhanced Mail 803
8.8.3 S/MIME 804
8.9 WEB SECURITY 805
8.9.1 Threats 8-5
8.9.2 Secure Naming 806
8.9.3 SSL—^The Secure Sockets Layer 813
8.9.4 Mobile Code Security 816
8.10 SOCIAL ISSUES 819
8.10.1 Privacy 819
8.10.2 Freedom of Speech 922
8.10.3 Copyright 826
9 READING LIST AND BIBLIOGRAPHY
9.1 SUGGESTIONS FOR FURTHER READING 835
9.1.1 Introduction and General Works 836
9.1.2 The Physical Layer 838
9.1.3 The Data Link Layer 840
9.1.4 The Medium Access Control Sublayer 840
9.1.5 The Network Layer 842
9.1.6 The Transport Layer 844
9.1.7 The Application Layer 844
9.1.8 Network Security 846