Distributed split flow routing mechanism for multi-node packet switching communication network

• US 4,974,224 A
• Filed: 11/07/1989
• Issued: 11/27/1990
• Est. Priority Date: 11/07/1989
• Status: Expired due to Fees

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Boone, Stephen W.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HSU, ALPUS
• Application Number:
  US07/432,944
• Time in Patent Office: 385 Days
• Field of Search: 370/94.1, 370/94.3, 370/60, 370/104.1, 370/105, 370/93, 370/16, 370/54, 340/825.03, 340/826, 340/827, 379/219, 379/220, 379/221, 379/271, 379/272, 379/273
• US Class Current: 370/400
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/24 Multipath

Abstract

Routing variables for near optimally controlling the distributed flow of information signals from a node s over a multinode communication network to a destination node d are generated in accordance with a prescribed heuristic among network path delays. A prescribed routing variable value (e.g. zero) is assigned to each route to a node n, representing that that node is not to be used to route information signals from node s to node d, for any node of the network that either is not directly connected to node s, has not established a connection path to a destination node d, or is using node s as part of its communication path to destination node d. The path delays from node s to neighboring nodes n are measured and a measurment of the path delay from node s to destination node d is obtained. In addition periodically updated measurements of the path delays from neighboring nodes n to destination node d are received. For each neighboring node that may be used to route traffic, its associated routing variable is generated in accordance with the heuristic among the path delays. The path delay from node s to node d is then updated in accordance with a weighted sum of the routing variables and transmitted to neighboring nodes.

Claims

1. A method of controlling the distribution of transmission routes for information signal packets from node s over communication links through other nodes to a destination node d of a multinode communication network comprising the steps of:

(a) obtaining a measurement of path delay DELAY(s,d) between node s and destination node d;

(b) obtaining a measurement of path delay DELAY(n,d) between a neighboring node n, through which a packet may be transmitted in the course of its transmission from node s to destination node d, and destination node d;

(c) obtaining a measurement of the delay estimate NAYDIS(s,n) between node s and neighboring node n;

(d) generating a routing variable PHI(s,n,d) representative of the percentage of time that a packet is to be transmitted from node s to neighboring node n, in the course of its transmission to destination node d, in accordance with a prescribed relationship among the measurements obtained in steps (a)-(c);

(e) carrying out steps (a)-(d) for plural neighboring nodes n through which a packet may be transmitted in the course of its transmission from node s to said destination node d, so as to obtain a plurality of routing variables respectively associated with neighboring nodes of node s; and

(f) selectively routing packets for transmission from node s to destination node d in accordance with the routing variables obtained in step (e).

2. A method according to claim 1, wherein step (d) comprises generating an initial value of a routing variable PHI (s,n,d) in accordance with a prescribed relationship among the measurements obtained in steps (a)-(c) and combining said initial value of said routing variable with a previously generated value of said routing variable to obtain a current value of said routing variable, and wherein step (f) comprises selectively routing packets for transmission from node s to neighboring nodes n in accordance with current values of said routing variables.

3. A method according to claim 2, wherein step (d) includes the steps of:

(d1) for each node that has no direct communication path to node s, generating an associated routing variable PHI(s,n,d) that is equal to a prescribed value,

(d2) for each node that is using node s as part of a communication path between said each node and said destination node d, generating an associated routing variable PHI(s,n,d) that is equal to said prescribed value, and

(d3) for each node that has no established path to said destination node d, generating an associated routing variable PHI(s,n,d) that is equal to said prescribed value, but otherwise generating an associated routing variable PHI(s,n,d) in accordance with the prescribed relationship among the measurements obtained in steps (a)-(c).

4. A method according to claim 3, wherein step (d) further includes the step of:

(d4) for each node that has an established path, but undefined delay, to said destination node d, setting the initial value of its associated routing variable PHI(s,n,d) to said prescribed value.

5. A method according to claim 4, wherein said prescribed value is zero.

6. A method according to claim 2, wherein step (d) includes generating the current value of a routing variable as the sum of a predefined fraction of the initial value of the routing variable and the product of a previous value of the routing variable and the difference between unity and said predefined fraction.

