Methods, systems, and computer program products for routing using headers including a sequence of node scope-specific identifiers

• US 10,382,327 B1
• Filed: 08/10/2018
• Issued: 08/13/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): Tran, Jimmy H
• Application Number:
  US16/101,382
• Time in Patent Office: 368 Days
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: H04L 45/22 Alternate routing
• 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 61/106 across networks, e.g. mapping telephone numbers to data network addresses
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes

Abstract

In various embodiments, an apparatus, a non-transitory computer-readable media, and a method are provided, involving: a current node configured to be positioned in a Multiprotocol Label Switching (MPLS) network, the current 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 one or more processors is configured to execute the instructions to cause the current node to: detect first data to be transmitted to a receiving node; identify a sequence of node scope-specific identifiers that is selected from a plurality of node scope-specific identifiers based on at least one of: the current node, the receiving node, or a policy, where each of the node scope-specific identifiers of the sequence is in one of a plurality of node scope-specific identifier spaces that is specific to a corresponding one of a plurality of nodes in a path from the current node toward the receiving node, and each of the node scope-specific identifiers of the sequence identifies, for the corresponding one of the plurality of nodes, a corresponding next node in the path from the current node toward the receiving node.

Claims

1. An apparatus, comprising:

a current node configured to be positioned in a Multiprotocol Label Switching (MPLS) network, the current 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 one or more processors is configured to execute the instructions to cause the current node to;

detect first data to be transmitted to a receiving node;

identify a sequence of node scope-specific identifiers that is selected from a plurality of node scope-specific identifiers based on at least one of;

the current node, the receiving node, or a policy, where each of the node scope-specific identifiers of the sequence is in one of a plurality of node scope-specific identifier spaces that is specific to a corresponding one of a plurality of nodes in a path from the current node toward the receiving node, and each of the node scope-specific identifiers of the sequence identifies, for the corresponding one of the plurality of nodes, a corresponding next node in the path from the current node toward the receiving node;

identify a first one of the node scope-specific identifiers of the sequence;

identify a next node, based on the first one of the node scope-specific identifiers of the sequence;

generate a first header including at least a remaining of the node scope-specific identifiers of the sequence other than the first one, for use in transmitting the first data along the path toward the receiving node; and

transmit, based on the first one of the node scope-specific identifiers of the sequence and in a first packet, the first data and the first header, including the at least remaining of the node scope-specific identifiers of the sequence other than the first one, along the path from the current node toward the next node.

2. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a loopback interface of the next node.

3. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a loopback interface of another next node.

4. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a network interface of the next node that is not a loopback interface.

5. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a network interface of another next node that is not a loopback interface.

6. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to a path node and identifies another path node in a hop included along the path from the current node toward the receiving node.

7. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is for use, by the next node in transmitting the first data along the path from the next node toward the receiving node.

8. The apparatus of claim 1, wherein the apparatus is configured such that at least one of the remaining of the node scope-specific identifiers of the sequence is for use, by a path node in transmitting the first data along the path from the path node to the receiving node.

9. The apparatus of claim 1, wherein the apparatus is configured such that the first one of the node scope-specific identifiers of the sequence is identified, based on information received from at least on other node in the MPLS network.

10. The apparatus of claim 1, wherein the apparatus is configured such that the first one of the node scope-specific identifiers of the sequence is identified by:

receiving, from the next node, mapping information in a particular identifier space specific to the next node; and

identifying the first one of the node scope-specific identifiers, based the mapping information.

11. The apparatus of claim 1, wherein the apparatus is configured such that the first one of the node scope-specific identifiers of the sequence is identified by:

receiving, from the next node, a first origin and a coordinate in a first identifier space specific to the next node, and

identifying the first one of the node scope-specific identifiers, by mapping the coordinate based on a second identifier space specific to the current node.

12. The apparatus of claim 1, wherein the apparatus is configured such that the sequence of node scope-specific identifiers is identified by:

sending a signal to a controller, and

after sending the signal, receiving, from the controller, information associated with the sequence of node scope-specific identifiers, for use in identifying the sequence of node scope-specific identifiers.

13. The apparatus of claim 12, wherein the apparatus is configured such that the controller is part of the current node.

14. The apparatus of claim 12, wherein the apparatus is configured such that the controller is separate from the current node and communicatively coupled thereto via at least one other node.

15. The apparatus of claim 1, wherein the apparatus is configured such that the sequence of node scope-specific identifiers is identified by:

sending a signal to a controller,

after sending the signal, receiving, from the controller, a mapping identifier associated with the sequence of node scope-specific identifiers, and

looking up the sequence of node scope-specific identifiers, based on the mapping identifier.

16. The apparatus of claim 1, wherein the apparatus is configured such that the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers based on at least two of:

the current node, the receiving node, and the policy.

17. The apparatus of claim 1, wherein the apparatus is configured such that the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers based on each of:

the current node, the receiving node, and the policy.

18. The apparatus of claim 1, wherein the apparatus is configured such that the receiving node is included in the MPLS network.

19. The apparatus of claim 1, wherein the apparatus is configured such that the receiving node resides outside the MPLS network.

20. The apparatus of claim 1, wherein the apparatus is configured such that the plurality of node scope-specific identifier spaces have an identical origin and thereby create a region scoped identifier space.

21. The apparatus of claim 1, wherein the apparatus is configured such that the plurality of node scope-specific identifier spaces have an identical origin and thereby create a virtual region scoped identifier space that include global identifiers in a region in which the plurality of nodes reside.

22. The apparatus of claim 21, wherein the apparatus is configured such that the region in which the plurality of nodes reside, corresponds to an area of a one-dimensional metric space represented as a data structure in a table, where the area is reserved for the plurality of node scope-specific identifiers.

23. The apparatus of claim 1, wherein the apparatus is configured such that the sequence of node scope-specific identifiers includes a node scoped network interface identifier that identifies a network interface of one of the plurality of nodes.

24. The apparatus of claim 1, wherein the apparatus is configured such that the current node includes a source node, and the first data is detected via an application or process running on the current node.

25. The apparatus of claim 1, wherein the apparatus is configured such that the current node includes a border node, and the first data is detected in an incoming packet that is received from another node.

26. The apparatus of claim 1, wherein the apparatus is configured such that the first one of the node scope-specific identifiers of the sequence, and a second one of the node scope-specific identifiers of the sequence, are identical.

27. The apparatus of claim 1, wherein the apparatus is configured such that the first one of the node scope-specific identifiers of the sequence, and a second one of the node scope-specific identifiers of the sequence, are capable of being identical, despite being specific to different nodes and being in different spaces.

30. The apparatus of claim 1, wherein the apparatus is configured such that at least one of:

the path is a virtual path;

a region in which the plurality of nodes reside, is in the MPLS network;

each node scope-specific identifiers of the sequence is in a different one of the plurality of node scope-specific identifier spaces;

at least two of the node scope-specific identifiers of the sequence are in a common one of the plurality of identifier spaces;

the first one of the node scope-specific identifiers of the sequence, is a newly designated first one after a previous first one is removed from the sequence;

the plurality of nodes in the path from the current node toward the receiving node, include the receiving node;

the first packet is received from a previous node;

the first packet is a copy of an incoming packet;

the first packet is a version of an incoming packet;

the first packet is generated;

the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers, by a previous node;

the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers, by a source node;

the sequence of node scope-specific identifiers includes a subset of the plurality of node scope-specific identifiers;

the path is a physical path;

the policy identifies an algorithm;

at least some of the plurality of nodes are not nodes that route based on segment identifiers;

the plurality of nodes includes the current node;

the corresponding next node in the path from the current node toward the receiving node, is toward the receiving node by being physically toward the receiving node;

the receiving node is included in the MPLS network;

the receiving node resides outside the MPLS network;

or

the corresponding next node in the path from the current node toward the receiving node, is toward the receiving node by being logically toward the receiving node along the path; and

further comprising at least one of a previous node or the next node.

28. A non-transitory computer-readable media storing computer instructions, that when executed by one or more processors of a current node configured to be positioned in a Multiprotocol Label Switching (MPLS) network, cause the current node to:

detect first data to be transmitted to a receiving node;

identify a sequence of node scope-specific identifiers that is selected from a plurality of node scope-specific identifiers based on at least one of;

the current node, the receiving node, or a policy, where each of the node scope-specific identifiers of the sequence is in one of a plurality of node scope-specific identifier spaces that is each specific to a corresponding one of a plurality of nodes in a path from the current node toward the receiving node, and each of the node scope-specific identifiers of the sequence identifies, for the corresponding one of the plurality of nodes, a corresponding next node in the path from the current node toward the receiving node;

identify a first one of the node scope-specific identifiers of the sequence;

