Method and apparatus for dynamic source routing in ad hoc wireless networks

• US 6,678,252 B1
• Filed: 10/28/1999
• Issued: 01/13/2004
• Est. Priority Date: 10/28/1999
• Status: Expired due to Term

• Current Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Cansever, Derya H.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Emdadi, Kamran
• Application Number:
  US09/428,502
• Time in Patent Office: 1,538 Days
• Field of Search: 370/248, 370/252, 370/255, 370/328, 370/394, 370/395.41, 370/395.4, 370/253, 370/351, 370/400, 370/468, 370/431
• US Class Current: 370/253
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

This invention addresses Media Access Control (MAC) routing protocol that accounts for QoS constraints for IP traffic in MANETs. Methods and systems consistent with this example use a decentralized algorithm that is run by the participating nodes with a minimal amount of control packets adding to network overhead. Methods and systems consistent with this invention calculate a maximum available bandwidth (MAB) metric used in the MAC protocol. The MAB, along with other information may be shared among nodes in the MANET. The shared information is also used in computing the traffic loads in other parts of the MANET, and in identifying the available links that could support the QoS requirements. Then, the information concerning available links is used in the MANET routing algorithm.

Claims

1. A method for managing data traffic in a network comprised of a plurality of nodes including a first node having at least one neighboring node, the method performed by the first node and comprising:

determining a value indicative of a maximum unused bandwidth of the first node;

receiving from the at least one neighboring node data indicative of at least one maximum unused bandwidth of the at least one neighboring node;

calculating a value indicative of a maximum available bandwidth of the first node from the value indicative of the maximum unused bandwidth of the first node and the received data indicative of the at least one maximum unused bandwidth; and

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node.

2. The computer-readable medium of claim 1, including receiving data during an air time of the at least one neighboring node.

3. The computer-readable medium of claim 2, including calculating a value indicative of a start tag.

4. The computer-readable medium of claim 2, including calculating a value indicative of a finish tag.

5. The method of claim 1, comprising

calculating at least one value indicative of the maximum available bandwidth of the at least one neighboring node from the received data.

6. The method of claim 5, including

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node and the at least one maximum available bandwidth of the at least one neighboring node.

7. The method of claim 1, including broadcasting data during the air time according to a packet scheduling algorithm.

8. The method of claim 1, including

receiving a route request packet having a requested bandwidth;

comparing the requested bandwidth to the calculated value indicative of the maximum available bandwidth.

9. The method of claim 8, wherein comparing the requested bandwidth includes

granting the requested bandwidth if the requested bandwidth is less than or equal to the maximum available bandwidth of the first node.

10. The method of claim 8, wherein comparing the requested bandwidth includes denying the requested bandwidth if the requested bandwidth is greater than the maximum available bandwidth of the first node.

11. The method of claim 1, wherein allocating the air time comprises:

generating a first value indicative of a first packet to be transmitted in the network;

transmitting the first value indicative of the first packet to the plurality of nodes;

receiving a second value indicative of a second packet to be transmitted in the network; and

allocating the air time of the first packet based on the first value and the second value.

12. The method of claim 11, wherein the first value indicative of the first packet is a function of an arrival time of the first packet and a length of the first packet, and wherein the second value indicative of the second packet is a function of an arrival time of the second packet and a length of the second packet.

13. The method of claim 11, wherein the first value indicative of the first packet is a function of an estimate of a bandwidth required to support a flow of the first packet, and wherein the second value indicative of the second packet is a function of an estimate of a bandwidth required to support a flow of second the packet.

14. The method of claim 1, comprising

broadcasting data indicative of the maximum unused bandwidth of the first node to the at least one neighboring node.

15. The method of claim 14, wherein broadcasting occurs only when the maximum unused bandwidth of the first node changes.

16. The method of claim 1, comprising

broadcasting data indicative of the maximum available bandwidth of the first node to the at least one neighboring node.

17. The method of claim 1, comprising

receiving data, from the at least one neighboring node, indicative of the maximum available bandwidth of the at least one neighboring node.

18. The method of claim 1, comprising

broadcasting data indicative of a maximum bandwidth capacity of the first node to the at least one neighboring node.

19. The method of claim 1, comprising

receiving data indicative of at least one maximum bandwidth capacity of the at least one neighboring node.