7. A method according to claim 1, wherein step (a) includes the step of periodically transmitting, from node s to each of its neighboring nodes n, a measurement of path delay DELAY(s,d) from node s to destination node d.

8. A method according to claim 7, wherein step (a) further includes the step of transmitting, from node s to each of its neighboring nodes n, a signal representative of which nodes are currently being used as part of a communication path between node s and destination node d.

9. A method according to claim 8, wherein step (a) includes the step of transmitting, from node, ,s to each of its neighboring nodes n, a vector-representative signal indicative of which nodes in the network are being used as part of a communication path from node s to destination node d.

10. A method according to claim 9, wherein step (a) comprises transmitting said vector representative signal only in response to the occurrence of a change as to which nodes in the network are being used as part of a communication path from node s to destination node d.

11. A method according to claim 1, wherein step (c) comprises obtaining a measurement of delay estimate NAYDIS(s,n) between node s and a neighboring node n as a function of propagation time between node s and neighboring node n and average packet queueing delay at node s on the link to node n.

12. A method according to claim 7 wherein step (a) comprises obtaining a measurement of path delay DELAY(s,d) between node s and destination node d as a function of the sum of measurement of the path delay DELAY(n,d) from node n to destination node d that has been transmitted to node s from neighboring node n and delay estimate NAYDIS(s,n) between said node s and node n.

13. A method according to claim 12, wherein step (a) comprises, at node s, obtaining a measurement of path delay DELAY(s,d) between node s and destination node d as a weighted summation of the product of a plurality of routing variables PHI(s,n,d) and the sum of the measurements of path delay DELAY(n,d) from its neighboring nodes n to destination node d that have been transmitted to node s from neighboring nodes n and delay estimates NAYDIS(s,n) between said node s and neighboring nodes n.

14. A method according to claim 6, wherein step (d) includes generating the initial value of a respective routing variable PHI(s,n,d)^init in accordance with the ratio of the difference between a measurement of path delay DELAY(s,d) between node s and destination node d from a previous iteration and a measurement of path delay DELAY(n d) between neighboring node n and destination node d to a quantity based upon the sum of a measurement of path delay DELAY(n,d) between neighboring node n and destination node d and a measurement of delay estimate NAYDIS(s,n) between node s and neighboring node n.

15. A method according to claim 14, wherein said quantity corresponds to the square of the sum of a measurement of path delay DELAY(n,d) between neighboring node n and destination node d and a measurement of delay estimate NAYDIS(s,n) between node s and node n.

16. A method of controlling the distribution of transmission routes for information signal packets from a node s over a plurality of communication links through neighboring nodes n to a destination node d of a multinode communication network comprising the steps of:

(a) generating a set of routing variables PHI(s,n,d), respectively representative of percentages of time that packets to be transmitted from node s to destination node d are transmitted from node s through respective nodes n; and

(b) selectively routing packets for transmission from node s to destination node d through nodes n in accordance with the set of routing variables generated in step (a); and

wherein step (a) comprises the steps of;

(a1) for each node that has no direct communication path to node s, generating an associated routing variable PHI(s,n,d) that is equal to a prescribed value,

(a2) for each node that is using node s as part of a communication path from that node to said destination node d, generating an associated routing variable PHI(s,n,d) that is equal to said prescribed value,

(a3) for each node that has no established path to destination node d, generating an associated routing variable PHI(s,n,d) that is equal to said prescribed value,

(a4) measuring path delay DELAY(s,d) between node s and destination node d,

(a5) measuring path delays DELAY(n,d) between neighboring nodes n and destination node d,

(a6) measuring packet propagation and queueing delays NAYDIS(s,n) between node s and neighboring nodes n, and

(a7) for each neighboring node that has an available path to destination node d and whose associated routing variable PHI(s,n,d) has not been set to said prescribed value in step (a2), generating an associated routing variable PHI(s,n,d) in accordance with a prescribed relationship among delays measured in steps (a4)-(a6).

17. A method according to claim 16, wherein step (a7) comprises generating an initial value of a routing variable PHI (s,n,d) in accordance with a prescribed relationship among the measurements obtained in steps (a4)-(a6) and combining said initial value of said routing variable with a previously generated value of said routing variable to obtain a current value of said routing variable, and wherein step (b) comprises selectively routing packets for transmission from node s to destination node d through neighboring nodes n in accordance with current values of said routing variables.

