Routing methods, systems, and computer program products

• US 10,708,168 B1
• Filed: 03/20/2020
• Issued: 07/07/2020
• Est. Priority Date: 12/27/2012
• Status: Active Grant

• Current Assignee: MORRIS ROUTING TECHNOLOGIES, LLC
• Original Assignee: Sitting Man LLC
• Inventors: Morris, Robert Paul
• Primary Examiner(s): Kamara, Mohamed A
• Application Number:
  US16/826,159
• Time in Patent Office: 109 Days
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

In various embodiments, a system and method are provided for generating segment routing (SR) segment lists. In one embodiment, a node receives information that identifies a path from a first node to a second node. Based on the received path, a set of segment identifiers that encodes the path is generated. A packet that is forwarded along the set of segment identifiers travels the received path.

Claims

1. A method comprising:

receiving information that identifies an explicit path from a first node to a second node in a communications network, wherein

the information comprises an identification of a sequence of nodes or links defining the explicit path for a packet to traverse through the communications network;

generating a set of segment identifiers, wherein

the set of segment identifiers encodes the explicit path,

each segment identifier within the set of segment identifiers is included in one or more respective segment routing forwarding tables stored at each node along the explicit path, and

generating the set of segment identifiers comprises selecting a segment identifier type from among

a nodal segment identifier type in which a nodal segment identifier is assigned uniquely to a single node within the network, or

an adjacency segment identifier type in which an adjacency segment identifier is assigned to a link between two contiguous nodes; and

storing the set of segment identifiers at the first node, wherein

the first node is configured to add the set of segment identifiers to a header of the packet.

2. The method of claim 1, wherein a first segment identifier of the set of segment identifiers identifies a nodal segment, and the nodal segment comprises a shortest path to a node associated with the nodal segment.

3. The method of claim 2, wherein a second segment identifier of the set of segment identifiers identifies an adjacency segment.

4. The method of claim 1, further comprising:

computing a shortest path from the first node to the second node; and

comparing an explicit path node identifier with a shortest path node identifier.

5. The method of claim 2, further comprising:

determining, for a node along the explicit path, whether the shortest path represented by a nodal segment associated with the node diverges from the explicit path.

6. The method of claim 5, further comprising:

selecting, as one of the segment identifiers within the set of segment identifiers, a nodal segment identifier identifying a nodal segment encoding the longest path unambiguously following the explicit path.

7. The method of claim 6, wherein the selecting comprises selecting the nodal segment identifier identifying the nodal segment encoding the longest path starting at the first node, and further comprising:

selecting, as an additional one of the segment identifiers within the set of segment identifiers, a nodal segment identifier identifying a nodal segment encoding the longest path starting at the second node and unambiguously following the explicit path.

8. The method of claim 1, further comprising:

calculating a number of hops that represents an overlap between the explicit path and a shortest path from the first node to the second node.

9. The method of claim 1, wherein the information further identifies a second explicit path, and the generating comprises generating a second set of segment identifiers, and combining at least a portion of the set of segment identifiers and at least a portion of the second set of segment identifiers to form a combined set of segment identifiers.

10. The method of claim 1, wherein the generating comprises calculating a reverse shortest path from the second node towards the first node.

11. The method of claim 1, wherein the path is specified using a first number of identifiers that is fewer than a second number of identifiers required to specify the path deterministically.

12. The method of claim 1, wherein data is capable of being transmitted by the first node along different ones of a plurality of path segments based on a policy and a current state of a network domain, where a first path segment of the plurality of path segments, via which the data is transmitted from the first node, is not already selected at packet receipt and is therefore selected, in response to the packet receipt, based on the policy and the current state of the network domain, and without control signaling communications with another one or nodes in response to packet receipt.

13. The method of claim 1, wherein a current state of a network domain is not maintained by the first node.

14. The method of claim 1, wherein contents of the header of the packet includes everything necessary for routing data.

15. The method of claim 1, wherein a number of protocols used to transmit data is reduced.

16. The method of claim 1, wherein the set of segment identifiers are generated regardless as to whether one or more of the segment identifiers of the set and one or more segment identifiers of a previous set is identical or not.

