US007385994B2
`
`(12) Ulllted States Patent
`Speight
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,385,994 B2
`Jun. 10, 2008
`
`(54) PACKET DATA QUEUING AND PROCESSING
`
`2002/0172156 A1* 11/2002 Sandbote .................. .. 370/230
`
`(75)
`
`Inventor: Timothy James Speight, Bristol (GB)
`
`(73) Assignee:
`
`IPWireless, Inc., San Bruno, CA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U'S.C. 154(1)) by 1143 days.
`
`DE
`EP
`GB
`
`GB
`GB
`W0
`
`FOREIGN PATENT DOCUMENTS
`19907085
`4/2000
`1124356
`8/2001
`2338372
`12/1999
`
`3/2000
`2341751
`10/2001
`2351147
`10/2001
`W0-0174027
`OTHER PUBLICATIONS
`
`Chaskar et al. (2003). “Fair Scheduling with Tunable Latency: A
`Round-Robin Approach,” IEEE/ACM Transactions on Networking,
`11(4)592-601, 6 pages.
`
`International Search Report mailed Apr. 29, 2003 for PCT Applica-
`tion No. PCT/GB02/04823 filed Oct. 24, 2002, 3 pages.
`.
`(Continued)
`
`Primary Exammerichi Pham
`ASSl.Sll1"lExaml71€7’*PhuC Tran
`(74) Attorney, Agent, or Firm—Morrison & Foerster LLP
`
`ABSTRACT
`(57)
`k da
`.
`k
`d da
`.
`h d f
`A
`ta
`ta pac as In a pac et
`met 0 0 pmcessmg queue
`communication system is provided. The method includes
`allocating a tier of service for substantially each of a plurality
`ofindividual packet data queues and determining a total num-
`ber of data packets that can use an available communication
`resource. A proportion of a total number of data packets is
`allocated to a number ofthe tiers of service to allow individual
`
`packet data queues on a number of tiers to share a cornmum-
`C3110“ resource A °°mm“m°?‘“°n “°1S°“r°‘°11S Pr°V1ded 10
`queued packet data users on a tier-by.-tier basis, such that the
`communication resource is made available to substantially all
`Hers
`
`25 Claims, 3 Drawing Sheets
`
`(21) App1.No.: 10/278,342
`
`(22)
`
`Filed;
`
`()et_ 23, 2002
`
`(65)
`
`Prior Publication Data
`US 2003/0103497 A1
`Jun. 5, 2003
`
`Foreign Application Priority Data
`(30)
`Oct. 24, 2001
`(GB)
`............................... .. 0125502.5
`
`(51)
`
`Int. Cl.
`H04L 12/28
`(2006.01)
`(52) U.S. Cl. ................................. .. 370/412; 370/395.53
`(58) Field of Classification Search ............... .. 370/253,
`370/389, 412—429
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U~S~ PATENT DOCUMENTS
`
`“/2001 Giroux et a1.
`6,317,416 B1
`............ .. 370/395.2
`9/2003 veies et al.
`6,614,790 B1 *
`6/2005 Kohzuki et al. N
`370/412
`6,912,225 B1 =z<
`6,977,930 B1 »x< 12/2005 Epps et a1.
`............. N 370/392
`7,206,282 B1*
`4/2007 Goldman et al.
`370/230
`2001/0033581 A1* 10/2001 Kawarai et al.
`. . . . .
`. . . .. 370/468
`
`
`
`2002/0163922 A1* 11/2002 Dooley et al.
`
`............. .. 370/412
`
`234
`
`
`
`MEMORY I
`
`OMC
`LOGIC
`238
`
`_______ _,_
`252
`24
`254
`
`ERICSSON EXHIBIT 1001
`
`

`
`US 7,385,994 B2
`Page 2
`
`OTHER PUBLICATIONS
`
`Keshav, S. “Stop-and-Go Service Using Hierarchical Round Robin.”
`Downloaded on Jul. 31, 2007, from <http://cm.bell-labs.com/cm/cs/
`doc/91/2-15.ps.gz>, 10 pages.
`“Understanding Weighted Fair Queuing on ATM.” Downloaded on
`Jul.
`31,
`2007,
`from <http://www.cisco.com/warp/public/121/
`wfq_illustrated.pdf>, 10 pages.
`Zhang et al. (1993). “Rate Controlled Static-Priority Queueing,” In
`Proceedings of IEEE IFOCOM ’93. Downloaded on Jul. 31, 2007,
`from <http://www.cs.cmu.edu/-hzhang/papers/INFOCOM93.pdf>,
`11 pages.
`Bennett et al. (Oct. 1997). “Hierarchical packet fair queueing algo-
`rithms,” IEE/ACM Transactions on Networking (TON), 5(5):675-
`689.
`
`Semeria, C. (2001). “Supporting Differentiated Service Classes:
`Queue Scheduling Disciplines,” Juniper Network, Inc. Downloaded
`on Jul. 31, 2007, from <http://www.juniper.net/solutions/1iterature/
`white_papers/200020.pdf ><, pp. 1-25.
`Search Report dated May 10, 2002, for GB Application No. GB
`0125502.5, one page.
`Held, G. (1997). Understanding Data Communications.‘ From Fun-
`damentals to Networking. John Wiley & Sons Ltd: West Sussex,
`England, 16 pages (Table of Contents).
`Zhang, H. (Oct. 1995). “Service Disciplines for Guaranteed Perfor-
`mance Service in Packet-Switching Networks,” Proceedings of the
`IEEE 83(10):1374-1396.
`
`* cited by examiner
`
`

