Title of Invention	METHOD AND APPARATUS FOR ALLOCATING CHANNEL RESOURCES IN A RADIO COMMUNICATION SYSTEM.
Abstract	The present invention is related to a method and apparatus for resource allocation in a communication system as well as a radio network control node ad a radio access network including such an apparatus. A request for allocation of a channel resource is received (301). In response, a specific channel resource is allocated (302) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released.

Title of Invention

METHOD AND APPARATUS FOR ALLOCATING CHANNEL RESOURCES IN A RADIO COMMUNICATION SYSTEM.

Abstract

The present invention is related to a method and apparatus for resource allocation in a communication system as well as a radio network control node ad a radio access network including such an apparatus. A request for allocation of a channel resource is received (301). In response, a specific channel resource is allocated (302) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released.

Full Text	FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 COMPLETE SPECIFICATION (See section 10, rule 13) "METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM" TELEFONAKTIEBOLAGET LM ERICSSON (PUBL), 164 83 Stockholm, Sweden The following specification particularly describes the invention and the manner in which it is to be performed. WO 2004/114565 PCT/SE2003/001114 METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM TECHNICAL FIELD OF THE INVENTION The invention relates to a method of resource allocation in a communication system as well as an apparatus for resource 5 allocation and a radio network controller and a radio access network including such an apparatus for resource allocation. More in particular, the invention relates to allocation of channel resources in the communication system. DESCRIPTION OF RELATED ART 10 Radio resource management (RRM) is the function of a cellular radio communication system that is responsible for allocating radio channels when establishing calls or data transactions involving specific mobile stations. RRM is typically located in a Radio network node, such as the BSC in GSM or the RNC in a 3GPP 15 UMTS system (often referred to as a WCDMA. system) . In GSM the channel consists of a time slot, while in 3GPP WCDMA. the channel consists of a spreading code. In GSM the channels are basically of fixed bandwidth, a timeslot corresponds to a 16 kbps channel. In WCDMA, there are channels of different bandwidths from 12.2 20 kbps up to 2 Mbps. When a mobile station operating in a WCDMA. system makes a request for a channel it must specify a required bandwidth of the channel. There are channels of different bandwidths, and the length of the spreading code, the OVSF code, determines the bandwidth. OVSF stands for Orthogonal Variable 25 Spreading Factor. The available OVSFs form a Code Tree of codes of different lengths. The higher on the tree, the shorter the code is and the higher bit rate does the code provide. Higher bandwidth codes are of course of higher value. When a code is allocated, other codes above and below on that branch are blocked 30 and can not be allocated. The RRM allocates channels according to a channel (code) allocation algorithm, i.e. a rule for allocating channels. The 2 WO 2004/114565 PCT/SE2003/0011I4 available codes are the valuable resource of the system, it is important that the algorithm works in an optimised way, in order to optimise the capacity of the system. The optimisation principle of code allocation in WCDMA, is to keep as much high value codes as possible free. This is achieved in current WCDMA systems, by chosing codes next to another code of the same rate that is already allocated rather than taking one that is on a branch where no codes are allocated. The published international patent application WO 99/12284 discloses methods for assigning spreading codes to forward-link connections with variable bit-rate in DS-CDMA communication systems. According to one embodiment disclosed in WO 99/12284, spreading codes are assigned to forward-link connections from a first set of orthogonal codes as long as there are codes 15 available in the first set. When no more codes are available in the first set, spreading codes from a second set of orthogonal spreading codes which are non-orthogonal to the spreading codes in the first set are assigned to the forward-link connections. "Dynamic Code Assignment Improves Channel Utilization for Bursty 20 Traffic in Third-Generation Wireless Networks" by Carl E. Fossa, Jr and Nathanial J. Davis IV, discloses a dynamic OVSF code assignment algorithm for sharing bandwith between bursty traffic sources with different QoS requirements wherein the spreading code and bandwith assigned to high QoS traffic is dynamically 25 changed and best effort traffic is allowed to utilize an orthogonal spreading code when the high QoS traffic is not transmitting at peak data rata. "Signalling delay of code allocation strategies" by Goria et al discusses the use of Dynamic Code Assignment (DCA) schemes of 30 OVSF codes in WCDMA systems, wherein OVSF codes are reallocated, i.e. ongoing calls are forced to change codes ("code handover"), in order to prevent code blocking. 2 WO 2004/114565 PCT/SE2003/001114 The prior art algorithms for allocating OVSF codes in WCDMA systems are based on allocating OVSF codes which momentarily optimises the resource allocation at the time the new channel is needed. However, the resource situation is dynamic, new channels 5 are added and old channels are released. Since a specific code allocation will not only block the allocated code, but also other codes above and below in the OVSF. code tree, there is a possibility that two alternative allocations that look similar at the moment, will just a few moments later, when other codes are 10 released, look very different from a resource optimisation perspective. Thus, the current algorithm can make code allocation decisions which, when viewed over a period of time, are not optimal with respect to capacity utilization. 15 SUMMARY OF THE INVENTION The problem dealt with by the present invention is that of providing an alternative way of allocating channel resources in a radio communication system. The problem is solved by a method according to claim 1 and an 20 apparatus according to claim 11. A general object of the invention is to provide an alternative way of allocating channel resources in radio communication systems. A further object is to provide an improved way of allocating 25 channel resources in radio communication systems where channel resource are hierarchically organized such that allocation of a certain channel resource also affects the availability for allocation of other channel resources. Yet another object is to provide an improved way of allocating 30 channel resources in a CDMA based communication system, such as UMTS or CDMA2000, which reduces the risk for code blocking arising in the downlink direction. WO 2004/114565 PCT/SE2003/001114 The invention will now be described in more detail with reference to exemplary embodiments thereof and also with reference to the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS 5 Fig. 1 is a schematic view of an exemplary communication system in which the present invention may be advantageously employed. Fig. 2 is a chart illustrating a OVSF code tree. Fig. 3 is a flow diagram illustrating a basic method according to the invention for channel resource allocation. 10 Fig. 4A-B are flow diagrams illustrating a method for channel resource allocation according to a first exemplary embodiment of the invention. Fig. 5 is a diagram illustrating a first exemplary data structure for representing the OVSF code tree and supporting the method for 15 resource allocation illustrated in Fig. 4A-B. DETAIIiED DESCRIPTION OF THE EMBODIMENTS Fig. 1 illustrates a non-limiting example of a communication system SYS1 in which the present invention may be employed. The exemplary communication system SYS1 illustrated in Fig. 1 is a 20 3rd Generation Partnership Project (3GPP} Universal Mobile Telecommunication System (UMTS). The communication system SYS1 includes a core network CN1, a UMTS Terrestrial Radio Access Network (UTRAN) RANI and User Equipment (UE), alternatively referred to as mobile stations (MS). 25 The core network CKl includes a Mobile services Switching Center (MSC) node MSC1 that provides circuit-switched services and a General Packet Radio Service (GPRS) node SGSN1, sometimes referred to as a serving GPRS support node (SGSN), which is tailored to provide packet-switched type services. 5 WO 2004/114565 PCT/SE2003/001114 Each of the core network nodes MSC1 and SGSN1 connects to the the radio access network RANI over a radio access network interface referred to as the iu interface. The radio access network RANI includes one or more radio network controllers (RNCs). For sake 5 of simplicity, the radio access network RANI of Fig. 1 is shown with only one radio network controller node RNC1. Each radio network controller is connected to and controls a plurality of radio base stations (RBSs) . For example, and again for sake of simplicity, Fig. 1 only illustrates a first radio base station 10 node RBS1 and a second radio base station node RBS2 connected to the radio network controller node RNC1. The interface between the radio network controller RNC1 and the base stations RBS1 and RBS2 is referred to as the Iub interface. Mobile stations, such as mobile station MSI shown in Fig. 1, 15 communicate with one or more radio base stations RBS1-RBS2 over a radio or air interface referred to as the Uu interface. Communication in the direction from the radio base stations RBS1- RBS2 to the mobile stations is referred to as occuring in the downlink (or forward) direction while communication in the 20 opposite direction, i.e. from the mobile stations to the radio base stations RBS1-RBS2 is referred to as occuring in the uplink (or reverse) direction. Each of the radio interface Uu, the Iu interface and the Iub interface are shown by dashed lines in Fig. 1. 25 Information that i s transmitted in the downlink direct ion is spread to the chip rate (3.84 Mcps) using channelization codes and then scrambled by a cell-specific scrambling code while information that is transmitted in the uplink direction are spread to the chip rate using channelization codes and then 30 scrambled by a mobile station specific scrambling code. As is well known to a person skilled in the art, the channelization codes used for spreading are Orthogonal Variable 6 WO 2004/114565 PCT/SE2003/OU1114 Spreading Factor 40VSF) codes, which basically are orthogonal Walsh codes of different length. The OVSF codes preserve orthogonality between downlink physical channels of different rates and spreading factors (SF) and can be 5 organized into a tree-structure as illustrated in Fig. 2. The OVSF codes C11-C88 at different levels in the tree 201 are of different lenghts providing different spreading factor (the spreading factor defines the ratio between the output and input data rates of the spreading process) and bandwith. Codes higher 10 up in the tree are shorter, have lower spreading factor and provide higher bandwith than codes at levels further down in the tree structure. A specific code in the code tree can be used, i.e. allocated, only if no other code on the path from the top/root of the tree 15 or in the sub-tree below the specific code is used with the same scrambling code (Preferably a single downlink scrambling code is used in a cell, but multiple downlink scrambling codes may also be used) . As an example, if code C41 (see Fig. 2) is allocated for providing a physical channel, codes C21 and CI 1, i. e the 20 ancestor codes of code C41, as well as codes C81 and C82, i.e. the descendant codes in the subtree below code 41, would become unavailable for allocation for as long as code C41 remains allocated. The allocation of code C41 would not prevent the other codes of the tree, i.e. codes C22 and C42 and their descendant 25 codes, from being allocated to provide other channels. Due to the fact that there is a limited number of OVSF codes available and the allocation of a certain code causes its ancestor and descendant codes to become unavailable for allocation, the channel (code) allocation algorithm for 30 allocating downlink chanellization codes in the communication system SYS1 becomes crucial in order to optimise the capacity of the system. Codes higher up in the tree, i.e. higher bandwith codes of lower spreading factor, are of course of higher value 7 WO 2004/114565 PCT/SE2003/001114 than codes further down in the tree. The optimization principle of channel allocation in WCDMA, is to keep as much high value codes as possible free. In present WCDMA systems, this is achieved by selecting, for 5 allocation, codes next to another code of the same rate that is already allocated rather than selecting one that is located on a branch where no codes are allocated, i.e. a code which is available for allocation but whose parent code already is unavailable for allocation is preferred over a code which is 10 available for allocation and whose parent code also is available for allocation. As an example scenario (see Fig. 2) illustrating this algorithm for code allocation, consider a situation where codes C88 and C86 are the only codes that currently are allocated in the code tree 201 when a request for allocating a code of 15 spreading factor 8 is received. It is the task of the code allocation algorithm to allocate the optimal code of spreading factor 8 to serve the received request. Codes C87, C85 and C81-C84 are available for allocation. However, since the parent codes of C87 and C85, i.e. codes C44 and C43 respectively, are 20 currently not available for allocation due to the codes C88 and C86 being in use, while the parent codes of codes C81-C84, i.e. codes C41 and C42, are available for allocation, codes C87 and C85 are the preferred candidates for allocation. Hence, either code C87 or C85 is allocated in response to the received channel 25 request. This algorithm, makes no distinction between which one of codes C87 or C85 would be better suited for allocation, and maybe code C85 is selected over code C87 by random choice. The prior art channel (code) allocation algorithm described above is based on momentarily optimising the resource allocation at the 30 time the new channel is needed. However, the resource situation is dynamic, new channels are added and old channels are released. Since a specific code allocation will not only block the allocated code, but also other codes above and below in the code tree, there is a possibility that two alternative allocations 8 WO 2004/114565 PCT/SE2003/001114 that look similar at the moment, will just a few moments later, when other codes are released, look very different from a resource optimisation perspective. Thus, the current algorithm can make code allocation decisions which, when viewed over a 5 period of time, are not optimal with respect to capacity utilization. The present invention provides an improved way of allocating channel resources in a communication system which adresses the above illustrated problem. 10 Fig. 3 illustrates a basic method according to the invention for allocating channel resources in a communication system. At step 301, a request for allocation of a channel resource, e.g. a spreading code, is received. In response, a specific channel resource is allocated at step 302 15 according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released. The basic method can be applied in a variety of different 20 communication systems utilizing different kinds of channel resources. It is however especially useful to apply the invention in systems, e.g. Code Division Multiple Access (CDMA) based systems such as WCDMA, where the channel resources are hierarchically organized, including higher level channel 25 resources and associated lower level channel resources, in which the allocation of a lower level channel resource causes an associated higher level channel resource to become unavailable for allocation. As an example, in Fig. 2 OVSF codes C41-C44 are higher level 30 channel resources associated with lower level channel resources in the form of OVSF codes C81-C88. In this particular example, each higher level channel resource is associated with two lower 9 WO 2004/114565 PCI7SE2003/001114 level channel resources, e.g. higher level OVSF code C41 is associated with the two lower level OVSF codes C81 and C82. Further, a higher level channel resource is only available for allocation if both its associated lower level channel resources 5 are available for allocation, e.g. allocation of either one or both of the lower level OVSF codes C81 and C82 causes higher level OVSF code C41 to become unavailable for allocation. Fig. 4A-B illustrate a first exemplary embodiment of a method for allocating channel resources employed in the communication system 10 SYSl of Fig. 1. Allocation of channel resources in the form of OVSF codes is handled by a channel resource handler RHl (see Fig. 1) in the radio network controller node RNC1. The channel resource handler RHl is typically implemented as software executing on a processor in the radio network controller node 15 RNC1. The channel resource handler RHl allocates OVSF codes 102 in response to received channel requests 101. At step 401 of Fig. 4A, a request for a channel resource is received by the resource handler RHl. The request includes an estimate of for how long the channel resource will be needed. In 20 this exemplary embodiment of the invention, the application, e.g. a streaming multimedia application providing a video on demand service, provides a duration parameter when establishing a communication session with a certain mobile station and also QoS parameters indicating the required bandwith. The resource handler 25 RHl translates the provided duration parameter into an estimate of when the requested channel resource will be released based on the current time. At step 402 a check is made as to whether there is at least one OVSF code of suitable bandwith available for allocation. If no 30 available code is found (an alternative NO at step 402), the resource handler RHl reports' that no suitable OVSF code is available for serving the received request and the request for establishing a communication session is either refused or bandwith renegotiation is initiated. WO 2004/114565 PCT/SE2003/0U1114 If there is at least one OVSF code of suitable bandwith available for allocation (an alternative YES at step 402), a check is made at step 403 as to whether there is more than one such code available for allocation. If there is only one code of suitable 5 bandwith available for allocation (an alternative NO at step 403), said code is selected as the only available candidate code for allocation at step 404 and allocated at step 413 in response to the received channel request. If there are more than one OVSF code of suitable bandwith 10 available for allocation (an alternative YES at step 403), all the available OVSF codes of suitable bandwith are identified as "candidate codes" at step 405 and a first code among said candidate codes is selected for further analysis. At step 406 analysis of the selected candidate code is initiated 15 by considering whether the parent code of the candidate code is available for allocation. If the parent code is available for allocation (an alternative YES at step 406), i.e. all descendant codes of the parent code are available for allocation, the candidate code is added to list C at step 407. If the parent code 20 is not available for allocation (an alternative NO at step 406), implying that the sibling code (the code having the same parent code as the candidate code) of the candidate code is also not available for allocation, analysis of the candidate code proceeds at step 408. 25 At step 408 the estimated time of release for the requested channel resource is compared to an estimate for when the parent code of the candidate code will become available for allocation. If the estimated time of release for the requested channel resource is before or the same as the estimated time for when the 30 parent code will become available for allocation (an alternative YES at step 408), the candidate code is added to list A at step 409. Otherwise (an alternative NO at step 408), i.e. if the estimated time of release of the requested channel resource is 11 WO 2004/114565 PCTSE2003/001114 after the estimated time for when the parent code will become available, the candidate code is added to list B. After either one of steps 407, 409 and 410 processing continues at step 411 , where a check is made whether all candidate codes 5 have been analysed. If there remain candidate codes that need to be analyzed (an alternative NO at step 411), processing continues at step 406 where analysis of one of the remaining candidate codes is initiated. If all candidate codes have been analyzed (an alternative YES at step 411), all candidate codes will have been 10 entered on one of lists A, B and C and the candidate code considered to be most suitable for allocation is selected at step 412 from said lists. The selected candidate code is allocated at step 413 in response to the received channel request. Step 412 is further elaborated in Fig. 4B. Upon entering step 15 412, list A and B will contain those candidates whose parent codes are already unavailable for allocation. List A will contain candidate codes whose parents are estimated to become available for allocation after (or at the same time as) the estimated release of the requested channel resource while list B will 20 contain candidate codes whose parents are estimated to become available for allocation before the estimated release of the requested channel resource. List C will contain those candidates whose parent codes are currently available for allocation. At step 414 a check is made whether there are any candidate codes 25 in list A. If list A includes at least one candidate code (an alternative YES at step 414), the candidate code on list A whose parent code will first become available for allocation is selected as most suitable for allocation. Selecting a candidate code from list A for allocation implies that the estimated time 30' of the corresponding parent code becoming available for allocation will not be postponed while selecting the candidate code whose parent will first become available implies that allocation of similar duration is packed together, which is good since then 12 WO 2004/114565 PCT/SE2003/OOU14 channel resources will become available for allocation in "chunks", freeing up larger areas of the code tree at once. If list A is empty (an alternative NO) at step 414, a check is made at step 416 whether there are any candidate codes in List B. 5 If list B includes at least one candidate code (an alternative YES at step 416), the candidate code on list B whose parent code will last become available for allocation is selected as most suitable for allocation. Selecting a candidate code from list B for allocation implies that the estimated time of the 10 correspoding parent code becoming available for allocation will be postponed somewhat, while selecting the candidate code whose parent will last become available minimizes said postponement. Finally, if list B also is empty (an alternative NO at step 416), a candidate code is selected from list C. Selecting a candidate 15 code from list C for allocation implies that the corresponding parent code will become unavailable for allocation. Since selecting a candidate code for allocation from list A or B involves considering how the estimated time of release of the requested channel resource relates to the estimated time of 20 parent codes of said candidate codes becoming available for allocation, the candidate codes are Preferably sorted upon entry on list A and B respectively based on the estimated time of the respective parent code becoming available for allocation. Preferably lists A and B are sorted such that upon entering step 25 412, the first candidate code on list A and list B respectively are the candidate codes that would be selected from said lists, i.e. the first candidate code on list A is the candidate code whose parent code is estimated to be the first parent code that becomes available after, or Preferably at the same time as, the 30 requested channel resource is released, while the first candidate code on list B is the candidate code whose parent code will be the last parent code that becomes available before release of the requested channel resource. 13 WO 2004/114565 PCT/SE2003/00114 Lists A, B and C are used to organize the available channel resources, i.e. candidate codes, into different subsets in order to manage the selection process. On a first level, the candidate codes are divided into a first 5 subset including candidate codes (lower level channel resources) associated with parent codes (higher level channel resources) currently available for allocation, and a second subset including candidate codes associated with parent codes currently unavailable for allocation. The first subset of candidate codes 10 is represented by list C while the second subset of candidate codes is represented by the union of lists A and B. The second subset of candidate codes is further divided into a third subset including candidate codes associated with parent codes which are estimated to become available for allocation at 15 the same time or after the estimated release of the requested channel resource and a fourth subset including candidated codes associated with parent codes which are estimated to become available for allocation before the estimated release of the requested channel resource. The third subset of candidate codes 20 is represented by list A while the fourth subset of candidate codes is represented by list B. Thus, according to the rule for allocating channel resources (OVSF codes) illustrated above, allocation of a candidate code whose parent code already is unavailable for allocation is 25 preferred over allocating a code whose parent is available for allocation. Of those candidate codes whose parent codes already are unavailable for allocation, allocation of a code whose parent code is estimated to become available for allocation after or at the same time as the estimated release of the requested channel 30 resource is preferred over allocating a code whose parent is estimated to be released before the estimated release of the requested channel resource. Finally, if after considering the criterias above more than one candidate code appears suitable for selection, the code whose parent is estimated to become available 14 WO 2004/114565 PCT/SE2003/001114 for allocation closest in time to the estimated release of the requested channel resource is selected for allocation. Fig. 5 illustrates an exemplary data structure for representing the OVSF code tree of Fig. 2. The data strucuture comprises an 5 array of records representing the OVSF codes. The records have index 1 to n, where n is the total number of OVSF codes in the OVSF code tree. Each record, representing a single OVSF code, includes the following fields: Parent code ref 501: 10 The index of the codes parent code. The code at the root of the tree has no parent code, which is represented by a reserved nil-value (e.g. zero). Spreading factor 502: The spreading factor of the OVSF code 15 Status 503: Indicates whether the OVSF code is allocated/not allocated. Estimated time of release 504: Indicates the estimated time of release when the code is allocated. 20 Code 505: The OVSF code number represented by the record. Each time a OVSF code needs to be allocated, the array of records illustrated in Fig. 5 is traversed in search for candidate codes available for allocation, and the index of available candidate 25 codes, together with estimates for when the corresponding parent codes will become available for allocation, are registered in temporary data structures representing lists A, B and C (not shown in Fig. 5) . The estimate for when a parent code of a candidate code will become available for allocation corresponds 30 to the longest time any one of the parent codes descendant codes is estimated to remain allocated. 15 WO 2004/114565 PCT/SE2003/001114 Apart from the above disclosed exemplary first embodiment of the invention, there are several ways of providing rearrangements, modifications and substitutions of the first embodiment resulting in additional embodiments of the invention. 5 There are many possible alternative ways of providing estimates of how long channel resources are needed. According to the exemplary first embodiment of the invention disclosed above, the estimated time of release of channel resources is based on a duration parameter provide by an application when establishing a 10 communication session with a certain mobile station. Alternatively an application could indicate an amount of data to be transferred (e.g. the size of a picture, MMS message or file to be tranferred), allowing the estimated time of release of channel resources to be determined based on said amount of data 15 and the available (or by the application requested) bandwith. Yet other alternatives would be to provide said estimates based on statistical data on how long the channel resources are required by different applications, users and/or communication sessions established with a certain set of QoS-parameters. 20 Different rules can be defined for how channel resources are allocated while considering the estimated time of release of the requested channel resource and previosly allocated channel resources. Thus, one example of an alternative to the rule applied in the first exemplary embodiment disclosed above, would 25 be to divide the available candidate codes into candidate codes associated with parent codes which are curently available for allocation and candidate codes associated with parent codes which are currently unavailable for allocation, and then, among the candidate codes in the latter subset (i.e. available candidate 30 codes associated with parent codes currently not available for allocation) select a candidate code associated with a parent code whose estimated time of becoming available for allocation is closest to the estimated time of release of the requested channel resource (regardless of whether said parent code will become WO 2004/114565 PCT/SE2003/00U14 available before or after said estimated release of the requested channel resource). An allocated channel resource (e.g. an OVSF code) may be released before an established communication session (e.g. a multimedia 5 session) with a particular mobile station is terminated; thus requiring allocation of a new channel resource for supporting the remaining part of the communication session. This may occur e.g. as a result of handover from a first cell to a second cell/ requiring allocation of a new channel resource in the second cell 10 and release of the channel resource originally allocated in the first cell (note that when using soft handover, the channel resource in the first cell may be retained at least for a while). It may also occur e.g. as a result of code reallocation in a cell in order to achieve better resource usage in the cell. An 15 estimate for when the new channel resource will be released may then be based on the remaining time until the estimated release of the originally allocated channel resource. Allocation of the new channel resource may then proceed according to the invention based on said estimate for when the new channel resource will be 20 released. It is also possible to allow estimates for when channel resources will become available to be subsequently updated (extended or shortened). Even though the invention in its first exemplary embodiment has 25 been applied in a 3GPP UMTS system, the invention may of course be applied in other radio communication systems as well and in particular in communciation systems where channel resource are hierarchically organized such that allocation of a certain channel resource also affects the availability for allocation of 30 other channel resources. Another example of a system having hierarchically organized channel resources is CDMA2000 which similar to UMTS uses channel resources in the form of different length Walsh codes. Yet another example of a system utilizing hierarchically organized resources is TIA/EIA-136 (DAMPS). By 17 WO 2004/114565 PCT/SE2003/001114 utilizing the present invention in a TIA/EIA-136 system, where channel resources are provided in the form of carrier frequencies and time slots on said carrier frequencies/ it is possible to implement an Adaptive Channel Allocation (ACA) scheme wherein the 5 number of carrier frequencies in active use for communication in a cell can be minimized by packing allocations of similar duration on the same carrier frequency. ABBREVIATIONS 10 ACA Adaptive Channel Allocation BSC Base Station controller CDMA Code Division Multiple Access DAMPS Digital Advanced Mobile Phone System EIA Electrical Industries Associates 15 GPRS General Packet Radio Service GSM Global System for Mobile communication MS Mobile Station MSC Mobile services Switching Centre OVSF Orthogonal Variable Spreading Factor 20 QoS Quality of Service RBS Radio Base Station RNC Radio Network Controller RRM Radio resource Management SF Spreading Factor 25 TIA Telecommunications Industry Association SGSN Serving GPRS Support Node UE User Equipment UMTS Universal Mobile Telecommunication System UTRAN UMTS Terrestrial Radio Access Network 30 WCDMA Wideband CDMA 3GPP 3rd Generation Partnership Project 19 WO 2004/114565 PCT/SE/2003/00114 CLAIMS 1. A method for allocating channel resources in a radio communication system (SYS1), the method comprising: receiving (301) a request for allocation of a channel resource; 5 allocating (302) a specific channel resource (C11-C88) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released. 10 2. A method according to claim 1, wherein said radio communication system is a Code Division Multiple Access based system and said channel resources are spreading codes. 3. A method according to claim 2, wherein said spreading codes are Orthogonal Variable Spreading Factor codes (C11-C88). 15 4. A method according to any one of claims 2-3, wherein said channel resources include at least two higher level channel resources (C41, C42), said higher level channel resources being associated with at least two lower level channel resources each (C81-C82, C83-C84) such that a higher level channel resource 20 (C41) is available for allocation only when all lower level channel resources (C81-C82) associated with said higher level channel resource also are available for allocation, said lower level channel resources having higher spreading factors than said higher level channel resources. 25 5, A method according to claim 1, wherein said channel resources are hierarchically organized and include at least two higher level channel resources, said higher level channel resources being associated with at least two lower level channel resources each such that a higher level channel resource is available for 30 allocation only when all lower level channel resources associated WO 2004/114565 PCT/SE/2003/001114 with said higher level channel resource also are available for allocation. 6. A method according to any one of claims 4-5, wherein according to said predetermined rule, 5 if at least two lower level channel resources are available candidates for allocating as said specific channel resource, and if said available candidates include both a first and a second subset of lower level channel resources, wherein said first and second subsets include at least one lower level channel 10 resource each, and each lower level channel resource in said first subset is associated with a higher level channel resource which is currently available for allocation while each lower level channel resource in said second subset is associated with a higher level channel resource which is currently not available 15 for allocation, a lower level channel resource in said second subset is selected as said specific channel resource. 7. A method according to claim 6, wherein according to said predetermined rule, if said second subset includes at least two 20 lower level channel resources, said predetermined rule includes comparing estimates for when the higher level channel resources associated with the lower level channel resources in said second subset will become available for allocation with the estimate of when said specific channel resource will be released. 25 8. A method according to claim 7, wherein according to said predetermined rule, if said second subset includes both a third and a fourth subset, wherein said third and fourth subsets include at least one lower level channel resource each, and each lower level channel resource in said third subset is associated 30 with a higher level channel resource which is estimated to become available at the same time or after the estimated release of said specific channel resource while each lower level channel resource 20 WO 2004/114565 PCT/SE/2003/001114 in said fourth subset is associated with a higher level channel resource which is estimated to become available before the estimated release of said specific channel resource, a lower level channel resource in said third subset is selected 5 as said specific channel resource. 9. A method according to claim 8, wherein according to said predetermined rule, if said third subset includes at least two lower level channel resources, 10 a lower level channel resource in said third subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the estimated time of release of said specific channel resource, is selected as said specific channel resource. 15 10. A method according to claim 7, wherein according to said predetermined rule, a lower level channel resource in said second subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the estimated time of release of said specific channel 20 resource, is selected as said specific channel resource. 11. An apparatus (RH1) for allocating channel resources in a radio communication system, said apparatus comprising: electronic circuitry for receiving a request for allocation of a 25 channel resource; electronic circuitry for allocating a first channel resource according to a predetermined rule which includes considering an estimate of when said first channel resource will be released and estimates of when other previously allocated channel resources 30 will be released. 21 WO 2004/114565 PCT/SE2003/001114 12. An apparatus according to claim 11, wherein said radio communication system is a Code Division Multiple Access based system and said channel resources are spreading codes. 13. An apparatus according to claim 12, wherein said spreading 5 codes are Orthogonal Variable Spreading Factor codes (C11-C88). 14. An apparatus according to any one of claims 12-13, wherein said channel resources include at least two higher level channel resources (C41, C42), said higher level channel resources being associated with at least two lower level channel resources each 10 (C81-C82, C83-C84) such that a higher level channel resource (C41) is available for allocation only when all lower level channel resources (C81-C82) associated with said higher level channel resource also are available for allocation, said lower level channel resources having higher spreading factors than said 15 higher level channel resources. 15. An apparatus according to claim 11, wherein said channel resources are hierarchically organized and include at least two higher level channel resources, said higher level channel resources being associated with at least two lower level channel 20 resources each such that a higher level channel resource is available for allocation only when all lower level channel resources associated with said higher level channel resource also are available for allocation. 16. An apparatus according to any one of claims 14-15, wherein 25 according to said predetermined rule, if at least two lower level channel resources are available candidates for allocating as said specific channel resource, and if said available candidates include both a first and a second subset of lower level channel resources, wherein said 30 first and second subsets include at least one lower level channel resource each, and each lower level channel resource in said first subset is associated with a higher level channel resource 22 WO 2004/114565 PCT/SE2003/001114 which is currently available for allocation while each lower level channel resource in said second subset is associated with a higher level channel resource which is currently not available for allocation, 5 a lower level channel resource in said second subset is selected as said specific channel resource. 17. An apparatus according to claim 16, wherein according to said predetermined rule, if said second subset includes at least two lower level channel resources, said predetermined rule includes 10 comparing estimates for when the higher level channel resources associated with the lower level channel resources in said second subset will become available for allocation with the estimate of when said specific channel resource will be released. 18. An apparatus according to claim 17, wherein according to said 15 predetermined rule, if said second subset includes both a third and a fourth subset, wherein said third and fourth subsets include at least one lower level channel resource each, and each lower level channel resource in said third subset is associated with a higher level channel resource which is estimated to become 20 available at the same time or after the estimated release of said specific channel resource while each lower level channel resource in said fourth subset is associated with a higher level .channel resource which is estimated to become available before the estimated release of said specific channel resource, 25 a lower level channel resource in said third subset is selected as said specific channel resource. 19. An apparatus according to claim 18, wherein according to said predetermined rule, if said third subset includes at least two lower level channel resources, 30 a lower level channel resource in said third subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the 23 WO 2004/114565 PCT/SE2003/001114 estimated time of release of said specific channel resource, is selected as said specific channel resource. 20. An apparatus according to claim 17, wherein according to said predetermined rule, a lower level channel resource in said second subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the estimated time of release of said specific channel resource, is selected as said specific channel resource. 21. A radio network controller node for use in a radio communication system including an apparatus according to any one of claims 11-20. 22. A radio access network including an apparatus according to any one of claims 11-20. 23. A method for allocating channel resources in a radio communication system (SYS1), an apparatus (RH1) for the same and a radio network controller node for use in a radio communication system substantially as herein described with reference to the accompanying drawings. Dated this 10th day of November, 2005 (RAVI BHOLA) Of K & S PARTNERS AGENT FOR THE APPLICANT(S) 24 ABSTRACT "METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM" The present invention is related to a method and apparatus for resource allocation in a communication system as well as a radio network control node ad a radio access network including such an apparatus. A request for allocation of a channel resource is received (301). In response, a specific channel resource is allocated (302) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released. -25-

