Larry L. Peterson & Bruce S. Davie
`
`A Systems Approach
`
`Morgan Kaufmann Publishers, Inc.
`San Francisco, California
`
`SAMSUNG 1011
`
`1
`
`

`

`Sponsoring Editor Jennifer Mann
`Production Manager Yonie Overton
`Production Editor Julie Pabst
`Editorial Assistant Jane Elliott
`Cover and Text Design Ross Carron Design
`Illustration ST Associates, Inc.
`Copyedltor Jeff Van Bueren
`Proofreader Ken DellaPenta
`Composition Ed Sznyter, Babel Press
`Indexer Steve Rath
`Printer Courier Corporation
`
`Morgan Kaufmann Publishers, Inc.
`Editorial and Sales Office
`340 Pine Street, Sixth Floor
`San Francisco, CA 94104-3205 USA
`Telephone 415/392-2665
`Facsimile 415/982-2665
`Internet mkp@mkp.com
`Order toll free 800/7 45-7323
`
`© 1996 by Morgan Kaufmann Publishers, Inc.
`All rights reserved
`Printed in the United States of America
`
`00 99 98 97 96
`
`5 4 3 2 1
`
`No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any
`form or by any means-electronic, mechanical, photocopying, recording, or otherwise-without
`the prior written permission of the publisher.
`
`Library of Congress Cataloging-In-Publication Data
`Peterson, Larry L.
`Computer networks : a systems approach / Larry L. Peterson and Bruce S. Davie.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 1-55860-368-9
`1. Computer networks.
`TK5105.5.P479 1996
`004.6'5-dc20
`
`I. Davie, Bruce S.
`
`II. Title.
`
`96-1590
`
`
`
`2
`
`

`

`CONTENTS
`
`.
`
`Foreword
`Preface
`
`1 Foundation
`Problem : Building a Network
`1. 1 Motivation
`1. 1. 1 Explosive Growth
`1. 1.2 Network Applications
`1.2 Requirements
`1.2. 1 Connectivity
`1.2.2 Cost-Effective Resource Sharing
`1.2.3 Functionality
`1.2.lt Performance
`1.3 Network Architecture
`1.3. 1 Layering and Protocols
`1.3.2 OSI Architecture
`1.3.3 Internet Architecture
`1.lt Plan for the Book
`1.lt.1 Chapter Organization
`1.lt.2 Systems Approach
`1.5 Summary
`Open Issue : Ubiquitous Networking
`Further Reading
`Exercises
`
`2 Protocol Implementation
`Problem : Protocols Have to Be Implemented
`2. 1 Object-Based Protocol Implementation
`2.2 Protocols and Sessions
`2.2. 1 Configuring a Protocol Graph
`
`vii
`xvii
`
`3
`It
`It
`5
`10
`10
`1 It
`17
`22
`29
`29
`35
`37
`39
`ltO
`,. 1
`
`lt3
`lt3
`
`,.,.
`
`lt6
`
`51
`52
`53
`55
`
`
`
`3
`
`

`

`X
`
`Contents
`
`2.2.2 Operations on Protocol Objects
`2.2.3 Operations on Session Objects
`2.2.lti Process Models for Protocols
`2.3 Messages
`2.3 . 1 Manipulating Messages
`2.3.2 Implementation
`2.lti Events
`2.lti. 1 Scheduling Timeouts
`2.lti.2 Implementation
`2.5 ldMap
`2.5.1 Demultiplexing Packets
`2.5.2 Implementation
`2.6 Example Protocol
`2.6. 1 Protocol Semantics
`2.6.2 Header Flies
`2.6.3 Initialization
`2.6.lti Opening Connections
`2.6.5 Demultiplexing Incoming Messages
`2.6.6 Sending and Receiving Messages
`2.6. 7 Closing the Connection
`2.7 Summary
`Open Issue : Cost of Network Software
`Further Reading
`Exercises
`
`3 Direct Link Networks
`Problem : Physically Connecting Hosts
`3. 1 Hardware Building Blocks
`3.1 . 1 Nodes
`3.1.2 Links
`3.2 Encoding (NRZ, NRZI, Manchester, ltiB/5B}
`3.3 Framing
`3.3.1 Byte-Oriented Protocols (BISYNC, IMP-IMP, DDCMP}
`3.3.2 Bit-Oriented Protocols (HDLC}
`3.3.3 Clock-Based Framing (SONET}
`3.lti Error Detection
`3.lti. 1 Cyclic Redundancy Check
`3.lti.2 Two-Dimensional Parity
`
`/
`
`56
`57
`59
`61
`62
`65
`66
`67
`67
`69
`70
`71
`71
`72
`72
`71ti
`75
`78
`80
`81
`82
`82
`83
`81ti
`
`89
`90
`90
`91
`91ti
`98
`98
`100
`102
`105
`106
`108
`
`
`
`4
`
`

`