`
`U.S. Patent
`
`Jun. 10,2008
`
`Sheet 1 of3
`
`US 7,385,994 B2
`
`FIG. 1
`
`PRIOR ART
`
`

`
`U.S. Patent
`
`Jun. 10,2008
`
`Sheet 2 of3
`
`US 7,385,994 B2
`
`MEMORY
`
`236 LOGIC
`
`260
`
`262
`
`

`
`U.S. Patent
`
`Jun. 10,2008
`
`Sheet 3 of3
`
`US 7,385,994 B2
`
`FIG.3
`
`300
`
`\
`
`

`
`US 7,385,994 B2
`
`1
`PACKET DATA QUEUING AND PROCESSING
`
`FIELD OF THE INVENTION
`
`This invention relates to gateway queuing algorithms in
`packet networks. The invention is applicable to, but not lim-
`ited to, gateway queuing algorithms in packet data transmis-
`sions, for example for use in the universal mobile telecom-
`munication standard.
`
`BACKGROUND OF THE INVENTION
`
`An established cellular radio communication system is
`GSM (Global System for Mobile Communications). A fur-
`ther wireless communication system currently being defined
`is the universal mobile telecommunication system (UMTS),
`which is intended to provide a harmonised standard under
`which cellular radio communication networks and systems
`will provide enhanced levels of interfacing and compatibility
`with other types of communication systems and networks.
`A fixed network interconnects wireless communication
`
`serving elements, such as Node Bs. This fixed network com-
`prises communication lines, switches,
`interfaces to other
`communication networks and various controllers required for
`operating the network. Hence, a call from a UE is generally
`routed through the fixed network to the destination unit spe-
`cific to this call. If the call is between two UEs of the same
`
`communication system the call will be routed through the
`fixed network to the Node B of the cell in which the other
`
`mobile station currently is. A connection is thus established
`between the two serving cells through the fixed network.
`Wireless communication systems are distinguished over
`fixed communication systems, such as the public switched
`telephone network (PSTN), principally in that UEs move
`between coverage areas served by different Node B (and/or
`different service providers). In general, wireless subscriber
`units are typically provided with the ability to communicate
`to fixed networks such as the PSTN. If a UE wishes to call a
`
`telephone connected to the Public Switched Telephone Net-
`work (PSTN) the call is routed from the serving Node B to the
`interface between the cellular mobile communication system
`and the PSTN. It is then routed from the interface to the
`
`telephone by the PSTN.
`Traditional trafiic in wireless mobile cellular communica-
`
`tion systems, such as GSM, has been circuit-switched voice
`data. In circuit-switched data systems, a permanent link is set
`up between the communicating parties, for the entire duration
`of the communication. Even during idle times, no other
`potential users may use the resources of the allocated com-
`munication path.
`In addition to speech and data services, it is envisaged that,
`in future wireless communication systems, there will be an
`increasing need to support high-speed multimedia communi-
`cations. A significant requirement of future wireless commu-
`nication systems is
`their ability to provide users with
`improved opportunities to interact with information networks
`such as the Internet. It is also envisaged that the typical
`requirements for a subscriber communication terminal will
`be to transmit data at irregular intervals, in contrast to the
`continuous manner provided by current circuit-switched
`wireless communication systems. Clearly, with irregular
`transmissions it is ineflicient to l1ave a continuous link set up
`between users.
`
`Consequently, it is envisaged that wireless communication
`systems will increasingly use packet-switched data technol-
`ogy, to interface to public data networks or information net-
`works such as the Internet. In packet-switched data networks,
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`information or messages are divided into standard length data
`packets for transmission. Each data packet is transmitted
`independently through the infrastructure from a source node
`to a destination node. This may mean that the data packets
`arrive out oforder due to the fact that separate communication
`paths are established for individual data packets for the dura-
`tion of the particular data packet transmission.
`A cellular communication network generally interfaces
`with a packet-switched network, such as the Internet, via an
`Internet router serving as a gateway to the cellular communi-
`cations network. Thus, when information is to be communi-
`cated to or from a MS or UE in a cellular communications
`
`network or system, the route is established to the appropriate
`Internet router, serving as the gateway ofthe cellular commu-
`nication network. An example of a packet-based wireless
`communication system is the General Packet Radio Service
`(GPRS) developed to supplement the GSM communication
`system for high-speed data communication. Further details
`on packet data systems can be found in “Understanding data
`communications: from fundamentals to networking”, 2"“ ed.,
`John Wiley publishers, author Gilbert Held, 1997, ISBN
`0-471-96820-X.
`
`In a packet data based system, where a high number of
`subscriber units may require resources for packet transmis-
`sions at unknown and irregular intervals, it is important to
`optimise use the limited communication resource. Hence, a
`means of scheduling and ordering of the time of transmission
`of the individual packets is needed. This becomes even more
`important when individual data packets have different
`requirements with respect to delay, bit error rate etc.
`Therefore, most packet based systems contain schedulers
`which control when the individual data packets are transmit-
`ted in order to share the available resource, whether time-slots
`in a TDMA system or power and codes in a CDMA system.
`An introduction to schedulers can be fotmd in “Service dis-
`
`cipline for guaranteed performance service in packet-switch-
`ing networks”, Hui Zhang, Proceedings of the IEEE, volume
`83, no. 10, October 1995.
`However, known schedulers have been optimised for envi-
`ronments other than CDMA communication systems. For
`example, scheduling algorithms used for GPRS are optimised
`for a Time Division Multiple Access (TDMA) system and
`therefore not optimal for CDMA-based systems such as
`UMTS where codes and power must be shared.
`FIG. 1 illustrates a known arrangement 100 for providing a
`number of clients (C1 .
`.
`. CN) 110 with access to packet data
`based services. The individual clients 112, 114, 116 have data
`packets to be transferred through a network and are compet-
`ing for a time-shared resource (S) 130 such as a communica-
`tion channel or CPU time. A gateway 120 is positioned
`between the clients and the shared resource, to co-ordinate the
`transferral of the data packets onto the resource. Hence, a
`number of data packets are “queued” until the gateway trans-
`fers the data packet to the time-shared resource (S) 130. The
`gateway 120 includes a gateway queue algorithm (GW) that
`determines how the resource is to be shared between queued
`data packets from the respective clients.
`Two well know queue service algorithms, to allocate the
`communication resource between queued data packets, are:
`(i) Weighted fair queuing; and
`(ii) Hierarchical round robin.
`
`WEIGHTED FAIR QUEUING
`
`Weighted fair queuing is a packet queuing/ordering
`scheme based on a bit-by-bit round-robin allocation. The
`gateway 120 maintains separate queues for packets from each
`
`

