Routing methods, systems, and computer program products

• US 11,012,344 B1
• Filed: 02/20/2020
• Issued: 05/18/2021
• 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): Patel, Parth
• Assistant Examiner(s): Belete, Berhanu D
• Application Number:
  US16/796,931
• Time in Patent Office: 453 Days
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses

Abstract

In various embodiments, an apparatus, a non-transitory computer-readable media, and a method are provided, involving a technique to: receive, from at least one other node in a network, a plurality of segment identifiers, utilizing at least one of a link state protocol, a distance vector protocol, or a path vector protocol, store, in a data structure, the plurality of segment identifiers associated with nodes represented in a topology of at least a portion of a network, select, from the plurality of segment identifiers in the data structure and based on a specified policy, a first sequence of segment identifiers that identify a first sequence of at least one of: one or more nodes, one or more network interfaces, or one or more network regions, at least partially in a first path segment that communicatively couples the transmitting node with a receiving node in the network and that includes at least one particular node which is not predetermined by the first sequence of segment identifiers such that the at least one particular node is determined during routing of data between the transmitting node and the receiving node, identify, based on a segment identifier in a first subsequence, of the first sequence of segment identifiers, that precedes a second subsequence of the first sequence of segment identifiers, a first network interface of the transmitting node in the first path segment, store at least the second subsequence of the first sequence of segment identifiers in a header associated with a first packet, and transmit, via the first network interface, the first packet for delivering the data in a payload of the first packet to the receiving node in the network.

Claims

1. A method, comprising:

performing at least one act that is configured to cause a transmitting node to;

receive, from at least one other node in a network, a plurality of segment identifiers, utilizing at least one of a link state protocol, a distance vector protocol, or a path vector protocol,

store, in a data structure, the plurality of segment identifiers associated with nodes represented in a topology of at least a portion of a network,

select, from the plurality of segment identifiers in the data structure and based on a specified policy, a first sequence of segment identifiers that identify a first sequence of at least one of;

one or more nodes, one or more network interfaces, or one or more network regions, at least partially in a first path segment that communicatively couples the transmitting node with a receiving node in the network and that includes at least one particular node which is not predetermined by the first sequence of segment identifiers such that the at least one particular node is determined during routing of data between the transmitting node and the receiving node,

identify, based on a segment identifier in a first subsequence, of the first sequence of segment identifiers, that precedes a second subsequence of the first sequence of segment identifiers, a first network interface of the transmitting node in the first path segment,

store at least the second subsequence of the first sequence of segment identifiers in a header associated with a first packet, and

transmit, via the first network interface, the first packet for delivering the data in a payload of the first packet to the receiving node in the network; and

causing storage of a result of the at least one act on at least one non-transitory memory.

2. The method of claim 1, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first sequence of segment identifiers includes a first node scoped network interface identifier that is selected based on a representation of a link from a first node to a second node in the first path segment that communicatively couples the transmitting node with the receiving node in the network.

3. The method of claim 2, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node scoped network interface identifier is in a first node scoped identifier space that spans within the first node and identifies, for the first node, a particular network interface of the first node in the link.

4. The method of claim 2, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the at least one of the link state protocol, the distance vector protocol, or the path vector protocol is utilized to receive, from the at least one other node in the network, particular data that associates the first node scoped network interface identifier and the link, wherein the particular data is based on data transmitted by the first node to the at least one other node in the network.

5. The method of claim 3, and comprising:

performing at least one additional act that is configured to cause the transmitting node to;

receive an indication that the link has failed, utilizing the at least one of the link state protocol, the distance vector protocol, or the path vector protocol; and

update a data structure in response to the receipt of the indication.

6. The method of claim 5, and comprising:

performing at least one additional act that is configured to cause the transmitting node to;

determine, based on the updated data structure, a second sequence of segment identifiers that identify a second sequence of at least one of;

one or more nodes, one or more network interfaces, or one or more network regions, at least partially in a second path segment that communicatively couples the transmitting node with the receiving node in the network, where the second sequence of segment identifiers does not include the first node scoped network interface identifier;

store at least an end portion of the second sequence of segment identifiers in a header associated with a second packet;

identify, based on a segment identifier that precedes the end portion of the second sequence of segment identifiers, a second network interface of the transmitting node in the second path segment; and

transmit, via the second network interface, the second packet for delivering data in a payload of the second packet to the receiving node in the network.

7. The method of claim 6, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the second network interface is not the first network interface.

8. The method of claim 6, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the second sequence of segment identifiers is identical to the first sequence of segment identifiers.

9. The method of claim 6, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the determining the second sequence of segment identifiers comprises;

identifying, based on the updated data structure, a path segment identifier that is not included in the first sequence of segment identifiers and that identifies at least one of;

a network interface, a node, or a region that, without utilizing the failed link, communicatively couples the first node with a path node in a portion of the first path segment that communicatively couples the first node to the receiving node; and

including the path segment identifier in the second sequence of segment identifiers in a location that follows a segment identifier that identifies the first node.

10. The method of claim 9, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment identifier identifies, for at least the first node, the second node that is communicatively coupled to the first node via a particular path segment that is selectable based on the path segment identifier.

11. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment identifier includes another node scoped identifier, in the first node scoped identifier space, that identifies another network interface in another link that includes the second node.

12. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment communicatively couples the first node with the second node, and is selectable, based on the path segment identifier, from a routing table of the first node.

13. The method of claim 12, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment communicatively couples the first node with the second node, and is selectable from a plurality of path segments that communicatively couple the first node with the second node.

14. The method of claim 13, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the plurality of path segments includes at least one multi-hop path segment.

15. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that both the first node and the second node are in a particular region of the network that is within a span of a particular identifier space that includes particular identifiers that identify at least a portion of particular nodes in the particular region.

16. The method of claim 15, wherein at least one of:

the at least one act is performed at the transmitting node;

the at least one act is performed at a certain node other than the transmitting node;

the at least one act and the at least one additional act are performed at the transmitting node;

the at least one act and the at least one additional act are performed at a certain node other than the transmitting node;

the at least one act and the at least one additional act are performed at a certain node other than the transmitting node;

the at least one act and the at least one additional act are performed at a certain node other than the transmitting node;

at least one of the at least one act or the at least one additional act includes a configuration;

at least one of the at least one act or the at least one additional act includes a configuration of instructions;

the at least one act causes the transmitting node to perform the receipt, each instance of the receipt, the storage, the selection, the identification, and the transmission;

the at least one act causes the transmitting node to perform at least one of the receipt, the storage, the selection, the identification, or the transmission;

the at least one act causes at least one operation to be performed other than the receipt, the storage, the selection, the identification, and the transmission;

the causing storage includes causing storage of at least portion of instructions on the at least one non-transitory memory for being accessible to a user so that the user is capable of installing the at least portion of the instructions on other memory of the transmitting node, for execution;

the causing storage includes causing storage of at least portion of instructions on the at least one non-transitory memory, that is part of the transmitting node;

the causing storage includes causing storage of at least portion of instructions on the at least one non-transitory memory, that is part of the transmitting node, so that the transmitting node is provided to a user for use;

the causing storage includes installation;

the causing storage includes causing transfer of at least portion of instructions from persistent storage to volatile memory;

the at least one non-transitory memory includes a register;

the at least one non-transitory memory includes volatile memory;

the at least one non-transitory memory includes persistent storage;

the phrases at least one act and transmitting node do not invoke 35 U.S.C. 112, sixth paragraph;

the method further comprises configuring the transmitting node;

the method further comprises coupling the at least one non-transitory memory to one or more processors;

the method further comprises providing the transmitting node;

the method further comprises providing the at least one non-transitory memory;

the method further comprises providing one or more processors;

the at least one non-transitory memory is part of the transmitting node;

or

the at least one non-transitory memory is separate from transmitting node memory of the transmitting node.

17. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node is in a particular region of the network that is within a span of a particular identifier space that includes particular identifiers that identify at least a portion of particular nodes in the particular region, where the second node is not in the particular region.

18. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that both the first node and the second node are in a domain of at least one of;

a link state protocol, a distance vector protocol, or a path vector protocol utilized for communicating at least some segment identifiers of nodes or network interfaces within the domain.

19. The method of claim 10, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node is in a domain where at least one of;

a link state protocol, a distance vector protocol, or a path vector protocol utilized for communicating at least some identifiers of nodes or network interfaces within the domain and the second node is not in the domain.

20. The method of claim 9, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment identifier identifies, for at least the first node, a third node that follows the second node in the first path segment and that is communicatively coupled to the first node via a particular path segment that is selectable based on the path segment identifier.

21. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment identifier includes another node scoped identifier, in the first node scoped identifier space, that identifies another network interface in another link that includes the third node.

22. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment that communicatively couples the first node with the third node is selectable, based on the path segment identifier, from a routing table.

23. The method of claim 22, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment that communicatively couples the first node and the third node is selectable from a plurality of path segments that communicatively couple the first node with the third node.

24. The method of claim 23, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the plurality of path segments that communicatively couple the first node with the second node include at least one multi-hop path segment.

25. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that both the first node and the third node are in a region of the network that is within a span of an identifier space that includes identifiers that identify at least a portion of the nodes in the region.

26. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node is in a region of the network that is within a span of an identifier space that includes identifiers that identify at least a portion of the nodes in the region and the third node that is not in the region.

27. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that both the first node and the third node are in a domain where at least one of a link state protocol, a distance vector protocol, or a path vector protocol utilized for communicating at least some identifiers of nodes or network interfaces within the domain.

28. The method of claim 20, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node is in a domain where at least one of a link state protocol, a distance vector protocol, or a path vector protocol utilized for communicating at least some identifiers of nodes or network interfaces within the domain.

29. The method of claim 9, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the path segment identifier includes at least one of;

a node scope-specific identifier in a node scope-specific identifier space specific to the first node, another node scoped network interface identifier in the node scoped identifier space that spans the first node, a region scoped identifier in a region scoped identifier space of a region that includes the first node, a region scope-specific identifier specific to the region that includes the first node, or an outside scope identifier that, for the first node, identifies a region that does not include the first node.

30. The method of claim 9, and comprising:

performing at least one additional act that is configured to cause the transmitting node to operate such that the first node includes the transmitting node.