20. The method of claim 1, including

receiving data indicative of at least one maximum bandwidth capacity of at least one node neighboring the at least one neighboring node.

21. The method of claim 1, including

receiving data indicative of at least one maximum unused bandwidth of at least one node neighboring the at least one neighboring node.

22. The method of claim 1, wherein the maximum unused bandwidth of the first node is a function of a maximum bandwidth capacity of the first node less a bandwidth of traffic generated at the first node and transit traffic through the first node.

23. The method of claim 22, wherein the maximum available bandwidth of the first node is a function of the maximum unused bandwidth of the first node less a bandwidth of traffic generated at the at least one neighboring node and transit traffic through the at least one neighboring node to a neighbor of the at least one neighboring node.

24. The method of claim 22, wherein the value indicative of the maximum unused bandwidth of the first node is defined by $\mathrm{MUB}=C-\sum _{}$

j

lj,

where

∀

jε

neighborhood of the first node;

MUB is the value indicative of the maximum unused bandwidth of the first node;

C is a value indicative of the maximum bandwidth capacity of the first node; and

l_j is a data traffic from the first node to a node j in bits per second.

25. The method of claim 22, wherein the value indicative of the maximum available bandwidth of the first node is defined by $\mathrm{MAB}=\mathrm{MUB}-\sum _{}$

j

∑

k

 



ljk,

where

∀

jε

neighborhood of the first node;

∀

kε

neighborhood of a node j;

MAB is the value indicative of the maximum available bandwidth of the first node;

MUB is the value indicative of the maximum unused bandwidth of the first node; and

l_jk is a data traffic from the node j to a node k in bits per second.

26. The method of claim 25, wherein allocating the air time includes

allocating the air time in proportion to the maximum bandwidth capacity of the first node minus the maximum available bandwidth of the first node.

27. A network comprising:

a plurality of nodes including a first node having at least one neighboring node;

a receiver in the first node for receiving, from the at least one neighboring node, data indicative of at least one maximum unused bandwidth of the at least one neighboring node;

a memory in the first node containing a program for determining a value indicative of a maximum unused bandwidth of the first node, calculating a value indicative of a maximum available bandwidth of the first node from the value indicative of the maximum unused bandwidth of the first node and the received data indicative of the at least one maximum unused bandwidth, and allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node; and

a processor in the first node for running the program.

28. The apparatus of claim 27, wherein the maximum unused bandwidth of the first node is a function of a maximum bandwidth capacity of the first node less a bandwidth of traffic generated at the first node and transit traffic through the first node.

29. The apparatus of claim 28, wherein the maximum available bandwidth of the first node is a function of the maximum unused bandwidth of the first node less a bandwidth of traffic generated at the at least one neighboring node and transit traffic through the at least one neighboring node to a neighbor of the at least one neighboring node.

30. The apparatus of claim 28, wherein the program determines the value indicative of the maximum unused bandwidth of the first node by $\mathrm{MUB}=C-\sum _{}$

j

lj,

where

∀

jε

neighborhood of the first node;

MUB is the value indicative of the maximum unused bandwidth of the first node;

C is a value indicative of the maximum bandwidth capacity of the first node; and

l_j is a data traffic from the first node to a node j in bits per second.

31. The apparatus of claim 29, wherein the program determines the value indicative of the maximum available bandwidth of the first node by $\mathrm{MAB}=\mathrm{MUB}-\sum _{}$

j

∑

k

 



ljk,

where

∀

jε

neighborhood of the first node;

MAB is the value indicative of the maximum available bandwidth of the first node;

∀

jε

neighborhood of a node j;

MUB is value indicative of the maximum unused bandwidth of the first node; and

l_jk is a data traffic from the node j to a node k in bits per second.

32. The apparatus of claim 31, wherein the program allocates the air time in proportion to the maximum bandwidth capacity of the first node minus the maximum available bandwidth of the first node.

33. The apparatus of claim 27, wherein the program

calculates at least one value indicative of the maximum available bandwidth of the at least one neighboring node from the received data.

34. The apparatus of claim 33, wherein the program

allocates an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node and the at least one maximum available bandwidth of the at least one neighboring node.

35. The apparatus of claim 27, including

