Routing methods, systems, and computer program products

• US 10,367,737 B1
• Filed: 11/19/2018
• Issued: 07/30/2019
• 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): Ohri, Romani
• Application Number:
  US16/195,816
• Time in Patent Office: 253 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: generate a first data structure identifying a mapping of a first path segment identifier to a first network interface that is included in the first node or that is included in a hop including an additional node reachable from the first node, where the first path segment identifier identifies a first path segment that is selected from a plurality of path segments based on at least one of a policy, a metric, or a routing table; receive an incoming data packet with a header including incoming network path information that includes the first path segment identifier as an active identifier in the incoming path information; identify a second path segment identifier as the active identifier rather than the first path identifier in outgoing network path information for a header of an outgoing data packet; and forward the outgoing data packet via the first network interface that is identified based on the first path segment identifier utilizing the mapping, wherein the second path segment identifier in the outgoing network path information identifies a second network interface of a different node in the network.

Claims

1. A non-transitory computer-readable media storing computer instructions that;

when executed by one or more processors of a first node in a network where the network further includes a previous node configured to utilize, for forwarding data toward the first node, a previous path segment identifier that identifies one of a particular network interface of the first node or a particular network interface of a particular node that relays the data forwarded by the previous node;

cause the first node to;

generate a first data structure identifying a mapping of a first path segment identifier to a first network interface that is included in the first node or that is included in a hop including an additional node reachable from the first node, where the first path segment identifier identifies a first path segment that is selected from a plurality of path segments based on at least one of a policy, a metric, or a routing table;

receive an incoming data packet with the data, and with a header including incoming network path information that includes the first path segment identifier as an active identifier in the incoming path information;

identify a second path segment identifier as the active identifier rather than the first path identifier in outgoing network path information for a header of an outgoing data packet, the outgoing data packet including the data; and

forward the outgoing data packet via the first network interface that is identified based on the first path segment identifier utilizing the mapping, wherein the second path segment identifier in the outgoing network path information identifies a second network interface of a different node in the network.

2. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

send mapping information that identifies the mapping to a second node in the network.

3. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

send particular information that identifies the first node to a second node in the network.

4. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

send particular information that identifies a second node to a third node in the network.

5. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

receive, by the first node from a third node in the network, particular information that identifies a second node in the network to the first node.

6. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

store data that maps a second node identifier of a second node to a certain network interface of the first node that is capable of communicatively coupling the first node and the second node.

7. The non-transitory computer-readable media of claim 6, further including instructions that, when executed by the one or more processors, cause the first node to operate such that at least one of:

said certain network interface includes the first network interface;

said certain network interface includes a network interface other than the first network interface;

said first path segment that is identified by the first path segment identifier includes the first network interface;

said active identifier indicates which identifier to use;

said active identifier includes a pointer as to which identifier a certain node should use;

said active identifier indicates to use the first path segment identifier;

said active identifier initially identifies the first path segment identifier for routing by the first node, and then is updated in the header to identify the second path segment identifier as the active identifier for use by the different node;

said first path segment is one of the plurality of path segments;

said first path segment includes a multi-hop path segment;

said first path segment does not include a multi-hop path segment;

said first path segment is selected, based on at least two of the policy, the routing table, or the metric;

said first path segment is selected, based on at least all of the policy, the routing table, and the metric;

said first path segment is selected, based on the policy;

said first path segment is selected, based on the routing table;

said first path segment is selected, based on the metric;

said first network interface is included in the first node;

said first network interface is included in the hop including the additional node reachable from the first node;

said first network interface is included in the hop by being included in the additional node reachable from the first node;

said first data structure includes the mapping;

said first data structure is configured for being used to locate the mapping;

said second path segment identifier is identified as the active identifier rather than the first path identifier in the outgoing network path information for the header of the outgoing data packet, so that the second path segment identifier is used by the different node for forwarding purposes;

said non-transitory computer-readable media is included as part of a system that further comprises the first node;

or

said non-transitory computer-readable media is included as part of the first node.

8. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to:

receive, at the first node, structured data generated by a second node in the network, the structured data identifying a mapping of the second path segment identifier to the second network interface that is included in the second node or that is included in a hop including an additional node reachable from the second node.

9. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that the first network interface is included in the first node in the network.

10. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that the first network interface is included in the hop including the additional node reachable from the first node.

11. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that the first path segment identifier is deterministic.

12. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that the first path segment identifier identifies only the first path segment.

13. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that the second path segment identifier is identified as the active identifier rather than the first path identifier in the outgoing network path information for the header of the outgoing data packet, so that the second path segment identifier is used by the different node for forwarding purposes.

14. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the first path segment identifier and the second path segment identifier are part of network path information that is predetermined by multiple topology nodes.

15. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the first path segment identifier and the second path segment identifier are part of network path information that is predetermined by another node other than the first node.

16. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

a network path defined by the plurality of path segments is specified using a first number of identifiers that is fewer than a second number of identifiers required to specify the network path deterministically.

17. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the first path segment is selected without control signaling after the receipt of the incoming data packet.

18. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the outgoing data packet is capable of being forwarded by the first node along different ones of the plurality of path segments.

19. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the outgoing data packet is capable of being forwarded by the first node along different ones of the plurality of path segments based on;

a particular policy, and a state of the network at a time when the incoming data packet is received.

20. The non-transitory computer-readable media of claim 19, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

the plurality of path segments are predetermined before the incoming data packet is received by the first node, and the selection of the first path segment is performed by the first node based on;

the particular policy, and the state of the network at the time when the incoming data packet is received.

21. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the first node to operate such that:

a current state of the network is not maintained by the first node.

22. An apparatus, comprising:

a first node including at least one non-transitory memory configured to store instructions, and one or more processors in communication with the at least one non-transitory memory, wherein the first node is configured for being positioned in a network that further includes a previous node configured to utilize, for forwarding data toward the first node, a previous path segment identifier that identifies one of a particular network interface of the first node or a particular network interface of a particular node that relays the data forwarded by the previous node, and further wherein the one or more processors is configured to execute the instructions to cause the first node to;

generate a first data structure identifying a mapping of a first path segment identifier to a first network interface that is included in the first node or that is included in a hop including an additional node reachable from the first node, where the first path segment identifier identifies a first path segment that is selected from a plurality of path segments based on at least one of a policy, a metric, or a routing table;

receive an incoming data packet with the data, and with a header including incoming network path information that includes the first path segment identifier as an active identifier in the incoming path information;

identify a second path segment identifier as the active identifier rather than the first path identifier in outgoing network path information for a header of an outgoing data packet, the outgoing data packet including the data; and

forward the outgoing data packet via the first network interface that is identified based on the first path segment identifier utilizing the mapping, wherein the second path segment identifier in the outgoing network path information identifies a second network interface of a different node.

23. A first node configured for operation in a network that further includes a previous node configured to utilize, for forwarding data toward the first node, a previous path segment identifier that identifies one of a particular network interface of the first node or a particular network interface of a particular node that relays the data forwarded by the previous node, comprising:

means for generating a first data structure identifying a mapping of a first path segment identifier to a first network interface that is included in the first node or that is included in a hop including an additional node reachable from the first node, where the first path segment identifier identifies a first path segment that is selected from a plurality of path segments based on at least one of a policy, a metric, or a routing table;

means for receiving an incoming data packet with the data, and with a header including incoming network path information that includes the first path segment identifier as an active identifier in the incoming path information;

means for identifying a second path segment identifier as the active identifier rather than the first path identifier in outgoing network path information for a header of an outgoing data packet, the outgoing data packet including the data; and

means for forwarding the outgoing data packet via the first network interface that is identified based on the first path segment identifier utilizing the mapping, wherein the second path segment identifier in the outgoing network path information identifies a second network interface of a different node.

24. A method, comprising the acts of:

configuring at least a portion of instructions for a first node configured to be positioned in a network that further includes a previous node configured to utilize, for forwarding data toward the first node, a previous path segment identifier that identifies one of a particular network interface of the first node or a particular network interface of a particular node that relays the data forwarded by the previous node, wherein the instructions cause the first node to;

generate a first data structure identifying a mapping of a first path segment identifier to a first network interface that is included in the first node or that is included in a hop including an additional node reachable from the first node, where the first path segment identifier identifies a first path segment that is selected from a plurality of path segments based on at least one of a policy, a metric, or a routing table, receive an incoming data packet with the data, and with a header including incoming network path information that includes the first path segment identifier as an active identifier in the incoming path information,

identify a second path segment identifier as the active identifier rather than the first path identifier in outgoing network path information for a header of an outgoing data packet, the outgoing data packet including the data, and

forward the outgoing data packet via the first network interface that is identified based on the first path segment identifier utilizing the mapping, wherein the second path segment identifier in the outgoing network path information identifies a second network interface of a different node; and

causing storage of the at least portion of the instructions on at least one non-transitory memory.

25. The method of claim 24, and comprising:

further configuring the at least portion of the instructions, where the instructions cause the first node to operate such that the previous path segment identifier identifies the particular network interface of the first node, and the incoming data packet is directly received, by the first node, from the previous node.

26. The method of claim 24, and comprising:

further configuring the at least portion of the instructions, where the instructions cause the first node to operate such that the previous path segment identifier identifies the particular network interface of the particular node, and the incoming data packet is received, by the first node, from the particular node.

27. The method of claim 24, and comprising:

further configuring the at least portion of the instructions, where the instructions cause the first node to operate such that the second path segment identifier is identified as the active identifier without control signaling after the receipt of the incoming data packet.

28. The method of claim 24, and comprising:

further configuring the at least portion of the instructions, where the instructions cause the first node to operate such that contents of the header of the incoming data packet include everything necessary for the first node to forward the data.

29. The method of claim 24, and comprising:

further configuring the at least portion of the instructions, where the instructions cause the first node to operate such that a current state of the network is not maintained by the first node, nor the previous node, nor the additional node, and nor the different node.

30. The method of claim 29, wherein at least one of:

said first path segment that is identified by the first path segment identifier includes the first network interface;

said active identifier indicates which identifier to use;

said active identifier includes a pointer as to which identifier a certain node should use;

said active identifier indicates to use the first path segment identifier;

said active identifier initially identifies the first path segment identifier for routing by the first node, and then is updated in the header to identify the second path segment identifier as the active identifier for use by the different node;

said first path segment is one of the plurality of path segments;

said first path segment includes a multi-hop path segment;

said first path segment does not include a multi-hop path segment;

said first path segment is selected, based on at least two of the policy, the routing table, or the metric;

said first path segment is selected, based on at least all of the policy, the routing table, and the metric;

said first path segment is selected, based on the policy;

said first path segment is selected, based on the routing table;

said first path segment is selected, based on the metric;

said first network interface is included in the first node;

said first network interface is included in the hop including the additional node reachable from the first node;

said first network interface is included in the hop by being included in the additional node reachable from the first node;

said first data structure includes the mapping;

said first data structure is configured for being used to locate the mapping;

said second path segment identifier is identified as the active identifier rather than the first path identifier in the outgoing network path information for the header of the outgoing data packet, so that the second path segment identifier is used by the different node for forwarding purposes;

said non-transitory memory is included as part of a system that further comprises the first node;

said non-transitory memory is included as part of the first node;

said non-transitory memory is not included as part of a system that further comprises the first node;

said non-transitory memory is not included as part of the first node;

said configuring occurs at the first node;

said configuring occurs at a certain node other than the first node;

said configuring and the further configuring occur at the first node;

said configuring and the further configuring occur at a certain node other than the first node;

said configuring occurs at the first node and the further configuring occurs at a certain node other than the first node;

said further configuring occurs at the first node and the configuring occurs at a certain node other than the first node;

only part of the instructions is subject to the configuring;

only the at least portion of the instructions is subject to the configuring;

an entirety of the instructions is subject to the configuring;

said at least portion of the instructions that is subject to the configuring, is also subject to the further configuring;

said at least portion of the instructions that is subject to the configuring, is the same as the at least portion of the instructions that is subject to the further configuring;

said at least portion of the instructions that is subject to the configuring, is different from the at least portion of the instructions that is subject to the further configuring;

a first part of the at least portion of the instructions is subject to the configuring, and a second part of the at least portion of the instructions that is subject to the further configuring;

said at least portion of the instructions that is subject to the configuring is a part thereof that causes the first node to perform the generation, the receipt, the identification, and the forwarding;

said at least portion of the instructions that is subject to the configuring is a part thereof that causes the first node to perform at least one of the generation, the receipt, the identification, or the forwarding;

said at least portion of the instructions that is subject to the configuring is not a part thereof that causes the first node to perform the generation, the receipt, the identification, or the forwarding;

said at least portion of the instructions that is subject to the configuring is a part thereof that causes the first node to perform at least one operation other than the generation, the receipt, the identification, and the forwarding;

said configuring includes customization;

said configuring causes the second path segment identifier to be identified as the active identifier;

said plurality of the instructions includes a subset of instructions required for the first node to operate;

said plurality of the instructions includes an entirety of instructions required for the first node to operate;

said causing storage includes causing storage of the at least portion of the 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 first node, for execution;

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

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

said causing storage includes installation of the at least portion of the instructions;

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

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

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

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

said method further comprises configuring the first node;

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

said method further comprises providing the first node;

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

said method further comprises providing one or more processors;

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

said at least one non-transitory memory is separate from first node memory of the first node;

said instructions are hardware instructions;

said instructions are software instructions;

said instructions is software code;

an entirety of the instructions are caused to be stored;

said method further comprises executing the instructions;

or

said instructions cause the first node to perform the generation, the receipt, the identification, and the forwarding, in response to being executed via at least one processor of the first node.