Multiplex communications – Channel assignment techniques – Polling
Reexamination Certificate
1998-04-29
2001-12-25
Ton, Dang (Department: 2661)
Multiplex communications
Channel assignment techniques
Polling
C370S252000, C370S270000, C370S462000
Reexamination Certificate
active
06333936
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 reorganized using the data structure.
The method of the present invention is general with respect to the number of lower level resource units that together forms a 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 fully 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.
Therefore, it is an object of the present invention to overcome this kind of inefficiency by providing a resource pool structure including a data structure reflecting the free resources in the pool and that permits organized and efficient but still flexible allocation and de-allocation of resources.
It is a further object of the present invention to ensure that resource units are evenly utilized in a resource pool.
It is another object of the present invention to selectively re-allocate resources among the resource users to free other resources that can be used to form higher level resource blocks in order to meet a particular resource demand or to simply make available higher level resource blocks.
It is another object of the present invention to determine and implement a resource pool structure data structure, mirroring the free resources in the resource pool, that best suits current resource demands.
The present invention configures a pool of resource units using a logical structure that includes first level and second level resource blocks. The terms “configure resources” or “configuration of resources” refer to a data structure which is organized to reflect or represent actual or physical resources. However, the actual resources themselves are not necessarily configured in a resource hierarchy like that shown in FIG.
1
. Each first level resource block corresponds to an individual resource unit, where an individual resource unit is the smallest resource that a resource handler allocates from the resource pool. The first level resource blocks are provided in groups that form a lowest level of the resource pool structure. Each second level resource block corresponds to one of the groups of the first level resource blocks. For example, two first level resource blocks form a first level resource block group logically linked to a second level resource block. The second level resource blocks are provided in groups and form a next higher level of the resource pool structure.
Resources are allocated from the resource unit pool in an efficient manner. For example, if a request is made for a first level resource block, an available first level resource block is allocated from a partially-allocated, first level resource group where one or more first level resource blocks are currentl
Andersson Christoffer
Johansson Peter
Johansson Staffan E.
Jönsson Nils T. E.
Rynbäck Patrik J. E.
Hom Shick
Nixon & Vanderhye P.C.
Telefonaktiebolaget LM Ericsson (publ)
Ton Dang
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-2593191