identify a next node, based on the first one of the node scope-specific identifiers of the sequence;

generate a first header including at least a remaining of the node scope-specific identifiers of the sequence other than the first one, for use in transmitting the first data along the path toward the receiving node; and

transmit, based on the first one of the node scope-specific identifiers of the sequence and in a first packet, the first data and the first header, including the at least remaining of the node scope-specific identifiers of the sequence other than the first one, along the path from the current node toward the next node.

29. A method, comprising:

at a current node configured to be positioned in a Multiprotocol Label Switching (MPLS) network;

detecting first data to be transmitted to a receiving node;

identifying a sequence of node scope-specific identifiers that is selected from a plurality of node scope-specific identifiers based on at least one of;

the current node, the receiving node, or a policy, where each of the node scope-specific identifiers of the sequence is in one of a plurality of node scope-specific identifier spaces that is each specific to a corresponding one of a plurality of nodes in a path from the current node toward the receiving node, and each of the node scope-specific identifiers of the sequence identifies, for the corresponding one of the plurality of nodes, a corresponding next node in the path from the current node toward the receiving node;

identifying a first one of the node scope-specific identifiers of the sequence;

identifying a next node, based on the first one of the node scope-specific identifiers of the sequence;

generating a first header including at least a remaining of the node scope-specific identifiers of the sequence other than the first one, for use in transmitting the first data along the path toward the receiving node; and

transmitting, based on the first one of the node scope-specific identifiers of the sequence and in a first packet, the first data and the first header, including the at least remaining of the node scope-specific identifiers of the sequence other than the first one, along the path from the current node toward the next node.

31. A method, comprising the acts of:

configuring at least a portion of a plurality of instructions to cause a current node, that is positioned in a Multiprotocol Label Switching (MPLS) network, to;

detect first data to be transmitted to a receiving node,

identify a sequence of node scope-specific identifiers that is selected from a plurality of node scope-specific identifiers based on at least one of;

the current node, the receiving node, or a policy, where each of the node scope-specific identifiers of the sequence is in one of a plurality of node scope-specific identifier spaces that is specific to a corresponding one of a plurality of nodes in a path from the current node toward the receiving node, and each of the node scope-specific identifiers of the sequence identifies, for the corresponding one of the plurality of nodes, a corresponding next node in the path from the current node toward the receiving node,

identify a first one of the node scope-specific identifiers of the sequence,

identify a next node, based on the first one of the node scope-specific identifiers of the sequence,

generate a first header including at least a remaining of the node scope-specific identifiers of the sequence other than the first one, for use in transmitting the first data along the path toward the receiving node, and

transmit, based on the first one of the node scope-specific identifiers of the sequence and in a first packet, the first data and the first header, including the at least remaining of the node scope-specific identifiers of the sequence other than the first one, along the path from the current node toward the next node; and

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

32. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a loopback interface of the next node.

33. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a loopback interface of another next node.

34. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a network interface of the next node that is not a loopback interface.

35. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to the next node and identifies a network interface of another next node that is not a loopback interface.

36. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is in a particular identifier space specific to a path node and identifies another path node in a hop included along the path from the current node toward the receiving node.

37. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is for use, by the next node in transmitting the first data along the path from the next node toward the receiving node.

38. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that at least one of the remaining of the node scope-specific identifiers of the sequence is for use, by a path node in transmitting the first data along the path from the path node to the receiving node.

39. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the first one of the node scope-specific identifiers of the sequence is identified, based on information received from at least on other node in the MPLS network.

40. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the first one of the node scope-specific identifiers of the sequence is identified by;

receiving, from the next node, mapping information in a particular identifier space specific to the next node; and

identifying the first one of the node scope-specific identifiers, based the mapping information.

41. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the first one of the node scope-specific identifiers of the sequence is identified by;

receiving, from the next node, a first origin and a coordinate in a first identifier space specific to the next node, and

identifying the first one of the node scope-specific identifiers, by mapping the coordinate based on a second identifier space specific to the current node.

42. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the sequence of node scope-specific identifiers is identified by;

sending a signal to a controller, and

after sending the signal, receiving, from the controller, information associated with the sequence of node scope-specific identifiers, for use in identifying the sequence of node scope-specific identifiers.

43. The method of claim 42, wherein the controller is part of the current node.

44. The method of claim 42, wherein the method is performed by an apparatus that is configured such that the controller is separate from the current node and communicatively coupled thereto via at least one other node.

45. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the sequence of node scope-specific identifiers is identified by;

sending a signal to a controller,

after sending the signal, receiving, from the controller, a mapping identifier associated with the sequence of node scope-specific identifiers, and

looking up the sequence of node scope-specific identifiers, based on the mapping identifier.

46. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers based on at least two of;

the current node, the receiving node, and the policy.

47. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers based on each of;

the current node, the receiving node, and the policy.

48. The method of claim 31, wherein the receiving node is included in the MPLS network.

49. The method of claim 31, wherein the receiving node resides outside the MPLS network.

50. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the plurality of node scope-specific identifier spaces have an identical origin and thereby create a region scoped identifier space.

51. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the plurality of node scope-specific identifier spaces have an identical origin and thereby create a virtual region scoped identifier space that include global identifiers in a region in which the plurality of nodes reside.

52. The method of claim 51, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the region in which the plurality of nodes reside, corresponds to an area of a one-dimensional metric space represented as a data structure in a table, where the area is reserved for the plurality of node scope-specific identifiers.

53. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the sequence of node scope-specific identifiers includes a node scoped network interface identifier that identifies a network interface of one of the plurality of nodes.

54. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the current node includes a source node, and the first data is detected via an application or process running on the current node.

55. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the current node includes a border node, and the first data is detected in an incoming packet that is received from another node.

56. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the first one of the node scope-specific identifiers of the sequence, and a second one of the node scope-specific identifiers of the sequence, are identical.

57. The method of claim 31, and comprising:

further configuring the at least portion of the instructions to cause the current node to operate such that the first one of the node scope-specific identifiers of the sequence, and a second one of the node scope-specific identifiers of the sequence, are capable of being identical, despite being specific to different nodes and being in different spaces.

58. The method of claim 31, wherein at least one of:

the configuring occurs at the current node;

the configuring occurs at a certain node other than the current node;

the configuring and the further configuring occur at the current node;

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

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

the further configuring occurs at the current node and the configuring occurs at a certain node other than the current 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;

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

the 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;

the 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;

the at least portion of the instructions that is subject to the configuring is a part thereof that causes the current node to perform the detection, each instance of the identification, the generation, and the transmission;

the at least portion of the instructions that is subject to the configuring is a part thereof that causes the current node to perform at least one of the detection, each instance of the identification, the generation, or the transmission;

the at least portion of the instructions that is subject to the configuring is not a part thereof that causes the current node to perform the detection, each instance of the identification, the generation, or the transmission;

the at least portion of the instructions that is subject to the configuring is a part thereof that causes the current node to perform at least one operation other than the detection, each instance of the identification, the generation, and the transmission;

the configuring includes customization;

the configuring includes causing the first one of the node scope-specific identifiers of the sequence to be identified;

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

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

the 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 current node, for execution;

the 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 current node;

the 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 current node, so that the current node is provided to a user for use;

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

the causing storage includes causing transfer of the at least portion of the 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 method further comprises configuring the current node;

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

the method further comprises providing the current 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 current node;

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

the instructions are hardware instructions;

the instructions are software instructions;

the instructions is software code;

the path is a virtual path;

a region in which the plurality of nodes reside, is in the MPLS network;

each node scope-specific identifiers of the sequence is in a different one of the plurality of node scope-specific identifier spaces;

at least two of the node scope-specific identifiers of the sequence are in a common one of the plurality of identifier spaces;

the first one of the node scope-specific identifiers of the sequence, is a newly designated first one after a previous first one is removed from the sequence;

the plurality of nodes in the path from the current node toward the receiving node, include the receiving node;

the first packet is received from a previous node;

the first packet is a copy of an incoming packet;

the first packet is a version of an incoming packet;

the first packet is generated;

the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers, by a previous node;

the sequence of node scope-specific identifiers is selected from the plurality of node scope-specific identifiers, by a source node;

the sequence of node scope-specific identifiers includes a subset of the plurality of node scope-specific identifiers;

the path is a physical path;

the policy identifies an algorithm;

at least some of the plurality of nodes are not nodes that route based on segment identifiers;

the plurality of nodes includes the current node;

the corresponding next node in the path from the current node toward the receiving node, is toward the receiving node by being physically toward the receiving node;

the receiving node is included in the MPLS network;

the receiving node resides outside the MPLS network;

or

the corresponding next node in the path from the current node toward the receiving node, is toward the receiving node by being logically toward the receiving node along the path.