Full Text

FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION (See section 10, rule 13)
"METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM"
TELEFONAKTIEBOLAGET LM ERICSSON (PUBL), 164 83 Stockholm, Sweden
The following specification particularly describes the invention and the manner in which it is to be performed.

WO 2004/114565

PCT/SE2003/001114

METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM TECHNICAL FIELD OF THE INVENTION
The invention relates to a method of resource allocation in a communication system as well as an apparatus for resource
5 allocation and a radio network controller and a radio access network including such an apparatus for resource allocation. More in particular, the invention relates to allocation of channel resources in the communication system.
DESCRIPTION OF RELATED ART
10 Radio resource management (RRM) is the function of a cellular radio communication system that is responsible for allocating radio channels when establishing calls or data transactions involving specific mobile stations. RRM is typically located in a Radio network node, such as the BSC in GSM or the RNC in a 3GPP
15 UMTS system (often referred to as a WCDMA. system) . In GSM the channel consists of a time slot, while in 3GPP WCDMA. the channel consists of a spreading code. In GSM the channels are basically of fixed bandwidth, a timeslot corresponds to a 16 kbps channel. In WCDMA, there are channels of different bandwidths from 12.2
20 kbps up to 2 Mbps. When a mobile station operating in a WCDMA. system makes a request for a channel it must specify a required bandwidth of the channel. There are channels of different bandwidths, and the length of the spreading code, the OVSF code, determines the bandwidth. OVSF stands for Orthogonal Variable
25 Spreading Factor. The available OVSFs form a Code Tree of codes of different lengths. The higher on the tree, the shorter the code is and the higher bit rate does the code provide. Higher bandwidth codes are of course of higher value. When a code is allocated, other codes above and below on that branch are blocked
30 and can not be allocated.
The RRM allocates channels according to a channel (code) allocation algorithm, i.e. a rule for allocating channels. The
2

