United States Patent (19)
`Bonomi et al.
`
`54 METHOD FOR INTEGRATED TRAFFIC
`SHAPING IN A PACKET-SWITCHED
`NETWORK
`
`75 Inventors: Flavio Giovanni Bonomi, Palo Alto,
`Calif.; Albert Gordon Greenberg,
`Millburn; Jennifer Lynn Rexford,
`Summit, both of N.J.
`73 Assignee: AT&T Corp/CSI Zeinet (A Cabletron
`Co.), Middletown, N.J.
`
`21 Appl. No.: 825,990
`22 Filed:
`Apr. 4, 1997
`(51) Int. Cl. .................................................. H04J 3/14
`52 U.S. Cl. ..................
`... 370/235; 370/413
`58 Field of Search ..................................... 370/229, 230,
`370/231, 232, 233,234, 235, 236, 412,
`413, 414, 415, 416, 417, 418, 389, 392,
`395, 428, 429, 465, 468
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,260,935 11/1993 Turner ..................................... 370/418
`5,268,900 12/1993 Hluchyi.
`... 370/418
`5,499,238 3/1996 Shon ................
`... 370/399
`... 370/412
`5,515,363 5/1996 Ben-Nun et al.
`5,602,830 2/1997 Fichou et al. .
`... 370/412
`5,629,937 5/1997 Hayter et al. ........................... 370/412
`OTHER PUBLICATIONS
`Pierre E. Boyer, Fabrice M. Buillemin, Michael J. Servel,
`and Jean-Pierre Courdreuse; “Spacing Cells Protects and
`Enhances Utilization of ATM Network Links.” IEEE Net
`work, Sep., 1992, pp. 38-49.
`
`
`
`USOO586.4540A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,864,540
`Jan. 26, 1999
`
`Eugene Wallmeir and Tom Worster; “The Spacing Policer,
`An Algorithm for Efficient Peak Bit Rate Control in ATM
`Networks,” Proceedings of 14th International Switching
`Symposium; Oct., 1992, vol. 2, A5.5, pp. 22-26.
`Jennifer L. Rexford, Albert G. Greenberg, and Flavio G.
`Bonomi; “Hardware-Efficient Fair Queueing Architectures
`for High-Speed Networks,” Proceedings of IEEE Infocom
`96, Mar, 1996.
`Jon C. R. Bennet and Hui-Zhang, “Hierarchical Packet Fair
`Queueing Algorithms,” Proceedings of ACM SIGCOMM,
`Aug., 1996, pp. 143-156.
`Jennifer Rexford, Flavio Bonomi, Albert Greenberg, and
`Albert Wong; IEEE INFOCOM: A Scalable Architecture for
`Fair Leaky-Bucket Shaping, 1997.
`Jennifer Rexford, Flavio Bonomi, Albert Greemberg and
`Alberg Wong; IEEE Journal on Selected Areas in Commu
`nications Special Issue on Advances in ATM Switching
`Systems; Scalable Architectures for integrated Traffic Shap
`ing and Link Scheduling in High-Speed ATM Switches,
`1997.
`
`Primary Examiner Huy D. Vu
`57
`ABSTRACT
`
`A Scalable integrated traffic shaper for a use in a packet
`Switched network that regulates multiple connections and
`prevents lost data by integrating link Scheduling and traffic
`Shaping to fairly arbitrate between incoming connections.
`
`18 Claims, 5 Drawing Sheets
`
`GUEST TEK EXHIBIT 1004
`Guest Tek v. Nomadix, IPR2019-00211
`
`

`

`U.S. Patent
`US. Patent
`
`
`
`Jan. 26, 1999
`Jan. 26, 1999
`
`Sheet 1 of 5
`Sheet 1 0f 5
`
`5,864,540
`5,864,540
`
`
`
`

`

`U.S. Patent
`
`Jan. 26, 1999
`
`Sheet 2 of 5
`
`5,864,540
`
`FIG. 2
`
`ESTIMATE
`ARRIVAL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COMPUTE
`C
`
`4.
`
`IDLE
`CONNECTION?
`
`
`
`NO
`
`ENGUEUE ON
`SORTING BIN
`
`44
`
`
`
`ENGUEUE CELL, ON
`CONNECTION FIFO
`
`45
`
`ENGUEUE IN
`TXFIFO
`
`43
`
`

`

