Methods and systems for detecting collisions in access/utilization of resources of contention

Systems and methods are described for detecting collisions in packets related to attempted access or utilization of a resource or pool of resources in a given timeslot in which the energy level of corrupted received access probe packets are compared with a threshold energy level, and if above the threshold, the timeslot is marked as a collision slot.

FIELD OF THE INVENTION

The invention relates to communications systems in general, and more particularly to collision detection systems and methods for detecting collisions in packets related to access or utilization of a resource or pool of resources.

INCORPORATION BY REFERENCE

The following previously filed and currently pending U.S. patent applications are hereby incorporated by reference in their entireties as if fully set forth herein: Yoshikawa Ser. No. 11/193,522, filed Jul. 29, 2005, entitled METHODS AND SYSTEMS FOR UTILIZATION OF RESOURCES OF CONTENTION UNDER ANY LOAD TO FACILITATE DESIRED BANDWIDTH ACROSS SINGLE OR MULTIPLE CLASSES OF DEVICES; and Yoshikawa Ser. No. 11/257,337, filed Oct. 24, 2005, entitled METHODS AND SYSTEMS FOR ESTIMATING ACCESS/UTILIZATION ATTEMPT RATES FOR RESOURCES OF CONTENTION ACROSS SINGLE OR MULTIPLE CLASSES OF DEVICES.

BACKGROUND OF THE INVENTION

In communications and computing systems, many system resources are shared for use by large numbers of devices. For example, shared resources are commonplace in wireless, wireline, LAN, WAN, WIMAX, Blue Tooth wireless mobile communications systems, in which resources or pools of resources (hereinafter “resources” collectively) such as network elements, base stations, networks, servers, communications media, etc. are shared among multiple devices that require access to or continued utilization of the shared resources. Resource contention can occur in mobile communications systems such as Evolution Data Only (EVDO)-wireless networks, when multiple cell phones, PDAs, portable computers, etc. attempt to simultaneously access a local base station resource such that the input handling capacity of the base station is exceeded (access attempt failure), or when the base station is operating at maximum capacity and is unable to service any additional information from one or more currently served devices (utilization attempt failure). Contention may arise when multiple mobiles simultaneously attempt to access the base station on the access channel, leading to a collision of the call initiation messages. When a mobile device fails to obtain access or utilization of the base station, an internal apersistence system will cause the mobile to back off and refrain from further attempts for a given amount of time, where the time is determined according to an apersistence value provided by the base station resource or an apersistence control system associated therewith. By selecting the apersistence values, the apersistence control system sets the back off behavior of the mobile devices in a manner that ideally maximizes the access and utilization of the base station resource, and may also support multiple priority classes with different apersistence for each class. To accurately determine the apersistence values sent to the mobile devices, the apersistence control system must have data or information regarding the amount of incoming traffic such as requests for access or utilization of the access channel for a base station resource. In this regard, the mobile devices in EVDO systems send access probe requests to the base station access channel in discrete timeslots, and incoming traffic estimation systems may be constructed to operate on timeslot information that indicates whether a particular timeslot was empty (no access probe packets), or contained either a successful single probe or a collision of multiple probe packets. Thus, there is a need for techniques and systems to distinguish between the three possible conditions in a given timeslot in an unambiguous and robust way to facilitate implementation of traffic estimation systems and control systems for adjusting the resource to minimize collisions.

SUMMARY OF THE INVENTION

The following is a summary of one or more aspects of the invention to facilitate a basic understanding thereof, wherein this summary is not an extensive overview of the invention, and is intended neither to identify certain elements of the invention, nor to delineate the scope of the invention. Rather, the primary purpose of the summary is to present some concepts of the invention in a simplified form prior to the more detailed description that is presented hereinafter.