WO 2004/114565

PCT/SE2003/0011I4

available codes are the valuable resource of the system, it is important that the algorithm works in an optimised way, in order to optimise the capacity of the system. The optimisation principle of code allocation in WCDMA, is to keep as much high
value codes as possible free. This is achieved in current WCDMA systems, by chosing codes next to another code of the same rate that is already allocated rather than taking one that is on a branch where no codes are allocated.
The published international patent application WO 99/12284
discloses methods for assigning spreading codes to forward-link connections with variable bit-rate in DS-CDMA communication systems. According to one embodiment disclosed in WO 99/12284, spreading codes are assigned to forward-link connections from a first set of orthogonal codes as long as there are codes
15 available in the first set. When no more codes are available in the first set, spreading codes from a second set of orthogonal spreading codes which are non-orthogonal to the spreading codes in the first set are assigned to the forward-link connections.
"Dynamic Code Assignment Improves Channel Utilization for Bursty
20 Traffic in Third-Generation Wireless Networks" by Carl E. Fossa, Jr and Nathanial J. Davis IV, discloses a dynamic OVSF code assignment algorithm for sharing bandwith between bursty traffic sources with different QoS requirements wherein the spreading code and bandwith assigned to high QoS traffic is dynamically

25 changed and best effort traffic is allowed to utilize an orthogonal spreading code when the high QoS traffic is not transmitting at peak data rata.
"Signalling delay of code allocation strategies" by Goria et al discusses the use of Dynamic Code Assignment (DCA) schemes of
30 OVSF codes in WCDMA systems, wherein OVSF codes are reallocated, i.e. ongoing calls are forced to change codes ("code handover"), in order to prevent code blocking.
2

