Multiaccess carrier sensing network communication protocol with priority messages

• US 5,319,641 A
• Filed: 12/03/1990
• Issued: 06/07/1994
• Est. Priority Date: 12/03/1990
• Status: Expired due to Term

• Current Assignee: Echelon Systems Corp.
• Original Assignee: Echelon Systems Corp.
• Inventors: Riley, Glen M., Dolin, Robert A. Jr., Fridrich, Marek J.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US07/621,737
• Time in Patent Office: 1,282 Days
• Field of Search: 370/85.1, 370/85.2, 370/85.3, 370/85.6, 370/60, 370/94.1, 370/93, 34/825.5, 34/825.51
• US Class Current: 370/447
• CPC Class Codes: G05D 23/1905 associated with tele control
• CPC Class Codes: H04L 12/40156 by using dedicated slots associated with a priority level
• CPC Class Codes: H04L 12/40163 by assigning priority to messages according to a message field
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]

Abstract

An improved network for communication of message packets. The network of the present invention implements an improved collision avoidance, detection and backoff system for communication on a media between nodes. The apparatus calculates a time period P after detecting the media is idle using a formula F which is a function of a pseudo-random delay factor T. If the media remains idle during the time period P, the device may transmit a message. The apparatus further has the ability to assign messages as being either priority or non-priority messages. Priority messages may be transmitted during priority message slots preassigned to transmitting nodes. Non-priority message contend for the media during a period of time following the period set for transmission of priority messages.

Claims

1. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, comprising the steps of:

a) a first device preparing a first message packet for transmission on said medium;

b) said first device sensing said medium to determine if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F including as a factor a pseudo-random delay factor T, said pseudo-random delay factor T representing an integer number of time slots S, said integer number of time slots S varying dependent on backlog of the network;

e) said first device monitoring said medium during said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle during said time period P.

2. The method as recited by claim 1 wherein said pseudo-random delay factor T is specified as an integer number.

3. The method as recited by claim 2 wherein said backlog is estimated by said first device.

4. The method as recited by claim 1 wherein said medium is considered idle when:

a) said medium is in a first binary state; and

b) said first device has not detected a transition on said medium for a time period Beta1.

5. The method of claim 4 wherein said medium comprises twisted pair wiring.

6. The method as recited by claim 5 wherein said pseudo-random delay factor T is representative of an integer number of time slots S, each of said time slots S of duration Beta2, where Beta2 meets the constraint:

space="preserve" listing-type="equation">Beta2>

(2*Tau.sub.p)+Tau.sub.m

and where Tau_p is representative of a physical propagation of said medium and Tau_m is representative of a detection and turnaround delay characteristic of said first device.

7. The method as recited by claim 6 wherein said time period Beta1 is limited by the constraint:

space="preserve" listing-type="equation">Beta1>

(2*Tau.sub.p)+Tau.sub.m

and, where Tau_p is representative of a physical propagation of said medium and Tau_m is representative of a detection and turnaround delay characteristic of said first device.

8. The method as recited by claim 1 wherein said medium comprises power lines.

9. The method as recited by claim 1 wherein said medium comprises radio waves.

10. The method as recited by claim 1 wherein said medium comprises microwaves.

11. The method as recited by claim 1 wherein said messages transmitted on said medium are encoded utilizing differential Manchester coding and the medium is considered idle during periods when the voltage remains level during both a first and second interval of a clock cycle.

12. The method as recited by claim 1 wherein said pseudo-random delay factor T is calculated including a backlog factor BL, said backlog factor BL based on the backlog of messages for transmission on said medium.

13. The method as recited by claim 12 wherein message packets are classified as either priority message packets or a non-priority message packets.

14. The method as recited by claim 13 wherein said plurality of devices in a network further comprises a second device, a priority slot is preassigned to said first device, and message packets classified as priority are communicated onto the medium during said priority slot.

15. The method as recited by claim 14 wherein, for non-priority messages, said backlog factor BL is in the range of (N+1) . . . (N+1+(w_base *BL))where:

N is the number of priority slots;

w_base is a predetermined number of time slots S; and

BL is a backlog factor based on an estimated backlog of messages for transmission on said medium.

16. The method as recited by claim 15 wherein w_base is equal to 16.

17. The method as recited by claim 12 wherein said backlog factor BL calculated by said first device, said backlog factor BL being incremented each time a message packet is received or transmitted by said first device and said backlog factor BL being decremented each time a busy cycle is detected on said medium by said first device.

18. The method as recited by claim 17 wherein said backlog factor BL is incremented by an estimate of the number of messages to be generated responsive to the received message packet.

19. The method as recited by claim 18 wherein said received message packet includes an estimate of the number of messages to be generated responsive to the received message packet.

20. The method as recited by claim 1 wherein said plurality of devices in a network further comprises a second device, a priority slot is preassigned to said first device, and said first device transmits priority message packets during said priority slot.