The invention relates to systems and methods for detecting collisions in packets for attempting access or utilization of a shared resource, and may be implemented in conjunction with any system in which access probe messages or packets associated with access/utilization attempts are subject to collisions, and finds particular utility in association with mobile communications system applications related to shared base station resources. In general, the present invention employs energy information for a given time period (timeslot) to differentiate between corrupt or invalid received packets caused by actual collisions of access probes and those attributable to other causes, such as bad RF conditions which are more properly characterized as empty slots for purposes of incoming traffic estimation and apersistence control. In certain embodiments, the energy levels of corrupted received access probe packets are compared to a threshold value set to a value that has a high assurance of a single access probe being successfully received, so that if the measured energy exceeds the threshold level, the timeslot is presumed to correspond to a collision, whereas lower energy corrupted timeslots are deemed to be empty. The invention may thus be advantageously employed to unambiguously map success/empty/collision timeslots to a traffic load estimate in association with advanced apersistence control and estimation technologies related to wireless communications systems as well as in other situations requiring accurate estimation of incoming traffic destined for a resource of contention.

In accordance with one or more aspects of the invention, collision detection methods are provided for detecting collisions in packets related to attempted access or utilization of a base station or other resource or pool of resources. The method includes determining whether a received packet is a corrupted access probe indicating an attempted access or utilization of the resource or pool of resources, and determining whether the received packet is indicative of a collision in the corresponding timeslot based at least in part on the energy of the received packet. In one implementation, the method includes marking the timeslot as successful if a preamble of a received packet indicates the received packet corresponds to an access probe packet and if the received packet passes a checksum test. In this example, if the preamble indicates an access probe preamble but the checksum fails or other test indicates the packet is corrupted, the received packet energy is measured and compared with a threshold energy level above which a single packet is likely to be received without error by the resource or pool of resources. The timeslot is then marked as a collision if the measured energy is above the threshold energy level, and may otherwise be marked as an empty slot. The method may thus be used to differentiate between corrupted access attempts attributable to collisions and other situations for which the timeslot data is more properly characterized as an empty slot.

Further aspects of the invention involve wireless system base station resources that receive access probes data packets in certain predefined time periods or slots. The base station resource includes an energy measurement system that measures an energy associated with incoming packets in a given time period, as well as a collision detection system which provides timeslot data including an indication of empty, collision, or successful access/utilization attempts in the given time period, where the collision detection system determines whether a received packet indicates a collision in the given timeslot based at least in part on the measured energy of the received packet. In one example, the collision detection system compares the measured energy of the received packet with a threshold energy level, and sets the timeslot data indication to collision if the received packet is a corrupted access attempt packet and the energy of the received packet is above the threshold. Any suitable threshold value may be used, such as a level above which a single packet is likely to be received without error by the base station resource in one example. The system may also determine whether no packet has been received in the given time period and to determine whether a received packet is an access probe packet, such as by suitable preamble testing. In this case, the collision detection system sets the timeslot data indication to empty if no packet is received in the given time period or if a received packet is not an access probe packet. The system may also be operative to determine whether a received packet is corrupted, for example, using checksum or other suitable testing, where the timeslot data indication is set to successful if the received packet is an uncorrupted access probe packet.

DETAILED DESCRIPTION OF THE INVENTION

Referring now to the drawings, several embodiments or implementations of the various aspects of the present invention are hereinafter illustrated and described in conjunction with the drawings, wherein like reference numerals are used to refer to like elements.FIG. 1shows a simplified flow diagram illustrating a method2for detecting collisions in packets related to attempted access or utilization of a resource or pool of resources in accordance with one or more aspects of the invention. Although the method2is illustrated and described below in the form of a series of acts or events, the methods of the invention are not limited by the illustrated ordering of such acts or events, wherein some acts or events may occur in different order and/or concurrently with other acts or events apart from those illustrated and described herein in accordance with the invention, and not all illustrated steps may be required to implement a process or method in accordance with the present invention. Furthermore, the methods of the invention can be used in a variety of applications, for example, including without limitation data analysis or acquisition situations in which the collision detection information is used to derive a measure of system utilization, and control situations wherein the estimated value is used as system feedback to control one or more facets of the system operation, such as apersistence parameters, etc.

