HK1088167A - Grade of service and fairness policy for bandwidth reservation system - Google Patents

Description

Service level and fairness principle for bandwidth reservation systems

Background

The present invention relates generally to wireless communication systems, and more particularly to techniques for allocating communication resources among multiple users.

The widespread use of personal computers has created a need for the public to access the internet and other computer networks at low cost. Currently, such demands have expanded to connect portable devices, such as laptop computers, personal digital assistants, etc., to computer networks. Unfortunately, the internet wireless access market represents a convergence of two different cultures. Traditional internet cable access cultures desire a fixed rate of data access, for example, 56 kbits/sec to the internet, which is commonly achieved with voice-grade home telephone lines. However, this market desires that data transfer be non-metered, in other words, that users desire to transfer all of the data they wish to transfer, as long as the users pay an average per month. This type of access is quite different from the traditional wireless cellular telephone model that provides voice communication. Cellular telephone networks are characterized by the ability to provide high quality rate, fast access. However, the amount of communication is fixed, i.e., users of cellular phones are accustomed to paying per minute access fees.

Market research has shown that wireless users of the internet are unlikely to pay for the metered amount of access or usage cost per ten thousand bits. Conversely, the user wishes to have access to unlimited, or at least unlimited, amounts of data. Unfortunately, the basic architecture of a wireless system can only provide limited resources. For example, the wireless channels within a cell are limited. Thus, multiple users must somehow share access to these limited physical resources.

Summary of The Invention

Only certain types of internet communication are suitable for shared access. For example, web browsing functionality is often desirable for time sharing among a limited number of communication resources. I.e. the user's usual operation is to specify a certain web page and wish to download this web page at high speed. But then the user takes seconds, or even minutes, to view the contents of this page and think about what to do next, and then apply for another web page. Thus, when this user thinks about what is to be applied later, the network resources can be temporarily reallocated to other users.

Other applications, including internet communications, are not well suited for bandwidth sharing. For example, real-time radio broadcasting, executable file downloading, music file (MP3) downloading, etc. are very different from the web browsing function. In particular, users who need such content often occupy these resources for many seconds or minutes. For these streaming data type download functions, the user wants to be able to allocate bandwidth continuously.

Therefore, in a central control part such as a base station, available resources can be sorted and allocated to users according to the requirements of the users, for example, communication channels can be sorted and allocated. The ordering and allocation of resources proceeds smoothly as long as there are enough channels to meet the user's needs. However, if the amount of available resources exceeds the demand, the system must be set up on a fair basis so that users share these resources. This problem is multifaceted by not only deciding how many resources to allocate, but also which users to allocate and when to allocate these resources.

What is needed, therefore, is a way to implement resource sharing in a manner whereby the service degradation experienced by a particular user occurs in a proper manner and fairly such that users requiring more access over a period of time are allocated less resources than users that have been less than the cumulative use of the resources. The present invention relates to a system for giving priority to a user. The system assigns priority levels based on historical requests for resource access by users. If a user has fewer requests than a specified amount over a historical period of time, the user is assigned a higher level than users having greater resource usage than the specified amount. Thus, the users using the most available resources are allocated fewer resources despite the demand, while the users using fewer resources are allocated more resources.

Another feature of the access allocation system of the present invention is that some resources are reserved for the user at the lowest priority level. Thus, even the user assigned the lowest priority level may have at least occasionally some access.

A third feature associated with the present invention is the use of continuous delivery time as a threshold to lower the current priority level of the user. For example, when a user at a particular priority level continues to use the system's resources for a predetermined amount of time, the user is assigned the next lowest priority level and its resources are reclaimed. If the user wants to access the resource again, the user needs to compete at a lower priority level.

According to the present invention, the level of service experienced by any one user depends on the history of the user's use of the resource and the continuity of the resource demand. This approach allows the resources allocated to users to be reasonably reduced in a fair manner while at the same time providing users with a system access paradigm that at least always allows each user some access regardless of how much they have been in the past.