21. In a network of devices, said network for facilitating sending and receiving of messages between said devices, said network comprising a medium for transmitting said messages, an improved method for managing message traffic on said medium comprising the steps of:

a) a first of said devices monitoring said medium;

b) said first device preparing a message for transmission on said medium, said first device continuing to monitor said medium during said step (b);

c) said first device sensing said medium is idle;

d) said first device waiting a time period P after completing said step (c), said time period P calculated utilizing a backlog counter BL as a factor, said first device continuing to monitor said channel during said time period P;

e) said first device transmitting said message on said medium if said medium remains idle during said time period P.

22. The improvement as recited by claim 21 further comprising the step of initiating said backlog counter BL to a first value at initialization of said network.

23. The improvement as recited by claim 21 further comprising the step of incrementing said backlog counter BL based on information received by said first device detailing expected message transmissions on said medium.

24. The improvement as recited by claim 23 wherein said information detailing expected message transmissions a field N contained in the header of a transmitted message M, said field N designating a number of expected packets to be generated as a result of transmission of said message M.

25. The improvement as recited by claim 24 wherein said step of incrementing said backlog counter BL is not carried out where said backlog counter BL exceeds a threshold.

26. The improvement as recited by claim 25 wherein said threshold is less than or equal to the number of nodes on said network.

27. The improvement as recited by claim 21 wherein said backlog counter BL is adjusted periodically based on feedback from said network.

28. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, said network comprising a plurality of devices including a first device and a second device;

independent of said second device said first device being preassigned a priority slot n for communication of priority messages, and independent of said first device said second device being preassigned a priority slot m for communication of priority messages, where m is not equal to n, said method of avoiding collisions comprising the steps of;

a) said first device preparing a first message packet for transmission on said medium, said first message being a priority message;

b) said first device sensing said medium to determine if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device continuing to monitor said medium for n-1 priority slots;

e) said first device communicating said message packet onto the medium during said priority slot n if said medium remains idle during priority slots 1 through n-1.

29. The method as recited by claim 28 an indicator is set in said first message packet to indicate the message is a priority message.

30. A networked communication system having at least a first device and a second device, said first device coupled with said second device over a medium, said first device comprising:

(a) means for preparing a first message packet for transmission on said medium;

(b) means for sensing said medium to determine if said medium is idle;

(c) means for computing a time period P after detecting said medium is idle, said means for computing said time period P using a formula F, said formula F including as a factor a pseudo-random delay factor T;

said pseudo-random delay factor T representing and integer number of time slots S, said integer number of time slots S varying dependent on backlog of the network; and

(d) means for transmitting said first message packet onto said medium if said medium remains idle during said time period P.

31. In a network of devices, said network for facilitating sending and receiving of messages between said device, said network including a medium for transmitting said messages, an improved means for managing message traffic on said medium wherein a first of said devices comprises:

(a) means for monitoring said medium to determine if said medium is idle;

(b) means for preparing a first message packet for transmission on said medium;

(c) means for calculating a time period P after determining said medium is idle, said time period P utilizing a backlog counter BL as a factor; and

(d) means for transmitting said first message packet on said medium if said medium remains idle during said time period P.

32. A networked communication system including a medium for coupling in communication at least a first device and a second device;

said first device comprising;

(a) means for storing a preassigned priority slot number N, said preassigned priority slot number N being preassigned to said first device;

(b) means for preparing a first message packet for transmission on said medium, said first message packet being a priority message;

(c) means for sensing said medium to determine if said medium is idle;

(d) means for monitoring said medium during a plurality of priority slots 1 through N-1; and

(e) means for communicating said first message packet onto said medium during priority slot N if said medium remains idle during said plurality of priority slots 1 through N-1;

and said second device comprising;

(f) means for storing a preassigned priority slot number M, where M is not equal to N, said preassigned priority slot number M being preassigned to said second device.

33. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, comprising the steps of:

a) a first device preparing a first message packet for transmission on said medium;

b) said first device sensing said medium to determined if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F varies dependent on the backlog;

e) said first device continuing to monitor said medium during said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle during said time period P.

34. The method as recited by claim 33 wherein said backlog is estimated by said first device.

36. The method as recited by claim 34 wherein said time period Beta1 is limited by the constraint:

space="preserve" listing-type="equation">Beta1>

(2*Tau.sub.p)+Tau.sub.m

and, where Tau_p is representative of a physical propagation of said medium and Tau_m is representative of a detection and turnaround delay characteristic of said first device.

35. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, comprising the steps of:

a) a first device preparing a first message packet for transmission on said medium;

b) said first device sensing said medium to determine if said medium is idle, as determined when said medium is in a first binary state and said first device has not detected a transition on said medium for a time period Betal;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F including as a factor a pseudo-random delay factor T, said pseudo-random delay factor T representing an integer number of time slots S, each of said time slots S of duration Beta2, where Beta2 meets the constraint;

space="preserve" listing-type="equation">Beta2>

(2*Tau.sub.p)+Tau.sub.m

