Prepared by l‘ml'cnnr linmd Mmclcln. University of ALassarbtrs("SILL-arm“ruff:
`
`NETWORK SIMULATION EXPERIMENTS MANUAL
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 1
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 1
`
`

`

`T H I R D E D I T I O N
`
`C O M P U T E R
`N E T W O R K S
`
`A Systems Approach
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 2
`
`

`

`The Morgan Kaufmann Series in Networking
`Series Editor, David Clark, M.I.T.
`
`Computer Networks: A Systems Approach, 3e
`Larry L. Peterson and Bruce S. Davie
`Network Architecture, Analysis, and Design, 2e
`James D. McCabe
`MPLS Network Management: MIBs, Tools, and Techniques
`Thomas D. Nadeau
`Developing IP-Based Services: Solutions for Service Providers and Vendors
`Monique Morrow and Kateel Vijayananda
`Telecommunications Law in the Internet Age
`Sharon K. Black
`Optical Networks: A Practical Perspective, 2e
`Rajiv Ramaswami and Kumar N. Sivarajan
`Internet QoS: Architectures and Mechanisms
`Zheng Wang
`TCP/IP Sockets in Java: Practical Guide for Programmers
`Michael J. Donahoo and Kenneth L. Calvert
`TCP/IP Sockets in C: Practical Guide for Programmers
`Kenneth L. Calvert and Michael J. Donahoo
`Multicast Communication: Protocols, Programming, and Applications
`Ralph Wittmann and Martina Zitterbart
`MPLS: Technology and Applications
`Bruce Davie and Yakov Rekhter
`High-Performance Communication Networks, 2e
`Jean Walrand and Pravin Varaiya
`Internetworking Multimedia
`Jon Crowcroft, Mark Handley, and Ian Wakeman
`Understanding Networked Applications: A First Course
`David G. Messerschmitt
`Integrated Management of Networked Systems: Concepts, Architectures,
`and their Operational Application
`Heinz-Gerd Hegering, Sebastian Abeck, and Bernhard Neumair
`Virtual Private Networks: Making the Right Connection
`Dennis Fowler
`Networked Applications: A Guide to the New Computing Infrastructure
`David G. Messerschmitt
`Modern Cable Television Technology: Video, Voice, and Data Communications
`Walter Ciciora, James Farmer, and David Large
`Switching in IP Networks: IP Switching, Tag Switching, and Related Technologies
`Bruce S. Davie, Paul Doolan, and Yakov Rekhter
`Wide Area Network Design: Concepts and Tools for Optimization
`Robert S. Cahn
`Frame Relay Applications: Business and Technology Case Studies
`James P. Cavanagh
`
`For further information on these books and for a list of forthcoming titles, please visit
`our website at http://www.mkp.com
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 3
`
`

`

`T H I R D E D I T I O N
`
`Larry L. Peterson & Bruce S. Davie
`
`C O M P U T E R
`N E T W O R K S
`
`A Systems Approach
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 4
`
`

`

`Senior Editor Rick Adams
`Simon Crump
`Publishing Services Manager
`Developmental Editor Karyn Johnson
`Cover Design Ross Carron Design
`Cover Image Vasco de Gama Bridge, Lisbon, Portugal
`Composition/Illustration International Typesetting and Composition
`Copyeditor Ken DellaPenta
`Jennifer McClain
`Proofreader
`Steve Rath
`Indexer
`Printer Courier Corporation
`
`Designations used by companies to distinguish their products are often claimed as trademarks
`or registered trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a
`claim, the product names appear in initial capital or all capital letters. Readers, however, should
`contact the appropriate companies for more complete information regarding trademarks and
`registration.
`
`Morgan Kaufmann Publishers
`An Imprint of Elsevier Science
`340 Pine Street, Sixth Floor
`San Francisco, CA 94104-3205
`www.mkp.com
`
`© 2003 by Elsevier Science (USA)
`All rights reserved
`Printed in the United States of America
`
`07 06 05 04 03
`
`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, or otherwise—without the
`prior written permission of the publisher.
`
`Library of Congress Control Number: xxxxxxxxxx
`ISBN: 1-55860-832-X (Casebound)
`ISBN: 1-55860-833-8 (Paperback)
`
`This book is printed on acid-free paper.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 5
`
`

`

