INTERPLANETARY COMMUNICATIONS NETWORK, INTERPLANETARY COMMUNICATIONS NETWORK BACKBONE AND METHOD OF MANAGING INTERPLANETARY COMMUNICATIONS NETWORK

• US 20080151811A1
• Filed: 12/20/2006
• Published: 06/26/2008
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: El-Damhougy, Hersham, Jerelt, Keith
• Granted Patent: US 7,764,622 B2
• Time in Patent Office: Days
• US Class Current: 370/316
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00

Abstract

An interplanetary communications network, an interplanetary communications backbone network of Artificial Neural Network (ANN) nodes, an ANN node and a method of managing interplanetary communications. The backbone network operates as a neural network with each node identifying optimum paths, e.g., end-to-end through the backbone network from a distant planet to an earth node. Each node maintains a window matrix identifying reoccurring (e.g., periodically) communications windows between nodes and a propagation delay matrix identifying time varying propagation delays between nodes. Each node determines whether and how long to store packets locally to minimize path delays. Each node also maintains a link cost matrix indicating the cost of links to neighboring nodes and further determines whether and how long to store packets locally to minimize path delays at minimal link cost.

Claims

1. A method of managing an interplanetary communications network, said method comprising the steps of:

a) providing a backbone network configuration, said backbone network configuration having a plurality (k) of nodes;

b) determining transmission propagation times from each node to every other of said plurality of nodes;

c) determining connection windows from said each node to every other node of said plurality of nodes; and

d) determining an optimum transmission time in each said connection window to a respective one of said plurality of nodes.

2. A method as in claim 1, wherein the step (c) of determining connection windows identifies re-occurring windows to one or more of said plurality of nodes.

3. A method as in claim 2, wherein the step (c) of determining connection windows provides a window matrix indicating windows occurring between said each node and said every other node and has the form

$W$

( t ) = ( w 1 1 

( t ) w 1 2 

( t ) ⋯

w 1 k 

( t ) w 2 1 

( t ) w 2 2 

( t ) ⋯

w 2 k 

( t ) ⋯

⋯

⋯

⋯

w k 1 

( t ) w k 2 

( t ) ⋯

w k k 

( t ) ) .

4. A method as in claim 3, wherein matrix entries, w_jⁱ(t), comprise time varying binary values indicating linked periods from node i to each of the other (k−

1) nodes j and only entries in row i with said time varying binary values are in a neighborhood of node i.

5. A method as in claim 3, wherein the transmission propagation times determined in step (b) are time varying.

6. A method as in claim 5, wherein the step (b) of determining transmission propagation times provides a propagation delay matrix indicating time varying propagation delays between said each node and said every other node and has the form

$\Delta$



( t ) = ( d 1 1 

( t ) d 1 2 

( t ) ⋯

d 1 k 

( t ) d 2 1 

( t ) d 2 2 

( t ) ⋯

d 2 k 

( t ) ⋯

⋯

⋯

⋯

d k 1 

( t ) d k 2 

( t ) ⋯

d k k 

( t ) ) .

7. A method as in claim 6, wherein the step (d) of determining optimum transmission times comprises generating a matrix having the form

$D$

( t ) = ( D 1 1 

( t ) D 1 2 

( t ) ⋯

D 1 k 

( t ) D 2 1 

( t ) D 2 2 

( t ) ⋯

D 2 k 

( t ) ⋯

⋯

⋯

⋯

D k 1 

( t ) D k 2 

( t ) ⋯

D k k 

( t ) ) .

8. A method as in claim 7, wherein the step (d) of determining optimum transmission times further comprises determining a storage time (τ

) above a minimum queuing time (t_q) for storing a packet arriving at said first node at a given arrival time (t₀) in said each window until said packet is forwarded to said respective one.

9. A method as in claim 8, wherein entries, D_jⁱ(t), in the matrix satisfy:

Min<sub>τ

≧