WO 2004/114565

PCT/SE2003/001114

The prior art algorithms for allocating OVSF codes in WCDMA systems are based on allocating OVSF codes which momentarily optimises the resource allocation at the time the new channel is needed. However, the resource situation is dynamic, new channels
5 are added and old channels are released. Since a specific code allocation will not only block the allocated code, but also other codes above and below in the OVSF. code tree, there is a possibility that two alternative allocations that look similar at the moment, will just a few moments later, when other codes are
10 released, look very different from a resource optimisation perspective. Thus, the current algorithm can make code allocation decisions which, when viewed over a period of time, are not optimal with respect to capacity utilization.
15 SUMMARY OF THE INVENTION
The problem dealt with by the present invention is that of providing an alternative way of allocating channel resources in a radio communication system.
The problem is solved by a method according to claim 1 and an
20 apparatus according to claim 11.
A general object of the invention is to provide an alternative way of allocating channel resources in radio communication systems.
A further object is to provide an improved way of allocating
25 channel resources in radio communication systems where channel resource are hierarchically organized such that allocation of a certain channel resource also affects the availability for allocation of other channel resources.
Yet another object is to provide an improved way of allocating
30 channel resources in a CDMA based communication system, such as UMTS or CDMA2000, which reduces the risk for code blocking arising in the downlink direction.

