Adaptive algorithms for optimal control of contention access
Contention for a shared communications medium in a communications network involves a fine balancing act between wasting much network bandwidth sitting idle or recovering from collisions and transmitting data. Contention adaptation concepts are introduced for access to a shared medium, and adaptive algorithms for contention access using probabilities and backoffs are presented.
1. A method for adaptively controlling network traffic on a communications network with a shared communications medium, said method comprising:
determining traffic category permission probabilities;
calculating an overall permission probability, PP;
contending for access to the shared communications medium, comprising:
determining if a contending station is permitted to transmit; and
transmitting traffic from an appropriate traffic category;
updating the traffic category permission probabilities by an amount that is proportional to how far a ratio of an amount of time the medium is in an idle state to an amount of time the medium is in a collision state is from optimal;
determining updated traffic category permission probabilities; and
repeating the above steps until buffered traffic is transmitted wherein there are a plurality of traffic categories, and a traffic category permission probability is assigned for each traffic category and the calculating an overall permission probability, PP, is a summation of the traffic category permission probabilities assigned to each traffic category.
2. The method of claim 1 , wherein updating traffic category permission probabilities comprises a centralized controller assigning the traffic category permission probabilities.
3. The method of claim 1 , wherein the shared communications medium is shared by a plurality of stations, and wherein updating traffic category permission probabilities comprises each station assigning the traffic category permission probabilities.
4. The method of claim 1 , wherein the shared communications medium is shared by a plurality of stations, and wherein the calculating overall permission probability step is performed by stations with traffic to transmit.
5. The method of claim 1 , wherein the determining step comprises:
generating a random number, X; and
granting the contending station permission to transmit only if the random number, X, is less than or equal to the overall permission probability, PP.
6. The method of claim 1 , wherein the contending for access step comprises:
setting a backoff timer;
determining if a contending station can transmit; and
sending traffic from an appropriate traffic category.
7. The method of claim 6 , wherein the setting a backoff timer comprises:
calculating a backoff time based on the random number, X; and
setting the backoff timer to the backoff time.
8. The method of claim 7 , wherein the calculating a backoff time uses the formula:
J=[log( X )/log(1 −PP )],
where [ Y ] denotes a largest integer number not exceeding Y and PP is the overall permission probability.
9. The method of claim 6 , wherein the determining step comprises:
freezing a backoff timer when the shared communications medium is busy;
decrementing a backoff timer after the shared communications medium is idle for a point coordinating function inter-frame space period; and
waiting until the backoff timer expires.
10. The method of claim 6 , wherein the sending traffic from an appropriate traffic category comprising sending traffic from traffic category N, where N meets the criteria:
if 0< C*X≦TCPP +0 , then N= ;else
if
∑
i
=
0
M
-
1
TCPP
i
<
C
*
X
≤
∑
i
=
0
M
TCPP
i
,
where
1
<
_
M
<
_
7
,
then
N
=
M
,
and where
C
=
∑
i
=
0
Z
TCPP
i
,
Z
+
1
is a total number of traffic categories, and TCPP 1 , is the traffic category transmission probability for traffic category i and is set to zero if traffic category i has no traffic to send from the contending station.
11. The method of claim 1 , wherein the determining updated traffic category permission probabilities occurs at regular fixed intervals of time.
12. The method of claim 1 , wherein the shared communications medium is shared by a plurality of stations, and wherein the determining traffic category updated traffic category permission probabilities is performed at each station with traffic to transmit.
13. The method of claim 1 , wherein the determining updated traffic category permission probabilities is performed at a centralized controller.
14. The method of claim 1 , wherein the determining updated traffic category permission probabilities step occurs at irregular time intervals and is triggered by a network performance metric.
15. The method of claim 14 , wherein the network performance metric is a ratio of an amount of time the medium is in an idle state to an amount of time the medium is in a collision state is outside of an interval (1−epsilon, 1+epsilon), where epsilon is a predetermined value.
16. A method for adaptively controlling network traffic on a communications network with a shared communications medium, said method comprising:
generating a random number, X;
determining traffic category permission probabilities;
calculating an overall permission probability, PP;
determining if a contending station is permitted to transmit;
sending traffic from traffic category N, where N meets the following criteria:
if 0≦ X≦TCPP + 0 , then N =0; else
if
∑
i
=
0
M
-
1
TCPP
i
<
X
≤
∑
i
=
0
M
TCPP
i
,
where
1
<
_
M
<
_
7
,
then
N
=
M
,
and where TCPP 1 is the traffic category permission probability for traffic category i and is set to zero if traffic category i has no traffic to send from the contending station;
determining updated traffic category permission probabilities; and
repeating the above steps until buffered traffic is transmitted wherein there are a plurality of traffic categories, and a traffic category permission probability is assigned for each traffic category and the calculating an overall permission probability, PP, is a summation of the traffic category permission probabilities assigned to each traffic category.