(12) United States Patent
`Lu
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006480911Bl
`US 6,480,911 B1
`Nov. 12, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) GROUPING CLASS SENSITIVE QUEUES
`
`(75)
`
`Inventor: Xiaolin Lu, Middletown, NJ (US)
`
`(73) Assignee: AT&T Corp., New York, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/404,290
`
`(22) Filed:
`
`Sep. 23, 1999
`
`(51)
`
`Int. Cl? ......................... G06F 3/00; G06F 15/173;
`H04L 12/54
`(52) U.S. Cl. ......................... 710/54; 370/429; 370/329;
`709/240; 709/242; 710/52
`(58) Field of Search ................................. 370/329, 395,
`370/399, 429; 710/52, 54, 56; 709/240,
`227
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,923,656 A * 7/1999 Duan et a!. ................. 370/395
`5,974,467 A * 10/1999 Haddock et a!. ............ 709/240
`6,072,800 A * 6/2000 Lee ............................ 370/412
`6,075,791 A * 6/2000 Chiussi eta!. .............. 370/412
`6,101,193 A * 8/2000 Ohba
`......................... 370/429
`6,205,150 B1 * 3/2001 Ruszczyk ................... 370/412
`6,219,351 B1 * 4/2001 Kilkki ........................ 370/412
`6,229,795 B1 * 5/2001 Pankaj eta!. ............... 370/329
`6,259,698 B1 * 7/2001 Shin eta!. .................. 370/395
`6,262,986 B1 * 7/2001 Oba et a!. ................... 370/399
`6,262,989 B1 * 7/2001 Gemar eta!. ............... 370/412
`6,295,295 B1 * 9/2001 Wicklund ................... 370/392
`
`6,304,906 B1 * 10/2001 Bhatti et a!. ................ 709/227
`6,317,416 B1 * 11/2001 Giroux eta!. .............. 370/232
`6,330,223 B1 * 12/2001 Shimonishi ................. 370/230
`
`FOREIGN PATENT DOCUMENTS
`403101443 A * 4/1991
`410191455 A * 7/1998
`411032050 A * 2/1999
`
`JP
`JP
`JP
`
`* cited by examiner
`
`Primary Examiner-Thomas Lee
`Assistant Examiner---Chun Cao
`(74) Attorney, Agent, or Firm---Oliff & Berridge, PLC
`
`(57)
`
`ABSTRACT
`
`This invention provides a class queuing system where data
`is placed in queues distinguished by class. The class queuing
`system distinguishes one class from another based on
`desired characteristics of a host process such as a network
`process. The class queuing system groups the class queues
`into groups based on output ports, for example. Each of the
`groups is separated into logical or physical multiple levels
`that extend from an input to an output. Input data is queued
`in a lowest level queue and the data is moved from level to
`level until the data is placed in an output queue and
`transferred via a respective output port. Data movement
`between levels of the class queues is controlled by weight
`sets where the weights of the weight sets are determined
`based on the desired characteristics that distinguish the
`classes. In this way, classes having greater bandwidth, for
`example, are moved through the class queues at a faster rate
`than classes having lower bandwidth specifications.
`
`12 Claims, 11 Drawing Sheets
`
`3002
`
`SOFT
`
`NO
`
`NO
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 1 of 11
`
`US 6,480,911 B1
`
`108
`(
`END(cid:173)
`USER
`
`106
`
`END(cid:173)
`USER
`
`FIG. 1
`
`102
`
`NETWORK
`
`104
`
`END(cid:173)
`USER
`
`I
`
`100
`
`102
`
`202
`
`214,215
`
`208,
`209
`
`104
`
`END(cid:173)
`USER
`
`END(cid:173)
`USER
`
`108
`
`FIG. 2
`
`END(cid:173)
`USER
`
`106
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 2 of 11
`
`US 6,480,911 B1
`
`r-209
`
`r--211
`
`r--213
`
`r-----215
`
`NETWORK
`UNIT
`
`...--_. 202
`
`208 ,.--..
`
`210--
`
`212--
`
`214--
`
`FIG. 3
`
`

