Multiplex communications – Channel assignment techniques – Combining or distributing information via time channels...
Reexamination Certificate
2000-06-20
2004-06-22
Marcelo, Melvin (Department: 2663)
Multiplex communications
Channel assignment techniques
Combining or distributing information via time channels...
C370S461000, C370S462000
Reexamination Certificate
active
06754225
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to an optimal contention region allocation for medium access control. More specifically, the present invention relates to an optimal contention region allocation for medium access control in multipoint-to point networks.
2. Description of the Related Art
Wired broadband networks, such as HFC, and wireless broadband networks, such as MMDS networks, are key access technologies to extend NII to the home due to their large bandwidth and two-way communication capability. In these network structures, the transmission delay between a head-end and each station is too large to be neglected. Therefore, the head-end and each station must be synchronized. Synchronization is performed by sending the stations' requests for ranging in order to execute a ranging in synchronization. At the same time, in order to effectively utilize the bandwidth, such networks utilize a reservation and a fixed bandwidth access mode. For the bandwidth access, the stations must send a request to the head-end because the bandwidth is allocated by the head-end. Thus, allocating bandwidth is achieved by utilizing the ranging in synchronization or bandwidth reservation.
For the ranging in synchronization, the stations' requests for the range are sent within a range assigned by the head-end. Similarly, the stations' requests for the bandwidth are sent within the range assigned by the head-end. The regions assigned by the head-end are referred to as “contention regions”. Since the upstream channel within the contention region is shared by multipoint-to-point, the stations' requests may collide within the contention region and thus lead to the wastage of bandwidth and a larger request access delay. That is, even though the possibility of collision will be reduced within a bigger contention region, it will lead to the wastage of bandwidth and increase the access delay if the contention region is too big. On the other hand, the possibility of collision will greatly increase if the contention region is too small. To resolve the collision problem is to assign the contention region repeatedly for collision groups until no collision group. This also wastes the bandwidth. Therefore, the allocation of contention region is essential for efficiency of bandwidth usage.
A traditional method for allocating contention regions is disclosed in Lazaros Merakos and Chatschik Bisdikian, “Delay analysis of the n-ary stack random-access algorithm”, IEEE Trans. On Information Theory, vol. 34, no. 5, pp. 931-942, September 1988.
The n-ary method applies statistics to find the possibility of collision within a synchronized random access system. Applying this method to a slot-typed contention with under 100 slots (within a given contention region) and 100 requests participating contention, the possibility of collision is 2.2 to 2.3 requests on average in a slot. Therefore, the throughput is optimal as n=3. That is, the collision problem can be solved by allocating 3 slots to the collided clusters. However, such a fixed contention region method cannot be applied to a practical dynamic contention environment.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide a method of determining an optimal contention region to achieve efficient contention region usage.
Another object of the present invention is to provide a method of determining a contention region allocation to achieve the maximum throughput of the contention region.
Another object of the present invention is to provide a method of determining a contention region allocation for medium access control in multipoint-to-point networks. The method is applied to obtain maximum throughput either in synchronized or in asynchronized collision resolutions.
The objects of present invention are achieved by providing an optimal ranging method for medium access control in multipoint-to-point networks. The method applies the possibility of collision to establish an optimal table so that the optimal efficiency of usage for medium access in multipoint-to-point networks can be achieved. A contention cycle of the present invention consists of an initial contention and collision resolution phase. A station failing to send its request in the initial contention will exercise the collision resolution process until the request is sent successfully, wherein the access channel of request is of blocking mode.
The method of the present invention comprises the steps as follow. First, a Most Likely Request Table MLR (d,s,c) and an Optimal Table OPT (n,d) are found by simulating the practical contention situation with a computer. Second, for the initial contention of a new contention cycle, the head-end utilizes the proportional scheme to estimate the number of requests participating the contention in the new contention cycle. Thus, the optimal contention region is obtained, based on that number, by looking up Table OPT(n,d), where n is the requests and d is n's corresponding optimal contention region. Third, in the collision resolution phase, for each contention round, the number of collided requests is estimated, based on the contention result, through the Table MLR(d,s,c), where d is the allocated contention region, s is the number of successful requests, and c is the number of collided clusters. Finally, looking up the Table OPT (n,d) based on the estimated number of collided clusters, the optimal value d of each contention region can be determined and the throughput of requests is maximized. Therefore, optimal throughput can be achieved and the wastage of bandwidth reduced (see
FIGS. 6
,
7
, and
8
).
These and further features, aspects and advantages of the present invention, as well as the structure and operation of the embodiment thereof, will become readily apparent with reference to the following detailed description of a presently preferred but nonetheless illustrative embodiment, when read in conjunction with the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements.
REFERENCES:
patent: 5953344 (1999-09-01), Dail et al.
patent: 6529520 (2003-03-01), Lee et al.
Charoenpanitkit, A. et al, “An analysis of a new access control technique for channel request in wireless communications”, May 2001, Circuits and Systems, 2001, IEEE, vol. 2, pp. 333-336.*
Daigle, J.N. et al, ‘Analysis of Packet Networks Having Contention-Based Reservation With Application to GPRS’, IEEE/ACM Transactions on Networking, vol. 2, No. 4, Aug. 2003, pp. 602-615.*
L. Merakos, et al.; Delay Analysis of the n-Ary Stack Random-Access Algorithm; IEEE Transactions on Information Theory, vol. 34, No. 5, Sep. 1988; pp. 931-942.
Lin Yeong-Sung
Lin Ying-Dar
Yin Wei Ming
Marcelo Melvin
National Science Council
Norris McLaughlin & Marcus P.A.
LandOfFree
Optimal contention region allocation for medium access... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal contention region allocation for medium access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal contention region allocation for medium access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3360253