WO 2004/114565

PCT/SE2003/001114

The invention will now be described in more detail with reference to exemplary embodiments thereof and also with reference to the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
5 Fig. 1 is a schematic view of an exemplary communication system in which the present invention may be advantageously employed.
Fig. 2 is a chart illustrating a OVSF code tree.
Fig. 3 is a flow diagram illustrating a basic method according to the invention for channel resource allocation.
10 Fig. 4A-B are flow diagrams illustrating a method for channel resource allocation according to a first exemplary embodiment of the invention.
Fig. 5 is a diagram illustrating a first exemplary data structure for representing the OVSF code tree and supporting the method for
15 resource allocation illustrated in Fig. 4A-B.
DETAIIiED DESCRIPTION OF THE EMBODIMENTS
Fig. 1 illustrates a non-limiting example of a communication system SYS1 in which the present invention may be employed. The exemplary communication system SYS1 illustrated in Fig. 1 is a 20 3rd Generation Partnership Project (3GPP} Universal Mobile Telecommunication System (UMTS). The communication system SYS1 includes a core network CN1, a UMTS Terrestrial Radio Access Network (UTRAN) RANI and User Equipment (UE), alternatively referred to as mobile stations (MS).
25 The core network CKl includes a Mobile services Switching Center (MSC) node MSC1 that provides circuit-switched services and a General Packet Radio Service (GPRS) node SGSN1, sometimes referred to as a serving GPRS support node (SGSN), which is tailored to provide packet-switched type services.
5

WO 2004/114565

PCT/SE2003/001114

Each of the core network nodes MSC1 and SGSN1 connects to the the radio access network RANI over a radio access network interface referred to as the iu interface. The radio access network RANI includes one or more radio network controllers (RNCs). For sake
5 of simplicity, the radio access network RANI of Fig. 1 is shown with only one radio network controller node RNC1. Each radio network controller is connected to and controls a plurality of radio base stations (RBSs) . For example, and again for sake of simplicity, Fig. 1 only illustrates a first radio base station
10 node RBS1 and a second radio base station node RBS2 connected to the radio network controller node RNC1. The interface between the radio network controller RNC1 and the base stations RBS1 and RBS2 is referred to as the Iub interface.
Mobile stations, such as mobile station MSI shown in Fig. 1,
15 communicate with one or more radio base stations RBS1-RBS2 over a
radio or air interface referred to as the Uu interface.
Communication in the direction from the radio base stations RBS1-
RBS2 to the mobile stations is referred to as occuring in the
downlink (or forward) direction while communication in the
20 opposite direction, i.e. from the mobile stations to the radio
base stations RBS1-RBS2 is referred to as occuring in the uplink
(or reverse) direction.
Each of the radio interface Uu, the Iu interface and the Iub interface are shown by dashed lines in Fig. 1.
25 Information that i s transmitted in the downlink direct ion is spread to the chip rate (3.84 Mcps) using channelization codes and then scrambled by a cell-specific scrambling code while information that is transmitted in the uplink direction are spread to the chip rate using channelization codes and then
30 scrambled by a mobile station specific scrambling code.
As is well known to a person skilled in the art, the channelization codes used for spreading are Orthogonal Variable
6

WO 2004/114565

PCT/SE2003/OU1114

Spreading Factor 40VSF) codes, which basically are orthogonal Walsh codes of different length.
The OVSF codes preserve orthogonality between downlink physical channels of different rates and spreading factors (SF) and can be
5 organized into a tree-structure as illustrated in Fig. 2.
The OVSF codes C11-C88 at different levels in the tree 201 are of different lenghts providing different spreading factor (the spreading factor defines the ratio between the output and input data rates of the spreading process) and bandwith. Codes higher
10 up in the tree are shorter, have lower spreading factor and provide higher bandwith than codes at levels further down in the tree structure.
A specific code in the code tree can be used, i.e. allocated, only if no other code on the path from the top/root of the tree
15 or in the sub-tree below the specific code is used with the same scrambling code (Preferably a single downlink scrambling code is used in a cell, but multiple downlink scrambling codes may also be used) . As an example, if code C41 (see Fig. 2) is allocated for providing a physical channel, codes C21 and CI 1, i. e the
20 ancestor codes of code C41, as well as codes C81 and C82, i.e. the descendant codes in the subtree below code 41, would become unavailable for allocation for as long as code C41 remains allocated. The allocation of code C41 would not prevent the other codes of the tree, i.e. codes C22 and C42 and their descendant
25 codes, from being allocated to provide other channels.
Due to the fact that there is a limited number of OVSF codes available and the allocation of a certain code causes its ancestor and descendant codes to become unavailable for allocation, the channel (code) allocation algorithm for
30 allocating downlink chanellization codes in the communication system SYS1 becomes crucial in order to optimise the capacity of the system. Codes higher up in the tree, i.e. higher bandwith codes of lower spreading factor, are of course of higher value
7

WO 2004/114565

PCT/SE2003/001114

than codes further down in the tree. The optimization principle of channel allocation in WCDMA, is to keep as much high value codes as possible free.
In present WCDMA systems, this is achieved by selecting, for
5 allocation, codes next to another code of the same rate that is already allocated rather than selecting one that is located on a branch where no codes are allocated, i.e. a code which is available for allocation but whose parent code already is unavailable for allocation is preferred over a code which is
10 available for allocation and whose parent code also is available for allocation. As an example scenario (see Fig. 2) illustrating this algorithm for code allocation, consider a situation where codes C88 and C86 are the only codes that currently are allocated in the code tree 201 when a request for allocating a code of
15 spreading factor 8 is received. It is the task of the code allocation algorithm to allocate the optimal code of spreading factor 8 to serve the received request. Codes C87, C85 and C81-C84 are available for allocation. However, since the parent codes of C87 and C85, i.e. codes C44 and C43 respectively, are
20 currently not available for allocation due to the codes C88 and C86 being in use, while the parent codes of codes C81-C84, i.e. codes C41 and C42, are available for allocation, codes C87 and C85 are the preferred candidates for allocation. Hence, either code C87 or C85 is allocated in response to the received channel
25 request. This algorithm, makes no distinction between which one of codes C87 or C85 would be better suited for allocation, and maybe code C85 is selected over code C87 by random choice.
The prior art channel (code) allocation algorithm described above is based on momentarily optimising the resource allocation at the
30 time the new channel is needed. However, the resource situation is dynamic, new channels are added and old channels are released. Since a specific code allocation will not only block the allocated code, but also other codes above and below in the code tree, there is a possibility that two alternative allocations
8