The invention thus avoids situations where some users that require a large amount of communication dominate a certain part of the available resources. Otherwise, this would exhaust the available channels, possibly making any channels unavailable to other users at all. Resources are periodically retrieved from those users with high demand and allocated to other users, thereby achieving an equal sharing of resources.

In addition, according to the present invention, particular users can compete for available channels on a more equal basis, and therefore, even during periods of peak usage, the totality of users experience only a short lag.

Brief description of the drawings

The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings. Like reference characters designate like parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

Fig. 1 is a block diagram of units supporting wireless data transmission in the present invention.

Figure 2 illustrates the allowable system usage versus the actual usage of the wireless channel over a one month time period in accordance with the present invention.

Fig. 3 is a table of maximum data continuous transmission time allowed by various priority levels in the present invention.

Fig. 4a and 4b are flow charts illustrating a method for allocating wireless channel usage among a plurality of competing users in a wireless communication system in accordance with the present invention.

Fig. 5 illustrates a typical distribution of users' demand for communications during a month.

Fig. 6 shows a typical user application amount, a data transmission size required by a user, and a typical monthly transmission amount.

Fig. 7 is a typical daily peak usage graph.

Fig. 8 is a parameter diagram assumed by system simulation.

Fig. 9 is a diagram of a usage scenario for a particular user.

Fig. 10 shows the response time experienced by different types of users on average during a day.

Fig. 11 shows how the assignment of only two priority levels improves the overall access speed for high priority users.

Detailed description of the preferred embodiments

Fig. 1 is a block diagram of the elements of the present invention that support multiple levels of service in a wireless communication system 100. In general, communication between a plurality of field units 105 and a base station 140 may be accomplished by transmitting data over a wireless channel 130.

As shown, each end-user personal computer is connected to its corresponding user access unit transceiver 120 via a wired interface through which digital data, such as TCP/IP packets, may be transmitted. The transceiver 120 reformats the digital data for transmission over the wireless channel 130, forming a reverse link.

At the base station 140, the reformatted data packets transmitted over the wireless channel 130 are received and reassembled by the wireless interface device 145. After the received data is reassembled according to the original format transmitted by the corresponding field unit 105, the data packet is transmitted from the wireless interface device 145 to the network 155 and then to the appropriate destination device connected to the network 155.

In addition to the reverse link data transfer described above, the wireless communication system 100 of the present invention also supports forward data transfer, data transfer from devices connected to the network 155 to users in the field unit 105. Similarly, to transmit data over the wireless channel 130, the wireless interface device 145 reformats the network data packet received from the network 155. These packets are destined for the corresponding transceiver unit 120, and the transceiver unit 120 receives the packets and reassembles them. After the transceiver 120 receives the data packets, the data packets are reassembled according to the original format transmitted by the data source and transmitted over the line 112 to the corresponding personal computer 110 for further processing.

In accordance with the above-described two-way communication, a client server (not shown) connected to network 155 may be required to provide information, such as providing a web page; and corresponding information can be obtained at the remote field unit 105 by wireless connection.

In the preferred embodiment, the forward and reverse connections between the base station 140 and the field unit 105 are defined as Code Division Multiple Access (CDMA) channels in the wireless communication system 100; i.e., each wireless channel 130 is preferably defined by a pseudo-random noise-plus-signal code sequence. The pseudo-random noise code sequence and the source data are modulated onto a radio frequency carrier for data transmission over the wireless channel 130. This allows the receiving party to decode one CDMA channel and the data from another CDMA channel based on the particular pseudo-random noise assigned to that channel. Thus, one or more wireless channels 130 can be used for communication between the base station 140 and a particular field unit 105 without interference from other users.