and where Tau_p is representative of a physical propagation of said medium and Tau_m is representative of a detection and turnaround delay characteristic of said first device;

e) said first device continuing to monitor said medium during said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle during said time period P.

37. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, said network comprising a first device and a second device, comprising the steps of:

a) said first device preparing a first message packet for transmission on said medium, said first message packet being classified as either a priority message packet or a non-priority message packet, independent of said second device said first device being preassigned a priority slot, and message packets classified as priority are communicated onto said medium during said priority slot;

b) said first device sensing said medium to determine if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F including as a factor a pseudo-random delay factor T, said pseudo-random delay factor T calculated including a backlog factor BL, said backlog factor BL is based on the estimated backlog of messages for transmission on said medium and said backlog factor BL is in the range of (N+1) . . . (N+1+(w_base *BL) where;

N is the number of said priority slots; and

w_base is a predetermined number of priority slots S;

e) said first device continuing to monitor said medium during said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle during said time period P.

38. The method as recited by claim 37 wherein w_base is equal to 16.

39. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, comprising the steps of:

a) a first device preparing a first message packet for transmission on said medium;

b) said first device sensing said medium to determine if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F varying depending on a backlog factor BL, said backlog factor BL based on the backlog of messages for transmission on said medium, said backlog factor BL being incremented each time a message packet is received or transmitted by said first device, said backlog factor BL being incremented by an estimate of the number of messages to be generated responsive to a received message packet, said backlog factor BL being decremented each time a busy cycle is detected on said medium by said first device;

e) said first device continuing to monitor said medium during said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle during said time period P.

40. The method as recited by claim 39 wherein said received message packet includes an estimate of the number of messages to be generated responsive to the received message packet.

41. In a network of devices, said network for facilitating sending and receiving of messages between said devices, said network comprising a medium for transmitting said messages, an improved method for managing message traffic on said medium comprising the steps of:

(a) a first of said devices initiating said backlog counter BL to a first value at initialization of said network;

(b) said first device monitoring said medium;

(c) said first device preparing a message for transmission on said medium, said first device continuing to monitor said medium during said step (b);

(d) said first device sensing said medium is idle;

(e) said first device waiting a time period P after completing said step (c), said time period P calculated utilizing a backlog counter BL as a factor, said first device continuing to monitor said channel during said time period P;

(f) said first device transmitting said message on said medium if said medium remains idle during said time period P.

42. In a network of devices, said network for facilitating sending and receiving of messages between said devices, said network comprising a medium for transmitting said messages, an improved method for managing message traffic on said medium comprising the steps of:

(a) a first of said devices monitoring said medium;

(b) said first device preparing a message for transmission on said medium, said first device continuing to monitor said medium during said step (b);

(c) said first device sensing said medium is idle;

(d) said first device waiting a time period P after completing said step (c), said time period P calculated utilizing a backlog counter BL as a factor, said first device continuing to monitor said channel during said time period P;

(e) said first device incrementing said backlog counter BL based on information received by said first device detailing expected message transmissions on said medium;

(f) said first device transmitting said message on said medium if said medium remains idle during said time period P.

43. The improvement as recited by claim 42 wherein said information detailing expected message transmissions a field N contained in the header of a transmitted message M, said field N designating a number of expected packets to be generated as a result of transmission of said message M.

44. The improvement as recited by claim 43 wherein said step of incrementing said backlog counter BL is not carried out where said backlog counter BL exceeds a threshold.

45. The improvement as recited by claim 44 wherein said threshold is less than or equal to the number of nodes on said network.

46. The improvement as recited by claim 45 wherein said backlog counter BL is adjusted periodically based on feedback from said network.

47. A method of avoiding data collisions in a medium connecting a plurality of devices in a network, said network comprising a plurality of devices including a first and a second device;

said first device being preassigned a priority slot n for communications of priority messages, and said second device being preassigned a priority slot m for communication of priority messages, where m is not equal to n, said method of avoiding collisions comprising the steps of;

(a) said first device preparing a first message packet for transmission on said medium, said first message being a priority message, said first message having an indicator set to indicate said first message is a priority message;

(b) said first device sensing said medium to determine if said medium is idle;

(c) said first device sensing said medium is idle;

(d) said first device continuing to monitor said medium for n-1 priority slots;

(e) said first device communicating said message packet onto the medium during said priority slot n if said medium remains idle during priority slots 1 through n-1.

48. A method for avoiding data collisions in a medium connecting a plurality of devices in a network, comprising the steps of:

a) a first device preparing a first message packet for transmission on said medium;

b) said first device sensing said medium to determine if said medium is idle;

c) said first device sensing said medium is idle;

d) said first device computing a time period P after detecting said medium is idle using a formula F, said formula F including as a factor a pseudo-random delay factor T, said pseudo-random delay factor T representing an integer number of time slots S, said integer number of time slots S varying dependent on backlog of the network;

e) said first device monitoring said medium after said time period P;

f) said first device transmitting said first message packet onto said medium if said medium remains idle after said time period P.