The method2begins for a given time period or time slot at4, with a determination being made at6as to whether or not a received packet is a corrupted access probe, wherein an access probe is any data message or packet associated with an attempt to access or utilize a shared resource or pool of resources. Thereafter, the method2includes determining whether the received packet indicates a collision occurred in the given timeslot based at least in part on an energy of the received packet. At6a, a determination is made as to whether a packet was detected in the current time slot. If not (NO at6a), the slot is marked as an “empty” slot at5and the method2proceeds to the next time slot at12and returns to6a. Otherwise (YES at6a), the energy is measured for the received packet at6b. The energy measurement at6bcan be any suitable characterization of the energy associated with the received packet in the current timeslot, including but not limited to average, peak, median, energy over all or a portion of the length of the received packet, over all or a portion of the entire length of the time slot, or other suitable measurement by which timeslots including corrupted access probe packets can be accurately and repeatably distinguished from truly empty timeslots and timeslots in which non-access probe data is received, for example, by comparison with a suitable threshold energy value.

At6c, a determination is made as to whether a preamble of the received packet corresponds to that of a recognized access probe, which may be accomplished using any suitable preamble recognition, parsing, or reading and comparison techniques. For instance, where a correct access probe is defined as having all binary “1”s or all “0”s or some predefined pattern thereof, the received preamble can be compared at6cin suitable hardware or software logic with the known acceptable preamble (or with a plurality of acceptable preambles) to ascertain whether the packet is indeed an access probe attempting to initiate or request access or utilization of the resource. If the preamble does not match an acceptable access probe preamble (NO at6c), the method proceeds to5where the current timeslot is marked as empty. Otherwise (YES at6c), the method2proceeds to determine whether the access probe packet is corrupted at6d, in one example by performing a checksum test on the received access probe packet. Alternatively, other suitable tests can be performed at6dusing suitable logic, whether hardware, software, or combinations thereof, to determine whether the received access probe is corrupted, for example, by checking a checksum field of the packet. In the illustrated example, a determination is made at6eas to whether the corruption test (e.g., checksum) passed. If so, the method2proceeds to7where the current timeslot is marked “successful”, and the method2proceeds to the next slot at12.

If, however, the access probe packet is corrupted (NO at6e), the measured energy is compared with a threshold value at8. Any suitable comparison can be performed at8to determine whether the measured energy of the received packet is above the threshold energy level or not, for instance, in hardware, software, or combinations thereof, etc. Moreover, any suitable energy threshold level may be used at8which allows actual or probable collisions to be distinguished from other situations, such as weak signals, bad RF conditions, or noise in the channel between the resource and the requesting device, etc. In one possible implementation, the measured energy is compared with a threshold energy level above which a single packet is likely to be received without error by the resource. If the received packet energy is less than or equal to the threshold (NO at8), the method2provides for marking the time slot as empty at5. In this manner, the method presumes that the received information is not a collision of two or more access probes attempting to use the resource, which is useful in ascertaining appropriate control actions to take with respect to apersistence control applications in wireless communications systems, as described further below. However, if the measured energy is above the threshold energy level (YES at8), the current timeslot is marked as a collision at10, and the method2proceeds to the next timeslot at12. The method2may thus be operated essentially as a continuous loop to identify the timeslot data for each successive timeslot, with the data including an indication of either “empty”, “successful”, or “collision” for attempts to access or utilize the resource in each timeslot.

Referring also toFIG. 2, the techniques embodied in the exemplary method2may be advantageously employed to differentiate between corrupted access attempts attributable to collisions and other situations for which the timeslot data is more properly characterized as an empty slot based at least in part on the measured energy of the received packet. This information may be particularly useful in measuring or estimating current incoming access probe traffic for use in closed loop type control of the resource utilization, such as apersistence control in wireless communications systems.FIG. 2schematically illustrates an exemplary resource20, which can be a wireless system base station in one example, which is operable to receive incoming data packets30in a given time period, including access probe type packets that request access or utilization of the resource20. The resource20includes a collision detection system22with an energy measurement system24operative to measure an energy associated with the incoming packets30in the given time period. Any suitable energy measurement system or apparatus may be employed, such as hardware, software, combinations thereof, etc., that is operatively associated with the resource and the collision detection system22for measuring and or analyzing energy for the received packet30, for example, average energy or power, peak energy or power, median energy or power, etc., which can be measured over all or a portion of the temporal length of the received packet30, over all or a portion of the entire length of the time slot, or other suitable measurement period by which timeslots including corrupted access probe packets can be accurately and repeatably distinguished from truly empty timeslots and timeslots in which non-access probe data or corrupted single access probe data is received by the resource.

