Packet data queuing and processing

[0001] This invention relates to gateway queuing algorithms in packet networks. The invention is applicable to, but not limited to, gateway queuing algorithms in packet data transmissions, for example for use in the universal mobile telecommunication standard.

[0002] An established cellular radio communication system is GSM (Global System for Mobile Communications). A further 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.

[0003] A fixed network interconnects wireless communication serving elements, such as Node Bs. This fixed network comprises 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 specific 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.

[0004] 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 Network (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.

[0005] Traditional traffic in wireless mobile cellular communication 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 communication path.

[0006] 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 communications. A significant requirement of future wireless communication 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 inefficient to have a continuous link set up between users.

[0007] Consequently, it is envisaged that wireless communication systems will increasingly use packet-switched data technology, to interface to public data networks or information networks such as the Internet. In packet-switched data networks, 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 of order due to the fact that separate communication paths are established for individual data packets for the duration of the particular data packet transmission.

[0008] 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 communications network. Thus, when information is to be communicated 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 of the cellular communication 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^nd ed., John Wiley publishers, author Gilbert Held, 1997, ISBN 0-471-96820-X.

[0009] In a packet data based system, where a high number of subscriber units may require resources for packet transmissions 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.

[0010] Therefore, most packet based systems contain schedulers which control when the individual data packets are transmitted 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 found in Service discipline for guaranteed performance service in packet-switching networks, Hui Zhang, Proceedings of the IEEE, volume 83, no. 10, October 1995.

[0011] However, known schedulers have been optimised for environments 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.

[0012] FIG. 1 illustrates a known arrangement 100 for providing a number of clients (C₁ . . . C_N) 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 competing for a time-shared resource (S) 130 such as a communication 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 transfers 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.

[0013] Two well know queue service algorithms, to allocate the communication resource between queued data packets, are:

[0014] (i) Weighted fair queuing; and

[0015] (ii) Hierarchical round robin.

[0016] Weighted Fair Queuing

[0017] 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 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 conditions it is clear that if there are N users then the throughput provided to each user will be 1/N.

[0018] It is possible to extend the scheme by defining parameters ₁ . . . _N (weights) that set the number of bits allocated to each user per round. This extension allows differential service rates to be provided to different users.

[0019] Weighted fair queuing (also known as generalised processor sharing) further extends the bit-by-bit round-robin technique so that it can be used in packet-based systems with packets of differing size. If we assume that F_P is the hypothetical 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 F_P.

[0020] A weighted fair queuing system is therefore characterised in the following manner. Let S_i (t₀, t) be the amount of traffic served from user i in the interval (t₀, t), such that: $\begin{array}{cc}\frac{S_i\left(t_0,t\right)}{S_j\left(t_0,t\right)}\frac{{}_i}{{}_j}& \left[1\right]\end{array}$

[0021] Where j1,2, . . . N

[0022] Therefore, it can be seen that the features of fair weighted queuing are:

[0023] (i) It provides a fair allocation of bandwidth;

[0024] (ii) It is resistant to ill-behaved packet data sources; and

[0025] (iii) It offers the potential to provide a lower delay for sources not using their full share of the available communication bandwidth.

[0026] Hierarchical Round-Robin

[0027] A hierarchical round-robin scheme employs multiple levels 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.

[0028] However, the hierarchical round robin system does not provide fair allocation of bandwidth to users because resources cannot be transferred between tiers. Furthermore, where differential service is to be provided on a tier-wise basis, the provision of many queues is undesirable. The inventor of the present invention has recognised that the increased number of queues is a function of the lower tiers being serviced only once all of the higher tier queues have been processed. 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.

[0029] Furthermore, when data packets are all of the same length, a round-robin allocation of packets maintains the fair allocation of resources that fair weighted queuing offers. Therefore, the maintenance of a notional bit-by-bit round-robin allocator is redundant and thereby inefficient in the speedy processing of queued packets.

[0030] 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 problems in fair allocation to users since the bit-by-bit round robin simplification does not hold.

[0031] 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.

[0032] Thus, there exists a need in the field of the present invention to provide an improved packet data queuing method, algorithm and associated elements wherein the abovementioned disadvantages may be substantially alleviated.

[0033] Statement of Invention

[0034] 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, comprising the step of:

[0035] allocating a tier of service for substantially each of a plurality of individual packet data queues;

[0036] wherein the method is characterised by the steps of:

[0037] determining a total number of data packets that can use an available communication resource;

[0038] allocating a proportion of said total number of data packets to a number of the tiers of service to allow individual packet data queues on a number of tiers to share a communication resource; and

[0039] 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 substantial number of tiers.

[0040] In accordance with a second aspect of the present invention, there is provided a packet data scheduler queuing data packets in a packet data communication system, the packet data scheduler comprising:

[0041] means for allocating a tier of service for substantially each of a plurality of individual packet data queues;

[0042] means for determining a total number of data packets that can use an available communication resource;

[0043] means, operably coupled to the aforementioned means, for allocating a proportion of said total number of data packets to a number of the tiers of service to allow individual packet data queues on a number of tiers to share a communication resource;

[0044] wherein the packet data scheduler is characterised by:

[0045] 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.

[0046] In accordance with a third aspect of the present invention, a communication unit comprises the packet data scheduler of the second aspect.

[0047] In accordance with a fourth aspect of the 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.

[0048] In accordance with a fifth aspect of the present invention, there is provided a storage medium storing processor-implementable instructions to carry out the method of the first aspect.

[0049] 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 advantageous features of known 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.

[0050] FIG. 1 illustrates a simple known packet data queuing arrangement.

[0051] Exemplary embodiments of the present invention will now be described, with reference to the accompanying drawings, in which:

[0052] FIG. 2 shows a block diagram of a wireless communication system, adapted in accordance with various inventive concepts of a preferred embodiment of the present invention; and

[0053] FIG. 3 shows a flowchart/functional block diagram of a packet data processing operation incorporating the present invention.

[0054] Referring now to FIG. 2, a cellular-based telephone communication system 200 is shown in outline, in accordance with a preferred embodiment of the 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 Generation Partnership Project (3GPP) specification for wide-band code-division multiple access (WCDMA) standard relating to the UTRAN radio Interface (described in the European Telecommunication Standards Institute's (ETSI's)3G TS 25.xxx series of specifications).

