z=SQo
`
`=ol=
`
`FatPipe Exhibit 2022, pg. 1
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`DATA AND
`COMPUTER
`COMMUNICATIONS
`
`
`
`FatPipe Exhibit 2022, pg. 2
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 2
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`FIFTH EDITION
`
`DATA AND
`COMPUTER
`COMMUNICATIONS
`
`WILLIAM STALLINGS
`
`Prentice-Hall of India Private Limited
`New Delhi - 110 001
`2001
`
`FatPipe Exhibit 2022, pg. 3
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 3
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`This Fourteenth Indian Reprint—Rs. 250.00
`(Original U.S. Edition—-Rs. 3367.00)
`
`DATA AND COMPUTER COMMUNICATIONS, 5th Ed.
`by William Stallings
`
`© 1997 by Prentice-Hall, Inc., Upper Saddle River, New Jersey 07458, U.S.A. All rights reserved.
`No part of this book may be reproduced in any form, by mimeograph or any other means, without
`permission in writing from the publisher.
`The author and publisher of this book have used their best efforts in preparing this book. These efforts include
`the development, research, and testing of the theories and programs to determine their effectiveness. The author
`and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising
`out of,
`the furnishing, performance, or use of
`these programs.
`
`ISBN-81-203-1240-6
`The export rights of this book are vested solely with the publisher.
`This Eastern Economy Edition is the authorized, complete and unabridged photo-offset reproduction
`of the latest American edition specially published and priced for sale only in Bangladesh, Burma,
`Cambodia, China, Fiji, Hong Kong, India, Indonesia, Laos, Malaysia, Nepal, Pakistan, Philippines,
`Singapore, South Korea, Sri Lanka, Taiwan, Thailand, and Vietnam.
`Reprinted in India by special arrangement with Prentice-Hall,
`Inc., Upper Saddle River, New
`Jersey 07458, U.S.A.
`Fourteenth Printing (Fifth Edition)
`
`tee
`
`we
`
`April, 2001
`
`Published by Asoke K. Ghosh, Prentice-Hall of India Private Limited, M-97, Connaught Circus,
`New Delhi-110001
`and Printed by Mohan Makhijani at Rekha Printers Private Limited,
`New Delhi-110020.
`
`FatPipe Exhibit 2022, pg. 4
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 4
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`cuaprer9
`
`PACKET SWITCHING
`
`
`
`9.1 Packet-Switching Principles
`9.2 Routing
`9.3 Congestion Control
`9.4 X.25
`
`9.5 Recommended Reading
`9.6 Problems
`Appendix 9A Least-Cost Algorithms
`
`FatPipe Exhibit 2022, pg. 5
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 5
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`254 CHAPTER 9 / PACKET SWITCHING
`
`"
`
`/ Aisa switchinghasevolvedsubstantiallysince that time,itisremarkable
`
`round 1970, research began on a newform ofarchitecture forlong-distance
`digital data communications: packet switching. Although the technology of
`that (1) the basic technology of packet switching is fundamentally the same today
`as it wasin the early-1970s networks, and (2) packet switching remains one of the
`few effective technologies for long-distance data communications.
`This chapter provides an overview of packet-switching technology. Wewill
`see that many of the advantages of packet switching(flexibility, resource sharing,
`robustness, responsiveness) come with a cost. The packet-switching network is a
`distributedcollection of packet-switching nodes.Ideally, all packet-switching nodes
`would always know the state of the entire network. Unfortunately, because the
`nodesare distributed, there is alwaysa time delay between a changein status in one
`portion of the network and the knowledge of that change elsewhere. Furthermore,
`there is overhead involved in communicating status information. As a result, a
`packet-switching network can never perform “perfectly,” and so elaborate algo-
`rithms are used to cope with the time delay and overhead penalties of network
`operation. These sameissueswill appear again when wediscuss internetworking in
`Part IV.
`The chapter begins with an introduction to packet-switching network princi-
`ples. Next, we lookatthe internal operation of these networks, introducing the con-
`cepts of virtual circuits and datagrams. Following this, the key technologies of
`routing and congestion control are examined. The chapter concludes with an intro-
`duction to X.25, which is the standard interface between an end system and a
`packet-switching network.
`
`9.1
`
`PACKET-SWITCHING PRINCIPLES
`
`The long-haul circuit-switching telecommunications network was orginally de-
`signed to handlevoice traffic, and the majority of traffic on these networks con-
`tinues to be voice. A key characteristic of circuit-switching networks is that
`resources within the network are dedicated to a particularcall. For voice connec-
`tions, the resulting circuit will enjoy a high percentage ofutilization because, most
`of the time, oneparty or the other is talking. However,as the circuit-switching net-
`work began to be used increasingly for data connections, twoshortcomings became
`apparent:
`
`e Ina typical user/host data connection (e.g., personal computeruser logged on
`to a database server), much of the time thelineis idle. Thus, with data con-
`nections, a circuit-switching approachis inefficient.
`In a circuit-switching network, the connection provides for transmission
`at constant data rate. Thus, each of the two devices that are connected
`must transmit and receive at the same data rate as the other; this limits the
`utility of the network in interconnecting a variety of host computers and
`terminals.
`
`FatPipe Exhibit 2022, pg. 6
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 6
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 255
`
`To understand how packet switching addresses these problems, let us briefly
`summarize packet-switching operation. Data are transmitted in short packets. A
`typical upper boundon packet length is 1000 octets (bytes). If a source has a longer
`message to send, the messageis brokenupinto a series of packets (Figure 9.1). Each
`packet contains a portion (or all for a short message) of the user’s data plus some
`control information. The control information, at a minimum,includes the informa-
`tion that the network requires in orderto be able to route the packet through the
`network and deliver it to the intended destination. At each node en route, the
`packet is received, stored briefly, and passed onto the next node.
`Let us return to Figure 8.1, but now assumethatit depicts a simple packet-
`switching network. Consider a packet to be sent from station A to station E. The
`packetwill include controlinformation that indicates that the intended destination
`is E. The packet is sent from A to node 4. Node 4 stores the packet, determines the
`next leg of the route (say 5), and-queuesthe packet to go out on thatlink (the 4-5
`link), Whenthelink is available, the packetis transmitted to node 5, which will for-
`ward the packet to node6, andfinally to E. This approach has a numberof advan-
`tages overcircuit switching:
`
`e Line efficiency is greater, as a single node-to-node link can be dynamically
`shared by many packetsover time. The packets are queued up andtransmit-
`ted as rapidly as possible-over the link. By contrast, with circuit switching,
`time on a node-to-nodelink is preallocated using synchronous time-division
`multiplexing. Muchofthe time, such a link may be idle because a portion of
`its time is dedicated to a connection whichis idle.
`A packet-switching network can perform data-rate conversion. Two stations
`of different data rates can exchange packets because each connects to its node
`at its proper data rate.
`
`2
`
`
`
`Userdata
`
`
`A
`oO
`i
`\\
`nA
`\
`iy
`aN
`on
`Voy
`\
`l
`\
`I
`\
`\
`I
`\
`\
`t
`\
`\
`!
`\
`\
`
`|
`
`t
`/
`!
`!
`i
`!
`i
`!
`t
`
`|
`
`|
`
`\
`
`\\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\\
`
`\
`
`\
`
`N
`
`\
`
`| oo |
`
`Control information
`(packet header)
`ipe
`
`Packet
`
`FIGURE 9.1 Packets.
`
`FatPipe Exhibit 2022, pg. 7
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 7
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`256 CHAPTER 9 / PACKET SWITCHING
`
`° Whentraffic becomes heavy onacircuit-switching network, somecalls are
`blocked; thatis, the network refuses to accept additional connection requests
`until the load on the network decreases. On a packet-switching network,
`packetsarestill accepted, but delivery delay increases.
`° Priorities can be used. Thus,if a node has a numberof packets queued for
`transmission, it can transmit the higher-priority packets first. These packets
`will therefore experience less delay than lower-priority packets.
`
`Switching Technique
`A station has a message to send through a packet-switching network that is of
`length greater than the maximum packetsize. It therefore breaks the message up
`into packets and sends these packets, one at a time, to the network. A question
`arises as to how the network will handle this stream of packets asit attempts to
`route them through the network anddeliver them to the intended destination; there
`are two approaches that are used in contemporary networks: datagram and virtual
`circuit.
`In the datagram approach, each packetis treated independently, with noref-
`erence to packets that have gone before. Let us consider the implication of this
`approach. Supposethatstation A in Figure 8.1 has a three-packet message to send
`to E.It transmits the packets, 1-2-3, to node 4, On each packet, node 4 must make
`a routing decision. Packet 1 arrives for delivery to E. Node 4 could plausibly for-
`wardthis packet-to either node 5 or node 7 as the nextstep in the route. In this case,
`node 4 determines that its queue of packets for node 5 is shorter than for node 7,80
`it queues the packet for node 5. Ditto for packet 2. But for packet 3, node 4 finds
`thatits queue for node7 is now shorter and so queuespacket3 for that node. So the
`packets, each with the same destination address, do not all follow the sameroute.
`Asa result, it is possible that packet 3 will beat packet 2 to node 6. Thus,it is also
`possible that the packetswill be delivered to E in a different sequence from the one
`in which they were sent. It is up to E to figure out how to reorder them. Also,it is
`possible for a packet to be destroyed in the network. For example, if a packet-
`switching node crashes momentarily, all of its queued packets maybelost. If this
`were to happento one of the packets in our example, node 6 has no wayof know-
`ing that oneof the packets in the sequenceof packets has beenlost. Again, it is up
`to E to detect the loss of a packet and figure out howto recoverit. In this technique,
`each packet, treated independently,is referred to as a datagram.
`In the virtual-circuit approach, a preplanned route is established before any
`packets are sent. For example, suppose that A has one or more messages to send to
`E. It first sends a special control packet, referred to as a Call-Request packet,to 4,
`requesting a logical connection to E. Node 4 decides to route the request andall
`subsequent packets to 5, which decides to route the request and all subsequent
`packets to 6, which finally delivers the Call-Request packetto E.If Eis prepared to
`accept the connection,it sends a Call-Acceptpacket to 6. This packetis passed back
`through nodes 5 and 4 to A. Stations A and E may now exchange data over the
`route that has been established. Becausethe route is fixed for the duration of the
`logical connection,it is somewhatsimilar to a circuit in a circuit-switching network,
`and is referred to as a virtual circuit. Each packet now containsa virtual-circuit
`identifier as well as data. Each node onthe preestablished route knows where to
`
`FatPipe Exhibit 2022, pg. 8
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 8
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES. 257
`
`direct such packets;.no routing decisions are required. Thus, every data packet from
`A intended for E traverses nodes 4,5, and 6; every data packet from F intended for
`A traverses nodes 6, 5, and 4, Eventually, one of the stations terminates the con-
`nection with a Clear-Request packet. At any time, each station can have more than
`onevirtualcircuit to any other station and can havevirtual circuits to more than one
`station.
`So, the main characteristic of the virtual-circuit technique is that a route
`betweenstations is set up prior to data transfer. Note that this does not mean that
`this is a dedicated path,as in circuit switching. A packetis still buffered at each
`node, and queued for output over a line. The difference from the datagram
`approachis that, with virtualcircuits, the node need not make a routing decision for
`each packet;it is made only oncefor all packets using that virtual circuit.
`If two stations wish to exchange data over an extended period of time, there
`are certain advantages to virtual circuits. First, the network may provide services
`related to the virtual circuit, including sequencing and error control. Sequencing
`refers to the fact that, becauseall packets follow the sameroute, they arrive in the
`original order. Errorcontrolis a service that assures not only that packets arrive in
`proper sequence,butthatall packets arrive correctly. For example, if a packet in a
`sequence from node4 to node6fails to arrive at node6, or arrives with an error,
`node 6 can request a retransmission of that packet from node 4. Another advantage
`is that packets should transit the network more rapidly with a virtualcircuit;it is not
`necessary to makea routing decision for each packet at each node.
`One advantage of the datagram approachis that the call setup phase
`isis
`avoided. Thus,if a station wishes to send only one or a few packets, datagram deliv-
`ery will be quicker. Another advantage of the datagram service is that, becauseitis
`moreprimitive, it is more flexible. For example, if congestion develops in, onepart
`of the network, incoming datagrams can be routed away from the congestion. With
`the use ofvirtual circuits, packets follow a predefined route, and it is thus moredif-
`ficult for the network to adapt to congestion. A third advantage is that datagram
`delivery is inherently morereliable. With the use of virtual circuits, if a node fails,
`all virtual circuits that pass through that node are lost. With datagram delivery,if a
`nodefails, subsequent packets mayfind an alternate route that bypasses that node.
`Most currently available packet-switching networks make use of virtualcir-
`cuits for their internal operation. To some degree,this reflects a historical motiva-
`tion to provide a networkthat presents a service asreliable (in terms of sequencing)
`as a circuit-switching network. There are, however, several providers of private
`packet-switching networks that make use of datagram operation. From the user’s
`point of view, there should be verylittle difference in the external behavior based
`on the use of datagramsorvirtual circuits. If a manageris faced with a choice, other
`factors such as cost and performance should probably take precedence over
`whether the internal network operation is datagram or virtual-circuit. Finally, it
`should be noted that a datagram-style of operation is common in internetworks
`(discussed in Part IV).
`
`
`
`Packet Size
`
`One important design issue is the packetsize to be used in the network, Thereis a
`significant relationship between packet size and transmissiontime,asillustrated in
`
`FatPipe Exhibit 2022, pg. 9
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 9
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