The collision detection system22can be any suitable hardware, software, or combinations thereof, etc., which operates to provide timeslot data28for a given timeslot period according to the principles set forth herein, wherein the timeslot data28provides an indication of attempts to access or utilize the resource20in the given time period, and where the indication has a value of empty, collision, or successful. In particular, the exemplary collision detection system22operates to determine whether a received packet30indicates a collision in the given timeslot based at least in part on the measured energy of the received packet, thereby facilitating differentiation between collision slots and empty slots from the perspective of closed loop control feedback information, wherein the timeslot data28may be used to estimate incoming access/utilization traffic requesting use of the resource20. In the illustrated embodiment ofFIG. 2, moreover, the collision detection system22compares the measured energy of the received packet30with a threshold energy level26and sets the timeslot data indication to collision for the given time period if the energy of a corrupted access probe packet is greater than the threshold26.

In general, the system22may be operated in accordance with the above-described method2ofFIG. 1or other suitable operational method. In one embodiment, the threshold energy26is set to a level above which a single packet30is likely to be received without error by the resource, although other suitable levels26may be used by which the system22can differentiate between actual collisions of two or more access probe packets30and other timeslot conditions. In the illustrated example, moreover, the incoming access probe packet30includes a preamble portion32, a data or payload portion34, and a checksum portion or field36, where any of the fields or portions32,34,36may be a single bit or multiple bits, and where the information of the fields or the packet30generally may be binary, trinary, decimal, or other suitable data format. In operation, the collision detection system22determines for a given time slot whether a packet30has been received, and if not, sets the timeslot data28to indicate “empty”. However, if a packet30was indeed received in the timeslot, the system22determines whether the received packet30is an access probe packet or not, for example, by checking the preamble field32. If the preamble32does not indicate an access probe type packet, the data28is also marked “empty”. The system22also determines whether received access probe packets30are corrupted, for example, by checking the checksum portion36using known verification techniques, and if uncorrupted, the system22sets the timeslot data28to indicate a “successful” timeslot.

It is noted that while the packet30is illustrated as a unitary packet for purposes of explaining the operation of the collision detection system22, in practice the access probe data or packet30may be a single packet with respect to upper layers and may be segmented or partitioned into smaller portions or sub-packets by lower network layers, with or without padding and other additions of various control or padding bits. In one example, an upper layer in the sender (the entity requesting access or utilization of the resource20, such as a mobile phone) may, create the packet30including the data field34and the checksum36(with or without padding), and provide this to one or more lower layers which may add the preamble32to identify the packet30as an access probe. The lower layer(s) may also segment the packet30into smaller sub-packets for transmission through the communications channel, with the receiving entity (e.g., the resource20or another element associated therewith, such as the collision detection system22) receiving the individual sub-packets and reassembles the unitary packet30, which may including removal of control or padding bits or other information associated with the lower layer(s). The receiving entity checks the preamble (e.g., before or after re-assembly) to verify that the received packet30is indeed an access probe requesting resource access or utilization, and performs a verification, such as a checksum test, on the reconstructed packet30to ascertain whether the access probe30has been corrupted. Thus, regardless of the specific form of the access probe30and regardless of whether the packet30or the data thereof has been modified, reformatted, segmented, padded, augmented, or otherwise changed, the invention provides for determining therefrom whether the packet is an access probe and if so, whether the packet30has been corrupted.

