(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0097719 A1
`Chaskar et al.
`(43) Pub. Date:
`Jul. 25, 2002
`
`US 2002O097719A1
`
`(54) METHOD AND APPARATUS FOR TRAFFIC
`SHAPING FOR PROUTER
`QUEUES/EGRESS
`
`(22) Filed:
`
`Dec. 1, 2000
`
`Publication Classification
`
`(76) Inventors: Hemant M. Chaskar, Woburn, MA
`(US); Rayadurgam Ravikanth,
`Waltham, MA (US)
`Correspondence Address:
`ROBERT C. ROLNIK
`NOKIA INC.
`6000 CONNECTION DRIVE
`MD 1-4-755
`IRVING, TX 75039 (US)
`(21) Appl. No.:
`09/727,559
`
`(51) Int. Cl. ............................................. H04L 12/28
`(52) U.S. Cl. ............................................ 370/392; 370/408
`(57)
`ABSTRACT
`A shaper 201 and a scheduler 203 are combined to determine
`a target tree 203 and insert 207 a tag into a data structure,
`wherein the tag is associated with a packet that has reached
`the head of line (HOL) of a queue in a packet router. A tag
`may become an eligible tag and be placed in a set of tags to
`be searched. Such tags are Searched for the Smallest tag. A
`packet associated with the Smallest tag is transmitted if the
`output link is available.
`
`/OO
`
`
`
`Cloudflare - Exhibit 1043, page 1
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 1 of 6
`
`US 2002/0097719 A1
`
`/do
`
`
`
`Cloudflare - Exhibit 1043, page 2
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 2 of 6
`
`US 2002/0097719 A1
`
`10 f -
`52
`
`S6
`
`CS 57
`
`ear-r
`- art
`
`i5 4
`- -
`- - - T /
`
`Cloudflare - Exhibit 1043, page 3
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 3 of 6
`
`US 2002/0097719 A1
`
`C
`
`265
`
`SS - 2
`
`Cloudflare - Exhibit 1043, page 4
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 4 of 6
`
`US 2002/0097719 A1
`
`
`
`Cloudflare - Exhibit 1043, page 5
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 5 of 6
`
`US 2002/0097719 A1
`
`
`
`Cloudflare - Exhibit 1043, page 6
`
`

`

`Patent Application Publication
`
`Jul. 25, 2002 Sheet 6 of 6
`
`US 2002/0097719 A1
`
`5o \
`
`5 & 2,
`
`Cloudflare - Exhibit 1043, page 7
`
`

`

`US 2002/0097719 A1
`
`Jul. 25, 2002
`
`METHOD AND APPARATUS FOR TRAFFIC
`SHAPING FOR IP ROUTER QUEUES/EGRESS
`
`FIELD OF THE INVENTION
`0001. The invention relates to providing a traffic shaping
`and Scheduling function for the release of packets from a
`queue, and more particularly, to providing a Scalable, low
`latency and low-loss, traffic Shaping in a variable-length
`packet network that can work in conjunction with various
`Scheduling algorithms.
`
`BACKGROUND OF THE INVENTION
`0002. A router of packets or cells in either an internet
`protocol (IP) or asynchronous transfer mode (ATM) net
`work, must associate incoming packets or cells with an
`output port or link. For purposes of discussion, we will refer
`only to packets as a more generalized form of cell. The link,
`in order to avoid local collisions at a router or data Switch,
`must often queue packets before dispatching. The act of
`Selecting from two or more queues of a packet having the
`correct priority for transmission on the output link is the job
`of the Scheduler unit. The Scheduler unit in a router Sched
`ules packets for transmission, thus transmitting packets from
`one queue at a time. Frequently Scheduling algorithms
`running on the Scheduler unit have measures in place to
`either 1) not play favorites among the input queues; or 2)
`favor an input queue or a data flow according to an estab
`lished priority Scheme. In Some cases, a pseudo-random
`element may be introduced into the Selection of packets for
`transmission. Frequently Such pseudo-random elements
`have been used to determine when to discard packets when
`queue overflows are occurring or are imminent.
`0.003 Shaping, or the processing done by a shaper unit,
`has different goals however. Rather than prepare packets for
`transmission from different queues, a shaper will time, or
`delay packets from a particular queue to enforce limitations
`on rates of data or rates of packets allowable from that
`queue. This action Smoothes out the burstineSS that would
`otherwise occur in the output link of packets from that
`queue. The intended outcome and goal of the shaper, is to
`diminish wide Swings in data rates to routers downstream
`from the current router, and diminish the chances of buffer
`overflow in those routers.
`0004 Some developments in routers have been able to
`combine shaping algorithms with Scheduling algorithms.
`The competing goals under Such Schemes are to maintain
`fairneSS among queues, minimize delays and drops of pack
`ets, reduce burstineSS while keeping the algorithm to a
`modest complexity that can Scale to ever increasing traffic
`rates and Sources. One Such attempt has been limited to
`scheduling and shaping of ATM cells (Jennifer Rexford,
`Flavio Bonomi, Albert Greenberg, and Albert Wong, “Scal
`able Architectures for Integrated Traffic Shaping and Link
`Scheduling in High-Speed ATM Switches”, IEEE Journal on
`Selected Areas in Communications, Vol. 15, No. 5, June
`1997, pp.938-950.) Therein, architectures are disclosed that
`perform a shaping operation in Series with a Scheduling
`operation. In addition, the architectures are limited to fixed
`cell sizes used in ATM.
`0005. In developing routers that have both scheduling
`and routing, it is imperative that complexity of the algo
`rithms that perform these functions is kept low. Low com
`
`plexity algorithms reduce computational delays, and
`enhance the Scalability of the router, i.e. the router may
`handle more data or more links or both.
`0006 Routers generally have central processing units
`that execute programmed instructions. Such instructions
`may be stored in a memory unit. The memory unit may also
`hold data Structures that permit various operations to occur.
`Such data Structures may include queues that may store data
`packets that await transmittal from the router.
`0007. A memory location may be addressed by various
`means in the art. An array or a linked-list data Structure may
`have conceptually adjacent Storage Space in a memory
`location. A datum Stored adjacent to another datum, is Said
`to be one step away from the first datum. Similarly, the term
`location is used interchangeably with Storage Space, Such
`that both terms denote a Space in memory that may be
`addressable in linear terms as an absolute location related to
`the beginning of memory. Memory may be allocated
`dynamically So that, although Storage may not be physically
`next to each other, an array, for example, may be indexed in
`Sequential Steps.
`0008. A data structure has a capacity to store data or a
`Storage capacity. Such a capacity may be strictly limited, e.g.
`as in an array having a preset number of elements. Such a
`capacity may be open-ended, Such as a linked list, or a tree
`Structure, in which capacity may be limited only to the
`amount of available unallocated memory.
`0009. A binary tree is a useful data structure. Its advan
`tages are that it can be grown to the limits of available
`memory, and be rapidly reallocated by Setting a root node
`pointer to null. Similarly, Such a tree can be rapidly Searched
`and navigated to locate a Smallest or largest data element
`Stored amongst its nodes.
`
`SUMMARY OF THE INVENTION
`0010. According to an embodiment of the invention, a
`packet that reaches the head of line (HOL) of a queue is
`handled by a release-time calculator to determine whether to
`discard a packet, associate the packet with an eligible tag, or
`place the packet or associated data amongst trees waiting to
`become eligible. If the packet is not discarded, a tag, which
`may be a floating-point number, is created for the packet.
`The tag may operate as a criterion for Sorting a packet in a
`binary tree of tags.
`0011. The tag, then, is one of the determinants of the
`order in which Several packets are Selected for transmission.
`The tag may be added to a data structure, which may be a
`circular-data Structure Such as a list of trees that is rotated
`after each time interval or delta time. There may be a band
`of eligible trees in the list of trees. The tag may be added to
`the latest of the eligible trees, or added to a tree in the list
`that may eventually be added to the band of eligible trees.
`The operation of a tree shifting from an ineligible tree to the
`band of eligible trees may be a Step to Select an eligible Set
`of trees. The operation of Selecting an eligible Set of trees
`may include removing a tree from the eligible Set of trees.
`A Set of eligible tags may be created from tags in the eligible
`trees. The Set of eligible tags may expand to include tags that
`had formerly been in an eligible tree.
`0012 Tags may be removed from the data structure when
`a tag is the Smallest among tags in the eligible Set of tags.
`
`Cloudflare - Exhibit 1043, page 8
`
`

`

`US 2002/0097719 A1
`
`Jul. 25, 2002
`
`When this occurs, a packet associated with the tag may be
`transmitted through the output link. A larger tag will have
`priority in as compared a Smaller tag that has not yet entered
`the eligible Set of trees. Otherwise, the Smallest tag always
`prevails amongst the Set of eligible tags. This results in
`Selection of a tree without consideration of any release time
`asSociated with the tree for purposes of Selecting a tag or
`packet associated with the tree, So long as the tree has
`graduated to be among the eligible trees. Thus a release time
`calculation of a shaping algorithm influences Selection only
`to the extent the shaping algorithm may delay associating a
`packet and tag with an eligible set of tags.
`0013 The present invention may provide the flexibility to
`perform traffic shaping on flows having packets of arbitrary
`length, and therefore, may be Suitable for internet protocol
`(IP) routers. More importantly, a Scheduling algorithm may
`be performed as well. A maximum complexity may be set in
`Some embodiments by limiting complexity of trees, and
`therefore tree-Sorting algorithms, by discarding packets
`upon conditions of tree overflow and Stale tags. Such trees
`enhance Shaping because their data content is chiefly tag or
`Shaping information.
`0.014 Embodiments of the invention are easy to scale
`upward to high-transmission Speeds, and computational
`times, in most cases, do not increase as fast a transmission
`throughput. For example, an algorithm using a single tree to
`store the scheduled (only) release times of multiple flows of
`packets will be as complex or more complex than a distrib
`uted Set of trees having both a Scheduling component and a
`Shaping component in their organization. Consequently, the
`time to build the data structure of multiple trees (per an
`embodiment) will be no worse than a competing algorithm;
`and moreover, the time to Select an optimal packet for
`transmission may similarly be no worse than the competing
`algorithm. The complexity of tree additions and removals
`according to one or more embodiments of the invention
`increases as a logarithmic function of the number of flows
`that are competing for the output port. In addition, the
`Scheduling function and the Shaping function can be said to
`be largely complete prior to inserting data to a circular-data
`Structure. Additional operations may occur afterward; how
`ever, this aspect of doing much of a Scheduling operation
`concurrent to shaping calculations is efficient as compared to
`a purely Serial-shaping, then Scheduling, algorithm.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0015 The disclosed inventions will be described with
`reference to the accompanying drawings, which Show
`important Sample embodiments of the invention, wherein:
`FIG. 1A shows a list of tree pointers;
`0016
`0017 FIG. 1B shows a tree of tags pointed to by a tree
`pointer of FIG. 1A;
`0.018
`FIG. 2 shows a block diagram of a combined
`shaper and Scheduler apparatus according to an embodiment
`of the invention;
`0019)
`FIG. 3A shows the construction of a min-tree;
`0020 FIG. 3B shows the relationship between the list of
`tree pointers and the min-tree;
`0021
`FIG. 4A shows a selection set of tree pointers used
`by a first alternative mapper;
`
`0022 FIG. 4B shows a selection set of tree pointers used
`by a Second alternative mapper; and
`0023 FIG. 5 shows non-optimal three-node combina
`tions and an optimized three-node combination of a binary
`tree.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`0024 FIG. 1A shows a data structure 100 of root-node
`pointers to tree-data Structures, which may be binary trees.
`The data structure 100 may be a linked list or an array or a
`number of equivalents. The list may be circular in nature,
`Such that moving a pointer 101 along the list in a given
`direction eventually brings the pointer to its starting point.
`The list stores M pointers to trees, which may be initialized
`to null pointers. An indeX may be used to track the list, Such
`that a list element, or tree number may be numbered 0
`through M-1. AS an example, for a list of M elements, there
`may be list elements 0 through 199. There is a release time
`asSociated with each tree. The release time may indicate the
`earliest time when the corresponding tree becomes eligible
`for transmission.
`0025. A current tree pointer 163 may be used to identify
`or Select one or more trees that may contain tags associated
`with packets that are eligible for transmission. Each node in
`the trees pointed to by the elements of list 100, e.g. the left
`node 155, may be a tag representing the Scheduling priority
`and information concerning a packet identity or Storage
`location. The terms left and right are arbitrary spatial terms.
`An equally fitting term of Smaller node and larger node, or
`Smaller Side and larger Side could be used. The tree, in
`essence, may be a binary tree.
`0026 FIG. 1B shows a tree that may be pointed to by a
`list element 101. The tree may have a root node 153, a left
`node 155 that is located to the left of the root node 153, and
`a right node 157 that is located to the right of the root node
`153. A list element 101 may be associated with a range of
`times.
`0027. There are points of interest along the list 100. In
`order from oldest time to newest or most futuristic time, the
`points are a) current tree having a current-tree pointer 163;
`and b) release-time, tree pointer 165. Each list element, e.g.
`tree pointer 172, may have a future neighbor or future
`neighbor tree 173 and a past neighbor or past-neighbor tree
`171. One or more trees in the future may comprise a future
`neighborhood. One or more trees in the past may comprise
`a past neighborhood. The cutoff for eligible trees 161 may be
`T-time units before the current tree 163. An advancement of
`the tree pointed to by current tree pointer 163 may result in
`list element or old tree 162 being more than T from the list
`element pointed to by the current-tree pointer 163. That list
`element or old tree 162 may be converted or reallocated 140
`to a T1-time units, list element 167 in the future. The tree
`pointers that extend from the tree pointed to by current-tree
`pointer 163 to far-future tree 167 may comprise a future
`portion 180 of the data structure. The future portion may
`thus be the T-list elements right of the current-tree pointer
`163 and including the current tree. An advancement or
`forward movement of the pointerS may occur when a time
`unit (delta-t) has elapsed. This causes current-tree pointer
`163 to move from left to right, i.e. the pointer points to a
`future neighbor, while the last eligible tree 162 is reallocated
`
`Cloudflare - Exhibit 1043, page 9
`
`

`

