eoition A
`
`
`
`COMPUTER
`NETWORKS
`
`A SYSTEMS APPROACH
`
`LARRY L. PETERSON & BRUCE S. DAVIE
`
`
`
`Data Co Exhibit 1033
`AMSTERDAMe BOSTON « HEIDELBERG e LONDON Lal < Data Co Exhib " »
`ibit 1033
`Data Co v. Bright Data
`NEWYORK ¢ OXFORD e PARIS # SAN DIEGO
`Data Co v. Bright
`Data
`SAN FRANCISCO « SINGAPORE # SYDNEY « TOKYO
`Morgan KaufmannPublishers is an imprint of Elsevier
`MORGAN KAUFMANN PUBLISHERS
`
`‘
`
`

`

`Acquisitions Editor
`Publishing Services Manager
`Production Editor
`Associate Acquisitions Editor
`Design Direction
`Composition
`Copyeditor
`Proofreader
`dndexer
`interior printer
`Coverprinter
`
`Rick Adams
`George Morrison
`Dawnmarie Simpson
`Rachel Roumeliotis
`Louis Forgione
`VTEX
`Multiscience Press, Inc.
`Jodie Allen
`Multiscience Press, Inc.
`Courier Westford
`Phoenix Color, Inc.
`
`Morgan Kaufmann Publishers is an imprintof Elsevier.
`500 SansomeStreet, Suite 400, San Francisco, CA 94111
`
`This bookis printed on acid-free paper.
`
`© 2007, Elsevier, Inc. All rights reserved.
`Designations used by companies to distinguish cheir products are often claimed as trademarks or registered trademarks. Inall
`instances in which Morgan Kaufmann Publishers is aware of a claim, che product names appearin initial capical orall capital
`letters. Readers, however, should comtacr the appropriate companies for more complete information regarding trademarks and
`registration.
`No partof this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—
`electronic, mechanical, photocopying, scanning, or otherwise—without prior written permission of the publisher.
`Permissions may be sought directly ftam Elsevier's Science & Technology Rights Department in Oxford, UK: phone: (44)
`1865 843830, fax: (+44) 1865 853333, E-mail: permiissions@elsevier.com, You may also complete your request online via the
`Elsevier homepage (Attp:/ebevier.com), byselecting “Support 8 Contact” then “Copyright and Permission” and then “Obtaining
`Permissions.”
`
`ISBN 13: 978-0-12-370548-8 (Case bound)
`ISBN 10: 0-12-370548-7 (Case bound)
`
`ISBN 13: 978-0-12-374013-7 (Paperback)
`ISBN 10: 0-12-374013-4 (Paperback)
`Library of Congress Cataloging-in-Publication Data
`Peterson, LarryL.
`Computer networks ; a systems approach / Larry L. Peterson & Bruce S.
`Davi — 4th ed.
`p.cm.
`Includes bibliographical references and index.
`ISBN-13: 978-0-12-370548-8 (hardcover: alk. paper)
`ISBN-10: 0-12-370548-7 (hardcover : alk. paper)
`ISBN-13: 978-0-12-374013-7 (pbk.: alk. paper)
`ISBN-10: 0-12-374013-4 (pbk. : alk. paper)
`1. Computer networks.
`Davie, Bruce S. II. Title.
`TK5105.5.P479 2007
`004.6°5-de22
`
`I.
`
`2006102454
`
`For information on all Morgan Kaufmann publications, visit our
`Web site ar ww akp.com or wow. books, ebevier. com
`Printed in the United States of America.
`06 07 08 09
`10
`5432 ]
`
`~ Working together to grow
`libraries in developing countries
`www.elsevier.com | www.bookaid.org | www.sabre.org
`
`International
`
`ELSEVIER
`
`BEOKAID
`
`Sabre Foundation
`
`