0</sub>{d_jⁱ(t₀+τ

)+τ

}=t₀+d_jⁱ(t₀+t_q)=D_jⁱ(t₀).

10. A method as in claim 9, wherein all values of D_jⁱ(t) are piecewise continuous and finite for all nodes and D_jⁱ(t)=min_τ

≧

0{d_jⁱ(t₀+τ

)+τ

.

11. A method as in claim 8, before the step (d) of determining optimum transmission times, said method further comprising determining a time dependent minimum/shortest path cost (π

_i(t)) from each node i to each other node j.

12. A method as in claim 11, wherein determining said time dependent minimum/shortest path cost comprises recursively analyzing π

_i(t)=Min[t_q+π

_i(t_q);

min {D_jⁱ(t)+π

_i(D_jⁱ(t))}].

13. A method as in claim 12, wherein t_q+π

_i(t_q) is the result of only waiting at node i to get first contact window to node to j; and

{D_jⁱ(t)+π

_i(D_jⁱ(t))} provides an optimal wait time at node i.

14. A method as in claim 11, further comprising determining storage costs (C_i) for each node i, a link cost (l_jⁱ(t)) for each node j linked to i, a link utilization rate U_jⁱ(t) and a corresponding node capacity Q_i(t).

15. A method as in claim 14, further comprising determining total queuing time (Φ

_i(t)) for each node i, where Φ

_i(t);

=t_q+Q_i(t).

16. A method as in claim 15, wherein determining said time dependent minimum/shortest path cost comprises recursively analyzing π

_i(t)=Min[Φ

_i(t)C_i+π

_i(Φ

_i(t));

min{(l_jⁱ+(Φ

_i(t)+τ

)C_i+π

_i(D_jⁱ(t))}].

17. A method as in claim 16, wherein Φ

_i(t)C_i+π

_i(Φ

_i(t)) is the result of waiting at node i to get first contact window to node to j extended by traffic load queuing time; and

(l_jⁱ+(Φ

_i(t)+τ

)C_iπ

_i(D_jⁱ(t))} provides an optimal wait time at node i.

18. A method as in claim 16, wherein multi-layer perceptron (MLP) ANN analysis is used for recursively analyzing π

_i(t).

19. A method as in claim 18, wherein a result from said MLP ANN analysis is compared with a measured delay and an error signal from comparing said measured delay is fed back to adapt said MLP ANN analysis.

20. A method as in claim 18, wherein each node i includes a link path table for each destination node j.

21. A method as in claim 20, wherein said link path table is in a cyclic 3-tuple set.

22. A method as in claim 6, wherein the complete shortest path and the associated costs between a given node and all other nodes in the network is determined from D(t) at a selected time.

23. A method as in claim 2, wherein the re-occurring windows reoccur periodically to one or more of said plurality of nodes and ones of said plurality of nodes receiving a majority of communications from Earth nodes having a separate schedule and configuration for sending communications to Earth and for receiving communications from Earth.

24. A method as in claim 1, wherein whenever one of said plurality of nodes determines a neighboring node is unresponsive, said node uses agent based routing to reroute paths around said unresponsive neighboring node.

25. An Artificial Neural Network (ANN) node for a backbone network in an interplanetary communications network, said backbone network including a plurality (k) of nodes, said ANN node comprising:

a window matrix indicating re-occurring communications windows between each node and each other of said plurality of nodes;

a propagation delay matrix indicating time varying transmission propagation times from each node to said each other of said plurality of nodes; and

means for determining an optimum transmission time in each window to a respective one of said plurality of nodes.

26. An ANN node as in claim 25, wherein said window matrix is a k by k matrix with one row for each one of said plurality of nodes, each entry, w_jⁱ(t), in each row indicating communications windows from a corresponding node i to each node j of the other (k−

1) nodes in said backbone network, said window matrix having the form

$W<br><br>\left(t\right)=\left(\begin{array}{cccc}{w}_1^1<br><br>\left(t\right)& w_1^2<br><br>\left(t\right)& \mathrm{\cdots <br><br>}& w_1^k<br><br>\left(t\right)\\ w_2^1<br><br>\left(t\right)& w_2^2<br><br>\left(t\right)& \mathrm{\cdots <br><br>}& w_2^k<br><br>\left(t\right)\\ \mathrm{\cdots <br><br>}& \mathrm{\cdots <br><br>}& \mathrm{\cdots <br><br>}& \mathrm{\cdots <br><br>}\\ w_k^1<br><br>\left(t\right)& w_k^2<br><br>\left(t\right)& \mathrm{\cdots <br><br>}& w_k^k<br><br>\left(t\right)\end{array}\right).$

27. An ANN node as in claim 26, wherein each window matrix entry comprises a time varying binary value indicating linked periods and only entries in row i with said time varying binary values are in a neighborhood Ni of node i.

28. An ANN node as in claim 27, wherein the propagation delay matrix has the

$\Delta$



( t ) = ( d 1 1 

( t ) d 1 2 

( t ) ⋯

d 1 k 

( t ) d 2 1 

( t ) d 2 2 

( t ) ⋯

d 2 k 

( t ) ⋯

⋯

⋯

⋯

d k 1 

( t ) d k 2 

( t ) ⋯

d k k 

( t ) ) .

29. An ANN node as in claim 28, wherein the means for determining optimum transmission times comprises generating a matrix having the form

$D$

( t ) = ( D 1 1 

( t ) D 1 2 

( t ) ⋯

D 1 k 

( t ) D 2 1 

( t ) D 2 2 

( t ) ⋯

D 2 k 

( t ) ⋯

⋯

⋯

⋯

D k 1 

( t ) D k 2 

( t ) ⋯

D k k 

( t ) ) .

30. An ANN node as in claim 29, wherein said means for determining optimum transmission times comprises means for determining a storage time (τ

) above a minimum queuing time (t_q) for storing a packet arriving in said each window at said node i at a given arrival time (t₀) until said packet is forwarded to said respective node j.

31. An ANN node as in claim 30, wherein said means for determining optimum transmission times determines matrix entries, D_jⁱ(t), according to the relationship Min_τ

≧

0 {d_jⁱ(t₀+τ

)+τ

}=t₀+d_jⁱ(t₀+t_q)=D_jⁱ(t₀).

32. An ANN node as in claim 31, wherein all values of D_jⁱ(t) are piecewise continuous and finite for all nodes and D_jⁱ(t)=min_τ

≧

0{d_jⁱ(t₀+τ

)+τ

}.

33. An ANN node as in claim 30, further comprising means for determining a time dependent minimum/shortest path cost (π

_i(t)) from each node i to each neighboring node j.

34. An ANN node as in claim 33, wherein said means for determining said time dependent minimum/shortest path cost recursively analyzes

π

_i(t)=Min[t_q+π

_i(t_q);

min{D_jⁱ(t)+π

_i(D_jⁱ(t))}],

wherein t_q+π

_i(t_q) is the result of only waiting at node i to get first contact window to node to j; and

{D_jⁱ(t)+π

_i(D_jⁱ(t))} provides an optimal wait time at node i.

35. An ANN node as in claim 33, wherein said means for determining said time dependent minimum/shortest path cost further determines storage costs (C_i) for each node i, a link cost (l_i^j(t)) for each node j linked to i, a link utilization rate U_jⁱ(t) and a corresponding node capacity Q_i(t).

36. An ANN node as in claim 35, further comprising means for determining total queuing time (Φ

_i(t)) for each node i, where Φ

_i(t);

=t_q+Q_i(t).

37. An ANN node as in claim 36, wherein said means for determining said time dependent minimum/shortest path cost recursively analyzes

π

_i(t)=Min[Φ

_i(t)C_i+π

_i(Φ

_i(t));

min{(l_jⁱ+(Φ

_i(t)+τ

)C_i+π

_i(D_jⁱ(t))}],

wherein Φ

_i(t)C_i+π

_i(Φ

_i(t)) is the result of waiting at node i to get first contact window to node to j extended by traffic load queuing time; and

{(l_jⁱ+(Φ

_i(t)+τ

)C_i+π

_i(D_jⁱ(t))} provides an optimal wait time at node i.

38. An interplanetary communications network, said interplanetary communications network having a backbone network comprising k ANN nodes as in claim 37.

39. An interplanetary communications network as in claim 38, further comprising means for recursively applying multi-layer perceptron (MLP) ANN analysis to π

_i(t).

40. An interplanetary communications network as in claim 39, further comprising means for comparing a result from said MLP ANN analysis with a measured delay, said means for comparing generating an error signal responsive to a difference between said measured delay and said result.

41. An ANN node as in claim 25, wherein ones of said re-occurring communications windows reoccur periodically and said ANN node further comprises agent based routing means for rerouting paths around an unresponsive neighboring said node.

42. A method of managing a backbone network of an interplanetary communications network, said method comprising the steps of:

a) providing a backbone network configuration, said backbone network configuration having a plurality of nodes;

b) determining transmission propagation times from each node to every other of said plurality of nodes;

c) determining connection windows from said each node to every other node of said plurality of nodes, ones of said connection windows being re-occurring windows; and

d) determining an optimum transmission time in each said connection window to a respective one of said plurality of nodes.

