Orthodromic routing

Patent metadata

Field	Value
Publication number	US-11438823-B2
Application number	US-202016887675-A
Country	US
Kind code	B2
Filing date	May 29, 2020
Priority date	May 29, 2020
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

A method and apparatus for routing packets in a network, such as a satellite mesh network. Geographic routing is employed in which packets specify their physical destination location. Network nodes maintain physical location information for nodes, along with routing information, for a limited portion of the network which is local thereto. At each node and for each packet, a target node is selected from the limited portion. The target node may be the node which is closest in orthodromic distance to the physical destination location. Based on the routing information, a next node belonging to the limited portion of the network and located along an available network path between the node and the target node is determined, and the packet is forwarded to the next node.

First claim

What is claimed is:

1. A method for routing a data packet in a network, the data packet specifying a physical location of a destination for the data packet, the method comprising, at a first node of the network in possession of the data packet:
maintaining physical location information for nodes in a limited portion of the network directly coupled to the first node, and maintaining routing information for the limited portion of the network, said limited portion of the network comprising at least one node which is indirectly coupled to the node via at least one intermediate node;
selecting, from among the nodes in the limited portion of the network, a target node that meets a predetermined objective with respect to orthodromic distance to the physical location of the destination for the data packet;
determining, based on the routing information, a next node belonging to the limited portion of the network and located along an available network path between the node and the target node; and
forwarding the packet toward said next node.

2. The method of claim 1 , further comprising determining respective orthodromic distances or approximations thereof between at least some of the nodes in the limited portion of the network and the physical location of the destination for the data packet.

3. The method of claim 2 , wherein orthodromic distance is determined based on a Haversine function calculation, Cartesian function calculation, approximate Haversine function calculation, or approximate Cartesian function calculation, wherein the Cartesian function calculation comprises computing an inner product of a first vector and a second vector, the first vector originating at a first point and directed toward a physical location of one of the nodes in the limited portion of the network, and the second vector originating at the first point and directed toward the physical location of the destination for the data packet.

4. The method of claim 1 , wherein the routing information comprises a routing table which is maintained based on one or both of: dynamic updates of status of communication links between nodes in the limited portion of the network; and dynamic changes to a topology of the network.

5. The method of claim 1 , wherein determining the next node comprises determining, based on a predetermined rule, a preferred path through the limited portion of the network to the target node, and determining the next node as being a node directly coupled to the first node and lying along said preferred path.

6. The method of claim 1 , wherein the physical location of the destination is encoded into a header of the data packet.

7. The method of claim 1 , wherein the physical location of the destination is specified using latitude and longitude, coordinates in a polar coordinate system, or coordinates in a Cartesian coordinate system.

8. The method of claim 1 , wherein the limited portion of the network comprises one or more of: all nodes of the network which are within a predetermined number of hops from the first node, said predetermined number being greater than one; all nodes of the network which are within a predetermined distance of the first node; and all nodes which are in a predetermined spatial region containing or adjacent to the first node.

9. The method of claim 8 , wherein the predetermined number, the predetermined distance or the predetermined spatial region is determined based on link outage characteristics of the network.

10. The method of claim 1 , wherein said physical location information for the nodes changes over time in response to motion of said nodes.

11. The method of claim 1 , wherein some or all of the network node and the nodes in the limited portion of the network are satellite-based network nodes.

12. The method of claim 1 , further comprising selecting the target node from among a plurality of candidate target nodes, the plurality of candidate target nodes being nodes in the limited portion of the network which meet the predetermined objective.

13. The method of claim 12 , wherein the predetermined objective specifies that a node in the limited portion of the network is one of the candidate target nodes when said node is among k nodes in the limited portion of the network which are closest, with respect to orthodromic distance, to the physical location of the destination for the data packet.

14. The method of claim 1 , wherein the predetermined objective specifies that the target node is closest in orthodromic distance, among all nodes in the limited portion of the network, to the physical location of the destination for the data packet.

15. A method for routing a data packet in a network, the data packet specifying a physical location of a destination for the data packet, the method comprising, at each node of a plurality of nodes of the network, when in possession of the data packet:
maintaining physical location information for respective nodes in a limited portion of the network directly coupled to the node, and routing information for the limited portion of the network, said limited portion of the network comprising at least one node which is indirectly coupled to the node via at least one intermediate node;
selecting, from among the nodes in the limited portion of the network, a target node that meets a predetermined objective with respect to orthodromic distance to the physical location of the destination for the data packet;
determining, based on the routing information, a next node belonging to the limited portion of the network and located along an available network path between the node and the target node; and
forwarding the packet to said next node.

16. An apparatus for routing a data packet in a network, the data packet specifying a physical location of a destination for the data packet, the apparatus located at a first node of the network in possession of the data packet, the apparatus comprising a network interface and processing electronics and configured to:
maintain physical location information for nodes in a limited portion of the network directly coupled to the first node, and maintain routing information for the limited portion of the network, said limited portion of the network comprising at least one node which is indirectly coupled to the node via at least one intermediate node;
select, from among the nodes in the limited portion of the network, a target node that meets a predetermined objective with respect to orthodromic distance to the physical location of the destination for the data packet;
determine, based on the routing information, a next node belonging to the limited portion of the network and located along an available network path between the node and the target node; and
forward the packet toward said next node.

17. The apparatus of claim 16 , further configured to determine respective orthodromic distances or approximations thereof between at least some of the nodes in the limited portion of the network and the physical location of the destination for the data packet.

18. The apparatus of claim 16 , wherein determining the next node comprises determining, based on a predetermined rule, a preferred path through the limited portion of the network to the target node, and determining the next node as being a node directly coupled to the first node and lying along said preferred path.

19. The apparatus of claim 16 , wherein the limited portion of the network comprises one or more of: all nodes of the network which are within a predetermined number of hops from the first node, said predetermined

Assignees

• Ashwood Smith Peter
• Halabian Hassan
• Akhavain Mohammadi Mehdi Arashmid
• Huawei Tech Co Ltd

Inventors

• Ashwood-Smith Peter
• Halabian Hassan
• Akhavain Mohammadi Mehdi Arashmid

Classifications

• H04W40/20 Primary

  based on geographic position or location · CPC title

• H04W40/38

  adapting due to varying relative distances between nodes · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W40/22

  using selective relaying for reaching a BTS [Base Transceiver Station] or an access point · CPC title