`
`211
`
`314
`' I
`r OUTPUT- -,...----J._____,
`QUEUE
`
`338
`
`316
`--- 213
`' I
`r - ' - - - - - - - - - - -
`OUTPUT
`QUEUE
`
`r- 348
`
`328
`
`1
`
`d •
`\Jl
`•
`
`215
`
`,...----J'-----,
`
`358
`
`318
`' I
`r _, ___ _
`OUTPUT
`QUEUE
`
`:
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I I
`I I
`
`' I
`~ OUTPUT- ,----'~
`1 QUEUE
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`•
`
`c_ _____ f _____ _
`320 322 324 326
`
`330 332 334 336
`
`340 342 344 346
`
`_____ T ______ c_ _____ T _____ _
`
`350 352 354 356
`
`(
`310
`
`t
`
`SWITCH
`
`t
`
`INPUT
`QUEUE
`
`INPUT
`QUEUE
`
`INPUT
`QUEUE
`
`INPUT
`QUEUE
`
`(
`302
`
`(
`304
`
`(
`306
`
`(
`308
`
`r--208
`
`---210
`
`~212
`
`~214
`
`\
`
`202
`
`FIG. 4
`
`

`
`FIG. 5
`
`209-----
`
`328~ DESTINATION
`OUTPUT QUEUE
`
`442l MEDIUM I
`
`d •
`\Jl .
`
`LEVEL3
`
`LEVEL2
`
`LEVEL1
`
`416
`
`418
`
`420
`
`422
`
`424
`
`426
`
`428
`
`430
`
`432
`
`434
`
`436
`
`438
`
`DESTINATION
`INPUT QUEUE
`
`DESTINATION
`INPUT QUEUE
`
`DESTINATION
`INPUT QUEUE
`
`DESTINATION
`INPUT QUEUE
`
`LEVELO
`
`I
`320
`
`I
`322
`
`I
`324
`
`I
`326
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 5 of 11
`
`US 6,480,911 B1
`
`a+1
`a+2
`a+3
`a+4
`a+5
`a+6
`a+?
`a+8
`a+9
`a+ 10
`a+ 11
`a+ 12
`a+ 13
`a+ 14
`a+ 15
`
`\
`I
`I
`I
`jl
`
`1\
`,--" 602
`l
`~
`~
`
`lJ
`R I
`
`I
`I
`I
`
`• • •
`
`LOW
`MEDIUM
`MEDIUM
`LOW
`LOW
`LOW
`HIGH
`LOW
`MEDIUM
`HIGH
`MEDIUM
`MEDIUM
`LOW
`HIGH
`LOW
`
`•
`•
`•
`
`a+m
`
`MEDIUM
`
`I
`
`600
`
`FIG. 6
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 6 of 11
`
`US 6,480,911 B1
`
`622
`
`624
`
`IDENTIFICATION I LENGTH I •••
`CLASS I
`•••
`
`•
`•
`•
`
`CRC
`
`I
`
`•••
`
`I
`
`LINK
`
`DATA
`
`FIG. 7
`
`I
`
`620
`
`

`
`FIG. 8
`
`209~
`
`328--
`
`DESTINATION
`OUTPUT QUEUE
`
`452 -=CisECOND WEIGHT SET
`
`4448
`4428
`~i:]
`450 -li FIRST WEIGHT SET li- 450
`
`d •
`\Jl
`•
`
`LEVEL3
`
`LEVEL2
`
`LEVEL1
`
`416
`
`418
`
`420
`
`422
`
`424
`
`426
`
`428
`
`430
`
`432
`
`434
`
`436
`
`438
`
`DESTINATION
`INPUT QUEUE
`I
`320
`
`DESTINATION
`INPUT QUEUE
`
`DESTINATION
`INPUT QUEUE
`
`DESTINATION
`INPUT QUEUE
`
`LEVELO
`
`I
`322
`
`I
`324
`
`I
`326
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 8 of 11
`
`US 6,480,911 B1
`
`504--- MEMORY
`
`502---- CONTROLLER
`
`(
`512
`
`NETWORK
`INTERFACE
`(
`506
`
`•••
`
`NETWORK
`INTERFACE
`(
`508
`
`DATABASE
`INTERFACE
`(
`510
`
`FIG. 9
`
`

`
`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 9 of 11
`
`US 6,480,911 B1
`
`START
`
`COLLECT SUBSCRIBER VOLUME DATA
`
`1000
`
`NO
`
`NO
`
`1002
`
`GENERATE NEW WEIGHTS
`AND THRESHOLDS
`
`1004
`
`APPLY NEW WEIGHTS
`AND THRESHOLDS
`
`1006
`
`1008
`
`YES
`
`END
`
`1010
`
`FIG. 10
`
`

`
`START
`
`NO
`
`2000
`
`PLACE IN DESTINATION
`INPUT QUEUE
`
`2004
`
`YES
`
`LINK NEXT PACKET IN
`DESTINATION INPUT QUEUE
`
`2008
`
`YES
`
`END
`
`2012
`
`NO
`
`FIG. 11
`
`d •
`\Jl
`•
`~
`~ ......
`=
`~
`......
`
`z
`0
`~
`'"""'
`~N
`N c c
`
`N
`
`'JJ. =-~
`~ .....
`c
`'"""'
`0 ......,
`'"""'
`'"""'
`
`e
`
`rJ'l
`0'1
`'l.
`00
`Q
`\o
`1--"
`1--"
`~
`1--"
`
`

`
`d •
`\Jl
`•
`
`NO
`
`3002
`
`YES
`
`END
`
`3008
`
`MOVE HEAD PACKET
`IN SELECTED QUEUE
`TO NEXT LEVEL
`
`3010
`
`HARD
`
`SOFT
`
`NO
`
`YES
`
`FIG. 12
`
`REQUEST WEIGHT
`AND THRESHOLD
`UPDATE
`
`3016
`
`

`
`US 6,480,911 Bl
`
`1
`GROUPING CLASS SENSITIVE QUEUES
`
`BACKGROUND OF THE INVENTION
`1. Field of Invention
`This invention relates to methods and apparatus for class
`sensitive queuing.
`2. Description of Related Art
`Data transmitted in a network is often placed in a serial
`queue for routing and forwarding. The order that the data is
`queued is irrespective of the subscribers' subscription rela(cid:173)
`tionship with the network service provider. Thus, there are
`no provisions in the network routing and forwarding pro(cid:173)
`cesses for making distinctions based on subscribers' sub-
`scription requirements. In fact, queuing techniques in gen(cid:173)
`eral do not address subscription related issues. Accordingly,
`new technology is needed.
`
`5
`
`10
`
`15
`
`2
`The class queuing system may use a weight based sched(cid:173)
`uling scheme to control transfer of data packets among
`queues. The weight sets may specify the data throughput for
`a queue during each cycle of the weight based scheduling so
`that appropriate transfer rates corresponding to the desired
`characteristics of each class may be achieved.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention is described in detail with reference to the
`following figures, wherein like numerals reference like
`elements, and wherein:
`FIG. 1 is an exemplary diagram of a communication
`network;
`FIG. 2 is an exemplary diagram of the network in FIG. 1
`with further detail;
`FIG. 3 is an exemplary block diagram of a network unit;
`FIG. 4 is an exemplary queuing structure;
`FIG. 5 is an exemplary queue organization;
`FIG. 6 is an example of a destination input queue;
`FIG. 7 is an exemplary diagram for a data packet;
`FIG. 8 is an exemplary diagram showing control of data
`movement by first and second weight sets;
`FIG. 9 is an exemplary block diagram of a queue proces(cid:173)
`sor of the network unit that performs queue processing;
`FIG. 10 is an exemplary flowchart for a subscriber volume
`collection process of the queue processor;
`FIG. 11 shows an exemplary flowchart for a destination
`input queue process of the queue processor; and
`FIG. 12 is an exemplary flowchart for class queue process
`of the queue processor.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`This invention provides a class queuing system that
`processes data transmitted by a subscriber based on a class
`subscribed to by the subscriber. For example, in a network
`environment having high, medium, and low classes, each of
`the classes may be guaranteed a minimum bound relative to
`one or more network characteristics. The network charac(cid:173)
`teristics may be qualities such as transmission capacity
`expressed in terms of bandwidth (bw), quality of service
`such as video display quality, multimedia capability, or
`end-to-end transmission delay, for example. Based on a
`specific selection of class specification parameters, the
`resulting bandwidth/line quality/error rate, etc. may be
`determined and applied as appropriate.
`If network capacity serves as a class discriminator, a high
`capacity class may be guaranteed a bandwidth minimum
`bound of bw H so that data of high class subscribers may be
`transmitted through the network using a bandwidth of at
`least bw H· Correspondingly, data of medium class subscrib(cid:173)
`ers may be guaranteed transmission at a bandwidth of at
`least a bw M' and data of low class subscribers may be
`guaranteed data transmission at a bandwidth of at least bwL.
`Maximum bounds of bandwidth may also be applied so that
`each class may be bounded by both maximum and minimum
`bounds. For ease of description, only minimum bounds are
`discussed.
`The class queuing system may provide class
`independence, i.e., the volume of data in one class may be
`prevented from affecting the data transmission in other
`classes. For example, congestion in the low class may affect
`only low class throughput and quality. Medium and high
`class data transmissions may reach peak performances while
`
`30
`
`20
`
`25
`
`SUMMARY OF THE INVENTION
`This invention provides a class queuing system where
`data is placed in queues distinguished by class. The class
`queuing system distinguishes one class from another based
`on desired characteristics of a host process such as a network
`process. For example, in a network environment, the desired
`characteristics may be expressed in network parameters such
`as transmission capacity (bandwidth), transmission
`throughput, end-to-end delay, quality of transmission or
`error rate, for example. Classes may be distinguished from
`each other by specifying minimum bounds of the above
`parameters so that data transmission for each of the classes
`may be guaranteed performance above the specified mini(cid:173)
`mum bounds.
`The class queuing system establishes groups of class
`queues which may be implemented using a single or mul- 35
`tiple memories. Physical grouping of the class queues is not
`required because the complete class queuing system may be
`implemented via memory mapping, for example. However,
`for ease of visualization and discussion, related figures
`illustrate the group concept to show the functions of the 40
`invention.
`Each of the groups corresponds to one output port that is
`coupled to a network link. A group is separated into multiple
`levels (logical or physical) that extend from input ports to
`output ports. Again, physical levels are not required but 45
`illustrated in the related figures for clarity only. Input data is
`first queued in a lowest level queue, and then the data is
`moved from level to level until the data is placed in an output
`queue for transmission or output via one of the output ports.
`Data movement between levels of the class queues is 50
`controlled by a respective weight set where weights of the
`weight set are determined based on the desired characteris(cid:173)
`tics that distinguish the classes. In this way, data of classes
`requiring greater bandwidth, for example, is moved through
`the class queues at a faster rate than data of classes having 55
`lower bandwidth requirements.
`Each of the class queues may also be associated with
`buffer thresholds. The buffer thresholds specify a maximum
`size of a queue or a warning condition so that when an
`amount of data that is queued exceeds the buffer thresholds, 60
`either portions of the data may be dropped from the queue
`based on a data drop scheme or other queue management
`processes may be applied to adjust the queuing system. For
`example, the newest piece of data to be placed in the queue
`may be dropped or the weight set may be changed to account 65
`for the volume of data in the queue (e.g., by increasing queue
`throughput).
`
`

`
`US 6,480,911 Bl
`
`10
`
`15
`
`20
`
`3
`low class data transmission may experience transmission
`degradation. However, if desired, the class queuing system
`may take advantage of lower traffic conditions in one of the
`class queues to assist data transmission of another more
`congested class.
`The class queuing system may organize input queues into
`groups and a queue for each group may be separated into
`multiple levels (logical or physical). Data movement
`between queues at different levels of a group may be
`controlled based on weight sets.
`For example, for high, medium and low classes, the input
`queue for any network unit, such as a router, may be grouped
`according to output ports (e.g., a physical network connec(cid:173)
`tion to another network unit) and organized into logical or
`physical multiple levels. The queues may progress from a
`lowest level queue that receives data from data input sources
`and ending in one output queue per output port.
`A weight set may be assigned to queues at each level. The
`weight set regulates data movement from queues at one level
`to queues at a next level. In this way, data from different
`class subscribers may be controlled to partition a bandwidth
`of the output port to support the minimum bounds of the
`subscriber classes.
`In the following discussion, the classifications of high,
`medium, and low capacities are used as an example and two 25
`weight sets of capacity and subscriber volumes are described
`for supporting the three classes. Other types and numbers of
`weight sets based on different network parameters or char(cid:173)
`acteristics may also be used such as end-to-end delay, video
`quality, or error rate, for example.
`FIG. 1 shows an exemplary diagram of a communications
`system 100 that includes a network 102 and end-users
`104--108. The network 102 may be a telecommunication
`network, a data network or any of a variety of intra or
`internets that facilitates communication among end-users. 35
`The end-users 104-108 may be a terminal, a telephone
`station (wire or wireless) or other communication systems
`such as PBXs, for example.
`When end-users 104-108 desire to communicate, each of
`the end-users 104-108 sends communication signals 40
`through the network 102 in the form of data packets, for
`example. Data packets are not required but are convenient
`for discussion purposes. Each of the data packets are
`received by the network 102 and placed into queues await(cid:173)
`ing available network resources to complete the communi- 45
`cation.
`FIG. 2 shows an exemplary diagram of the network 102
`which includes network units 202-206. The network unit
`202 is coupled to the end-user 104 via communication links
`208 and 209; the end-user 108 via communication links 210
`and 211; network unit 204 via communication link 214 and
`215; and network unit 206 via communication links 212 and
`213. The communication links 208, 210, 212 and 214 are
`input into the network unit 202, and the communication
`links 209, 211, 213 and 215 are output from the network unit
`202. From the perspective of the network unit 202, data
`packets are received from the communication links 208,
`210, 212 and 214 and each of the received data packets is
`destined to one of the end-users 104 and 108 and the
`network units 204 and 206.
`As an example, the network unit 202 is illustrated in FIG.
`3, where the links 208, 210, 213 and 214 are input into the
`network unit 202, and the links 209, 211, 213 and 215 are
`output from the network unit 202. Data packets that are sent
`via the communication links 209, 211, 213 and 215 are
`destined for the end-users 104 and 108 and the network units
`204 and 206, respectively.
`
`4
`The network unit 202 places data packets received from
`the links 208, 210, 212 and 214 into input queues so that a
`switch, for example, within the network unit 202 may route
`each of the data packets to the proper destinations corre-
`5 sponding to the links 209, 211, 213 and 215. Each of the
`links 209, 211, 213 and 215 are provided with output queues
`that receive the data packets from the input queues for
`outputting to the respective end-users 104 and 108 and the
`network units 204 and 206.
`FIG. 4 shows an exemplary block diagram of the queues
`within the network unit 202. The input queues 302-308
`receives data packets from the links 208, 210, 212 and 214.
`A switch 310 receives data packets from the input queues
`302-308 and routes each of the data packets to one of output
`queues 312-318 corresponding to an appropriate destination
`of the data packet. While FIG. 4 shows the switch 310, there
`are many other known methods for routing the data packets
`from the input queues 302-308 to the output queues
`312-318. For example, a bus may couple the input queues
`and the output queues together and a controller may simply
`read the data packets from the input queues 302-308 and
`write them into the output queues 312-318.
`The class queuing system organizes each of the output
`queues 312-318 with destination input queues 320-356 and
`destination output queues 328-358. Each of the destination
`input queues 320-356 corresponds to one of the input
`queues 302-308. For example, the data packets that origi(cid:173)
`nated from the input queue 302 may be placed in one of the
`destination input queues 320, 330, 340 and 350; the data
`30 packets of the input queue 304 may be placed in one of the
`destination input queues 322, 332, 342 and 352; the data
`packets of the input queue 306 may be placed in one of the
`destination input queues 324, 334, 344 and 354; and the data
`packets of the input queue 308 may be placed in one of the
`destination input queues 326, 336, 346 and 356. The class
`queuing system moves the data packets in the destination
`input queues 320 -326 to the destination output queues 328
`based on network parameters such as the capacity for each
`class and the subscriber volume within each class.
`FIG. 5 shows a more detailed exemplary diagram of the
`output queue 312 that supports high, medium and low
`classes. FIG. 5 illustrates functions that may be implemented
`in many ways such as memory mapping, application specific
`integrated circuits (ASICs), computer programs, etc. The
`destination input queues 320-326 form level zero queues;
`initial class queues 416-438 form level one queues; final
`class queues 440--444 form level two queues; and the
`destination output queue 328 forms a level three queue. The
`data packets within each of the destination input queues
`50 320-326 may be organized into separate level one queues
`corresponding to each of the high, medium and low classes.
`The class queuing system moves data packets from the level
`one initial class queues 416-438 to the level two final class
`queues 440-444 based on a first weight set, and the data
`55 packets in the final class level two queues 440--444 into the
`destination output queue 328 based on a second weight set.
`The first and second weight sets may be determined using
`the capacity minimum bounds corresponding to each of the
`classes and the subscriber volumes of each of the classes, as
`60 described in detail below.
`Capacity may be one of the parameters that determines
`either the first or the second weight set. For example,
`capacity may be defined in terms of a kilobits per second
`(KBPS) unit. Assuming that high capacity subscribers have
`65 a minimum bound bandwidth of 128 KBPS, medium capac(cid:173)
`ity subscribers have a minimum bound bandwidth of 64
`KBPS, and low capacity subscribers have a minimum bound
`
`

`
`US 6,480,911 Bl
`
`5
`bandwidth of 8 KBPS, then capacity weights for high,
`medium, and low capacity classes may be in a ratio of
`128:64:8 or 16:8:1 when common factors are removed.
`Thus, the capacity weight for the high class is 16, for the
`medium class is 8 and for the low class is 1.
`The subscriber volume of each of the classes may be
`another parameter for determining the value of the first
`and/or second weight sets. If the subscriber volume nHr is
`the total high class data volume and the subscriber volume
`nH; is the high class data volume that are currently being
`received at the ith destination input queue where i=1, 2, 3
`and 4 for destination input queues 320, 322, 324 and 326,
`respectively, then a subscriber volume based weight for the
`high class may be nH;/nHr· Similarly, the medium and low
`class subscriber volume based weights may be nM;/nMr and
`nL;/nLr, respectively. Data packets may be transferred
`between the level one initial class queues 416-438 to the
`level two final class queues 440-444 and between the level
`two final class queues 440-444 to the level three destination
`output queue 328 based on the above definition of capacity
`and subscriber volume based weight sets.
`The subscriber volume may also be based on the number
`of subscribers of each class that are currently communicat(cid:173)
`ing. In this case, the subscriber volume nHr is the total
`number of high class subscribers that are currently commu(cid:173)
`nicating via the network unit 102 and the subscriber volume 25
`nH; is the total number of high class subscribers for the ith
`destination input queue. The subscriber volume may also be
`based on both the data volume and the number of subscribers
`for each class. For example, the subscriber volume may be
`the data volume divided by the number of subscribers for 30
`each class at a network unit 102 or for each of the destination
`input queues.
`The class queuing system may move data packets from
`the level 0 destination input queues 320-326 to the level 1
`initial class queues 416-438 by simply linking data packets 35
`within each of the destination input queues 320-326
`together in a chronological order (time of arrival) for each of
`the classes. FIG. 6 shows an example of a level 0 destination
`input queue 600 that has received data packets from all three
`high, medium and low classes, for example. The data 40
`packets at address a+1 was received before the data packet
`at address a+2. The data packets within the level 0 destina(cid:173)
`tion input queue 600 may be converted into level 1 initial
`class queues by linking data packets of respective classes
`together.
`For example, all the data packets of the low class may be
`linked together by placing a parameter in a header portion of
`each of the low class data packets indicating where the next
`(in time) low class data packet may be found. Such linking
`is indicated in FIG. 6 by the set of arrows 602 which links 50
`the low class data packet at a+1 with the low class data
`packet at a+4 which in turn links to the low class data packet
`at a+S and so on. If the medium and high class data packets
`are similarly linked, the destination input queue 600 would
`be separated into three initial class queues for high, medium 55
`and low classes.
`FIG. 7 shows an example of a data packet 620 that
`includes a header portion 622 and a data portion 624. The
`header portion 622 may include information relating to
`control and identification of the data packet 620 such as an 60
`identification field, a length field, a class field, a cyclical
`redundancy code (CRC) field and a link field. The class field
`may indicate the class of the data packet 620 and the link
`field may indicate the address of the next data packet of the
`same class. Thus, the data packets are linked together in the 65
`order of arrival at each of the destination input queues
`320--326.
`
`6
`Other methods may be used to move data packets from the
`level 0 destination input queues 320-326 to the level1 initial
`class queues 416-438. For example, all the data packets of
`the same class may be transferred to a dedicated area in a
`5 memory specifically allocated for data packets of that class.
`Thus, the above example is provided for illustration pur(cid:173)
`poses only and not intended to be limiting in any way.
`FIG. 8 shows that data packets from the initial class
`queues 416-438 may be moved into the final class queues
`10 440-444 based on the first weight set as indicated by arrow
`450 and data packets from the final class queues 440--444
`may be moved into the destination output queue 328 based
`on the second weight set as shown by arrow 452. Thus, the
`rate at which the data packets of each class move from the
`15 destination input queues 320-326 to the destination output
`queue 328 is based on a product of a weight of the first
`weight set times a weight of the second weight set.
`The first and second weight sets may control a data packet
`transfer process based on a specific data packet transfer
`20 technique such as a weight based scheduling technique. In
`this technique, each weight set may specify how often data
`packets from a queue is transferred to a next level queue.
`For a weight based scheduling scheme, head data packets
`from each of the initial class queues are transferred in
`sequence based on the weight set. A head data packet is a
`data packet that is waiting to be transferred ahead of all other
`data packets in a queue. After the head data packet is
`transferred, the next data packet (in time) in the queue
`becomes the head data packet and so on. In this way, the data
`packets in a queue is sequentially moved out of the queue.
`A weight based scheduling scheme may operate in cycles
`where for each cycle a number of data packets is selected for
`transfer based on the weights of the weight set. For example,
`assume that the first weight set is 4, 3, 2, 1 corresponding to
`high class initial class queues 420, 426, 432 and 438
`associated with destination input queues 320-326, respec(cid:173)
`tively. Then four data packets from the initial class queue
`420 is transferred to the high class final class queue 444 for
`three data packets from the initial class queue 426, two data
`packets from the initial class queue 432 and one data packet
`from the initial class queue 438.
`If the second weight set is: high class=S; medium class=2;
`and low class=1, then five data packets from the high class
`45 final class queue 444 is transferred to the destination output
`queue 328 for two data packets of the medium class final
`class queue 442 and for one data packet of the low class final
`queue 440. The data packet transfers corresponding to the
`second weight set are illustrated in Table 1 below where
`columns are labeled with the final class queues 440-444 and
`the rows are labeled in the first column by cycles and the
`second column by class.
`
`TABLE 1
`
`High
`444
`
`1-5
`
`9-13
`
`17-21
`
`25-29
`
`Medium
`442
`
`Low
`440
`
`6-7
`
`14-15
`
`22-23
`
`30-31
`
`8
`
`16
`
`24
`
`High
`Medium
`Low
`High
`Medium
`Low
`High
`Medium
`Low
`High
`Medium
`
`2
`
`3
`
`4
`
`

`
`US 6,480,911 Bl
`
`7
`
`TABLE 1-continued
`
`High
`444
`
`Medium
`442
`
`Low
`440
`
`32
`
`Low
`
`5
`
`8
`communication. For example, if the data packets represent
`digitized voice, it may be advantageous to drop data packets
`that are evenly spread across time. In such a case, when
`transferring a data packet that caused the total number of
`5 data packets of a queue to exceed the hard buffer threshold,
`a voice data packet of the same communication already
`stored in the final class queue may be dropped. However,
`such schemes may be too complex because it may be
`difficult to determine the relationship among data packets
`10 relative to a specific communication among parties, for
`example. Thus, if data packets arrive at a particular network
`unit 202-206 in a random manner, dropping either the latest
`transfer data packet or the head data packet may be the
`simplest procedure.
`Data packet dropping may be an indication that network
`resources need to be increased. The number of data packets
`dropped, the time at which data packet dropping occurs and
`the location where data packet dropping occurs may be
`flagged as data dropping occurs and later collected. By
`20 analyzing the above types of collected data, network
`improvements and expansion may be made to achieve high
`quality of service in a controlled manner with high efficiency
`and low cost.
`A soft buffer threshold is a buffer threshold that is less
`25 than a hard buffer threshold. When soft buffer thresholds are
`exceeded, the class queuing system is alerted to take some
`recovery action such as changing the weights to realign data
`throughput to adapt to current subscriber volume conditions
`of the different classes.
`As discussed above, a set of capacity weights may be
`related to a minimum bound bandwidth assigned to each
`class. For the example, the weight set may be 16:8:1
`corresponding to the high, medium and low classes. Weights
`that are determined based on subscriber volume (data
`35 volume/number of subscribers/combination of data volume
`and number of subscribers) are called subscriber weights
`and may be set based on current subscriber volume of a
`particular destination input queue 320-326 n; divided by a
`total current subscriber volume of a particular class nr. For
`40 example, the subscriber weight for high class subscribers
`may be expressed as nH;/nHr· Thus, the subscriber weights
`dynamically tracks the current usage or congestion of the
`network. Depending on how the first and second weight sets
`and the buffer thresholds are determined, all of these param-
`45 eters may be adapted to a specific congestion condition.
`Three examples for setting the first and second weight sets
`and the buffer thresholds are listed in Table 2 and described
`below.
`
`For the first cycle, five data packets numbered 1-5 are
`transferred from the high class final class queue 444; two
`data packets 6 and 7 are transferred from the medium class
`final class queue 442; and one data packet 8 is transferred
`from the low class final class queue 440. Table 1 shows that 15
`the queues of each class is selected in a circular fashion, as
`an example. Other selection schemes are also possible such
`as transferring all the data packets from one of the queues for
`each cycle, selecting the queue having the largest number of
`data packets, or more complex techniques of transferring
`data packets oldest in time first.
`In a second cycle, five data packets 9-13 are transferred
`from the high class final class queue 444; two data packets
`14 and 15 are transferred from the medium class final class
`queue 442; and one data packet 16 is transferred from the
`low class final class queue 440. In cycle 3 another five data
`packets 17-21 are transferred from the high class final class
`queue 444; two data packets 22 and 23 are transferred from
`medium class final class queue 442; and one data packet 24
`is transferred from the low class final class queue 440. 30
`Finally, in cycle 4, five data packets 25-26 are transferred
`from the high class final class queue 444; two data packets
`30 and 31 are transferred from the medium class final class
`queue 442; and one data packet 32 is transferred from the
`low class final class queue 440.
`As can be seen from Table 1, a number of data packets
`determined by the weight is transferred from a particular
`class queue in a circular manner for each cycle. In this way,
`the weights control the rate at which data packets are moved
`through each of the queues 444-440. Data is transferred
`through the high, medium and low class queues 420, 426,
`432, 438; 418, 424, 430, 436; and 416, 422, 428, 434
`independently of other class queues. Thus, congestion
`occurring in one of the class queues does not affect the
`throughput in other class queues.
`A similar process, as described above, may be applied