a transmitter for broadcasting data during the air time according to a packet scheduling algorithm.

36. The apparatus of claim 27, wherein the receiver receives a route request packet having a requested bandwidth, and wherein the memory contains a program for comparing the requested bandwidth to the calculated value indicative of the maximum available bandwidth.

37. The apparatus of claim 27, wherein the program grants the requested bandwidth if the requested bandwidth is less than or equal to the maximum available bandwidth of the first node.

38. The apparatus of claim 27, wherein the program denies the requested bandwidth if the requested bandwidth is greater than the maximum available bandwidth of the first node.

39. The apparatus of claim 27, comprising

a transmitter for broadcasting data indicative of the maximum unused bandwidth of the first node to the at least one neighboring node.

40. The apparatus of claim 39, wherein the transmitter broadcasts only when the maximum unused bandwidth of the first node changes.

41. The apparatus of claim 27, comprising

a transmitter for broadcasting data indicative of the maximum available bandwidth of the first node to the at least one neighboring node.

42. The apparatus of claim 27, wherein the receiver receives data, from the at least one neighboring node, indicative of the maximum available bandwidth of the at least one neighboring node.

43. The apparatus of claim 27, comprising

a transmitter for broadcasting data indicative of a maximum bandwidth capacity of the first node to the at least one neighboring node.

44. The apparatus of claim 27, wherein the receiver receives data indicative of at least one maximum bandwidth capacity of the at least one neighboring node.

45. The apparatus of claim 27, wherein the receiver receives data indicative of at least one maximum bandwidth capacity of at least one node neighboring the at least one neighboring node.

46. The apparatus of claim 27, wherein the receiver receives data indicative of at least one maximum unused bandwidth of at least one node neighboring the at least one neighboring node.

47. A node having at least one neighboring node, the node comprising:

a receiver for receiving, from the at least one node neighboring node, data indicative of at least one maximum unused bandwidth of the at least one neighboring node;

a memory containing a program for determining a value indicative of a maximum unused bandwidth of the node, calculating a value indicative of a maximum available bandwidth of the node from the value indicative of the maximum unused bandwidth of the node and the received data indicative of the at least one maximum unused bandwidth, and allocating an air time for the node to transmit data as a function of the maximum available bandwidth of the node; and

a processor for running the program.

48. The node of claim 47, wherein the program further generates a first value indicative of a first packet to be transmitted in the network;

wherein the node further comprises a transmitter to transmit the first value indicative of the first packet to the at least one neighboring node;

wherein the receiver receives a second value indicative of a second packet to be transmitted in the network; and

wherein the program allocates the air time of the first packet based on the first value indicative of the first packet and the second value indicative of the second packet.

49. The node of claim 48, wherein the first value indicative of the first packet is a function of an arrival time of the first packet and a length of the first packet, and wherein the second value indicative of the second packet is a function of an arrival time of the second packet and a length of the second packet.

50. The node of claim 48, wherein the first value indicative of the first packet is a function of an estimate of a bandwidth required to support a flow of the first packet, and wherein the second value indicative of the second packet is a function of an estimate of a bandwidth required to support a flow of second the packet.

51. The apparatus of claim 47, wherein the maximum unused bandwidth of the first node is a function of a maximum bandwidth capacity of the first node less a bandwidth of traffic generated at the first node and transit traffic through the first node.

52. The apparatus of claim 51, wherein the maximum available bandwidth of the first node is a function of the maximum unused bandwidth of the first node less a bandwidth of traffic generated at the at least one neighboring node and transit traffic through the at least one neighboring node to a neighbor of the at least one neighboring node.

53. The apparatus of claim 51, wherein the program determines the value indicative of the maximum unused bandwidth of the node by $\mathrm{MUB}=C-\sum _{}$

j

lj,

where

∀

jε

neighborhood of the first node;

MUB is the value indicative of the maximum unused bandwidth of the node;

C is a value indicative of the maximum bandwidth capacity of the node; and

l_j is a data traffic from the node to a node j in bits per second.

54. The apparatus of claim 52, wherein the program determines the value indicative of the maximum available bandwidth of the node by $\mathrm{MAB}=\mathrm{MUB}-\sum _{}$

j

 



∑

k

 



ljk,

where

∀

jε

neighborhood of the first node;

∀

kε

