Source-based routing

Patent metadata

Field	Value
Publication number	US-11329912-B2
Application number	US-201916410131-A
Country	US
Kind code	B2
Filing date	May 13, 2019
Priority date	May 13, 2019
Publication date	May 10, 2022
Grant date	May 10, 2022

Abstract

A routing system for routing packets for a route or service comprises a plurality of routers including a source router, wherein the source router is configured to receive, using a service and topology exchange protocol, service and topology state information from a STEP repository for at least one other router based on configured relationships between routers; determine a first path to a destination for a route or service based on the service and topology state information, the first path including an ordered list of successive routers to receive a packet associated with the route or service starting with a first successive router and ending with a destination router; and transmit a packet toward the first successive router with first metadata including a list of at least one remaining router of the ordered list of routers to receive the packet associated with the route or service. Each successive router, starting with the first successive router, is configured to receive a packet and determine if the router is the destination router based on metadata associated with the received packet, and when the router is not the destination router, forward the packet toward a next successive router in the ordered list of routers.

First claim

What is claimed is:

1. A system comprising:
a plurality of routers, wherein a source router of the plurality of routers is configured to:
receive, for each other router of the plurality of routers, state information comprising service availability information indicating an availability of a service through the other router and service topology information indicating a network topology for reaching the service via the one or more other routers;
determine, based on the state information, a path for the service, the path including one or more successive routers of the plurality of routers to receive a packet associated with the service;
determine that a packet is associated with the service for the path, wherein the packet comprises an initial packet of a communication session, and wherein the initial packet comprises a header for routing the initial packet to a destination address specified within the header for the service;
generate a modified packet comprising the header of the initial packet, wherein the source router is configured to construct the modified packet to include metadata inserted after the header and prior to an end of the initial packet, and wherein the metadata of the modified packet comprises:
(i) a first portion of metadata specifying information that controls forwarding of the modified packet and subsequent packets of the communication session, wherein the information specifies a list of the one or more successive routers along the path to the service, and
(ii) a second portion of metadata specifying a session identifier for the communication session associated with the packet, and transmit the modified packet toward the one or more successive routers.

2. The system of claim 1 , wherein the source router is further configured to include a next successive router in the list of one or more successive routers in the first portion of metadata.

3. The system of claim 1 , wherein the source router is further configured to exclude a next successive router from the list of one or more successive routers in the first portion of metadata.

4. The system of claim 1 , wherein each of the one or more successive routers is configured to:
receive the modified packet;
determine, based on the first portion of metadata and the second portion of metadata in the received modified packet, that a next successive router in the list of one or more successive routers is not a destination router for the path;
remove itself from the first portion of metadata before forwarding the modified packet to the next successive router; and
forward the modified packet toward the next successive router as specified in the first portion of the metadata inserted after the header of the packet and prior to the end of the packet.

5. The routing system of claim 4 , wherein each of the one or more successive routers is configured to forward the modified packet to the next successive router by changing a destination address within the header of the modified packet to an address of the next successive router as specified within the metadata.

6. The routing system of claim 5 , wherein each of the one or more successive routers is configured to forward the modified packet to the next successive router by further changing a source address within the header of the packet to an address of a forwarding router of the one or more successive routers.

7. The routing system of claim 1 , wherein a destination router for the path is configured to forward the initial packet to the destination address specified within the header without the first portion of metadata and the second portion of metadata.

8. The system of claim 1 , further comprising a destination router for a first district, wherein the destination router for the first district is a source router for a second district, wherein the destination router for the first district is configured to:
determine a second path to the destination for the service, the second path including one or more second successive routers to receive the modified packet associated with the service, and;
transmit the modified packet toward the one or more second successive routers, wherein the modified packet further comprises a third portion of metadata inserted after the header and prior to the end of the packet, the third portion of metadata specifying a list of the one or more second successive routers and the first portion of metadata specifying the session identifier for the session associated with the packet associated with the service.

9. The system of claim 1 ,
wherein each of the one or more successive routers is configured to:
receive one or more the subsequent packets for the communication session, wherein each of the subsequent packets includes a header having a destination address for the service,
modify, based on the second portion of the metadata, the one or more subsequent packets by rewriting the destination addresses within the headers to destination addresses of the successive routers specified within the second portion of the metadata as next hops along the path, and
forward the modified subsequent packets to a next successive router of the one or more successive routers.

10. A router comprising:
router logic configured to:
a memory; and
one or more processors coupled to the memory, wherein the one or more processors are configured to:
receive, for each other router of the plurality of routers, state information comprising service availability information indicating an availability of a service through the other router and service topology information indicating a network topology for reaching the service via the one or more other routers;
determine, based on the state information, a path for the service, the path including one or more successive routers of a plurality of routers to receive a packet associated with the service;
determine that a packet is associated with the service for the path, wherein the packet comprise an initial packet of a communication session, and wherein the initial packet comprises a header for routing the initial packet to a destination address specified within the header for the service;
generate a modified packet comprising the header of the initial packet, wherein the router is configured to construct the modified packet to include metadata inserted after the header and prior to an end of the initial packet, and wherein the metadata of the modified packet comprises:
(i) a first portion of metadata specifying information that controls forwarding of the modified packet and subsequent packets of the communication session, wherein the information specifies a list of the one or more successive routers along the path to the service, and
(ii) a second portion of metadata specifying a session identifier for the communication session associated with the packet, and transmit the modified packet toward the one or more successive routers.

11. The router of claim 10 , wherein the one or more processors are configured to include a next successive router in the list of one or more successive routers in the first portion of metadata.

12. The router of claim 10 , wherein the one or more processors are configured to exclude a next successive router from the list of one or more successive routers in the first portion of metadata.

13. The router of claim 10 , wherein the one or more processors are configured to:
receive a second packet, the second packet comprising a first portion of metadata specifying a second list of one or more successive routers and a second portion of metadata specifying a second session identifier for a second session associated with the second packet;
determine, based on a firs

Assignees

• 128 Tech Inc

Inventors

• Kaplan Hadriel S
• Menon Abilash
• Timmons Patrick
• Baj Michael
• Penfield Robert
• Melampy Patrick

Classifications

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L45/28 Primary

  using route fault recovery · CPC title

• H04L45/34 Primary

  Source routing · CPC title

• H04L45/245

  Link aggregation, e.g. trunking · CPC title

• H04L45/60

  Router architectures · CPC title