18. A method according to claim 17, wherein step (a) further includes the step of:

(a8) for each node that has an established path, but undefined delay, to destination node d, setting the initial value of its associated routing variable PHI(s,n,d) to said prescribed value.

19. A method according to claim 18 wherein said prescribed value is zero.

20. A method according to claim 17, wherein step (a7) includes generating the current value of a routing variable as the sum of a predefined fraction of the initial value of the routing variable and the product of a previous value of the routing variable and the difference between unity and said predefined fraction.

21. A method according to claim 16, wherein step (a4) includes the step of periodically transmitting, from node s to each of its neighboring nodes n, a measurement of path delay DELAY(s,d) from node s to destination node d.

22. A method according to claim 21, wherein step (a4) further includes the step of transmitting, from node s to each of its neighboring nodes n, a signal representative of whether or not the neighboring node to whom the signal is transmitted is being used as part of a communication path between node s and destination node d.

23. A method according to claim 22, wherein step (a4) includes the step of transmitting, from node s to each of its neighboring nodes n, a vector-representative signal indicative of which nodes in the network are being used as part of a communication path from node s to destination node d.

24. A method according to claim 23, wherein step (a4) comprises transmitting said vector representative signal only in response to the occurrence of a change as to which nodes in the network are being used as part of a communication path from node s to destination node d.

25. A method according to claim 21, wherein step (a4) comprises measuring path delay DELAY(s,d) between node s and destination node d as a function of the sum of the path delay DELAY(n,d) from node n to destination node d that has been transmitted to node s from neighboring node n and delay estimate NAYDIS(s,n) between said node s and node n.

26. A method according to claim 25, wherein step (a4) comprises, at node s, measuring path delay DELAY(s,d) between node s and destination node d as a weighted summation of the product of a plurality of routing variables PHI(s,n,d) and the sum of measurements of the path delay DELAY(n,d) from its neighboring nodes n to destination node d that have been transmitted to node s from neighboring nodes n and delay estimate NAYDIS(s,n) between said node s and neighboring nodes n.

27. A method according to claim 20, wherein step (a7) includes generating the initial value of a respective routing variable PHI(s,n,d)^init in accordance with the ratio of the difference between a measurement of path delay DELAY(s,d) between node s and destination node d from a previous iteration and a measurement of path delay DELAY(n,d) between neighboring node n and destination node d to a quantity based upon the sum of a measurement of path delay DELAY(n,d) between neighboring node n and destination node d and a measurement of delay estimate NAYDIS(s,n) between node s and neighboring node n.

28. A method according to claim 27, wherein said quantity corresponds to the square of the sum of a measurement of path delay DELAY(n,d) between neighboring node n and destination node d and a measurement of delay estimate NAYDIS(s,n) between node s and node n.

29. A method of generating respective routing variables for controlling the distributed flow of information signals from a node s over a multinode communication network to a destination node d comprising performing, at node s of the network, the steps of:

(a) for any node of the network that either is not a directly connected neighbor to node s, has not established a connection path to a destination node d, or is using node s as part of its communication path to destination node d, generating an associated routing variable having a prescribed value which represents that said any node is not to be used to route information signals from node s to node d;

(b) measuring path delays from node s to neighboring nodes n;

(c) obtaining a measurement of path delay from node s to destination node d;

(d) obtaining measurements of path delays from neighboring nodes n to destination node d; and

(e) for each neighboring node, an associated routing variable for which was not generated in step (a), generating a respective routing variable associated with that neighboring node n in accordance with a prescribed relationship among path delays of steps (b)-(d).

30. A method according to claim 29, further including the step of:

(f) periodically transmitting, to each neighboring node n, a path delay from node s to destination node d, a measurement for which was obtained in step (c).

31. A method according to claim 30, further including the steps of:

(g) transmitting, to each neighboring node n, a signal representative of whether or not node s is using that neighboring node n to route information signals from node s to destination node d.