[0055] A plurality of subscriber terminals (or user equipment (UE) in UMTS nomenclature) 212, 214, 216 communicate over radio links 218, 219, 220 with a plurality of base transceiver stations, referred to under UMTS terminology as Node-Bs, 222, 224, 226, 228, 230, 232. The system comprises many other UEs and Node Bs, which for clarity purposes are not shown.

[0056] 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 Internet. The Network Operator's Network Domain (described with reference to both a 3^rd generation UMTS and a 2^nd generation GSM system) includes:

[0057] (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

[0058] (ii) An access network, namely:

[0059] (ai) a GPRS (or UMTS) Radio network controller (RNC) 236-240; or

[0060] (aii) Base Site Controller (BSC) in a GSM system and/or

[0061] (bi) a GPRS (or UMTS) Node B 222-232; or

[0062] (bii) a Base Transceiver Station (BTS) in a GSM system.

[0063] 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 traffic within say, a GPRS core network, whilst a GGSN 244 links to external packet networks, in this case ones accessing the GPRS mode of the system.

[0064] 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).

[0065] Each Node-B 222-232 contains one or more transceiver units and communicates with the rest of the cell-based system infrastructure via an I_ub interface, as defined in the UMTS specification.

[0066] Each RNC 236-240 may control one or more Node-Bs 222-232 and includes both processing elements 248 and logical elements 250. Each MSC 242 provides a gateway to the external network 234. The Operations and Management Centre (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.

[0067] 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 embodiment of the present invention describes an algorithm implemented in one or more RNCs to schedule queued packet data transmissions using rate allocating service disciplines rather than rate controlled service disciplines.

[0068] 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.

[0069] In the preferred embodiment of the invention, we assume that allocation of resources 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 1 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.

[0070] It should be noted that the inventive concepts could still be applied when non-fixed length packets are employed. However, 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).