17. The method of claim 1, wherein the set of segment identifiers is generated without changing the path.

18. The method of claim 1, wherein the generation of the set of segment identifiers results in a modification of a first segment identifier without changing the path.

19. The method of claim 1, wherein a first virtual identifier space for a first plurality of nodes in a network domain is realized by configuring each node in the first plurality to have a respective identifier space that includes a particular identifier that identifies, for the each node in the first plurality, the first node, where the particular identifier in the respective identifier space for the each node in the first plurality matches the particular identifier in the respective identifier space for every other node in the first plurality.

20. The method of claim 19, wherein the first node is included in the first plurality;

and the first virtual identifier space includes the particular identifier that takes the form of a scoped identifier with a scope that spans within the first plurality, and that identifies the first node within a span of the first virtual identifier space.

21. The method of claim 1, wherein an index value and a base value are predetermined by a topology service.

22. The method of claim 1, wherein an index value and a base value are predetermined by a transmitting node, and the set of segment identifiers are generated based on the index value and the base value.

23. The method of claim 1, wherein a first path segment, via which data is transmitted from the first node, is not known when the information is received and therefore determined in response to the receipt thereof.

24. The method of claim 1, wherein a network path segment, via which data is transmitted from the first node, is selected without network-based control signaling after the receipt of the information.

25. The method of claim 1, wherein at least one of:

the segment routing forwarding tables include routing tables;

the segment routing forwarding tables include mapping information;

the segment routing forwarding tables look up tables;

the segment routing forwarding tables correspond with at least one identifier space;

the segment routing forwarding tables correspond with node scope-specific identifier spaces;

the nodal segment identifier type includes a region scoped identifier type;

the nodal segment identifier type includes a region scoped identifier;

the sequence of nodes or links includes the nodes;

the sequence of nodes or links includes the links;

the sequence of nodes or links includes the nodes and the links;

the two contiguous nodes includes two nodes with no intermediate nodes therebetween;

the terms system and first node all do not invoke U.S.C. 112, sixth paragraph;

the generating the set of segment identifiers comprises selecting the segment identifier type from among a closed set including the nodal segment identifier type and the adjacency segment identifier type;

the generating the set of segment identifiers comprises selecting the segment identifier type from among an open set including the nodal segment identifier type and the adjacency segment identifier type;

the generating the set of segment identifiers comprises selecting the segment identifier type from only among the nodal segment identifier type or the adjacency segment identifier type;

the generating the set of segment identifiers comprises selecting the segment identifier type from a set that does not only include the nodal segment identifier type and the adjacency segment identifier type;

the generating the set of segment identifiers comprises selecting another segment identifier type other than the nodal segment identifier type and the adjacency segment identifier type;

the generating the set of segment identifiers comprises;

selecting the segment identifier type as the nodal segment identifier type in a first case scenario, selecting the segment identifier type as the adjacency segment identifier type in a second case scenario;

selecting another segment identifier type other than the nodal segment identifier type and the adjacency segment identifier type in a third case scenario;

each node is segment routing enabled by being capable of supporting a segment routing protocol;

the first node is segment routing enabled by being capable of storing the set of segment identifiers;

the adjacency segment identifier type includes a node scoped network interface identifier type;

the adjacency segment identifier type includes a node scoped network interface identifier;

the adjacency segment identifier type includes a node scoped network interface of a particular node;

or

the adjacency segment identifier type includes a node scoped network interface that identifies a network interface of a node.

26. A system comprising:

a first node configured to

receive information that identifies an explicit path from the first node to a second node in a communications network, wherein

the information comprises an identification of a sequence of nodes or links defining the explicit path for a packet to traverse through the communications network;

generate a set of segment identifiers, wherein

the set of segment identifiers encodes the explicit path,

each segment identifier within the set of segment identifiers is included in one or more respective segment routing forwarding tables stored at each node along the explicit path, and

generating the set of segment identifiers comprises selecting a segment identifier type from among

a nodal segment identifier type in which a nodal segment identifier is assigned uniquely to a single node within the network, or

an adjacency segment identifier type in which an adjacency segment identifier is assigned to a link between two contiguous nodes; and

add the set of segment identifiers to a header of the packet.