`
`US 7,385,994 B2
`
`3
`user 112, 114, 116. The gateway 120 processes the queues in
`a bit-by-bit round-robin manner by knowing the throughput
`of the time-shared resource/server 130. Under these condi-
`
`tions it is clear that if there are N users then the throughput
`provided to each user will be l/N.
`It is possible to extend the scheme by defining parameters
`<1) 1 .
`.
`. <1)N (weights) that set the number ofbits allocated to each
`user per round. This extension allows differential service
`rates to be provided to different users.
`Weighted fair queuing (also known as generalised proces-
`sor sharing) further extends the bit-by-bit round-robin tech-
`nique so that it can be used in packet-based systems with
`packets of differing size. If we assume that F1, is the hypo-
`thetical time a data packet would depart the queuing gateway
`when bit-by-bit round-robin servicing is employed,
`the
`weighted fair queuing algorithm would process data packets
`in increasing order of FP.
`A weighted fair queuing system is therefore characterised
`in the following manner. Let S1. (to, t) be the amount of trafiic
`served from user i in the interval (to, t), such that:
`
`Si([0a 1) >
`Sjllosl) _ ¢j
`
`. .N
`Wherej:l,2, .
`Therefore, it can be seen that the features of fair weighted
`queuing are:
`(i) It provides a fair allocation of bandwidth;
`(ii) It is resistant to ill-behaved packet data sources; and
`(iii) It offers the potential to provide a lower delay for
`sources not using their full share of the available com-
`munication bandwidth.
`
`HIERARCHICAL ROUND-ROBIN
`
`A hierarchical round-robin scheme employs multiple lev-
`els or tiers. Within each tier a round-robin service is provided
`to users using a fixed number of slots. A user is allocated a
`fixed number of slots in each tier. The time taken to service all
`the slots within a level (or tier) is termed the frame time.
`Clearly the shorter the frame time the greater the proportion
`of the bandwidth allocated to this level. Thus, differential
`service can be provided to users on a level or tier basis.
`However, the hierarchical round robin system does not
`provide fair allocation of bandwidth to users because
`resources carmot be transferred between tiers. Furthermore,
`where differential service is to be provided on a tier-wise
`basis, the provision ofmany queues is undesirable. The inven-
`tor of the present invention has recognised that the increased
`number of queues is a function of the lower tiers being ser-
`viced only once all of the higher tier queues have been pro-
`cessed. This is particularly the case when the number of
`allocated resource units per round is small compared to the
`total number of clients requiring service.
`Furthermore, when data packets are all of the same length,
`a round-robin allocation of packets maintains the fair alloca-
`tion ofresources that fair weighted queuing offers. Therefore,
`the maintenance ofa notional bit-by-bit round-robin allocator
`is redundant and thereby inefiicient in the speedy processing
`of queued packets.
`Also in a system where different users experience very
`different throughputs (e. g. when they experience different
`radio conditions) a weighted fair queuing system faces prob-
`lems in fair allocation to users since the bit-by-bit round robin
`simplification does not hold.
`
`4
`
`The approach of combining hierarchical round robin and
`weighted fair queuing has not be considered in the past due to
`the difficulty of determining the number of packets which
`should be allocated to each tier when there are a variable
`number of users in each tier.
`
`Thus, there exists a need in the field ofthe present invention
`to provide an improved packet data queuing method, algo-
`rithm and associated elements wherein the abovementioned
`disadvantages may be substantially alleviated.
`
`STATEMENT OF INVENTION
`
`In accordance with a first aspect of the present invention,
`there is provided a method of processing queued data packets
`in a packet data communication system, the method, com-
`prising the step of:
`allocating a tier of service for substantially each of a plu-
`rality of individual packet data queues;
`wherein the method is characterised by the steps of:
`determining a total number of data packets that can use
`an available communication resource;
`allocating a proportion of said total number ofdata pack-
`ets to a number of the tiers of service to allow indi-
`
`vidual packet data queues on a number oftiers to share
`a communication resource; and
`providing said communication resource to queued
`packet data users on a tier-by-tier basis, such that said
`communication resource is made available to a sub-
`stantial number of tiers.
`
`In accordance with a second aspect of the present inven-
`tion, there is provided a packet data scheduler queuing data
`packets in a packet data communication system, the packet
`data scheduler comprising:
`means for allocating a tier of service for substantially each
`of a plurality of individual packet data queues;
`means for determining a total number of data packets that
`can use an available communication resource;
`means, operably coupled to the aforementioned means, for
`allocating a proportion of said total number ofdata pack-
`ets to a number ofthe tiers of service to allow individual
`
`packet data queues on a number of tiers to share a com-
`munication resource;
`wherein the packet data scheduler is characterised by:
`scheduling means to provide said communication
`resource to queued packet data users on a tier-by-tier
`basis, such that said resource is made available to
`substantially all tiers.
`In accordance with a third aspect of the present invention,
`a communication unit comprises the packet data scheduler of
`the second aspect.
`In accordance with a fourth aspect ofthe present invention,
`packet data communication system comprises the packet data
`scheduler of the second aspect or is adapted to facilitate the
`method of the first aspect.
`In accordance with a fifth aspect of the present invention,
`there is provided a storage medium storing processor-imple-
`mentable instructions to carry out the method of the first
`aspect.
`In summary, an apparatus and method are described to
`provide for a tier-based weighted fair queuing scheme. The
`preferred algorithm operates using rate allocating service
`disciplines rather than rate controlled service disciplines.
`That is to say the algorithm is configured to combine advan-
`tageous features ofknown techniques, without incurring their
`associated problems, in order to service packets at a faster rate
`than the prior art hierarchical round-robin or weighted fair
`queuing schemes.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`
`US 7,385,994 B2
`
`5
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a simple known packet data queuing
`arrangement.
`Exemplary embodiments ofthe present invention will now
`be described, with reference to the accompanying drawings,
`in which:
`
`FIG. 2 shows a block diagram ofa wireless communication
`system, adapted in accordance with various inventive con-
`cepts of a preferred embodiment of the present invention; and
`FIG. 3 shows a flowchart/functional block diagram of a
`packet data processing operation incorporating the present
`invention.
`
`DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`Referring now to FIG. 2, a cellular-based telephone com-
`munication system 200 is shown in outline, in accordance
`with a preferred embodiment ofthe invention. In the preferred
`embodiment of the invention, the cellular-based telephone
`communication system 200 is compliant with, and contains
`network elements capable of operating over, a UMTS air-
`interface. In particular, the invention relates to the Third Gen-
`eration Partnership Project (3GPP) specification for wide-
`band code-division multiple access (WCDMA) standard
`relating to the UTRAN radio Interface (described in the Euro-
`pcan Tclccommunication Standards Institutc’s (ETSI’s)3G
`TS 25.xxx series of specifications).
`A plurality of subscriber terminals (or user equipment
`(U3) in UMTS nomenclature) 212, 214, 216 communicate
`over radio links 218, 219, 220 with a plurality of base trans-
`ceiver stations, referred to under UMTS terminology as
`Node-Bs, 222, 224, 226, 228, 230, 232. The system com-
`prises many other UEs and Node Bs, which for clarity pur-
`poses are not shown.
`The wireless communication system, sometimes referred
`to as a Network Operator’ s Network Domain, is connected to
`an external packet-based network 234, for example the Inter-
`net. The Network Operator’s Network Domain (described
`with reference to both a 3"’ generation UMTS and a 2"d
`generation GSM system) includes:
`(i) A core network, namely at least one Gateway GPRS
`Support Node (GGSN) 244 and or at least one Serving
`GPRS Support Nodes (SGSN); and
`(ii) An access network, namely:
`(ai) a GPRS (or UMTS) Radio network controller
`(RNC) 236-240; or
`(aii) Base Site Controller (BSC) in a GSM system and/or
`(bi) a GPRS (or UMTS) Node B 222-232; or
`(bii) a Base Transceiver Station (BTS) in a GSM system.
`The GGSN/SGSN 244 is responsible for GPRS (or UMTS)
`interfacing with a Public Switched Data Network (PSDN)
`such as the Internet 234 or a Public Switched Telephone
`Network (PSTN) 234. A SGSN 244 performs a routing and
`tunnelling function for trafiic within say, a GPRS core net-
`work, whilst a GGSN 244 links to external packet networks,
`in this case ones accessing the GPRS mode of the system.
`The Node-Bs 222-232 are connected to external networks,
`through base station controllers, referred to under UMTS
`terminology as Radio Network Controller stations (RNC),
`including the RNCs 236, 238, 240 and mobile switching
`centres (MSCs), such as MSC 242 (the others are, for clarity
`purposes, not shown) and SGSN 244 (the others are, for
`clarity purposes, not shown).
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Each Node-B 222-232 contains one or more transceiver
`units and communicates with the rest ofthe cell-based system
`infrastructure via an Iub interface, as defined in the UMTS
`specification.
`Each RNC 236-240 may control one or more Node-Bs
`222-232 and includes both processing elements 248 and logi-
`cal elements 250. Each MSC 242 provides a gateway to the
`external network 234. The Operations and Management Cen-
`tre (OMC) 246 is operably connected to RNCs 236-240 and
`Node-Bs 222-232 (shown only with respect to Node-B 226
`for clarity). The OMC 246 administers and manages sections
`of the cellular telephone communication system 200, as is
`understood by those skilled in the art.
`In the preferred embodiment of the invention, one or more
`processing elements 248 contained with one or more RNCs
`236-240 have been adapted, to facilitate packet data queuing
`and scheduling in accordance with the preferred embodiment
`of the present invention. In particular, the preferred embodi-
`ment of the present invention describes an algorithm imple-
`mented in one or more RNCs to schedule queued packet data
`transmissions using rate allocating service disciplines rather
`than rate controlled service disciplines.
`In a rate allocating service discipline if excess bandwidth is
`available then it is possible to allocate more packets to certain
`users as long as the service guarantees provided to the other
`users are not broken. In contrast, in a rate controlled service
`discipline, irrespective of the bandwidth that is available, the
`packets are only allocated at the guaranteed rate.
`In the preferred embodiment of the invention, we assume
`that allocation ofresources by the RNC 236 can only be made
`at certain time interval or rounds (also possibly referred to as
`frames), as occurs in known packet data systems. Hence, for
`example, users compete for a 10 Mbps link, the users transmit
`data packets of length l kbit and that the round period is 10
`msec. Therefore, in each round 100 packets are allocated. For
`simplicity, it is also assumed that packets are always of fixed
`size.
`
`It should be noted that the inventive concepts could still be
`applied when non-fixed length packets are employed. How-
`ever, under these conditions the scheme will not guarantee a
`fair allocation of bandwidth. It is envisaged that in some
`packet data systems, this may be acceptable. Nevertheless, in
`the preferred context of a wireless communication system the
`packet (resource unit) allocations are likely to be the same
`size (and small).
`The packet data queuing algorithm in the RNC processor
`248 is based around the concept of employing different tiers
`of service. In particular, each tier, of a number of tiers of
`service, is configured to provide users with a commitment
`that a proportion of the entire system bandwidth will be
`allocated to users operating on that particular tier. As a simple
`example, if we assume two-tiers of service with a single user
`in each tier, we might allocate 75% of the entire system
`resource to the user of the higher tier and 25% of the entire
`resource to the user of the lower tier.
`
`It is within the contemplation of the invention that any
`number of tiers can be used in employing the inventive con-
`cepts herein described.
`Furthermore, in the preferred embodiment ofthe invention,
`in order to control the relative proportions of system band-
`width allocated to each tier, different weights are allocated for
`each tier. Hence, the i”' tier may be defined with a tier weight
`St'ier7z"
`In this manner, a tier-based weighted fair queuing scheme
`has been implemented. Although the invention is described
`with regard to a 3GPP wireless communication system, it is
`envisaged that for other wired or wireless communication
`
`

`
`US 7,385,994 B2
`
`8
`This is repeated for all tiers, in the pre-allocated propor-
`tions for each tier. Within each lower tier, packets are also
`allocated in a round-robin fashion. When the tier level reaches
`
`the lowest tier of users, the resource is again allocated to the
`user, who’s ID is at the head 370 of the lowest tiered queue.
`When the available communication resource has been allo-
`
`cated the user ID at the head of the lowest tiered queue 370,
`the user ID is sent to the tail of the queue 350, and the queue
`moved along. Hence, the lowest priority users move from the
`tail of the queue at location 350, through an intermediate
`location at 360 to the head of the queue at location 370, and
`then back to the tail ofthe queue at location 350. This process
`is repeated until a total of 61 packets 340 have been allocated
`in the lowest tier.
`
`In this manner, the number of queues is kept to a minimum
`and the available communication resource more effectively
`shared amongst all users, dependent upon their allocated tier
`and, to some extent, irrespective of their (tail) starting posi-
`tion in the queue within the tier.
`It is envisaged that the various packet data queuing/order-
`ing components within the RNC 236-240 are realised in this
`embodiment in integrated component form. Of course, in
`other embodiments, they may be realized in discrete form, or
`a mixture of integrated components and discrete components,
`or indeed any other suitable form.
`Furthermore, in this embodiment the queuing algorithm
`function is implemented preferably in a digital signal proces-
`sor. However, it is within the contemplation of the invention
`that the queuing algorithm function described in the above
`embodiments can be embodied in any suitable form of soft-
`ware, firmware or hardware. The queuing algorithm function
`may be controlled by processor-implementable instructions
`and/or data, for carrying out the methods and processes
`described, which are stored in a storage medium or memory.
`The proccssor-implcmcntablc instructions and/or data may
`include any of the following:
`(i) The algorithm for determining the tier-based queuing
`scheme, or
`(ii) A new or adapted lookup table containing revised queu-
`ing parameters or weights.
`(iii) New values of Sfiefi for allocating respective propor-
`tions of the available communication resource to an
`individual tier.
`
`It is envisaged that the memory containing the above pro-
`grams can be a circuit component or module, e.g. a random
`access memory (RAM) or programmable read only memory
`(PROM), or a removable storage medium such as a disk, or
`other suitable medium.
`
`It will be understood that the tier based weighted fair queu-
`ing algorithm, described above, provides at least the follow-
`ing advantages over the weighted fair queuing scheme:
`(i) It is considerably easier to implement.
`(ii) It allows better control of resources when throughput
`rates vary on a per user basis but the packet size remains
`fixed.
`
`(iii) It is more applicable when the when the number of
`allocated resource units per round is small compared to
`the total number of clients requiring service.
`It will also be understood that the tier based weighted fair
`queuing algorithm, described above, provides at least the
`following advantages over the hierarchical round robin
`scheme:
`
`(i) The algorithm is processor efficient, i.e. the system is
`not idle when there is a data packet to send.
`(ii) The algorithm is more flexible to changes in the overall
`number of users served changes (each tier is provided
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`7
`systems facilitating packet data transmissions, algorithms
`other than the preferred one described below with respect to
`FIG. 3 could be implemented, that use a tier-based weighted
`fair queuing algorithm. Furthermore, other criteria and/or
`equation(s) could be employed in determining an appropriate
`queuing scheme using the hereinafter described inventive
`concepts.
`It is also within the contemplation ofthe invention that any
`elements managing packet data transmission, queuing,
`scheduling and/or routing may be controlled, implemented in
`full or implemented in part by adapting any other suitable part
`of the communication system 200. For example, packet data
`queuing may be implemented in one or more MSC 242, or
`within a cell using an adapted Node B 222. Alternatively,
`equivalent elements in other types of systems may, in appro-
`priate circumstances, be adapted to provide or facilitate the
`tier-based weighted fair queuing as described herein.
`Referring now to FIG. 3, a flowchart/functional block dia-
`gram of a packet data processing scheme 300 incorporating
`the present invention is illustrated. The preferred scheme
`operates over a number of tiers, greater than one, with two
`tiers shown for clarity purposes only. The tier of service for
`each user is determined when the session for each user begins.
`For the remaining part ofthis description, it has been assumed
`that this procedure has already been completed.
`Preferably, eachuser is provided with an identification (ID)
`code, which provides an identifier for the user and an indica-
`tion of the amount of the data the user wishes to transfer.
`
`When a user is entered onto the packet data scheme, the user’ s
`ID is placed at the tail ofthe appropriate queue, depending on
`the tier of service, for example tail 355 ofthe it” tier, or tail 350
`of the lowest tier. Note that the user data is stored separately.
`In the it” tier, let us assume that Nfiefl. users are determined
`as wishing to transmit data packets. Thus, the proportion of
`the entire system resource, allocated to the 1”’ tier, (within a
`system employing a total of L tiers), can be defined by the
`following function 325:
`
`Ntier_i * S!ier_i
`
`Nzm /( *Stirr /(
`
`L E
`
`/(:1
`
`¢n'er,z =
`
`The total number of data packets that can be allocated in a
`single round, B310, can then be determined. Assuming that
`there are L tiers we define the number of packets
`
`. BL. Thus, Bl. packets 345 can be
`.
`allocated to each tier; 61 .
`allocated to the it” tier, where:
`ez':¢tz'er7* [5
`
`[3]
`
`Within each tier, packets are then allocated in a round-robin
`fashion in the following manner. y packets are allocated to the
`user whose ID is at the head 375 ofthe tier queue. y is selected
`offline as a value that defines the number of packets that can
`be allocated to a user when at the head of the tier queue.
`Alternatively, it can be determined from an algorithm that
`attempts to counteract the fact that user throughputs vary
`dependent on radio -charmel conditions.
`When these y packets have been allocated the user ID at the
`head of the tier queue 375 is sent to the tail of the queue 355,
`and the queue moved along. Hence, the users move froin the
`tail of the queue at location 355, through an intermediate
`location at 365 to the head of the queue at location 375, and
`then back to the tail of the queue at location 355. This process
`is repeated until a total of 6 packets 345 have been allocated
`in this tier.
`
`

`
`US 7,385,994 B2
`
`9
`with a constant share of the overall bandwidth irrespec-
`tive of the number of users in that tier).
`Thus, an improved packet data queuing algorithm and
`associated elements have been described wherein the afore-
`
`mentioned disadvantages associated with prior art arrange-
`ments has been substantially alleviated.
`Whilst specific, and preferred,
`implementations of the
`present invention are described above, it is clear that one
`skilled in the art could readily apply variations and modifica-
`tions of such inventive concepts.
`The invention claimed is:
`
`1. A method of processing queued data packets in a packet
`data communication system, the method comprising:
`allocating a tier of service for each of a plurality of indi-
`vidual packet data queues, wherein allocating a tier of
`service compri