WO2001037494A2 - Access spreading in a packet data radio system - Google Patents

Abstract

A technique for spreading access attempts in a communication system entails transmitting messages from an application host to respective terminals via a packet data system, each of the messages including an access description element which specifies a time interval. Each terminal receives its respective message and generates a reply thereto. This reply is performed by making an initial uplink access on the random access channel. Once the first access is made, the network reserves radio resources for the terminal for use in conducting communication between the application host and the terminal. The initial access is transmitted following a lapse of the time interval specified in the message. The application host specifies different time intervals for different terminals. Accordingly, the access attempts made by the terminals are spread out over time to reduce congestion in the random access channel.

Description

ACCESS SPREADING IN A PACKET DATA RADIO SYSTEM

BACKGROUND OF THE INVENTION The present invention relates to a method and system for spreading access attempts in a packet data system.

General Packet Radio Service (GPRS) refers to a high-speed packet data service for use in cellular networks, particularly GSM cellular networks. GPRS overlays a packet based wireless interface on the existing circuit switched GSM network. Information is transmitted in packets which are reassembled at the receiving site. Radio resources are used only when packets are being sent or received. This allows multiple users to share radio resources, in contrast to circuit switched connections in which each mobile data user is assigned a dedicated channel. This results in efficient use of the radio spectrum. Further, the packet-based approach of GPRS allows a seamless connection to the Internet from a mobile personal computer.

The beneficial features of GPRS allow operators to introduce many new data services in their GSM networks. One application that has been proposed is real-time betting. In a typical real-time betting environment, participants place bets during an event based on projections of what might happen during the event. For instance, real- time betting can involve betting by spectators in a sporting arena in the course of a game or match. For instance, the participants could place bets on who will score the next goal, or whether an upcoming power play (in the game of ice hockey) will result in a goal or not. Other applications include betting on horse races, quiz or game shows. Related application include bidding at auctions, buying and selling securities, polling audiences, etc.

Implementation of these applications may require changes in the dimensioning of the radio system. For instance, in a real-time betting scenario, many people (e.g.. several thousand) will place their bets within a short period of time, for example, 10-30 seconds. This surge in betting activity places a heavy load on the resources of the radio network. GPRS systems and other packet data radio systems may be incapable of handling applications with these characteristics.

For instance, a potential problem with applications like the real-time betting and voting is that they induce large peaks in the number of random access attempts to the system. To illustrate this, consider the example where a bet is to be placed within 30 seconds. It is likely that most participants will respond to the bet during the last 10 seconds of the given 30 second period. With a typical configuration providing a random access capacity of 40 attempts per second, this constraint limits the number of participants per cell to 400. If more than 400 participants choose to participate in the bet, the Random Access Channel may become jammed due to access burst collisions. This would effectively stall the GPRS service in the cell. Note that since all applications share the same Random Access Channels, the GPRS service would be stalled for all GPRS applications, not just the betting applications. This situation would be, of course, clearly unsatisfactory to the system operator.

More specifically, in a radio packet data system with more than one user, the uplink resources are conceptually (and often physically) divided into two groups. In the Access Channel Group, a mobile station performs an initial uplink access when no resources are dedicated to that mobile station. Once the first access is made, the network reserves radio resources for the mobile station radio resources from a

Dedicated Resource Channel Group. In GPRS, the Access Channel Group consists of the Packet Random Access Channel (PRACH) or possibly the Random Access Channel (RACH). The logical channels in the Dedicated Resource Channel Group in GPRS (on the uplink) consist of the Packet Data Traffic Channel (PDTCH). the Packet Associated Control Channel (PACCH) and the Packet Timing Control Channel (PTCCH).

On channels in the Access Channel Group, the timing of the transmissions from the mobile station to the network is essentially random. Two mobile stations may independently decide to transmit access bursts to the system at the same time. When this happens, the network is unable to decode either of the access bursts, and both access attempts fail. To limit the random access collisions, the Random Access Channel has to be properly dimensioned. When the number of random access attempts is larger than approximately 20% of the bare capacity of the Random Access Channel, the performance of the system rapidly deteriorates. This means that the effective random access capacity is roughly 20% of the bare capacity of the Random Access Channel. In GPRS, the effective capacity of the random access channel is between 40 and 320 random access attempts per second depending on the specific channel configuration. In a typical configuration, the random access capacity is no more than 40 attempts per second. While sufficient for most applications, this is not enough when thousands of real-time betters try to access the system simultaneously. An overload in the RACH of a GPRS system is illustrated in Figure 1. As indicated there, multiple users respond to a bet at approximately the same time close to the end of the deadline for the bet, thereby exceeding the effective RACH capacity of the radio system (which is denoted by a dashed line). As mentioned above, this can result in the stalling of all GPRS service. More specifically, it may be impossible to contact the GPRS system during and some time after the peak period.