`

`4
`
`1 Foundation
`
`1.1 Applications
`Most people know the Internet throughits applications: the World Wide Web, email,
`streaming audio and video, chat rooms, and music(file) sharing. The Web, for example,
`presents an intuitively simple interface. Users view pages full of textual and graphical
`objects, click on objects that they want to learn more about, and a corresponding new
`page appears. Most peopleare also aware that just under the covers, each selectable object
`on a page is boundto an identifierfor the next page to be viewed. This identifier, called a
`Uniform Resource Locator (URL), is used to provide a way ofidentifyingall the possible
`pages that can be viewed from your web browser. For example,
`
`http://www.cs.princeton.edu/~llp/index.html
`
`is the URL for a page providing information about one ofthis book’s authors: the string
`http indicates that the HyperText Transfer Protocol (HTTP) should be used to down-
`load the page, Www.cs.princeton.edu is the name of the machine that serves the
`page, and
`
`/~I|p/index.html
`
`uniquely identifies Larry's homepageat thissite.
`What most Web users are not aware of, however, is that by clicking on just one such
`URL, as many as 17 messages may be exchanged over the Internet, and this assumes
`the pageitself is small enough to fit in a single message. This numberincludes up to
`six messages to translate the server name (WWW.cSs.princeton.edu) into its Internet
`address (128.112.136.35), three messages to set up a Transmission Control Protocol
`(TCP) connection between your browserandthisserver, four messages for your browser
`to send the HTTP “get” request and theserver to respond with the requested page (and
`for each side to acknowledge receipt of that message), and four messages to tear down the
`TCP connection. Of course, this does not include the millions of messages exchanged
`by Internet nodes throughout the day, just to let each other know that they exist and
`are ready to serve web pages, translate names to addresses, and forward messages toward
`their ultimate destination.
`Another widespread application of the Internetis the delivery of “streaming” audio
`and video. While an entire video file could first be fetched from a remote machine and
`then played on the local machine, similar to the process of downloading and displaying
`a web page, this wouldentail waiting for the last second ofthevideo file to be delivered
`before starting to look at it. Streaming video implies that the sender and the receiver
`are, respectively, the source and thesink for the video stream. That is, the source gener-
`ates a video stream (perhaps using a video capture card), sends it across the Internetin
`messages, and the sink displays the stream asit arrives.
`
`

`

`i
`
`1.1 Applications
`
`5
`
`There are a variety of different classes of video applications. Oneclass of video ap-
`plication is video-on-demand, which reads a preexisting movie from disk and transmits
`it over the network. Anotherkind of application is videoconferencing, whichis in some
`ways the morechallenging (and, for networking people, interesting) case becauseit has
`very tight timing constraints. Just as when using the telephone, the interactions among
`the participants must be timely. When a person at one end gestures, then that action
`must be displayed at the other end as quickly as possible. Too much delay makes the
`system unusable. Contrast this with video-on-demand where, if it takes several seconds
`from the timethe user starts the video until the first imageis displayed, the serviceis still
`deemedsatisfactory. Also, interactive video usually implies that videois flowing in both
`directions, while a video-on-demandapplicationis mostlikely sending video in onlyone
`direction.
`One pioneering example of a videoconferencing tool, developed in the early and
`mid-1990s, is vic. Figure 1.1 shows the control panel for a vic session. vic is actually
`
`* beretchecelale padec com
`192.6.28284peg
`9 T4f/o 1.Mb/a G45)
`4 color=stallsmule
`
`
`
`PModes,,. Oigmisa
`
`Steven McCanne (LBL)
`mccain) 128.3.112.153/261
`B1Vo S0kb/s
`(0%)
`“mile ° color
`
`slals
`
`‘qo yetye | Elan Amir (UC Berkeley)
`t
`~
` elanen1282.33.50;n261
`S.A f's UWikb’o
`(355)
`“anilie
`color
`stats
`
`VIC v2 Jal
`
`(Menu Help Quit
`
`—
`Size,
`
`.
`Modes... Dismiss |
`
`-
`Site...
`
`|
` Modes,, Dismiss
`
`Transmission
`
`- Transmit:
`‘Lack
`Release
`
`Hate Control
`i
`
`i
`
`i
`
`SIKB/s
`9103s
`fs kbps
`FE 10 tes
`
`Device...
`Port_.
`
`Stir
`
`Quality
`
`Encoder
`
`ny
`C
`
`Session
`
`feta
`h261
`
`nipig
`
`Sis]
`
`mall
`nomial
`
`larye
`
`20
`
`Deal: 224.2886 Port 188& ID 2955997023 TTL: 40
`
`Hame: Stevan ifeCahe (LBL)
`Koy
`
`Paute Mew Sources
`
`Sending Slides
`
`‘Tiler, .
`
`Members
`
`Colors
`
`Dismiss
`
`Size,,
`
`Figure 1.1 The vic video application. This shot is from a 1995 release of thetool.
`
`

