Dynamic packet routing using prioritized groups

Patent metadata

Field	Value
Publication number	US-2025039078-A1
Application number	US-202418917976-A
Country	US
Kind code	A1
Filing date	Oct 16, 2024
Priority date	Sep 2, 2021
Publication date	Jan 30, 2025
Grant date	—

Abstract

An example method for dynamic packet routing using prioritized groups includes: receiving, by a node, a network packet to be forwarded to a network destination, identifying, based on data stored in a forwarding information data structure of the node, a first path satisfying a first cost criterion to the network destination, determining that a path latency of the first path exceeds a threshold latency, selecting, based on the data stored in the forwarding information data structure of the node, a second path to the network destination, wherein the second path satisfies a second cost criterion and does not satisfy the first cost criterion, and forwarding, by the node, the network packet to the network destination via a local interface associated with the second path.

First claim

1 . A method comprising:
receiving, by a node, a network packet to be forwarded to a network destination; identifying, based on data stored in a forwarding information data structure of the node, a first path to the network destination, wherein the first path satisfies a first cost criterion; determining that a path latency of the first path exceeds a threshold latency; selecting, based on the data stored in the forwarding information data structure of the node, a second path to the network destination, wherein the second path satisfies a second cost criterion and does not satisfy the first cost criterion; and forwarding, by the node, the network packet to the network destination via a local interface associated with the second path.

2 . The method of claim 1 , wherein the first cost criterion defines a least cost path.

3 . The method of claim 2 , wherein the first path is determined to satisfy the first cost criterion when a cost metric value of the first path does not exceed a cost metric value of the least cost path.

4 . The method of claim 3 , wherein the cost metric value of the first path reflects a number of hops of the first path.

5 . The method of claim 1 , wherein the second cost criterion is based on a cost metric threshold.

6 . The method of claim 5 , wherein the second path is determined to satisfy the second cost criterion while not satisfying the first cost criterion when a cost metric value of the second path exceeds a cost metric value of the first path by at most the cost metric threshold.

7 . The method of claim 1 , wherein:
the data stored in the forwarding information data structure comprises a first definition of a first priority routing group and a second definition of a second priority routing group; the first priority routing group is associated with a first subset of a plurality of paths to the network destination, the first subset of the plurality of path comprising the first path, and each path in the first subset satisfying the first cost criterion; and the second priority routing is associated with a second subset of the plurality of paths to the network destination, the second subset of the plurality of path comprising the second path, and each path in the second subset satisfying the second cost criterion.

8 . The method of claim 7 , wherein the network destination is identified by a subnetwork address.

9 . The method of claim 7 , wherein each path of the plurality of paths is associated with an identifier of a next-hop network interface.

10 . The method of claim 7 , wherein the first priority routing group is represented by a primary group of a routing information base (RIB) and the second priority routing group is represented by a backup group of a routing information base (RIB).

11 . The method of claim 7 , wherein the forwarding information data structure is represented by a forwarding information base (FIB).

12 . The method of claim 7 , further comprising:
identifying, based on the first definition of the first priority routing group and the second definition of the second priority routing group, a network interface for forwarding the network packet to the network destination.

13 . A system for a node, the system comprising:
a memory; and a processing device, coupled to the memory, to perform operations comprising:
receiving a network packet to be forwarded to a network destination;
identifying, based on data stored in a forwarding information data structure of the node, a first path to the network destination, wherein the first path satisfies a first cost criterion;
determining that a path latency of the first path exceeds a threshold latency;
selecting, based on the data stored in the forwarding information data structure of the node, a second path to the network destination, wherein the second path satisfies a second cost criterion and does not satisfy the first cost criterion; and
forwarding the network packet to the network destination via a local interface associated with the second path.

14 . The system of claim 13 , wherein:
the first cost criterion defines a least cost path; and the first path is determined to satisfy the first cost criterion when a cost metric value of the first path does not exceed a cost metric value of the least cost path.

15 . The system of claim 14 , wherein the cost metric value of the first path reflects a number of hops of the first path.

16 . The system of claim 13 , wherein:
the second cost criterion is based on a cost metric threshold; and the second path is determined to satisfy the second cost criterion while not satisfying the first cost criterion when a cost metric value of the second path exceeds a cost metric value of the first path by at most the cost metric threshold.

17 . The system of claim 13 , wherein:
the data stored in the forwarding information data structure comprises a first definition of a first priority routing group and a second definition of a second priority routing group; the first priority routing group is associated with a first subset of a plurality of paths to the network destination, the first subset of the plurality of path comprising the first path, and each path in the first subset satisfying the first cost criterion; and the second priority routing is associated with a second subset of the plurality of paths to the network destination, the second subset of the plurality of path comprising the second path, and each path in the second subset satisfying the second cost criterion.

18 . A non-transitory computer-readable storage medium comprising executable instructions that, when executed by a processing device of a node, cause the processing device to perform operations comprising:
receiving a network packet to be forwarded to a network destination; identifying, based on data stored in a forwarding information data structure of the node, a first path to the network destination, wherein the first path satisfies a first cost criterion; determining that a path latency of the first path exceeds a threshold latency; selecting, based on the data stored in the forwarding information data structure of the node, a second path to the network destination, wherein the second path satisfies a second cost criterion and does not satisfy the first cost criterion; and forwarding, by the node, the network packet to the network destination via a local interface associated with the second path.

19 . The non-transitory computer-readable storage medium of claim 18 , wherein:
the first cost criterion defines a least cost path; and the first path is determined to satisfy the first cost criterion when a cost metric value of the first path does not exceed a cost metric value of the least cost path.

20 . The non-transitory computer-readable storage medium of claim 18 , wherein:
the second cost criterion is based on a cost metric threshold; and the second path is determined to satisfy the second cost criterion while not satisfying the first cost criterion when a cost metric value of the second path exceeds a cost metric value of the first path by at most the cost metric threshold.

Assignees

• Mellanox Technologies Ltd

Inventors

• Gafni Barak
• Sharp Donald Bruce

Classifications

• H04L45/121

  by minimising delays · 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