Referring now toFIGS. 3-6B, the timeslot data28may be used for many purposes, and finds particular utility as an input to rate estimation systems for use in closed-loop adaptation of a resource with respect to access or utilization.FIG. 3shows an exemplary rate estimation system70that uses the timeslot data28from the collision detection system (CDS)22in the resource20to derive one or more current rate estimates78of attempts to access or utilize the resource20. In general, the CDS22and/or the access/utilization attempt rate determination system (MRDS)70may be integrated into the resource20or other connected network element operatively associated with the resource20, or may be provided as separate components, where the system70may be implemented in hardware, software, or combinations thereof, and the AARDS70may provide the estimate78to any system component, for example, to an apersistence control system160associated with a base station resource150in a wireless network190as described below in connection withFIG. 5. The exemplary MRDS70ofFIG. 3includes a simulated rate model76and rate estimation logic72which obtains a plurality of timeslot data values28forming a current rate analysis timeslot data window74indicating the number of successful, empty, and collision timeslots28observed for the resource20in the current window74. The estimation logic72in this embodiment provides the current attempt rate78based on the current rate analysis window timeslot data74and the simulated attempt rate model76, which can be equations, formulas, algorithms, curves, data files, etc., by which the logic72obtains or derives the estimate78of an actual attempt rate corresponding to the current window data74, wherein the exemplary model76maps simulations of attempt rates to observed data in an integer number of successive timeslots28forming the rate analysis window74.

FIG. 4provides a flow diagram80illustrating operation of the exemplary MRDS70ofFIG. 3in estimating or determining a rate of attempted access/utilization of a resource or pool of resources, wherein the current rate analysis window timeslot data is obtained from the collision detection system22at82, where the data window corresponds to a plurality of timeslots forming a current rate analysis window.FIGS. 6A and 6Billustrate one such rate analysis window74having an integer number K timeslots281-28K, where K is a positive integer greater than 1 for which timeslot data28is obtained with indications of empty, successful, and collision timeslots28. As shown best inFIG. 6B, each timeslot28has one of three identified values, including empty (E), successful (S), and collision (C), wherein the success data (e.g., SC1, SC2) may also indicate a priority class of the device that successfully accessed or utilized the resource in a particular timeslot28(e.g., class 1, class 2, etc.). InFIG. 6B, timeslot data174may be tabulated from the window data entries28to totalize the number of observed empty timeslots NEOBS174ain which no attempts occurred, the observed number of timeslots NSOBS174bin which a successful attempt occurred, and the observed number of timeslots NCOBS174cin which a collision occurred for the subject window74. With this information obtained at82inFIG. 4, the current access/utilization attempt rate is estimated at84based on a simulated attempt rate model (model76inFIG. 3) and the current rate analysis window timeslot data174. The window74is then updated at86with data28from one or more new timeslots28obtained from the collision detection system22, and another estimate78is thereafter generated in similar fashion.

FIG. 5shows an exemplary application of the collision detection system22in providing timeslot data28for use in controlling apersistence in a mobile communications system190in combination with the AARDS70, where the communications system190includes a base station resource150providing communications services for a number of mobile communications units (MUs)180, and where the system190includes an access/utilization attempt rate determination system (AARDS)70with a simulation model and estimation logic as described in association with the system70ofFIG. 3above. The collision detection system22provides timeslot data78to the MRDS70, where one or both of the systems22and/or70may be integrated in the base station resource150or may be implemented in another system component (e.g., such as in a network server192of communications system190, shown in dashed lines inFIG. 5).

The system190also includes an apersistence control system (ACS)160operatively associated with the base station resource150, where the ACS160uses the attempt rate estimate78from the MRDS70to control apersistence of the mobile units180in attempting to access/utilize base station resource150. In operation, the collision detection system22provides the data28indicating whether each individual timeslot was empty, successful, or a collision, and a number of these data values28are formed into a data window74by the MRDS70. The MRDS70, in turn, estimates a current attempt rate78for the base station150based on the simulated attempt rate model76(FIG. 3) and provides the attempt rate78to the apersistence control system160for apersistence value adjustment/control in accordance therewith.