WO 2004/114565

PCT/SE2003/001114

that look similar at the moment, will just a few moments later, when other codes are released, look very different from a resource optimisation perspective. Thus, the current algorithm can make code allocation decisions which, when viewed over a
5 period of time, are not optimal with respect to capacity utilization.
The present invention provides an improved way of allocating channel resources in a communication system which adresses the above illustrated problem.
10 Fig. 3 illustrates a basic method according to the invention for allocating channel resources in a communication system.
At step 301, a request for allocation of a channel resource, e.g. a spreading code, is received.
In response, a specific channel resource is allocated at step 302 15 according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released.
The basic method can be applied in a variety of different
20 communication systems utilizing different kinds of channel resources. It is however especially useful to apply the invention in systems, e.g. Code Division Multiple Access (CDMA) based systems such as WCDMA, where the channel resources are hierarchically organized, including higher level channel
25 resources and associated lower level channel resources, in which the allocation of a lower level channel resource causes an associated higher level channel resource to become unavailable for allocation.
As an example, in Fig. 2 OVSF codes C41-C44 are higher level
30 channel resources associated with lower level channel resources
in the form of OVSF codes C81-C88. In this particular example,
each higher level channel resource is associated with two lower
9

WO 2004/114565

PCI7SE2003/001114

level channel resources, e.g. higher level OVSF code C41 is associated with the two lower level OVSF codes C81 and C82. Further, a higher level channel resource is only available for allocation if both its associated lower level channel resources
5 are available for allocation, e.g. allocation of either one or both of the lower level OVSF codes C81 and C82 causes higher level OVSF code C41 to become unavailable for allocation.
Fig. 4A-B illustrate a first exemplary embodiment of a method for allocating channel resources employed in the communication system
10 SYSl of Fig. 1. Allocation of channel resources in the form of OVSF codes is handled by a channel resource handler RHl (see Fig. 1) in the radio network controller node RNC1. The channel resource handler RHl is typically implemented as software executing on a processor in the radio network controller node
15 RNC1. The channel resource handler RHl allocates OVSF codes 102 in response to received channel requests 101.
At step 401 of Fig. 4A, a request for a channel resource is received by the resource handler RHl. The request includes an estimate of for how long the channel resource will be needed. In
20 this exemplary embodiment of the invention, the application, e.g. a streaming multimedia application providing a video on demand service, provides a duration parameter when establishing a communication session with a certain mobile station and also QoS parameters indicating the required bandwith. The resource handler
25 RHl translates the provided duration parameter into an estimate of when the requested channel resource will be released based on the current time.
At step 402 a check is made as to whether there is at least one OVSF code of suitable bandwith available for allocation. If no
30 available code is found (an alternative NO at step 402), the resource handler RHl reports' that no suitable OVSF code is available for serving the received request and the request for establishing a communication session is either refused or bandwith renegotiation is initiated.

WO 2004/114565

PCT/SE2003/0U1114

If there is at least one OVSF code of suitable bandwith available for allocation (an alternative YES at step 402), a check is made at step 403 as to whether there is more than one such code available for allocation. If there is only one code of suitable
5 bandwith available for allocation (an alternative NO at step 403), said code is selected as the only available candidate code for allocation at step 404 and allocated at step 413 in response to the received channel request.
If there are more than one OVSF code of suitable bandwith

10 available for allocation (an alternative YES at step 403), all the available OVSF codes of suitable bandwith are identified as "candidate codes" at step 405 and a first code among said candidate codes is selected for further analysis.
At step 406 analysis of the selected candidate code is initiated 15 by considering whether the parent code of the candidate code is available for allocation. If the parent code is available for allocation (an alternative YES at step 406), i.e. all descendant codes of the parent code are available for allocation, the candidate code is added to list C at step 407. If the parent code
20 is not available for allocation (an alternative NO at step 406), implying that the sibling code (the code having the same parent code as the candidate code) of the candidate code is also not available for allocation, analysis of the candidate code proceeds at step 408.
25 At step 408 the estimated time of release for the requested channel resource is compared to an estimate for when the parent code of the candidate code will become available for allocation. If the estimated time of release for the requested channel resource is before or the same as the estimated time for when the
30 parent code will become available for allocation (an alternative YES at step 408), the candidate code is added to list A at step 409. Otherwise (an alternative NO at step 408), i.e. if the estimated time of release of the requested channel resource is
11

WO 2004/114565

PCTSE2003/001114

after the estimated time for when the parent code will become available, the candidate code is added to list B.
After either one of steps 407, 409 and 410 processing continues at step 411 , where a check is made whether all candidate codes
5 have been analysed. If there remain candidate codes that need to be analyzed (an alternative NO at step 411), processing continues at step 406 where analysis of one of the remaining candidate codes is initiated. If all candidate codes have been analyzed (an alternative YES at step 411), all candidate codes will have been
10 entered on one of lists A, B and C and the candidate code considered to be most suitable for allocation is selected at step 412 from said lists. The selected candidate code is allocated at step 413 in response to the received channel request.
Step 412 is further elaborated in Fig. 4B. Upon entering step 15 412, list A and B will contain those candidates whose parent codes are already unavailable for allocation. List A will contain candidate codes whose parents are estimated to become available for allocation after (or at the same time as) the estimated release of the requested channel resource while list B will
20 contain candidate codes whose parents are estimated to become available for allocation before the estimated release of the requested channel resource. List C will contain those candidates whose parent codes are currently available for allocation.
At step 414 a check is made whether there are any candidate codes 25 in list A. If list A includes at least one candidate code (an alternative YES at step 414), the candidate code on list A whose parent code will first become available for allocation is selected as most suitable for allocation. Selecting a candidate code from list A for allocation implies that the estimated time 30' of the corresponding parent code becoming available for allocation will not be postponed while selecting the candidate code whose parent will first become available implies that allocation of similar duration is packed together, which is good since then
12

WO 2004/114565

PCT/SE2003/OOU14

channel resources will become available for allocation in "chunks", freeing up larger areas of the code tree at once.
If list A is empty (an alternative NO) at step 414, a check is made at step 416 whether there are any candidate codes in List B.
5 If list B includes at least one candidate code (an alternative YES at step 416), the candidate code on list B whose parent code will last become available for allocation is selected as most suitable for allocation. Selecting a candidate code from list B for allocation implies that the estimated time of the
10 correspoding parent code becoming available for allocation will be postponed somewhat, while selecting the candidate code whose parent will last become available minimizes said postponement.
Finally, if list B also is empty (an alternative NO at step 416), a candidate code is selected from list C. Selecting a candidate
15 code from list C for allocation implies that the corresponding parent code will become unavailable for allocation.
Since selecting a candidate code for allocation from list A or B involves considering how the estimated time of release of the requested channel resource relates to the estimated time of
20 parent codes of said candidate codes becoming available for allocation, the candidate codes are Preferably sorted upon entry on list A and B respectively based on the estimated time of the respective parent code becoming available for allocation. Preferably lists A and B are sorted such that upon entering step
25 412, the first candidate code on list A and list B respectively are the candidate codes that would be selected from said lists, i.e. the first candidate code on list A is the candidate code whose parent code is estimated to be the first parent code that becomes available after, or Preferably at the same time as, the
30 requested channel resource is released, while the first candidate code on list B is the candidate code whose parent code will be the last parent code that becomes available before release of the requested channel resource.
13

WO 2004/114565

PCT/SE2003/00114

