Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1999-10-27
2004-11-16
Chin, Wellington (Department: 2664)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S447000, C370S458000, C370S445000
Reexamination Certificate
active
06819676
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a local area network (LAN) employing the Ethernet and more particularly to a method for improving scheduling fairness of signal transmission/reception in a network when collisions occur in an Ethernet based LAN.
2. Background of the Related Art
Generally, all nodes can access a network with fair scheduling priority in a CSMA/CD (Carrier Sense Multiple Access with Collision Detection) system. All the nodes must confirm that the network is not used for a time interval of an inter packet gap (IPG) before transmitting a packet. The IPG is typically about 9.6 &mgr;s for a 10M network and 0.96 &mgr;s at a 100M network. However, a collision occurs when two nodes transmit a packet simultaneously.
FIG. 1
illustrates channel access processing in a conventional Ethernet based LAN. As shown in
FIG. 1
, all m nodes, from the first node S
1
, to the mth node S
m
, transmit a first packet. After the transmission is completed, the nodes S
1
to S
m
wait for up to the IPG duration before transmitting a second packet. After the transmission of the second packet is completed, the first node S
1
to the next to last node S
m
wait for the IPG and then transmit a third packet. However, the mth node S
m
delays for the IPG after finishing the transmission of the second packet and then transmits a fourth packet. If the first node S
1
and the mth node S
m
simultaneously transmit their packets, then a conflict or collision occurs after ½ slot time. In
FIG. 1
, a collision occurs between the fourth packets transmitted from nodes S
1
and S
m
.
If the collision occurs, each node that transmitted the colliding packets waits as long as the IPG plus a backoff time before retransmitting the same packet. The backoff time is set differently for each node to prevent another collision. Each node that transmits a colliding packet repeats the transmission immediately after a lapse of the predetermined backoff time until the packet is successfully transmitted or until the number of retransmission trials or attempts due to collisions exceeds a predetermined maximum number and the trial terminates.
One related process for setting the backoff time is called a truncated binary exponential backoff algorithm.
FIG. 2
illustrates a channel capture effect occurring when using such a related backoff algorithm. The backoff time is set to an integral multiple number r of a slot time. The slot time is a maximum turnaround time delay in the network. In other words, the time slot is a maximum time necessary for a certain node to transmit a packet and receive an answer. For example, the slot time in a 10M network is 51.2 &mgr;s.
The integral multiple number r that will be multiplied by the slot time is determined based on the number of times the packet is retransmitted by the node in accordance with the following formula:
0≦r<2
k
, where variable k=min (n, 10), n is the number of times of signal retransmission and 10 is the predetermined maximum number of retransmission attempts before the trial terminates.
Table 1 illustrates the values of the integral multiple number r and available backoff times based on the number of times of signal retransmission n.
TABLE 1
number of times
of retransmission
r
backoff time (rx slot time)
1
0,1
0x slot time, 1x slot time
2
0,1,2,3
.
3
0,1,2,3,4,5,6,7
.
4
0~15
0x slot time~15x slot time
.
.
.
.
.
.
.
.
.
10
0~1023
0x slot time~1023x slot time
For example, the number of retransmissions n varies form 1 through 10. When the number of retransmissions n is 1, namely, at the first retransmission, variable k=min(1, 10)=1 and 0<r<2
1
. Therefore, the integral multiple number r may be 0 or 1. Based on the selected value of the integral multiple number r the backoff time may be 0 times the slot time or 1 times the slot time.
At the 10th retransmission, variable k=min(10,10)=10 and 0<r <2
10
, so the integral multiple number r may be one of 0 to 1023. Therefore, the backoff time may be one of 0 times the slot time to 1023 times the slot time based on the selected integral multiple number r value optionally selected. At this time, the slot time in the 10M network is 52.4 ms.
If such method as described above is applied to a network having many nodes, some amount of scheduling fairness could be realized. The following description referring to
FIG. 2
concerns the case that signals are transmitted in the related method in a network having a few active nodes.
FIG. 2
illustrates a channel capture effect occurring when using a related backoff algorithm.
If the node A and the node B perform transmission of a packet at the same time, a collision of the packets occur. If the collision occurs, each of the nodes A and B determines a backoff time. If respective integral multiple number r values of nodes A and B are set to 0 and 1 respectively, the backoff time of node A becomes 0× slot time, and the backoff time of node B becomes 1× slot time. Accordingly, node A transmits a signal after waiting for only an IPG while node B waits for IPG +1× slot time until the node A completes the packet transmission. Then node B waits for another IPG before transmitting its signal. According to such a scheme, node A can successfully transmit its packet without interference from node B.
Afterwards, if node A tries to successively transmit another packet, the packet collides with the first packet transmitted from node B. For node A which successfully transmitted its previous packet, this collision is the first collision for the successive packet, but the collision is the second collision for the first packet transmitted from node B. In other words, the number of times of signal retransmission, n, by the node A is less than the number of times of signal retransmission, n, by the node B. Therefore, there is low probability that the backoff time of node A is longer than the backoff time of node B. That is, the probability that node A can use the network is higher than the probability that node B can use the network. A problem exists that node A continuously transmits its packets while node B must only wait. This channel capture effect is more common when the conventional packet transmission method is applied to the LAN having a few active nodes.
Accordingly, when the related method is applied to a network having a few active nodes, there occurs the channel capture effect that one node must continuously wait while another node can continuously transmit packets, thus decreasing scheduling fairness of the network.
SUMMARY OF THE INVENTION
An object of the present invention is to substantially obviate one or more of the limitations and disadvantages of the related art.
Another object of the present invention is to improve scheduling fairness in using a network when collisions in an Ethernet based LAN occur during signal transmission.
A further object of the present invention is to increase overall network use efficiency.
To achieve these and other advantages, and in accordance with the purpose of the present invention as embodied and broadly described, a method for improving scheduling fairness for a network in accordance with a preferred embodiment of the invention includes detecting a packet collision occurring while different nodes transmit a packet; reading a previous network state for application of the backoff algorithm; selecting a new IPG based upon the read information; and determining a backoff time before retransmitting a packet.
The present invention can be achieved in a whole or in parts by a method for improving scheduling fairness in using a network by detecting whether or not collision occurs during packet transmission in the network having a plurality of nodes, and storing and monitoring signal transmit/receive state of X bit(s) before the collision with respect to each of the plurality of nodes. If the collision is detected, reading the previous transmit/receive state of X bit(s) with respect to a node having the collision, and judging the prev
Chin Wellington
Fleshner & Kim LLP
Ho Chuong
Hyundai Electronics Industries Co,. Ltd.
LandOfFree
Method for improving scheduling fairness of signal... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for improving scheduling fairness of signal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for improving scheduling fairness of signal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300875