Method and apparatus for packet forwarding in a manhattan grid network

Patent metadata

Field	Value
Publication number	US-2025358217-A1
Application number	US-202519290808-A
Country	US
Kind code	A1
Filing date	Aug 5, 2025
Priority date	Apr 23, 2023
Publication date	Nov 20, 2025
Grant date	—

Abstract

A method of routing a packet in a network with a Manhattan grid geometry arranged in columns and rows, including receiving, by a source network node, a packet and extracting a destination address of the destination node. Each of the links of the network has a nominal routing cost of one hop and the plurality of links including additional links connecting respective opposing ends of each of the plurality of columns and opposing ends of each of the plurality of rows of the Manhattan grid. Then determining a plurality of distances between the source network node and the destination network node based on the Manhattan grid geometry. Selecting a minimum distance from the plurality of distances and transmitting the packet on an interface associated with the minimum distance.

First claim

What is claimed is:

1 . A method, comprising:
receiving, by a source network node, a packet; extracting, by the source network node, a destination address from the packet, the destination address specifying a destination network node in a network, the network having a Manhattan grid geometry including a plurality of columns and a plurality of rows, a plurality of network nodes being located at intersections of the plurality of columns and the plurality of rows with a plurality of links aligned with the plurality of columns and the plurality of rows connecting the plurality of network nodes, each of the plurality of links having a nominal routing cost of one hop, the plurality of links including additional links connecting respective opposing ends of each of the plurality of columns and opposing ends of each of the plurality of rows, and the source network node and the destination network node being included in the plurality of network nodes; determining, by the source network node, a plurality of distances between the source network node and the destination network node, each distance of the plurality of distances determined by adding a vertical distance in rows between the source network node and the destination network node and a horizontal distance in columns between the source network node and the destination network node, the vertical distance being measured in two directions along a source row where the source network node is located, the horizontal distance being measured in two directions along a source column where the source network node is located; selecting, by the source network node, a target minimum distance from the plurality of distances; and transmitting, by the source network node, the packet on an interface associated with the target minimum distance.

2 . The method of claim 1 , further comprising:
receiving, by the source network node, an equal cost multi-path (ECMP) hint; and wherein, when at least two distances of the plurality of distances are all equal to a minimum distance, selecting, by the source network node, the target minimum distance from the plurality of distances comprises: selecting, by the source network node, utilizing the ECMP hint, the target minimum distance from the at least two distances of the plurality of distances.

3 . The method of claim 2 , wherein the ECMP hint indicates selecting a distance along the plurality of rows over a distance along the plurality of columns.

4 . The method of claim 2 , wherein the ECMP hint indicates no preference.

5 . The method of claim 1 , wherein the network is a satellite network, and the plurality of network nodes are satellites, the plurality of columns include a plurality of orbits in a longitudinal direction, the plurality of links aligned with the plurality of columns include a plurality of intra-orbital links, and the plurality of links aligned with the plurality of rows include a plurality of inter-orbital links.

6 . A method, comprising:
receiving, by a source network node, a packet and extracting a destination address from the packet, the destination address specifying a destination network node in a network, the network having a Manhattan grid geometry including a plurality of columns and a plurality of rows, a plurality of network nodes being located at intersections of the plurality of columns and the plurality of rows with a plurality of links aligned with the plurality of columns and the plurality of rows connecting the plurality of network nodes, each of the plurality of links having a nominal routing cost of one hop, the plurality of links including additional links connecting respective opposing ends of each of the plurality of columns and opposing ends of each of the plurality of rows, and the source network node and the destination network node being included in the plurality of network nodes; determining, by the source network node, a plurality of distances between the source network node and the destination network node; receiving, by the source network node, an equal cost multi-path (ECMP) hint; when at least two distances of the plurality of distances are equal to a minimum distance, selecting, by the source network node, utilizing the ECMP hint, a target minimum distance from the at least two distances of the plurality of distances; and transmitting, by the source network node, the packet on an interface associated with the target minimum distance.

7 . The method of claim 6 , wherein each distance of the plurality of distances is combined with an associated interface of the source network node into a distance-interface tuple, each of the distance-interface tuples including a distance between the source network node and the destination network node, and an interface to transmit the packet to reach the destination network node on a route of a length equal to the respective distance, the respective distance being expressed as a number of hops in the route.

8 . The method of claim 6 , wherein the network is a satellite network, and the plurality of network nodes are satellites, the plurality of columns includes a plurality of orbits in a longitudinal direction, the plurality of links aligned with the plurality of columns include a plurality of intra-orbital links, and the plurality of links aligned with the plurality of rows include a plurality of inter-orbital links.

9 . The method of claim 6 , wherein the ECMP hint indicates selecting a distance along the plurality of rows over a distance along the plurality of columns.

10 . The method of claim 6 , wherein the ECMP hint indicates no preference.

11 . A network node, the network node comprising:
at least one processor; and non-transitory computer readable media storing instructions that are executable by the at least one processor, to cause the network node to:
receive addresses of a plurality of other network nodes and a plurality of output interfaces associated with the plurality of other network nodes;
receive a destination address of a packet in a network;
compute a plurality of distances between a source network node and a destination network node indicated by the destination address, based on the addresses of the plurality of other network nodes and the plurality of output interfaces associated with the plurality of other network nodes; and
a comparator circuit, configured to:
receive the plurality of distances and the plurality of output interfaces, and to receive an equal cost multi-path (ECMP) hint; and
determine a target minimum distance and an output interface corresponding to the target minimum distance.

12 . The network node of claim 11 , wherein the network node is the source network node.

13 . The network node of claim 11 , wherein the network is a Manhattan grid network including a plurality of columns and a plurality of rows, the network node, the destination network node, and the plurality of other network nodes being located at intersections of the plurality of columns and the plurality of rows with a plurality of links aligned with the plurality of columns and the plurality of rows connecting the network node, the destination network node, and the plurality of other network nodes, each of the plurality of links having a nominal routing cost of one hop, the plurality of links including additional links connecting respective opposing ends of each of the plurality of columns and opposing ends of each of the plurality of rows.

14 . The network node of claim 13 , wherein the ECMP hint gives priority to a distance along the plurality of rows over a distance along the plurality of columns.

15 . The network node of

Assignees

• Huawei Tech Co Ltd

Inventors

• Mccormick William Carson

Classifications

• H04L49/101

  using crossbar or matrix · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/24

  Multipath · CPC title

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title