`

`6
`
`1 Foundation
`
`one ofa suite of conferencing tools designed at Lawrence Berkeley Laboratory and UC
`Berkeley. The others include a whiteboard application (Wb) that allows users to send
`sketches and slides to each other, a visual audio tool called vat, and a session directory
`(sdr) thatis used to create and advertise videoconferences. All these tools run on Unix—
`hence their lowercase names—andarefreely available on the Internet. Many similar tools
`are available for other operating systems.It is interesting to note that while video over the
`Internetis still considered to be in its relative infancy at the time of this writing (2006),
`that the tools to support video over IP haveexisted for well over a decade.
`Although they are just two examples, downloading pages from the Web and partic-
`ipating in a videoconference demonstrate the diversity of applications that can be built
`on top of the Internet, and hint at the complexity of the Internet's design. Starting from
`the beginning, and addressing one problem attime, the rest of this book explains how
`to build a network that supports such a wide range of applications. Chapter 9 concludes
`the book by revisiting these two specific applications, as well as several others that have
`becomepopular on today’s Internet.
`
`1.2 Requirements
`We havejust established an ambitious goal for ourselves: to understand how to build a
`computer network from the ground up. Our approach to accomplishingthis goal will
`be to start from first principles, and then ask the kinds of questions we would naturally
`ask if building an actual network. At each step, we will use today’s protocols to illustrate
`various design choices available to us, but we will not accept these existing artifacts as
`gospel, Instead, we will be asking (and answering) the question of why networks are
`designed the way they are. While it is tempting to settle for just understanding the way
`it’s done today,it is important to recognize the underlying concepts because networks are
`constantly changing as the technology evolves and new applications are invented.Icis
`our experience that once you understand the fundamental ideas, any new protocol that
`you are confronted with will be relatively easy to digest.
`The first step is to identify the set of constraints and requirements that influence
`network design. Before getting started, however, it is important to understand that the
`expectations you have of a network depend on your perspective:
`
`M An application programmer would list the services that his application needs, for
`example, a guarantee that each message the application sends will be delivered
`‘* without error within a certain amountoftime.
`
`B A network designer wouldlist the properties of a cost-effective design, for exam-
`ple, that network resources are efficiently utilized and fairly allocated to different
`users,
`
`

`

`2.8 Wireless
`
`133
`
`SONETandthe physical layer specified for Ethernet. This saved the designers the time
`and effort of developing their own physical layer specs and hardware—a goodexample
`of the value of layered architectures.
`
`|
`_
`
`|
`
`2.8 Wireless
`Wireless technologies differ in a variety of dimensions, most notably in how much band-
`width they provide and how far apart communicating nodes can be. Other importantdif-
`ferences include which part of the electromagnetic spectrum theyuse (including whether
`
`it requires a license
`) and how much power they consume(important for mobile nodes).
`In this section we discuss four promi-
`
`nent wireless
`technologies: Bluetooth,
`
`
` to string cables in a hub-and-spoke
`Wi-Fi (more formally known as 802.11),
`WiMAX (802.16), and third-generation
`or 3G cellular wireless. In the following
`sections we present them in order from
`shortest range to longest. Table 2.6 gives
`an overview of these technologies and
`howtheyrelate to each other.
`The most widely used wireless links
`today are usually asymmetric, that is, the
`two endpointsare usually different kinds
`of nodes. One endpoint, sometimes de-
`scribed as the base station, usually has no
`mobility, but has a wired (or at least high
`bandwidth) connection to the Internet or
`other networks as in Figure 2.38. The
`nodeat the other end of the link—shown
`here as a “client node”—is often mobile,
`and relies on its link to the base sta-
`tion forall its communication with other
`nodes.
`in Figure 2.38 we
`Observe that
`have used a wavy pair oflines to repre-
`sent the wireless “link” abstraction pro-
`vided between twodevices(e.g., between _
`a base station and oneofits client nodes).
`Oneoftheinteresting aspects of wireless
`
`manner from a central switch to each
`workstation, a ring actually provides
`a very cost-effective way to intercon-
`nect nodes in a MAN, where the cost
`of obtaining rights-of-way and lay-
`ing fiber can be significant. The re-
`siliency of a ring is also attractive in
`this environment—the fact that you
`have both a “clockwise” and an “coun-
`terclockwise” path between any two
`points ensures that a single fiber cut
`wont cut off a customer. RPR was also
`developed with some fairness mech-
`anisms that ensure that a node's lo-
`
`
`cation on the ring doesn’t put it at
`an unfair advantage or disadvantage
`
`to another node in another location
`
`whenit comesto getting access to the
`bandwidcth—this is harder to achieve
`with Ethernet. Thus, while there is
`certainly plenty of momentum behind
`
`Ethernet in the MAN,it is probably
`
`too soonto predict the demise of RPR
`in this environment.
`
`
`
`
`

`

`134
`
`2 Direct Link Networks
`
`
`
`
`
`USB
`
`Wired technol-
`ogy analogy
`
` Bluetooth
`
`802.15.1 Wi-Fi 802.11
`3G Cellular
`
`Tens of km
`Typical link
`10m
`
`length
`
`
`
`2.1 Mbps
`Typical
`54 Mbps
`70 Mbps
`384+ Kbps (per
`(shared)
`bandwidth
`(shared)
`(shared)
`connection)
`
`
`
`
`
`Typical use Link a building|Link a cellLink a Link a
`
`
`
`notebook
`peripheral to a to a wired tower|phone toa
`
`
`
`
` notebook
`computer toa
`wired tower
`
` computer
`wired base
`
`
`
` Ethernet
`
`
`Coaxial cable
`
`
`Table 2.6 Overview of leading wireless technologies.
`
`————
`
`
`
`
`
`Client
`node
`
`
`
`Client
`node
`
`i Wired
`sii a Base
`
`network
`
`\
`J
`_
`
`station
`
`between 2 nodes
`
`Wireless “link”
`
`Figure 2.38 A wireless network using a base station,
`
`
`
`

`

`2.8 Wireless
`
`135
`
`
`
`Mobile node
`
`
`
`Mobile node}
`
`Figure 2.39 A wireless ad hoc or mesh network.
`
`communication is that it naturally supports point-to-multipoint communication, be-
`cause radio waves sent by one device can be simultaneously received by many devices.
`However, it is often useful to create a point-to-point link abstraction for higher-layer
`protocols, and we will see examples of how this works later in this section.
`Notethat in Figure 2.38, communication between nonbase (client) nodesis routed
`via the base station. This is in spite of the fact that radio waves emitted by one client node
`may weil be received by otherclient nodes—the common base station model does not
`permit direct communication between the client nodes.
`This topology implies three qualitatively different levels of mobility. Thefirst level
`is no mobility, such as when a receiver must bein a fixed location to receive a directional
`transmission from the basestation, as is the case with the initial version of WiMAX. The
`second level is mobility within the range of a base, as is the case with Bluetooth. The
`third level is mobility between bases, as is the case with cell phones and Wi-Fi.
`An alternative topology that is seeing increasing interest is the mesh or ad hoc net-
`work. In a wireless mesh, nodes are peers (i.e., there is no special base station node).
`Messages may be forwarded via a chain of peer nodes as long as each node is within
`range of the preceding node. This is illustrated in Figure 2.39. This allows the wireless
`Portion ofa network to extend beyond thelimited range of a single radio. From the point
`of view of competition between technologies, this allows a shorter-range technology to
`
`

`

`136
`
`2 Direct Link Networks
`
`extend its range and potentially compete with a longer-range technology. Meshes also
`offer fault tolerance by providing multiple routes for a message to get from point A to
`point B. A mesh network can be extended incrementally, with incremental costs. On
`the other hand, a mesh requires nonbase nodesto have a certain level of sophistication
`in their hardware and software, potentially increasing per-unit costs—and power con-
`sumption,a critical consideration for battery-powered devices. Wireless mesh networks
`are of considerable research interest, but they arestill in their relative infancy compared
`to networks with base stations, and thus we do not cover them further here.
`We now turn our attention to the details of the four wireless technologies men-
`tioned above, beginning with the most short-range technology, Bluetooth.
`
`2.8.1 Bluetooth (802.15.1)
`Bluetooth fills the niche of very short-range communication between mobile phones,
`PDAs, notebook computers, and other personalor peripheral devices. For example, Blue-
`tooth can be used to connect a mobile phoneto a headset, or a notebook computer to a
`printer. Roughly speaking, Bluetooth is a more convenientalternative to connecting two
`devices with a wire. In such applications, it is not necessary to provide much range or
`bandwidth. This is fortunate for some of the target battery-powered devices, since it is
`important that they not consume much power.
`Bluetooth operates in the license-exempt band at 2.45 GHz.It has a range of only
`about 10 m.Forthis reason, and because the communicating devices typically belong to
`one individual or group, Bluetooth is sometimes categorized as a personal area network
`(PAN). Version 2.0 provides speeds up to 2.1 Mbps. Power consumptionis low.
`Bluetooth is specified by an industry consortium called the Bluetooth Special Inter-
`est Group. It specifies an entire suite of protocols, going beyond thelink layer to define
`application protocols, which it calls profiles, for a range of applications, For example,
`there is a profile for synchronizing a PDA with a personal computer. Anotherprofile
`gives a mobile computeraccess to a wired LAN in the mannerof 802.11, although this
`was not Bluetooth’s original goal. The IEEE 802.15.1 standard is based on Bluetooth
`but excludes the application protocols.
`The basic Bluetooth network configuration, called apiconet, consists ofa master de-
`vice and upto seven slave devices, as in Figure 2.40. Any communication is between the
`master and a slave; the slaves do not communicate directly with each other. Because slaves
`have a simplerrole, their Bluetooth hardware and software can be simpler and cheaper.
`Singe Bluetooth operates in an license-exempt band,it is required to use a spread
`spectrum technique (as discussed in Section 2.1.2) to deal with possible interference
`in the band. It uses frequency hopping with 79 channels (frequencies), using each for
`625 jm at a time. This provides a natural time slot for Bluetooth to use for synchronous
`time division multiplexing. A frame takes up 1, 3, or 5 consecutive time slots. Only
`
`

`

`2.8 Wireless
`
`137
`
`(active)
`
`Slave
`{active)
`
`Slave
`(active)
`
`(active)
`
`Slave
`
`
`
`Slave
`
`Figure 2.40 A Bluetooth piconet.
`
`the master can start to transmit in odd-numberedslots. A slave can start to transmit in
`an even-numbered slot, but only in response to a request from the master during the
`previousslot, thereby preventing any contention between theslave devices.
`A slave device can be parked:set to an inactive, low-powerstate. A parked device
`cannot communicate onthe piconet; it can only be reactivated by the master. A piconet
`can have up to 255 parked devices in additiontoits active slave devices.
`ZigBee is a newer technology that competes with Bluetooth to some extent. De-
`vised by the ZigBeealliance and standardized as IEEE 802.15.4,it is designed forsit-
`uations where the bandwidth requirements are low and power consumption must be
`very low to give very long batterylife. It is also intended to be simpler and cheaperthan
`Bluetooth, makingit financially feasible to incorporate in cheaper devices such as a wall
`switch that wirelessly communicates with a ceiling-mountedfan.
`
`2.8.2 Wi-Fi (802.11)
`This section takes a closer look at a specific technology centered around the emerging
`IEEE 802.11 standard,also known as W3-Fi.9 Wi-Fi is technically a trademark, owned by
`Oy
`.
`There is some debate over whether Wi-Fistands for “wireless fidelity,” by analogy to Hi-Fi, or whetherir is just a catchy
`namethat doesn’t stand for anything other than 802.11.
`
`

`

`138
`
`2 Direct Link Networks
`
`a trade group called the Wi-Fi alliance, that certifies product compliance with 802.11.
`Like its Ethernet and token ring siblings, 802.11 is designed for use in a limited geo-
`graphical area (homes, office buildings, campuses), andits primary challenge is to medi-
`ate access to a shared communication medium—inthiscase, signals propagating through
`space. 802.11 supports additionalfeatures (e.g., time-boundedservices, power manage-
`ment, and security mechanisms), but we focus our discussion onits base functionality.
`
`Physical Properties
`802.11 runsoversix different physical layer protocols (so far). Five are based on spread
`spectrum radio, and one on diffused infrared (and is of historical interest only at this
`point). Thefastest runs at a maximum of 54 Mbps.
`The original 802.11 standard defined two radio-based physical layers standards,
`one using frequency hopping (over 79 1-MHz-wide frequency bandwidths) and the
`other using direct sequence (with an 11-bit chipping sequence). Both provide up to
`2 Mbps. Then physical layer standard 802.11b was added. Using a variant of direct
`sequence, 802.11b provides up to 11 Mbps. These three standards run in the license-
`exempt 2.4 GHz frequency bandofthe electromagnetic spectrum. Then came 802.1 1a,
`which delivers up to 54 Mbpsusing a variant ofFDM called orthogonalfrequency division
`multiplexing (OFDM). 802.11a runs in the license-exempt 5-GHz band. On one hand,
`this bandis less used, so there is less interference. On the other hand, there is more ab-
`sorption ofthe signal anditis limited to almostline of sight. The most recent standard
`is 802.11g, which is backward compatible with 802.11b (and returns to the 2.4-GHz
`band). 802.1 1g uses OFDM anddelivers up to 54 Mbps. It is common for commercial
`products to supportall three of 802.11a, 802.11b, and 802.1 1g, which not only ensures
`compatibility with any device that supports any oneofthe standards, but also makesit
`possible for two such products to choose the highest bandwidth option for a particular
`environment.
`
`Collision Avoidance
`Atfirst glance,it might seem that a wireless protocol would follow the same algorithm as
`the Ethernet—wait until the link becomesidle before transmitting and back off should
`a collision oecur—andtoafirst approximation, this is what 802.11 does. The additional
`complication for wireless is that, while a node on an Ethernetreceives every other node’s
`transmissions, a node on an 802,11] network may be toofar from certain other nodes to
`receive their transmissions (andvice versa).
`Consider thesituation depicted in Figure 2.41, where A and C are both within
`range of B but not each other. Suppose both A and C want to communicate with B and
`so they each sendit a frame. A and C are unaware of each othersince their signals do
`not carry that far. These two frames collide with each otherat B, but unlike an Ethernet,
`
`

`

`2.8 Wireless
`
`139
`
`Figure 2.41 The hidden node problem. Although A and C are hidden from each other,
`their signals can collide at B. (B’s reach is not shown.)
`
`
`
`
`
`
`
`
`Figure 2.42 The exposed node problem. Although B and C are exposedto each other's
`signals, there is no interference if B transmits to A while C transmits to D. (A’s and D's
`reaches are not shown.)
`
`neither A nor C is aware ofthis collision. A and C are said to be Aidden nodes with respect
`to each other.
`A related problem,called the exposed node problem, occurs under the circumstances
`illustrated in Figure 2.42, where each ofthe four nodesis able to send and receive signals
`that reach just the nodesto its immediate left and right. For example, B can exchange
`frames with A and C but it cannot reach D, while C can reach B and D but not A.
`Suppose B is sending to A. NodeC is aware of this communication because it hears B’s
`transmission. It would be a mistake, however, for C to conclude that it cannot transmit
`to anyone just because it can hear B’s transmission. For example, suppose C wants to
`transmit to node D. This is not a problem since C’s transmission to D will notinterfere
`with A’s ability to receive from B. (It would interfere with A sending to B, but B is
`transmitting in our example.)
`
`

`

`140
`
`2 Direct Link Networks
`
`802.11 addresses these two problems with an algorithm called multiple access with
`collision avoidance (MACA). The idea is for the sender and receiver to exchange control
`frames with each other before the sender actually transmits any data. This exchange
`informs all nearby nodes that a transmission is about to begin. Specifically, the sender
`transmits a Request to Sencl (RTS) frame to the receiver; the RT'S frame includes a field
`that indicates how long the sender wants to hold the medium (i.-e., it specifies the length
`of the data frame to be transmitted). The receiver then replies with a Clear to Send (CTS)
`frame; this frame echoesthis length field back to the sender. Any nodethat sees the CTS
`frame knowsthatit is close to the receiver, and therefore cannot transmit for the period
`of timeit takes to send a frameofthe specified length. Any node that sees the RTS frame
`but not the CTS frameis not close enough to the receiver to interfere with it, and so is
`free to transmit.
`There are two more details to complete the picture. First, che receiver sends an
`ACKto the senderafter successfully receiving a frame. All nodes must wait for this ACK.
`before trying to transmit.’ Second, should two or more nodes detect an idle link and
`try to transmit an RTS frameat the same time, their RTS frames will collide with each
`other. 802.11 does not support collision detection, but instead the senders realize the
`collision has happened when they do notreceive the CTS frameafter a period oftime,
`in which case they each wait a random amountoftime before trying again. The amount
`of time a given node delays is defined by the same exponential backoff algorithm used
`on the Ethernet (see Section 2.6.2).
`
`Distribution System
`As described so far, 802.11 would be suitable for a network with a mesh (ad hoc) topol-
`ogy, and developmentof an 802.11s standard for mesh networks is nearing completion.
`At the current time, however, nearly all 802.11 networks use a base-station-oriented
`topology.
`Instead of all nodes being created equal, some nodes are allowed to roam (ce.g.,
`your laptop) and some are connected to a wired network infrastructure. 802.11 calls
`these base stations access points (AP), and they are connected to each other by a so-called
`distribution system. Figure 2.43 illustrates a distribution system that connects three access
`points, each of which services the nodes in some region. The details of the distribution
`system are not importantto this discussion—it could be an Ethernet or a tokenring, for
`example. The only important point is that the distribution network runsat layer 2 of
`the ISO architecture (the link layer), that is, it operates at the same protocollayer as the
`wireless links. In other words, it does not depend on any higher-level protocols (such as
`the networklayer).
`
`“This ACK was not part of che original MACAalgorithm, but was instead proposed in an extended versioncalled
`MACAW MACAfor Wireless LANs.
`
`

`

`2.8 Wireless
`
`141
`
` Distribution system
`
`Figure 2.43 Access points connected to a distribution network.
`
`
`
`Although two nodes can communicatedirectly with each otherif they are within
`reach of each other, the idea behind this configuration is that each nodeassociatesitself
`with one access point. For node A to communicate with node E, for example, A first
`sends a frame to its access point (AP-1), which forwards the frame across the distribution
`system to AP-3, which finally transmits the frame to E. How AP-1 knew to forward the
`message to AP-3 is beyond the scope of 802.11; it may have used the bridging protocol
`described in the next chapter (Section 3,2), What 802.11 does specify is how nodesselect
`their access points and, more interestingly, how this algorithm works in light of nodes
`moving from onecell to another.
`The techniquefor selecting an AP is called scanning and involves thefollowing four
`
`steps:
`
`1 The node sends a Probe frame;
`
`2 All APs within reach reply with a Probe Responseframe;
`
`3 The node selects one of the access points, and sends that AP an Association
`Requestframe;
`
`4 The APreplies with an Association Responseframe.
`
`A node engages this protocol wheneverit joins the network, as well as when it becomes,
`unhappy with its current AP. This might happen, for example, because thesignal from.
`its current AP has weakened due to the node moving away from it. Whenever a node
`
`

`

`142
`
`2 Direct Link Networks
`
` Distribution system
`
`
`
`Figure 2.44 Node mobility.
`
`16
`
`16
`
`48
`
`48
`
`
`
`
`
`
`
`
`
`
`
`48 32 16 48 0-18,496
`
`Figure 2.45
`
`802.11 frame format.
`
`acquires a new AP, the new AP notifies the old AP of the change(this happensin step 4)
`via the distribution system.
`Considerthe situation shown in Figure 2.44, where node C moves from thecell
`serviced by AP-1 to thecell serviced by AP-2. As it moves, it sends Probe frames, which
`eventually result in Probe Response frames from AP-2. At some point, C prefers
`AP-2 over AP-1, and so it associates itself with that access point.
`The mechanism just described is called active scanning since the nodeis actively
`searching for an access point. APs also periodically send a Beacon framethat advertises
`the capabilities of the access point; these include the transmission rates supported by
`the AP. This is called passive scanning, and a node can change to this AP based on the
`Beacon frame simply by sending an Association Requestframebackto theaccess
`point.
`
`Frame Format
`Most of the 802.11 frame format, whichis depicted in Figure 2.45, is exactly what we
`would expect. The frame contains the source and destination node addresses, each of
`which are 48 bits long, up to 2,312 bytes of data, and a 32-bit CRC. The Control
`
`

`

`2.8 Wireless
`
`143
`
`field contains three subfields of interest (not shown): a 6-bit Type field that indicates
`whetherthe framecarries data, isan RTS or CTS frame,oris being used by the scanning
`algorithm; and a pair of 1-bit fields—called TODS and FromDS—that are described
`below.
`The peculiar thing about the 802.11 frame formatis that it contains four, rather
`than two, addresses. How these addresses are interpreted depends on thesettings of the
`ToDS and FromDSbits in the frame’s Control field. This is to account for the pos-
`sibility that the frame had to be forwarded across the distribution system, which would
`meanthat the original senderis not necessarily the same as the most recent transmitting
`node. Similar reasoning applies to the destination address. In the simplest case, when
`one nodeis sending directly to another, both the DS bits are 0, Addr1 identifies the
`target node, and Addr2identifies the source node. In the most complex case, both DS
`bits are set to 1, indicating that the message went from a wireless node onto the dis-
`tribution system, and then from the distribution system to another wireless node. With
`both bits set, Addr1 identifies the ultimate destination, Addr2 identifies the immediate
`sender (the one that forwarded the frame from the distribution system to the ultimate
`destination), Addr3 identifies the intermediate destination (the one that accepted the
`frame from a wireless node and forwardedit across the distribution system), and Addr4
`identifies the original source. In terms of the example given in Figure 2.43, Addr1
`corresponds to E, Addr2 identifies AP-3, Addr3 corresponds to AP-1, and Addr4
`identifies A.
`
`2.8.3 WiMAX (802.16)
`WiMAX, which stands for Worldwide Interoperability for Microwave Access, was de-
`signed by the WiMAX Forum and standardized as IEEE 802.16. It was originally con-
`ceived as a last-mile technology (Section 2.1.2). In WiMAX’s case that “mile” ts typically
`1 to 6 miles, with a maximum of about 30 miles, leading to WiMAX beingclassified
`as a metropolitan area network (MAN). In keeping with a last-mile role, WiMAX does
`not incorporate mobility at the time of this writing, although efforts to add mobility are
`nearing completion as IEEE 802.16e. Also in keeping with the last-mile niche, WiMAX’s
`client systems,called subscriber stations, are assumed to be not end-user computing de-
`vices, but rather systems that multiplex all the communication of the computing devices
`being used in a particular building. WiMAX provides up to 70 Mbpstoasingle sub-
`scriberstation.
`In order to adapt to different frequency bands and different conditions, WiMAX
`defines several physical layer protocols. The original WiMAX physical laye