`U.S. Patent
`
`Jan. 26, 1999
`
`Sheet 3 of 5
`
`5,864,540
`
`FIG. 4
`
`
`
`DEPORTS
`
`50
`
`5.
`
`
`
`
`
`CONNECTION
`BACKLOGGED?
`
`DEGUEUE FROM
`CONNECTION
`
`52
`
`
`
`
`
`ENGUEUE ON
`SORTING BIN
`
`
`
`ENGUEUE ON
`TXFIFO
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 26, 1999
`Jan. 26, 1999
`
`Sheet 4 of 5
`Sheet 4 0f 5
`
`5,864,540
`5,864,540
`
`
`
`
`
`mm
`
`
`
`m.9:
`
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 26, 1999
`Jan. 26, 1999
`
`Sheet 5 of 5
`Sheet 5 0f5
`
`5,864,540
`5,864,540
`
`S
`8
`m
`t
`
`||
`||
`III“
`s
`301
`
`S
`8
`'\
`N.
`
`o
`8
`d
`
`o0L
`
`Cd
`D
`Cd
`O
`
`u—I
`C)
`CU
`un
`d
`y
`
`S
`200
`
`mo
`
`cy
`(.0
`Co
`O
`CL]
`V
`D
`Co.
`O
`
`0L
`
`6
`C)
`se
`LD
`ad
`d
`
`501
`
`-I 511512513
`
`S.
`410
`
`500
`
`
`
`O
`6
`
`S
`FIG.
`
`400 -I--I-
`
`S.
`
`101
`
`s S
`
`100
`
`

`

