Method and apparatus for prioritizing traffic in half-duplex networks

• US 5,852,723 A
• Filed: 08/06/1996
• Issued: 12/22/1998
• Est. Priority Date: 08/06/1996
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Kalkunte, Mohan, Kadambi, Jayant, Merchant, Shashank, Mangin, Jim
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US08/692,689
• Time in Patent Office: 868 Days
• Field of Search: 395/200.65, 370/229, 370/237, 370/416, 370/418, 370/454, 370/455, 370/459, 370/447, 370/448, 370/461, 370/462
• US Class Current: 709/235
• CPC Class Codes: H04L 12/40156 by using dedicated slots associated with a priority level
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 2012/6435 Bus
• CPC Class Codes: H04L 2012/6448 Medium Access Control [MAC]
• CPC Class Codes: H04L 2012/6454 Random, e.g. Ethernet
• CPC Class Codes: H04L 2012/6464 Priority

Abstract

Collision delay intervals are modified in Ethernet network devices transmitting priority data requiring a guaranteed latency by multiplying an integer multiple number of slot times with a fractional coefficient. A network device having priority data for transmission uses the conventional Truncated Binary Exponential Backoff (TBEB) algorithm during the first access attempt to calculate a collision delay interval from a randomly selected integer multiple of slot times. If the network device encounters another collision, the next randomly selected integer multiple of slot times is multiplied by the fractional coefficient. Use of the fractional coefficient during collision mediation on a half-duplex Ethernet network provides a bounded access latency for real-time and multimedia applications by granting the network device a higher probability of successfully accessing the network media.

Claims

1. A method in a network station of mediating collisions on network media, comprising:

sensing a collision on the media;

determining a priority of data to be transmitted by the network station;

determining a slot time interval by multiplying a predetermined slot time interval with (1) an integer randomly selected from a range of integers calculated from an exponential number of access attempts by the network station, and (2) a selected coefficient having a value corresponding to the determined priority; and

attempting access of the media in response to the detected collision and after the slot time interval.

2. The method of claim 1, wherein the determining step comprises:

storing a plurality of priority coefficients as said selected coefficient in said network station, each having a unique fractional value;

reading a priority value from a data packet to be transmitted on the media; and

selecting one of said priority coefficients in response to the read priority value.

3. The method of claim 2, wherein the storing step comprises receiving data packets carrying the priority coefficients from a second network station.

4. The method of claim 1, wherein the selecting step comprises selecting the coefficient based on the number of access attempts.

5. A method in a network station of mediating collisions on network media, comprising:

sensing a collision on the media;

determining a priority of data to be transmitted by the network station;

determining a slot time interval in accordance with (1) an integer randomly selected from a range of integers calculated from an exponential number of access attempts by the network station, and (2) a priority coefficient having a value corresponding to the determined priority; and

attempting access of the media in response to the detected collision and after the slot time interval, wherein the determining step further comprises;

setting the priority coefficient equal to one if the number of access attempts by the network stations is one; and

setting the priority coefficient to a value less than one and greater than zero if the number of access attempts by the network station is greater than one and the determined priority is a high priority.

6. The method of claim 5, wherein the network has a data rate of 10 megabits per second and a predetermined delay interval, used to calculate the slot time interval, that equals 51.2 microseconds.

7. The method of claim 5, wherein the network has a data rate of 100 megabits per second and a predetermined delay interval, used to calculate the slot time interval, that equals 5.12 microseconds.

8. The method of claim 5, wherein the network has a data rate of 1000 megabits per second and a predetermined delay interval, used to calculate the slot time interval, that has a duration equal to four thousand ninety-six (4096) bit times.

9. A method in a network station of mediating collisions on network media, comprising:

sensing a collision on the media;

determining a collision delay interval comprising;

(1) randomly selecting a first integer from a range of integers calculated from an exponential number of access attempts by a network station,

(2) first determining a number of collisions encountered by the network station,

(3) multiplying a predetermined slot time with the first integer to obtain an integer multiple slot time interval;

(4) if the number of collisions equals one, using the integer multiple slot time interval as the collision delay interval;

(5) second determining if data for transmission has a priority status;

(6) if the number of collisions is greater than one and the data has said priority status, multiplying the integer multiple slot time interval with a fractional coefficient to obtain the collision delay interval; and

attempting access of the media following the collision delay interval after the detected collision.

10. The method of claim 9, wherein the range of integers has a maximum value of 2¹⁰ -1.

11. The method of claim 10, wherein the network has a data rate of 10 megabits per second and the predetermined delay interval equals 51.2 microseconds.

12. The method of claim 10, wherein the network has a data rate of 100 megabits per second and the predetermined delay interval equals 5.12 microseconds.

13. The method of claim 10, wherein the network has a data rate of 1000 megabits per second and the predetermined delay interval has a duration equal to four thousand ninety six (4096) bit times.

14. A network interface for connection with network media, comprising:

a buffer storing data having an identified priority for transmission on the media;

a collision sensor sensing a collision on the media;

a delay time calculator selectively calculating a delay time by multiplying a selected integer multiple of slot times with a fractional coefficient in response to a number of access attempts by the network interface and the identified priority; and

a media access device attempting access of the media in response to the sensed collision of the media and after said delay time.

15. The network interface of claim 14, wherein the delay time calculator calculates said delay time as said integer multiple of a predetermined delay if the identified priority is low, the integer multiple randomly selected from an integer range calculated from an exponential number of the access attempts.

18. The network interface of claim 14, wherein the delay time calculator selects one of a plurality of fractional values as said fractional coefficient based on the number of access attempts.

16. A network interface for connection with network media, comprising:

a buffer storing data having an identified priority for transmission on the media;

a collision sensor sensing a collision on the media;

a delay time calculator selectively calculating a delay time in response to a number of access attempts by the network interface and the identified priority; and

a media access device attempting access of the media in response to the sensed collision of the media and after said delay time,

wherein the delay time calculator calculates said delay time as an integer multiple of a predetermined delay if the identified priority is low, the integer multiple randomly selected from an integer range calculated from an exponential number of the access attempts,

wherein the delay time calculator calculates said delay time as a fraction of said integer multiple of said predetermined delay if the identified priority is low and the number of access attempts is greater than one.

17. The network interface of claim 16, further comprising a register storing said fraction.

19. A method in a network station of accessing a network media, comprising:

transmitting a data packet carrying data requiring a bounded access latency;

sensing a collision on the media;

determining a collision delay interval by multiplying a predetermined delay interval with (1) an integer randomly selected from a range of integers calculated from an exponential number of access attempts by the network station, and (2) a priority coefficient having a value less than one if the number of said access attempts is greater than one; and

attempting access of the media in response to the detected collision and after the collision delay interval.

20. The method of claim 19, wherein said data is multimedia data.

21. A method of limiting access latency during data transmission in a network station, comprising:

sensing a collision on a network media;

if a number of access attempts is one, determining a delay time by randomly selecting between zero and a predetermined slot time;

if the number of access attempts is greater than one, determining said delay time by (1) randomly selecting an integer, (2) multiplying the selected integer with the predetermined slot time, and (3) multiplying the selected integer multiple of slot times with a coefficient corresponding to an access latency variability; and

attempting access of the media in response to the detected collision and after the determined delay time.

22. The method of claim 21, wherein the coefficient has a value of one and corresponds to an unbounded access latency.

23. The method of claim 21, wherein the coefficient has a value greater than one and corresponds to a bounded access latency.

24. The method of claim 23, wherein the coefficient has a value of eight (8).