`Contents
`
`3.lt.3 Internet Checksum Algorithm
`3.5 Reliable Transmission
`3.5. 1 Stop-and-Wait
`3.5.2 Sliding Window
`3 .5 .3 Concurrent Logical Channels
`3.6 CSMA/ CD (Ethernet)
`3.6. 1 Physical Properties
`3.6.2 Access Protocol
`3.6.3 Experience with Ethernet
`3.7 Token Rings (FDDI)
`3. 7 . 1 Physical Properties
`3.7.2 Timed-Token Algorithm
`3. 7 .3 Token Maintenance
`3.7.lt Frame Format
`3.8 Network Adaptors
`3.8. 1 Components
`3.8.2 View from the Host
`3.8.3 Example Device Driver
`3 .9 Summary
`Open Issue : Does It Belong In Hardware?
`Further Reading
`Exercises
`
`It Packet Switching
`Problem : Not All Machines Are Directly Connected
`lt. 1 Switching and Forwarding
`It. 1. 1 Source Routing
`lt.1.2 Virtual Circuit Switching
`lt.1.3 Datagrams
`lt.1.lt Implementation and Performance
`lt.2 Routing
`lt.2. 1 Network as a Graph
`lt.2.2 Distance Vector
`lt.2.3 Link State
`lt.2.lt Metrics
`lt.2.5 Routing, Addressing, and Hierarchy
`lt.3 Cell Switching (ATM)
`lt.3. 1 Cells
`
`xi
`
`109
`110
`111
`113
`121
`121
`122
`123
`127
`127
`128
`130
`132
`133
`13/e
`135
`136
`140
`143
`14/e
`145
`11t6
`
`151
`152
`15/t
`156
`158
`161
`162
`163
`16/e
`169
`17/t
`176
`177
`177
`
`
`
`5
`
`

`

`xii
`
`Contents
`
`,.,3.2 Segmentation and Reassembly
`,.,3.3 Virtual Paths
`,.,3,,. Physical Layers for ATM
`
`"·" Switching Hardware
`
`"·"· 1 Design Goals
`,.,,.,2 Ports and Fabrics
`,.,,.,3 Crossbar Switches
`
`"·"·" Self-Routing Fabrics
`"·"·5 Shared-Media Switches
`,.,5 Summary
`Open Issue : What Makes a Route Good?
`Further Reading
`Exercises
`
`5 lnternetworking
`Problem : There Is More than One Network
`5. 1 Bridges and Extended LANs
`5. 1. 1 Learning Bridges
`5.1.2 Spanning Tree Algorithm
`5. 1.3 Broadcast and Multicast
`5.1.,. Limitations of Bridges
`5.2 Simple lnternetworking (IP)
`5.2. 1 What Is an Internetwork?
`5.2.2 Service Model
`5.2.3 Global Addresses
`5.2,,. Datagram Forwarding in IP
`5.2.5 Address Translation (ARP)
`5.2.6 Error Reporting (ICMP)
`5.3 Global Internet
`5.3.1 Subnetting
`5 .3.2 Route Propagation (RIP, OSPF, BGP)
`5.3.3 Classless Routing (CIDR)
`5,,. Next Generation IP (1Pv6)
`5.,., 1 Historical Perspective
`5,,.,2 Addresses and Routing
`5.,.,3 1Pv6 Features
`5.5 Multicast
`5.5.1 Link-State Multicast
`
`182
`186
`187
`188
`188
`190
`192
`196
`200
`202
`202
`203
`201ti
`
`209
`210
`210
`211
`215
`216
`217
`217
`219
`229
`231
`233
`236
`237
`239
`
`2"3
`250
`252
`253
`25"
`258
`262
`263
`
`
`
`6
`
`

`

