Association in line-of-sight communication networks

Patent metadata

Field	Value
Publication number	US-9661552-B2
Application number	US-201414534709-A
Country	US
Kind code	B2
Filing date	Nov 6, 2014
Priority date	Nov 6, 2014
Publication date	May 23, 2017
Grant date	May 23, 2017

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.

First claim

What is claimed is:

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 s

Assignees

• Facebook Inc

Inventors

• Yogeeswaran Karthik
• Panah Ali Yazdan
• Maguire Yael

Classifications

• H04W40/20

  based on geographic position or location · CPC title

• H04W40/04

  based on wireless node resources · CPC title

• H04W16/18 Primary

  Network planning tools · CPC title

• H04W40/246 Primary

  Connectivity information discovery · CPC title

• H04B10/27 Primary

  Arrangements for networking · CPC title