Routing methods, systems, and computer program products

• US 10,374,938 B1
• Filed: 04/24/2018
• Issued: 08/06/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): Swearingen, Jeffrey R
• Assistant Examiner(s): Gidado, Oluwatosin M
• Application Number:
  US15/961,832
• Time in Patent Office: 469 Days
• Field of Search: 709245
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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/12 Shortest path evaluation
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

In one embodiment, an apparatus is provided, comprising: 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 one or more processors is configured to execute the instructions to: receive a packet at a current node in a network path between a source node and a destination node, the network path including a path node between the current node and the destination node that is not the destination node and that is reachable by a plurality of path portions including a first path portion that includes multiple hops, and a second path portion; in response to the receipt of the packet at the current node, identify a header and data of the packet, the header including a segment identifier that identifies the path node that is not the destination node, where the destination node is outside a domain of a multiple protocol-labeling switch (MPLS) network protocol in accordance with which the path node operates and the segment identifier identifies the path node in the domain of the MPLS network protocol; detect the segment identifier that identifies the path node that is not the destination node; determine, based on the segment identifier that identifies the path node that is not the destination node, that the data is to be sent to the path node; and based on the determination, send the data to the path node via at least one of the plurality of path portions.

Claims

1. An apparatus, comprising:

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 one or more processors is configured to execute the instructions to;

receive a packet at a current node in a network path between a source node and a destination node, the network path including a path node between the current node and the destination node that is not the destination node and that is reachable by a plurality of path portions including a first path portion that includes multiple hops, and a second path portion;

in response to the receipt of the packet at the current node, identify a header of the packet, the header configured for use in identifying a segment identifier that identifies the path node that is not the destination node, where the destination node is outside a domain utilizing at least one aspect of a Multiprotocol Label Switching (MPLS) network protocol in accordance with which the path node operates and the segment identifier identifies the path node in the domain utilizing the at least one aspect of the Multiprotocol Label Switching (MPLS) network protocol;

identify the segment identifier that identifies the path node that is not the destination node;

determine, based on the segment identifier that identifies the path node that is not the destination node, that data is to be sent to the path node; and

based on the determination, send the data to the path node via at least one of the plurality of path portions.

2. The apparatus of claim 1, wherein the apparatus is configured such that the segment identifier is identical to another segment identifier that, for another node in the network path, identifies the path node.

3. The apparatus of claim 2, wherein the apparatus is configured such that the current node and the another node are both configured to use identical node-specific identifier spaces.

4. The apparatus of claim 3, wherein the apparatus is configured such that global identifiers are realized as a result of the current node and the another node each being configured to use one of the identical node-specific identifier spaces.

5. The apparatus of claim 2, wherein the another node is a previous node, and the apparatus is configured to use the segment identifier as a replacement for the another segment identifier.

6. The apparatus of claim 1, wherein the apparatus is further configured to process protocol identifiers other than the segment identifier.

7. The apparatus of claim 1, wherein the apparatus is further configured to route Internet Protocol addresses from at least one global identifier space specified by at least one of:

RFC 791 or RFC 3513.

8. An apparatus, comprising:

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 one or more processors is configured to execute the instructions to;

receive, from a previous node, a packet at a current node in a network path between a source node and a destination node where the previous node is included in a portion of the network path that starts with the source node and ends before the current node, the network path including a path node between the current node and the destination node that is not the destination node and that is reachable by a plurality of path portions including a first path portion that includes multiple hops, and a second path portion;

in response to the receipt of the packet at the current node, identify a header of the packet, the header configured for use in identifying a segment identifier that identifies the path node that is not the destination node, where the destination node is outside a domain utilizing at least one aspect of a Multiprotocol Label Switching (MPLS) network protocol in accordance with which the path node operates;

perform, by the current node, a mapping that results in the header being configured for use in identifying another segment identifier that identifies the path node that is not the destination node, for use by the path node that is not the destination node in transmitting data; and

based on the segment identifier that identifies the path node that is not the destination node, send the another segment identifier and the data to the path node via at least one of the plurality of path portions.

9. The apparatus of claim 8, wherein the apparatus is configured such that the segment identifier is identical to the another segment identifier.

10. The apparatus of claim 8, wherein the apparatus is configured such that the current node and the previous node are both configured to use identical node-specific identifier spaces.

11. The apparatus of claim 10, wherein the apparatus is configured such that global identifiers are realized as a result of the current node and the previous node each being configured to use one of the identical node-specific identifier spaces with identical identifiers configured to identify the same respective nodes.

12. The apparatus of claim 11, wherein the apparatus is configured such that the global identifiers include a same value for the path node for use in the domain utilizing the at least one aspect of the Multiprotocol Label Switching (MPLS) network protocol.

13. The apparatus of claim 8, wherein the apparatus is further configured to process protocol identifiers other than the segment identifier and other than the another segment identifier.

14. The apparatus of claim 8, wherein the apparatus is further configured to route Internet Protocol addresses from at least one global identifier space specified by at least one of:

RFC 791 or RFC 3513.

15. An apparatus, comprising:

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 one or more processors is configured to execute the instructions to;

receive a packet at a current node in a network path between a source node and a destination node, the network path including a path node, that is in a same region as the current node and that is not the destination node, between the current node and the destination node, the path node being reachable by a plurality of path portions including a first path portion that includes multiple hops, and a second path portion;

in response to the receipt of the packet at the current node, identify a header of the packet, the header including a plurality of segment identifiers including a first region scoped segment identifier that is in a region scoped identifier space of the same region and that globally identifies the path node within the same region, and a second segment identifier;