Referring also toFIG. 7and to TABLE 1 below,FIG. 7provides a plot200illustrating a three dimensional graph of the system attempt data for a given number K timeslots28per window74, where the plotted plane202is the solution to the equation NS+NE+NC=K. As shown in the plot200, simply attempting to estimate the access/utilization attempt rate based solely on success rates (without differentiating actual empty slots from collision slots) leads to an ambiguity for all conditions except at maximal throughput (maximum NS) in a closed loop control of apersistence in the wireless system190. The collision detection techniques of the present invention facilitate drawing distinctions between received access probe packets having corrupt checksums due to actual collisions between two or more access probes of sufficient energies (that would have otherwise been correctly received if sent individually), and probes corrupted due to weak signal strength, thermal noise, interference from other weak mobile units180, or other causes unrelated to actual access probe collisions. In the illustrated embodiments described above, these distinctions are drawn by comparing the energy of corrupted probe packets30with the energy threshold26(FIG. 2above) in which the energy threshold26is preferably set to a value that has a high assurance of a single access probe30being successfully received. In this manner, access probes30of a sufficient energy with a corrupt checksum are identified as collision slots and weaker corrupt probes are identified as empty slots.

In the apersistence control application ofFIG. 5, the robust identification of empty, collision, and successful timeslots is thus advantageous to unambiguously determining the load (e.g., incoming access/utilization attempts) imposed on the base station resource150. As shown in TABLE 1 below, the access channel in a wireless EVDO network was simulated using a rate analysis window of K=56 access cycles (e.g., 5.97 second window length), where the number of empty timeslots (NE) plus number of success timeslots (NS) plus number of collision timeslots (NC) equal to number of timeslots in rate analysis interval (NI).

Without the ability to distinguish collisions from empty slots, estimating the incoming traffic load on the base station resource150is difficult, since the success rate alone is ambiguous, as shown in the plot200ofFIG. 7. The simulation results of TABLE 1 show that the maximum simulated throughput occurs at 10,400 BHCA (NS/56=15.07/56=0.269). On both sides of this maximum, there are two traffic loads with similar fractional success rates. For example, the success rate for 6500 BHCA (NS/56=10.23/56=0.183) is similar to that of 13,000 BHCA (NS/56=10.02/56=0.179). Thus, absent the techniques of the invention to detect collisions as shown inFIGS. 1 and 2above, when a system observes a success rate on the order of about 0.18 in a rate analysis interval, it is impossible to decide whether the resource load is 6500 BHCA or 13,000 BHCA. However, using the above-described collision detection techniques and systems of the invention, NCand NEare known or discernable, whereby the collision rate for 6500 BHCA (NC/56=3.176/56=0.0567) is easily distinguished from that of 13,000 BHCA (NC/56=37.29/56=0.666).

Referring now to FIGS.5and8-11, using the collision differentiated timeslot and window data28,74, the AARDS70can provide robust estimates of the loading of the base station resource150to the apersistence control system160for controlling system response times and throughput for single or multiple classes of mobile devices180. As shown inFIGS. 8 and 9, the base station resource150periodically sends broadcast messages182to the mobile units180including apersistence values204aand204bcorresponding to first and second (e.g., high and low) priority classes. The devices180then perform internal apersistence tests to decide whether and when to initiate call attempts184. As shown inFIG. 10, the mobiles180include apersistence logic systems191that perform apersistence tests using the apersistence value204aor204bfrom the apersistence control system160of the base station150.FIG. 11illustrates an apersistence test300performed by the apersistence logic191in the exemplary mobile units180, beginning at302with an apersistence property value “n” (e.g.,204aor204b) being received at301from the received broadcast message182from the base station resource150. The mobile180obtains the most recently received apersistence property value (n)204at304and computes an instantaneous throughput scaling factor (ITSF)=p=2−n/4at306. A random number “x” in a range of 0 to 1 is generated at308, which is compared to the ITSF (p) at310to determine whether the device180should attempt to access or utilize the base station150. If the test fails (e.g., NO at310for x greater than or equal to p), the method300returns to304and another test is performed in the subsequent access cycle. Otherwise (YES at310), an access/utilization attempt is made at312, and if successful (YES at320), the apersistence test300ends at330. If unsuccessful (NO at320), the method300returns to run another apersistence test at304.