As mentioned, the wireless channel 130 supports data transmission between each field unit 105 and the base station 140. In a preferred embodiment, field units 105 requesting to send or receive data are assigned to multiple wireless channels 130 to establish a wireless data connection. The wireless interface device 145 and corresponding resources 150 manage and allocate the wireless channel 130. The radio channels are also allocated on demand. Thus, when a field unit 105-A is idle, it is assigned to only one low speed single physical channel, and when data needs to be transferred, the channels combine to form a high bandwidth connection. Thus, the number of channels allocated to any particular field unit at a particular time varies greatly during a particular network layer connection. For more information on formatting and demand assignment for wireless channels, see U.S. patent application entitled "maintain connection lines using main/backup request channels," serial No. 09/755,305, filed on 1/2/2001 and assigned to Tantivy carrier, also the assignee of the present patent application.

The wireless link, which is comprised of a plurality of wireless channels 130, allows users of the field unit 105 to communicate with the network 155 and corresponding terminal devices, such as with a remote server. The network 155 is typically a public switched telephone network or a computer network such as the internet, and the data is typically formatted according to a particular network protocol, such as TCP/IP.

Each field unit 105 competes for the use of the limited number of wireless channels 130 supported by the communication system 100. For example, the bandwidth of a data transmission depends on the number of channels available and the amount of data traffic, and the amount of data required to be transmitted at any time may be greater than the bandwidth available for such data transmissions. Thus, the wireless channel 130 must be fairly allocated among the uses of the field units 105. According to the invention, the fair allocation is carried out according to the historical usage situation of the user and the current access requirement; i.e. users requiring the use of a particularly large amount of resources beyond the time specified by the service level will pay a price for the excessive use. Thus, such users are placed at a lower priority level and generally get less service.

The wireless communication system 100 supports several service levels. A field unit 105 subscribing to a higher level of service, upon request, will be assigned more wireless channels 130 and higher bandwidth required to transmit data than a unit with a lower level of service. Thus, data transmissions by field units 105 of higher priority are typically completed in less time than by field units 105 of lower priority.

FIG. 2 illustrates the usage of a resource by a user over a period of one month, and the line segment B represents a threshold that specifies the usage allowed by the user at any time during the one month period. For example, on the first day on the X-axis, the user is allowed to use 10 megabits of data transfer, where the user is not penalized for excessive usage. As shown in the figure, the maximum cumulative usage in a month occurs on the thirty th day, and the usage is 170 megabits. It should be noted that line segment B contains an initial value of 10 megabits so that the user is not immediately penalized for overdosing on the first day of the month.

As indicated by the segment C, if the actual usage of the resource is less than the allowable usage of the corresponding point in the segment B, the priority level of the user is usually based only on the level predetermined by the user, which is referred to herein as "priority level 1". When the user's actual cumulative usage line segment C exceeds the allowed usage line segment B, then the user's priority level is lowered due to excessive usage. Thus, during the period that line segment C exceeds line segment B, the user is served at a lower level; i.e., field unit 105 at high priority level 1 drops to priority level 2.

It is noted that if the user no longer uses the wireless communication system 100 continuously for a certain period of time such that the actual usage on line C is less than the allowed usage on line B, the user is no longer penalized. For example, on day 20, the actual usage on line C is again less than the allowable usage on line B.

In addition, lower priority levels may be associated with larger usage. For example, line segment D defines a threshold for usage, and users exceeding this threshold are dropped to a lower priority level of 3.

The usage of the wireless communication system 100 is preferably recorded over time, such as monthly. At the end of a month, the actual usage of the field unit 105 recorded by segment C is reset; i.e., the actual usage of the field unit 105 on the first day of the next month is set to zero. Preferably, each field unit 105 begins a new month some time later, which allows a balanced distribution of the user penalties for overuse at any one time.

The access requests made by the users are sorted according to the priority levels of the users. As shown, sequence 160 contains a list of access requests that are ordered by priority. The request is entered into the sequence each time the user of the field unit 105 makes a request to access content stored in the network 155. When the requests suddenly leave the order, resources are assigned to the requests according to the priority level. At least some channels are reserved for users with lower priority. For example, there are multiple channels available to a user at priority level 1, but N of the channels are assigned to a user at priority level 2. Similarly, the priority level 2 user is assigned to a plurality of channels, wherein M channels are assigned to the priority level 3 user. If X represents the total system resources allocated to the users of priority level 1, the radio channels 130 are finally allocated according to the priority levels in the ratio of X: X/N: X/(N: M) ] 1: 2: 3. I.e. the lower priority users are allocated less resources but these users always have at least some resources available.

