Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1997-05-09
2001-03-20
Patel, Ajit (Department: 2732)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S235000, C709S238000, C709S253000
Reexamination Certificate
active
06205153
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a network access protocol known as Carrier Sense Multiple Access with Collision Detection (CSMA/CD) and, more particularly, to a method for improving network performance when multiple parties collide in such a network.
The CSMA/CD protocol, generally used in Ethernet LANs (local area networks), is defined in ANSI/IEEE Standard 802.3 published by the Institute of Electrical and Electronics Engineers (hereinafter, the “IEEE 802.3 standard”).
Under the CSMA/CD rules for access to a network bus or cable, any node or station wishing to transmit must first listen to ensure that the channel is clear before beginning to transmit. All nodes on the network have equal priority of access and may begin transmitting as soon as the channel is clear and a required interpacket delay of 9.6 microseconds has elapsed. However, if a first node that has begun transmitting detects a collision with a transmission from another node, the first node continues transmitting for a short time to make sure that all nodes wishing to transmit will detect the collision (it is assumed that, while the attempts to transmit are nearly simultaneous, the first node is actually the first to begin). Every other node detecting the collision also continues to transmit for a short time. Then each node that has detected a collision terminates transmission of the packet or frame. The nodes involved in the collision then wait for the required interpacket delay of 9.6 microseconds and then select random and therefore usually different delay times, referred to backoff times, before attempting to transmit their packets again. As used herein, “collision” refers to the condition in which two or more nodes attempt to transmit nearly simultaneously after detecting the bus is clear.
The IEEE 802.3 standard defines a collision backoff procedure referred to as “truncated binary exponential backoff.”When a transmission attempt has terminated due to a collision, it is retried by the transmitting node after a selected backoff time until either the transmission is successful or a maximum number of attempts have been made and all have terminated due to collisions. The backoff time is selected by each node as an integral multiple of the “slot time” which is the maximum round trip propagation time for the network, i.e., the time required to propagate a data packet from one end of the network to the other and back. The slot time is defined by the IEEE 802.3 Standard as 51.2 microseconds. The number of slot times selected as the backoff time before the nth retransmission is chosen as a randomly distributed integer r in the range:
0
≦r≦
2
k
, where
k=
min (
n,
10).
Therefore, for the first attempted retransmission, the backoff time is selected as 0 or 1 slot times. For the second attempted retransmission the backoff time is selected as 0, 1, 2 or 3 slot times. For the third attempted retransmission, the backoff time is selected as 0, 1, 2, 3, 4, 5, 6 or 7 slot times and so on, up to a maximum backoff time of up to 1,023 slot times or 52.4 milliseconds. The backoff-time retransmission attempt number relationships are set forth in Table 1 below.
TABLE 1
Retransmission Attempt No.
Backoff Time in Slot Times
n
r
1
0,1
2
0,1,2,3
3
0,1,2,3,4,5,6,7
4
0-15
n
0-(2
n
− 1)
10 (max n)
0-1023
As can be appreciated, if two parties collide there is a fifty percent chance that the parties will take the same transmission window on the first retransmission attempt. There is similarly a fifty percent chance that they will pick different transmission windows. On the second retransmission attempt, the wider range of numbers makes the chances of colliding on each of the attempts progressively smaller.
If, however, a collision occurs between more than two parties, there is a greater likelihood that the collision will occur again on the second attempt. For example, if nodes A, B and C collide, node A will pick a number X on its first retransmission attempt. There is a fifty percent chance that node B will pick the same number X, and a fifty percent chance that node C will pick the same number X before attempting retransmission. Thus, no matter what happens, there will be at least two parties attempting to transmit in one window, thereby increasing the chances of another collision. The possibilities for three parties colliding with a backoff window of 2 (e.g., x or y time slots) are set forth in Table 2 below:
TABLE 2
COLLISION POSSIBILITIES:
3 PARTIES COLLIDE, BACKOFF WINDOW OF 2
PARTY
A
B
C
BACKOFF
X
X
X
X
X
Y
X
Y
X
X
Y
Y
Y
X
X
Y
X
Y
Y
Y
X
Y
Y
Y
Clearly, as the number of parties colliding increase, this problem becomes worse. The developers of the IEEE 802.3 Standard and Ethernet did not efficiently handle the possibility of multiple parties colliding. At the time the IEEE 802.3 standard was developed, E-mail traffic was the prevalent LAN use envisioned. However, today's higher bandwidth graphics and multimedia traffic increase the chances of multiple parties colliding. Thus, the two-party collision is, in many cases, an unrealistic assumption. As more and more parties collide, the chances for a lockup on a network employing the IEEE 802.3 collision backoff standard increase exponentially.
A method has been developed in which backoff times in a two node collision in which one node has “captured” the system are selected to be different from those prescribed in the IEEE 802.3 standard, for example, in U.S. Pat. No. 5,436,903. In that system, backoff times are changed, for example, by selecting backoff times deterministically and then using a stopped backoff technique in which a node's backoff timer is stopped when the collision signal on the bus is active. While apparently successful at preventing node capture, the system does not address the possibility that more than two nodes might collide.
SUMMARY OF THE INVENTION
These problems in the prior art are overcome in large part by a system and method according to the present invention in which each node is configured to be able to determine how many parties have collided. If more than two parties collide, the retransmission attempt number is incremented such that a greater number of backoff times are selectable by each of the colliding nodes. Thus, for example, if three parties A, B and C collide, the parties will select from backoff times corresponding to, for example, retransmission attempt n=2, rather than backoff times based upon retransmission attempt n=1. In this manner the likelihood of a repeat collision is reduced.
According to one embodiment of the present invention an access controller monitors voltage levels on the bus. A first voltage level corresponds to a collision between two parties on the bus. A second voltage level corresponds to more than two nodes colliding for access on the bus. If the second voltage level is detected during a collision, the nodes back off and select backoff times from a backoff time window greater than that corresponding to the prescribed standard.
Briefly, the present invention relates to a network node capable of detecting how many parties have collided during attempts to transmit on a bus. If more than one party has been detected to collide, the node selects a backoff window from a larger randomized group of possible backoff windows than if the node had collided with only one other party. In this way, delays due to multiple parties colliding are minimized.
REFERENCES:
patent: 4063220 (1977-12-01), Metcalfe et al.
patent: 4464658 (1984-08-01), Thelen
patent: 4584679 (1986-04-01), Livingston et al.
patent: 4598285 (1986-07-01), Hoshen
patent: 4630264 (1986-12-01), Wah et al.
patent: 4965792 (1990-10-01), Yano
patent: 5018138 (1991-05-01), Twitty et al.
patent: 5268899 (1993-12-01), Brown
patent: 5319641 (1994-06-01), Fridrich et al.
patent: 5353287 (1994-10-01), Kuddes et al.
patent: 5381413 (1995-01-01), Tobagi et al.
patent: 5398244 (1995-03-01), Mathews et al.
patent: 5418784 (1995-05-01), Ramakrishnan et al.
patent: 5422887 (1995-06-01), Diepstraten e
Beyda William J.
Shaffer Shmuel
White Charles Marcus
Yen Harry
Patel Ajit
Phunkulh Bob A.
Siemens Information and Communications Systems, Inc.
LandOfFree
System and method for improving CSMA/CD network performance... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for improving CSMA/CD network performance..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for improving CSMA/CD network performance... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520261