Jt
`
`ii
`
`Broadcasting
`
`BrJ_
`
`100000110 SMILE
`
`1001l01lO 4MLE
`
`0110110011' 2MLE
`
`SHALL ICOMPARE THEE
`TO A SUMMERS DAY? LALOHA
`
`E
`PION
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page A
`
`

`
`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, Andrew S. 1944-.
`Computer networks / Andrew S. Tanenbaum. -- 3rd ed.
`p. cm.
`Includes bibliographical references and index.
`ISBN 0-13-349945-6
`1.Computer networks. I. Title.
`TK5105.5.T36 1996 (cid:9)
`004.6--dc2O (cid:9)
`
`96-4121
`CIP
`
`Editoriallproduction manager: Camille Trentacoste
`Interior design and composition: Andrew S. Tanenbaum
`Cover design 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 mentioned herein are the trademarks of their respective owners.
`
`Printed in the United States of America
`10 9 8
`
`ISBN 0-13-349945 -6
`
`Prentice-HaI1 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, Ltda., Rio de Janeiro
`
`I
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page B
`
`

`
`CONTENTS
`
`PREFACE
`
`1
`
`INTRODUCTION
`
`xv
`
`1
`
`10
`
`1.1 USES OF COMPUTER NETWORKS 3
`1.1.1 Networks for Companies 3
`1.1.2 Networks for People 4
`1.1.3 Sociallssues 6
`1.2 NETWORK HARDWARE 7
`1.2.1 Local Area Networks 9
`1.2.2 Metropolitan Area Networks (cid:9)
`1.2.3 Wide Area Networks (cid:9)
`11
`1.2.4 Wireless Networks (cid:9)
`13
`1.2.5 Internetworks (cid:9)
`16
`1.3 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
`1.4 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
`1.5 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
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page vi
`
`

`
`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 (cid:9) 66
`1.7 NETWORK STANDARDIZATION 66
`1.7.1 Who's Who in the Telecommunications World 67
`1.7.2 Who's Who in the International Standards World (cid:9) 69
`1.7.3 Who's Who in the Internet Standards World 70
`1.8 OUTLINE OF THE REST OF THE BOOK 72
`1.9. SUMMARY 73
`
`Z THE PHYSICAL LAYER
`
`77
`
`'
`
`2.1 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
`2.2 TRANSMISSION MEDIA 82
`2.2.1 Magnetic Media 82 (cid:9)
`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
`2.3 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 100
`2.3.5 Lightwave Transmission 100
`2.4 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
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page vii
`
`

`
`viii (cid:9)
`
`CONTENTS
`
`2.5 NARROWBAND ISDN 139
`2.5.1 ISDN Services 140
`2.5.2 ISDN System Architecture 140
`2.5.3 The ISDN Interface 142
`2.5.4 Perspective on N-ISDN 143
`2.6 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
`2.7 CELLULAR RADIO 155
`2.7.1 Paging Systems (cid:9)
`155
`2.7.2 Cordless Telephones (cid:9) 157
`157
`2.7.3 Analog Cellular Telephones (cid:9)
`2,7.4 Digital Cellular Telephones (cid:9) 162
`2.7.5 Personal Communications Services (cid:9)
`2.8 COMMUNICATION SATELLITES 163
`2.8.1 Geosynchronous Satellites 164
`2.8.2 Low-Orbit Satellites 167
`2.8.3 Satellites versus Fiber 168
`2.9 SUMMARY 170
`
`162
`
`3 THE DATA LINK LAYER
`3.1 DATA LINK LAYER DESIGN ISSUES 176
`3.1.1 Services Provided to the Network Layer 176
`3.1.2 Framing (cid:9)
`179
`3.1.3 Error Control (cid:9) 182
`3.1.4 Flow Control (cid:9)
`183
`3.2 ERROR DETECTION AND CORRECTION
`3.2.1 Error-Correcting Codes (cid:9) 184
`3.2.2 Error-Detecting Codes (cid:9)
`186
`3.3 ELEMENTARY DATA LINK PROTOCOLS 190
`3.3.1 An Unrestricted Simplex Protocol (cid:9)
`195
`3.3.2 A Simplex Stop-and-Wait Protocol (cid:9)
`195
`3.3.3 A Simplex Protocol for a Noisy Channel 197
`
`183
`
`175
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page viii
`
`

`
`CONTENTS
`
`ix
`
`3.4 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
`3.5 PROTOCOL SPECIFICATION AND VERIFICATION 219
`3.5.1 Finite State Machine Models 219
`3.5.2 Petri Net Models 223
`3.6 EXAMPLE DATA LINK PROTOCOLS 225
`3.6.1 HDLC—High-level Data Link Control 225
`3.6.2 The Data Link Layer in the Internet 229
`3.6.3 The Data Link Layer in ATM 235
`3.7. SUMMARY 239
`
`4 THE MEDIUM ACCESS SUBLAYER (cid:9)
`
`243
`
`4.1 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
`
`4.2 MULTIPLE ACCESS PROTOCOLS 246
`4.2.1 ALOHA 246
`4.2.2 Carrier Sense Multiple Access Protocols (cid:9) 250
`4.2.3 Collision-Free Protocols (cid:9) 254
`4.2.4 Limited-Contention Protocols (cid:9) 256
`4.2.5 Wavelength Division Multiple Access Protocols (cid:9) 260
`4.2.6 Wireless LAN Protocols 262
`4.2.7 Digital Cellular Radio (cid:9) 266
`
`4.3 IEEE STANDARD 802 FOR LANS AND MANS 275
`4.3.1 IEEE Standard 802.3 and Ethernet 276
`4.3.2 IEEE 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
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page ix
`
`(cid:9)
`

`
`x (cid:9)
`
`CONTENTS
`
`4.4 BRIDGES 304
`4.4.1 Bridges from 802.x to 802.y (cid:9) 307
`4.4.2 Transparent Bridges (cid:9) 310
`4.4.3 Source Routing Bridges (cid:9) 314
`4.4.4 Comparison of 802 Bridges (cid:9) 316
`4.4.5 Remote Bridges (cid:9) 317
`4.5 HIGH-SPEED LANS 318
`4.5.1 FDDI 319
`4.5.2 Fast Ethernet 322
`4.5.3 HIPPI—High-Performance Parallel Interface 325
`4.5.4 Fibre Channel 326
`4.6 SATELLITE NETWORKS 327
`4.6.1 Polling (cid:9) 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
`
`5 THE NETWORK LAYER (cid:9)
`
`339
`
`5.1 NETWORK LAYER DESIGN ISSUES 339
`5.1.1 Services Provided to the Transport Layer (cid:9) 340
`5.1.2 Internal Organization of the Network Layer (cid:9) 342
`5.1.3 Comparison of Virtual Circuit and Datagram Subnets 344
`5.2 ROUTING ALGORITHMS 345
`5.2.1 The Optimality Principle (cid:9) 347
`5.2.2 Shortest Path Routing (cid:9) 349
`5.2.3 Flooding (cid:9) 351
`5.2.4 Flow-Based Routing 353
`5.2.5 Distance Vector Routing (cid:9) 355
`5.2.6 Link State Routing (cid:9) 359
`5.2.7 Hierarchical Routing (cid:9) 365
`5.2.8 Routing for Mobile Hosts (cid:9) 367
`5.2.9 Broadcast Routing (cid:9) 370
`5.2.10 Multicast Routing (cid:9) 372
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page x
`
`

`
`CONTENTS
`
`xi
`
`5.3 CONGESTION CONTROL ALGORITHMS 374
`5.3.1 General Principles of Congestion Control (cid:9) 376
`5.3.2 Congestion Prevention Policies (cid:9) 378
`5.3.3 Traffic Shaping (cid:9) 379
`5.3.4 Flow Specifications (cid:9) 384
`5.3.5 Congestion Control in Virtual Circuit Subnets (cid:9) 386
`5.3.6 Choke Packets (cid:9) 387
`5.3.7 Load Shedding 390
`5.3.8 Jitter Control (cid:9) 392
`5.3.9 Congestion Control for Multicasting (cid:9) 393
`5.4 INTERNETWORKING 396
`5.4.1 How Networks Differ 399
`5.4.2 Concatenated Virtual Circuits (cid:9) 401
`5.4.3 Connectionless Internetworking (cid:9) 402
`5.4.4 Tunneling 404
`5.4.5 Internetwork Routing 405
`5.4.6 Fragmentation 406
`5.4.7 Firewalls (cid:9) 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 (cid:9) 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 (cid:9) 431
`5.5.8 Mobile IP 432
`5.5.9 CIDR—Classless Interpomain Routing 434
`5.5.10IPv6 (cid:9) 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 (cid:9) 458
`5.6.5 Quality of Service (cid:9) 460
`5.6.6 Traffic Shaping and Policing (cid:9) 463
`5.6.7 Congestion Control 467
`5.6.8 ATM LANs 471
`5.7 SUMMARY 473
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page xi
`
`

`
`CONTENTS
`Xii
`6 THE TRANSPORT LAYER (cid:9)
`
`479
`
`6.1 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
`
`6.2 ELEMENTS OF TRANSPORT PROTOCOLS 488
`6.2.1 Addressing 489
`6.2.2 Establishing a Connection (cid:9) 493
`6.2.3 Releasing a Connection 498
`6.2.4 Flow Control and Buffering (cid:9) 502
`6.2.5 Multiplexing (cid:9) 506
`6.2.6 Crash Recovery 508
`
`6.3 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
`
`6.4 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
`
`6.5 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 AAL 2 549
`6.5.4 AAL 3/4 550
`6.5.5 AAL 5 552
`6.5.6 Comparison of AAL Protocols 554
`6.5.7 SSCOP—Service Specific Connection-Oriented Protocol 555
`
`6.6 PERFORMANCE ISSUES 555
`6.6.1 Performance Problems in Computer Networks 556
`6.6.2 Measuring Network Performance 559
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page xii
`
`(cid:9)
`

`
`CONTENTS (cid:9)
`
`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
`
`rI THE APPLICATION LAYER
`
`577
`
`7.1 NETWORK SECURITY 577
`7.1.1 Traditional Cryptography 580
`7.1.2 Two Fundamental Cryptographic Principles (cid:9) 585
`7.1.3 Secret-Key Algorithms (cid:9) 587
`7.1.4 Public-Key Algorithms (cid:9) 597
`7.1.5 Authentication Protocols (cid:9) 601
`7.1.6 Digital Signatures (cid:9) 613
`7.1.7 Social Issues (cid:9) 620
`
`7.2 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
`
`7.3 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 Management Information 639
`7.3.4 The MIB—Management Information Base 641
`7.3.5 The SNMP Protocol 642
`
`7.4 ELECTRONIC MAIL 643
`7.4.1 Architecture and Services (cid:9) 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 USENET is Implemented 675
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page xiii
`
`(cid:9)
`

`
`xiv (cid:9)
`
`CONTENTS
`
`7.6 THE WORLD WIDE WEB 681
`7.6.1 The Client Side (cid:9) 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
`
`8 READING LIST AND BIBLIOGRAPHY (cid:9)
`8.1 (cid:9) 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
`
`767
`
`NETAPP ET AL. EXHIBIT 1003
`
`Page xiv
`
`

`
`3
`
`THE DATA LINK LAYER
`
`In this chapter we will study the design of layer 2, the data link layer. This
`study deals wi _ _-the al orithms for achievin reliable, efficient communication
`between two d'acent machine at the data link la er. By adjacent, we mean that
`the two machines are physically connected by a communication channel that acts
`conceptually like a wire (e.g., a coaxial cable or a telephone line). The essential
`property of a channel that makes it "wire-like" is that th e bits are delivered in
`exactly the same orde in which they are sent.
`At first you might think this problem is so trivial that there is no software to
`study—machine A just puts the bits on the wire, and machine B just takes them
`off. Unfortunately, conununi ircnirs_.n re errors occasionally. Further-
`more, they have only a finite data rate, and there is a nonzero propagation delay
`between the timeenttIif is received. These limitations have
`important implications for the efficiency of e daTãier. The protocols used
`for communications must take all these factors into consideration. These proto-
`cols are the subject of this chapter.
`After an introduction to the key design issues present in the data link layer, we
`will start our study of its protocols by looking at the nature of errors, their causes,
`and how they can be detected and corrected. Then we will study a series of
`increasingly complex protocols, each one solving more and more of the problems
`present in this layer. Finally, we will conclude with an examination of protocol
`modeling and correctness and give some examples of data link protocols.
`
`175
`
`Page 175
`
`NETAPP ET AL. EXHIBIT 1003
`
`

`
`176 (cid:9)
`
`THE DATA LINK LAYER (cid:9)
`
`CHAP. 3
`
`3.1. DATA LINK LAYER DESIGN ISSUES
`
`The data link layer has a number of specific functions to carry out. These
`functions include providing a well-defined service interface to the network layer,
`determining how the bits of the physical layer are grouped into frames, dealing
`with transmission errors, and regulating the flow of frames so that slow receivers
`are not swamped by fast senders. In the following sections we will examine each
`of these issues in turn.
`
`3.1.1. Services Provided to the Network Layer
`
`The function of the data link (cid:9)
`odidserices-to-thworl
`The principal service is transferri ata nom xhe network Iay_ex p n the s__ ounce
`machine to the network layer on the.destination-. achin.e._ On the source machine
`there is an entity, call it a process, in the network layer that hands some bits to the
`data link layer for transmission to the destination. The job of the data link layer is
`to transmit the bits to the destination machine, so they can be handed over to the
`network layer there, as shown in Fig. 3-1(a). The actual transmission follows the
`path of Fig. 3-1(b), but it is easier to think in terms of two data link layer
`processes communicating using a data link protocol. For this reason, we will
`implicitly use the model of Fig. 3-1(a) throughout this chapter.
`
`Host 1 (cid:9)
`
`Host 2 (cid:9)
`
`Host 1 (cid:9)
`
`Host 2
`
`4
`
`3
`
`2 (cid:9)
`
`Virtual
`data path
`
`4 (cid:9)
`
`3 (cid:9)
`
`2 (cid:9)
`
`1 (cid:9)
`
`4
`
`3
`
`2
`
`1
`
`4
`
`3
`
`2
`
`1
`
`(a)
`
`(b)
`
`Fig. 3-1. (a) Virtual communication. (b) Actual communication.
`The data link layer can be designed to offer various services. The actual
`
`Page 176
`
`NETAPP ET AL. EXHIBIT 1003
`
`

`
`SEC. 3.1 (cid:9)
`
`DATA LINK LAYER DESIGN ISSUES (cid:9)
`
`177
`
`services offered can vary from system to system. Three reasonable possibilities
`that are commonly provided are
`
`—1. Unacknowledged connectionless service.
`
`2. Acknowledged connectionless service.
`
`3. Acknowledged connection-oriented service.
`
`Let us consider each of these in turn.
`Unacknowledged connectionless service consists of having the source
`machine send independent frames to the destination machine without having the
`destination machine acknowledge them. No connection is established beforehand
`or released afterward. If a frame is lost due to noise on the line, no attemni t is
`made to recover it in the data link layer. Th is class of service is appropriate when
`the error rate is very low so recovery is left to higher layers. It is also appropriate
`for real-time traffic, such as speech, in which late data are worse than bad data.
`Most LANs use unacknowledged connectionless service in the data link layer.
`The next step up in terms of reliability is acknowledged connectionless ser-
`vice. When this service is offered, there are still no connections used, but each
`frame sent is individually acknowledged. In this way, the sender knows whether
`or not a rame as amve s e y. fit has not arrived within a specified time
`interval, it can be sent again. This service is useful over unreliable channels, such
`as wireless systems.
`It is perhaps worth emphasizing that providing acknowledgements in the data
`Iink layer is just an optimization, never a requirement. The transport layer can
`always send a message and wait for it to be acknowledged. If the acknowledge-
`ment is not forthcoming before the timer goes off, the sender can just send the
`entire message again. The trouble with this strategy is that if the average message
`is broken up into, say, 10 frames, and 20 percent of all frames are lost, it may take
`a very long time for the message to get through. If individual frames are acknowl-
`edged and retransmitted, entire messages get through much faster. On reliable
`channels, such as fiber, the overhead of a heavyweight data link protocol may be
`unnecessary, but on wireless channels it is well worth the cost due to their
`inherent unreliability.
`Getting back to our services, the most sophisticated service the data link layer
`can provide to the network layer is connection-oriented service. With this service,
`the source and destination machines establish &jQnnetion before any data are
`transferred. Each frame sent over the connection is numbered, and the data link
`layer guarantees that each frame sent is i eeed received. Fur ermore, it guaran-
`tees that each frame is received exactly once and that all frames are received in
`the right order. With connectionless service, in contrast, it is conceivable that a
`lost acknowledgement causes a frame to be sent several times and thus received
`several times. Connection-oriented service, in contrast, provides the network
`layer processes with the equivalent of a reliable bit stream.
`
`Page 177
`
`NETAPP ET AL. EXHIBIT 1003
`
`

`
`178 (cid:9)
`
`THE DATA LINK LAYER (cid:9)
`
`CHAP. 3
`
`When connection-oriented service is used, transfers have three distinct
`phases. In the first phase the connection is established by having both sides ini-
`tialize variables and counters needed to keep track of which frames have been
`received and which ones have not. In the second phase, one or more frames are
`actually transmitted. In the third and final phase, the connection is released, free-
`ing up the variables, buffers, and other resources used to maintain the connection.
`Consider a typical example: a WAN subnet consisting of routers connected by
`point-to-point leased telephone lines. When a frame arrives at a router, the
`hardware verifies the checksum and passes the frame to the data link layer
`software (which might be embedded in a chip on the network adaptor board). The
`data link layer software checks to see if this is the frame expected, and if so, gives
`the packet contained in the payload field to the routing software. The routing
`software chooses the appropriate outgoing line and passes the packet back down
`to the data link layer software, which then transmits it. The flow over two routers
`is shown in Fig. 3-2.
`
`Router
`
`Data link (cid:9)
`layer process (cid:9)
`
`Routing
`process
`
`1 \
`
`Frames Packets (cid:9)
`here (cid:9)
`here
`
`------------Data link
`protocol
`
`Transmission
`line to a router
`
`Fig. 3-2. Placement of the data link protocol.
`The routing code frequently wants the job done right, that is, reliable,
`sequenced connections on each of the point-to-point lines. It does not want to be
`bothered too often with packets that got lost on the way. It is up to the data link
`protocol, shown in the dotted rectangle, to make unreliable communication lines
`look perfect-,or--at least, fairly good. This property is especially important for
`wireless links, which are inherently very unreliable. As an aside, although we
`have shown multiple copies of the data link layer software in each router, in fact,
`one copy handles all the lines, with different tables and data structures for each
`one.
`Although this chapter is explicitly about the data link layer and the data link
`
`Page 178
`
`NETAPP ET AL. EXHIBIT 1003
`
`(cid:9)
`

`
`SEC. 3.1 (cid:9)
`
`DATA LINK LAYER DESIGN ISSUES (cid:9)
`
`179
`
`protocols, many of the principles we will study here, such as error control and
`flow control, are also found in transport and other protocols as well.
`
`3.1.2. Framing
`
`(Ye~f~~.v~{c~ sf- (cid:9)
`
`~s
`
`Vn ~C Gjt[Izdu ~L
`
`j (cid:9)
`
`j t/c cG~fr^ ~1
`
`In order to provide service to the network layer,-.the-data-linlE-layer-r-nusLilse
`the service provided to it by the physical layer. What the h sical la er does is
`accept a raw bit stream and aflemptio deliver it to the destination. This bit stream
`is not guaranteed to be error free. The nu mber of bits received may be less than,
`equal to, or more than the number of bits transmitted, and they may have different
`values. It is up to the data link laver test,and-if-necessar_y,. ~o ors.
`The usual approach is for the data link layer to break the bit stream up into
`discrete frames and comTute e checksum fox eachJr (Checksum algo-
`rithms will be dYSCi ~sseci later ~u1 th_s cha~ter,_Wl1en a frame arrives at the desti -
`nation the checksum is recomputed. If the newly computed checksum is different
`from the one contained in the frame, the data link layer knows that an error has
`occurred and takes steps to deal with it (e.g., discarding the bad frame and sending
`back an error report).
`Breaking the bit stream up into frames is more difficult than it at first appears.
`One way to achieve this framing is to insert time gaps between frames, much like
`the spaces between words in ordinary text. However, networks rarely make any
`guarantees about timing, so it is possible these gaps might be squeezed out, or
`other gaps might be inserted during transmission.
`Since it is too risky to count on timing to mark the start and end of each
`frame, other methods have been devised. In this section we will look at four
`methods:
`
`0 —d ),
`-1. Character count. (cid:9)
`2. Starting and ending characters, with character stuffing.
`
`( r- i
`
`3. Starting and ending flags, with bit stuffing.
`
`4. Physical layer coding violations.
`
`The first framing meth od uses a field in the header to specify the number of
`e-ehar
`characters in the frame. W en t e a a link -1 yer at t e es zn (cid:9)
`acter count, it knows how many characters follow, and hence where the end of the
`frame is. This technique is shown in Fig. 3-3(a) for four frames of sizes 5, 5, 8,
`and 8 characters respectively.
`The trouble with this algorithm is that the count can be garbled by .a, txansmis-
`sion error. For example, if the character count of 5 m the second frame of Fig. 3-
`3(b) becomes a 7, the destination will get out of synchronization and will be
`unable to locate the start of the next frame. Even if the checksum is incorrect so
`the destination knows that the frame is bad, it still has no way of telling where the
`
`Page 179
`
`NETAPP ET AL. EXHIBIT 1003
`
`

`
`THE DATA LINK LAYER
`
`CHAP. 3
`
`One character
`
`Frame 1 (cid:9)
`5 characters (cid:9)
`
`Frame 2 (cid:9)
`5 characters (cid:9)
`
`Frame 3 (cid:9)
`8 characters (cid:9)
`
`Frame 4
`8 characters
`
`Error
`
`180 (cid:9)
`
`(a)
`
`(b)
`
`Frame 1 (cid:9)
`
`Frame 2 (cid:9)
`(Wrong) (cid:9)
`
`Now a
`character count
`
`Fig. 3-3. A character stream. (a) Without errors. (b) With one error.
`next frame starts. Sending a frame back to the source asking for a retransmission
`does not help either, since the destination does not know how many characters to
`skip over to get to the start of the retransmission. For this reason, the character
`count method is rarely used anymore.
`The second framing method gets around the problem of resynchronization
`after an error by ha ving each frame start with the A $CJLchararter sequence.DLE-
`STX. and the- sequence- DLE -ETX—(DLE is Data Link Escape, STX is
`Start of TeXt, and ETX is End of TeXt.) In this way, if the destination ever loses
`track of the frame boundaries, all it has to do is look for DLE STX or DLE ETX
`characters to figure out where it is.
`A serious problem occurs with this method when binary data, such as object
`programs or floating-point numbers, are being transmitted. It may easily happen
`that the characters for DLE STX or DLE ETX occur in the data, which will inter-
`fere with the framing. One way to solve this problem is to have the sender's data
`link layer insert an ASCII DLE characte ust before _etc h "accidental" DLE
`character in the data. e ata link layer, on the receiving end removes the DLE
`before the data aregiven-to-the iletwork layer. This technique is called character
`stuffing. Thus a framing DLE STX or DLE ETX can be distinguished from one
`in tl edata by the absence or presence of a single DLE. DLEs in the data are
`always doubled. Figure 3-4 gives an example data stream before stuffing, after
`stuffing, and after destuffing.
`A major disadvantage of using this framing method is that it is closely tied to
`8-bit characters in general and the ASCII character code in particular. As net-
`works developed,-.the-disadvantages of embedding the character code in the fram-
`ing mechanism became, more-and more obvious so a new technique had to be
`developed to allow arbitrary sized characters.
`The new technique allows data frames to contain an arbitrary number of bits
`
`Page 180
`
`NETAPP ET AL. EXHIBIT 1003
`
`(cid:9)
`

`
`SEC. 3.1 (cid:9)
`
`DATA LINK LAYER DESIGN ISSUES (cid:9)
`
`181
`
`
`FA
`(a)
`
`DLE H
`
`5TX DLE (cid:9)
`
`AA (cid:9)
`
`DLE DLE (cid:9)
`
`B (cid:9)
`
`DLE ETX
`
`(b)
`
`Stuffed DLE
`
`(c) t DLEfl
`
`
`
`Fig. 3-4. (a) Data sent by the network layer. (b) Data after being character
`stuffed by the data link layer. (c) Data passed to the network layer on the re-
`ceiving side.
`
`and allows character codes with... an _arbitrary number of bits per charactex._Jt__.
`
`works like tliis. Each frame begins and end with a s pecial bit pattern, 011111 10,
`called a flag byte. Whenever the sender's data link layer encounters five consecu-
`tive ones in the data, it automatically stuffs a 0 bit into the outgoing bit stream.
`This bit stuffing is analogous to character stuffing, in which a DLE is stuffed into
`the outgoing character stream before DLE in the data.
`ed by a 0 bit
`ceiver sees flue c onsecutive incog Lb' (cid:9)
`WhenJkz
`it automaticall destuffs i.e., deletes) the 0 bit._ Just as character stuffing is com-
`pletely transparent to the network layer in both computers, so is bit stuffing. If the
`user data contain the flag pattern, 01111110, this flag is transmitted as 011111010
`but stored in the receiver's memory as 01111110. Figure 3-5 gives an example of
`bit stuffing.
`
`(a) 0 1 1 0 j1 1111 I I i i i ii 1 1 1 1' 0 0 1 0
`
`(b) 0 11 0 1 1 1 1 1 0 11 1 1 1 0 1 1 1 1 10 1 0 0 1 0
`
`Stuffed bits
`(c) 01.1 01 1 1 1 111.1 1 1 1 1 1 1 1 1 110010
`
`Fig. 3-5. Bit stuffing. (a) The original data. (b) The data as they appear on the
`line. (c) The data as they are stored in the receiver's memory after destuffing.
`
`With bit stuffing, the boundary between two frames can be unambiguously
`recognized by the flag pattern. Thus if the receiver loses track of where it is, all it
`has to do is scan the input for flag sequences, since they can only occur at frame
`boundaries and never within the data.
`The last method of framing is only applicable to networks in which the encod-
`hdaricy. For example, some LANs
`ing on the physical medium contains (cid:9)
`
`Page 181
`
`NETAPP ET AL. EXHIBIT 1003
`
`(cid:9)
`

`
`182 (cid:9)
`
`THE DATA LINK LAYER (cid:9)
`
`CHAP. 3
`
`encode 1 bit of data by using 2 physical bits. Normally, a 1 bit is a high-low pair
`and a 0 bit is a low-high pair. The combinations high-high and Iow-low are not
`used for data. The scheme means that every data bit has a transition in the mid-
`dle, making it easy for the receiver to locate the bit boundaries. This use of
`invalid physical codes is part of the 802 LAN standard, which we will study in
`Chap. 4.
`As a final note on framing, many data link protocols use a combination of a
`character count with one of the other me o extra afety. When a frame
`arrives, the count field is used to locate the end of the frame. Only if the appropri-
`ate delimiter is present at that position and the checksum is correct, is the frame
`accepted as valid. Otherwise, the input stream is scanned for the next delimiter.
`
`3.1.3. Error Control
`
`Having solved the problem of marking the start and end of each frame, we
`come to the next problem: how to make sure all frames are eventually delivered to
`the network layer at the destination, and in the proper order. Suppose that the
`sender just kept outputting frames without regard to whether they were arriving
`properly. This might be fine for unacknowledged cornectionless service but
`would most certainly not be fine for reliable, connection-oriented service.
`The usual way to ensure reliable delivery is to provide the sender with some
`feedback about what is happening at the other end of the line, Typically thepro-
`ails -for th.e-receiver to_send-back-spec-ial--control-frames-bearing..positive. or
`. negative-acknowledgements_.about-the_incoming frames. If the sender receives a
`positive acknowledgement about a frame, it knows the'r' If has arrived safely.
`On the other hand, a negative acknowledgement means that something has gone
`wrong, and the frame must be transmitted again. .
`An additional complication comes from the possibility that hardware troubles
`
`receiver will not react at all, since it h_, as no eason to-r-eact. It should be clear that
`a protocol in which the sender transmitted a frame and then waited
`for an
`acknowledgement, positive or negative, would hang forever if a frame were ever
`completely lost due to malfunctioning hardware.
`This possibility is dealt with by in troducing timers into the data link layer.
`When the sender transmits a frame, it generally also starts a timer. The timer is
`set to go off after an interval long enough for the frame to reach the destination,
`be processed there, and have the acknowledgement propagate back to the sender.
`Normally, the frame will be correctly received and the acknowledgement will get
`back before the timer runs out, in which case it will be canceled.
`However, if either the frame or the acknowledgement is lost, t he timer will go.
`off, alerting the sender to a potential problem. The obvious solution is to just
`transmit the frame again. However, when frames may be transmitted _multiple
`ties there is a danger.that the receiver will accept the same frame two or more
`
`Page 182
`
`NETAPP ET AL. EXHIBIT 1003
`
`

`
`SEC. 3.1 (cid:9)
`
`DATA LINK LAYER DESIGN ISSUES (cid:9)
`
`183
`
`times, and pass it to the network layer more than once. To prevent this from hap-
`pening, it is generally necessary to assign sequence numbers to outgoing frames,
`so that the receiver can distinguish ransmissions room originals.
`The whole issue of managing the