In a preferred embodiment, the proportion of users of different priority levels that are given priority levels is independent of the total number of users in each priority level. According to this approach, a change in the proportion of users assigned priority level 1 actually changes the overall amount of available resources for priority level 1 users as compared to a change in the proportion of users assigned priority level 2.

The sequence 160 assigns system resources to various priority levels according to the specified levels. For understanding in the preferred embodiment thisHow this is done, we first assume that the system has two priority levels, P₁And P₂Respectively representing the number of users in each priority level. For example,

P₁priority 1 user number as a percentage

P₂Priority level 2 user number as a percentage

We also define a preferred ratio R, which is the ratio of the amount of resources allocated to the two levels of users. In this embodiment we assume that this ratio is 1/4, i.e. the amount of resources allocated to users in priority level 1 is four times the amount of resources allocated to users in priority level 2. We can define the two unknowns X and Y as follows:

x is the percentage of the amount of user resources allocated to priority level 1

Y is the percentage of the amount of user resources allocated to priority level 2

Then the ratio R is Y/X, from which we get Y RX.

Now, assume that 90% of the total number of users are given priority level 1 and 10% of the users are given priority level 2. Then 80% of the resources are allocated to 90% of the users (at priority level 1) and 20% of the resources are allocated to 10% of the users (at priority level 2). However, this actually means that a greater amount of resources is allocated to users with a low priority, i.e. the unit user at priority 2 occupies 2% of the resources, while users in priority 1 only get 80/90 or 0.88% of the resources.

A better way to decide on resource allocation is as follows. Since the total amount of available resources is always equal to 100%, we can specify the following relation:

XP₁+YP₂＝100

by replacing the unknown Y in the previous relation with a known allocation ratio, we can obtain the following relation:

XP₁+RXP₂＝100

substituting the known user ratio into the last relation, we can obtain:

X90+X(10/4)＝100

solving for X, we get:

90X+2.5X＝100

or 92.5X 100

X＝100/92.5＝1.08

1.08 is a percentage that indicates the amount of resources to be allocated to each user at priority level 1, the total percentage of resources allocated to users at priority level 1 being:

1.08×90％＝97.2％

the amount of resources allocated to each user in priority level 2 is 0.27, and the total amount of resources allocated to all users in priority level 2 is 0.27 × 10% — 2.7%.

In this way, the priority ratio R is independent of the number of users in each priority level. Therefore, the above calculation needs to be performed again each time the user is assigned a different priority level.

Fig. 3 is a table showing how users using wireless channel 130 over time may be penalized. For example, a user with a predetermined highest priority level 1 may be allowed to transmit for a number of 600 seconds in succession. If this time threshold is exceeded, the user is reduced to the next priority level because of excessive usage. Thus, if the corresponding transmission exceeds 600 seconds, the user at priority level 1 is dropped to priority level 2. As shown, the user with lower priority can allocate shorter continuous data transfer time without penalty.

The continuous usage time is limited in order to alert a user requesting the transfer of large executable files, voice files, etc., and not to penalize a user performing normal web browsing functions. Thus, a user downloading a web page may only need sufficient resources to make a 50 kilobit transfer. While users reading web pages no longer need wireless channels, which can be reassigned to other users in the system. This type of user typically does not exceed the 600 second threshold when at priority level 1. However, a user downloading an MP3 voice file will typically run out of the threshold of 600 seconds. The channel to which the user is assigned is thus retrieved and the user is queued in the next priority level to compete for access to the MP3 voice file again.

Fig. 4a-b are flow diagrams illustrating a method of granting access requests according to a priority principle. Reference 410 indicates the starting point for performing the method. At step 420, a new connection line is formed between the newly activated field unit 105 and the base station 140. At this point, the wireless communication channel 130 is no longer in use, but is typically used as a maintenance channel. At step 425, the system management unit at the base station 140 determines the priority levels for all stationary users based on the monthly usage history previously shown in FIG. 2.