`Contents
`
`5.5.2 Distance-Vector Multicast
`5.6 Host Names (DNS)
`5.6. 1 Domain Hierarchy
`5.6.2 Name Servers
`5.6.3 Name Resolution
`5.7 Summary
`Open Issue : IP versus ATM
`Further Reading
`Exercises
`
`6 End-to-End Protocols
`Problem : Getting Processes to Communicate
`6.1 Simple Demultiplexer (UDP)
`6.2 Reliable Byte Stream (TCP)
`6 .2. 1 End-to-End Issues
`6.2.2 Segment Format
`6.2.3 Connection Establishment and Termination
`6.2.lt Sliding Window Revisited
`6.2.5 Adaptive Retransmission
`6.2.6 Record Boundaries
`6.3 Remote Procedure Call
`6.3. 1 Bulk Transfer (BLAST)
`6.3.2 Request/Reply (CHAN)
`6.3.3 Dispatcher (SELECT)
`6.3.lt Putting It All Together (SunRPC)
`6 .lt Application Programming Interface
`6.5 Performance
`6.5.1 Experimental Method
`6.5.2 Latency
`6.5.3 Throughput
`6.6 Summary
`Open Issue : Application-Specific Protocols
`Further Reading
`Exercises
`
`7 End-to-End Data
`Problem : What Do We Do with the Data?
`7. 1 Presentation Formatting
`
`xiii
`
`261a
`267
`268
`269
`272
`271a
`276
`277
`278
`
`283
`281a
`285
`286
`289
`292
`296
`301
`301a
`305
`309
`315
`321a
`326
`332
`335
`335
`336
`337
`338
`339
`3la0
`31t1
`
`3la7
`3la8
`
`
`
`7
`
`

`

`xiv
`
`Contents
`
`7. 1. 1 Taxonomy
`7. 1.2 Examples (XDR, ASN. 1, NDR)
`7.2 Data Compression
`7 .2. 1 Lossless Compression Algorithms
`7 .2.2 Image Compression (JPEG)
`7 .2.3 Video Compression (MPEG)
`7.3 Security
`7 .3.1 Secret Key versus Public Key Cryptography
`7 .3.2 Encryption Algorithms (DES, RSA)
`7.3.3 Authentication Protocols (Kerberos)
`7 .3.lt Message Integrity Protocols
`7.lt Summary
`Open Issue : Presentation-Layer of the 90s
`Further Reading
`Exercises
`
`8 Congestion Control
`Problem : Allocating Resources
`8.1 Issues In Congestion Control
`8. 1. 1 Network Model
`8. 1.2 Taxonomy
`8. 1.3 Evaluatlon Criteria
`8 .2 Queuing Dlsclpllnes
`8.2.1 FIFO
`8.2.2 Fair Queuing
`8 .3 TCP Congestion Control
`8.3.1 Additive lncrease/ Multlpllcatlve Decrease
`8.3.2 Slow Start
`8.3.3 Fast Retransmit and Fast Recovery
`8 .lt Congestion-Avoidance Mechanisms
`8.la. 1 DECblt
`8.lt.2 RED Gateways
`8.lt.3 Source-Based Congestion Avoidance
`8.5 Virtual Clock
`8.5.1 Defining Rate
`8.5.2 Virtual Clock as a Queuing Dlsclpllne
`8.5.3 Virtual Clock as a Flow Meter
`8 .5.lt Other Rate-Based Mechanisms (ABR)
`
`31t9
`353
`357
`358
`360
`36/t
`368
`369
`371
`378
`382
`385
`386
`387
`388
`
`393
`39/t
`39/t
`397
`399
`lt01
`la01
`la02
`lt06
`la06
`lt09
`la13
`lt15
`la15
`la17
`lt19
`lt21a
`la25
`lt26
`la28
`lt28
`
`
`
`8
`
`

`

`Contents
`
`8.6 Summary
`Open Issue : Inside versus Outside the Network
`Further Reading
`Exercises
`
`9 High-Speed Networking
`Problem : What Breaks When We Go Faster?
`9.1 Latencylssues
`9.1 . 1 Latency/Throughput Tradeoff
`9. 1.2 Implications
`9.2 Throughput Issues
`9.2. 1 Memory Bottleneck
`9.2.2 Techniques for Avoiding Data Transfers
`9.3 Integrated Services
`9.3. 1 New Service Model
`9.3.2 Mechanisms (RSVP)
`9.lt Summary
`Open Issue : Realizing the Future
`Further Reading
`Exercises
`
`APPENDIX Network Management
`A. 1 SNMP Overview
`A.2 MIB Variables
`A.2. 1 System Group
`A .2.2 Interfaces Group
`A.2.3 Address Translation Group
`A.2.lt IP Group
`A.2.5 TCP Group
`A.2.6 UDP Group
`
`Glossary
`References
`Index
`
`
`
`xv
`
`lt30
`lt30
`lt31
`lt32
`
`lt37
`lt38
`lt38
`lt39
`/tit 1
`ltlt2
`ltlt3
`lt50
`lt51
`lt56
`lt61t
`lt65
`lt65
`lt66
`
`lt72
`lt73
`lt11t
`lt76
`lt77
`lt78
`lt81t
`lt88
`
`lt91
`511
`521
`
`
`
`9
`
`

`

`1 O
`
`1 Foundation
`
`1.2 Requirements
`Before trying to understand how a network that supports applications like FTP, WWW, and
`NV is designed and implemented, it is important to identify what we expect from a network.
`The short answer is that there is no single expectation; computer networks are designed and
`built under a large number of constraints and requirements. In fact, the requirements differ
`widely depending on your perspective:
`■ a network user would list the services that his or her application needs, for example,
`a guarantee that each message the application sends will be delivered without error
`within a certain amount of time;
`■ a network designer would list the properties of a cost-effective design, for example,
`that network resources are efficiently utilized and fairly allocated to different users;
`and
`■ a network provider would list the characteristics of a system that is easy to administer
`and manage, for example, in which faults can be easily isolated and where it is easy
`to account for usage.
`This section attempts to distill these different perspectives into a high-level introduction to
`the major considerations that drive network design, and in doing so, identifies the challenges
`addressed throughout the rest of this book.
`
`1.2. 1 Connectivity
`Starting with the obvious, a network must provide connectivity among a set of computers.
`Sometimes it is enough to build a limited network that connects only a few select machines.
`In fact, for reasons of privacy and security, many private (corporate) networks have the explicit
`goal of limiting the set of machines that are connected. In contrast, other networks ( of which
`the Internet is the prime example), are designed to grow in a way that allows them the poten(cid:173)
`tial to connect all the computers in the world. A system that is designed to support growth
`to an arbitrarily large size is said to scale. Using the Internet as a model, this book addresses
`the challenge of scalability.
`
`Links, Nodes, and Clouds
`Network connectivity occurs at many different levels. At the lowest level, a network can con(cid:173)
`sist of two or more computers directly connected by some physical medium, such as a coaxial
`cable or an optical fiber. We call such a physical medium a link, and we often refer to the
`computers it connects as nodes. (Sometimes a node is a more specialized piece of hardware
`rather than a computer, but we overlook that distinction for the purposes of this discussion.)
`As illustrated in Figure 1.4, physical links are sometimes limited to a pair of nodes (such a
`link is said to be point-to-point), while in other cases, more than two nodes may share a single
`physical link (such a link is said to be multiple-access). Whether a given link supports point(cid:173)
`to-point or multiple- access connectivity depends on how the node is attached to the link. It
`
`
`
`10
`
`

`

`1.2. Requirements
`
`11
`
`<•> □~--□
`
`Figure 1.la Direct links: (a) point-to-point; (b) multiple-access.
`
`Figure 1.5 Switched network.
`
`is also the case that multiple-access links are often limited in size, in terms of both the geo(cid:173)
`graphical distance they can cover and the number of nodes they can connect. The exception
`is a satellite link, which can cover a wide geographic area.
`If computer networks were limited to situations in which all nodes are directly con(cid:173)
`nected to each other over a common physical medium, then networks would either be very
`limited in the number of computers they could connect or the number of wires coming out of
`the back of each node would quickly become both unmanageable and very expensive. Fortu(cid:173)
`nately, connectivity between two nodes does not necessarily imply a direct physical connec(cid:173)
`tion between them-indirect connectivity may be achieved among a set of cooperating nodes.
`Consider the following two examples of how a collection of computers can be indirectly con(cid:173)
`nected.
`Figure 1.5 shows a set of nodes, each of which is attached to one or more point-to-point
`links. Those nodes that are attached to at least two links run software that forwards data re(cid:173)
`ceived on one link out on another. If organized in a systematic way, these forwarding nodes
`
`
`
`11
`
`

`

`12
`
`1 Foundation
`
`form a switched network. There are numerous types of switched networks, of which the two
`most common are circuit-switched and packet-switched. The former is most notably employed_
`by the telephone system, while the latter is used for the overwhelming majority of computer
`networks and will be the focus of this book. The important feature of packet-switched net(cid:173)
`works is that the nodes in such a network send
`discrete blocks of data to each other. Think of
`these blocks of data as corresponding to some
`piece of application data such as a file, a piece
`of email, or an image. We call each block of
`data either a packet or a message, and for now
`we use these terms interchangeably; we discuss
`the reason they are not always the same in Sec(cid:173)
`tion 1.2.2.
`Packet-switched networks typically use a
`strategy called store-and-forward. As the name
`'--
`suggests, each node in a store-and-forward net-
`work first receives a complete packet over some
`link, stores the packet in its internal memory,
`and then forwards the complete packet to the
`next node. In contrast, a circuit-switched net(cid:173)
`work first establishes a dedicated circuit across
`a sequence of links and then allows the source
`node to send a stream of bits across this circuit
`to a destination node. The major reason for us(cid:173)
`ing packet switching rather than circuit switch(cid:173)
`ing in a computer network is discussed in the
`next subsection.
`The cloud in Figure 1.5 distinguishes be(cid:173)
`tween the nodes on the inside that implement
`the network ( they are commonly called switches
`and their sole function is to store and forward
`packets) and the nodes on the outside of the
`cloud that use the network ( they are commonly
`called hosts and they support users and run ap(cid:173)
`plication programs). Also note that the cloud
`in Figure 1.5 is one of the most important icons
`of computer networking. In general, we use a cloud to denote any type of network, whether it
`is a single point-to-point link, a multiple-access link, or a switched network. Thus, whenever
`you see a cloud used in a figure, you can think of it as a placeholder for any of the networking
`technologies covered in this book.
`
`DANs, LANs, MANs,
`andWANs
`One way to characterize networks is
`according to their size. Two well(cid:173)
`known examples are LANs (local
`area networks) and WANs (wide
`area networks)-
`the former typically
`extend less than 1 kilometer, while
`the latter can be worldwide. Other
`networks are classified as MANs
`(metropolitan area networks), which,
`as the name implies, usually span
`tens of kilometers. The reason such
`classifications are interesting is that
`the size of a network often has impli(cid:173)
`cations for the underlying technology
`that can be used, with a key factor
`being the amount of time it takes for
`data to propagate from one end of the
`network to the other; we discuss this
`issue more in later chapters.
`An interesting historical note
`is that the term wide area network
`was not applied to the first WAN s
`because there was no other sort of
`network to differentiate them from.
`When computers were incredibly rare
`and expensive, there was no point in
`
`
`
`12
`
`

`

`1.2. Requirements
`
`13
`
`A second way in which a set of computers can be indirectly connected is shown in Fig(cid:173)
`ure 1.6. In this situation, a set ofindependent networks (clouds) are interconnected to form an
`internetwork, or internet for short. We adopt the Internet's convention of referring to a generic
`internetwork of networks as a lowercase i internet, and the currently operational TCP/IP
`Internet as the capital I Internet. A node that
`is connected to two or more networks is com(cid:173)
`monly called a router or gateway, and it plays
`much the same role as a switch-it forwards
`messages from one network to another. Note
`that an internet can itself be viewed as another
`kind of network, which means that an internet
`can be built from an interconnection of inter(cid:173)
`nets. Thus, we can recursively build arbitrar(cid:173)
`ily large networks by interconnecting clouds to
`form larger clouds.
`Just because a set of hosts are directly
`or indirectly cpnnected to each other does not
`mean that we have succeeded in providing
`host-to-host connectivity. The final require(cid:173)
`ment is that each node must be able to say
`which of the other nodes on the network it
`wants to communicate with. This is done by
`assigning an address to each node. An address is
`a byte string that identifies a node; i.e., the net(cid:173)
`work can use a node's address to distinguish it
`from the other nodes connected to the network.
`When a source node wants the network to de-
`liver a message to a certain destination node, it
`specifies the address of the destination node. If
`the sending and receiving nodes are not directly
`co.nnected, then the switches and routers of the
`network use this address to decide how to for(cid:173)
`ward the message toward the destination. The
`process of determining systematically how to
`forward messages toward the destination node
`based on its address is called routing. _
`This brief introduction to addressing and routing has presumed that the source node
`wants to send a message to a single destination node (unicast). While this is the most common
`scenario, it is also possible that the source node might want to broadcast a message to all the
`nodes on the network. Or a source node might want to send a message to some subset of
`
`thinking about how to connect all
`the computers in the local area-there
`was only one computer in that area.
`Only as computers began to prolifer(cid:173)
`ate did LANs become necessary, and
`the term WAN was then introduced
`to describe the larger networks that
`interconnected geographically distant
`computers.
`One of the most intriguing kinds
`of networks that is gaining attention
`today is the DAN ( desk area net(cid:173)
`work). The idea of a DAN is to
`open up the computer setting on your
`desk and to treat each component
`of that computer--e.g., its display,
`disk, CPU, as well as peripherals like
`cameras and printers--as a network(cid:173)
`In essence, the
`accessible device.
`I/0 bus is replaced by a network (a
`DAN) that can, in turn, be intercon(cid:173)
`nected to other LANs, MANs, and
`WANs. Establishing this intercon(cid:173)
`nection provides uniform access to all
`the resources that might be required
`by a network application.
`
`
`
`13
`
`

`

`1 Foundation
`
`Figure 1.6 Interconnection of networks.
`
`►
`
`the other nodes, but not all of them, a situation called multicast. Thus, in addition to node(cid:173)
`specific addresses, another requirement of a network is that it support multicast and broadcast
`addresses.
`The main thing to take away from this discussion is that we can define a network re(cid:173)
`cursively as consisting of two or more nodes connected by a physical link, or as two or more
`networks connected by one or more nodes. In other words, a network can be constructed
`from a nesting of networks, where at the bottom level, the network irmplemented by some
`physical medium. One of the key challenges in providing network connectivity is to defi11e
`an address for each node that is reachable on the network (including support for broadcast
`and multicast connectivity), and to be able to use thi~ address to route messages toward the
`appropriate destination node(s).
`
`1.2.2 Cost-Effective Resource Sharing
`As stated above, this book focuses on packet-switched networks. This section explains the key
`requirement of computer networks-in short, efficiency-that leads us to packet switching as
`the strategy of choice.
`Given a collection of nodes indirectly connected by a nesting of networks, it is possible
`for any pair of hosts to send messages to each other across a sequence of links and nodes. Of
`course, we want to do more than support just one pair of communicating hosts-we want to
`provide all pairs of hosts with the ability to exchange messages. The question, then, is how
`do all the hosts that want to communicate share the netwprk, especially if they want to use it
`at the same time? And, as if that problem isn't hard enough, how do several hosts share the
`same link when they all want to use it at the same time?
`
`
`
`14
`
`

`

`1,2, Requirements
`
`15
`
`....
`....
`....
`
`7
`
`~
`
`Switch 1
`
`L
`
`....
`....
`"--
`
`Switch 2
`
`Figure 1.7 Multlplexlng multiple loglcal flows over a single physical link.
`
`To understand how hosts share a network, we need to introduce a fundamental concept,
`multiplexing, which means that a system resource is shared among multiple users. At an intu(cid:173)
`itive level, multiplexing can be explained by analogy to a timesharing computer system, where
`a single physical CPU is shared (multiplexed) among multiple jobs, each of which believes it
`has its own private processor. Similarly, data being sent by multiple users can be multiplexed
`over the physical links that make up a network.
`To see how this might work, consider the simple network illustrated in Figure 1. 7, where
`the three hosts on the left side of the network are sending data to the three hosts on the right
`by sharing a switched network that contains only one physical link. (For simplicity, assume
`that the top host on the left is communicating with the top host on the right, and so on.)
`In this situation, three flows of data-corresponding to the three pairs of hosts-are multi(cid:173)
`plexed onto a single physical link by Switch 1 and then demultiplexed back into separate flows
`by Switch 2. Note that we are being intentionally vague about exactly what a "flow of data"
`corresponds to. For the purposes of this discussion, assume that each host on the left has a
`large supply of data(mat it wants to send to its counterpart on the right.
`There are several different methods for multiplexing multiple flows onto one physical
`link. One method, which is commonly used in the telephone network, is synchronous t ime(cid:173)
`division multiplex ing (STDM). The idea ofSTDM is to divide time into equal-sized quanta,
`and in a round-robin fashion, give each flow a chance to send its data over the physical link.
`In other words, during time quantum 1, data from the first flow is transmitted; during time
`quantum 2, data from the second flow is transmitted; and so on. This process continues until
`all the flows have had a turn, at which time the first flow gets to go again, and the process re(cid:173)
`peats. Another common method is frequency -div ision multiplexing (FDM). The idea ofFDM
`is to transmit each flow over the physical link at a different frequency, much the same way that
`the signals for different TV stations are transmitted at a different frequency on a physical cable
`TV link.
`Although simple to understand, both STDM and FDM are limited in two ~ays. First,
`if one of the flows (host pairs) does not have any data to send, its share of the physical link(cid:173)
`i.e., its time quantum or its frequency-remains idle, even if one of the other flows has data
`to transmit. For computer communication, the amount of time that a link is idle can be very
`
`
`
`15
`
`

`

`16
`
`1 Foundation
`
`large-for example, consider the amount of time you spend reading a Web page (leaving the
`link idle) compared to the time you spend fetching the page. Second, both STDM and FDM
`are limited to situations in which the maximum number of flows is fixed and known ahead of
`time. It is not practical to resize the quantum or to add additional quanta in the case of STD M
`or to add new frequencies in the case ofFDM.
`The form of multiplexing that we make most use of in this book is called statistical mu!-
`- tiplexing. Although the name is not all that helpful for understanding the concept, statistical
`multiplexing is really quite simple; it involves two key ideas. First, it is like STDM in that
`the physical link is shared over time-first data from one flow is transmitted over the physical
`link, then data from another flow is transmitted, and so on. Unlike STDM, however, data is
`transmitted from each flow on demand rather than during a predetermined time slot. Thus,
`if only one flow has data to send, it gets to transmit that data without waiting for its quantum
`to come around and thus without having to watch the quanta assigned to the other flows go
`by unused. It is this avoidance of idle time that gives packet switching its efficiency.
`As defined so far, however, statistical multiplexing has no mechanism to ensure that all
`the flows eventually get their turn to transmit over the physical link. That is, once a flow be(cid:173)
`gins sending data, we need some way to limit the transmission, so that the other flows cap
`have a turn. To account for this need, statistical multiplexing defines an upper bound on the
`·size of the block of data that each flow is permitted to transmit at a given time. This limited(cid:173)
`size block of data is typically referred to as a packet, to distinguish it from the arbitrarily large
`message that an application program might want to transmit. The fact that a packet-switched
`network limits the maximum size of packets means that a host may not be able to send a com(cid:173)
`plete message in one packet-the source may need to fragment the message into several pack(cid:173)
`ets, with the receiver reassembling the packets back into the original message.
`In other words, each flow sends a sequence of packets over the physical link, with a
`decision made on a packet-by-packet basis as to which flow's packet to send next. Notice that
`if only one flow has data to send, then it can send a sequence of packets back to back. However,
`should more than one of the flows have data to send, then their packets are interleaved on the
`link. Figure 1.8 depicts a switch multiplexing packets from multiple sources onto a single
`shared link.
`The decision as to which packet to send next on a shared link can be made in a number
`of different ways. For example, in a network consisting of switches interconnected by links
`such as the one in Figure 1. 7, the decision would be made by the switch that transmits packets
`onto the shared link. (As we will see later, not all packet-switched networks actually involve
`switches, and they may use other mechanisms to determine whose packet goes onto the link
`next.) Each switch in a packet-switched network makes this decision independently, on a
`packet-by-packet basis. One of the issues that faces a network designer is how to make this
`decision in a fair manner. For example, a switch could be designed to service the different
`flows in a round-robin manner, just as in STDM. However, statistical multiplexing does not
`
`
`
`16
`
`

`

`1.2. Requirements
`
`17
`
`"' 'III
`
`C:=JC:=J-
`
`...
`
`C:=JC:=J
`
`,
`~
`
`Figure 1.8 A switch multiplexing packets from multiple sq_urces onto one shared link.
`
`require a round-robin approach. In fact, another equally valid choice would be to service each
`fl.ow's packets on a first-in-first-out (FIFO) basis.
`Also, notice in Figure 1.8 that since the switch has to multiplex three incoming packet
`streams onto one outgoing link, it is possible that the switch will receive packets faster than
`the shared link can accommodate. In this case, the switch is forced to buffer these packets
`in its memory. Should a switch receive packets faster than it can send them for an extended
`period of time, then the switch will eventually run out of buffer space, and some packets will
`have to be dropped. When a switch is operating in this state, it is said to be congested:
`The bottom line is that statistical multiplexing defines a cost-effective way for multiple
`users (e.g., host-to-host flows of data) to share network resources (links and nodes) in a fine(cid:173)
`grained manner. It defines the packet as the granularity with which the links of the network
`are allocated to different flows, with each switch able to schedule the use of the physical links
`it is connected to on a per-packet basis. ~airly allocating link capacity to different flows and
`dealing with congestion when it occurs are the key challenges of statistical multiplexing.
`I
`
`►
`
`1.2.3 Functionality
`While the previous section outlined the challenges involved in providing cost-effective con(cid:173)
`nectivity among a group of hosts, it is overly simplistic to view a computer network as simply
`delivering packets among a collection of computers. It is more accurate to think of a net(cid:173)
`work as providing the means for a set of application processes that are distributed over those
`computers to communicate. In other words, the next requirement of a computer network is
`that the application programs running on the hosts connected to the network must be able to
`communicate in a meaningful way.
`
`
`
`17
`
`

`

`28li
`
`6 End-to-End Protocols
`
`6. 1 Simple Demultiplexer (UDP)
`The simplest possible transport protocol is one that extends the host-to-host delivery service
`of the underlying network into a process-to-process communication service. There are likely
`to be many processes running on any given host, so the protocol needs to add a level of demul(cid:173)
`tiplexing, thereby allowing multiple application processes on each host to share the network.
`Aside from this requirement, the transport protocol adds no other functionality to the best(cid:173)
`effort service provided by the underlying network. The Internet's User Datagram Protocol
`(UDP) is an example of such a transport protocol. So is A Simple Protocol (ASP) described
`in Chapter 2.
`The only interesting issue in such a protocol is the form of the address used to identify
`the target process. Although it is possible for processes to directly identify each other with
`an OS-assigned process id (pid), such an approach is only practical in a "closed" distributed
`system in which a single OS runs on all hosts and assigns each process a unique id. A more
`common approach, and the one used by both ASP and UDP, is for processes to indirectly iden(cid:173)
`tify each other using an abstract locater, often called a port or mailbox. The basic idea is for a
`source process to send a message to a port and for the destination process to receive the mes(cid:173)
`sage from a port.
`The header for an end-to-end protocol that implements this demultiplexing function
`typically contains an identifier (port) for both the sender (source) and the receiver (destina(cid:173)
`tion) of the message. For example, the UDP header is given in Figure 6.1. Notice that the
`UDP port field is only 16 bits long. This means that there are up to 64-K possible ports,
`clearly not enough to identify all the processes on all the hosts in the Internet. Fortunately,
`ports are not interpreted across the entire Internet, but only on a single host. That is, a pro(cid:173)
`cess is really identified by a port on some particular host-a (port, host) pair. In fact, this pair
`constitutes the demultiplexing key for the UDP protocol.
`The next issue is how a process learns the port for the process to which it wants to send
`a message. Typically, a client proce