Association in line-of-sight communication networks

• US 9,661,552 B2
• Filed: 11/06/2014
• Issued: 05/23/2017
• Est. Priority Date: 11/06/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Maguire, Yael, Yogeeswaran, Karthik, Panah, Ali Yazdan
• Primary Examiner(s): Khirodhar, Maharishi
• Assistant Examiner(s): Dewan, Sanjay K
• Application Number:
  US14/534,709
• Publication Number:
  US 20160135110A1
• Time in Patent Office: 929 Days
• CPC Class Codes: H04W 36/125 involving different types of service backbones
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Various of the disclosed embodiments relate to line-of-sight (LOS), e.g., optical, based networks. Systems and methods are provided for connecting nodes based on their topological position in a line-of-sight communication network. Some embodiments may represent each node by a “backbone” and a “subnetwork” rank. The determination of a node'"'"'s rank can prevent the formation of isolated “islands” of nodes, cut off from the backbone. The ranking can also provide a total ordering of nodes relative to the “fiberpop” node which can be used for healing and routing behaviors.

Claims

1. A computer-implemented method in a first node for establishing a connection with a backbone in a network, comprising:

determining initial values for a ranking of the first node, the ranking of the first node comprising;

a first ranking part reflecting a communication distance to a node having connectivity with the backbone; and

a second ranking part reflecting a communication distance to one or more nodes in a first subnetwork of the network, wherein the first subnetwork includes the first node and the one or more nodes;

receiving ranking information from a peer node, the ranking information including a ranking for the peer node, the ranking for the peer node relating to connectivity of the peer node with the backbone for preventing isolation of the first node from the network, the ranking for the peer node including;

a first ranking part reflecting a communication distance to a node having connectivity with the backbone; and

a second ranking part reflecting a communication distance to one or more nodes in a second subnetwork of the network, wherein the second subnetwork includes the peer node and the one or more nodes;

attempting by the first node to establish communication with the peer node, based on the ranking information, via Line-of-Sight (LOS) communication;

establishing, by the first node, communications with the peer node;

updating a first value in the first node'"'"'s first ranking part, the first value being the same value as the peer node'"'"'s first ranking part; and

updating a second value in the first node'"'"'s second ranking part, the second value generated from an arithmetic operation applied to the peer node'"'"'s second ranking part.

2. The computer-implemented method of claim 1, wherein the first subnetwork and the second subnetwork are the same subnetwork.

3. The computer-implemented method of claim 1, wherein the peer node is in communication with the backbone prior to the first node receiving the ranking information.

4. The computer-implemented method of claim 1, wherein the ranking information comprises association metadata determined from a planning phase.

5. The computer-implemented method of claim 1, wherein the ranking information comprises a priority indication, the priority indication indicating that the ranking information is of a higher priority than ranking information previously received by the first node.

6. The computer-implemented method of claim 1, wherein the ranking information indicates a total ordering of nodes within the subnetwork.

7. The computer-implemented method of claim 1, wherein the ranking information depicts a total ordering of nodes directly connected with the backbone.

8. The computer-implemented method of claim 1, wherein receiving ranking information from a peer node comprises actively querying the peer node for ranking information, the method further comprising:

passively querying the peer node for ranking information after assigning the first value to the first node'"'"'s first ranking part.

9. A non-transitory computer-readable storage medium storing instructions configured to cause a computer system to perform a method comprising:

determining initial values for a ranking of a first node, the ranking of the first node comprising;

a first ranking part reflecting a communication distance to a node having connectivity with a backbone in a network; and

a second ranking part reflecting a communication distance to one or more nodes in a first subnetwork of the network, wherein the first subnetwork includes the first node and the one or more nodes;

receiving ranking information from a peer node, the ranking information including a ranking for the peer node, the ranking for the peer node relating to connectivity of the peer node with the backbone for preventing isolation of the first node from the network, the ranking for the peer node including;

a first ranking part reflecting a communication distance to a node having connectivity with the backbone;

a second ranking part reflecting a communication distance to one or more nodes in a second subnetwork of the network, wherein the second subnetwork includes the peer node and the one or more nodes;

attempting by the first node to establish communication with the peer node, based on the ranking information, via Line-of-Sight (LOS) communication;

establishing, by the first node, communications with the peer node;

updating a first value in the first node'"'"'s first ranking part, the first value the same value as the peer node'"'"'s first ranking part; and

updating a second value in the first node'"'"'s second ranking part, the second value generated from an arithmetic operation applied to the peer node'"'"'s second ranking part.

10. The computer-readable storage medium of claim 9, wherein the first subnetwork and the second subnetwork are the same subnetwork.

11. The computer-readable storage medium of claim 9, wherein the peer node is in communication with the backbone prior to the first node receiving the ranking information.

12. The computer-readable storage medium of claim 9, wherein the ranking information comprises association metadata determined from a planning phase.

13. The computer-readable storage medium of claim 9, wherein the ranking information comprises a priority indication, the priority indication indicating that the ranking information is of a higher priority than ranking information previously received by the first node.

14. The computer-readable storage medium of claim 9, wherein the ranking information indicates a total ordering of nodes within the subnetwork.

15. The computer-readable storage medium of claim 9, wherein the ranking information depicts a total ordering of nodes directly connected with the backbone.

16. The computer-readable storage medium of claim 9, wherein receiving ranking information from a peer node comprises actively querying the peer node for ranking information, the instructions further comprising:

passively querying the peer node for ranking information after assigning the first value to the first node'"'"'s first ranking part.

