stem
`
`sonamy
`hie}! ‘
`
`,3_mBW
`
`H.T..w,.
`
`.r_
`
`FatPipe Exhibit 2022, pg. 1
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

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

`

`FIFTH EDITIOE
`
`DATA AND
`
`COMPUTER
`COMMUNICATIONS
`
`WILLIAM STALLINGS
`
`Prentice'Hall of India @FEWIGGQ lfimfificgefl
`New Delhi - 110 001
`
`2001
`
`FatPipe Exhibit 2022, pg. 3
`Cisco v. FatPipe
`|PR2017-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 ol
`these programs.
`
`lSBN-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 lndia by special arrangement with Prentice-Hall,
`Jersey 07458, U.S.A.
`
`Inc., Upper Saddle River, New
`
`Fourteenth Printing (Fifth Edition)
`
`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 Fiekha Printers Private Limited,
`New Delhi-110020.
`
`FatPipe Exhibit 2022, pg. 4
`Cisco v. FatPipe
`lPR2017-01845
`
`FatPipe Exhibit 2022, pg. 4
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`CHwER9
`
`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
`V
`
`Appendix 9A Least-Cost Algorithms
`
`FatPipe Exhibit 2022, pg. 5
`Cisco v. FatPipe
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 5
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`254 CHAPTER 9 / PACKET SWITCHING
`
`‘
`
`round 1970, research began on a new form of architecture for'long-distance
`digital data communications: packet switching. Although the technology of
`
`j kpacket switching has evolved substantially since that time, it is remarkable
`
`that (1) the basic technology of packet switching is fundamentally the same today
`as it was in 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. We will
`see that many of the advantages of packet switching (flexibility, resource sharing,
`robustness, responsiveness) come with a cost. The packet-switching network is a
`distributed» collection of packet-switching nodes. Ideally, all packet-switching nodes
`would always know the state of the entire network. Unfortunately, because the
`nodes are distributed, there is always a time delay between a change in 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 same issues will appear again when we discuss internetworking in
`Part IV.
`
`The chapter begins with an introduction to packet-switching network princiw
`ples. Next, we look at the 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 X25, 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 handle voice traffic, and the majority of traffic on these networks cona
`tinues to be voice. A key characteristic of circuit-switching networks is that
`resources Within the network areldedicated to a particular call. For voice connec-
`tions, the resulting circuit will enjoy a high percentage of utilization because, most
`of the time, one party or the other is talking. However, as the circuit—switching net«
`work began to be used increasingly for data connections, twoshortcomings became
`apparent:
`
`o In a typical user/host data connection (e.g., personal computer user logged on
`to a database server), much of the time the line is idle. Thus, with data con—
`nections, a circuit-switching approach is inefficient.
`- Ina 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
`|PR2017-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 bound on packet length is 1000 octets (bytes). If a source has a longer
`message to send, the message is broken up into 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 order to 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 on to the next node.
`Let us return to Figure 8.1, but now assume that it depicts a simple packet-
`switching network. Consider a packet to be sent from station A to station E. The
`packet will include control information 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), andqueues the packet to go out on that link (the 4—5
`link). When the link is available, the packet is transmitted to node 5, which will for-
`ward the packet to node 6, and finally to E. This approach has a number of advan-
`tages over circuit switching:
`
`a Line efficiency is greater, as a single node—to—node link can be dynamically
`shared by many packets over time. The packets are queued up and transmit—
`ted as rapidly as possible-over the link. By contrast, with circuit switching,
`time on a node-to-node link is preallocated using synchronous time—division
`multiplexing. Much of the time, such a link may be idle because a portion of
`its time is dedicated to a connection which is idle.
`6 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.
`
`
`
`L
`
`I
`l
`’
`I
`I
`I
`I
`l
`l
`
`Userdata
`
`\
`
`\
`
`\
`
`\\
`
`\
`
`\\
`
`1
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\\
`
`\
`
`\\
`
`\i
`
`
`A
`“"T
`‘
`I \
`\\
`I
`\
`\ \
`’
`‘
`‘
`\
`I
`\
`I
`\
`\
`I
`\
`\
`I
`\
`\
`I
`\
`\
`I
`\
`\
`
`II
`
`H—H
`
`II
`
`‘]
`
`Control information
`(packet header)
`\_—‘—P————4
`
`Packet
`
`FIGURE 9.1 Packets.
`
`‘i
`
`i]
`
`,
`
`FatPipe Exhibit 2022, pg. 7
`Cisco v. FatPipe
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 7
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`256 CHAPTER 9 / PACKET SWITCHING
`
`- When traffic becomes heavy on a circuit-switching network, some calls are
`blocked; that is, the network refuses to accept additional connection requests
`until the load on the network decreases. On a packet-switching network,
`packets are still accepted, but delivery delay increases.
`- Priorities can be used. Thus, if a node has a number of 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 packet size. 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 as it attempts to
`route them through the network and deliver them to the intended destination; there
`are two approaches that are used in contemporary networks: datagram and virtual
`circuit.
`
`In the datagram approach, each packet is treated independently, with no ref-
`erence to packets that have gone before. Let us consider the implication of this
`approach. Suppose that station 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-
`ward this packetto either node 5 or node 7 as the next step in the route. In this case,
`node 4 determines that its queue of packets for node 5 is shorter than for node 7, so
`it queues the packet for node 5. Ditto for packet 2. But for packet 3, node 4 finds
`that its queue for node 7 is now shorter and so queues packet 3 for that node. So the
`packets, each with the same destination address, do not all follow the same route.
`As a result, it is possible that packet 3 will beat packet 2 to node 6. Thus, it is also
`possible that the packets will 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 may be lost. If this
`were to happen to one of the packets in our example, node 6 has no way of know-
`ing that one of the packets in the sequence of packets has been lost. Again, it is up
`to E to detect the loss of a packet and figure out how to recover it. 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 and all
`subsequent packets to 5, which decides to route the request and all subsequent
`packets to 6, which finally delivers the Call-Request packet to E. If E is prepared to
`accept the connection, it sends a Call-Accept packet to 6. This packet is passed back
`through nodes 5 and 4 to A. Stations A and E may now exchange data over the
`route that has been established. Because the route is fixed for the duration of the
`logical connection, it is somewhat similar to a circuit in a circuit-switching network,
`and is referred to as a virtual circuit. Each packet now contains a virtual-circuit
`identifier as well as data. Each node on the preestablished route knows where to
`
`FatPipe Exhibit 2022, pg. 8
`Cisco v. FatPipe
`|PR2017-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 E 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
`one virtual circuit to any other station and can have virtual circuits to more than one
`station.
`
`So, the main characteristic of the virtual-circuit technique is that a route
`between stations is set up prior to data transfer. Note that this does not mean that
`this. is a dedicated path, as in circuit switching. A packet is still buffered at each
`node, and queued for output over a line. The difference from the datagram
`approach is that, with virtual circuits, the node need not make a routing decision for
`each packet; it is made only once for 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, because all packets follow the same route, they arrive in the
`original order. Error control is a service that assures not only that packets arrive in
`proper sequence, but that all packets arrive correctly. For example, if a packet in a
`sequence from node 4 to node 6 fails to arrive at node 6, or arrives with an error,
`node 6 can requesta retransmission of that packet from node 4. Another advantage
`is that packets should transit the network more rapidly with a virtual circuit; it is not
`necessary to make a routing decision for each packet at each node.
`'
`One advantage of the datagram approach is that the call setup phase is
`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, because it is
`more primitive, it is more flexible. For example, if congestion develops in. one part
`of the network, incoming datagrams can be routed away from the congestion. With
`the use of virtual circuits, packets follow a predefined route, and it is thus more dif—
`ficult for the network to adapt to congestion. A third advantage is that datagram
`delivery is inherently more reliable. 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
`node fails, subsequent packets may find an alternate route that bypasses that node.
`Most currently available packet—switching networks make use of virtual cir-
`cuits for their internal operation. To some degree, this reflects a historical motiva—
`tion to provide a network that presents'a service as reliable (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 very little difference in the external behavior based
`on the use of datagrams or virtual circuits. If a manager is 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 packet size to be used in the network. There is a
`significant relationship between packet size and transmission time, as illustrated in
`
`FatPipe Exhibit 2022, pg. 9
`Cisco v. FatPipe
`|PR2017-01845
`
`
`
`FatPipe Exhibit 2022, pg. 9
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`258 CHAPTER 9 /, PACKET SWITCHING
`
`Data Data
`2
`1
`
`
`
`
`
`
`
`
`
`Data
`
`
`Data
`2
`
`
`
`(b)
`‘ 2-packet message
`
`'
`
`(d)
`10—packet message
`
`(a)
`1-packet message
`
`FIGURE 9.2 Effect of packet size 0n transmission time.
`
`Figure 9.2. In this example, it is assumed that there isa virtual circuit from station
`X through nodes a and b to 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
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 10
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.1 / PACKET—SWITCHING PRINCIPLES 259
`
`beginning of each packet and is referred to as a header. If the entire message is sent
`as a single packet of 33 octets (3 octets of header plus 30 octets of data), then the
`packet is first transmitted from station X to node a (Figure 9.2a). When‘the entire
`packet is received, it can then be transmitted from a to b. When the entire packet is
`received at node b, it is then'transferred to station ‘Y. The total transmission time at
`the nodes is 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 header or 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 savings in 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 as illustrated in Figure 9.2d; this is because each packet
`contains a fixed amount of header, and more packets means more of these headers.
`Furthermore, the example does not show the processing and queuing delays at 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 packet size
`(53 octets) can result in an efficient network design.
`
`Comparison of Circuit Switching and Packet Switching
`
`Having looked at the internal operation of packet switching, we can now return to
`a comparison of this technique with circuit switching. We first look at the important
`issue of performance, and then examine other characteristics.
`
`Performance
`
`A simple comparison of circuit switching and the two forms of packet switching are
`provided in 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:
`
`0 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 m‘edium, for example, is typically 2 X 108 m/s.
`0 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-kbps line.
`0 Node delay. The time it takes for a node to perform the necessary processing
`as it switches data.
`
`
`
`For circuit 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 order to 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 the call
`request; this time is spent at each node setting up the route of the connection. On
`
`FatPipe Exhibit 2022, pg. 11
`Cisco v. FatPipe
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 11
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`260 CHAPTER 9 / PACKET SWITCHING
`
`Propagation
`delay
`‘ /
`
`Processing
`delay
`
`Call
`requet
`
`Call
`request
`signal
`
`packet
`
`
`Acknowledgement
`signal
`
`link
`
`link
`
`o o o o
`
`Call
`accept
`
`packet
`Acknowledgement
`
`
`packet
`
`(a) Circuit switching
`
`(b) Virtual circuit packet switching
`
`(c) Datagram packet switching
`
`FIGURE 9.3 Event timing for circuit switching and packet'switching.
`
`”the return, this processing is not needed because the connection is already set up;
`once it 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 packet is
`queued at each node and must wait its turn for retransmission. Once the virtual cira
`cuit is established, the message is transmitted in packets. It should be clear that this
`phase of the operation can be no faster 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 packet switching 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 may be 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
`|PR2017-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
`
`No dedicated path
`Transmission of packets
`
`No dedicated path
`Transmission of packets
`
`Dedicated transmission path
`Continuous transmission of
`data
`
`Fast enough for interactive
`Messages are not stored
`
`The path is established for
`entire conversation
`
`Call setup delay; negligi~
`ble transmission delay
`Busy signal if called party
`busy
`Overload may block call
`setup; no delay for
`established calls
`Electromechanical or
`computerized switching
`nodes
`
`Fast enough for interactive
`Packets may be stored until
`delivered
`Route established for each
`
`packet
`Packet transmission delay
`
`Sender may be notified if
`packet not delivered
`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
`Sender notified 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
`
`Overhead bits 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
`Overhead bits in each
`No overhead bits after» call
`message
`setup
`
`Dynamic use of bandwidth
`
`Other Characteristics
`
`Besides performance, there are a number of 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 connected sta-
`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 may arrive 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 overhead bits, such as the destination address.
`
`FatPipe Exhibit 2022, pg. 13
`Cisco v. FatPipe
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 13
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`262 CHAPTER 9 / PACKET SWITCHING
`
`External and Internal Operation
`
`One of the most important characteristics of a packet-switching network is whether
`it uses datagrams or virtual circuits. Actually, there are two dimensions of this char-
`acteristic, as illustrated in Figure 9.4. At the interface between a station and a net-
`work node, a network may provide either a connection-oriented or connectionless
`service. With a connection—oriented service, a station performs a call request to set
`up a logical connection to another station. All packets presented to the network are
`identified as belonging to 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 concept of internal virtual-circuit operation”
`as we shall see. An important example of an external virtual circuit service is X25,
`which is examined in Section 9.4.
`
`—>
`
`
`
`
`Packet-switched
`network
`
`-—->
`
`(a) External virtual circuit. A logical connection is set up between two stations.
`Packets are labeled with a virtual circuit number and a sequence number.
`Packets arrive in sequence.
`
`-—->
`
`-—-—->-
`
`
`
`
`
`
` Packet-switched
`network
`
`
`
`FIGURE 9.4 External and internal virtual circuits and datagrams.
`(continued on next page)
`.
`
`FatPipe Exhibit 2022, pg. 14
`Cisco v. FatPipe
`|PR2017-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 service is
`sometimes known as an external datagram service; again, this concept is distinct
`from that of internal datagram operation. Internally, the network may actually con-
`struct a fixed route between endpoints (virtual circuit), or it may not (datagram).
`These internal and external design decisions need not coincide:
`
`0 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.
`
`0 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 packets at the destination
`node, if necessary, so that they are delivered to the destination station in the
`proper order.
`0 External datagram, internal datagram. Each packetis treated independently
`from both the user’s and the network’s point of View.
`
`0 External datagram, internal virtual circuit. The external user does not see any
`connections, as it simply sends packets one at a time. The network, however,
`sets up a logical connection between stations for packet delivery and may
`
`
`
`(c) Internal virtual circuit A route for packets between two stations is defined
`and labeled All packets for that virtual circuit follow the same route and
`arrive in sequence
`
`
`
`FIGURE 9.4
`
`(continued)
`
`FatPipe Exhibit 2022, pg. 15
`Cisco v. FatPipe
`|PR2017-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 as to 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 external service,
`. we can make the 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 error is retransmitted. This latter 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,
`such as file 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 design is
`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 III.
`
`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 requirements for this
`function include
`
`9 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
`|PR2017-01845
`
`FatPipe Exhibit 2022, pg. 16
`Cisco v. FatPipe
`IPR2017-01845
`
`

`

`9.2 / ROUTING 265
`
`failures and overloads. Ideally, the netw0rk 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 requirement for stability. Techniques that
`react to changing conditions have an unfortunate tendency to 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 the first is underutilized,
`causing a second shift. During these shifts, packets may travel in loops through the
`network.
`
`' A tradeoff also exists between fairness and optimality. Some performance cri-
`teria may give higher priority to the exchange of packets between nearby stations
`compared to an exchange between distant 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
`node and often a transmission overhead as well, both of which impair network effi-
`ciency. The penalty of such overhead needs to be less than the benefit accrued
`based on some reasonable metric, such as increased robustness or 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.
`Some of 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
`Number of hops
`Cost
`
`Delay
`Throughput
`
`Decision time
`
`Packet (datagram)
`Session (virtual circuit)
`
`Decision place
`Each node (distributed)
`Central node (centralized)
`Originating node (source)
`
`Performance Criteria
`
`Network information source
`None
`Local
`
`Adjacent node
`Nodes along route
`All nodes
`
`Network information update timing
`Continuous
`Periodic
`
`Major load change
`Topology change
`-
`
`The selection of a route is generally based on some performance criterion. The sim—
`plest criterion is to choose the minimum-hop route (one that passes through the
`least number of nod