neighborhood of a node j;

MAB is the value indicative of the maximum available bandwidth of the node;

MUB is the value indicative of the maximum unused bandwidth of the node; and

l_jk is a data traffic from the node j to a node k in bits per second.

55. The apparatus of claim 54, wherein the program allocates the air time in proportion to the maximum bandwidth capacity of the node minus the maximum available bandwidth of the node.

56. The apparatus of claim 47, wherein the program

calculates at least one value indicative of the maximum available bandwidth of the at least one neighboring node from the received data.

57. The apparatus of claim 56, wherein the program

allocates an air time for the node to transmit data as a function of the maximum available bandwidth of the node and the at least one maximum available bandwidth of the at least one neighboring node.

58. The apparatus of claim 47, including

a transmitter for broadcasting data during the air time according to a packet scheduling algorithm.

59. The apparatus of claim 47, wherein the receiver receives a route request packet having a requested bandwidth, and wherein the memory contains a program for comparing the requested bandwidth to the calculated value indicative of the maximum available bandwidth.

60. The apparatus of claim 59, wherein the program grants the requested bandwidth if the requested bandwidth is less than or equal to the maximum available bandwidth of the node.

61. The apparatus of claim 59, wherein the program denies the requested bandwidth if the requested bandwidth is greater than the maximum available bandwidth of the node.

62. The apparatus of claim 47, comprising

a transmitter for broadcasting data indicative of the maximum unused bandwidth of the node to the at least one neighboring node.

63. The apparatus of claim 62, wherein the transmitter broadcasts only when the maximum unused bandwidth of the node changes.

64. The apparatus of claim 47, comprising

a transmitter for broadcasting data indicative of the maximum available bandwidth of the node to the at least one neighboring node.

65. The apparatus of claim 47, wherein the receiver receives data, from the at least one neighboring node, indicative of the maximum available bandwidth of the at least one neighboring node.

66. The apparatus of claim 47, comprising

a transmitter for broadcasting data indicative of a maximum bandwidth capacity of the node to the at least one neighboring node.

67. The apparatus of claim 47, wherein the receiver receives data indicative of at least one maximum bandwidth capacity of the at least one neighboring node.

68. The apparatus of claim 47, wherein the receiver receives data indicative of at least one maximum bandwidth capacity of at least one node neighboring the at least one neighboring node.

69. The apparatus of claim 47, wherein the receiver receives data indicative of at least one maximum unused bandwidth of at least one node neighboring the at least one neighboring node.

70. A method for managing data traffic in a network comprised of a plurality of nodes including a first node having at least one neighboring node, the method comprising:

determining values indicative of a maximum unused bandwidth of the first node and the at least one neighboring node;

calculating a value indicative of a maximum available bandwidth of the first node from the values indicative of a maximum unused bandwidth of the first node and the at least one neighboring node; and

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the node.

71. The method of claim 70, including

receiving data indicative of at least one maximum bandwidth capacity of at least one node neighboring the at least one neighboring node.

72. The method of claim 70, including

receiving data indicative of at least one maximum unused bandwidth of at least one node neighboring the at least one neighboring node.

73. The method of claim 70, wherein the maximum unused bandwidth of the first node is a function of a maximum bandwidth capacity of the first node less a bandwidth of traffic generated at the first node and transit traffic through the first node.

74. The method of claim 73, wherein the maximum available bandwidth of the first node is a function of the maximum unused bandwidth of the first node less a bandwidth of traffic generated at the at least one neighboring node and transit traffic through the at least one neighboring node to a neighbor of the at least one neighboring node.

75. The method of claim 73, wherein the value indicative of the maximum unused bandwidth of the first node is defined by $\mathrm{MUB}=C-\sum _{}$

j

lj,

where

∀

jε

neighborhood of the first node;

MUB is the value indicative of the maximum unused bandwidth of the first node;

C is a value indicative of the maximum bandwidth capacity of the first node; and

l_j is a data traffic from the first node to a node j in bits per second.

76. The method of claim 74, wherein the value indicative of the maximum available bandwidth of the first node is defined by $\mathrm{MAB}=\mathrm{MUB}-\sum _{}$

j

 



∑

k

 



ljk,

where

∀

jε

neighborhood of the first node;

∀

kε