17. A computer system comprising:

at least one processor;

at least one memory comprising instructions configured to cause the at least one processor to perform a method comprising;

determining initial values for a ranking of a first node, the ranking of the first node comprising;

a first ranking part reflecting a communication distance to a node having connectivity with a backbone in a network; and

a second ranking part reflecting a communication distance to one or more nodes in a first subnetwork of the network, wherein the first subnetwork includes the first node and the one or more nodes;

receiving ranking information from a peer node, the ranking information including a ranking for the peer node, the ranking for the peer node relating to connectivity of the peer node with the backbone for preventing isolation of the first node from the network, the ranking for the peer node including;

a first ranking part reflecting a communication distance to a node having connectivity with the backbone; and

a second ranking part reflecting a relationship to one or more nodes in a second subnetwork of the network, wherein the second subnetwork includes the peer node and the one or more nodes;

attempting by the first node to establish communication with the peer node, based on the ranking information, via Line-of-Sight (LOS) communication,

establishing, by the first node, communications with the peer node;

updating a first value in the first node'"'"'s first ranking part, the first value the same value as the peer node'"'"'s first ranking part; and

updating a second value in the first node'"'"'s second ranking part, the second value generated from an arithmetic operation applied to the peer node'"'"'s second ranking part.

18. The computer system of claim 17, wherein the peer node is in communication with the backbone prior to the first node receiving the ranking information.

19. The computer system of claim 17, wherein the ranking information comprises association metadata determined from a planning phase.

20. The computer system of claim 17, wherein the ranking information comprises a priority indication, the priority indication indicating that the ranking information is of a higher priority than ranking information previously received by the first node.

21. The computer system of claim 17, wherein the ranking information indicates a total ordering of nodes within the subnetwork.

22. The computer system of claim 17, wherein the ranking information depicts a total ordering of nodes directly connected with a backbone.

23. The computer system of claim 17, wherein receiving ranking information from a peer node comprises actively querying the peer node for ranking information, the method further comprising:

passively querying the peer node for ranking information after assigning the first value to the first node'"'"'s first ranking part.

24. A computer-implemented method of maintaining connectivity in a communication network including a plurality of geographically distributed nodes, the method comprising:

selecting a random value as a self-assigned rank at a non-backbone node, the non-backbone node included in the plurality of geographically distributed nodes, wherein the non-backbone node lacks a backbone network connection, wherein each node in the plurality of geographically distributed nodes is aware of a geographic location of each node, wherein each node in the plurality of geographically distributed nodes maintains a respective lookup table; and

iteratively performing, at the non-backbone node, the operations of;

receiving a list specifying ranks of nodes that are neighbors of the non-backbone node;

updating a lookup table associated with the non-backbone node based upon information in the list, the updating comprising;

searching the list for (i) a first node associated with a lower rank than the self-assigned rank of the non-backbone node and (ii) a second node associated with a higher rank than the self-assigned rank of the non-backbone node, wherein the first node and the second node are included in the plurality of geographically distributed nodes,

attempting to communicate routing information associated with the non-backbone node to the first node and the second node, wherein the routing information includes the geographic location of the non-backbone node, wherein the routing information includes a ranking of peer nodes of the non-backbone node, the ranking of peer nodes relating to connectivity of the non-backbone node with a backbone node that is connected to the backbone network for preventing isolation of the non-backbone node from the network, and

upon establishment of successful communication between the non-backbone node and the first node, adjusting, by the non-backbone node, the self-assigned rank of the non-backbone node.

25. The computer-implemented method of claim 24, wherein adjusting the self-assigned rank of the non-backbone node includes incrementing the self-assigned rank of the non-backbone node, in the lookup table associated with the non-backbone node, by one.

26. The computer-implemented method of claim 24, further comprising:

upon establishment of successful communication between the non-backbone node and the second node, adjusting, by the second node, a self-assigned rank of the second node in a lookup table associated with the second node.

27. The computer-implemented method of claim 26, wherein adjusting the self-assigned rank of the second node in the lookup table associated with the second node includes incrementing the self-assigned rank of the second node, in the lookup table associated with the second node, by one.

28. The computer-implemented method of claim 24, further comprising:

selecting a zero (0) value as a self-assigned rank at the backbone node, the backbone node included in the plurality of geographically distributed nodes, wherein the backbone node is connected to the backbone network connection; and

iteratively performing, at the backbone node, the operations of;

receiving, at the backbone node, a list specifying ranks of nodes that are neighbors of the backbone node;

updating a lookup table associated with the backbone node based upon information in the list, the updating comprising;

searching the list for a third node associated with a higher rank than the self-assigned rank of the backbone node, wherein the third node is included in the plurality of geographically distributed nodes,

attempting to communicate routing information associated with the backbone node to the third node, wherein the routing information includes the geographic location of the backbone node.

29. The computer-implemented method of claim 24, wherein upon establishment of successful communication between the backbone node and the third node, adjusting, by the third node, the self-assigned rank of the third node.

30. The computer-implemented method of claim 24, wherein the random value is a non-zero integer between 1 and N, wherein N is a total number of nodes in the plurality of geographically distributed nodes.

31. The computer-implemented method of claim 24, wherein the list specifying ranks of nodes that are neighbors of the non-backbone node is obtained from a node in the plurality of geographically distributed nodes.

32. The computer-implemented method of claim 24, wherein the list specifying ranks of nodes that are neighbors of the non-backbone node is obtained from a user.