Lists A, B and C are used to organize the available channel resources, i.e. candidate codes, into different subsets in order to manage the selection process.
On a first level, the candidate codes are divided into a first 5 subset including candidate codes (lower level channel resources) associated with parent codes (higher level channel resources) currently available for allocation, and a second subset including candidate codes associated with parent codes currently unavailable for allocation. The first subset of candidate codes
10 is represented by list C while the second subset of candidate codes is represented by the union of lists A and B.
The second subset of candidate codes is further divided into a third subset including candidate codes associated with parent codes which are estimated to become available for allocation at
15 the same time or after the estimated release of the requested channel resource and a fourth subset including candidated codes associated with parent codes which are estimated to become available for allocation before the estimated release of the requested channel resource. The third subset of candidate codes
20 is represented by list A while the fourth subset of candidate codes is represented by list B.
Thus, according to the rule for allocating channel resources (OVSF codes) illustrated above, allocation of a candidate code whose parent code already is unavailable for allocation is
25 preferred over allocating a code whose parent is available for allocation. Of those candidate codes whose parent codes already are unavailable for allocation, allocation of a code whose parent code is estimated to become available for allocation after or at the same time as the estimated release of the requested channel
30 resource is preferred over allocating a code whose parent is estimated to be released before the estimated release of the requested channel resource. Finally, if after considering the criterias above more than one candidate code appears suitable for selection, the code whose parent is estimated to become available
14

WO 2004/114565

PCT/SE2003/001114

for allocation closest in time to the estimated release of the requested channel resource is selected for allocation.
Fig. 5 illustrates an exemplary data structure for representing the OVSF code tree of Fig. 2. The data strucuture comprises an 5 array of records representing the OVSF codes. The records have index 1 to n, where n is the total number of OVSF codes in the OVSF code tree. Each record, representing a single OVSF code, includes the following fields:
Parent code ref 501:
10 The index of the codes parent code. The code at the root of the tree has no parent code, which is represented by a reserved nil-value (e.g. zero).
Spreading factor 502:
The spreading factor of the OVSF code
15 Status 503:
Indicates whether the OVSF code is allocated/not allocated.
Estimated time of release 504:
Indicates the estimated time of release when the code is allocated.
20 Code 505:
The OVSF code number represented by the record.
Each time a OVSF code needs to be allocated, the array of records illustrated in Fig. 5 is traversed in search for candidate codes available for allocation, and the index of available candidate
25 codes, together with estimates for when the corresponding parent codes will become available for allocation, are registered in temporary data structures representing lists A, B and C (not shown in Fig. 5) . The estimate for when a parent code of a candidate code will become available for allocation corresponds
30 to the longest time any one of the parent codes descendant codes is estimated to remain allocated.
15

WO 2004/114565

PCT/SE2003/001114

Apart from the above disclosed exemplary first embodiment of the invention, there are several ways of providing rearrangements, modifications and substitutions of the first embodiment resulting in additional embodiments of the invention.
5 There are many possible alternative ways of providing estimates of how long channel resources are needed. According to the exemplary first embodiment of the invention disclosed above, the estimated time of release of channel resources is based on a duration parameter provide by an application when establishing a
10 communication session with a certain mobile station. Alternatively an application could indicate an amount of data to be transferred (e.g. the size of a picture, MMS message or file to be tranferred), allowing the estimated time of release of channel resources to be determined based on said amount of data
15 and the available (or by the application requested) bandwith. Yet other alternatives would be to provide said estimates based on statistical data on how long the channel resources are required by different applications, users and/or communication sessions established with a certain set of QoS-parameters.
20 Different rules can be defined for how channel resources are allocated while considering the estimated time of release of the requested channel resource and previosly allocated channel resources. Thus, one example of an alternative to the rule applied in the first exemplary embodiment disclosed above, would
25 be to divide the available candidate codes into candidate codes associated with parent codes which are curently available for allocation and candidate codes associated with parent codes which are currently unavailable for allocation, and then, among the candidate codes in the latter subset (i.e. available candidate
30 codes associated with parent codes currently not available for allocation) select a candidate code associated with a parent code whose estimated time of becoming available for allocation is closest to the estimated time of release of the requested channel resource (regardless of whether said parent code will become

WO 2004/114565

PCT/SE2003/00U14

available before or after said estimated release of the requested channel resource).
An allocated channel resource (e.g. an OVSF code) may be released before an established communication session (e.g. a multimedia
5 session) with a particular mobile station is terminated; thus requiring allocation of a new channel resource for supporting the remaining part of the communication session. This may occur e.g. as a result of handover from a first cell to a second cell/ requiring allocation of a new channel resource in the second cell
10 and release of the channel resource originally allocated in the first cell (note that when using soft handover, the channel resource in the first cell may be retained at least for a while). It may also occur e.g. as a result of code reallocation in a cell in order to achieve better resource usage in the cell. An
15 estimate for when the new channel resource will be released may then be based on the remaining time until the estimated release of the originally allocated channel resource. Allocation of the new channel resource may then proceed according to the invention based on said estimate for when the new channel resource will be
20 released.
It is also possible to allow estimates for when channel resources will become available to be subsequently updated (extended or shortened).
Even though the invention in its first exemplary embodiment has 25 been applied in a 3GPP UMTS system, the invention may of course be applied in other radio communication systems as well and in particular in communciation systems where channel resource are hierarchically organized such that allocation of a certain channel resource also affects the availability for allocation of
30 other channel resources. Another example of a system having hierarchically organized channel resources is CDMA2000 which similar to UMTS uses channel resources in the form of different length Walsh codes. Yet another example of a system utilizing hierarchically organized resources is TIA/EIA-136 (DAMPS). By
17

WO 2004/114565

PCT/SE2003/001114

utilizing the present invention in a TIA/EIA-136 system, where channel resources are provided in the form of carrier frequencies and time slots on said carrier frequencies/ it is possible to implement an Adaptive Channel Allocation (ACA) scheme wherein the
5 number of carrier frequencies in active use for communication in a cell can be minimized by packing allocations of similar duration on the same carrier frequency.
ABBREVIATIONS
10 ACA Adaptive Channel Allocation
BSC Base Station controller
CDMA Code Division Multiple Access
DAMPS Digital Advanced Mobile Phone System
EIA Electrical Industries Associates
15 GPRS General Packet Radio Service
GSM Global System for Mobile communication MS Mobile Station
MSC Mobile services Switching Centre
OVSF Orthogonal Variable Spreading Factor
20 QoS Quality of Service
RBS Radio Base Station
RNC Radio Network Controller
RRM Radio resource Management
SF Spreading Factor
25 TIA Telecommunications Industry Association SGSN Serving GPRS Support Node
UE User Equipment
UMTS Universal Mobile Telecommunication System UTRAN UMTS Terrestrial Radio Access Network 30 WCDMA Wideband CDMA
3GPP 3rd Generation Partnership Project
19
WO 2004/114565

PCT/SE/2003/00114

CLAIMS
1. A method for allocating channel resources in a radio communication system (SYS1), the method comprising:
receiving (301) a request for allocation of a channel resource;
5 allocating (302) a specific channel resource (C11-C88) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released.
10 2. A method according to claim 1, wherein said radio communication system is a Code Division Multiple Access based system and said channel resources are spreading codes.
3. A method according to claim 2, wherein said spreading codes are Orthogonal Variable Spreading Factor codes (C11-C88).
15 4. A method according to any one of claims 2-3, wherein said
channel resources include at least two higher level channel
resources (C41, C42), said higher level channel resources being
associated with at least two lower level channel resources each
(C81-C82, C83-C84) such that a higher level channel resource
20 (C41) is available for allocation only when all lower level channel resources (C81-C82) associated with said higher level channel resource also are available for allocation, said lower level channel resources having higher spreading factors than said higher level channel resources.
25 5, A method according to claim 1, wherein said channel resources are hierarchically organized and include at least two higher level channel resources, said higher level channel resources being associated with at least two lower level channel resources each such that a higher level channel resource is available for
30 allocation only when all lower level channel resources associated

WO 2004/114565

PCT/SE/2003/001114

with said higher level channel resource also are available for
allocation.
6. A method according to any one of claims 4-5, wherein according
to said predetermined rule,
5 if at least two lower level channel resources are available candidates for allocating as said specific channel resource,
and if said available candidates include both a first and a second subset of lower level channel resources, wherein said first and second subsets include at least one lower level channel
10 resource each, and each lower level channel resource in said first subset is associated with a higher level channel resource which is currently available for allocation while each lower level channel resource in said second subset is associated with a higher level channel resource which is currently not available
15 for allocation,
a lower level channel resource in said second subset is selected as said specific channel resource.
7. A method according to claim 6, wherein according to said
predetermined rule, if said second subset includes at least two
20 lower level channel resources, said predetermined rule includes comparing estimates for when the higher level channel resources associated with the lower level channel resources in said second subset will become available for allocation with the estimate of when said specific channel resource will be released.
25 8. A method according to claim 7, wherein according to said predetermined rule, if said second subset includes both a third and a fourth subset, wherein said third and fourth subsets include at least one lower level channel resource each, and each lower level channel resource in said third subset is associated
30 with a higher level channel resource which is estimated to become available at the same time or after the estimated release of said specific channel resource while each lower level channel resource
20

WO 2004/114565

PCT/SE/2003/001114