neighborhood of a node j;

MAB is the value indicative of the maximum available bandwidth of the first node;

MUB is the value indicative of the maximum unused bandwidth capacity of the first node; and

l_jk is a data traffic from the node j to a node k in bits per second.

77. The method of claim 76, wherein allocating the air time includes

allocating the air time in proportion to the maximum bandwidth capacity of the first node minus the maximum available bandwidth of the first node.

78. The method of claim 70, comprising

calculating at least one value indicative of the maximum available bandwidth of the at least one neighboring node from the received data.

79. The method of claim 78, including

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node and the at least one maximum available bandwidth of the at least one neighboring node.

80. The method of claim 70, including broadcasting data during the air time according to a packet scheduling algorithm.

81. The method of claim 70, including

receiving a route request packet having a requested bandwidth;

comparing the requested bandwidth to the calculated value indicative of the maximum available bandwidth.

82. The method of claim 81, wherein comparing the requested bandwidth includes

granting the requested bandwidth if the requested bandwidth is less than or equal to the maximum available bandwidth of the first node.

83. The method of claim 81, wherein comparing the requested bandwidth includes

denying the requested bandwidth if the requested bandwidth is greater than the maximum available bandwidth of the first node.

84. The method of claim 70, comprising

broadcasting data indicative of the maximum unused bandwidth of the first node to the at least one neighboring node.

85. The method of claim 84, wherein broadcasting occurs only when the maximum unused bandwidth of the first node changes.

86. The method of claim 70, comprising

broadcasting data indicative of the maximum available bandwidth of the first node to the at least one neighboring node.

87. The method of claim 70, comprising

receiving data, from the at least one neighboring node, indicative of the maximum available bandwidth of the at least one neighboring node.

88. The method of claim 70, comprising

broadcasting data indicative of a maximum bandwidth capacity of the first node to the at least one neighboring node.

89. The method of claim 70, comprising

receiving data indicative of at least one maximum bandwidth capacity of the at least one neighboring node.

90. A computer-readable medium containing instructions for controlling a system to perform a method for managing data traffic in a network comprised of a plurality of nodes including a first node having at least one neighboring node, the method performed by the first node and comprising:

determining a value indicative of a maximum unused bandwidth of the first node;

receiving from the at least one neighboring node data indicative of at least one maximum unused bandwidth of the at least one neighboring node;

calculating a value indicative of a maximum available bandwidth of the first node from the value indicative of the maximum unused bandwidth of the first node and the received data indicative of the at least one maximum unused bandwidth; and

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node.

91. The computer-readable medium of claim 90, wherein the maximum unused bandwidth of the first node is a function of a maximum bandwidth capacity of the first node less a bandwidth of traffic generated at the first node and transit traffic through the first node.

92. The computer-readable medium of claim 91, wherein the value indicative of the maximum unused bandwidth of the first node is defined by $\mathrm{MUB}=C-\sum _{}$

j

lj,

where

∀

jε

neighborhood of the first node;

MUB is the value indicative of the maximum unused bandwidth of the first node;

C is a value indicative of the maximum bandwidth capacity of the first node; and

l_j is a data traffic from the first node to a node j in bits per second.

93. The computer-readable medium of claim 91, wherein the maximum available bandwidth of the first node is a function of the maximum unused bandwidth of the first node less a bandwidth of traffic generated at the at least one neighboring node and transit traffic through the at least one neighboring node to a neighbor of the at least one neighboring node.

94. The computer-readable medium of claim 93, wherein the value indicative of the maximum available bandwidth of the first node is defined by $\mathrm{MAB}=\mathrm{MUB}-\sum _{}$

j

 



∑

k

 



ljk,

where

∀

jε

neighborhood of the first node;

∀

kε

neighborhood of a node j;

MAB is the value indicative of the maximum available bandwidth;

MUB is a value indicative of a maximum unused bandwidth of the first node; and

l_jk is a data traffic from the node j to a node k in bits per second.

95. The computer-readable medium of claim 94, wherein allocating the air time includes

allocating the air time in proportion to the maximum bandwidth capacity of the first node minus the maximum available bandwidth of the first node.

96. The computer-readable medium of claim 90, comprising

calculating at least one value indicative of the maximum available bandwidth of the at least one neighboring node from the received data.