[0071] 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.

[0072] It is within the contemplation of the invention that any number of tiers can be used in employing the inventive concepts herein described.

[0073] Furthermore, in the preferred embodiment of the invention, in order to control the relative proportions of system bandwidth allocated to each tier, different weights are allocated for each tier. Hence, the i^th tier may be defined with a tier weight S_tieri.

[0074] 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 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.

[0075] It is also within the contemplation of the 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 appropriate circumstances, be adapted to provide or facilitate the tier-based weighted fair queuing as described herein.

[0076] Referring now to FIG. 3, a flowchart/functional block diagram 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 of this description, it has been assumed that this procedure has already been completed.

[0077] Preferably, each user is provided with an identification (ID) code, which provides an identifier for the user and an indication 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 of the appropriate queue, depending on the tier of service, for example tail 355 of the i^th tier, or tail 350 of the lowest tier. Note that the user data is stored separately.

[0078] In the i^th tier, let us assume that N_tieri users are determined as wishing to transmit data packets. Thus, the proportion of the entire system resource, allocated to the 1^th tier, (within a system employing a total of L tiers), can be defined by the following function 325: $\begin{array}{cc}{}_{{\mathrm{tier}}_{-}i}=\frac{N_{{\mathrm{tier}}_{\text{-}}i}*S_{{\mathrm{tier}}_{\text{-}}i}}{\underset{k=1}{\overset{L}{}}{N}_{{\mathrm{tier}}_{\text{-}}k}*S_{{\mathrm{tier}}_{\text{-}}k}}& \left[2\right]\end{array}$

[0079] The total number of data packets that can be allocated in a single round, 310, can then be determined. Assuming that there are L tiers we define the number of packets

[0080] allocated to each tier; ₁ . . . _L. Thus, _i packets 345 can be allocated to the i^th tier, where:

[0081] Within each tier, packets are then allocated in a round-robin fashion in the following manner. packets are allocated to the user whose ID is at the head 375 of the tier queue. 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-channel conditions.

[0082] When these 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 from 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 packets 345 have been allocated in this tier.

[0083] This is repeated for all tiers, in the pre-allocated proportions 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 allocated 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 of the queue at location 350. This process is repeated until a total of ₁ packets 340 have been allocated in the lowest tier.

[0084] 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 position in the queue within the tier.

[0085] It is envisaged that the various packet data queuing/ordering 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.

[0086] Furthermore, in this embodiment the queuing algorithm function is implemented preferably in a digital signal processor. 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 software, 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 processor-implementable instructions and/or data may include any of the following:

[0087] (i) The algorithm for determining the tier-based queuing scheme, or

[0088] (ii) A new or adapted lookup table containing revised queuing parameters or weights.

[0089] (iii) New values of S_tieri for allocating respective proportions of the available communication resource to an individual tier.

[0090] It is envisaged that the memory containing the above programs 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.

[0091] It will be understood that the tier based weighted fair queuing algorithm, described above, provides at least the following advantages over the weighted fair queuing scheme:

[0092] (i) It is considerably easier to implement.

[0093] (ii) It allows better control of resources when throughput rates vary on a per user basis but the packet size remains fixed.

[0094] (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.

[0095] 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:

[0096] (i) The algorithm is processor efficient, i.e. the system is not idle when there is a data packet to send.

[0097] (ii) The algorithm is more flexible to changes in the overall number of users served changes (each tier is provided with a constant share of the overall bandwidth irrespective of the number of users in that tier).

[0098] Thus, an improved packet data queuing algorithm and associated elements have been described wherein the aforementioned disadvantages associated with prior art arrangements has been substantially alleviated.

[0099] 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 modifications of such inventive concepts.