`1
`METHOD FOR INTEGRATED TRAFFIC
`SHAPING IN A PACKET-SWITCHED
`NETWORK
`
`FIELD OF THE INVENTION
`The invention relates generally to controlling traffic in a
`communications network. More particularly, the invention
`relates to integrated traffic shaping in an asynchronous
`transfer mode (ATM) Switch operating in a high speed
`network.
`
`BACKGROUND OF THE INVENTION
`Communications networks currently transfer vast quanti
`ties of information in both local and wide area networks The
`information typically consists of Signals (electronic or
`optical) representing digitized or digital voice, Video, and/or
`data that is transferred between endpoints in networks. For
`information to be transmitted in a network, a communication
`path must be established within the network between the
`Sender(s) and receiver(s) of the information. A communica
`tion path may be established by circuit Switching, wherein
`an exclusive channel is established between the Sender(s)
`and receiver(s) throughout the entire transmission and until
`the connection is released. Alternatively, a communication
`path may be established by packet Switching, wherein Vir
`tual circuits or channels are established between Sender(s)
`and receiver(s) and with the channel only occupied for the
`duration of transmission of the packet.
`Packet switching enables networks to handle the heter
`ogenous mix of network traffic with varying Service require
`ments that are encountered in Broadband Integrated Services
`Digital Networks (B-ISDN). Ideally, packet switching is
`Scalable and can reliably establish and maintain Virtual
`channels without any prespecified rates (so-called band
`width on demand). Asynchronous Transfer Mode (ATM) is
`a connection oriented network technology that provides a
`possible framework for ideal packet Switching that is
`designed to Support multiple classes (e.g., voice, Video, data)
`of traffic.
`In ATM, information is transmitted as packets of digital
`information called cells. Each cell includes 53 bytes of
`digital information, ATM is connection oriented; a connec
`tion is formed between the transmitter(s) and receiver(s)
`where each intermediate Switch in the Virtual circuit or
`channel (VC) is aware of the Service requirements and traffic
`parameters of the connection. The links between Switches
`are “virtual' only in that each link may be shared by several
`connections on a demand basis instead of a fixed allocation
`of the entire link to a Single connection as in a circuit
`Switched network. By making each Switch aware of the
`Service requirements and traffic parameters for each
`connection, the quality of Service (QOS) of the channel can
`be guaranteed by the network if the connection stays within
`its Stated traffic parameters.
`The quality of service in an ATM-Switched network
`typically refers to the probability of a cell being dropped,
`(cell loSS) and factors affecting cell delivery timeliness,
`particularly cell delay and cell delay variation. Traffic
`parameters typically refer to the rate at which data bits are
`transmitted through the network (bit rate) and the variations
`in the bit rate (burstiness). Different classes of traffic require
`different levels of QOS and have different traffic parameters.
`For example, Voice communications are typically transmit
`ted at a continuous bit rate (CBR) of 64 Kbit/second with no
`burstineSS and can tolerate Some cell loSS but little delay.
`Another example is compressed packetized Voice or Video
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,864,540
`
`2
`which is transmitted at a variable bit rate (VBR) with
`varying degrees of burstineSS and bounded limits on delay
`because of the need to reconstruct the Video or Voice.
`Computer file transfer and data network applications, on the
`other hand, will generate data at widely varying rates
`without Stringent requirements regarding cell delay and may
`be readily transmitted whenever bandwidth is available in
`the channel at the available bit rate (ABR). Available Bit
`Rate traffic may also be classified as Unspecified Bit Rate
`(UBR) if no minimum cell rate is declared.
`The QOS of a connection in an ATM Switched network
`may be “guaranteed' by “contract' when a connection is
`established through a process of connection admission con
`trol (CAC). Essentially, each connection “contracts” to
`transmit cells to the network at a rate p (bandwidth
`descriptor) with burstiness O (burst descriptor) when the
`connection is established. The network will not allow the
`connection to be established if there are insufficient network
`resources (e.g., buffer and/or bandwidth) to provide the
`required QOS at the contracted traffic parameters.
`Once connections have been established, the connections
`have to be regulated to prevent congestion in the network.
`Although each connection is expected to comply with the
`contracted traffic parameters, it is necessary for the network
`to ensure compliance by the connection. Prior art techniques
`for regulating connections (traffic control) include policing
`the connection and discarding excess cells (i.e., cells vio
`lating the contracted traffic parameters) Seeking to enter the
`network. See, e.g., Boyer, P., “A Congestion Control for the
`ATM.” Proc. 7th ITC Spec. Seminar, Paper 4.3, New Jersey,
`October, 1990 (Describing pick-up policing algorithms).
`Prior art techniques have also Suggested policing by tagging
`the cell loss priority (CLP) bit of non-compliant cells and
`only discarding the cells if the network becomes Sufficiently
`congested to adversely affect network performance.
`Traffic shaping is another form of traffic control for ATM
`Switched networkS. Traffic shaping can be used to ensure
`compliance with the traffic contract when applied at the edge
`of the network or, if applied within the network interior, to
`normalize traffic and limit jitter by reshaping connections
`and Spacing cells. So-called “leaky bucket traffic shaping” is
`often used in ATM Switched networks. In a typical prior art
`leaky bucket traffic shaper, credit “tokens' are provided by
`the traffic shaper at a rate p that represents the Sustainable
`bandwidth for the connection. For example, tokens could be
`provided at a rate of one token every ten time slots, where
`a time slot represents the minimum time for a cell to leave
`the traffic shaper. In other words, a fully utilized traffic
`shaper would transmit one cell every time slot. These credit
`tokens accumulate in a “leaky bucket' that holds up to O
`(burst size) credit tokens. Each cell arriving at the traffic
`shaper must claim a token to pass through the shaper; if no
`tokens are available, the cell is considered "nonconforming”
`and is delayed until a token is available when the connection
`conforms to the traffic contract.
`A traffic shaper determines whether an arriving cell con
`forms to its connection's traffic parameters or descriptors
`using any of a variety of algorithms known in the art, the
`most common of which is the generic cell rate algorithm
`(GCRA) from the ATM Forum. The GCRA computes con
`formance based on a connection's Shaping rate and bursti
`neSS and when the last cell arrived at the shaper from that
`connection.
`Cells are Scheduled for transmission from a traffic shaper
`based on the cell's conformance times. In typical prior art
`traffic shapers, cells are Sorted in exact order of conformance
`
`

`

`3
`times. One prior art implementation is a shift register
`wherein the Sorted cells (or pointers) are stored and appro
`priately shifted when a cell with an intermediate conform
`ance time is added. This implementation is disadvantageous
`because of the prohibitive hardware costs incurred by par
`allel comparison operations and additional circuitry needed
`to compensate for clock rollovers.
`An alternative prior art traffic shaper avoided these draw
`backs by implementing the Scheduler as a Series of bins
`corresponding to Single transmission slots. By traversing the
`bins at the transmission, the traffic shaper can transmit one
`cell at each time slot if there is a cell awaiting transmission
`in the bin. If the bin is empty then a cell will not be
`transmitted during that time slot. This traffic shaper puts an
`arriving cell into the first bin that corresponds to or follows
`its conformance time. There are, however, Several disadvan
`tages with this implementation. Complex logic is required to
`locate an appropriate empty bin and, under heavy traffic
`conditions a cell may be Scheduled for transmission far after
`its conformance time. Moreover, early arrivals inherently
`receive preferential treatment at the expense of cells arriving
`from connections adhering to traffic contract parameters.
`Some of these disadvantages have been addressed by
`another prior art traffic shaper using a calendar queue where
`each bin corresponds to a linked list of cells having a
`particular conformance time instead of a Single cell. In this
`implementation, a cell is merely appended to the linked list
`corresponding to its conformance time. Because only one
`cell may be transmitted at a time, an additional transmit
`queue is required to enqueue multiple cells for Output. This
`implementation does reduce the need for a complex exact
`priority queue, but also has several disadvantages.
`The primary disadvantage is the need to accomodate the
`maximum possible number of conformance times while
`accounting for Switch capacity limitations and the resultant
`possibility of dropping non-conforming cells. Although it
`has been Suggested that a range of consecutive conformance
`times could be associated with each bin to reduce the
`number of bins, (i.e., bin granularity>1), large bin granular
`ity creates excessive jitter distorting traffic parameters, espe
`cially in high bandwidth connections. Moreover, this imple
`mentation does not mediate between multiple connections
`with Simultaneously conforming cells.
`A traffic shaper with multiple incoming connections can
`quickly develop a backlog of conforming cells Simulta
`neously eligible for transmission. Prior art techniques for
`arbitrating amongst the Simultaneously conforming cells
`have proven inadequate, frequently increasing cell-shaping
`delays and distorting connection parameters for all cells,
`even cells that conformed upon arrival. These problems can
`propagate through the network, violating traffic descriptors
`for downstream Switches and further increasing delay and
`loSS. Constant bit rate and real-time variable bit rate con
`nections are particularly impacted because of the inherent
`low tolerance for delay variations.
`Prior art traffic policing and Shaping techniques are prov
`ing to be inadequate for B-ISDN and the heterogenous traffic
`of contemporary networking, resulting in traffic distortions
`and congestion. In particular, the prior art techniques do not
`efficiently handle numerous traffic classes while fairly dis
`tributing network resources amongst Several connections.
`The unique difficulties encountered when attempting to
`shape traffic from Several connections with widely varying
`rates are not adequately handled by prior art policers and
`shapers. For example, prior art policers are unsuitable for
`responding to momentary violations of contract parameters
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,864,540
`
`4
`by connections that are fully compliant over the long term,
`resulting in avoidable packet loSS or traffic disruption. Many
`proposed techniques for fairly distributing network
`resources cannot be readily implemented because they are
`not readily Scalable or impose unacceptable costs (e.g.,
`Switching delays or hardware implementation complexity)
`Without efficient and scalable techniques for traffic shaping,
`the potential of ATM Switched networks cannot be realized.
`SUMMARY OF THE INVENTION
`In View of the foregoing, there is a need for Scalable traffic
`Shaping in a communications network that fairly distributes
`network resources between widely variant connections with
`out incurring excessive costs.
`The present invention simultaneously reduces implemen
`tation complexity and traffic distortions by a novel integra
`tion of leaky-bucket traffic Shaping and rate-based link
`Scheduling. The present invention is able to shape traffic at
`the edges of a network while equitably distributing
`bandwidth, even during periods of bursty traffic Moreover,
`the present invention can also Schedule links in a network
`interior, reducing cell delay jitter and downstream buffering
`requirements.
`Traffic shaping in the present invention is achieved
`through a novel combination of techniques. The initial Step
`is to Separately enqueue each connection coming into the
`Switch. Per-connection queues are more than then mere
`extensions of Sorting bins because they provide a mecha
`nism for additional network management features Such as
`buffer management and flow control. Moreover, per
`connection queuing enables each connection to be treated
`Separately, allowing the traffic shaper to take each connec
`tions unique traffic parameters into account when shaping
`traffic received from that connection. By So doing, it is
`possible to perform weighted Scheduling that provides pref
`erential treatment to connections with critical parameters.
`Weighted Scheduling ensures that high bandwidth connec
`tions or connections with no delay tolerance (e.g., real-time
`video) are able to maintain QOS when switched with low
`bandwidth or ABR connections.
`Per-connection queuing alone will not optimally shape
`network traffic. Another aspect of the present invention is
`“approximate Sorting, ensuring that cells leave the traffic
`shaper approximately, but not exactly, in order of conform
`ance time. This is unlike prior art Systems that perform exact
`Sorting, with each cell leaving the traffic shaper having a
`conformance time equal to or greater than the conformance
`time of the preceding cell. Approximate Sorting, like exact
`Sorting, can be implemented with an output queue and
`Sorting bins, but it differs from exact Sorting in that the
`output queue can be a simple first in first out (FIFO) queue
`without requiring complex parallel comparison and insertion
`circuitry.
`Approximate Sorting may be implemented by moving a
`cell from a per-connection queue directly to an output queue
`if the cell's conformance time has been reached or passed
`and moving cells that are non-conforming into Sorting bins
`until they conform, i.e., the cells conformance time is
`reached. A cell that is in a Sorting bin at its conformance time
`goes directly to the output queue at that time. Cells that are
`not moved from the per-connection queue into the output
`queue until after their conformance time will not be placed
`into the output queue at a location exactly corresponding to
`their relative conformance time, even though these cell
`bypass the Sorting bins. Hence, the output queue will only be
`approximately Sorted.
`
`

`

`5,864,540
`
`15
`
`25
`
`35
`
`40
`
`S
`Fair arbitration amongst the incoming connections is
`another advantage of the present invention. There are Several
`alternative techniques for determining when a cell from an
`incoming connection is processed by the traffic shaper in the
`present invention. The first technique is round robin
`arbitration, whereby a cell coming from a connection is
`processed every time a cell from that connection leaves the
`traffic shaper. During periods of heavy traffic, each incoming
`connection is essentially treated equally with each connec
`tion being Serviced in Sequence. The primary disadvantage
`with this technique is that backlogged high bandwidth
`connections proceSS cells through the traffic shaper at the
`Same rate as backlogged low bandwidth connections, mak
`ing it difficult for the high bandwidth connections to main
`tain quality of Service, even though overall shaping delayS
`and traffic distortions are reduced.
`The present invention addresses this problem by weighted
`round-robin Scheduling. In weighted round-robin
`Scheduling, Some connections receive preferential treatment
`to ensure that more cells from the preferred connections are
`being processed by the traffic shaper at a given time.
`Weighted round-robin Scheduling essentially operates by
`allowing Several cells from a high bandwidth connection in
`the traffic shaper Sorting unit Simultaneously. Instead of
`processing one cell from the per-connection queue at a time,
`Several cells are processed Simultaneously. The Scheduling is
`weighted in favor of the high bandwidth connections, ensur
`ing that each connection has a quantity of cells in the output
`queue proportionate to the connection's bandwidth. This
`enables each connection to provide an appropriate quality of
`Service during periods of high traffic, even if every connec
`tion is backlogged.
`Weighted round-robin Scheduling addresses one aspect of
`the difficulties created when low and high bandwidth incom
`ing connections share a traffic shaper, but other difficulties
`remain. One of the difficulties inherent when connections
`with widely varying rates are common to a Single traffic
`shaper is the wide variance in conformance time intervals
`The interval between conformance times for a low band
`width connection is much larger than the interval between
`conformance times for a high bandwidth connection The
`possible conformance times for a low bandwidth connection
`may extend far into the future, especially relative to the
`possible conformance times of high bandwidth connections.
`It is frequently impractical to have Sorting bins correspond
`ing to the conformance times of both the high bandwidth
`connections (with Short intervals between the Sorting bin
`conformance times) and the low bandwidth connections
`(with lengthy intervals encompassing several high band
`width conformance time intervals), and increasing bin
`granularity distorts traffic. However, the hierarchical archi
`tecture of the present invention provides a Solution to these
`problems that avoids traffic distortions. Grouping connec
`tions based on their bandwidth requirements provides high
`bandwidth connections with Small granularity Sorting
`advantageously reducing jitter and cell Shaping delay with
`out requiring a prohibitively large number of Sorting bins.
`Moreover, the weighted round-robin Scheduling techniques
`of the present invention are equally applicable to arbitration
`between groups, further reducing traffic distortion and
`improving traffic shaper performance.
`The advantages and alternatives of the integrated traffic
`shaper disclosed herein is described in J. Rexford et al., “A
`Scalable Architecture for Fair Leaky-Bucket Shaping,” to be
`published in Proceedings, IEEE INFOCOM, April, 1997;
`and J. Rexford et al., “Scalable Architectures for Integrated
`Traffic Shaping and Link Scheduling in High-Speed ATM
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Switches,” to be published in IEEE Journal on Selected
`Areas in Communications, Special ISSue on Advances in
`ATM Switching Systems, 1997, the disclosures of which are
`incorporated by reference herein.
`This invention provides an integrated System for shaping
`traffic in packet-Switched networks that ensures resources
`are fairly shared between all Switched connections while
`maintaining minimum QOS for each connection. This
`unique integration of novel techniques forms a traffic shaper
`capable of providing traffic shaping for the variety of net
`work traffic classes possible in ATM networks. In contrast to
`prior art traffic Shaping techniques, the present invention
`arbitrates fairly between all incoming connections and is
`highly Scalable, thereby enabling ASynchronous Transfer
`Mode networks to be used to their full potential.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a Schematic representation of a Scalable shaping
`architecture according to an embodiment of the present
`invention.
`FIG. 2 is a flowchart representation of a procedure for
`determining the conformance time of an arriving cell.
`FIG. 3 is a flowchart representation of a procedure for
`traffic shaping upon cell arrival.
`FIG. 4 is a flowchart representation of a procedure for
`traffic shaping upon cell departure.
`FIG. 5 is a schematic representation of a hierarchical
`Scalable Shaping architecture according to the present inven
`tion.
`FIG. 6 is a block diagram representation of a hardware
`implementation of an embodiment of the present invention.
`DETAILED DESCRIPTION
`A novel traffic shaper for use in a packet Switched network
`is described herein. This traffic shaper is optimally Suited for,
`but not limited to, high Speed Switches in an ASynchronous
`Transfer Mode network. The disclosed traffic shaper is a
`novel implementation of per-connection queuing and
`approximate Sorting techniques Suitable for Shaping traffic
`arriving from Several connections with varying bandwidth
`and traffic characteristics Such as burstineSS. This novel
`implementation is highly Scalable, requiring only a fixed
`number of operations to process a cell upon arrival or
`departure from the traffic shaper. By integrating link Sched
`uling into the traffic shaper, the present invention is able to
`fairly allocate network resources between incoming connec
`tions in a novel manner that guarantees a minimum Quality
`Of Service for each connection. A novel hierarchical imple
`mentation of the present invention is disclosed by which
`traffic from connections with widely variant bandwidth
`requirements can be fairly shaped without excessive hard
`ware requirements. An efficient hardware implementation of
`the present invention is also disclosed.
`FIG. 1 illustrates the Scalable architecture of the novel
`traffic shaper In one embodiment of the present invention,
`cells enter the traffic shaper through input 1 and are initially
`routed to a set of connection queues 10. The Set of connec
`tion queues 10 interface to a Sorting unit 20 acroSS connec
`tion 2 and the cell is ultimately transmitted to the network
`through output 3. Although only three connection queues 11,
`12 and 13 are shown in FIG. 1, there is a queue for each
`connection coming into the traffic shaper, e.g., a traffic
`shaper with ten incoming connections would have ten
`queues. In a preferred embodiment of the present invention
`the connection queues are first in first out linked lists
`(FIFOs).
`
`

`

`7
`Cells that arrive from an idle connection pass directly
`through the connection FIFOs 10 and across connection 2 to
`Sorting unit 20. If the connection is not idle, i.e., if a previous
`cell from the connection is in connection FIFOs 10 or sorting
`unit 20, the newly arrived cell is enqueued on the appropri
`ate connection FIFO. A cell entering sorting unit 20 will be
`enqueued on a Sorting bin 21, 22 or 23 if it is non
`conforming or enqueued on an output queue 24 if it is
`conforming.
`A cell is conforming if its conformance time c has been
`reached or passed (i.e., cist). In the preferred embodiment,
`cells are not placed in the transmission queue in exact order
`of conformance times. Instead, transmission queue 24 is a
`FIFO which is approximately sorted by conformance times.
`Cells entering sorting unit 20 from connection FIFOs 10
`after their conformance time are not inserted into transmis
`Sion queue 24 at the exact position corresponding to their
`conformance time but are instead appended to the end of
`transmission queue 24. Although a cell entering Sorting unit
`20 at its conformance time is also appended to the end of
`transmission queue 24, this operation enqueues the cell at
`the same location exact Sorting would since no cells with
`later conformance times are in transmission queue 24. Cells
`enqueued from a Sorting bin are similarly positioned in
`transmission queue 24 at the exact Sorting location
`(assuming bin granularity of 1).
`The approximate Sorting of the present invention advan
`tageously reduces implementation complexity in the traffic
`shaper. For example, parallel insertion capability is not
`required in the transmission queue. More significantly and
`perhaps unexpectedly, approximate Sorting performs better
`than exact Sorting for connections with Similar bandwidth
`characteristics by guaranteeing a minimum Service rate for
`each connection on a Small time Scale.
`The number of Sorting bins required for the Sorting unit is
`advantageously independent of the number of incoming
`connections or the amount of backlogged traffic at the
`switch. The granularity of the bins (i.e., the number of
`consecutive conformance times associated with a single bin)
`and the Shaping rate of the slowest incoming connection
`(i.e., the minimum shaping rate, p.) determine the maxi
`mum number of Sorting bins required for the illustrated
`embodiment of the present invention. The optimal number
`of Sorting bins for a Sorting unit in the present invention
`varies depending on the divergence of incoming connection
`bandwidth parameters, the lowest Shaping rate determines
`the range and the highest Shaping rate determines the grain.
`The bounded number of sorting bins is a product of
`per-connection queuing. A cell arriving in Sorting unit 20
`will have a conformance time 1/p or less time slots in the
`future. Cells with conformance times farther in the future
`will be enqueued in a connection FIFO until the previous
`cell from that connection has been transmitted. For example,
`if a cell in Sorting unit 20 was transmitted at its conformance
`time, the next cell from the same connection will necessarily
`conform in 1/p time slots (or less if the connection has
`unused O) and would be placed in the corresponding Sorting
`bin.
`Because of the bounded number of sorting bins and the
`reduced complexity of a single approximately Sorted trans
`mission FIFO, the present invention has a highly scalable
`architecture. The Scalability of the present invention is
`further enhanced because a Small, bounded number of
`operations are performed each time a cell arrives at or
`departs from the novel traffic shaper. Thus, only the number
`of connection queues increases in direct proportion to the
`number of connections to the traffic shaper.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,864,540
`
`8
`The first thing that occurs when a cell arrives at the traffic
`shaper is computation of the cell's conformance time c.
`Conformance time is the time at which an arriving cell
`conforms to the contracted traffic parameters of the connec
`tion the cell is coming from. These traffic parameters rep
`resent a negotiated agreement between the network and the
`connection whereby the network agrees to provide a specific
`quality of Service and the connection agrees to only transmit
`a specific number of cells in a given interval. The rate at
`which the connection agrees to transmit cells to the network
`is the bandwidth or shaping rate p. In addition, the network
`may agree to allow the connection to transmitbursts of cells
`exceeding the negotiated Shaping rate. The number of nego
`tiated exceSS cells is the burstineSS, O, of the connection. In
`one embodiment of the present invention, conformance time
`is computed using the generic cell rate algorithm of the ATM
`Forum as illustrated by the flowchart of FIG. 2.
`A cell's conformance time is determined from the cells
`estimated arrival time, X, the contracted traffic parameters
`for the cells connection, p and O, and the arrival time of the
`last cell from the same connection. Referring to Step 31 of
`FIG. 2, if a cell has not been received from a connection for
`a relatively long period of time or the traffic shaper has just
`been initialized, the State variable X, representing the cells
`arrival time, is initialized to -1/p to avoid clock wrap
`around errors. If X is not reinitialized then it corresponds to
`the arrival time of the previous token received from the
`connection. The cells arrival time is estimated at Step 32. A
`cell's estimated arrival time is X-1/p or the current time, t,
`whichever is greater. Whether the estimated arrival time X
`complies with the traffic contract is determined at step 33
`where X is compared to t+1/O. If X is less than or equal to
`t+O/O then the connection is complying with the traffic
`contract and the cell is conforming as shown in Step 34. In
`the case of a conforming cell, conformance time c equals the
`current time t. AS Shown in Step 35, if X is greater than t--O/p
`the cell is non-conforming and the conformance time is Set
`to comply with the contracted traffic parameters, c=X-O/O.
`The operations performed when a cell arrives at the traffic
`shaper are shown in FIG. 3. As noted above, the first
`operation performed is computation of cell conformance
`time, c, as shown in Step 30. AS shown in Step 41, the next
`operation is a determination of whether the connection is
`currently idle, i.e., there are no cells from the conn