Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
1998-08-28
2002-10-15
Olms, Douglas (Department: 2661)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S320000, C370S342000, C370S395300, C370S457000, C370S465000
Reexamination Certificate
active
06466559
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to allocating resources in general, and more particularly, to allocating various data, signal, and/or communications processing resources.
BACKGROUND AND SUMMARY OF THE INVENTION
In certain environments, data, signal, and communication processing resources may be dedicated for use by particular hardware elements, software elements (e.g., application programs), and human operators, each of which may be generally viewed as a “resource user.” While such resource dedication is convenient and also ensures that the necessary or otherwise appropriate resources are available whenever the resource user requests them, this one-to-one, dedicated relationship between a resource and a resource user is inefficient. This inefficiency is primarily due to the fact that dedicated resources are most often underutilized since the resource user typically uses its dedicated resource less than 100% of the time.
The present invention employs a more efficient resource allocation approach in which resources are pooled and allocated on an “as needed” basis. In other words, in response to a resource request, a resource (if available) is “withdrawn” from a pool of resources and provided to the requesting resource user. When the resource user is finished using that resource, it is returned to the resource pool. Efficiency is increased because (1) the number of resource users may be considerably larger than the number of resources in the pool and (2) resources are removed from the pool only when they are actually used.
In order for a pooled resource system to work smoothly, the allocation and return of resources from and to the resource pool needs to be managed in an effective and efficient manner. Efficient management is more challenging when the pool of resources as well as the resource requests are not all the same. For instance, one resource request may be for a relatively small resource while another resource request might be for a relatively large resource. Moreover, resource requests may also differ in parameters other than size.
The present invention resolves these issues in part by imposing a structure on the resource pool including specific rules regarding how resources are to be allocated from the pool. Those rules may vary depending on the end application that requests and uses the resources. One example (but non-limiting) structure is the resource hierarchy shown in FIG.
1
. The hierarchy includes a plurality of levels or tiers with each level having plural nodes representing a resource block at that level. The data structure is organized in such a way that it “mirrors” the physical resources in terms of how those physical resources are linked or grouped. The physical resources are configured, reconfigured, allocated, de-allocated, organized, and re-organized using the data structure.
In general, a number of lower level resource units are grouped to form a corresponding, higher level resource unit. Level
1
resource blocks correspond as shown in
FIG. 1
to one data processing resource unit, where a resource unit may comprise hardware and/or software. Each level
2
resource block corresponds to a group (in this example two) of consecutive level
1
resource blocks. Similarly, each level
3
resource block of the resource hierarchy corresponds to a group of consecutive level
2
resource blocks.
Thus, if a resource request requires four data processing resource units, a single level
3
resource block would be allocated to that request. A level
3
resource block corresponds, in this example, to two level
2
resource blocks which in turn corresponds to four level
1
resource blocks equivalent to the four data processing resource units.
While resources may be allocated from and returned to such a hierarchical structure in random fashion, such an approach may ultimately lead to inefficiencies. In particular, the initial, ordered structure of the resource hierarchy may become fragmented after several resource block allocations and returns. Unfortunately, because of the fragmentation, resource blocks at certain levels cannot be filly utilized. For example,
FIG. 2
shows the resource hierarchy of
FIG. 1
with a fragmented resource allocation configuration. Circled resource blocks correspond to a currently allocated resource block, and a square enclosing a resource block represents a currently-available resource block. Because level
1
resource block
14
is currently allocated, level
2
resource block
16
, logically linked to both level
1
resource blocks
14
and
15
, cannot be allocated. A “domino effect” occurs—since level
3
resource block
17
is linked to resource blocks
16
and
18
, level
3
resource block
17
cannot be currently allocated even if level
2
resource block
18
were currently available.
On the other hand, if the currently-allocated resource block
19
had been allocated from currently-available resource block
15
, the level resource block
18
would have been available for allocation. Similarly, if currently-allocated, level
1
resource block
21
was not allocated, and instead the currently-available level
1
resource block
23
was assigned to the resource request, the currently-unavailable level
2
resource block
21
would be available. The level
2
resource block
21
could then be combined with the level
2
resource block
25
to make available the level
3
resource block
26
. Accordingly, as a result of fragmented/inefficient resource allocation at lower levels in the hierarchy, it may be difficult to provide a higher level resource block to a resource request even though there are sufficient, available resources in the resource pool to accommodate the higher level resource request.
In a pooled resource system where resources are allocated according to a particular strategy, different types or groups of pooled resources will likely have different resource allocation structures or algorithms. If more than one type of resource is required to satisfy individual service requests, coordinating the allocation of both types of resources using two or more resource structures and/or algorithms becomes complicated and inefficient.
Consider the following example in a Code Division Multiple Access (CDMA) communications system. In order for a user to transmit information, the user must be allocated a spreading code (a software resource) corresponding to a particular channel capacity. Certain spreading codes have a smaller capacity. Other spreading codes in a spreading code resource hierarchy or tree may correspond to plural ones of smaller spreading code resources. As a result, a higher capacity, spreading code parent can only be allocated if its corresponding lower capacity, spreading code children are all available. If one of those spreading code children is already allocated, the higher capacity channel spreading code parent cannot be allocated.
In addition to a software spreading code resource, a user must be allocated the necessary hardware resource to physically perform the communication. An example of such hardware includes Digital Signal Processing (DSP) and/or radio transceiver circuitry. For example, a lowest capacity channel might use only one DSP and/or transceiver hardware unit. On the other hand, a higher capacity channel may require more than one DSP and/or transceiver hardware unit. Similarly, the higher capacity parent can only be allocated if all its supporting children are available. The fact that two different resource hierarchies, (i.e., software and hardware resources) in the above example, must be navigated makes the provision of an appropriate capacity spreading code with appropriate capacity hardware resources particularly cumbersome and inefficient. Not only are two resource allocation strategies required for each pool of resources, there is no guarantee that just because a suitable resource is available from one pool that a corresponding and necessary resource from the other pool is also available.
It is an object of the present invention to overcome inefficiency by providing a r
Andersson Christoffer
Johansson Peter
Johansson Staffan E.
Jonsson Nils T. E.
RynbÅck Patrik J. E.
Hom Shick
Nixon & Vanderhye P.C.
Olms Douglas
Telefonaktiebolat LM Ericsson (publ)
LandOfFree
Method and apparatus for allocating processing resources does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for allocating processing resources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for allocating processing resources will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2998584