Method and apparatus for controlling latency and jitter in a local area network which uses a CSMA/CD protocol

• US 5,568,469 A
• Filed: 09/27/1994
• Issued: 10/22/1996
• Est. Priority Date: 09/27/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Hickey, John F., Lo, Lai-Chin, Sherer, William P.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/313,674
• Time in Patent Office: 756 Days
• Field of Search: 370/17, 370/44, 370/48, 370/79, 370/85.2, 370/85.3, 370/85.6, 370/85.13, 370/93, 370/94.3, 370/94.1, 370/105.3, 370/85.1, 340/825.5, 340/825.51, 364/240.8, 364/241.2, 364/241.4, 364/241.5
• US Class Current: 370/448
• CPC Class Codes: H04L 12/4015 by scheduling the transmission of messages at the communication node
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]

Abstract

An Ethernet network or other CSMA/CD network includes hub adaptors that are modified to provide a known bounded low maximum access latency. The modified adaptors maintain a state variable whose values indicates whether the last operation by the adaptor was a transmit or a receive. In the case where the last operation was a receive, the adaptor transmits a packet with a minimum or zero backoff and as an option with a reduced interpacket gap. In the case where the last operation was a transmit, the adaptor waits before transmitting a packet a period of time that allows the other node on the channel to transmit a packet if the other node has a packet to transmit.

Claims

1. In a carrier-sense/collision-detect network, a method for transferring data over a communication channel between a first node and a second node whereby said first node ensures fairness of access and low bounded maximum access latency, comprising the steps of:

forming the data into packets;

at said first node, detecting the state of a last action state variable;

if the last action variable indicates the last action performed by said first node was a receive action, transmitting a packet from said first node to said second node according to a last-action-equals-receive protocol such that said packet from said first node is given priority over a packet originating at said second node;

if the last action variable indicates the last action performed by said first node was a transmit action, transmitting a subsequently available packet from said first node to said second node according to a last-action-equals-transmit protocol such that transmissions from said first node are deferred if a packet from said second node is detected on said communication channel thereby giving priority to a packet originating at said second node; and

setting said last action state variable to conform to the last action performed by said first node on said channel.

2. The method according to claim 1 further comprising the step of:

initiating a timer whenever said last action state variable indicates the last action at said first node was a transmit and resetting said last action state variable to receive whenever when said timer expires if there has been no traffic on said channel.

3. The method according to claim 1 wherein said last-action-equals-receive protocol comprises the steps of:

waiting a predetermined minimum interpacket gap time;

transmitting said packet from said first node while listening for a collision;

upon detection of a collision, repeating transmission of said packet with a backoff period of zero for a predetermined number of attempts;

at the last attempt of said predetermined number of attempts, delaying transmission of said packet so as to determine if said second node is transmitting with a backoff of zero;

if said second node is transmitting with a backoff period of zero, discarding said packet; and

if no collision is detected on any one attempted transmission, completing transmission of said packet.

4. The method according to claim 1 wherein said last-action-equals-transmit protocol comprises the steps of:

determining whether said second node has experienced a collision in attempting to transmit said packet to said first node;

if said second node has experienced a collision, waiting a backoff allowance time substantially equal to the maximum possible backoff time of said second node and when said time expires or said packet is received from said second node, resetting said last action variable to receive and transmitting according to said last-action-equals-receive protocol;

if said second node has not experienced a collision, waiting an interpacket gap time before transmitting a packet;

if a packet is received at said first node during said interpacket gap time, resetting said last action variable to receive and transmitting according to said last-action-equals-receive protocol;

transmitting said packet from said first node to said second node; and

if a collision occurs during transmission of said packet, waiting a backoff allowance time substantially equal to a maximum possible backoff time of said second node and upon expiration of said time or upon receipt of a packet from said second node, resetting said last action variable to receive and then transmitting packets according to said last-action-equals-receive protocol.

5. The method according to claim 1 wherein said last-action-equals-transmit protocol comprises the steps of:

transmitting the packet from said first node to said second node so long as no collision has occurred with a packet from said second node since the last time said second node successfully transmitted a packet; and

if said second node has experienced a collision, waiting a backoff allowance time substantially equal to a maximum possible backoff time of said second node and when said time expires or a packet is received from said second node, resetting said last action variable to receive and transmitting according to said last-action-equals-receive protocol.

6. The method according to claim 1 further comprising the step of monitoring at said first node a number of collisions experienced by said second node when said second node is attempting to transmit a packet and using said number of collisions to determine a backoff allowance time.

7. The method according to claim 3 wherein said last-action-equals-receive protocol further comprises the step of reducing said predetermined minimum interpacket gap time.

8. The method according to claim 4 wherein said last-action-equals-transmit protocol further comprises the step of extending the interpacket gap between back-to-back packet transmissions.

9. The method according to claim 4 wherein said last-action-equals-transmit protocol further comprises the steps of:

setting an interpacket gap reduction timer when the last action variable is initially set to transmit; and

upon expiration of said timer, reducing an interpacket gap time between back-to-back packet transmissions from said first node until a collision is detected or a packet is received at said first node.

10. The method according to claim 1 wherein:

said packets contain information indicating that said packets have one of at least two different levels of priority;

and further comprising the steps of;

at said first node, detecting the priority of a packet to be transmitted;

at said first node, detecting the priority of a packet being received;

at said first node, preempting an operation for a lower priority packet when a competing packet has a higher priority; and

at said first node, halting preemption of a lower priority packet when a maximum allowable latency limit of said lower priority packet is reached.

11. In a carrier-sense/collision-detect network, a method for transferring data over a communication channel between a first node and a second node ensuring fairness of access and low bounded maximum access latency, comprising the steps of:

at said first node, detecting the state of a mode variable;

if the mode variable indicates the first node is in a transmit mode, transmitting data from said first node to said second node according to a last-action-equals-receive protocol such that said data from said first node is given priority over data originating at said second node;

if the mode variable indicates the first node is in a receive mode, transmitting data from said first node to said second node according to a last-action-equals-transmit protocol such that said first node defers data transmission when it detects data from said second node; and

changing the value of mode variable from transmit to receive according to a predetermined timing schedule.

12. A network for the exchange of digital data comprising;

a first node having a plurality of first node adapters;

a plurality of second nodes, each having a second node adaptor and each connected to a first node adaptor by a private communication channel, wherein each said first node adaptor comprises;

means for receiving data from said first node for transmission on its connected communication channel to its connected second node;

means for transmitting said data on said channel;

means for detecting data on said channel from said second node;

means for receiving said data from said channel;

means for transferring said data to said first node;

means for detecting collisions on said channel while said first node adapter is transmitting on said channel;

state variable means for storing the state of the last action performed by said adaptor on said communications channel; and

control means responsive to the state of said state variable means and said detecting means for controlling the transmitting of said data on said communications channel and the receiving of said packets from said channel.

13. The network according to claim 12 wherein said second node adaptor is a standard 802.3 CSMA/CD adaptor.

14. A method for enabling a plurality of 802.3 ethernet standard workstations to send and receive multi-media data and ensuring fairness of access and low bounded maximum access latency, comprising the steps of:

connecting said standard 802.3 workstations to a multi-media enabled hub via a plurality of private point-to-point transmission channels;

transmitting packet data between a first workstation and a second workstation by first transmitting a packet from said first workstation to said hub and then transmitting said packet from said hub to said second workstation; and

using said hub to ensure low bounded access latency by said first node alternating its packet protocol such that said hub transmits a plurality of packets according to a protocol favoring said packets and then transmits a second plurality of packets according to a protocol such that said hub defers to any packets being sent by said workstations.