Metric-based multi-hop path selection

Patent metadata

Field	Value
Publication number	US-12137045-B2
Application number	US-202117449618-A
Country	US
Kind code	B2
Filing date	Sep 30, 2021
Priority date	May 13, 2019
Publication date	Nov 5, 2024
Grant date	Nov 5, 2024

Abstract

Techniques are described for a router providing metric-based multi-hop path selection. For example, a first router of a plurality of routers receives a plurality of network performance metrics for a plurality of links interconnecting the plurality of routers. The plurality of links form a plurality of multi-hop paths through the plurality of routers to a service instance. The router determines, based on the plurality of network performance metrics for the plurality of links, an end-to-end performance of each of the plurality of multi-hop paths. The router selects a multi-hop path over which to forward traffic associated with the session based on the end-to-end performance of each of the plurality of multi-hop paths and one or more performance requirements for a service associated between a session between a client device and the service instance. The router forwards the traffic to the service instance along the selected multi-hop path.

First claim

What is claimed is:

1. A method comprising:
receiving, by a first router of a plurality of routers and from a server, metrics of individual links forming a plurality of paths associated with a service, wherein the server is configured to store the metrics of individual links, the metrics of individual links received from each router of the plurality of routers;
selecting, by the first router and based on the metrics of the individual links forming the plurality of paths associated with the service, a path of the plurality of paths associated with the service, wherein the path satisfies a performance requirement of the service and one or more of the individual links forming the path do not satisfy the performance requirement of the service; and
in response to selecting the path of the plurality of paths associated with the service, forwarding, by the first router, network traffic associated with a session between a source client device and a destination client device providing the service on the selected path, wherein the network traffic includes at least one packet that is modified to include metadata specifying addressing information for the source client device and the destination client device.

2. The method of claim 1 , wherein receiving the metrics of individual links forming the plurality of paths associated with the service comprises:
receiving, from the server, a JavaScript Object Notation (JSON) document comprising the metrics of individual links forming the plurality of paths associated with the service.

3. The method of claim 1 , wherein selecting, based on the metrics of the individual links forming the plurality of paths associated with the service and one or more network performance metrics for the service, the path of the plurality of paths associated with the service comprises:
applying, by the first router, the metrics of the individual links forming the plurality of paths associated with the service as a cost to a shortest path first calculation.

4. A method comprising:
receiving, by a first router of a plurality of routers of a network connecting a client device to a service instance, a plurality of network performance metrics for a plurality of links interconnecting the plurality of routers, wherein the plurality of links form a plurality of multi-hop paths from the first router through the plurality of routers to the service instance;
determining, by the first router and based on the plurality of network performance metrics, an end-to-end performance of each of the plurality of multi-hop paths;
selecting, by the first router and based on determining that the end-to-end performance of a corresponding multi-hop path of the plurality of multi-hop paths satisfies a performance requirement for the service instance and, a multi-hop path over which to forward traffic associated with a session, wherein one or more links of the corresponding multi-hop path do not satisfy the performance requirement for the service instance; and
forwarding, by the first router, the traffic associated with the session to the service instance along the selected multi-hop path.

5. The method of claim 4 , wherein receiving the plurality of network performance metrics for the plurality of links interconnecting the plurality of routers comprises:
receiving, from a server, the plurality of network performance metrics, wherein the server is configured to store the plurality of network performance metrics received from each of the plurality of routers.

6. The method of claim 4 , wherein determining the end-to-end performance of each of the plurality of multi-hop paths comprises:
computing, based on the plurality of network performance metrics, a path performance metric for each of the plurality of multi-hop paths.

7. The method of claim 6 , wherein the path performance metric for each of the plurality of multi-hop paths comprises at least one of a latency of the multi-hop path, a jitter of the multi-hop path, a packet loss of the multi-hop path, or a bandwidth of the multi-hop path.

8. The method of claim 4 , wherein determining the end-to-end performance of each of the plurality of multi-hop paths comprises:
computing, based on the plurality of network performance metrics, a mean opinion score (MOS) for each of the plurality of multi-hop paths.

9. The method of claim 4 , wherein the plurality of network performance metrics further comprises:
one or more network performance metrics for one or more first links interconnecting a first edge router of the plurality of routers and the client device; and
one or more network performance metrics for one or more second links interconnecting a second edge router of the plurality of routers and the service instance.

10. The method of claim 4 , wherein the selected multi-hop path comprises a first multi-hop path, the method further comprising:
receiving, by the first router, a plurality of updated network performance metrics for the plurality of links interconnecting the plurality of routers;
determining, by the first router and based on the plurality of updated network performance metrics, an updated end-to-end performance of each of the plurality of multi-hop paths;
determining, by the first router and based on the updated end-to-end performance of the first multi-hop path, that the first multi-hop path no longer complies with the one or more performance requirements for the service associated with the session;
selecting, by the first router and based on the updated end-to-end performance of each of the plurality of multi-hop paths and the one or more performance requirements for the service associated with the session, a second multi-hop path over which to forward the traffic associated with the session, wherein the second multi-hop path complies with the one or more performance requirements for the service associated with the session; and
forwarding, by the first router, the traffic associated with the session to the service instance along the second multi-hop path.

11. The method of claim 4 , further comprising:
determining, by the first router, at least two of the plurality of multi-hop paths that comply with the one or more performance requirements for the service associated with the session,
wherein selecting the multi-hop path over which to forward the traffic comprises selecting the multi-hop path that best satisfies the one or more performance requirements for the session from among the at least two of the plurality of multi-hop paths.

12. The method of claim 4 , further comprising:
determining, by the first router, at least two of the plurality of multi-hop paths that comply with the one or more performance requirements for the service associated with the session,
wherein selecting the multi-hop path over which to forward the traffic comprises selecting the multi-hop path that least satisfies the one or more performance requirements for the session from among the at least two of the plurality of multi-hop paths.

13. The method of claim 4 , wherein selecting the multi-hop path over which to forward the traffic comprises:
applying, by the first router, the plurality of network performance metrics for the plurality of links interconnecting the plurality of routers as a cost to a shortest path first calculation.

14. A first router of a plurality of routers of a network connecting a client device to a service instance, the first router comprising:
processing circuitry; and
a memory operably coupled to the processing circuitry and comprising instructions configured to cause the processing circuitry to:
receive a plurality of network performance metrics for a plurality of link

Assignees

• Juniper Networks Inc

Inventors

• Menon Abilash
• Jork Markus
• Peterson John M

Classifications

• H04L45/0377 Primary

  for service chaining · CPC title

• H04L45/04

  Interdomain routing, e.g. hierarchical routing · CPC title

• H04L43/08

  Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters · CPC title

• H04L67/51

  Discovery or management thereof, e.g. service location protocol [SLP] or web services · CPC title

• H04L41/5019

  Ensuring fulfilment of SLA · CPC title