Methods and apparatus for use in a network of the ethernet type, to improve fairness by controlling collision backoff times and using stopped backoff timing in the event of channel capture

Abstract

A technique for modifying the IEEE 802.3 standard for selecting backoff times in a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) network, in the event that a collision is sensed by a node that has captured the network communication channel. If there is a small number of active nodes on the network, one node may capture the channel and the standard backoff algorithm makes it increasingly unlikely for another node to transmit. The new technique provides for less aggressive, i.e. longer, backoff times before at least the first retransmission attempt made by a node that has captured the channel, and in addition provides for the use of a stopped backoff algorithm. Three specific examples of methods to choose a backoff time and two methods of using a stopped backoff algorithm are disclosed. Even though the invention represents a departure from the standard CSMA/CD backoff algorithm, the overall average backoff times provided by the invention can be selected to be consistent with the average times provided by the standard. Moreover, nodes using the invention interoperate successfully with nodes that do not use the invention.

We claim: 
     
       1. For use in a first node in a network having a plurality of nodes employing Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol for channel access, a method for improving the fairness of access to a channel, comprising the steps of: sensing whether or not the first node of the network has captured a channel;   sensing a collision between a first packet transmission by the first node and a second packet transmission by a second node of the network;   after sensing the collision, selecting a backoff time to wait before making each of a number of retransmission attempts of the .[.second.]. .Iadd.first .Iaddend.packet, .[.the selected backoff time between each said attempt and the immediately preceding attempt conforming to a selected integral multiple r of a slot time, where r is a positive integer, and corresponding to the number of the retransmission attempts made previously,.]. whereby, if the first node has .Iadd.not .Iaddend.captured the channel, the backoff time is .Iadd.selected from .Iaddend.a prescribed .Iadd.range of .Iaddend.backoff .[.time.]. .Iadd×Iaddend.;   if the first node has .[.not.]. captured the channel, the backoff time .[.before making at least a first of the retransmission of the attempts.]. is selected .[.to be r slot times longer than the prescribed backoff time.]. .Iadd.from a different range of backoff times including a longer backoff time than those included in said prescribed range.Iaddend.;   monitoring the channel for activity from .[.the second node.]. .Iadd.other nodes .Iaddend.on the network;   operating a backoff timer to provide the selected backoff time when the channel is idle;   halting the backoff timer during any period in which the channel is not idle; and   attempting retransmission of the .[.second.]. .Iadd.first .Iaddend.packet when the backoff timer expires.   
     
     
       2. For use in a first node in a network having a plurality of nodes employing Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol for channel access, a method for improving the fairness of access to a channel, comprising the steps of: sensing whether or not the first node of the network has captured a channel;   sensing a collision between a first packet transmission by the first node of the network and a second packet transmission by a second node of the network;   after sensing the collision, selecting a backoff time to wait before making each of a number of retransmission attempts of the .[.second.]. .Iadd.first .Iaddend.packet, .[.the selected backoff time between each said attempt and the immediately preceding attempt conforming to a selected integral multiple r of a slot time, where r is a positive integer, and corresponding to the number of the retransmission attempts made previously,.]. whereby, if the first node has .Iadd.not .Iaddend.captured the channel, the backoff time is .Iadd.selected from .Iaddend.a prescribed .Iadd.range of .Iaddend.backoff .[.time.]. .Iadd×Iaddend.;   if the first node has .[.not.]. captured the channel, the backoff time .[.before making at least a first retransmission of the attempts.]. is selected .[.to be r slot times longer than the prescribed backoff time.]. .Iadd.from a different range of backoff times including a longer backoff time than those included in said prescribed range.Iaddend.;   determining if the .[.second.]. .Iadd.first .Iaddend.node is waiting a first backoff time .Iadd.selected from said different range .Iaddend.for a first retransmission attempt;   in response to a determination that the .[.second.]. .Iadd.first .Iaddend.node is waiting the first backoff time, monitoring the channel for activity from the .[.first node.]. .Iadd.other nodes .Iaddend.on the network, operating a backoff timer when the channel is idle, and halting the backoff timer during any period in which the channel is not idle;   in response to a determination that the .[.second.]. .Iadd.first .Iaddend.node is not waiting the first backoff time, operating the backoff timer; and attempting retransmission of the .[.second.]. .Iadd.first .Iaddend.packet when the backoff timer expires.   
     
     
       3. The method in as in claim 1 or 2 wherein the step of monitoring the channel for activity from the .[.second node.]. .Iadd.other nodes .Iaddend.further comprises recognizing when .[.the second.]. .Iadd.another .Iaddend.node is transmitting on the channel. 
     
     
       4. The method in as in claim 1 or 2 wherein the step of monitoring the channel for activity from the .[.second node.]. .Iadd.other nodes .Iaddend.further comprises recognizing when a collision is occurring on the channel. 
     
     
       5. The method in as in claim 1 or 2 wherein the step of monitoring the channel for activity from the .[.second node.]. .Iadd.other nodes .Iaddend.further comprises recognizing when .[.the first.]. .Iadd.another .Iaddend.node is transmitting or a collision is occurring on the channel. 
     
     
       6. For use in a first node in a network having a plurality of nodes employing Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol for channel access, an apparatus for improving the fairness of access to a channel, comprising: means for sensing whether or not the first node has captured a channel;   means for sensing a collision between a first packet transmission by the first node and a second packet transmission by a second node on the network;   means, in response to sensing the collision, for selecting a backoff time to wait before making each of a number of retransmission attempts of the .[.second.]. .Iadd.first .Iaddend.packet, .[.the selected backoff time between each said attempt and the immediately preceding attempt conforming to a selected integral multiple r of a slot time, where r is a positive integer, and corresponding to the number of the retransmission attempts made previously,.]. whereby, if the first node has .Iadd.not .Iaddend.captured the channel, the backoff time is .Iadd.selected from .Iaddend.a prescribed .Iadd.range of .Iaddend.backoff .[.time.]. .Iadd×Iaddend.;   if the first node has .[.not.]. captured the channel, the backoff time .[.before making at least a first of the retransmission of the attempts.]. is selected .[.to be r slot times longer than the prescribed backoff time.]. .Iadd.from a different range of backoff times including a longer backoff time than those included in said prescribed range.Iaddend.;   means for monitoring the channel for activity from .[.the first node.]. .Iadd.other nodes .Iaddend.of the network;   a backoff timer to provide .[.a.]. .Iadd.the selected .Iaddend.backoff time for retransmission of the .[.second.]. .Iadd.first .Iaddend.packet;   means for operating the backoff timer when the channel is idle;   means for halting the backoff timer during any period in which the channel is not idle; and   means for attempting retransmission of the .[.second.]. .Iadd.first .Iaddend.packet when the backoff timer expires.   
     
     
       7. For use in a first node in a network having a plurality of nodes employing Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol for channel access, an apparatus for improving the fairness of access to a channel, comprising: means for sensing whether or not the first node has captured a channel;   means for sensing a collision between a first packet transmission by the first node and a second packet transmission by a second node on the network;   means, in response to sensing the collision, for selecting a backoff time to wait before making each of a number of retransmission attempts of the .[.second.]. .Iadd.first .Iaddend.packet, .[.the selected backoff time between each said attempt and the immediately preceding attempt conforming to a selected integral multiple r of a slot time, where r is a positive integer, and corresponding to the number of the retransmission attempts made previously,.]. whereby, if the first node has .Iadd.not .Iaddend.captured the channel, the backoff time is .Iadd.selected from .Iaddend.a prescribed .Iadd.range of .Iaddend.backoff .[.time.]. .Iadd×Iaddend.;   if the first node has .[.not.]. captured the channel, the backoff time .[.before making at least a first of the retransmission attempts.]. is selected .[.to be r slot times longer than the prescribed backoff time.]. .Iadd.from a different range of backoff times including a longer backoff time than those included in said prescribed range.Iaddend.;   a backoff timer to provide .[.a.]. .Iadd.the selected .Iaddend.backoff time for retransmission of the .[.second.]. .Iadd.first .Iaddend.packet;   means for determining if the .[.second.]. .Iadd.first .Iaddend.node is waiting a first backoff time .Iadd.selected from said different range .Iaddend.for a first retransmission attempt of the .[.second.]. .Iadd.first .Iaddend.packet;   means, in response to a determination that the .[.second.]. .Iadd.first .Iaddend.node is waiting the first backoff time, for monitoring the channel for activity from .[.the first node.]. .Iadd.other nodes .Iaddend.on the network, operating .[.a.]. .Iadd.the .Iaddend.backoff timer when the channel is idle, and halting the backoff timer during any period in which the channel is not idle;   means, in response to a determination that the .[.second.]. .Iadd.first .Iaddend.node is not waiting the first backoff time, for operating .[.a.]. .Iadd.the .Iaddend.backoff timer; and   means for attempting retransmission of the .[.second.]. .Iadd.first .Iaddend.packet when the backoff timer expires.   
     
     
       8. The apparatus as in claim 6 or 7 wherein the means for monitoring the channel for activity from .[.second node.]. .Iadd.other nodes .Iaddend.further comprises means for recognizing when .[.second.]. .Iadd.another .Iaddend.node is transmitting on the channel. 
     
     
       9. The apparatus as in claim 6 or 7 wherein the means for monitoring the channel for activity from .[.second node.]. .Iadd.other nodes .Iaddend.further comprises means for recognizing when a collision is occurring on the channel. 
     
     
       10. The apparatus as in claim 6 or 7 wherein the means for monitoring the channel for activity from .[.the second node.]. .Iadd.other nodes .Iaddend.further comprises means for recognizing when .[.second.]. .Iadd.another .Iaddend.node is transmitting or a collision is occurring on the channel. 
     
     
       11. For use in a first node in a network having a plurality of nodes employing Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol for channel access, a method for improving the fairness of access to a channel, comprising the steps of: sensing whether or not the first node has captured a channel;   sensing a collision between a first packet transmission by the first node and a second packet transmission by a second node on the network;   after sensing the collision, examining the contents of a data field in .[.second.]. .Iadd.the first .Iaddend.packet .[.requiring retransmission.]. to determine whether a special backoff algorithm should be used for .[.the second.]. .Iadd.retransmission of the first .Iaddend.packet;   in response to a determination that the special backoff algorithm should be used, selecting a backoff time to wait before making each of a number of retransmission attempts of the .[.second.]. .Iadd.first .Iaddend.packet, .[.the selected backoff time between each said attempt and the immediately preceding attempt conforming to a selected integral multiple r of a slot time, where r is a positive integer, and corresponding to the number of the retransmission attempts made previously,.]. whereby, if the first node has .Iadd.not .Iaddend.captured the channel, the backoff time is a prescribed backoff time;   if the first node has .[.not.]. captured the channel, the backoff time before at least a first of the retransmission attempts is selected to be .[.r slot times.]. longer than the prescribed backoff time, and wherein the backoff time before a second retransmission .Iadd.attempt .Iaddend.of the .[.second.]. .Iadd.first .Iaddend.packet .[.attempt.]. is selected to be .[.r slot times.]. shorter than the prescribed backoff time, monitoring the channel for activity from .[.the second node.]. .Iadd.other nodes .Iaddend.on the network, operating a backoff timer .Iadd.to provide the selected backoff time .Iaddend.when the channel is idle, and halting the backoff timer during any period in which the channel is not idle;   in response to a determination that the special backoff algorithm should not be used, operating a backoff timer .Iadd.to provide the prescribed backoff time.Iaddend.; and attempting retransmission of the .[.second.]. .Iadd.first .Iaddend.packet when the backoff timer expires.