Various solutions have been proposed to reduce collisions in packet data systems, and more specifically, to prevent the peak in traffic from exceeding the effective RACH capacity. One simple way to reduce collisions is to increase the effective capacity of the RACH by reconfiguring the logical channels. However, this method has two significant drawbacks. First, the RACH is vastly over dimensioned between access peaks. Hence, the average utilization of the RACH is very low and expensive radio resources are reserved for rare events (the access peaks). This solution therefore wastes radio resources. Second, there is a limit to how much bandwidth can be allocated to the RACH. In GPRS, this constraint currently sets a limit of approximately 320 access attempts per second. Another conventional solution is to dynamically adjust the RACH capacity to the load (number of access attempts). This technique addresses the first-mentioned drawback of the solution described above. However, in this solution, there remains a limit to how much bandwidth can be allocated to the RACH at one time. Further, the change in bandwidth on the PRACH in GPRS is implemented by restructuring the logical control channels. This restructuring leads to interruptions in ongoing transfers, since mobile stations need to reread the system information messages. Hence, it is undesirable to change the PRACH bandwidth too frequently. Further, a dynamic solution cannot predict future traffic loads; it simply reacts to heavy loads which have already occurred. Hence, a dynamic solution cannot prevent the flooding of access attempts. It only helps to resolve the congestion once it has occurred.

Another technique partly ameliorates the problem of collisions by allowing the radio system to recover after the access peak by performing a "back off" procedure upon access failure. In short, according to this method, when a user receives no response to a first access attempt, an assumption is made that a collision has occurred. The user then transmits a second attempt at a random time interval following the first attempt. If the second attempt also fails, a third attempt is made at another randomly selected time. The interval between requests can be lengthened upon each failure to further spread the accesses over a longer time period. In this manner, access congestion is eventually resolved, since users are forced to wait for progressively longer intervals of time before they make access retries.

However, this method also fails to satisfactorily address the problems identified above. For instance, the "back off" cannot prevent the peak (and hence access congestion) from occurring. It can only resolve the congestion once it has occurred. Further, the "back off" technique is implemented (or "resides") in the access system, not in the application. Hence, all applications will experience the same access spreading and delay when trying to access the system. This means that the average delay experienced at peak traffic will affect all users, not simply those involved in real- time betting . This may result in an increase of voice call set-up time to unacceptable values .

Thus, the identified conventional approaches have a number drawbacks. Generally, the conventional techniques cannot prevent access congestion from occurring; these technique only resolve the situation once congestion occurs. Second, these techniques affect all applications in the system; they cannot be applied to some applications and not others. Third, the conventional techniques are implemented as part of the packet data radio system rather than on an application level. This introduces complicated dependencies between the applications and the specific packet data radio system.

SUMMARY OF THE INVENTION

It is accordingly an exemplary objective of the present invention to address the above-identified problems by providing a more effective technique for reducing access congestion in a communication system.

This objective is achieved by a technique for spreading access attempts in the communication system. The communication system can include an application host communicatively coupled to a plurality of terminals via a packet data system, the packet data system employing a random access channel. The technique comprises transmitting messages from the application host to respective terminals via the packet data system, each of the messages including an access description element which specifies a time interval. Each terminal receives its respective message and generates a reply thereto. This reply is performed by making an initial uplink access on the random access channel. Once the first access is made, the network reserves radio resources for the terminal for use in conducting communication between the application host and the terminal. The initial access is transmitted following a lapse of the time interval specified in the message. The application host specifies different time intervals for different terminals. Accordingly, the access attempts made by the terminals are spread out over time. The distribution of access attempts ensures that the access attempts do not exceed the capacity of the random access channel.

The technique can be implemented at the application level and is independent from the packet data system. As such, the technique does not require any special protocol for interaction between the application level and the packet data system. Further, because the technique is entirely implemented in the application layer, the technique does not directly affect those applications which do not use access spreading.

BRIEF DESCRIPTION OF THE DRAWINGS The foregoing, and other, objects, features and advantages of the present invention will be more readily understood upon reading the following detailed description in conjunction with the drawings in which:

