Title of Invention

METHOD FOR PERSISTENCE-VECTOR-BASED MODIFICATION OF USAGE RATES

Abstract

When a resource of limited capacity is shared by several users, it is possible for the usage rates of the users to exceed the resource's capacity, thereby causing an overload condition. In a system or method according to an embodiment of the invention, at least some of the users have a set of persistence vectors. When an overload condition is detected, the usage rate of at least one of these users is changed, at least in part according to the user's set of persistence vectors.

Full Text

SYSTEM AND METHOD FOR PERSISTENCE-VECTOR-BASED MODIFICATION OF USAGE RATES BACKGROUND OF THE INVENTION Field of the Invention This invention relates to distribution of the use of a limited resource among multiple users. More specifically, this invention relates to the modification of usage rates according to a set of persistence vectors. Description of Related Art and General Background A shared resource is one which may be used by multiple users. Shared resources which have limited availabilities or capacities include such diverse examples as electric power stations and other energy plants, water sources such as reservoirs and flowing bodies, supply systems for the distribution of goods and/or materiel, and data communications networks and pathways. Problems associated with allocating the use of a shared resource among multiple users may therefore arise in many different contexts. Regardless of the particular context, however, such resources may be found in many systems in which at least the following conditions hold: • the capacity or availability of the shared resource may be expressed in terms of a finite rate R of units per measure of time (i.e. kilowatts/hour, gallons/minute, canons/week, or bits/second); • at any particular time, the resource is being used by n different users, where n is a nonnegative integer; and • at any particuiar time, the usage of the i-th user (where 1 A basic model for such a system is shown in FIG. I, where resource 100 is used by users 120a-d at rates 110a-d, respectively. Depending on the particular implementation, the rate R which characterizes the shared resource may indicate an actual or estimated limit of the capacity of the resource (e.g. in the case of a communications pathway) or, in the alternative, the rate R may be a threshold indicating a maximum safe or permissible load of the resource (e.g. in the case of a power generation facility or device). Likewise, the usage rates ui may indicate actual use, expected use, or requests or demands for use. An overload condition arises when the sum of the n usage rates ui at any one time exceeds the value R. With respect to a power plant, for example, an overload condition may arise when the total current draw exceeds the rated capacity. With respect to a data communications pathway, an overload condition may arise when the total data transfer rate exceeds the pathway's actual capacity, thereby corrupting the data in transmission. In certain situations such as water supply or warehousing of materials, an overload condition may also indicate that although user demands are currently being met, reserve or buffer capacity is being depleted. Depending on the nature of the resource, the consequences of an overload condition will vary, possibly including the need for an offline period for resource recovery (e.g. cooling of an power generation system or replenishment of a reservoir) or the need to expend present capacity in order to repeat a use that was attempted in the past but failed because of the overload (e.g. retransmission of a data packet corrupted by a collision). The resource may even become temporarily or permanently unable to regain its former capacity. In any case, it is generally desirable to avoid overload conditions whenever possible. due to a resource overload or to the failure of another component in the supply path. Moreover, in certain applications such as wireless data communications, it is possible that no feedback mechanism exists whereby a user may obtain timely notification of an overload. Therefore, the user may continue to use the resource, unaware of the problem. In such a situation, it is desirable for the system to include a capability for notifying the users of the overload condition \ia, e.g., a warning signal. FIG. 2 shows an example of such a system, wherein control unit 230 receives information related to usage of resource 200 by users 220a-d and sends feedback information such as a warning signal to users 220a-d over respective communications pathways 240a-d. Note that it is possible for control unit 230 to be implemented as a part of resource 200 or alternatively as a part of one of the users 220a-d. If a user becomes aware of an overload condition, then the possibility exists for user-driven remediation. In this case, if at least some of the users are able to communicate with each other, then a solution such as a reduction in usage rate may be negotiated. In many instances, however, such communication between users may be unavailable, impractical, or otherwise undesirable, in which case an alternate control mechanism may be provided for controlling usage of the resource. This alternate control mechanism may be centralized and/or decentralized. If complete knowledge of the future usage requirements of the users were available, then it would be theoretically possible to construct an optimal usage schedule that would satisfy the users' requirements as much as possible while completely avoiding all overload conditions. In many practical systems, however, a user's future needs will be unknown even to the user itself. One way to prevent overload conditions in such systems would be on the basis of current usage requirements: for example, by granting usage rate allocations to users only on a request basis. In order to convey usage requests from the users back to the control unit, however, such a scheme would require an upstream communication pathway which may not otherwise be necessary. Moreover, additional costs and delays are incurred in receiving, processing and responding to such requests. In order to avoid some of the disadvantages of a request/grant scheme, a decentralized system may be designed wherein control is shared with the users. The control unit in such a system concentrates on the prediction and avoidance of overload conditions while issuing enough feedback information to allow the users to control their own usage to some extent. A method according to an embodiment of the invention may be implemented in any system that fits the model of FIG. 1 wherein the users may obtain notification of an overload condition (as in the modified system of FIG. 2). An exemplary application of such a system is shown in FIG. 3 wherein users 320a-d are data producers, resource 300 is a common transmission channel linking the producers with data consumer 350, and control unit 330 receives usage information from the consumer. The producers use resource 300 by transmitting data to consumer 350 at or below rates 310a"-d, respectively, and they receive respective signals 340a-d (which may include feedback and/or other control information) from the control unit. One possible implementation of the exemplary application is the reverse link of a CDMA telecommunications system. In this case, each producer may comprise 1) a transmitter, such as a mobile telephone or a WLL (wireless local loop) station, connected to 2) a data-producing device, such as a laptop computer or a point-of-sale terminal, through a PCMCIA card or a similar interface, and outputting data encapsulated in packets over IP or any other suitable protocol. Consumer 350 and control unit 330 may be parts of a base station, and control signals 340 may be carried Note that the usage rate rj may indicate a maximum allowable rate. i.e. a permission rather than a requirement to use the resource at the given rate. The actual rate at which the user uses the resource may depend upon other factors in addition to the usage rate, such as a user's current need and/or ability to use the resource. Likewise, note that the actual rate at which the user uses the resource need not be a member of the set of available rates. In one particular implementation, each user has the same fixed set of available rates, wherein each rate is expressed in kilobits per second (Kb/s) and the set of rates is designed to increment in powers of two. Because a doubling in rate requires a doubling in power to maintain the same ratio of energy per bit to noise power spectral density (Eb/No), each rate step thus corresponds to a power step of 3 dB. The available rate values in this example include 4.8, 9.6, 19.2, 38.4, 76,8, 153.6, and 307.2 Kb/s. In addition to a usage rate, each user also has a set of persistence vectors, although it is possible to have other users in the system that lack a set of persistence vectors. The length of each such vector may be any integer greater than zero, and each vector element corresponds to one among the set of available rates and represents a probability that the usage rate will be the corresponding one among the set of available rates. In the exemplary application, each vector element is a persistence value which represents a probability from 0 to L The set of persistence vectors may be unique to each user, or the same set may be assigned to all users in a particular class, or the same set may be assigned to all of the users in the system. Likewise, the set of persistence vectors may be a permanent aspect of the operation of the user, or it may be issued by control unit 230, in which case it may be updated periodically or otherwise. Other relevant aspects of persistence vector distribution and use are discussed in the co-pending Application No. 09/XXX,XXX entitled "METHOD AND APPARATUS FOR PERSISTENCE-VECTOR-BASED RATE ASSIGNMENT". the disclosure of which application is incorporated by reference above. In this method, the user's set of persistence vectors includes an (m-l)-element vector P, wherein P = {Pk such that 1 In block 410, the user receives a warning signal from control unit 230. This warning signal may issue, for example, when an actual or impending overload condition is detected, and it may be sent to all users or only to a subset of the users (e.g. only to the users who have persistence vectors). Various embodiments and applications of a system wherein the warning signal is indicated by a busy bit in a reverse hnk signal are described in co-pending Application No, 09/346,882 entitled "METHOD AND APPARATUS FOR SIGNAL COMBINING IN A HIGH DATA RATE COMMUNICATION SYSTEM," filed July 2, 1999 and assigned to the assignee of the present invention. Upon receiving the warning signal, the user generates a random number x as indicated in block 420. The range and distribution of x are limited only by the particular implementation; in an exemplary application, x represents a value drawn from a set havins a uniform distribution over the range 0 to 1. In block 430, the value Numerous variations of the method described above may be used in applications of this embodiment. For example, the users may share the same set of persistence vectors, or different sets of persistence vectors may be assigned to allow the implementation of a priority scheme among the users. In another variation, the first element of each persistence vector may be eliminated (or set to represent a probability of 1) so that users already having the lowest usage rate will not suffer a further rate reduction. Likewise, more than one among the first elements of the persistence vectors may be so treated to protect users of other low rates. Additional constraints on usage rate may exist as consequences of other aspects of the particular implementation. For example, the rale at which the user actually uses or accesses the shared resource may be limited by factors such as the user's present capacity or power. Therefore, it is possible that the user may use or may be permitted to use a rate lower than the usage rate granted by this or a similar method. It may be desirable to choose rate R (a capacity measure of the shared resource) to be a threshold value rather than the actual capacity of the shared resource so that the warning signal is generated before an overload condition occurs, thereby allowing the system to react to avoid the condition. In this case, the threshold R should be selected to take into account at least (1) the longest possible delay in system response, as characterized by the maximum time between generation of the warning signal and the consequent reduction in total resource usage, and (2) the maximum possible increase in resource usage during the period of such delay. A method according to a second embodiment of the invention is described in FIG. 5 with reference to FIG. 2. In contrast to the method described above, this method allows the user's usage rate to be reduced to any other rate in the set of available rates rather than to only one particular rate. As in the method described above, a user is configured to have a usage rate TJ from the user's set of available rates ri to rm (as noted in block 500) and an (m-l)- element persistence vector P which may be selected from a set according to, for example, the index j. In block 510, a warning signal is received from control unit 230, and in block 520 the user generates a random number x as described above. At this stage, the user also sets an index k to be equal to the index j. In block 530, the value of x is tested against the persistence value Pk, where Pk is the element of persistence vector P that corresponds to usage rate Uk- If the test fails (i.e. X is not less than Pk), then the index j is set to be equal to k in block 560, and the method ends in block 570 with the user being configured to have the usage rate rj. In this case, in other words, the user's usage rate is not affected by the overload condition. If the test in block 530 succeeds (i.e. x is less than Pk), then the value of the index k is tested. If k is already at its minimum value (i.e. one in this example), then the procedure continues to blocks 560 and 570 as above. Otherwise, the value of k is decremented (i.e. reduced by one) and the test is repeated. Under this method, when block 570 is finally reached, the user may be configured to have any usage rate in the set which is equal to or less than the usage rate indicated in block 500. Again, this method may be altered to allow the use of one among many other relations between the values of x and Pk in place of the test condition shown in block 530, depending on the particular characteristics of the values chosen for x and Pk. In a variation of this method as shown in FIG. 6, it is possible for the user to be denied usage of the shared resource. Block 540 is replaced with block 542, which allows the index k to reach a value of zero. When that event occurs, the user is programs loaded from or into data storage media as machine-readable code, such coae being instructions executable by arrays of logic elements such as microprocessors or other digital signal processing units. Thus, the present invention is not intended to be limited to the embodiments shown above but rather is to be accorded the widest scope consistent with the principles and novel features disclosed in any fashion herein. What is claimed is: WE CLAIM : 1. A method for persistence-vector-based modification of user rates in a system comprising a resource having a capacity measure and a user having a usage rate and a persistence vector, said method comprising the steps of: determining a use of the resource by the user based in part on the usage rate of the user; and changing the usage rate based in part on the persistence vector when a predetermined relation exists between a total resource usage rate and the capacity measure; wherein the total resource usage rate is the sum of usage rates of a plurality of users including said user; wherein the user has a set of available rates, the user's usage rate being a member of the user's set of available rates, wherein each element of the persistence vector corresponds to a member of the user's set of available rates, and wherein each element of the persistence vector indicates a probability that the user's usage rate will change to be equal to the corresponding member of the user's set of available rates. 2. The method according to claim 1, wherein each of the plurality of users has the same set of available rates. 3. The method according to claim 1, wherein the predetermined relation exists when the total resource usage rate is not less than the capacity measure. 4. The method according to claim 3, comprising the steps of determining the usage rate of the user based in part on a predetermined relation between a random number and a selected persistence value of the user's persistence vector. 5. The method according to claim 3, comprising the steps of changing the usage rate of the user based in part on a predetermined relation between a random number and a selected persistence value of the user's persistence vector, wherein the selected persistence value corresponds to the user's usage rate. 5. The method according to claim 3, comprising the steps of reducing the usage rate of the user based in part on a predetermined relation between a random number and a selected persistence value of the user's persistence vector, wherein the selected persistence value corresponds to the user's usage rate. 7. The method according to claim 6, wherein the random number has a uniform distribution. 8. The method according to claim 3, comprising the steps of sending a warning signal to the user when the predetermined relation exists. 9. The method according to claim 1, wherein the user comprises a data producer, and wherein the usage rate comprises a rate of data production. 10. The method according to claim 9, wherein the resource comprises a wireless channel for data communications, and wherein the use of the resource comprises transmitting data over the wireless channel. 11. The method according to claim 10, wherein a first available rate in the set of the available rates is substantially equal to double a second available rate in the set of the available rates. 12. The method according to claim 10, wherein the usage rate comprises a null usage rate. 13. The method according to claim 10, comprising the steps of modifying the persistence vector. 14. The method according to claim 10, wherein the capacity measure comprises a predetermined threshold, the predetermined threshold being lower than an actual capacity of the resource. 15. The method according to claim 14, wherein the predetermined threshold is determined based in part on the actual capacity of the resource, a minimum delay between sending a warning signal and obtaining a resulting reduction in usage of the resource, and a maximum increase in resource usage over a period of the minimum delay. 16. A system comprising a shared resource and a plurality of users to perform the methods as claimed in any one of the preceding claims. 17. A method for persistence-vector-based modification of usage rates, comprising: using a shared resource at a first usage rate from a set of usage rates; receiving a warning signal, said warning signal relating to use of the shared resource; generating a random number; comparing the random number to a selected persistence value of a persistence vector, the selected persistence vector corresponding to the first usage rate; selecting a second usage rate from the set of usage rates based on said comparing, and using the shared resource at the second usage rate. 18. The method according to claim 17, wherein the second usage rate is different from the first usage rate, if the random number is less than the selected persistence value. 19. The method according to claim 17, wherein the second usage rate is the same as the first usage rate, if the random number is greater or equal to the selected persistence value. 20. An apparatus capable of performing the method claimed in any one of claims 17 to 19.

Documents:

in-pct-2002-420-che-abstract.pdf

in-pct-2002-420-che-assignement.pdf

in-pct-2002-420-che-claims filed.pdf

in-pct-2002-420-che-claims granted.pdf

in-pct-2002-420-che-correspondnece-others.pdf

in-pct-2002-420-che-correspondnece-po.pdf

in-pct-2002-420-che-description(complete)filed.pdf

in-pct-2002-420-che-description(complete)granted.pdf

in-pct-2002-420-che-drawings.pdf

in-pct-2002-420-che-form 1.pdf

in-pct-2002-420-che-form 19.pdf

in-pct-2002-420-che-form 26.pdf

in-pct-2002-420-che-form 3.pdf

in-pct-2002-420-che-form 5.pdf

in-pct-2002-420-che-other documents.pdf

in-pct-2002-420-che-pct.pdf