43. A method as in claim 42, wherein the step (c) of determining connection windows provides a window matrix indicating windows occurring between said each node and said every other node.

44. A method as in claim 43, wherein matrix entries comprise time varying binary values indicating linked periods from a first node to each other said plurality of nodes, ones of plurality of nodes being in a neighborhood of at least one other node.

45. A method as in claim 43, wherein the transmission propagation times determined in step (b) are time varying.

46. A method as in claim 45, wherein the step (b) of determining transmission propagation times provides a propagation delay matrix indicating time varying propagation delays between said each node and said every other node.

47. A method as in claim 46, wherein the step (d) of determining optimum transmission times comprises generating a path matrix.

48. A method as in claim 47, wherein the step (d) of determining optimum transmission times further comprises determining a storage time above a minimum queuing time for storing a packet arriving at said first node at a given arrival time in said each window until said packet is forwarded to said respective one.

49. A method as in claim 48, before the step (d) of determining optimum transmission times, said method further comprising determining a time dependent minimum/shortest path cost from said each node to each other node.

50. A method as in claim 49, wherein determining said time dependent minimum/shortest path cost comprises recursively analyzing paths to determine an optimal wait time at said each node.

51. A method as in claim 49, further comprising determining storage costs for said each node, a link cost for each pair of linked nodes, a link utilization rate for each ling and a corresponding node capacity.

52. A method as in claim 51, further comprising determining total queuing time for each node.

53. A method as in claim 52, wherein determining said time dependent minimum/shortest path cost comprises recursively analyzing the result of waiting at node i to get first contact window to node to j extended by traffic load queuing time to provides an optimal wait time at said each node.

54. A method as in claim 53, wherein multi-layer perceptron (MLP) ANN analysis is used for recursively analyzing.

55. A method as in claim 54, wherein a result from said MLP ANN analysis is compared with a measured delay and an error signal from comparing said measured delay is fed back to adapt said MLP ANN analysis.

56. A method as in claim 54, wherein each node includes a link path table for each destination node in a cyclic 3-tuple set.

57. A method as in claim 42, wherein the re-occurring windows reoccur periodically to one or more of said plurality of nodes.

58. A method as in claim 42, wherein whenever one of said plurality of nodes determines a neighboring node is unresponsive, said node uses agent based routing to reroute paths around said unresponsive neighboring node.

59. A method as in claim 42, wherein ones of said plurality of nodes receiving a majority of communications from Earth nodes have a separate schedule and configuration for sending communications to Earth and for receiving communications from Earth.