Figure 1 illustrates the distribution of access attempts in a real-time betting application in a conventional system; Figure 2 shows a radio network which can be used to implement the access spreading technique of the present invention;

Figure 3 is a flow chart illustrating the access spreading technique of the present invention;

Figure 4 is a timing diagram showing a sequence of events in one example of the accessing spreading technique of the present invention; and

Figure 5 illustrates the distribution of access attempts in a real-time betting application according to the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS In the following description, for purposes of explanation and not limitation, specific details are set forth in order to provide a thorough understanding of the invention. However it will be apparent to one skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well-known methods, devices, and circuits are omitted so as not to obscure the description of the present invention with unnecessary detail. In the drawings, like numerals represent like features.

For instance, the discussion is framed in the context of real-time betting or voting. However, those skilled in the art will appreciate that the principles discussed herein can be applied to any packet data system which can benefit from the reduction of congestion in the access channel. Further, the access spreading technique is described in the context of the GSM/GPRS system. However, the access spreading technique can be applied to other packet data systems, including D-AMPS/EDGE, IS-95 and future wideband systems such as UMTS and CDMA2000.

Figure 2 shows an overview of a system 1 which can implement the access spreading technique of the present invention. The system includes an application host (or server) 4. The application host 4 administers the application. In the real-time betting application, the application host 4 is the server responsible for formulating the bets, communicating the betting conditions to the corresponding applications residing in terminal equipment 5 , receiving the bets from the terminal equipment 5 and administrating the results of the bets. The logic used to perform these tasks can be implemented in software, discrete logic circuitry or combination thereof.

The application host 4 is communicatively coupled to a GPRS system 7. The GPRS system 7 provides communication between the application host 4 and the terminal equipment 5. The architecture of the GPRS system 7 is specified in TS GSM 03.60, which is incorporated herein by reference in its entirety. The GPRS system 7 includes a GPRS network 2, which, in turn, includes a Gateway GPRS Support Node (GGSN). a Serving GPRS Support Node (SGSN) and a GPRS Base Station System (GPRS BSS), as known to those skilled in the art.

The GPRS network 2 is communicatively coupled to one or more GSM/GPRS base stations 6. The base station(s) 6 are communicatively coupled to a mobile station 3, which may comprise a GPRS radio unit, via wireless (e.g. , radio) communication. The mobile station 3 also directly interfaces with the terminal equipment 5. The terminal equipment 5 can be a laptop computer, a smart phone, or any other device capable of running an application and interfacing with the mobile station 3. The application logic resides in the terminal equipment 5 and can be implemented as software, discrete logic circuitry or combination thereof.

Figure 3 is a flow chart illustrating the access spreading technique in the specific exemplary context of a real-time betting application. In step SI . the betting application in the application host 4 creates a message (Betting Offer Message) that contains the betting conditions as well as an Access Description Element. The Access Description Element contains information which specifies when the application in the terminal equipment 5 shall respond to the system. For example, the Access Description Element could tell the application to send the response at a time t, where t is a random time between 10 seconds and 30 seconds after the reception of the Betting Offer Message. In step S2, the Betting Offer Message is transported to the terminal equipment 5. In step S3, the betting offer is displayed to the end user. In step S4, it is determined whether the user has responded to the bet within the prescribed time limit. If so, in step S5 , the system determines the time at which a Response Message should be sent to the mobile station 3. In step S6. the terminal equipment 5 submits the Response Message to the mobile station 3. In step S7, the mobile station 3 accesses the system on the Random Access Channel according to standard GPRS procedures. Finally, in step S8, the Response Message is transmitted to the application host 4.

According to the above technique, including the Access Description Element in the Betting Offer Message assures that the responses from the terminal equipment 5 are spread out evenly over a prescribed time period (e.g.. in one exemplary case, about 10 to 30 seconds) after the reception of the Betting Offer Message. Since the GPRS mobile station 3 sends an access burst on the Random Access Channel immediately after the reception of the Response Message from the terminal equipment 5 , the access bursts are also spread evenly over the same period of time. As such, the overload of the Random Access Channel can be avoided.

