Optimized random access scheme for a shared response

Details Optimized random access scheme for a shared response Optimized random access scheme for a shared response

2000-02-23

2002-12-03

Wong, Peter (Department: 2181)

Electrical computers and digital data processing systems: input/

Access arbitrating

Access prioritizing

C710S240000

Reexamination Certificate

active

06490645

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method of allocation of a shared resource between multiple uncoordinated users, and more particularly, to the situation in which users are of different priority levels.
BACKGROUND OF THE INVENTION
There are many well known systems in which multiple users share a common resource in a way which can lead to conflict. These systems are known in the art as contention systems and include, but not exclusively, examples such as the sharing of memory between different peripherals inside a microprocessor, the sharing of a digital bus between different digital components connected to it, sharing of a multi-drop line connecting a group of computer terminals, or the sharing of a radio communications network.
There are two types of methods of resolving conflicts among multiple users: centralized schemes and distributed schemes. In a centralized scheme, a central site acts a moderator, providing a single point of coordination. An example of a centralized scheme is polling. The central site sends a message to each terminal in turn, giving it permission to transmit. Although the scheme is simple, there is added delay because the central site is involved in every single transfer. In addition, as the number of terminals becomes high, the full polling cycle increases to a level unacceptable to most users of interactive terminals. Finally, if only a fraction of the possible terminals are logged in at a particular moment, polling is particularly inefficient. Polling is not applicable to modern radio networks.
In a distributed scheme, all terminals are peers. Distributed systems have lower message delays and allow higher network utilization than centralized systems but are more complicated. ALOHA is one type of distributed system where users transmit whenever they have some information to deliver. The user waits for an acknowledgment. If no acknowledgment is received, a collision between transmissions of more than one sender is assumed. The user will wait a random time and then will retransmit. For pure ALOHA the transmission occurs as soon as transmit request is issued while for slotted ALOHA, the time axis is divided into slots and the terminal will wait for transmission until the beginning of the next slot.
Multiple access systems can be evaluated based on two metrics, 1) normalized throughput which is equivalent to the fraction of link capacity used to carry non-retransmitted packets of data, and 2) mean delay which is the amount of time that a terminal has to wait before it successfully transmits a packet. The normalized throughput is inversely dependent on collision probability. The mean delay is directly dependent on the mean access delay which is the mean waiting time in case of retransmission. In order to minimize the repetitive collision probability (maximize throughput), retransmissions should be spread out uniformly over the retransmission period, i.e. the random access delay in case of retransmission should have a uniformly distributed characteristic over the retransmission period. A uniform distribution f (x) is characterized by the equation:
f
(
x
)=0 for
x<L
1
,x≧L
2
f
(
x
)=1/(
L
2
−L
1
) for
L
1
≦×<L
2
  (1)
where L
1
and L
2
define the boundaries of the retransmission period
The size of the retransmission period is a tradeoff between collision probability and mean access delay.
Radio standards require that the random access delay in case of retransmission should be uniformly distributed. The TETRA standard (ETS 300 392-2)which is the pan-European standard for Trunked Radio Systems that are wholly digital utilizes this type of distribution.
Although in pure ALOHA or slotted ALOHA, using the uniformly spread out retransmissions will maximize overall throughput, these schemes do not address the case when some users should have higher priority. Reservation ALOHA, where slots are reserved for specific terminals, can give certain users higher priority, but the system does not perform as well as slotted ALOHA.
The SAE J1708 re-try protocol, proposes changes in the random retry time by a weighting factor which depends on a predetermined priority of different classes of users. Because the overall distribution is not uniform, the utilization of the retransmission interval is sub-optimal. In TETRA and other systems providing two-way radio communications, such sub-optimal use of the resource results in longer call setup delays and a degraded system performance. There is thus a widely recognized need for, and it would be highly advantageous to have, a method of sharing a resource among multiple uncoordinated users that allows higher priority users to have a lower mean access delay of retransmission while the overall randomization process preserves its uniformly distributed characteristic.


REFERENCES:
patent: 4161786 (1979-07-01), Hopkins et al.
patent: 5301332 (1994-04-01), Dukes

Affiliated with

Also associated with

Rating

Optimized random access scheme for a shared response does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimized random access scheme for a shared response, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized random access scheme for a shared response will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2997663