32. A method according to claim 31, wherein step (g) comprises transmitting, to each neighboring node n, a digital code representative of which nodes of the network are participants in the routing of information signals from node s to destination node d.

33. A method according to claim 29, wherein step (e) comprises the steps of:

(e1) generating a respective preliminary routing variable in accordance with a prescribed relationship among path delays of steps (b)-(d), and

(e2) generating a respective updated routing variable in accordance with a predefined relationship between said preliminary routing variable and a previously generated routing variable.

34. A method according to claim 33, wherein step (c) comprises obtaining a measurement of path delay from node s to node d in accordance with a summation of path delays of step (b) and step (d) weighted by the respective updated routing variables generated in step (e2).

35. A method according to claim 33, wherein step (e1) comprises setting the value of said preliminary routing variable at said prescribed value in step (a), in response to the value of path delay of neighbor node n that has established a connection path to said destination node, exceeding a predetermined path delay value.

36. A method according to claim 35, wherein said prescribed value of said associated routing variable is zero.

37. A method according to claim 33, wherein step (e1) comprises generating said preliminary routing variable PHI(s,n,d)^init in accordance with the ratio of the difference between a measurement of path delay between node s and destination node d from a previous iteration and a measurement of path delay between neighboring node n and destination node d to a quantity based upon the sum of a measurement of path delay between neighboring node n and destination node d and a measurement of delay estimate between node s and neighboring node n.

38. In a multinode communications network having a plurality of communication nodes, each of which is capable of transmitting information signals to and receiving communication signals from other nodes of the network, so that a plurality of transmission routes from a source node s to a destination node d may be established among plural nodes of the network, an arrangement, provided at said source node, for controlling the distributed flow of information signals from said node s to said destination node d comprising:

means for monitoring the network connectivity of the respective nodes of the network and, for any node of the network that either is not directly connected neighbor to node s, has not established a connection path to a destination node d, or is using node s as part of its communication path to destination node d, generating an associated routing variable having a prescribed value which represents that said any node is not to be used to route information signals from node s to node d, said monitoring means including means for measuring path delays from node s to neighboring nodes n, obtaining a measurement of path delay from node s to destination node d, and obtaining measurements of path delays from neighboring nodes n to destination node d and, for each neighboring node, an associated routing variable for which has not been generated at said prescribed value, generating a respective routing variable associated with that neighboring node n in accordance with a prescribed relationship among path delay measurements; and

means for selectively routing information signals from node s to neighboring node d in accordance with said respective routing variables.

39. An arrangement according to claim 38, wherein each node further comprises means for periodically transmitting, to each neighboring node n, a signal representative of the measurement of path delay from node s to destination node d.

40. An arrangement according to claim 39, wherein said transmitting means includes means for transmitting, to each neighboring node n, a signal representative of whether or not node s is using that neighboring node n to route information signals from node s to destination node d.

41. An arrangement according to claim 40, wherein said transmitting means comprises means for transmitting, to each neighboring node n, a digital code representative of which nodes of the network are participants in the routing of information signals from node s to destination node d.

42. An arrangement according to claim 38, wherein said connectivity monitoring means comprises means for generating a respective preliminary routing variable in accordance with a prescribed relationship among path delay measurements, and generating a respective updated routing variable in accordance with a predefined relationship between said preliminary routing variable and a previously generated routing variable.

43. An arrangement according to claim 42, wherein said connectivity monitoring means comprises means for obtaining a measurement of the path delay from node s to node d in accordance with a summation of measured path delays weighted by the respective updated routing variables.

44. An arrangement according to claim 42, wherein connectivity monitoring means comprises means for setting the value of said preliminary routing variable at said prescribed value in response to the value of path delay of said neighbor node that has established a connection path to said destination node, exceeding a predetermined path delay value.

45. An arrangement according to claim 44, wherein said prescribed value of said associated routing variable is zero.

46. An arrangement according to claim 42, wherein said connectivity monitoring means comprises means for generating said preliminary routing variable in accordance with the ratio of the difference between a measurement of path delay between node s and destination node d from a previous iteration and a measurement of path delay between neighboring node n and destination node d to a quantity based upon sum of a measurement of the path delay between neighboring node n and destination node d and a measurement of delay estimate between node s and neighboring node n.