It is then determined whether there is a request to transmit from an active, but not field unit 105 at step 430. If so, the transfer request is entered into the sequence at step 435. If no request is to be transmitted, the process continues to step 440 where it is determined whether there is a wireless channel 130 that can support the queued data transmission request. If no wireless data channel 130 is available to transmit the request, the process returns to step 420.

If at step 440 there are wireless channels 130 available, execution continues at step 450 where the available wireless channels 130 are assigned to certain transfer requests. The data is then transmitted over the assigned wireless channel 130 at step 455.

If the data transfer for a particular user is complete at step 460, the process returns to step 420. On the other hand, if the data transmission is not over, it is determined at step 465 how long it will take for a particular user to continue with the data transmission (see FIG. 3 for an actual threshold). If the maximum time for data transfer is exceeded, step 470, the corresponding data transfer is interrupted, step 475, and the user is reduced to the next priority level, step 480, due to the usage threshold being exceeded. The process then returns to step 435.

If the time to transmit the data at step 470 is not exceeded, the process returns to step 455 until the data transmission ends or the maximum continuous transmission time is exceeded.

FIG. 5 illustrates one possible distribution of user access to an anticipated amount of resource access. As shown, the average monthly data transfer requirement for the user is, for example, 175 megabits. A small number of users, such as 10% of users, have a monthly demand of less than 50 megabits, and up to 10% of users have a monthly demand of 450 megabits or more.

Fig. 6 illustrates typical internet data transmission scenarios and expected characteristics of those scenarios. For example, one application is short message delivery. A typical user expects 100 short messages each month, which are 0.1 kilobytes in length. Fig. 6 also shows the estimated number per month of the following items and the size of these items: wireless access protocol data, short email messages, normal size email messages, email messages with attachments, text-based web browsing, news and search based web browsing, web downloads, distance learning, MP3 downloads, voice file sharing, internet broadcasts, images, and visual conversations. The figure illustrates only an example of some applications that the system 100 may use to predict the monthly average load.

Fig. 7 shows the maximum load per day as a function of time of day. The maximum load occurs at about 10 am, 2 pm and 9 pm, and the minimum usage occurs at 1 pm to 4 pm.

The peak usage graph in fig. 7 and the application type in fig. 6 are used to simulate determining the average expected response time at different times of the day. Fig. 8 illustrates other assumptions made in this simulation. These assumptions include: the average size of each page is 65 kilobytes, the network tour delay time is 0.7 seconds (i.e., the round trip delay from the base station to the network), the transmission efficiency is 55%, and the shared bandwidth, i.e., the amount of bandwidth shared by the users, is 400 kilobits/second. Other assumptions made are that the maximum average speed per user is 168 kbits/sec, the maximum amount of resources that can be allocated to one user at a time. It is also assumed that the number of users and/or the number of users of the unit is 75. The initial ration was 10 megabits and the monthly ration was 175 megabits. In the present simulation scenario, it is assumed that the user makes access requests on average once a day.

The results of this simulation are shown in fig. 10. The X-axis represents the number of seconds of the response time and the Y-axis represents the user index. The user index is set to be 1-75, the lowest user number is the user with the least requirement on the system, and the highest user number (index 75) is the user with the most requirement on the system. Assume that the user's requirements are distributed according to the distribution in fig. 5. The squares on the X-axis increase in magnitude of 10 minutes. This simulation spans three months into the system, where there are two priority levels, each level being assigned to resources according to the algorithm shown in fig. 4a and 4b above.