in said fourth subset is associated with a higher level channel resource which is estimated to become available before the estimated release of said specific channel resource,
a lower level channel resource in said third subset is selected 5 as said specific channel resource.
9. A method according to claim 8, wherein according to said predetermined rule, if said third subset includes at least two lower level channel resources,
10 a lower level channel resource in said third subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the estimated time of release of said specific channel resource, is selected as said specific channel resource.
15 10. A method according to claim 7, wherein according to said predetermined rule, a lower level channel resource in said second subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the estimated time of release of said specific channel
20 resource, is selected as said specific channel resource.
11. An apparatus (RH1) for allocating channel resources in a radio communication system, said apparatus comprising:
electronic circuitry for receiving a request for allocation of a 25 channel resource;
electronic circuitry for allocating a first channel resource according to a predetermined rule which includes considering an estimate of when said first channel resource will be released and estimates of when other previously allocated channel resources
30 will be released.
21
WO 2004/114565

PCT/SE2003/001114

12. An apparatus according to claim 11, wherein said radio
communication system is a Code Division Multiple Access based
system and said channel resources are spreading codes.
13. An apparatus according to claim 12, wherein said spreading
5 codes are Orthogonal Variable Spreading Factor codes (C11-C88).
14. An apparatus according to any one of claims 12-13, wherein
said channel resources include at least two higher level channel
resources (C41, C42), said higher level channel resources being
associated with at least two lower level channel resources each
10 (C81-C82, C83-C84) such that a higher level channel resource (C41) is available for allocation only when all lower level channel resources (C81-C82) associated with said higher level channel resource also are available for allocation, said lower level channel resources having higher spreading factors than said
15 higher level channel resources.
15. An apparatus according to claim 11, wherein said channel
resources are hierarchically organized and include at least two
higher level channel resources, said higher level channel
resources being associated with at least two lower level channel
20 resources each such that a higher level channel resource is
available for allocation only when all lower level channel
resources associated with said higher level channel resource also
are available for allocation.
16. An apparatus according to any one of claims 14-15, wherein
25 according to said predetermined rule,
if at least two lower level channel resources are available candidates for allocating as said specific channel resource,
and if said available candidates include both a first and a second subset of lower level channel resources, wherein said
30 first and second subsets include at least one lower level channel resource each, and each lower level channel resource in said first subset is associated with a higher level channel resource

22

WO 2004/114565

PCT/SE2003/001114

which is currently available for allocation while each lower level channel resource in said second subset is associated with a higher level channel resource which is currently not available for allocation,
5 a lower level channel resource in said second subset is selected as said specific channel resource.
17. An apparatus according to claim 16, wherein according to said
predetermined rule, if said second subset includes at least two
lower level channel resources, said predetermined rule includes
10 comparing estimates for when the higher level channel resources associated with the lower level channel resources in said second subset will become available for allocation with the estimate of when said specific channel resource will be released.
18. An apparatus according to claim 17, wherein according to said
15 predetermined rule, if said second subset includes both a third
and a fourth subset, wherein said third and fourth subsets include at least one lower level channel resource each, and each lower level channel resource in said third subset is associated with a higher level channel resource which is estimated to become
20 available at the same time or after the estimated release of said specific channel resource while each lower level channel resource in said fourth subset is associated with a higher level .channel resource which is estimated to become available before the estimated release of said specific channel resource,
25 a lower level channel resource in said third subset is selected as said specific channel resource.
19. An apparatus according to claim 18, wherein according to said
predetermined rule, if said third subset includes at least two
lower level channel resources,
30 a lower level channel resource in said third subset which is associated with a higher level channel resource whose estimated time of becoming available for allocation is closest to the
23

WO 2004/114565

PCT/SE2003/001114

estimated time of release of said specific channel resource, is selected as said specific channel resource.
20. An apparatus according to claim 17, wherein according to said
predetermined rule, a lower level channel resource in said second
subset which is associated with a higher level channel resource
whose estimated time of becoming available for allocation is
closest to the estimated time of release of said specific channel
resource, is selected as said specific channel resource.
21. A radio network controller node for use in a radio
communication system including an apparatus according to any one
of claims 11-20.
22. A radio access network including an apparatus according to
any one of claims 11-20.
23. A method for allocating channel resources in a radio communication system
(SYS1), an apparatus (RH1) for the same and a radio network controller node for use in a
radio communication system substantially as herein described with reference to the
accompanying drawings.
Dated this 10th day of November, 2005
(RAVI BHOLA)
Of K & S PARTNERS
AGENT FOR THE APPLICANT(S)
24

ABSTRACT
"METHOD AND ARRANGEMENT IN A COMMUNICATION SYSTEM"
The present invention is related to a method and apparatus for resource allocation in a communication system as well as a radio network control node ad a radio access network including such an apparatus. A request for allocation of a channel resource is received (301). In response, a specific channel resource is allocated (302) according to a predetermined rule which includes considering an estimate of when said specific channel resource will be released and estimates of when other previously allocated channel resources will be released.
-25-

Documents:

1268-mumnp-2005-abstract(19-1-2009).doc

1268-MUMNP-2005-ABSTRACT(19-1-2009).pdf

1268-mumnp-2005-abstract.doc

1268-mumnp-2005-abstract.pdf

1268-MUMNP-2005-CANCELLED PAGES(19-1-2009).pdf

1268-MUMNP-2005-CLAIMS(19-1-2009).pdf

1268-mumnp-2005-claims(granted)-(19-1-2009).doc

1268-mumnp-2005-claims(granted)-(19-1-2009).pdf

1268-mumnp-2005-claims.doc

1268-mumnp-2005-claims.pdf

1268-MUMNP-2005-CORRESPONDENCE(19-1-2009).pdf

1268-mumnp-2005-correspondence(ipo)-(6-2-2009).pdf

1268-mumnp-2005-correspondence-received-ver-101105.pdf

1268-mumnp-2005-correspondence-received-ver-121205.pdf

1268-mumnp-2005-correspondence-received.pdf

1268-mumnp-2005-description (complete).pdf

1268-MUMNP-2005-DESCRIPTION(COMPLETE)-(19-1-2009).pdf

1268-MUMNP-2005-DRAWING(19-1-2009).pdf

1268-mumnp-2005-drawings.pdf

1268-MUMNP-2005-FORM 1(19-1-2009).pdf

1268-mumnp-2005-form 1(28-11-2005).pdf

1268-mumnp-2005-form 18(26-6-2006).pdf

1268-mumnp-2005-form 2(19-1-2009).pdf

1268-mumnp-2005-form 2(granted)-(19-1-2009).doc

1268-mumnp-2005-form 2(granted)-(19-1-2009).pdf

1268-MUMNP-2005-FORM 2(TITLE PAGE)-(19-1-2009).pdf

1268-mumnp-2005-form 26(16-8-2005).pdf

1268-MUMNP-2005-FORM 26(19-1-2009).pdf

1268-mumnp-2005-form 3(10-11-2005).pdf

1268-MUMNP-2005-FORM 3(19-1-2009).pdf

1268-mumnp-2005-form 3(2-2-2006).pdf

1268-mumnp-2005-form 5(10-11-2005).pdf

1268-MUMNP-2005-FORM 5(19-1-2009).pdf

1268-mumnp-2005-form-1.pdf

1268-mumnp-2005-form-2.doc

1268-mumnp-2005-form-2.pdf

1268-mumnp-2005-form-3.pdf

1268-mumnp-2005-form-5.pdf

1268-mumnp-2005-form-pct-ipea-409.pdf

1268-mumnp-2005-form-pct-isa-210(14-11-2005).pdf

1268-MUMNP-2005-OTHER DOCUMENT(19-1-2009).pdf

1268-mumnp-2005-pct-search report.pdf

1268-mumnp-2005-petition of under rule 137(19-1-2009).pdf

1268-MUMNP-2005-PETITION UNDER RULE 137(19-1-2009).pdf

abstract1.jpg

« Previous Patent

Next Patent »

Patent Number

228678

Indian Patent Application Number

1268/MUMNP/2005

PG Journal Number

10/2009

Publication Date

06-Mar-2009

Grant Date

06-Feb-2009

Date of Filing

14-Nov-2005

Name of Patentee

TELEFONAKTIEBOLAGET LM ERICSSON (PUBL)

Applicant Address

164 83 Stockholm,

Inventors:

#	Inventor's Name	Inventor's Address
1	LINDSKOG,JAN	Radavagen 54, S-435 43 Pixbo,
2	RYDNELL, GUNNAR	Silleskarsgatan 47, S-421 59 Vastra Frolunda, Sweden

PCT International Classification Number

H04J 11/00,

PCT International Application Number

PCT/SE2003/001114

PCT International Filing date

2003-06-26

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA