`
`Petitioner's Exhibit 1004
`Page 001
`
`
`
`High-Performance
`Communication
`Networks
`
`SECOND
`EDITION
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 002
`
`
`
`The Morgan Kaufma nn eries in l ~ctworking
`Series Editor, David Clark
`
`Hzgh-Perfonnance Communication Networks, 2e
`Jean Walrand and Pravin Varaiya
`
`Computer Networks: A Systems .Approach, 2e
`Larry Pecen;on and Bruce Davie
`
`lntemetworking lvfulhmedta
`Jon Crowcroft, Mark Handley, Ian 'Nakeman
`
`Understanding Networked Applications· A First Course
`Dav1d G. Messerschmill
`
`lncegrated Management of Nem.'Orketi Systems· Concepts, An::httectures,
`and the.ir Operational Application
`Heinz-Gerd Hegering, ~cbastian Abeck, a nd Bernhard Neumair
`
`Virtual Prfrate Networks: Making the Right Connection
`Dennis Fowler
`
`Networked Applications: A Guide to the New Computing Infrastructure
`David G. Mcsserschmitt
`
`Modern Cable 'TI:levzsron 'Il:chnology. Video, Voice, and Data Communicatio11s
`Walter Ciciora, James Farmer, ancl David Large
`
`Suritc11ing in IP Networks: IP Swi tclung, Tug Swrtching, and Related 'Iechnologu:s
`Bruce S Davie, Paul Doolan, and Yakov Rekhter
`
`Wide Area "letwork Design: Concepts and Tools for Optimization
`Robert S Cahn
`
`Optical Networks: A Practical Perspective
`RaJiv Ramaswami and Kumar 51, irajan
`
`Practical Computer Network Analysis and Design
`James D McCabe
`
`Frame Relay Appltcations· Business and Technology Case Studies
`James P. Cavanagh
`
`For a list of forthcoming titles, please visit our website al
`http://www.mkp.com/ publishl mann / nen~·orking.htm
`
`Supplied by the British Library 02 Dec 2020. 09 :36 (GMT )
`
`Petitioner's Exhibit 1004
`Page 003
`
`
`
`Comm u o ication
`
`SECOND
`EDITION
`
`Jean Walrand
`Pravin Varaiya
`
`r----8-R-,T-'C-f-' -11- , -v-- Berkeley
`' ''"' ' ._, ~ \
`DOCUMENT SUPPLY CENTRE
`
`Universitv of California,
`
`.; I~ 99
`
`9 9 /. 42515
`
`Morg,m Kaulm inn Publishr.rs
`San Francisco, Caltlorni.t
`
`Supplied by the British Library 02 Dec 2020, 09:36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 004
`
`
`
`S1x,nsoring &litor Jennifer Mann
`Director of Producnon and Manufaccunng Yonie Ovenon
`Production Editor Heather Collins
`Edttonal As.ststant Karyn Johnson
`Cover Design Ross Carron Design
`Th>:t De.sign, Compo51-hon, and mustrattons Wmdfoll Software
`Copyedttor Carol Leyba
`Proofreader Crin Milnes
`ind~, Tud Laux
`Pnnre, Courier Corporation
`Cover credit o Lockyer. Romilly/1ne Image Bank
`
`Morgan Kaufmann Publishers
`Edtrorilll and Sales Office
`340 Pine Street, Sixth f1oor
`San Francisco, CA 94104-3205
`USA
`'Thlephonc 415 / 392-2665
`Facsimile 41 5 982-2665
`E-mail mkp@mkp.com
`Web Stte http./luww.mkp com
`
`o 2000 by Morgan Kaufmann Publishen;
`
`All rights reserved
`Printed in lhe United States of America
`
`03 02 01 00 5 4 3 2 1
`
`No pan of this publication may be reproduced, stored in a retrieval system, or
`transmitted in any form or by any means-electronic, mec.hanicaJ, photocopying,
`recording, or otherwise-without the pnor written permission of the publisher.
`
`Library of Congress Cataloging-in-Publication Data
`Wa)rand, Jean.
`High-performance communication networks / Jean Walrancl, Pnl\'in Varaiya.
`- 2nd cd
`p. cm.-(The Morgan Kaufmann series in networking)
`Includes bibliographical references
`ISBN 1-55860-574-6
`1 Computer networks 2. Multimedia systems. :t High performance computing
`4. Asynchronous transfer mode. 5. Wireless communicat1ons systems. I. Vara1ya, P.f~
`(Pravin Pratap) U Title
`III Series.
`TKSl 05.S . W353 2000
`621 382' l -dc21
`
`99-047341
`CIP
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 005
`
`
`
`We dedicate this book
`
`to Annie and Tsabelle and Julie,
`
`and to Ruth ~
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 006
`
`
`
`xvii
`
`1
`
`Contents
`
`Preface
`
`1
`
`Overview
`1.1 History of Communication Neu~orks 5
`l 1 1 Tulephone Netwo11ts 6
`1 1 2 Compute, Nee-work
`10
`1 1 3 Cable Tulevision Networks 17
`l.1.4 Wireless Networks 19
`1 2 Networking Principle
`21
`1 2 1 D1git1zauon 21
`1.2 2 Economies ot Scale 24
`'envork E:xtemalilics 25
`l 2.3
`1.2 4 Service Integration 26
`Futu11e ~elworks 27
`1.3.1 The Internet 27
`1.3.2 Pure ATM Network 29
`l 3.3 Cable TV 29
`1.3.4 Wirele:;s 30
`1.3.5 And the Wmner Is . . .
`1.4 Summary 32
`1.5 Notes 33
`1.6
`Problems 33
`
`J.3
`
`JO
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 007
`
`
`
`Contents
`
`39
`
`VIII
`
`2
`
`2.2
`
`49
`
`Network Services and Layered Architectures
`2.1 Applications 41
`2. 1.1 \\orld Wide. Web 42
`2.1.2 Audio or Video Streams 42
`2.1.3 Voice over Packets and Vidcoconfercnces 43
`2 1 4 Networked Gan es B
`2 1.5 c I 1ent, Server 4 3
`1raffic Characterization and Quality of Service 44
`2.2.1 Const.ant Bit Rat
`45
`2.2.2 Variable Bit Rate 46
`-16
`2.2.3 Messa •es
`2.2.4 Other Requirements 47
`2.3 Netwnrk ervic.es 4 7
`2.3. l Connectio;1-0riented Service 48
`2.3.2 Connectionless Scrv1t.e 48
`2.4 High-Performance '\'.etwork
`2.·1.1 Traffic Increase 49
`2 -4 2 I ligh-Performanc:e 50
`2.5 Networ k Elements 51
`2.5.1 Principal Network Elements 51
`2.5.2 Network Elements and Sen·tc:e Characteri:..ucs 53
`2.5.3 E.x.amples 54
`2.6 Basic Network Mechan isms 56
`2 6 1 \1ultiplain 5"
`2.6 2 Switching 63
`2 3 Error Control 68
`2 6 4 Flow Control 77
`2.b.5 Congt· tion Control 78
`2.6.6 Resource Allocation 79
`Layered Architectu re 80
`2.7. 1 Layers 81
`2 7 2 lmplementltion of Laye~ 82
`2.8 Open Data Network Model 86
`2.9 Network Architectures 89
`1.10 N,!twork Bottlenecks 91
`2.11 Su mm ary 93
`2.12 ~otes 93
`2.13 Problems 93
`
`2.7
`
`Supplied by the British Library 02 Dec 2020. 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 008
`
`
`
`IX
`
`103
`
`Contents
`
`3
`
`Packet-Switched Networks
`3.1 OSI and IP Models 104
`3.1 .1 Layer l: Physical Layer 104
`3.1 2 Layer 2: Dara Link LaJer 10.5
`3.l.3 Sublayer 2a: M~dia Access Control 106
`3.1.4 Sublayer 2b: Logical Link Control 107
`3.1 5 Layer 3. Network Layer 109
`3.1.6 Layer 4. Transport Layer 110
`3.1.7 Layer 5: Session Layer 111
`3.1.8 Layer 6: Presentation Laver 112
`3.1.9 Layer 7· Application Laver 113
`11 3
`3.1.10 Summdry
`3.2 Ethernet (IEEE 802.3) 114
`3.2.1 Physical Layer 115
`3.2 2 MAC 118
`3.2.3 LLC 121
`3.2.4 LAN Tnterconneccion 122
`3.3 Token Ring ( IEEE 802.5) 127
`3.3 1 Physical Layer 128
`3.3.2 MAC 128
`3.3 3 LLC 110
`FDDI 131
`3 4
`3.5 DQDB 115
`Frame Relay 138
`3.6
`3.7
`SMD
`142
`3.7.1 Jmemetworking with SMDS 145
`Summary 147
`3 8
`3.9 Notes 149
`3.10 Problems 149
`
`4
`
`The Internet and TCP/IP Networks
`4 1 The Internet 155
`4.2 Overview of In ternet Protocols 158
`Internet Protocol 160
`4.3
`4.3. 1 1Pv4 160
`4.3.2 Multicast lP 173
`
`155
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 009
`
`
`
`Contents
`
`205
`
`X
`
`5
`
`4.4
`
`4.5
`-1.6
`
`4.3.3 Reliable Multicast 174
`4.3.4 Mobile IP 175
`4.3.5 1Pv6
`l 76
`TCP a nd UDP 178
`4.4 1 Applications 180
`4 4.2 FTP 181
`4.4.3 SMTP, rlogm, TFTP, and HTTP 182
`Internet ucce and Limitation 183
`Performance of TCP / IP Networks 18b
`4.6.1 Window Atljustmem m TCP 186
`4.6.2 Suggested Improvements for TCP 168
`4.6.3 Suggested Improvements for IP 190
`4.6 4 Queuing Algorithms 190
`4.6.5 Lahel Switchi ng 191
`4.6.6 Suggested Improvements for Other Protocols 1Y3
`4.7 Summary 196
`4.8 Notes 197
`4.9
`ProbJems 198
`
`Circuit-Switched Networks
`5.1
`Performance of Circuit-Switched etworks 208
`5.2
`SONET 211
`5.2. 1 SON ET Frame Structure 215
`5.3 Dense Wave-Division Multiplexing (DWDM) 223
`5.4
`Fiber to the Home 225
`5 4 1 The Optic'..al Loop Carner System 225
`5.4.2 Passive Optical Necworks (PONsJ 226
`5 4.3 Passive Photonic Loop (PPL) 230
`5.4.4 H)rbrid Scheme 231
`5.5 Digital Subscriber Line (DSL) 232
`5.5.1 ISDN 232
`5.5.2 ADSL 235
`Intelligent Networks 239
`5.6.l Service EX11mples 239
`5.6.2 Intelligent Network Architecture 241
`5.6.3 Funr.tion.ll Components 243
`5.7 CATV 244
`5.7.1 Lctyout 245
`
`5.6
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 010
`
`
`
`XI
`
`257
`
`Contents
`
`6
`
`5.7.2 CATV Layered Network 247
`5. 7 .3 Services over CATV 249
`5.7.4 MPEG 250
`5.8 Summary 252
`5.9 Notes 253
`5.10 Problems 254
`
`Asynchronous Transfer Mode
`6.1 Main Features of ATM 258
`6.1.l Connection-Orie nted Service 259
`6.1 .2 Fixed Cell Size 262
`6.l.3 Statistical Multiplexing 266
`6. 1.4 Allocating Resources 267
`6.2 Addressing, Signaling, and Routing 269
`6.2.1 ATM Addressing 269
`6.2.2 Signaling 270
`6.2.3 PNNI Routing 272
`6.3 ATM Header Structure 277
`6.3.1 VCl and VPl 278
`6.3.2 Other fields 280
`6.3.3 Reserved VCI/VPI 281
`6.4 ATM Adaptation Layer 282
`6.4.1 'fype 1 283
`6.4.2 'fype 2 283
`6.4.3 'fype 3/ 4 284
`6.4.4 'fype 5 285
`6.5 Management and Control 285
`6.5.1 Fault Management 287
`6.5.2 Traffic and Congestion Control 290
`6.5.3 Network Status Monitoring and Configuration 291
`6.5.4 User/ Network Signaling 292
`6.6 BISON 293
`6. 7
`lnternetworking with ATM 294
`6 7. 1 Multiprotocol Encapsulation over AAL5 295
`6.7.2 LAN Emulation over ATM 295
`6.7.3 IP over ATM 297
`6.7.4 Multiprotocol over ATM (MPOA) 300
`6.7.5 FR and SMDS over ATM 301
`6.8 Summary 301
`
`Supplied by the British Library 02 Dec 2020. 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 011
`
`
`
`XII
`
`7
`
`Contents
`
`305
`
`.l Otes 302
`6.9
`6.10 Problems 303
`
`Wireless Networks
`7.1
`Introduction 306
`7.1.1 History of Wireless Networks 306
`7.1.2 Wireless Daw Vision 309
`7.1.3 Tuchnlcal Cha llPnges 312
`7.2 The Wireless Channel 315
`7.2.1 Pach Loss 316
`7.2.2 Shadow Fading 317
`7.2.3 Multipath Flat-Fading and lntersymbol lnlerfercncc 318
`7.2 4 Doppler frequent v Shift 321
`7.2.5 Interference 321
`7.2.6 Infrared versus Radio 322
`7.2.7 Capacity Limit:, ofWucless Channels 323
`7.3 Link Level Design 324
`7.3.1 Modulation Tochniques 324
`7.3.2 Channel Coding and Link Layer Retransmission 325
`7.3.3 Flat-Fadmg Countermeasures 326
`7 .3.4 Intersymbol Interference Countermeasures 328
`7.4 Channel Access 331
`7.4.1 Multiple Acct·ss 332
`7.4.2 Random J\CCCSS 334
`7.4.3 Spectral Etiquette 337
`7.5 Network Design 337
`7 5 1 Archjtecture 337
`7.5.2 Mobility Management 339
`7 .5.3 Network Reliability 340
`7.5 4 Intemetworking 341
`7.5.5 Security 341
`7.5.6 A New Paradigm for Wireless Network Design 342
`7.6 Wireless Networks Today 343
`7.6.1 Cellular Tolephonc Systems 344
`7.6.2 Cordless Phones 348
`7.6.3 Wireless LANs 149
`7.6.4 Wide Arca Wireless Dala 5crvices 351
`7.6.S Paging Svstems 352
`7.6.6 Sacellice Networks 352
`7.6.7 Ocher \Virelc~s Systems and Applications 353
`Future Systems and Standards 354
`7.7.l Wireless wu-...:s 354
`
`7.7
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 012
`
`
`
`.. .
`XIII
`
`363
`
`Contents
`
`8
`
`7.7.2 Ad Hoc Wireless Networks 355
`7.7.3 IMT-2000 356
`7.7.4 High-Speed D1giraJ C.el1ular 357
`7.7.5 Fixed Wireless Access 357
`7.7.6 llomeRF and Bluetooth 358
`Summary 358
`7 .8
`~ates 359
`7.9
`7.10 Problems 360
`
`Control of Networks
`8.1 Objectives and Methods of Control 364
`8.1.l Overview 365
`8.1.2 Control Methods 365
`8.1.3 Time Scales 367
`8 1.4 Examples 368
`8.1.5 Quality of Service 369
`8.2 Circuit-Switch ed Networks 372
`8.2.l Blocking 372
`8.2.2 Routing Optimization 374
`8.3 Datagram Network
`378
`8.3.l Queuing Model 378
`8.3.2 Key Queuing .Result 379
`8.3 .3 Routing Optimization 381
`8.3.4 Congestion Control 387
`ATM. Networks 392
`8.4.1 Conrrol Problems 393
`8.4.2 Deterministic Approaches 395
`8.4.3 Statistical Procedures 405
`8.4.4 Deterministic or Statistical?
`8.5 Summary 424
`8.6 Notes 425
`8. 7
`Problems 426
`
`8.4
`
`-122
`
`9
`
`Control of Networks: Mathematical Background
`9.1 Markov Chains 431
`9.1.1 Overvtew 431
`9. 1.2 Discrete Time 432
`9.1.3 Continuous Time 438
`
`431
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 013
`
`
`
`XI V
`
`Contents
`
`-153
`
`9.2 Circuit-Switc hed Nenvorks 443
`9.2. l Single Switch 443
`q 2 2 Net~., ork 446
`9.3 Datagra m Networks 450
`9.3.l M/M, I Queue 450
`9.3.2 Discrete-Time Queue
`9.3.3 Jackson Network 456
`9 3.4 Buffer Occupancy for an ~MF Source 459
`9.3.5 lnsPnsttlVity of Blocking Probability 462
`9.4 ATM Networks 465
`9.4.J Determ,nisdc Approaches 466
`9.4 2 Large De\'iations ot iid Random Variables 470
`9.4 3 Str.iight-Line Large Deviations 474
`9.4.4 Large De,·iation oi a Queue 475
`9 .4.5 Bahadu r-Rao Theorem 480
`Summary 482
`9.5
`9.6 Notes 483
`9.7
`Proble m s 483
`
`10
`
`489
`
`10.2
`
`Network Economics
`10.1 De ri ve<l De mand for Ne twork Services 491
`10.1. l Jn tormation Goods 492
`10.1.2 .)ICC Rents 493
`internet en·ice Providers 494
`10.2.1 A Subscriber Demand Model 497
`10.2 2 Lmpiri<:al Evidence 501
`10.3 Necwork Charges: Theory and Prac tice 504
`10.3.1 A Resource Model 505
`10.3.2 Economic Principles 506
`10.3.:J Charges in Pracuc:e 509
`10.3 4 Vul nerability of the Internet 510
`10.4 A Billing and Provisioning System for Inte rn et Connections Sll
`lOA. l User Expenence 512
`10.4.2 Demand for Variable Qualiry 513
`10.4.3 'l11c JNDEX Billing and Provis1orung System 515
`10.4 4 Flexibilily of INDEX Pricing and Provisioning 517
`10.5 Pricing a
`inglc Resource 518
`10.5.1 USdgc-Hasecl Pnc es 520
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 014
`
`
`
`xv
`
`541
`
`575
`
`Contents
`
`11
`
`10.5.2 Congestion Prices 523
`10.5 J Cose Recovery dnd Optimum Link Capacity 526
`10.6 Pricing for ATM ervices 528
`10.6 1 A Model or ATM Resources and Services 529
`J0.6.2 Reven ue Maximi7.ation 5 J3
`10.7 Summary 535
`10.8
`ote
`536
`10.9 Problems 536
`
`Optical Networks
`11 .1 Optical Links 542
`11 1.1 1ransmitter 543
`11 1.2 Receiver 544
`11.1 .3 Fiber 546
`11 J 4 Subcarrier Mult1plexing 554
`11.2 WDM Systems 556
`11 .3 Optical Cross-Connects 557
`11.4 Optica l LAl~ s 561
`11.4.1 Single-hopLA"s 561
`11.4 2 Multihop LANs 563
`11.5 Optical Paths and ~ etworks 565
`11.5.1 Static Wavelength Assignme nt 565
`11.5.2 Dynamic. Wavelength Assign ment a nd Blocking 568
`l l .5.3 Ring Networks 569
`11 .5.4 Hierarchical Mesh Networks 570
`11 5.5 Optical Networks 571
`1L6 Summary 572
`11.7 Notes 572
`11.8 Problems 573
`
`12
`
`Switching
`12.1 Switch Performance Measures 576
`12.2 Time- and Space-Division Switc hing 580
`12.3 Modular Switch De igns 582
`12.4 Packet Switching 588
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 015
`
`
`
`XVI
`
`Contents
`
`12.S Distributed Buffer 593
`I 2.5 1 Impact of Hot Spots 596
`12.5.2 Input Buffers 598
`12 5 3 Combating I lot Spots 601
`12.5 4 Multlcasting 605
`12.6 Shared Buffer 605
`12.6.1 Multicasting 607
`I 2 6 2 Queuing Analysis 607
`12.7 Output Buffer 608
`12.7 1 Mulucastmg 608
`12.7.2 Knockout 609
`12.8 Input Buffer 610
`12.8.J HOL Blocking 611
`12.8 2 Overcoming HOL Blocking 613
`12.8.3 Multlr.asting 614
`12.9 Summary 615
`12.10 Notes 616
`12.11 Problems 617
`
`13
`
`Toward a Global Multimedia Network
`13.1 Attributes of the Globa 1 Network 620
`13.2 Technology Areas 622
`13.2.1 Architecture 623
`13.2.2 Networking 624
`13.2.3 Signal Processing 625
`13.2.4 Applications 626
`13.3 Challenges 626
`13.3 1 Arclmec.tun· 627
`13.3.2 QualityofService 628
`13.3.3 Mobility 632
`13 3.4 Heterogeneity 636
`13.3 .5 Scalability and Configurabilitv 637
`13.3.6 Extensibility and Complexity Management 639
`t J 3 7 Secunty 641
`
`Bibliography
`
`Index
`
`619
`
`643
`
`655
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 016
`
`
`
`Preface
`
`Much has changed in the networking world since 1995 when we wrote the
`first edition. "Online" and "Web" joined ulnternet" in the popular vocabulary.
`Cellular phones became as common as the telephone. The 44fast" 56 Kbps
`modem introduced with much publicity in 1998 was quickly surpassed by the
`megabit-per-second access delivered at home by cable TV and ADSL. And at
`work, 100 Mbps Ethernet came to the desktop.
`The ongoing process of network convergence today is seen in the multi(cid:173)
`billion-dollar acquisitions of cable TV operators and data networks by telephone
`companies. Service providers and equipment manufacturers are beginning to
`compete in the delivery of quality of service or QoS. That competition will
`shape the future of ATM and IP.
`Advances in wireless communication promise soon to bring "anytime, any(cid:173)
`where connectivity. Within a decade optical networking will provide orders of
`magnitude increases in bandwidth. These advances will sustain the networking
`boom of the 1990s. The social consequences of these developments are diffi(cid:173)
`cult to predict, but the technological trends are in place. We wrote the second
`edition to explain these and related technological advances, some unexpected,
`others already evident in 1995.
`
`Audience
`
`This book is a uniquely comprehensive study of the major communication
`networks: data, telephone, cable TV, and wireless. We describe the technologies
`that help create these networks, explain the protocols and control mechanisms
`that operate them, and analyze the economic principles that regulate their use
`
`Supplied by the British Library 02 Dec 2020. 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 017
`
`
`
`xvi i i
`
`Preface
`
`and evolution. We wrote the book for the professionals and students who want
`such a comprehensive view of networking
`The professionals are those in 111dustry who must cvalur1te their decisions
`in the context of the wide role> that networking plays in their organizations.
`They may be networking engineers and compute1 scfrntists and their man(cid:173)
`agers, corporate network managers and administrators operations research
`and 5ystem ~ngineers engaged in network design and operations or in up(cid:173)
`grading networking infrastructure. Their decisions often will require an under(cid:173)
`stirnding of alternative technologies and performance evaluation and a sense
`of the pace ancl direction of innovation. We believe this book will help gain
`suc:.h an understanding.
`College seniors and graduate students come to networking with training
`in dcctric engmcering, computer science, or operations research. They are at(cid:173)
`tracted to the field because of its career opportunities or because a familiarity
`,vith networking is now necessary for their own specialization in communi(cid:173)
`cations or software engineering or control. They may have taken at most one
`or, more likely, no undergraduate course in networking. This book will meet
`che diverse needs of these students and give chem a wider, more sophisticated
`appreciation of this exciting field than other books with a narrow view of net(cid:173)
`working.
`The distinction between lhese two intended audiences is only nominal.
`Today's professional was yesterday's student, and the astonishing pace of tech(cid:173)
`nical change will co morrow make him or her a student again. To cope well with
`that pace requires a comprehensive view, and that is what we believe this book
`otlers.
`
`Approach
`
`We have conducted research m networking for twenty years. For the past fifteen
`years we have taught an introductory graduate course in networking to students
`from electrical engineering, computer science. and operations research. For
`more than ten years we have offered short courses to protessionals from the
`telecommunications industry and to managers in charge of networking in
`their companies For the past five years we have had intense interactions with
`industry, as consultant and technical adviser (PV. .TW) and as entrepreneur
`(JW). This experience in research, teaching, and industry has shaped our book
`In all three contexts we find the need for comprehensiveness of coverage and
`multiple perspectives.
`Most books take a narrow vif'w of the subject and dpproach networking
`from a single perspective. 1ypicaI1y, it is identified with the Internet or ATM
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 018
`
`
`
`Preface
`
`XIX
`
`networks and described through the associated protocols. Or networks arc
`modeled as networks of queues, whose operation is explained through routing
`algorithms and queuing analyses. Or network~ arc described through their
`enabling technology: wireless communication, optics, or svntching.
`We present a comprehensive study, discussing networks as the need arises
`from the basis o t first principles from comrnunicatio11s engineering, compulc1
`science, operations research, and economics. We have minimized the use of
`advanced concepts from these disc1plines lt is our hope that the reader can thus
`gain a greater appreciation of these multiple views and a deeper understanding
`of how networks are built, how· they are used, and who will pay for them. We
`discuss questions of network performance and control in an incuitivc manner
`and, ma ~cpan1tr. chapter; we present the rigorous mathematical argument.
`
`Highlights of the
`Second Ed it ion
`
`In addition to changes and updates we have made throughout the manusr.ript,
`we would lik1; to highlight four major enhancements in the new edition. First,
`in the previous edition the Internet was treated simply as an cxamp1t· of
`packet-switched ncrwnrks. There is now a complete scudy of the Internet,
`including the TCP/ IP protocol su1ce and the advances proposed to impro,·e
`its performance or provide quality of service.
`«;econd, wireless communicat10n, absent lrom the previous edition, now
`receives an extended discussion. The growing importance of wireless tele(cid:173)
`phone access nncl its potential for use in data lnrnsfer mandated its inclusion.
`Tlurd, rapid advances in the last five years in wave-division multiplexing
`and wave-selective switching have brought forward the era of optical network(cid:173)
`ing. These Jdvances will evenrualJy change the fundamentals of nenvork de(cid:173)
`sign, operations, and economics, and so they arc described here.
`Lastl), quality of service (QoS) 1s likely to become an important cfuncnsion
`of competition among p1oviders. The ability to operate nen,vorks that can give
`QoS guarantees is also key to service integration. The economics of QoS .md
`the mechanisms needed to guarantee QoS receive much attention in the new
`edition.
`
`Contents
`
`We give a chapter by chapter outJine, pomting out the changes in the new
`edition. Chapter 1 con tams a brief historic •I account and explains the principles
`
`Supplied by the British Library 02 Dec 2020, 0936 (GMT)
`
`Petitioner's Exhibit 1004
`Page 019
`
`
`
`xx
`
`Preface
`
`of networking. Added are recent estimates of the size, growth, and trends in
`the telecommunications industry. Chapter 2 explains how network s<·rvic:.es are
`produced by layered ~rchitecturcs. A nc,~· section summarizes applications that
`are driving networking demand.
`Chapter 3 discusses packer-switched networks using the OSI model, and
`the important~~ implementations. The 100-Mbps Ethernet, and the replace(cid:173)
`ment of Ethernet hubs by intelligem Ethernet switches that can create virtual
`local area networks or VLANS, have reorganized enterprise networking. De(cid:173)
`scriptions of these innovations and gigabit Ethernets are added
`A unified treatment of the Internet and TCP/IP networks occupies Chap(cid:173)
`ter 4. Advances in Internet technology in addressing, faster switching, improve(cid:173)
`ments in the TCP IIP protocol smte, and protocol proposals that seek better
`control arc discussed
`Circuit-~witche<l net\o\·orks is the subject of Chapter 5. SONET continues to
`receive emphasis. The most significant addition is the discussion of broadband
`access networks: cable TV and ADSL, and European proposals advancing
`passive optical networks. Widespread deployment of these technologies will
`spur c:.ommercial development of broadband services.
`Chapter 6 updates the explanation of ATM with important recent work,
`including internetworking protocols MPOA, and more detailed specifications
`of PNNI routing and UNI signaling. Much of this work is focused on more
`efficient ATM support of IP. How .ATM and IP will compete and cooperate to
`provide QoS remains unresolved.
`Wireless access has exploded worldwide over the last five years. Primarily
`used for voice and short message transfers, wireless communication is begin(cid:173)
`ning to be used for data. Cha peer 7 explains the .. characteristics of wireless links
`and the challenges these characteristics pose for networking. The discussion
`explains why, unlike the convergence experienced in wirclinc networks, wire(cid:173)
`less networking is fragmented and widespread adoption of wireless technology
`for data remains uncertain.
`Chapter 8 provides an accessible discussion, and Chapter 9 explains the
`mathematical derivations, of network performance and control. The treatment
`covers circuit-switched, packet-switched, and ATM networks. Resource a11o(cid:173)
`cation (band\\-;dth and priority assignment) to achieve QoS guarantees using
`window and rate control algorithms arc dis< u5scd there. The treatment of con(cid:173)
`gestion control is novel.
`Chapter 9, devoted to economics, now has a focus based on a formulation of
`demand for network services. implementation of QoS guarantees will require
`pricing of QoS-differentiated servicc:s-a major departure from the current
`practice of flat-rate tanffs for network access. There are analyses of data about
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 020
`
`
`
`Preface
`
`xx,
`
`how users value service quality in terms of their willingness to pay. The data
`are obtained from a market trial at Berkeley that began in April 1998.
`Five years ago, wave-division multiplexing (WDM) was limited to labo(cid:173)
`ratory demonstrations. Today, backbone optical links are being upgraded by
`installing WDM equipment. WDM ]mks v. ith J tcrabit per second speed (equaJ
`to the Lraffic carried by the entire Internet today) will be sold next year. Ad(cid:173)
`vances in optical routing and switching in less than ten years will culminate in
`all-optical networks, offering orders of magnitude higher speeds ,;vith a small
`increase in cost. 11us could inaugurate another revoluuonin communications.
`WDM and optical switching are discussed in Chapter 10. The treatment of op(cid:173)
`tical links in the first edition has been abridged.
`Chapter 11 updates the discussion on fast packet switching to incorporate
`multicasting and some recent work on fast table search. Chapter 12 gives a
`revised version of the future of networking.
`
`How To Use This Book
`
`This book can be used by industry professionals, or as a text for undergraduate
`or graduate students. Professionals may studv a ropic as they need it co facili(cid:173)
`tate understanding of a particular development. An interesting undergraduate
`course can be taught around Chapters 1 through 3 and either Chapters 4 and 6,
`if the audience is primarily from computer science, or Chapters 5 and 7, if the
`students are primarily from clecoical engineering.
`We ourselves have used this material in two ways. At Berkeley, we have
`taught a one-semester, 45-hour introductory graduate course to students from
`electrical cngi'1eering computer science. and operations research. (The course
`always attracts some seniors) Students need no pnor exposure to commu(cid:173)
`nication networks-the emphasis 1s on descriptive breadth chat conveys the
`excitement of the technological advances and the challenges posed by speed,
`distance, and demanding applications. Three or four times each year we have
`taught a short course to practitioners, between 8 and 20 hours long. The aim
`there is co provide an overvie".,. of recent developments, co decipher trends,
`and to speculate about opportunities.
`
`Support Materials
`
`Our own lectures make heavy use of the figures in the book. Postscript files of
`the figures arc available from the \·Veb page for our book at hrrp·/, wuw.mkp.
`com
`
`Supplied by the British Library 02 Dec 2020, 09 36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 021
`
`
`
`..
`XXII
`
`Preface
`
`Each chapter of the book ends in problems that test understanding of the
`material and challenge the reader to use that understanding in situations that
`may arise in practice. We will keep addmg to these problems .1nd pose them at
`the Web site. A solutions manual is also available from the publisher.
`
`Acknowledgments
`
`This book synthesizes the different viewpoints of networking specialists who
`know more about each view than we do. Inevitably, errors of fact and Judgment
`and balance of trentmcmt have crept into the book. We would be very grateful
`to our readers for bringing those errors to our attention and for providing us
`with feedback about their expenences m learning or lcachmg from this book.
`We can be reached via e-mail at {wlr. uaraiya}@ee.es.bcrkt:lcy.cdu We ~m post
`corrections and comm~nts at the Web site http·l l www mkp com In th1~ second
`ed1tJ.on we have incorporated comments from instructors who have used the
`first edition.
`Andrea Goldsmith's chapter on wireless communications discusses a very
`important technology that was entirely missing in the first edit10n. We am
`greatly indebted to her for the excellenc discussion of ,1 rapidly evolving field .
`She can be reached at andrea@ee.stanford edu.
`A draft of the entire manuscript for the second edition was reviewed by
`Vijay Bhagavath, AT&T Labs; Scott Jordan, Northwestern University; Ivy Hsu,
`Nortel Networks; and Ramesh Rao, UC, San Diego. Anthony Ephremides, Uni(cid:173)
`ven;icy of Maryland, rn i, ·wed Chapte1 7, Ke\'m Fall, LC, Berkeley, reviewed
`Chapter 4 Riad Hartani ~ortcl Networks. reviewed Chapter 6; and Eytan Me(cid:173)
`diano, MIT Lincoln Laboratory, reviewed Chapter 10.
`We are immensel) grateful to them for their cnt1cisms as well as their
`suggestions for improving the book. Most of those suggestions have been
`incorporated.
`Our editor, Jennifer Mann, provided the encouragment and friendly coax(cid:173)
`ing that we needed to start work on the second edition and to bring it to
`completion. Her assistant, Karyn Johnson, helped with logistics and with her
`enthusiasm. Finally, our thanks to our production editor,! leather Collins, who
`somehow managed a very tight schedule.
`
`Supplied by the British Library 02 Dec 2020. 09:36 (GMT)
`
`Petitioner's Exhibit 1004
`Page 022
`
`
`
`7
`
`CHAPTER
`
`Wireless
`Networks
`
`uture wireless networks ·will enable people on the move to communicate
`with anyone, anyw·here, at any time, using orange of multimedia services. The
`cxponcmial growth of cellular telephone and paging systems coupled with the
`proliferation oflaptop and palmtop computers indicate a bright future for such
`netwo, ks, both as standalone systems and as part of the larger networking
`infrastructure.
`This chapter describes wireless networks. Section 7.1 provides an introduc(cid:173)
`tion to these networks, including their history ancl prospects, and the technical
`challenges of design and operation posed bv the underlying ·wireless channel.
`SP.ction 7.2 presents the main characteristics of the ·wireless channel and their
`impact on the link and network layer design. Link layer design techniques
`developed ro overcome wireless channel impairments to delivering high data
`rates with low distortion are described in Section 7.3.
`The ·wireless channel is a limited resource that is shared among many
`users. Section 7.4 is devoted to channel access protocols Section 7.5 outlines de(cid:173)
`sign issues for wireless networks, including network architecture, user location
`and routing protocols, network reliability and QoS, intemetworking between
`wireless and wired networks, and security.
`Current wireless network technology is described in Section 7.6 including
`cellular and cordless telephones, wireless LANs and wide area data services.
`paging systems, and global satellite systems. Section 7.7 gives an overview
`of emerging systems and standards for future \\ireless networks. Section 7.8
`contains a summary and a discussion of future trends.
`
`Supplied by the British Library 02 Dec 2020, 09 53 (GMT)
`
`Petitioner's Exhibit 1004
`Page 023
`
`
`
`306
`
`7.1
`
`INTRODUCTION
`
`Wireless Networks
`
`Wireless communications is the fastest growing segment of the communica(cid:173)
`tions industry. Cellular phones, con.Jlcss phones, and paging services have
`experienced exponential growLh over the last decade, and this growth con(cid:173)
`tinues unabated worldwide. Wireless communications has become a critical
`business tool and part of evcry<ldy lire in most developed countries. Wire