` Data|Data
` Data|Data
`
`(c)
`5-packet message
`
`
`b
`Y
`
`
`=fs|telfetLeed
`258 CHAPTER 9 / PACKET SWITCHING
`
`x
`
`a
`
`b
`
`Y
`
`x
`
`a
`
`(b)
`’ 2-packet message
`
`(d)
`10-packet message
`
`1-packet message
`
`FIGURE 9.2 Effect of packet size on transmissiontime.
`
`Figure 9.2. In this example,it is assumed that there is-a virtual circuit from station
`X through nodes a andbto station Y. The message to be sent comprises 30 octets,
`and each packet contains 3 octets of control information, which is placed at the
`
`FatPipe Exhibit 2022, pg. 10
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 10
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 259
`
`beginning of each packet andis referred to as a header. If the entire messageis sent
`as a single packet of 33 octets (3 octets of header plus 30 octets of data), then the
`packetis first transmitted from station X to node a (Figure 9.2a), When the entire
`packetis received, it can then be transmitted from a to b. Whenthe entire packetis
`received at node bd,it is then transferred to station Y. The total transmission time at
`the nodesis 99 octet-times (33 octets X 3 packet transmissions).
`Suppose now that we break up the message into two packets, each containing
`15 octets of the message and,of course, 3 octets each of headeror control informa-
`tion. In this case, node a can begin transmitting the first packet as soon as it has
`arrived from X, without waiting for the second packet. Because of this overlap in
`transmission, the total transmission time drops to 72 octet-times. By breaking the
`message up into 5 packets, each intermediate node can begin transmission even
`sooner and the savingsin time is greater, with a total of 63 octet-times. However,
`this process of using more and smaller packets eventually results in increased,
`rather than reduced,delay asillustrated in Figure 9.2d; this is because each packet
`contains a fixed amount of header, and more packets means moreof these headers.
`Furthermore, the example does not show the processing and queuing delaysat each
`node. These delays are also greater when more packets are handled for a single
`message. However, we will see in Chapter 11 that an extremely small packetsize
`(53 octets) can result in an efficient network design.
`
`Comparison of Circuit Switching and Packet Switching
`Having lookedat the internal operation of packet switching, we can now return to
`a comparison of this technique with circuit switching. Wefirst look at the important
`issue of performance, and then examine other characteristics.
`
`Performance
`
`A simple comparisonofcircuit switching and the two formsof packet switching are
`providedin Figure 9.3. The figure depicts the transmission of a message across four
`nodes, from a source station attached to node 1 to a destination station attached to
`node 4.In this figure, we are concerned with three types of delay:
`
`e Propagation delay. The time it takes a signal to propagate from one node to
`the next. This time is generally negligible. The speed of electromagnetic sig-
`nals through a wire niedium, for example,is typically 2 x 10° m/s.
`e Transmission time. The time it takes for a transmitter to send out a block of
`data. For example,it takes 1 s to transmit a 10,000-bit block of data onto a
`10-kbpsline.
`e Node delay. Thetimeit takes for a node to perform the necessary processing
`as it switches data.
`
`
`
`Forcircuit switching, there is a certain amount of delay before the message
`can be sent.First, a call request signal is sent through the network in orderto set up
`a connection to the destination.If the destination station is not busy,a call-accepted
`signal returns. Note that a processing delay is incurred at each node during thecall
`request; this time is spent at each nodesetting up the route of the connection. On
`
`FatPipe Exhibit 2022, pg. 11
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 11
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`260 CHAPTER 9 / PACKET SWITCHING
`
`Propagation
`
`Call
`request
`signal
`
`Call
`Tequet
`acket
`P
`
`delay
`
`Call
`accept
`signal
`
`Call
`accept
`packet
`
` Processing
`delay
`
`link|fink|link
`
`Acknowledgement
`signal
`
`Acknowledgement
`packet
`
`ORO RORO
`
`(a) Circuit switching
`
`(b) Virtual circuit packet switching
`
`(c) Datagram packet switching
`
`FIGURE9.3 Eventtiming forcircuit switching and packet switching.
`
`the return, this processing is not needed because the connection is already set up;
`onceit is set up, the message is sent as a single block, with no noticeable delay at.
`the switching nodes.
`Virtual-circuit packet switching appears quite similar to circuit switching. A
`virtual circuit is requested using a call-request packet, which incurs a delay at each
`node. The virtual circuit is accepted with a call-accept packet. In contrast to the
`circuit-switching case,
`the call acceptance also experiences node delays, even
`though the virtual circuit route is now established; the reason is that this packetis
`queued at each node and must wait its turn for retransmission. Once the virtual cir-
`cuit is established, the message is transmitted in packets. It should beclear that this
`phase of the operation can be nofaster than circuit switching, for comparable net-
`works; this is because circuit switching is an essentially transparent process, provid-
`ing a constant data rate across the network. Packet switching involves some delay
`at each node in the path; worse,
`this delay is variable and will increase with
`increased load.
`Datagram packetswitching does not require a call setup. Thus, for short mes-
`sages, it will be faster than virtual-circuit packet switching and perhaps circuit
`switching. However, because each individual datagram is routed independently, the
`processing for each datagram at each node maybe longer than for virtual-circuit
`packets. Thus, for long messages, the virtual-circuit technique may be superior.
`Figure 9.3 is intended only to suggest what the relative performance of the
`techniques might be; however, actual performance depends on a host of factors,
`including the size of the network,its topology, the pattern of load, and the charac-
`teristics of typical exchanges.
`
`FatPipe Exhibit 2022, pg. 12
`Cisco v. FatPipe
`IPR2017-01845
`
`
`
`FatPipe Exhibit 2022, pg. 12
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 261
`
`TABLE.9.1 Comparison of communication switching techniques.
`
`Datagram packet
`Virtual-circuit
`Circuit switching
`switching
`packet switching
`
`
`Nodedicated path
`Transmission of packets
`
`Nodedicated path
`Transmission of packets
`
`Dedicated transmission path
`Continuoustransmission of
`data
`
`Fast enough for interactive
`Messagesare not stored
`
`The pathis established for
`entire conversation
`
`Call setup delay; negligi-
`ble transmission delay
`Busysignalif called party
`busy
`Overload mayblockcall
`setup; no delay for
`established calls
`Electromechanical or
`computerized switching
`nodes
`
`Fast enoughfor interactive
`Packets may be stored until
`delivered
`Route established for each
`
`packet
`Packet transmission delay
`
`Sender may be notified if
`packet notdelivered
`Overload increases packet
`delay
`
`Small switching nodes
`
`Fast enough for interactive
`Packets stored until
`delivered
`Route established for entire
`conversation
`
`Call setup delay; packet
`transmission delay
`Sendernotified of
`connection denial
`
`Overload may block call
`setup; increases packet
`delay
`Small switching nodes
`
`Network may be responsi-
`ble for packet sequences
`Speed and code
`conversion
`
`Dynamic use of bandwidth
`
`Overheadbits in each
`
`packet
`
`Network may be responsible
`for individual packets
`Speed and code
`conversion
`
`User responsible for message
`loss protection
`Usually no speed or code
`conversion
`Fixed bandwidth
`transmission
`No overheadbits aftercall
`Overheadbits in each
`message
`setup
`
`Dynamic use of bandwidth
`
`Other Characteristics
`
`Besides performance, there are a numberof other characteristics that may be con-
`sidered in comparing the techniques we have been discussing. Table 9.1 summarizes
`the most important of these. Most of these characteristics have already been dis-
`cussed, A few additional comments follow.
`As was mentioned,circuit switching is essentially a transparent service. Once
`a connection is established, a constant data rate is provided to the connectedsta-
`tions; this is not the case with packet switching, which typically introduces variable
`delay, so that data arrive in a choppy manner. Indeed, with datagram packet switch-
`ing, data mayarrive in a different order than they were transmitted.
`An additional consequence of transparency is that there is no overhead
`required to accommodate circuit switching. Once a connection is established, the
`analog or digital data are passed through, as is, from source to destination. For
`packet switching, analog data must be converted to digital before transmission; in
`addition, each packet includes overheadbits, such as the destination address.
`
`FatPipe Exhibit 2022, pg. 13
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 13
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`262 CHAPTER 9 / PACKET SWITCHING
`
`External and Internal Operation
`
`Oneof the most important characteristics of a packet-switching network is whether
`it uses datagramsorvirtual circuits. Actually, there are two dimensionsofthis char-
`acteristic, as illustrated in Figure 9.4. At the interface betweena station and a net-
`work node, a network may provide either a connection-oriented or connectionless
`service. With a connection-oriented service, a station performsa call request toset.
`up a logical connection to anotherstation. All packets presented to the network are
`identified as belongingto a particular logical connection and are numbered sequen-
`‘tially. The network undertakes to deliver packets in sequence-number order. The
`logical connection is usually referred to as a virtual circuit, and the connection-
`oriented ‘service is referred to as an external virtual-circuit service; unfortunately,
`this external service is distinct from the conceptof internal virtual-circuit operation,
`as we shall see. An important example of an external virtual circuit service is X.25,
`which is examined in Section 9.4.
`
`en
`
`secmemmenao
`
`Packet-switched
`network
`
`
`
`
`(a) Externalvirtualcircuit. A logical connectionis set up between twostations.
`Packets are labeled with a virtual circuit number and a sequence number.
`Packetsarrive in sequence,
`
`mommaoe
`
`
`
`
` Packet-switched
`network
`Sceneca
`
`
`
`
`
`FIGURE 9.4 External and internalvirtual circuits and datagrams.
`(continued on next page)
`.
`
`FatPipe Exhibit 2022, pg. 14
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 14
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET-SWITCHING PRINCIPLES 263
`
`With connectionless service, the network only agrees to handle packets inde-
`pendently, and may not deliver them in order or reliably. This type of serviceis
`sometimes known as an external datagram service; again, this concept is distinct
`from that of internal datagram operation. Internally, the network mayactually con-
`struct a fixed route between endpoints(virtual circuit), or it may not (datagram).
`Theseinternal and external design decisions need not coincide:
`
`_
`
`External virtual circuit, internal virtual circuit. When the user requests a vir-
`tual circuit, a dedicated route through the network is constructed. All packets
`follow that same route.
`External virtual circuit, internal datagram. The network handles each packet
`separately. Thus, different packets for the same external virtual circuit may
`take different routes. However, the network buffers packetsat the destination
`node,if necessary, so that they are delivered to the destination station in the
`proper order,
`External datagram, internal datagram. Each packetiis treated independently
`from both the user’s and the network’s point of view.
`External datagram, internal virtual circuit. The external user does not see any
`connections, as it simply sends packets oneat a time. The network, however,
`sets up a logical connection between stations for packet delivery and may
`
`
`
`
`(c) Internalvirtual circuit. A route for packets between two stationsis defined
`and labeled. All packets for that virtual circuit follow the same route and
`arrive in sequence.
`
`FIGURE9.4 (continued)
`
`FatPipe Exhibit 2022, pg. 15
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 15
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`264
`
`CHAPTER 9 / PACKET SWITCHING
`
`leave such connections in place for an extended period,so asto satisfy antic-
`ipated future needs,
`
`The question arises as to the choice of virtual circuits or datagrams, both inter-
`nally and externally. This will depend on the specific design objectives for the com-
`munication network and the cost factors that prevail.
`We have already made some comments concerning the relative merits of
`internal datagram versus virtual-circuit operation. With respect to externalservice,
`_ we can makethe following observations.
`
`¢ The datagram service, coupled with internal datagram operation, allows for
`efficient use of the network; no call setup and no need to hold up packets
`while a packet in erroris retransmitted. Thislatter feature is desirable in some
`real-time applications.
`® The virtual-circuit service can provide end-to-end sequencing and error con-
`trol; this service is attractive for supporting connection-oriented applications,
`suchasfile transfer and remote-terminal access.
`
`In practice, the virtual-circuit service is much more common than the data-
`gram service. The reliability and convenience of a connection-oriented service is
`seen as more attractive than the benefits of the datagram service.
`
`9.2
`
`ROUTING
`
`One of the most complex and crucial aspects of packet-switching network designis
`routing. This section begins with a survey of key characteristics that can be used to
`classify routing strategies. Then, some specific routing strategies are discussed.
`The principles described in this section are also applicable to internetwork
`routing, discussed in Part II.
`
`Characteristics
`
`The primary function of a packet-switching network is to accept packets from a
`source station and deliver them to a destination station. To accomplish this, a path
`or route through the network must be determined; generally, more than one route
`is possible. Thus, a routing function must be performed. The requirementsfor this
`function include
`
`e Correctness
`
`° Simplicity
`® Robustness
`° Stability
`
`® Fairness
`
`* Optimality
`* Efficiency
`
`The first two items on the list are self-explanatory. Robustness has to do with
`the ability of the network to deliver packets via some route in the face of localized
`
`FatPipe Exhibit 2022, pg. 16
`Cisco v. FatPipe
`IPR2017-01845
`
`FatPipe Exhibit 2022, pg. 16
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.2/ ROUTING 265
`
`failures and overloads. Ideally, the network can react to such contingencies without
`the loss of packets or the breaking of virtual circuits. The designer who seeks
`robustness must cope with the competing requirementfor stability. Techniques that
`react to changing conditions have an unfortunate tendencyto either react too slowly
`to events or to experience unstable swings from one extreme to another. For exam-
`ple, the network may react to congestion in one area by shifting most of the load to
`a second area. Now the second area is overloaded and thefirst is underutilized,
`causing a secondshift. During these shifts, packets may travel in loops through the
`network.
`A tradeoff also exists between fairness and optimality. Some performancecri-
`teria may: give higher priority to the exchange of packets between nearbystations
`compared to an exchange betweendistant stations. This policy may maximize aver-
`age throughput but will appear unfair to the station that primarily needs to com-
`municate with distant stations.
`Finally, any routing technique involves some processing overhead at each
`nodeandoften a transmission overhead as well, both of which impair networkeffi-
`ciency. The penalty of such overhead needs to be less than the benefit accrued
`based on some reasonable metric, such as increased robustnessor fairness.
`With these requirements in mind, we are in a position to assess the various
`design elements that contribute to a routing strategy. Table 9.2 lists these elements.
`Someof these categories overlap or are dependent on one another. Nevertheless,
`an examination of this list serves to clarify and organize routing concepts.
`
`TABLE 9.2 Elements of routing techniques for packet-switching networks.
`
`Performance criteria
`Numberof hops
`Cost
`Delay
`Throughput
`
`Decision time
`Packet (datagram)
`Session (virtual circuit)
`
`Decision place
`Each node (distributed)
`Central node (centralized)
`Originating node (source)
`
`Network information source
`None
`Local
`Adjacent node
`Nodesalong route
`All nodes
`
`Network information update timing
`Continuous
`Periodic
`
`Major load change
`Topology change
`
`Performance Criteria
`
`Theselection of a route is generally based on some performancecriterion. The sim-
`plest criterion is to choose the minimum-hop route (one that passes through the
`least numberof nodes) through the network;this is an easily measured criterion and
`should minimize the consumption of network resources. A generalization of the
`minimum-hopcriterion is least-cost routing. In this case, a cost is associated with
`each link, and, for any pair of attached stations, the route through the network
`that accumulatesthe least cost is sought. For