identify at least one of the plurality of segment identifiers from the header of the packet;

in the event that the first region scoped segment identifier is identified determine, based on the first region scoped segment identifier, that data of the packet is to be sent to the path node; and

based on the determination, send the data to the path node via at least one of the plurality of path portions.

16. The apparatus of claim 15, wherein the apparatus is configured such that the first region scoped segment identifier is identical to a second region scoped segment identifier that, for another node in the network path, identifies the path node.

17. The apparatus of claim 16, wherein the apparatus is configured such that the current node and the another node are both configured to use identical node-specific identifier spaces.

18. The apparatus of claim 17, wherein the apparatus is configured such that global identifiers are realized as a result of the current node and the another node both being configured to use the identical node-specific identifier spaces.

19. The apparatus of claim 16, wherein the another node is a previous node, and the apparatus is configured to use the first region scoped segment identifier as a replacement for the second region scoped segment identifier.

20. The apparatus of claim 15, wherein the apparatus is further configured to process protocol identifiers other than the segment identifiers.

21. The apparatus of claim 15, wherein the apparatus is further configured to route Internet Protocol addresses from at least one global identifier space specified by at least one of:

RFC 791 or RFC 3513.

22. An apparatus, comprising:

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 one or more processors is configured to execute the instructions to;

receive, from a previous node, a packet at a current node in a network path between a source node and a destination node where the previous node is included in a portion of the network path that starts with the source node and ends before the current node, the network path including a path node between the current node and the destination node that is not the destination node and that is reachable by a plurality of path portions including a first path portion that includes multiple hops, and a second path portion;

in response to the receipt of the packet at the current node, identify a header of the packet, the header including a plurality of segment identifiers including a segment identifier that identifies the path node;

identify at least one of the plurality of segment identifiers from the header of the packet;

replace, in the header and based on a mapping performed by the current node, the segment identifier with another segment identifier that identifies the another segment identifier for use by the path node that is not the destination node in transmitting data; and

based on the segment identifier that identifies the path node, send the another segment identifier and the data of the packet to the path node via at least one of the plurality of path portions.

23. The apparatus of claim 22, wherein the apparatus is configured such that the segment identifier is identical to the another segment identifier.

24. The apparatus of claim 23, wherein the apparatus is configured such that the previous node and the current node are both configured to use identical node-specific identifier spaces.

25. The apparatus of claim 24, wherein the apparatus is configured such that global identifiers are realized as a result of the previous node and the current node each being configured to use one of the identical node-specific identifier spaces.

26. The apparatus of claim 22, wherein the apparatus is further configured to process protocol identifiers other than the segment identifiers.

27. The apparatus of claim 22, wherein the apparatus is further configured to route Internet Protocol addresses from at least one global identifier space specified by at least one of:

RFC 791 or RFC 3513.

28. The apparatus of claim 22, wherein the apparatus is configured such that only one of the plurality of segment identifiers is identified.

29. The apparatus of claim 24, wherein at least one of:

the mapping involves a metric space;

the mapping controls the replacing;

the replacing includes replacing a particular position of the segment identifier, with the another segment identifier;

the replacing includes replacing a particular header position of the segment identifier, with the another segment identifier;

the replacing includes replacing a use of the segment identifier, with a use of the another segment identifier;

the another segment identifier and the data of the packet is sent to the path node via the at least one of the plurality of path portions, without the segment identifier being sent;

the mapping involves a mapping rule;

the mapping involves identifying based on an association;

the mapping involves identifying a particular identifier based on an association thereof with another identifier;

the mapping reduces a number of lookup tables that must be maintained;

the mapping reduces a number of records that must be maintained;

the mapping reduces a number of lookup tables that must be accessed;

the mapping reduces a number of records that must be accessed;

the another segment identifier is included in the packet when the packet is received at the current node;

an identifier of each node-specific identifier space does not define a scope for the identifier;

each node-specific identifier space includes a network interface-specific identifier space;

each identifier includes an address;

each identifier space includes an address space;

a loop-back internet identifier is associated with at least one of the segment identifier or the another segment identifier;

a loop-back internet identifier is associated with the another segment identifier, by virtue of the loop-back internet identifier and the another segment identifier both being specific to the current node;

the apparatus is configured to not use a Multiprotocol Label Switching (MPLS) control plane protocol;

the another segment identifier identifies a hop path;

the another segment identifier does not identify a hop path;

the network path includes a physical network path;

the network path includes a virtual network path;

the apparatus is part of the current node;

the apparatus constitutes at least a portion of the current node;

the apparatus includes the current node;

the apparatus is part of a system that includes the current node;

the current node includes a device of the apparatus having a network interface component;

the current node includes a portion of the apparatus including at least a network interface component;

the current node includes at least a network interface component of the apparatus;

the segment identifier is capable of identifying a single hop in a physical network;

the segment identifier is capable of identifying multiple hops in a physical network;

the segment identifier is capable of identifying a single hop in a virtual network;

the segment identifier is capable of identifying multiple hops in a virtual network;

the segment identifier identifies a hop path;

the segment identifier includes a scoped identifier;

the segment identifier does not include a scoped identifier;

the segment identifier is identified by being received;

the segment identifier is identified by being detected;

routing tables are not required when protocol identifiers include the segment identifiers;

routing policies are not required when protocol identifiers include the segment identifiers;

the data of the packet is sent to the path node in the packet;

the data of the packet is sent to the path node in another packet that is a copy of the packet;

or

the data of the packet is sent to the path node in another packet that is at least partially similar to the packet.