Figures 4 and 5 illustrate a specific example of the technique of Figure 3. Assume that the application host 4 has constructed a bet with betting alternatives A and B. In this exemplary case, the application host 4 needs the responses from the end users within 60 seconds . Without the present spreading technique there would be a great risk that the replies from the end users would congest the Random Access Channel, as previously illustrated in Figure 1. With the present spreading technique, the application host 4 inserts a requirement in the Betting Offer Message that the end user has to choose one of the alternatives A and B within 20 seconds after the reception of the Betting Offer Message. Furthermore, the application host 4 provides an Access Description Element that instructs the betting application in the terminal equipment 5 to stall sending of the reply and to submit the response to the mobile station 3 at a random time between 20 and 55 seconds after the reception of the Betting Offer Message. More specifically, the events shown in Figure 4 correspond to the steps shown in Figure 3. As shown there, the Betting Offer Message is forwarded and displayed to the user in events 1-3. The Betting Offer Message specifies that the user has 20 seconds to respond to the bet. Providing that the user responds in this time interval (as determined in event 4), the terminal equipment 5 will send the reply to the mobile station 3 after stalling for a random time between 20 and 55 seconds (in events 5 and 6). When the mobile station 5 receives the reply, it immediately forwards it to the application host 4 via the GPRS system (in events 7 and 8).

As shown in Figure 5, the technique described above has the effect of distributing the betting replies over a time interval. As a consequence, the traffic on the Random Access Channel does not exceed the capacity of this channel at any time. In conclusion, the above-described technique effectively addresses problems encountered with access-intense applications, such as real-time betting. In contrast to conventional systems, the present technique operates on an application level rather than in the packet data radio system itself. Thus, the technique provides a design that is tailored to each application to control the access load from that particular application to avoid access congestion. By working at an application level, the technique can make the access spreading transparent to other applications. For instance, while the access spreading increases the average access time for the particular application, other applications do not experience any delay in their access time. Further, because the technique is entirely confined to the application layer, it works equally well for all packet data radio systems, and it does not induce any complicated relations between the betting application and the packet data radio system. As mentioned above, the spreading technique is not limited to the GRPS or

GMS cellular environments. The technique can be used, for instance, in the D- AMPS/EDGE, IS-95, UMTS, UTRA, CDMA 2000 systems, and generally any packet data radio systems using random access channels. Further, the technique has application to other types of networks, including networks with hardwired links (e.g. , networks that do not use wireless communication).

Still other variations of the above described principles will be apparent to those skilled in the art. All such variations and modifications are considered to be within the scope and spirit of the present invention as defined by the following claims .

Claims

WHAT IS CLAIMED IS:

1. A method for reducing access congestion in a communication system, the communication system including an application host communicatively coupled to at least one terminal via a packet data system, the packet data system employing a random access channel, comprising the steps of: transmitting a message from the application host to the terminal via the packet data system, the message including an access description element which specifies a time interval; receiving the message at the terminal; generating a reply to the message at the terminal; and transmitting the reply to the application host via the random access channel of the packet data system following a lapse of the time interval specified in the message.

2. The method according to claim 1, further including the step of specifying the time interval associated with the terminal such that it differs from another time interval associated with another terminal.

3. The method according to claim 1 , further including the step of randomly generating a value and calculating the time interval based on the randomly generated value.

4. The method according to claim 1 , wherein the message conveys terms of a betting offer.

5. The method according to claim 4, wherein the terms of the betting offer specify a prescribed time at which a user can reply to the betting offer.

6. The method according to claim 1 , wherein the packet data system is a GPRS packet data system.

7. The method according to claim 1 , wherein the packet data system includes a communication network communicatively coupled to a mobile station via a base station using wireless communication, and the at least one terminal is coupled to the mobile station.

8. A communication system, comprising: an application host; at least one terminal; a packet data system using a random access channel for communicatively coupling the application host to the at least one terminal; message generation logic at the application host for generating and transmitting a message from the application host to the terminal via the packet data system, the message including an access description element which specifies a time interval; reply generation logic at the terminal for generating and transmitting a reply to the application host via the random access channel of the packet data system following a lapse of the time interval specified in the message.

9. The system according to claim 8, wherein the message generation logic specifies the time interval associated with the terminal such that it differs from another time interval associated with another terminal.

10. The system according to claim 8, wherein the message generation logic randomly generates a value and calculates the time interval based on the randomly generated value.

11. The system according to claim 8, wherein the message conveys terms of a betting offer.

12. The system according to claim 11 , wherein the terms of the betting offer specify a prescribed time in which a user can reply to the betting offer.

13. The system according to claim 8, wherein the packet data system is a GPRS packet data system.

14. The system according to claim 8, wherein the packet data system includes a communication network communicatively coupled to a mobile station via a base station using wireless communication, the at least one terminal is coupled to the mobile station.