97. The computer-readable medium of claim 96, including

allocating an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node and the at least one maximum available bandwidth of the at least one neighboring node.

98. The computer-readable medium of claim 90, including broadcasting data during the air time according to a packet scheduling algorithm.

99. The computer-readable medium of claim 90, including

receiving a route request packet having a requested bandwidth;

comparing the requested bandwidth to the calculated value indicative of the maximum available bandwidth.

100. The computer-readable medium of claim 99, wherein comparing the requested bandwidth includes

granting the requested bandwidth if the requested bandwidth is less than or equal to the maximum available bandwidth of the first node.

101. The computer-readable medium of claim 99, wherein comparing the requested bandwidth includes

denying the requested bandwidth if the requested bandwidth is greater than the maximum available bandwidth of the first node.

102. The computer-readable medium of claim 90, comprising

broadcasting data indicative of the maximum unused bandwidth of the first node to the at least one neighboring node.

103. The computer-readable medium of claim 102, wherein broadcasting occurs only when the maximum unused bandwidth of the first node changes.

104. The computer-readable medium of claim 90, comprising

broadcasting data indicative of the maximum available bandwidth of the first node to the at least one neighboring node.

105. The computer-readable medium of claim 90, comprising

receiving data, from the at least one neighboring node, indicative of the maximum available bandwidth of the at least one neighboring node.

106. The computer-readable medium of claim 90, comprising

broadcasting data indicative of a maximum bandwidth capacity of the first node to the at least one neighboring node.

107. The computer-readable medium of claim 90, comprising

receiving data indicative of at least one maximum bandwidth capacity of the at least one neighboring node.

108. The computer-readable medium of claim 90, including

receiving data indicative of at least one maximum bandwidth capacity of at least one node neighboring the at least one neighboring node.

109. The computer-readable medium of claim 90, including

receiving data indicative of at least one maximum unused bandwidth of at least one node neighboring the at least one neighboring node.

110. A method of managing data traffic in a network comprised of a plurality of nodes, the method comprising:

generating a first value indicative of a first packet to be transmitted in the network;

transmitting the first value to the plurality of nodes;

receiving a second value indicative of a second packet to be transmitted in the network; and

determining an order of transmission of the first and second packets based on the first value and the second value, wherein the first value is a function of an arrival time of the first packet and a length of the first packet, and wherein the second value is a function of an arrival time of the second packet and a length of the second packet.

111. The method of claim 110, wherein the first value is a function of an estimate of a bandwidth required to support a flow of the first packet, and wherein the second value is a function of an estimate of a bandwidth required to support a flow of second the packet.

112. The method of claim 110, further comprising transmitting the second value to the plurality of nodes.

113. The method of claim 110, further comprising detecting a collision and, if a collision is detected, repeating the steps of generating, transmitting, receiving, and determining.

114. The method of claim 110, further comprising transmitting the first and the second packet in the determined order.

115. The method of claim 114, further comprising detecting a collision and, if a collision is detected, repeating the steps of generating, transmitting, receiving, and determining.

116. A node having at least one neighboring node, the node comprising:

a processor to generate a first value indicative of a first packet to be transmitted in the network;

a transmitter to transmit the first value to the at least one neighboring node; and

a receiver to receive a second value indicative of a second packet to be transmitted in the network;

wherein the processor determines an order of transmission of the first and second packets based on the first value and the second value, wherein the first value is a function of an arrival time of the first packet and a length of the first packet, and wherein the second value is a function of an arrival time of the second packet and a length of the second packet.

117. The node of claim 116, wherein the first value is a function of an arrival time of the first packet and a length of the first packet, and wherein the second value is a function of an arrival time of the second packet and a length of the second packet.

118. The node of claim 116, wherein the first value is a function of an estimate of a bandwidth required to support a flow of the first packet, and wherein the second value is a function of an estimate of a bandwidth required to support a flow of second the packet.

119. The node of claim 116, wherein the transmitter transmits the first packet according to the determined order.

120. The node of claim 119, wherein the receiver detects a collision and, if a collision is detected, the processor regenerates the first value, the transmitter retransmits the first value to the at least one neighboring node, the receiver re-receives the second value, and the processor re-determines the order of transmission of the first and second packets based on the first value and the second value.