Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 1 of 74 PageID #: 1297
`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 1 of 74 PagelD #: 1297
`
`
`
`
`
`
`
`
`
`EXHIBIT B
`EXHIBIT B
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 29 of 74 PageID #: 1325
`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 29 of 74 PagelD #: 1325
`
`
`
`
`
`
`
`
`
`EXHIBIT C
`EXHIBIT C
`
`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 30 of 74 PageID #: 1326
`
`S
`
`Routing in Multihop Packet Switching
`Networks: Gb/s Challenge
`
`The authors survey networking solutions that have been proposed for high-speed packet-switched
`applications. Using these solutions as examples, they identify the specific problems resulting from
`very high transmission rates and explain how these problems influence the design of high-speed
`networks and protocols. They conclude that the solutions based on deflection routing are the
`most promising ones and suggest a number of directions for their evolution.
`Cesur Baransel, Wlodek Dobosiewicz, and Pawel Gburzynski
`
`NN
`
`ot so long ago, computer networks with
`high transmission rates (e.g., sever-
`al Mb/s) were naturally confined to
`local domains. Although such (and
`higher) transmission rates were available in
`telephony on long distances, they were used on
`a point-to-point basis. Concepts of highly-con-
`nected fast networks spanning geographical areas
`larger than the acreage typically covered by a sin-
`gle institution are relatively new and, besides
`the emerging ATM technology, there are no stan-
`dard commercially available solutions that can be
`recommended for such projects.
`Most of the legacy from local area network-
`ing is not easily adaptable to larger scale networks
`and/or networks with transmission rates sub-
`stantially higher than several Mb/s. Consider
`FDDI as an example. The network operates at
`100 Mb/s and is intended to provide campus-area
`service. The formula expressing the maximum
`effective throughput of FDDI can be roughly writ-
`ten as follows:
`THT
`+
`THT L
`where THT is the maximum token-holding
`time during one rotation of the token, and L is the
`propagation time across the ring. One obvious
`property of T is that it doesn’t grow as more
`stations are added to the network. Conse-
`quently, the more stations the network sup-
`ports the smaller fraction of T is allocated to
`one station. In fact, FDDI assumes that at
`most one pair of stations can communicate at any
`given moment. Besides, due to the bandwidth
`allocation policy of FDDI, more stations means
`larger access delays. If the network is expanded
`geographically (even without increasing the num-
`ber of stations), L will grow reducing the effec-
`
`T
`
`=
`
`CESUR BARANSEL is with
`the Department of Computing
`Science at the Turkish
`Military Academy, Ankara.
`
`WLODEK DOBOSIEWICZ
`is with the Department of
`Computing Science at
`Monmouth University.
`
`PAWEL GBURZYNSKI is
`with the Department of
`Computing Science at the
`University of Alberta.
`
`1 Attempts to accommo-
`date communities of inter-
`est in some bus networks,
`e.g., DQDB [1], have
`been only partially suc-
`cessful.
`
`2 Expressed in the normal-
`ized way—as the number
`of bits separating two
`most distant stations in
`the network [2].
`
`tive throughput in a linear fashion. The same phe-
`nomenon will occur, if somebody tries to extrap-
`olate the FDDI concept onto transmission
`rates substantially higher than 100 Mb/s, e.g., into
`the Gb/s range. Thus, we have to conclude that
`the network doesn’t scale up very well: its prin-
`ciple of operation has inherent limitations
`which restrict its applicability to a relatively
`narrow range of transmission rates, geographical
`areas, and populations of users.
`All unidimensional networks, e.g., busses, rings,
`and stars, are bound to suffer from poor scala-
`bility to the increasing number of users. If all of
`a network’s transmission resources (or a fixed
`large fraction of these resources) must be reserved
`for every single transfer, the network cannot cater
`to a large population of users. Most painfully, it
`cannot take advantage of the localized commu-
`nities of interest which naturally occur in any large
`population.1 Besides, the need to negotiate medi-
`um access across the entire network results in
`a throughput deterioration when the network
`diameter2 is large. Networks that avoid this prob-
`lem (e.g., Metaring [3]) suffer from poor fairness
`and/or starvation potential. Various protocol add-
`ons aimed at alleviating these problems are either
`partially successful (e.g., they exhibit slow respon-
`siveness to dynamic unfairness patterns) or they
`tend to sacrifice throughput to achieve their
`objective.
`The moral from the above observations is
`that the future of high-speed networking, at
`least beyond the local area scale, lies with meshed
`networks. A two-dimensional (planar) mesh
`network with N stations is potentially able to
`achieve a global throughput proportional to
`÷—
`N . By exploring other dimensions, this figure can
`be asymptotically brought as close to N as required.
`Mesh architectures also tend to be organized
`
`38
`
`0890-8044/95/$04.00 1995 © IEEE
`
`IEEE Network • May/June 1995
`
`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 31 of 74 PageID #: 1327
`proper destinations. Different taxonomies of rout-
`according to the geographical distribution of
`ing algorithms are possible, e.g., static vs. adap-
`the interconnected nodes; thus, they may natu-
`tive or centralized vs. distributed. Here we
`rally take advantage of the communities of
`prefer to put them into two groups, namely, table-
`interest to further improve their performance.
`based routing and self-routing.4 The first class cov-
`The existence of multiple paths between nodes
`complicates the communication protocols by
`ers most of the traditional approaches that
`introducing packet switching — the very issue that
`have been applied to many slow networks, includ-
`the unidimensional networks were meant to
`ing shortest path routing and optimal routing. Aside
`avoid. General packet-switching and flow-con-
`from other problems, as convergence delays
`trol techniques traditionally employed in slow
`proportional to the network diameter and sus-
`long-haul networks are usually inapplicable to
`ceptibility to oscillations, these algorithms are
`gigabit networking. To take full advantage of
`computationally expensive and require a sub-
`the high transmission rate of its channels, a
`stantial amount of bookkeeping and periodic
`gigabit packet-switching network cannot spend
`transmission of status information among the
`too much time on making sophisticated rout-
`nodes. In the case of self-routing, the routing
`ing decisions. Also, it should avoid buffering tran-
`decision is solely made based on information
`sient packets at intermediate nodes for extensive
`extracted from the packet’s header, typically
`periods of time. These postulates stem not
`the destination address. Most of the multipro-
`only from the natural need to avoid unneces-
`cessor interconnection networks use this scheme
`sary delays, which are magnified by the high trans-
`(e.g., shuffle-exchange networks, hypercubes,
`mission rates, but also from the need to make
`data manipulator networks, Benes networks, and
`these delays predictable. Modern networks are
`Clos networks). Another well-known example
`expected to handle traffic patterns of various kinds,
`that can be included in this category is flooding.
`and delay-sensitive or delay-variation-sensitive
`This classification groups the routing algo-
`patterns will constitute a substantial part of
`rithms according to the complexity of the rout-
`their load.
`ing decisions and, consequently, to the speed
`In this article, we conduct a survey of pack-
`at which packet switching can be carried out.
`et-switching protocols applicable to meshed
`Another important factor affecting the switching
`networks operating in the Gb/s range. By a
`speed is the organization of buffers for storing
`packet-switching protocol we mean the net-
`transient packets. When there are no buffers
`work-specific portion of the third OSI layer
`at all, purely photonic switching becomes feasible,
`(i.e., the network layer) of the protocol stack. The
`and E/O and O/E (electronic-to-optic and optic-
`full set of packet-switching rules determines
`to-electronic) conversions can be avoided.
`how the network organizes reliable packet
`However, the photonic switching technology is
`delivery between a pair of communicating switch-
`still in its infancy and for the time being is not
`es, possibly located in distant geographical regions
`a practical alternative to its electronic counter-
`of the communication subnet.3 One part of a pack-
`part (see [4]).
`et-switching protocol (according to our defini-
`Table-Based Routing
`tion) is the routing scheme, i.e., the set of rules
`that assign incoming packets to output links.
`In this category of routing schemes, upon a packet
`In general, we can talk about the following
`arrival at an intermediate node, the node consults
`three components of the communication subnet
`a table to select the outgoing link on which the
`which are relevant from our point of view:
`packet is to be forwarded. Although the loca-
`• The routing protocol.
`tion of the routing tables, the way they are
`• The congestion-control mechanisms that can
`maintained, and the information contained
`be effectively incorporated into the routing
`within them may differ from one implementation
`protocol.
`to another, some common characteristics are
`• The network topology.
`shared by all solutions that fit into this class:
`Clearly, these components are not indepen-
`• In most applications, the routing table contains an
`dent, but they are closely related to each other
`entry for every destination, indicating the out-
`and together offer a single functionality.
`put link appropriate for a packet addressed to
`Reflecting this relationship, this article is orga-
`that destination. Therefore, the table size
`nized as follows: we first discuss routing protocols
`increases with the network size and can be
`and congestion-control mechanisms employed
`large for a network with many nodes.
`in contemporary packet-switched networks,
`• For practical reasons (e.g., to cope with conges-
`not necessarily in networks operating at very high
`tion and to bypass faulty links or nodes), entries
`transmission rates. Then, following some basic
`in the routing tables need to be updated. There-
`definitions related to the topology component,
`fore, some network capacity must be allocated
`we investigate the challenges posed by the Gb/s
`to the extra traffic that disseminates status
`transmission rates. A later section is devoted to
`information, reducing the capacity available to
`case studies which cover a number of contem-
`the users.
`porary design proposals. Conclusions and sug-
`The problem of large routing tables in networks
`gestions for further research are presented in
`consisting of a huge number of stations can be
`the last section.
`alleviated by introducing domains, each domain
`representing a cluster of closely-located sta-
`tions which appear (almost) equally distant
`from a sufficiently remote location. From the point
`of view of such a location, it may be appropri-
`ate to route all packets addressed to the domain
`in the same way, effectively treating the domain
`
`Routing Protocols
`I n a multihop packet-switching network, the func-
`
`tion of the routing algorithm is to guide the pack-
`ets through the communication subnet to their
`
`The photonic
`switching
`technology is
`still in its
`infancy and
`for the time
`being is not a
`practical
`alternative to
`its electronic
`counterpart.
`
`3 According to the OSI
`terminology.
`
`4 Also known as header
`routing.
`
`IEEE Network • May/June 1995
`
`39
`
`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 32 of 74 PageID #: 1328
`tion) through link ij. Now, the routing problem
`as if it were a single station. This approach requires
`can be viewed as an optimization problem: the
`a hierarchical structure of the destination address.
`routing decisions should minimize the cost of
`Otherwise, lookup tables are needed to identi-
`resolving the offered load.6 Most commonly used
`fy the domains, which may reduce or even nul-
`lify the potential savings.
`cost functions are related to link capacities and
`the amount of traffic carried by each link which
`is viewed as a flow.
`The basic goal, i.e., optimal routing, is not
`always attainable solely by optimizing the aver-
`age levels of link traffic. Theoretically, there
`exist more effective alternatives (e.g., ones that
`take queue lengths into consideration as well),
`but they are impractical due to the overhead and
`large delays involved in the exchange of the queue
`length information among the nodes [11].
`For example, optimal routing in the CODEX
`network is based on the following cost function:
`(
`) =
`F
`ij
`-
`
`Shortest-path Routing — The basic premise of a
`routing scheme from this class is to have at every
`switch a unique mapping of the destinations to
`the output links. Given a destination address
`extracted from the header of an incoming
`packet, the switch selects the output link that offers
`the “shortest path” to the destination. The notion
`of length may be static, i.e., it may reflect the prop-
`agation distance, the number of hops (interme-
`diate switches), and the nominal link capacities,
`but it may also account for the perceived con-
`gestion level of the links. In the latter case, the
`shortest paths are determined dynamically and
`the routing algorithm can adapt itself to vari-
`able traffic conditions.
`Regardless of the criteria determining the path
`length used in selecting the output link suit-
`able for a given destination, all shortest-path
`schemes are essentially based on global topo-
`logical knowledge of the network. This knowledge
`is represented by the list of all nodes and their
`interconnections (the network graph) with a
`cost assigned to every link [5]. One can see both
`centralized (as in TYMNET) or distributed (as
`in ARPANET) techniques of representing this
`knowledge; however, every node must have
`access to its locally and momentarily relevant
`portion to be able to make routing decisions.
`TYMNET uses virtual circuits and the shortest
`path calculations are performed by a special
`node called the supervisor. The supervisor also
`decides upon the path to be used by a virtual
`circuit. The intermediate nodes are notified about
`the path by a needle packet that travels from
`the source to the destination threading the vir-
`tual circuit along its way, with the data packets
`trailing behind. The shortest-path calculation
`algorithm used by the supervisor is a modified
`version of Floyd’s algorithm [5].
`In contrast, ARPANET employs a distribut-
`ed approach in which every node maintains its
`own data base and carries out the shortest path
`calculations taking itself as the source. The
`original algorithm, based on the Bellman-Ford
`method, was implemented in 1969. 5 It has
`been modified twice since then, in 1979 and 1987,
`due to problems caused by oscillations. The
`latest modification was warranted by the
`increased traffic load, which once again lead to
`severe oscillations. The latest algorithm is still
`prone to oscillations, but not nearly as much as
`the first one [6]. The details of these algorithms
`can be found in [7].
`The common drawback of all shortest-path algo-
`rithms is the use of only one path per source-
`destination pair and their poor adaptability to
`abrupt traffic shifts, which is further limited by
`their inherent susceptibility to oscillations [6].
`
`Optimal Routing — Optimal routing is based on
`the theory of optimal multi-commodity flows.
`Assume that Zij(r) is a function that gives the
`cost of transmitting data at rate r (which may
`be viewed as the percentage of the link utiliza-
`
`5 In that version, the
`nodes exchanged their
`estimated shortest dis-
`tances to every destination
`every 625 ms.
`
`6 Provided that the cost
`function is sufficiently dif-
`ferentiable, it can be
`expanded as a Taylor
`series. If the first deriva-
`tives exist, then at local
`minima the Jacobian gra-
`dient vector has all ele-
`ments zero. If the second
`derivatives exist, the Hes-
`sian is positive definite at
`the minimum. For convex
`functions, the local mini-
`ma are also global. The
`gradient methods are
`based on the Taylor series
`expansion. Optimization
`methods which use only
`Jacobian gradient vector
`are termed first-order
`methods. If the optimiza-
`tion method utilizes sec-
`ond derivatives as well, it
`is called as a second-order
`method. The steepest
`descent method uses Jaco-
`bian gradient to determine
`a suitable direction of
`movement and is the fun-
`damental first order
`method. All in all, the
`appropriate choice of the
`cost function greatly sim-
`plifies the optimization
`process. For details, see
`[8-10].
`
`7 Many internal designs
`for ATM switches are
`based on the interconnec-
`tion paradigm, i.e., the
`switch is treated as a net-
`work of specialized pro-
`cessors.
`
`40
`
`Z
`
`ij
`
`F
`ij
`
`C
`
`ij
`
`F
`ij
`
`+
`
`d
`
`F
`ij ij
`
`(1)
`
`where Cij is the link capacity, Fij is the data rate
`of the link and dij is the processing and propa-
`gation delay. CODEX uses virtual circuits for user
`traffic and datagrams for its own system messages.
`Every node monitors some parameters of its
`adjacent links and periodically broadcasts them
`to all other nodes. The above formula applies
`to the case when all links are of the same pri-
`ority. For multiple priorities and other details see
`[11] and the references in that book.
`Self Routing
`In this class we put all routing techniques that
`either avoid routing tables completely or use
`static, possibly incomplete, routing tables
`which are seldom (or never) updated during
`the normal operation of the network. With self
`routing, a switch accepting an incoming packet
`is able to determine its fate locally without
`consulting the network’s data base in its centralized
`or distributed form. The price paid for the sim-
`plicity of the routing algorithm is its subopti-
`mal character. The gain is in the low cost of routing,
`the simplicity of the switch, and the absence of
`administrative traffic in the network.
`
`Networks with Regular Topologies — If the
`network forms a regular grid with a simple
`repetitive structure, then every switch may be able
`to de-facto “know” the configuration of the entire
`network without resorting to a data structure
`describing the individual locations of all stations.
`Networks with highly regular topologies com-
`monly occur as interconnection backplanes for
`multiprocessor systems.7 Interconnection net-
`works can be constructed from a single stage
`of switches or from multiple stages of switches.
`In a single-stage network, packets may have to
`pass through the switches several times before
`reaching their destinations. Therefore, single-
`stage networks are sometimes called recircu-
`lating networks and the subsequent passes of
`the same packet through the stage of switches are
`called recirculations. The number of recircula-
`tions depends on the connectivity. Generally, the
`higher the connectivity the smaller the number of
`recirculations. Typically, in a multi-stage network,
`one pass through the multiple stages of switches
`is sufficient to deliver a packet to its destination
`
`IEEE Network • May/June 1995
`
`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 33 of 74 PageID #: 1329
`[28]. When this happens, the queues at bottleneck
`[12]. A survey of switching techniques in high-
`nodes grow indefinitely and eventually exceed
`speed interconnection networks can be found
`the available buffer space. Consequently, some
`in [13, 14].
`packets will have to be discarded and later retrans-
`On a larger geographical scale, the regularity
`mitted, thereby wasting communication resources
`in the network topology is taken advantage of
`and feeding back the congestion. It is thus nec-
`in the Manhattan-street network (MSN), which
`is a single-stage solution.8 Although originally
`essary to prevent excess traffic from entering
`the network.
`proposed to cover metropolitan areas, MSNs can
`A special (local) case of congestion is when due
`also be used as interconnection networks.
`to a speed disparity and/or temporary unavail-
`Interconnection networks have been studied
`ability of resources, one receiver cannot accept
`extensively in the literature, mostly owing to their
`the incoming flow. Should this happen, the sender
`applications in distributed computing. Several
`must be made aware of the situation as soon as
`books are available on this subject, e.g., [15-18]
`possible and either adjust its speed or abstain
`as well as survey papers [12, 19-21]. MSNs were
`from further transmissions which are bound to be
`introduced by Maxemchuk [22] and since then
`rejected.
`they have been extensively studied by Maxem-
`Congestion control is a dynamic problem and
`chuk [23-25] and other authors [26, 27]. Later,
`cannot be solved with static mechanisms alone. It
`we discuss hypercubes, shuffle networks, and
`is also a difficult problem to solve due to the
`MSNs.
`following requirements that must be fulfilled
`by a good solution [29]:
`• The scheme must have a low overhead and should
`not offer new traffic to the network during
`congestion.
`• The scheme must be fair so that during the
`congestion the available resources are allocat-
`ed fairly.9
`• The method must be responsive. Due to the
`highly dynamic nature of the network, the resource
`availability profile changes very rapidly. The
`congestion-control procedure should be agile
`enough so that the demand curve can follow
`the capacity curve very closely.
`• The procedure must be robust so that it can
`function effectively under unfavorable conditions
`(e.g., poor availability of network resources at the
`time of congestion).
`• The scheme must be socially optimal. That is, it
`should optimize the performance of the entire
`network, as opposed to considering each user
`in isolation.
`No single classification of congestion-con-
`trol techniques will satisfy everybody, as the
`criteria that can be used for classification are often
`orthogonal and reflect the point of view of the
`researcher. One can naturally consider the fol-
`lowing attributes of a congestion-control
`scheme:
`• Preventive vs. reactive character of the method —
`Preventive schemes try to avoid congestion and
`reactive ones try do something about it, once it
`occurs.
`• The OSI layer in which the scheme is implemented
`— for example, schemes operating in the trans-
`port layer involve the end-points of a data
`path and are global in nature, whereas data-
`link schemes take care of local congestion, e.g.,
`resulting from incompatible transmission rates of
`two immediate neighbors.
`• Feedback-based vs. feedback-free character of
`the scheme — generally, the attractiveness of
`feedback-based techniques decreases with the
`increasing transmission rate of the network
`and/or its geographical size. Feedback-free
`schemes are usually rate-based, i.e., they try to
`allocate some portion of the network’s global
`rate to every data path and confine each sender
`to this portion.
`• Guaranteed-delivery schemes vs. schemes that
`admit packet loss during congestion.
`
`F l o o d i n g N e t w o r k s — Another simplistic
`approach to routing is flooding which, in its purest
`sense, means that an incoming packet is forwarded
`on every outgoing link except the one it arrived
`on [11]. The outstanding qualities of flooding can
`be summarized as follows:
`• The approach is highly robust, in case of link
`failures. As long as the network graph is not
`disconnected, packets always make it to their des-
`tinations. If the network is richly connected, flood-
`ing makes excellent use of alternative routes.
`• Error recovery at the destination is simplified
`by the availability of extra copies of the same
`packet.
`• No routing tables (or other data structures rep-
`resenting the network configuration) are
`required. Thus, network modifications can be
`made on a live network.
`• The scheme is suitable for all topologies, possi-
`bly very irregular ones. Consequently, the network
`is easily expandable.
`• Flooding automatically chooses the shortest
`path (since it chooses every possible path in
`parallel).
`• It is simple to implement and introduces less
`processing overhead than any other routing
`scheme.
`The most important weakness of flooding is
`that packets may loop and, as a result, unlimited
`numbers of copies of a single packet can crop up
`in the network. Therefore, some countermeasures
`to choke this process are necessary for the
`approach to be useful. In general, flooding is con-
`sidered to be more useful in broadcasting
`rather than one-to-one communication. Even
`in networks based on sophisticated routing meth-
`ods, flooding is occasionally used as a simple
`broadcasting technique, e.g., to disseminate
`various components of the network data base
`among individual stations. ARPANET uses flood-
`ing to broadcast periodic status information to
`the nodes. In a later section, we will discuss
`some flooding-based designs.
`
`Congestion Control
`C ongestion is the network state where, because
`
`of mismanagement (e.g., improper access
`and routing), excessive requests, or faults, the
`demand for resources exceeds their availability
`
`Even in
`networks
`based on
`sophisticated
`routing
`methods,
`flooding is
`occasionally
`used as a
`simple
`broadcasting
`technique.
`
`8 In a congested Manhat-
`tan-street network, a
`packet may visit the same
`switch several times; how-
`ever, multiple visits at the
`same switch are never
`necessary for a successful
`packet delivery.
`
`9 It should be pointed out
`that although several for-
`mal and precise defini-
`tions of fairness can be
`found in the literature,
`none in particular is wide-
`ly inferred from the gener-
`al term.
`
`IEEE Network • May/June 1995
`
`41
`
`

`

`Window-
`based flow-
`control
`schemes are
`very slow to
`adapt to
`changing
`load patterns
`and are only
`effective for
`congestion
`scenarios that
`last for
`several round-
`trip delays.
`
`10 The number of packets
`that can be outstanding in
`the network at a time.
`
`11 i.e., data-link, network,
`and transport.
`
`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 34 of 74 PageID #: 1330
`Window-Based Schemes
`The bulk of all research in ATM networks is
`currently devoted to admission control and band-
`width allocation.
`Consider the class of window-based schemes [29]
`which require the recipient to adjust the win-
`Grades of Service
`dow size10 of the sender by sending feedback
`signals. According to the above classification, win-
`In the face of the fact that the proportion of
`dow-based control techniques are reactive in
`multimedia traffic in contemporary networks is
`nature and based on feedback. However, they can
`already significant, and is going to increase
`be implemented in any of the three relevant
`substantially in the near future, it makes sense
`OSI layers,11 be loss-less (if the amount of reserved
`to consider the concept of “service grade” in
`the context of congestion-control policies. A
`buffer space accounts for the maximum feedback
`multimedia application may be willing to accept
`delay), or occasionally lose packets and force their
`a reduced bandwidth for its connection (and
`retransmission. Window-based schemes have
`operate at a lower quality of service) rather than
`been used in a number of slow networks,
`receive no service at all based on the original qual-
`ARPANET, TYMNET, SNA, and CODEX, to
`ity specification. For example, if there is no band-
`name a few. In networks that are not very fast, this
`width at the moment to accept a videophone
`approach is particularly popular and effective for
`call, the customer may downgrade the request
`preventing local congestion (in the sense men-
`to a regular voice connection. But even within the
`tioned above), i.e., for matching the source speed
`domain of video traffic (e.g., tele-conferenc-
`to the processing speed of the destination in a
`ing), one can think of several grades of service
`point-to-point scenario (e.g., in the data-link
`lower grades offering lower quality of the picture.
`layer).
`The grade-of-service approach applies both at the
`The applicability of window-based flow-con-
`connection-setup level and at the level of allo-
`trol schemes to high-speed networks is addressed
`cating bandwidth for individual packets (cells)
`in a number of references [30, 31]. The prob-
`relayed by a switch. A call can be admitted at a
`lems associated with this approach mostly stem
`high quality of service and later downgraded, if
`from the large normalized propagation delays
`the switch cannot deliver the high-quality ser-
`across the network, which render the feedback
`vice due to congestion. The user’s contract
`information obsolete and useless. Window-based
`with the network becomes now flexible, within the
`schemes are also very slow to adapt to chang-
`limits of user’s willingness to put up with ser-
`ing load patterns and they are only effective
`vice deterioration. The algorithm for allocat-
`for congestion scenarios that last for several round-
`ing bandwidth to multiple data streams handled
`trip delays.
`by the switch at any given moment must take
`Acceptance-Level Schemes
`into account the possibility of reducing the
`effective bandwidth assigned to flexible con-
`In high-speed networks, flow-control mechanisms
`nections. This complicates the optimization prob-
`have to be more preventive than reactive
`lem to be solved by the switch [33]. Note that a
`because, in order to react, the involved parties
`reduction in the quality of service implies a reduc-
`must exchange status information across the large
`tion in the cost of the connection both in terms
`normalized diameter of the network. Most of
`the contemporary designs or proposals12 prevent
`of network resources and the charge to the
`user’s account. Besides offering a reasonable ser-
`congestion by exercising flow control at two
`vice to its customers the network should also max-
`levels. First, at the circuit-setup level (call-accep-
`imize its revenue; the optimization problem must
`tance level, according to the ATM terminology)
`be parameterized by both cost components.
`whether the new data stream can be accommo-
`The issue of flexible bandwidth allocation
`dated within the network, considering its present
`along the lines suggested above was investigat-
`load, is checked. According to our classification,
`ed to some extent in [34] and [35]. In [33], the
`such schemes operate in the transport layer
`problem is analyzed in depth and several allo-
`and their primary role is to prevent excess traf-
`cation policies are proposed and compared.
`fic from entering the network, thus avoiding long-
`term congestion. The user is requested to
`Rate-Based Schemes
`submit indicators specifying the extent and
`quality of service demanded from the network.
`Current trends in preventive flow control seem
`Typical examples are the declaration of the
`to be towards rate-based mechanisms [29]. A
`peak rate, the minimum throughput demanded
`well known rate-based control technique is the
`in case of congestion, or some parameters describ-
`leaky bucket scheme [36]. It is a mechanism for
`ing the burstiness of the traffic (e.g., peak rate,
`policing the negotiated transmission rate, which
`average rate, and maximum burst size [32]).
`is translated into the size of a virtual bucket
`Regardless of the specific details of the indi-
`allocated to the session. This bucket is filled by
`vidual designs, the bottom line is the necessity for
`incoming packets, which may arrive spontaneously,
`the user to have a “contract” with the network
`and is emptied (leaks) at the negotiated con-
`stant rate.13 Packets arriving when the bucket
`before being able to proceed with the trans-
`mission. After the call/session/flow has been
`is full are discarded. Leaky bucket is basically
`accepted by the network (using ATM terminol-
`a packet policing scheme that exercises control at
`ogy, we will say that the virtual path has been estab-
`an entry point to the network. Note that its
`lished), the responsibility of monitoring the user’s
`virtue is not in guaranteeing a lossless connection
`adherence to the declared parameters is carried
`at the negotiated rate, but rather in a simple means
`out at the packet (cell) level. Owing to the sta-
`of enforcing the negotiated rate and indicating
`tistical and essentially unpredictable nature of
`(and eliminating) the packets that violate a user’s
`the data flow, this task is anything but trivial.
`contract with the network.
`
`12 Including those aimed
`at ATM networks.
`
`42
`
`IEEE Network • May/June 1995
`
`

`

`Case 1:16-cv-00455-RGA Document 24-2 Filed 10/04/16 Page 35 of 74 PageID #: 1331
`natural means of avoiding local congestion and
`According to our classification, leaky bucket is
`guarantee reasonable packet delivery on the glob-
`a preventive technique, operates