`3
`
`A key problem that a switch must deal with is the
`finite bandwidth of its outputs. If packets destined for a
`certain output arrive at a switch and their arrival rate ex-
`ceeds the capacity of that output, then we have a problem
`of contention. The switch queues (buffers) packets until
`the contention subsides, but if it lasts too long, the switch
`will run out of buffer space and be forced to discard pack-
`ets. When packets are discarded too frequently, the switch
`is said to be congested. The ability of a switch to handle
`contention is a key aspect of its performance, and many
`high-performance switches use exotic hardware to reduce
`the effects of contention.
`This chapter introduces the issues of forwarding and
`contention in packet switches. We begin by considering the
`various approaches to switching, including the connec-
`tionless and connection-oriented models. We then exam-
`ine two particular technologies in detail. The first is LAN
`switching, which has evolved from Ethernet bridging to
`become one of the dominant technologies in today’s LAN
`environments. The second noteworthy switching technol-
`ogy is asynchronous transfer mode (ATM), which is pop-
`ular among telecommunications service providers in wide
`area networks. Finally, we consider some of the aspects
`of switch design that must be taken into account when
`building large-scale networks.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 6
`
`

`

`166
`
`3 Packet Switching
`
`3.1 Switching and Forwarding
`In the simplest terms, a switch is a mechanism that allows us to interconnect links to
`form a larger network. A switch is a multi-input, multi-output device, which transfers
`packets from an input to one or more outputs. Thus, a switch adds the star topol-
`ogy (see Figure 3.1) to the point-to-point link, bus (Ethernet), and ring (802.5 and
`FDDI) topologies established in the last chapter. A star topology has several attractive
`properties:
`
`■ Even though a switch has a fixed number of inputs and outputs, which limits
`the number of hosts that can be connected to a single switch, large networks
`can be built by interconnecting a number of switches.
`
`■ We can connect switches to each other and to hosts using point-to-point links,
`which typically means that we can build networks of large geographic scope.
`
`■ Adding a new host to the network by connecting it to a switch does not
`necessarily mean that the hosts already connected will get worse performance
`from the network.
`
`This last claim cannot be made for the shared-media networks discussed in the
`last chapter. For example, it is impossible for two hosts on the same Ethernet to transmit
`continuously at 10 Mbps because they share the same transmission medium. Every host
`on a switched network has its own link to the switch, so it may be entirely possible for
`many hosts to transmit at the full link speed (bandwidth), provided that the switch is
`designed with enough aggregate capacity. Providing high aggregate throughput is one
`
`Figure 3.1 A switch provides a star topology.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 7
`
`

`