`US 2002/0097719 A1
`
`Jul. 25, 2002
`
`140. Looking at it another way, the list elements move from
`right to left, while a current-tree pointer 163 remains
`unchanged in position.
`0028. The tree pointed to by the current-tree pointer 163
`and all trees to the left of it, including the tree at Tunits from
`the current-tree pointer, are called post-current trees. All tags
`within these trees are post-current tags. In addition, any tags
`that were once in the post-current trees, and that continue to
`be available, may also be known as post-current tags. The Set
`of trees that are post-current trees changes with every
`advancing of the current-tree pointer. Similarly, the portion
`of the data structure which is the future portion shifts to
`reflect the movement of the current-tree pointer.
`0029 Reallocating all tags in an old tree, or reallocating
`Substantially all tags in an old tree is the operation of
`destroying the tree. The tree may be reinitialized to a null
`pointer at this time. A tag that was the Smallest tag in a tree
`at the time of tree destruction is called a vestigial tag.
`0.030. What does this have to do with packet queues and
`Scheduling a packet for transmission? Well, traffic or packets
`that conform to a shaping algorithm, e.g. the leaky bucket
`algorithm, are immediately eligible for transmission on the
`outgoing link. Each Such packet may be assigned a tag based
`on a weighted, fair-queueing algorithm, Such as Virtual
`clock. This tag represents the transmission priority of the
`packet relative to all the packets that are currently eligible
`for transmission. Note that the ordering of release times does
`not necessarily imply the same ordering of tags. The tag may
`be placed in a tree, where the tree receiving this tag is
`determined as per a release-time algorithm. For each queue
`at the output port of a router, a traffic-shaping profile is
`provided, which may be based on the leaky-bucket algo
`rithm.
`
`0031. The leaky bucket, as known in the art, may have
`two parameters: R, the rate at which tokens are added to the
`bucket; and B, the capacity of the bucket to store tokens. No
`more than B tokens may be added to the bucket. A packet
`having a block size of L bytes must claim L tokens from the
`bucket before it is eligible for transmission. This ensures that
`the bytes transmitted on the output link from that queue is
`always less than or equal to R*time--B, where time rep
`resents any time interval. The foregoing defines the leaky
`bucket shaper.
`0.032
`FIG. 2 shows a combined shaper and scheduler
`according to an embodiment which includes a release-time
`processor 201 which may use Scheduling algorithms known
`in the art, e.g. a leaky bucket. A release-time algorithm based
`on the leaky bucket may operate as shown in table 1,
`wherein the quantity of tokens present in the bucket at a
`given instant is denoted by X. The departure time of the
`last-data block on the output link is denoted by y, and the
`present time is denoted by t. The rate the bucket fills with
`tokens is R; L is the size of a packet that reaches the HOL
`position of a certain queue in the output interface at time t.
`B is the bucket size. B, X, R, and L may be expressed in
`consistent units, including bytes.
`
`TABLE 1.
`
`Pseudocode
`
`Comment
`
`1 Temp = min(x + R(t - y)", B);
`2 If (temp >= L)
`
`3 THEN
`4 x = x - L.
`
`Use absolute value of t-y
`If there are more than or equal to L
`tokens present in the bucket
`
`Claim L tokens from the bucket so
`that new bucket occupancy is
`X - L.
`
`6 Release time = y;
`7 ELSE
`8 X = 0;
`
`9 Y = y + (L - Temp)/R
`
`10 Release time = y
`
`New buffer occupancy at release
`time is going to be 0 as this block
`is going to claim all the tokens that
`would arrive until release time.
`Estimate the time it will take to fill
`the bucket to level L starting from
`the current occupancy, Temp
`
`0033. The if-then branch of the foregoing pseudocode
`Sets release time to now, whereas, the else branch of the
`pseudocode Sets release time to Some time in the future. The
`above algorithm would be used to operate on the packet that
`is at the head of line (HOL) of the queue.
`0034 FIG.2 shows the operation of the combined shaper
`and Scheduler. The release-time processor 201 generates the
`release time, which may be according to a Scheduling
`algorithm. If the release time is too far into the future, e.g.
`release time>T, where T represents a cutoff or discard time,
`then the packet is discarded. Otherwise a mapper 203
`identifies a target tree based on the current time, release
`time and the current tree in relation to the time granularity
`or delta-t and the available number of trees, or M.
`Target tree=current tree+(release time-current time)/
`delta-timodulo M
`0035. The target tree is the whole unit calculation of the
`modulus operation, and operates as an indeX into the data
`structure 100. Thus each tree is associated with a quantized
`period of time. For example, the tree one Step ahead of the
`current tree is associated with the delta-t time period ahead
`of the current tree. A tree two steps ahead of the current tree
`is associated with the next delta-t time period ahead of the
`current tree, wherein the first delta-t time period of the first
`tree does not overlap with the Second delta-t time period of
`the Second tree.
`0036 Packets that satisfy the cutoff time are associated
`with a scheduling tag from scheduler 205, which may be a
`weighted, fair-queuing algorithm, Such as Virtual clock,
`among others known in the art.
`0037 Mapper 203 may operate in several ways to select
`a Selected tree based on target tree. The Simplest way is
`merely to make the Selected tree the target tree. In which
`case the Scheduling tag from Scheduler 205 is placed in a tree
`pointed to by the selected tree. Sorted insert 207 places the
`tag in the tree according to Standard, binary tree-Sorting
`algorithm. Thus, mapper 203 Selects a Selected tree among
`a preset number of trees in the data structure 100 thus
`performing a mapping function. Sorted insert 207 adds a
`node to a selected tree, such as in FIG. 1B, thus inserting the
`tag. Combined, the Steps of mapping and inserting may
`accomplish adding a tag to a future portion of a circular data
`
`Cloudflare - Exhibit 1043, page 10
`
`

`

`US 2002/0097719 A1
`
`Jul. 25, 2002
`
`Structure. If the if-then branch of the loop is taken, release
`time is now, and the mapper 203, according to a first
`embodiment, Selects the same tree that is pointed to by the
`current tree pointer 163 of FIG. 1A. The sorted insert 207
`positions the tag in that tree according to Standard, binary
`tree-Sorting algorithm. A mapper may count the nodes it
`Sorts through as it identifies a position to locate the tag in the
`binary tree. If the node count or tree depth is greater than a
`maximum size 154, the tag may be discarded. The reason
`this approach might be taken is to keep the complexity of the
`trees to a reasonable level. This is done because, typically,
`a limited number of processing clock cycles are assigned to
`perform the task of sorted insert. This limits the number of
`comparisons that can be performed while inserting a tag in
`the tree.
`0038 FIG. 3A shows a tree of minimums or min-tree.
`Tags that are placed in trees become eligible for Selection at
`the removal Stage. The removal Stage relies on a set of
`eligible tags, which may be Stored in a tree of minimums, or
`a min-tree 301. A tree of minimums may consist of a null
`pointer. The tree of minimums may be grown by adding a tag
`based on the tag value of the tag. So that the min-tree is
`arranged as a binary tree.
`0039 FIG. 3B shows the relationship between the list of
`tree pointers and the min-tree. When a current tree pointer
`363 is advanced to a later tree 305, the leftmost node 311 of
`the tree, is the one with the Smallest tag among all the nodes
`in that tree. This is because each tree is built according to a
`binary tree-Sorting algorithm. This Smallest tag of the tree is
`also inserted in the min-tree according to standard binary
`tree-Sorting algorithm. The Step of inserting is also known as
`adding.
`0040 Similarly, in order to prepare the tree 390 that
`advanced beyond T-time units past the current tree, the root
`of the tree 390 may be set to be a null pointer. The tags in
`Such a tree may be discarded along with any packet asso
`ciated therewith. The tree associated with the list element
`390 is, in a Sense, re-allocated and thus is no longer included
`among the eligible trees. The tree pointed to by the list
`element now becomes a candidate to receive new tags. It is
`considered to be T-1 units ahead of the current time, on
`account of the circular nature of the list 101. The smallest tag
`that belonged to the post-current tree may be retained in the
`min-tree until that tag becomes the Smallest tag in the
`min-tree, while the corresponding packet may be main
`tained. A tag that was the Smallest tag in a tree at the time
`of tree destruction is called a vestigial tag. A min-tree that
`includes vestigial tags is an expanded min-tree. Any type of
`min-tree is composed entirely of tags that are associated
`with packets that are eligible for transmission, i.e. a min-tree
`is made up of the Set of eligible tags. The min-tree may have
`no more than one tag from a tree.
`0041 Transmitting of a packet is accomplished as fol
`lows:
`0042. When there is capacity open on the output port for
`another packet, the min-tree 301 is searched for the smallest
`tag 303 therein. Such a search does not require much
`processing, Since the Smallest tag is the leftmost tag. That tag
`is removed as the packet associated with the tag is trans
`mitted through the output port. The tag 303 may be dupli
`cated in a tree 309 of the eligible trees 310; and so the tag
`may be removed from that tree 309 as well. Note that this tag
`is readily available in tree 309 as the smallest tag in that tree.
`
`0043. Following this operation, a right child 305, if any,
`of the removed tag 303 may be elevated to the vacant spot.
`The min-tree 301 may be a tree of the smallest nodes of each
`tree among the set of trees 310 eligible for scheduling. The
`parent node or the right-child node, if any, may then become
`the Smallest node in the corresponding tree. AS Such, the
`parent node may be added to the min-tree 301 as represent
`ing the Smallest tag in the corresponding tree. A vestigial tag
`may not have a tree Structure other than the min-tree. Thus
`a vestigial tag, if it is the one that is removed, may not be
`replaced with a corresponding tree tag. The generic name for
`a tag that has been a part of a tree at, or within T, and Steps
`past the current-tree pointer 363 is post-current tag. This
`may include tags that have become vestigial tags, e.g.
`smallest tag 313. A tree is said to be post-current if the tree
`is at or within T-steps past the current-tree pointer. Note a
`post-current tag may not necessarily be a in a post-current
`tree.
`0044 Several alternative mapper algorithms may be
`implemented that place a Somewhat heavier weight on
`keeping trees short, or low-tree depth, at the Sacrifice of
`Short latency in dispatching a packet.
`004.5
`FIG. 4A shows a selection set of tree pointers used
`by a first-alternative mapper. The first-alternative mapper
`may Select the shortest of trees that are near the target tree
`465, e.g. by Selecting a future-neighbor tree 466, the target
`tree 465 and a past-neighbor tree 464, and then evaluating
`the tree depth of each tree. It is understood that the target tree
`is near itself, i.e. the quality of being near a tree includes
`being the tree itself, wherein the tree is zero steps from itself.
`The mapper then finally Selects a tree having the shortest
`depth as the insert tree, from among the Set of near trees. The
`insert tree may then be provided to the sorted insert 207.
`0046 FIG. 4B shows a selection set of tree pointers used
`by a Second-alternative mapper. The Second-alternative
`mapper may Select trees that are ahead of the target tree 475
`together with the target tree 475 to arrive at a set of near trees
`480. The mapper may apply a formula that weights the
`factors of tree depth combined with the number of steps
`distant a tree is from the target tree to arrive at a value,
`wherein the tree possessing the Smallest Value is Selected as
`the insert tree. AS an example of Steps, the tree 481 is three
`steps ahead of the target tree 475. The insert tree may then
`be provided to the sorted insert 207.
`0047 Since the complexity of later inserts may depend
`upon trees being optimized to be short, it can be helpful if
`Some processing time is devoted to reducing tree length or
`size. A complete optimization of a large tree can be costly,
`however, a modest Sub-tree optimization can curb tree
`growth, without, in Some cases, resorting to discarding a
`packet because of excessive tree growth.
`0048 FIG. 5 shows four three-node sub-trees that are not
`optimal. In every case, each node in the branch has a Single
`child node. There is an all-right, children tree 501; a right
`child, left-grandchild tree 503; a left-child, right-grandchild
`tree 505; and an all-left, children tree 507. These sub-trees
`can be converted from Sub-trees having a size of three to a
`two-deep Sub-tree 509. In other words, the size three sub
`tree is converted to an optimal Sub-tree. Such a conversion
`process is known in the art, and may be performed as an
`iterative Step with the addition of new nodes, or by a Separate
`process. Note that converting may be done anytime the
`
`Cloudflare - Exhibit 1043, page 11
`
`

`

`US 2002/0097719 A1
`
`Jul. 25, 2002
`
`nodes of a Sub-tree can be arranged to form a Sub-tree that
`observes the rules of binary trees, but yet has a Smaller
`length than the original Sub-tree. Thus a Sub-tree of fewer
`than 8 nodes may be optimized to a length of 3. Fewer than
`16 nodes can be optimized to a length of 4, i.e. Sub-trees
`having nodes less than 2^X may be converted to optimal
`lengths of less than or equal to X.
`0049. If the mapper, first-alternative mapper, and second
`alternative mapper are Susceptible to Still-producing trees of
`excessive length, a modification to each of the mapping
`algorithms may be done. FIG. 1B shows that a maximum
`size 154 of the tree depth may be enforced, wherein the tag
`and associated packet may be discarded when the insert tree
`has reached the maximum size. The condition of a tree
`reaching a maximum, and a tag being discarded as a
`consequence thereof, is known as tree overflow.
`0050 Although the invention has been described in the
`context of particular embodiments, various alternative
`embodiments are possible. For example, algorithms other
`than the leaky bucket may be used for the Shaping calcula
`tion, e.g. the calculation of release time. Thus, while the
`invention has been particularly shown and described with
`respect to specific embodiments thereof, it will be under
`stood by those skilled in the art that changes in form and
`configuration may be made therein without departing from
`the Scope and Spirit of the invention.
`
`What is claimed is:
`1. A method for transmitting a packet, Said packet having
`a release time and a tag having a tag value comprising the
`Steps of:
`adding the tag to a future portion of a data structure based
`on a release time, Said data Structure having a current
`tree near the future portion, Said future portion having
`Storage capacity for at least two tags,
`removing the tag from an eligible set of tags, including the
`tag, based on the tag value; and
`transmitting the packet on an output link.
`2. The method of claim 1 wherein the step of removing is
`preceded by a step of
`Selecting an eligible Set of tags.
`3. The method of claim 2 wherein the step of selecting
`further comprises the Step of Selecting at least one post
`current tag, including the tag.
`4. The method of claim 2 wherein the step of selecting
`further comprises the Step of Selecting a tag having a
`Smallest tag value in a post-current tree.
`5. The method of claim 1 wherein the step of removing the
`tag is preceded by the Step of
`advancing the current-tree, wherein the future portion is
`based on the current-tree.
`6. The method of claim 5 wherein the step of advancing
`further comprises the Steps of
`destroying a old tree at a location T Steps from the
`current-tree and wherein the data structure has at least
`2T trees.
`
`7. The method of claim 6 wherein the step of destroying
`further comprises the Step of
`reallocating at least one tag of the old tree that has a tag
`value at least as large as a Smallest tag value of the old
`tree.
`8. The method of claim 6 wherein the step of advancing
`further comprises the Steps of
`adding a tag having a Smallest tag value of a tree pointed
`to by current-tree to an eligible Set of tags.
`9. The method of claim 1 wherein the step of adding
`further comprises the Steps of
`adding the tag to a Sub-tree portion of a tree; and
`converting the Sub-tree to an optimized Sub-tree.
`10. The method of claim 1 wherein the step of removing
`is preceded by