(12) United States Patent
`Tzeng
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,438,135 B1
`Aug. 20, 2002
`
`US006438135B1
`
`6,157,654 A * 12/2000 Davis ....................... .. 370/412
`6,198,723 B1 *
`3/2001 Parruck et al.
`........ .. 370/230
`6,260,073 B1 *
`7/2001 VValker et al.
`370/412
`
`
`
`370/232
`.............. .. 370/230
`
`(54) DYNANIIC WEIGHTED ROUND ROBIN
`QUEUING
`
`(75)
`
`Inventor: Shrjie Tzeng’ Fremont, CA (US)
`
`6,317,416 B1 * 11/2001 Giroux et al.
`6,385,168 B1 *
`5/2002 Davis ct al.
`
`(73) Assignee: Advanced Micro Devices, Inc.,
`Sunnyvale, CA (US)
`
`*
`
`.t d b
`C1 e
`
`.
`y exammer
`
`(' * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`USC. 154(1)) by 0 days.
`
`Pri’WrY E""”’i’?er_KWang Bin Yao
`.
`Asslsmm Exammer—Prene1.l JOHCS
`(74) Attorney, Agent, or Ftrm—Renner, Otto, Boisselle &
`Sklar, LLP
`
`(21) Appl. No.2 09/422,591
`
`(57)
`
`ABSTRACT
`
`0915- 21: 1999
`(22) Filed:
`(51)
`Int. Cl? .............................................. .. H04L 12/28
`(59) U S C]
`370/412
`(58) Field of Search ............................... .. 370/412, 455,
`370/230-232, 392-104, 422-430, 911,
`389, 13, 360; 710/40-44, 72, 310, 455/525;
`709/249, 224
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,487,061 A *
`578709629 A *
`5,917,822 A
`5,926,459 A
`
`1/1996 Bray ......................... .. 370/'13
`2/1999 Borden et 81.
`370/412
`6/1999 Lyles et al.
`7/1999 Lyles et al.
`
`Amethod for transmitting a plurality of data packets through
`3 "e‘W°“<- Each data Pack“ is aSSig"ed *0 “"6 Of 3 P‘u”1“‘Y
`of priority queues and each priority queue has a service
`We1gh[' A pnomy Welght 15 asslgned [0 each of the data
`packets and each priority weight has a value. Data packets
`are delivered from one of the priority queues until a service
`satisfied condition is met. The service satisfied condition is
`met When a combination of the values of the priority Weights
`for each of the delivered datapackets is equal to or is greater
`than the service Weight assigned to the priority queue. A
`queuing switch for implementing this method is also dis-
`cussed. The queuing switch includes an incoming data
`k
`d
`1
`1.
`f
`.
`.
`pac et processor an
`a p ura ity 0 priority queues.
`
`15 Claims, 4 Drawing Sheets
`
`
`
`
`
`I
`
`Low Priority Queue
`(Service Weight
`2 —> 8)
`
`
`
`Normal/Low
`Ir - hlormal/Hig_h
`High Priority
`:
`Start
`: Queue (Service
`:
`I
`Priority Queue
`Priority Queue
`
`,
`Weight 16)
`_/Ir_12
`I (Service Weight 8) '
`(Service Weight 8)
`
`56 32 I
`4
`Packet 1
`:
`Packet 1
`I
`3
`
`Packet 2 /F
`{
`Packet 2
`2
`Packet 2
`
`1
`Packet 3 ‘
`I
`4
`Packet 3
`4
`Packet 4
`E
`7 packet 4
`2
`4
`Packet 5
`:
`4
`Packet 5
`4
`Packet 6
`i
`? Packet 6
`'
`I
`I 4
`‘3 n:
`3
`Packet 7
`L
`1
`Packet 7
`:
`CC
`I
`<: E
`4
`Packet 8
`4
`packet 3
`I
`I j T 8 D
`:
`4
`Packet 9
`i
`4
`Packet 10
`I
`I —I
`.
`I
`0
`I
`°
`
`
`
`
`I
`
`
`
`I
`
`I
`
`I
`
`’
`
`|
`
`'
`1
`:
`1
`
`L
`
`3
`4
`
`Packet 9
`Packet 10
`O
`0
`0
`
`I
`
`,
`
`T _ _ _ _ _ _ _ _ _ _
`
`55
`
`°
`Packet V
`
`1
`I
`— - ‘ ‘ ‘ “ ‘ ' ‘ — — —'
`
`1
`I
`
`Packet H
`
`'
`I
`
`Packet 2
`
`ERICSSON EXHIBIT 1005
`
`

`
`U.S. Patent
`
`Aug. 20, 2002
`
`Sheet 1 of4
`
`US 6,438,135 B1
`
`8
`
`
`
`oo_>mn_vcooww
`
`
`
`mm..mv_omn_E0930
`
`Bmmoooi
`
`N_\
`
`\IIIIIIIIIIIL
`
`_..0_n_
`
`
`
`>Eo_.n_5030..
`
`osmzd
`
`
`
`>Eo__n_mgm_nmE.mE_
`
`Awvwzmso
`
`
`
`>505.$._m_:
`
`mzmsd
`
`I-
`
`I I I
`
`/II
`
`
`
`umv_omn_mc_Eoo:_
`
`_ommmoo.n_
`
`E.
`
`
`
`mo_>wn_..m._u_
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 20, 2002
`
`Sheet 2 of4
`
`US 6,438,135 B1
`
`N_.
`
`(\l
`
`_.mm
`,\om
`
`_.mv_omn_98
`
`
`
`Em_w>>EmEcm_mm<
`
`om
`
`N_\mmonN_\mm
`
`om
`
`:!'E\lN N
`Q§_om.n_$8
`mu®v_omn_Ema
`
`o§_omn_9.3I\_m>%.wUzMosxoma£8ESSmcmQmmcmaA!
`
`N.0_u_
`
`momN.‘mmom
`
`Nwmomw_‘
`
`_<Egan.EmaF:91__<BxomaEma
`
`88
`
`mmom
`
`
`
`

`
`U.S. Patent
`
`Aug. 20, 2002
`
`Sheet 3 of4
`
`US 6,438,135 B1
`
`mm
`
`9.
`
`
`
`E9258_amwEm
`
`
`
`E950mo_Ewm.
`
`
`
`wsmzd>Eo_._n_
`
`3
`
`EV
`
`Qmxomm
`
`/\ w_\
`
`wo_Zmw
`
`mw>
`
`:_
`
`$03030
`
`ozEm_m>>
`
`so:
`
`oz
`
`we
`
`am;
`
`ow
`
`caz9__2_;m
`
`
`
`@3030>Eo__n_
`
`¢.O_n_
`
`mm
`
`3
`
`omm>:®Q
`
`
`
`#9_omn_Ema03$-40
`
`M.0_n_
`
`
`
`_8_E§w5260
`
`co:m_.Eo.E_
`
`..mxomn_EGO_m>__wQ
`
`m>>>>o2mc_Eo8<
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 20, 2002
`
`Sheet 4 of4
`
`US 6,438,135 B1
`
`__________________.________
`
`26303:0212,3
`
`7IIIIIIIIIIT
`
`___.____
`
`
`
`
`
`>Eo:n__8Em_m>>.8EmwV_mzmzo
`
`26._\_m::oz“
`
`._g_.=_m§oz
`
`
`
`msmso>Eo:n_
`
`
`
`3Em_m>>8_aomV
`
`E
`
`\,_____
`
`3A-NEm_m>>853
`
`v...mvW.uImn_I
`
`mEgan.
`
`N§_omn_
`
`w.\wv_omn_
`
`mE03
`
`COCS§_omn_
`
`_.........m.0_..._
`
`NEgan.
`
`V#mv_omn_
`
`m§_omn_
`
`HEI/V\G
`
`8|'lUI1UOQ
`
`mEOE
`
`mHmxoma
`
`
`
`0....wv_omn_
`
`VEOE
`
`N..wv_omn_
`
`m§_omn_
`
`TIIIIIIIIIII
`
`
`
` §Em_o>>"mo_>L_mwv96:0_tflm
`>Eo:n_:9:H
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`US 6,438,135 B1
`
`1
`DYNAMIC WEIGHTED ROUND ROBIN
`QUEUING
`TECHNICAL FIELD
`
`The present invention generally relates to network com-
`munications a11d, more particularly,
`to a method for the
`prioritized delivery of data packets from a queuing switch.
`BACKGROUND ART
`
`There is an ever present demand for the efficient delivery
`of data packets over computer networks and communication
`ietworks to establish a variety of quality of service (QOS)
`objectives. One QOS objective is to deliver high priority
`data packets either before or more efliciently than normal
`and low priority data packets. To achieve this goal, packet
`raffic shaping techniques and prioritization schemes have
`Jeen developed.
`Transport layer switches, or layer 4 switches, are typically
`used to implement most prioritization schemes. One com-
`non prioritization scheme is round robin (RR) queuing. In
`ound robin queuing, a set of queues, or buffers, are estab-
`lished for temporarily holding data packets while the data
`jackets await delivery. As an example, [our queues may be
`established, including a high priority queue, a normal/high
`ariority queue, a normal/low priority queue and a low
`Jriority queue. Each data packet is assigned to one of the
`queues based on a predetermined algorithm. The switch
`delivers messages from the queues based on a round robin
`approach. The round robin approach entails delivering a
`aredetermined number of data packets from one of the
`queues, then delivering the same number of data packets
`from each of the other queues in descending order of priority
`3efore returning to the initial queue and repeating the
`arocess. Since the same number of packets are sent from
`each queue, the service ratio between queues is 1:1. This
`neans that the high priority queue may not be serviced
`enough to deliver all the high priority packets while meeting
`QOS expectations.
`Another common prioritization scheme is weighted round
`obin (WRR) queuing. Weighted round robin queuing uses
`he same basic structure as round robin queuing, but services
`he higher priority queues more frequently than the lower
`ariority queues. A common implementation of WRR is to
`send a greater number of data packets from the higher
`riority queues than are sent from the lower priority queues
`for each round through the priority queues. It is common to
`iave a service ratio between the high priority queue and the
`low priority queue of the foregoing round robin example to
`3e set to 4:1, meaning that four packets are sent from the
`iigh priority queue for each packet sent from the low
`ariority queue. However,
`in most actual data network
`environments, high priority data packets may constitute only
`about 20% of all data packets. The remaining 80% of the
`data packets have lower priorities. The result is that high
`ariority data packets in this example are serviced with a
`ariority which is effectively 16 times the priority of low
`ariority packets. As a result, the lower priority queues are not
`serviced enough and the lower priority data packets may
`experience significant delay before being delivered. This
`means that QOS expectations for the lower priority data
`Jackets are not met.
`
`Round robin and weighted round robin queuing schemes
`are usually implemented using hardware having a fixed
`rocedure for delivering packets. Therefore, round robin and
`weighted round robin techniques are not able to adapt to any
`one particular network to optimize the packet delivery
`efficiency of the network.
`
`2
`SUMMARY OF THE INVENTION
`
`The present invention provides a method for transmitting
`a plurality of data packets through a network. Each data
`packet is assigned to one of a plurality of priority queues and
`each priority queue has a service weight. A priority weight
`is assigned to each of the data packets and each priority
`weight has a value. Data packets are delivered from one of
`the priority queues until a service satisfied condition is met.
`The service satisfied condition is met when a combination of
`
`the values of the priority weights for each of the delivered
`data packets is equal to or is greater than the service weight
`assigned to the priority queue.
`In accordance with another aspect of the invention, a
`queuing switch is provided. The queuing switch includes an
`incoming data packet processor which derives a queue
`assignment and a priority weight for each of a plurality of
`incoming data packets. Each priority weight has a value. The
`queuing switch also includes a plurality of priority queues
`and each priority queue has a service weight. The incoming
`data packet processor directs each data packet to one of the
`priority queues based on the queue assignment for each data
`packet. Data packets are delivered from a first one of the
`priority queues until a service satisfied condition is met. The
`service satisfied condition is met when a combination of the
`
`values of the priority weights for each of the delivered data
`packets is equal to or is greater than the service weight
`assigned to the first priority queue.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1 is a block diagram of a queuing switch according
`to the present invention.
`FIG. 2 is a schematic representation of a data packet and
`associated equation identifier according to the present inven-
`tion.
`
`FIG. 3 is a data packet flow chart according to the present
`invention.
`
`FIG. 4 is a dynamic weighted round robin flow chart
`according to the present invention.
`FIG. 5 is a schematic representation of an example queue
`structure controlled by a dynamic weighted round robin
`queuing method according to the present invention.
`DISCLOSURE OF INVENTION
`
`Referring to FIG. 1, a block diagram of a queuing switch
`10 having a switch fabric for implementing a dynamic
`weighted round robin (DWRR) queuing method is illus-
`trated. The method and queuing switch 10 are directed to
`prioritizing data packets 12 for delivery and may be adapted
`for use in data, computer, telecommunication or multimedia
`networks, or in any other type of network where packets of
`data requiring prioritization are transmitted from a
`transmitting, or a first device 14, to a receiving, or a second
`device 16. As used herein,
`the term data packet 12 is
`intended to mean any packet, frame, message, or the like,
`that is transmitted through the network. The prioritization
`scheme discussed herein is adaptable to networks such as
`asynchronous transfer mode (ATM) networks and Ethernets.
`The queuing switch 10 is preferably part of a programmable
`hardware switch used to carry out data packet 12 transmis-
`sion. For example, the switch 10 could be used to implement
`the network layer of an open systems interconnect (OSI)
`protocol stack, or layer 3 switch such as a router, or a switch
`used to implement the OSI transport layer, or layer 4 switch.
`However, one skilled in the art will appreciate that the
`queuing switch 10 and method according to the invention
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`
`US 6,438,135 B1
`
`3
`can be implemented with other hardware devices or with
`software alone.
`
`The queuing switch 10 is provided with an incoming
`packet processor 18, a series of priority queues 20 and an
`outgoing packet processor 22. Generally,
`the incoming
`packet processor 18 receives data packets 12 that are sent
`from the first device 14 to the second device 16. The priority
`queues 20 range in priority from highest to lowest and are
`implemented with conventional software or hardware data
`packet buifers for temporarily storing data packets as they
`await delivery. The outgoing packet processor 22 sends data
`packets 12 from the priority queues 20 to the second device
`16. As one skilled in the art will appreciate, the queuing
`switch 10 may be a part of the first device 14 or located in
`a separate message transmitting device. Other higher or
`lower order data packet switching devices, such as routers or
`bridges, may used as needed. The queuing switch 10 is
`preferably also provided with a counter 24 for collecting
`statistical information regarding data packet 12 throughput
`and priority queue 20 usage, for one or more of the priority
`queues 20.
`With additional reference to FIG. 2, the incoming packet
`jrocessor 18 creates an equation identifier (EID) 26 for each
`incoming data packet 12. The EID does not become a part
`of the data packet, but is logically associated with the data
`Jacket. Alternatively, the EID can be appended to the data
`aacket as a header which is later stripped before transmis-
`sion by the outgoing packet processor 22. The EID for each
`data packet is derived from a combination of factors related
`0 the data packet (step 28 in FIG. 3). Example factors
`include the hardware device generating the data packet, the
`identity of the person using the hardware device generating
`he data packet, choices made by the person using the
`iardware device generating the data packet, the general type
`of information contained in the data packet, the specific
`content of the data packet, the destination device of the data
`aacket, and/or the destination person of the data packet. In
`an example embodiment, the EID is a six bit binary word
`which represents the end step solution, or equation result, to
`an EID derivation algorithm. The EID derivation algorithm
`accounts for the selected combination of factors. In this
`
`example, the six bit EID has sixty four possible values. In
`addition to one of these values, additional prioritization data
`can be associated with each data packet. For example, the
`network can use IEEE Std. 802.1Q for prioritization of
`Ethernet traflic where a three bit field allows each user to set
`
`up to eight user priorities for time-critical information.
`The EID 26 serves two functions. The functions are
`
`assigning each data packet to a priority queue 20, or queue
`assignment 30, and assigning a priority weight 32 to each
`packet. Accordingly, the EID is preferably a binary word of
`a predetermined number of bits. The EID is preferably two
`to eight bits long, but could be longer if needed. The upper
`bits of the EID, or a first segment of the EID, represents the
`priority queue assignment 30 and the lower bits of the EID,
`or a second segment of the EID, represents the priority
`weight 32. The priority weight is preferably an integer
`number. FIG. 2 illustrates a generic EID associated with a
`data packet and, as an example, FIG. 2 also illustrates a set
`of four data packets 12 each having a four bit EID, where the
`first two bits represent
`the queue assignment 30 for the
`associated data packet 12 and the last two bits represent the
`priority weight 32 for the associated data packet 12.
`With additional reference to FIG. 3, once the incoming
`packet processor has associated each incoming data packet
`with an EID, the data packet is sent to the priority queue
`matching the priority queue assignment (step 34). It is noted
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`the EID for each data packet may alternatively be
`that
`generated before the data packet reaches the queuing switch
`10. In that event, the incoming packet processor 18 will not
`be responsible for generating the EID, but will only be
`responsible for reading the priority queue assignment and
`sending the data packet to the priority queue 20 matching the
`priority queue assignment. Once each data packet reaches its
`proper priority queue 20, it is buffered along with other data
`packets assigned to the same priority queue 20.
`With additional reference to FIG. 4, each priority queue
`20 is assigned a service weight (step 36). The service weight
`is preferably an integer number greater than zero. The value
`of the service weight for each priority queue 20 is prede-
`termined by either a default setting or by a network admin-
`istrator. As will be more fiilly described below, the service
`weight can be changed by the network administrator with
`the assistance of the statistical information collected by the
`counter 24. The service weight for each priority queue 20
`indirectly represents how many data packets should be sent
`from each priority queue 20 before the switch fabric of the
`queuing switch 20 begins sending data packets from the next
`priority queue 20. The service weight is preferably not a one
`for one count of how many data packets are sent from each
`priority queue 20 when the switch fabric services the cur-
`rently serviced priority queue 20. Rather, the service weight
`is satisfied when the sum of the priority weights 32 for each
`data packet 12 sent from the priority queue 20 being serviced
`is equal to or is greater than (i.e., meets or exceeds) the
`assigned integer number value of the service weight. As
`described herein, the priority weights 32 and the service
`weights 30 are numerical integers. However, one skilled in
`the art will appreciate that the values for the priority weights
`and the service weights can be any type of symbolic repre-
`sentation. As will be discussed in more detail below, the
`switch fabric will change which priority queue is being
`serviced when either the service weight is satisfied for the
`currently serviced queue or when there are no packets in the
`currently serviced queue.
`Generally, the switch fabric will service (i.e., deliver data
`packets 12, step 38) the priority queues 20 one after another
`(steps 40 and 42) and then return to the first serviced queue
`to repeat the process in dynamic weighted round robin
`queuing fashion to cyclically deliver data packets from each
`of the priority queues 20. Preferably, the highest priority
`queue is serviced first, followed by the other priority queues
`20 in descending order of priority. After the lowest priority
`queue is serviced, the queuing switch will again service the
`highest priority queue.
`The queuing switch 10 will change the priority queue 20
`being serviced when either of two service satisfied condi-
`tions is met. The first service satisfied condition is met when
`the service weight of the priority queue 20 being serviced is
`satisfied (step 44). This means that
`the number of data
`packets 12 sent from each priority queue 20 during one
`round of the dynamic weight round robin queuing method is
`dependent on the priority weight of the data packets l2 and
`the service weight of the priority queue 20. Therefore, on
`average, more data packets can be sent from a particular
`priority queue before the service weight is satisfied and the
`next queue is serviced if the average value of the priority
`weights sent through that priority queue is low. If the first
`service satisfied condition is met the switch will service the
`next priority queue to be serviced, step 42. If the service
`weight is not satisfied in step 44, the switch 10 will check
`whether the second service satisfied condition is met (step
`45). The second service satisfied condition is met when there
`are no data packets 12 awaiting delivery in the priority queue
`
`

`
`US 6,438,135 B1
`
`5
`20 being serviced. If there are no data packets waiting to be
`delivery in the queue being serviced, the switch 10 will
`service the next priority queue to be serviced, step 42. If
`there are data packets waiting to be delivered in the queue
`being serviced, the switch will deliver the next data packet
`(step 40).
`Each priority queue 20 preferably transmits data packets
`12 based on a first-in-first-out (FIFO) basis. IIowever, other
`queuing methods can be employed depending on network
`requirements. Example alternative queuing methods include
`last-in-first-out (LIFO) and highest-priority-first-out. If a
`highest-priority-first-out method is used, the data packets
`with the lowest priority weight value will be transmitted
`before data packets with a higher priority weight value.
`The outgoing data packet processor 22 manages the
`delivery of data packets 12 from each of the priority queues
`20 to the second device 16 or any intermediate transmission
`devices. The outgoing data packet processor 22 is tasked
`with keeping track of the sum of the priority weights for the
`data packets 12 delivered by the priority queue 20 being
`serviced and switching between priority queues 20, if either
`of the foregoing service satisfied conditions are met.
`Alternatively, the outgoing data packet processor 22 can be
`eliminated and either a queuing switch 10 controller or each
`individual priority queue 20 can be responsible for the tasks
`of the outgoing data packet processor 22.
`As indicated above, conventional RR and WRR switches
`deliver data packets based on a fixed algorithm which is
`programmed into the hardware and cannot be changed by a
`person or through software modifications. The present
`invention provides a switch 10 having changeable param-
`eters. More specifically, the service weights for each priority
`queue 20 and the EID for each data packet 12 is changeable
`to enhance performance of the queuing switch 10. These
`variables can be set depending on the nature of the network
`and can be adjusted in response to future changes in the
`network traffic pattern. The counter 24 collects statistical
`information to assist the network administrator in deciding
`what changes to make (step 46 in FIG. 3). These decisions
`include whether to raise, lower or keep the service weight
`for each priority queue 20 the same, whether to change
`which priority queue 20 certain data packets 12 are sent to,
`and whether to change the priority weight for certain data
`packets 12. Accordingly, the counter 24 tracks information
`such as how many data packets 12 of each priority weight
`are sent through each of the priority queues 20 and how long
`the data packets 12 Wait in the priority queues 20 before
`being delivered. This information, as recorded by the
`counter 24, can be polled by a host computer programmed
`with network management software and a GUI interface.
`The host computer presents the collected information in an
`organized format to the user, with or without programmed
`suggestions directed to enhancing performance of the queu-
`ing switch 10 or suggestions directed to establishing full
`utilization of all of the queuing switch 10 priority queues 20.
`The network administrator then can provide commands or
`information to the switch 10 to change or reconfigure the
`service weights of the priority queues 20 or the priority
`weights 32 of the data packets 12.
`
`EXAMPLE
`
`In order to further describe the dynamic weighted round
`robin method of the present
`invention,
`the following
`example is provided. Referring now to FIG. 5, an example
`queuing switch 10 is provided with four priority queues 20,
`including a high priority queue 48, a normal/high priority
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`queue 50, a normal/low priority queue 52 and a low priority
`queue 54. The high priority queue 48 is assigned a service
`weight of 16 and can store up to 11 number of packets, the
`normal/high priority queue 50 is assigned a service weight
`of 8 and can store up to x number of packets, the normal/low
`priority queue 52 is assigned a service weight of 8 and can
`store up to y number of packets and the low priority queue
`54 is assigned a service weight of two and can store up to z
`number of packets. In this example, each data packet 12 can
`have a priority weight of 1, 2, 3 or 4. For illustrative
`purposes, FIG. 5 shows each priority queue populated with
`a series of data packets 12. The high priority queue 48
`contains packets 1 through 10,
`the normal/high priority
`queue 50 contains packets 1 through 3,
`the normal/low
`priority queue 52 contains packets 1 through 5, and a low
`priority queue 54 contains packets 1 through 10. The priority
`weight portion of the EID for each of these data packets is
`shown next to the data packet in FIG. 5. For simplicity, the
`queue assignment portion of the EID for each data packet is
`omitted in FIG. 5.
`
`The switch fabric will start sending data packets from the
`high priority queue 48 (arrow 56). Data packets 1, 2, 3 and
`so forth will be sent until the sum of the values of the priority
`weight for each data packet sent is equal to or is greater than
`the service weight, thereby satisfying the first service satis-
`fied condition. In the example, the first five packets will be
`sent since the sum of the values of the priority weights for
`the first five data packets totals 16. Then the switching queue
`10 will start sending packets from the normal/high priority
`queue 50 (arrow 58). In the example, only three data packets
`are in the normal/high priority queue 50 and the sum of the
`packets’ priority weights does not exceed the service weight.
`However, after the three packets are sent the normal/high
`priority queue 50 will have no data packet entries and the
`second service satisfied condition will be met for the normal/
`high priority queue 50. Therefore, the three data packets will
`be sent and the queuing switch 10 will start sending packets
`from the normal/low priority queue 52 (arrow 60) until
`either the first service satisfied or the second service satisfied
`
`condition is met for the normal/low priority queue 52. In the
`example, the first two data packets in the normal/low priority
`queue 52 have priority weight values totaling seven, which
`does not meet or exceed the queues service weight. The
`third data packet has a priority weight value of four. The sum
`of the priority weight values of the first three data packets
`exceeds the queue’s service weight, thereby satisfying one
`of the service satisfied conditions for the normal/low priority
`queue 52.
`The switching fabric will then start to send data packets
`from the low priority queue 54 under the same operating
`procedure (arrow 62). Since the priority weight of the first
`data packet in the low priority queue 54 exceeds the service
`weight of that queue, the first service satisfied conditions is
`met for the low priority queue 54 and the switch fabric will
`return to servicing the high priority queue 48 (arrow 64). The
`foregoing dynamic weighted round robin procedure is the
`repeated (arrow 66). However, as illustrated, the low priority
`queue 54 will develop a backlog of data packets to send
`under such a low service weight. As the dynamic weighted
`round robin process continues, the counter 24 will collect
`information regarding the number of data packets 12 pro-
`cessed and how long the data packets 12 stayed in the
`priority queues 20 while awaiting delivery. The user admin-
`istrating the network can use this information to change the
`EID for selected types of data packets and adjust the service
`weight of the priority queues 20,
`thereby enhancing the
`performance and queue utilization of the queuing switch 10.
`
`

`
`US 6,438,135 B1
`
`7
`The switch 10 can also be programmed to alert the admin-
`istrator if data packets are not being delivered within a
`specified time. In addition, if the administrator is aware of a
`condition which may change network usage, such as the
`addition of a new network user or other network pattern
`change, then appropriate changes to the EIDs and service
`weights can also be made. With this in mind, if the backlog
`of data packets in the low priority queue 54 persists, the
`administrator can take counteractive actions. For example,
`the administrator can raise the service weight of the low
`priority queue 54 to a higher value, such as 8. The admin-
`istrator can also lower the priority weight of selected types
`of data packets being delivered through the low priority
`queue 54 and change the queue through which selected types
`of data packets are sent by modifying the queue assignment.
`Although particular embodiments of the invention have
`been described in detail, it is understood that the invention
`is not limited correspondingly in scope, but includes all
`changes, modifications and equivalents coming within the
`spirit and terms of the claims appended hereto.
`What is claimed is:
`
`1. A method of transmitting a plurality of data packets
`through a network, comprising the steps of:
`assigning each data packet to one of a plurality of priority
`queues, each priority queue having a numerical service
`weight;
`assigning a priority weight to each of the data packets,
`each priority weight having a numerical value; and
`servicing each of the priority queues in round robin order
`by delivering data packets from one of the priority
`queues and transitioning to deliver data packets from a
`subsequent priority queue in the round robin order
`when a service satisfied condition is met for the priority
`queue being serviced, the service satisfied condition
`being met when a combination of the numerical values
`of the priority weights for each of the data packets
`delivered from the priority queue being serviced is
`equal to or is greater than the numerical service weight
`assigned to the priority queue being serviced.
`2. The method of transmitting data pac<ets according to
`claim 1, further comprising the step of collecting statistical
`information regarding data packet througiput and priority
`queue usage.
`3. The method of transmitting data pac<ets according to
`claim 1, wherein the service satisfied cone ition is met if no
`data packets are currently assigned to the one of the priority
`queues.
`4. The method of transmitting data pac<ets according to
`claim 1, further comprising the step of chaiging the priority
`queue assignment of an incoming data packet.
`5. The method of transmitting data pacgets according to
`claim 1, further comprising the step of chaiging the priority
`weight of an incoming data packet.
`
`8
`6. The method of transmitting data packets according to
`claim 1, further comprising the step of changing the service
`weight of one of the priority queues.
`7. The method of transmitting data packets according to
`claim 1, wherein data packets are delivered from each queue
`on a first-in-first-out basis.
`
`8. A queuing switch, comprising:
`the incoming data
`an incoming data packet processor,
`packet processor deriving a queue assignment for each
`of a plurality of incoming data packets and assigning a
`numerical priority weight to each data packet;
`a plurality of priority queues, each priority queue having
`a numerical service weight, wherein the incoming data
`packet processor directs each data packet to one of the
`priority queues based on the queue assignment for each
`data packet; and
`the outgoing data
`an outgoing data packet processor,
`packet processor servicing each priority queue in round
`robin order by delivering data packets from each of the
`priority queues towards a receiving device, the outgo-
`ing data packet processor transitioning from one pri-
`ority queue to a subsequent priority queue in the round
`robin order when a service satisfied condition is met for
`
`the priority queue being serviced, the service satisfied
`condition being met when a combination of the numeri-
`cal values of the priority weights for each of the data
`packets delivered from the priority queue being ser-
`viced is equal to or is greater than the numerical service
`weight assigned to the priority queue being serviced.
`9. The queuing switch according to claim 8, wherein the
`outgoing data packet processor combines the priority
`weights of each of the sent data pac <ets.
`10. The queuing switch according to claim 8, further
`comprising a counter, the counter col ecting statistical infor-
`mation regarding data packet throughput and priority queue
`usage.
`11. The queuing switch according o claim 8, wherein the
`service satisfied condition is met i no data packets are
`currently assigned to the priority queue being serviced.
`12. The queuing switch according o claim 8, wherein the
`priority queue assignment of an incoming data packet is
`changeable.
`o claim 8, wherein the
`13. The queuing switch according
`priority weight of an incoming data packet is changeable.
`14. The queuing switch according o claim 8, wherein the
`service weight of each of the priority queues is changeable.
`15. The queuing switch according to claim 8, wherein data
`packets are delivered from each queue on a first-in-first-out
`basis.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`SO