Curve E in fig. 10 indicates the approximate average megabit per month for a particular user, as indicated by the 100, 200, 300, 400, and 500 designations above the X-axis. For example, user 20 is using approximately 100 megabits per month and user 52 is using approximately 230 megabits per month. Figure 9 shows a graph of the usage of the user 52 in this simulation. As shown, user 52 currently uses approximately 225 megabits per day on average. The average resource used by the user is compared to the allocation curve a. It can be seen that the user 52 has exceeded his dose for most of the 1 month period, and is therefore at priority level 2. At the beginning of month 2, the user 52 has days to remain under the assignment curve A, with the user at priority level 1 from day 3 of month 2 to day 9 of month 2. During the remainder of the month 2, the user 52 has exceeded his dose and dropped to priority level 2. The user 52 exceeded his ration on day 3-21, and about day 3-29 to 3-31.

The end result of this simulation is shown in fig. 10, which is a graph of the observed response times. As can be seen, the largest users, such as those with an index of 60 or higher, experience longer response times than small users with an index of 1-10. Users in the lower portion of the demand curve experience the shortest response time even during peak times of the day.

Fig. 11 is another illustration showing the advantage of the present invention. The figure assumes that the available resources are equally allocated between priority 1 and priority 2 in a 50: 50 ratio. In curve a in the middle of the graph, the allocation of channels has no priority rating. Thus, after the number of users exceeds about 50 in a communication at a time, the data bandwidth available to any one user will drop rapidly. However, in a system with two priority levels, users at priority level 1 will experience very modest service degradation, as shown by the priority level 1 curve.

We have therefore appreciated how the level of service allocated to a certain user depends on the usage history of that user over the past month, and on the extent of the continuous resource allocation, e.g. during an instant messaging period. The method provides for a proper reduction in allocation levels while at the same time providing for fair allocation. If the system is not overloaded, the result is that all users get the resources they need. However, once the system becomes overloaded, those users with historical usage greater than the permitted amount may be given a lower priority than those with historical usage less than the ration. The system has another principle of making a particular connection based on a continuous time allocation, and once these thresholds are exceeded, the user is reduced to a lower priority level.

While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the scope of the invention encompassed by the appended claims.

Claims (8)

1. A method for providing multiple levels of wireless service to a plurality of field users, whereby data communication is enabled between a base station and a plurality of subscriber units via one or more CDMA communication channels, each level of service corresponding to a priority level, the method comprising the steps of:

reserving a bandwidth and distributing the bandwidth into a plurality of channels;

maintaining connection lines between a plurality of subscriber units and a base station;

detecting a request for multiple field units to transmit data to a base station simultaneously;

the subchannels are assigned for communication between the base station and the subscriber units according to the corresponding priority level of the requesting field unit, the priority level being dependent upon the historical demand record of the particular requesting user.

2. The method according to claim 1, further comprising the steps of:

and for the case that a preset allowable usage threshold value is exceeded, the priority level of the field unit is lowered.

3. A method of providing multi-level services in a communications system requiring access, in which the level of service is dependent upon historical usage of available resources and the continuous allocation of resources.

4. A method of providing multiple levels of service in a constant access wireless communication system, wherein the levels of service depend on historical usage of available resources and continuity of resource allocation, the method comprising:

for a user applying for allocating bandwidth to transmit data information to a base station, confirming the priority level of the user according to whether the historical usage of the user on resources exceeds a certain threshold value;

allocating bandwidth to the user according to the identified respective priority level.

5. The method of claim 4, further comprising:

if the previous usage of the user is lower than the threshold, the user is given a higher priority level to transmit data information, the higher the priority level of the user is, the more channels used by the user is, otherwise, the lower the priority level is, the fewer channels are used.

6. The method of claim 4, further comprising:

if the previous usage of the user is higher than the threshold, the user is given a lower priority level to transmit data information, the lower the priority level of the user is, the fewer channels used by the user is, otherwise, the higher the priority level is, the more channels are used.

7. The method of claim 4, further comprising:

detecting whether the continuous data transmission exceeds the time limit of the distributed channel or not according to the corresponding priority level of the user, and if so, interrupting the data transmission of the user;

and reallocates the use of the previously allocated channel.

8. A method according to claim 4, wherein a threshold value defines the amount of data information a user transmits within a specified time, which threshold value will not be given a lower priority level.