`3.1 Switching and Forwarding
`
`167
`
`Switching
`protocol
`
`T3
`
`T3
`
`STS-1
`
`Figure 3.2 Example protocol graph running on a switch.
`
`T3
`T3
`STS-1
`
`Input
`ports
`
`Switch
`
`T3
`T3
`STS-1
`
`Output
`ports
`
`Figure 3.3 Example switch with three input and output ports.
`
`of the design goals for a switch; we return to this topic below. In general, switched
`networks are considered more scalable (i.e., more capable of growing to large numbers
`of nodes) than shared-media networks because of this ability to support many hosts
`at full speed.
`A switch is connected to a set of links and, for each of these links, runs the
`appropriate data link protocol to communicate with the node at the other end of the
`link. A switch’s primary job is to receive incoming packets on one of its links and to
`transmit them on some other link. This function is sometimes referred to as either
`switching or forwarding, and in terms of the OSI architecture, it is the main function
`of the network layer. Figure 3.2 shows the protocol graph that would run on a switch
`that is connected to two T3 links and one STS-1 SONET link. A representation of this
`same switch is given in Figure 3.3. In this figure, we have split the input and output
`halves of each link, and we refer to each input or output as a port. (In general, we
`assume that each link is bidirectional, and hence supports both input and output.) In
`other words, this example switch has three input ports and three output ports.
`The question then is, How does the switch decide which output port to place
`each packet on? The general answer is that it looks at the header of the packet
`for an identifier that it uses to make the decision. The details of how it uses this
`identifier vary, but there are two common approaches. The first is the datagram or
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 8
`
`

`

`168
`
`3 Packet Switching
`
`connectionless approach. The second is the virtual circuit or connection-oriented ap-
`proach. A third approach, source routing, is less common than these other two, but it
`is simple to explain and does have some useful applications.
`One thing that is common to all networks is that we need to have a way to iden-
`tify the end nodes. Such identifiers are usually called addresses. We have already seen
`examples of addresses in the previous chapter, for example, the 48-bit address used
`for Ethernet. The only requirement for Ethernet addresses is that no two nodes on a
`network have the same address. This is accomplished by making sure that all Ethernet
`cards are assigned a globally unique identifier. For the following discussions, we assume
`that each host has a globally unique address. Later on, we consider other useful prop-
`erties that an address might have, but global uniqueness is adequate to get us started.
`Another assumption that we need to make is that there is some way to identify the
`input and output ports of each switch. There are at least two sensible ways to identify
`ports: One is to number each port, and the other is to identify the port by the name of
`the node (switch or host) to which it leads. For now, we use numbering of the ports.
`
`3.1.1 Datagrams
`The idea behind datagrams is incredibly simple: You just make sure that every packet
`contains enough information to enable any switch to decide how to get it to its des-
`tination. That is, every packet contains the complete destination address. Consider
`the example network illustrated in Figure 3.4, in which the hosts have addresses A,
`B, C, and so on. To decide how to forward a packet, a switch consults a forwarding
`table (sometimes called a routing table), an example of which is depicted in Table 3.1.
`
`Destination
`
`Port
`
`A
`
`B
`
`C
`
`D
`
`E
`
`F
`
`G
`
`H
`
`3
`
`0
`
`3
`
`3
`
`2
`
`1
`
`0
`
`0
`
`Table 3.1 Forwarding table for switch 2.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 9
`
`

`

`3.1 Switching and Forwarding
`
`169
`
`Host D
`
`3
`
`Host C
`
`Switch 1
`1
`
`0
`
`2
`
`Host A
`
`Host F
`
`Host E
`
`3
`
`2
`
`0
`
`Switch 2
`1
`
`Host G
`
`0
`
`Switch 3 Host B
`3
`
`1
`
`2
`
`Host H
`
`Figure 3.4 Datagram forwarding: an example network.
`
`This particular table shows the forwarding information that switch 2 needs to forward
`datagrams in the example network. It is pretty easy to figure out such a table when you
`have a complete map of a simple network like that depicted here; we could imagine a
`network operator configuring the tables statically. It is a lot harder to create the for-
`warding tables in large, complex networks with dynamically changing topologies and
`multiple paths between destinations. That harder problem is known as routing and is
`the topic of Section 4.2. We can think of routing as a process that takes place in the
`background so that, when a data packet turns up, we will have the right information
`in the forwarding table to be able to forward, or switch, the packet.
`Connectionless (datagram) networks have the following characteristics:
`
`■ A host can send a packet anywhere at any time, since any packet that turns
`up at a switch can be immediately forwarded (assuming a correctly populated
`forwarding table). As we will see, this contrasts with most connection-oriented
`networks, in which some “connection state” needs to be established before
`the first data packet is sent.
`
`■ When a host sends a packet, it has no way of knowing if the network is capable
`of delivering it or if the destination host is even up and running.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 10
`
`

`

`170
`
`3 Packet Switching
`
`■ Each packet is forwarded independently of previous packets that might have
`been sent to the same destination. Thus, two successive packets from host A
`to host B may follow completely different paths (perhaps because of a change
`in the forwarding table at some switch in the network).
`
`■ A switch or link failure might not have any serious effect on communication
`if it is possible to find an alternate route around the failure and to update the
`forwarding table accordingly.
`
`This last fact is particularly important to the history of datagram networks. One
`of the important goals of the ARPANET, forerunner to the Internet, was to develop
`networking technology that would be robust in a military environment, where you
`might expect links and nodes to fail because of active attacks such as bombing. It was
`the ability to route around failures that led to a datagram-based design.
`
`3.1.2 Virtual Circuit Switching
`A widely used technique for packet switching, which differs significantly from the
`datagram model, uses the concept of a virtual circuit (VC). This approach, which is also
`called a connection-oriented model, requires that we first set up a virtual connection
`from the source host to the destination host before any data is sent. To understand how
`this works, consider Figure 3.5, where host A again wants to send packets to host B.
`We can think of this as a two-stage process. The first stage is “connection setup.” The
`second is data transfer. We consider each in turn.
`In the connection setup phase, it is necessary to establish “connection state” in
`each of the switches between the source and destination hosts. The connection state
`
`3
`
`0
`
`2
`
`1
`
`Switch 1
`
`3
`
`0
`
`2
`
`1
`
`Switch 2
`
`3
`
`1
`
`0
`
`2
`
`Host A
`
`3
`
`0
`
`2
`
`Switch 3
`1
`
`Host B
`
`Figure 3.5 An example of a virtual circuit network.
`
`Patent Owner Acceleration Bay, LLC - Ex. 2011, p. 11
`
`