Routing methods, systems, and computer program products

• US 10,447,575 B1
• Filed: 11/19/2018
• Issued: 10/15/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): Kamara, Mohamed A
• Application Number:
  US16/195,827
• Time in Patent Office: 330 Days
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

In various embodiments, an apparatus, a non-transitory computer-readable media, and a method are provided, involving a technique to: receive, from a network node located in a second region of the network, a packet along with a header having network path information that includes an outside-scope identifier that identifies the first region without identifying a single particular network node, a single particular interface, nor a single particular link; responsive to receiving the packet, identify a next indicator that identifies a next identifier in the network path information for the border node; modify the next indicator to identify, for another node, another identifier in the network path information; and forward the packet according to the next identifier to deliver data in the packet to the another node via the at least one network interface in the first region.

Claims

1. A non-transitory computer-readable media storing computer instructions that, when executed by one or more processors of a border node configured to have at least one network interface positioned in a first region of a network that includes a plurality of first-region network nodes, cause the border node to:

receive, from a network node located in a second region of the network, a packet along with a header having therein network path information that includes, in the header, an outside-scope identifier that identifies the first region without identifying a single particular network node, a single particular interface, nor a single particular link;

responsive to receiving the packet, identify, in the header, a next indicator that identifies a next identifier in the network path information for the border node;

modify, in the header, the next indicator to identify, for another node, another identifier in the network path information; and

forward the packet according to the next identifier to deliver data in the packet to the another node via the at least one network interface in the first region.

2. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the first region is an Interior Gateway Protocol (IGP) area.

3. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the first region is a Border Gateway Protocol Autonomous System.

4. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the first region is a Border Gateway Protocol area.

5. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the first region is a geographic area.

6. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the first region and the second region are in different administrative domains.

7. The non-transitory computer-readable media of claim 1, further including instructions that, when executed by the one or more processors, cause the border node to operate such that the outside-scope identifier that identifies the first region is the next indicator for the border node when the packet is sent from the network node to the border 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 border node to operate such that at least one of:

said next indicator includes an active indicator;

said next indicator indicates which identifier to use;

said next indicator includes a pointer as to which identifier a particular node should use;

said next indicator initially identifies the next identifier for routing by the border node, and then is updated to identify the another identifier for routing by the another node;

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

or

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

9. 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 first region of a network, cause the current node to:

identify a packet; and

forward, via a path segment to a path node in the first region, the packet so as to include, in a header thereof, network path information with a plurality of identifiers including an outside-scope identifier that is indicated, in the header, to be a next identifier, for at least the path node, in the plurality of identifiers when the packet is forwarded and that identifies a second region that includes a plurality of second-region network nodes, the outside-scope identifier being an identifier that identifies the second region without identifying a single particular network node, a single particular interface, nor a single particular link, the path segment being selected based on the outside-scope identifier and from a plurality of path segments that communicatively couple the current node to any node at least partially included in the second region.

10. The non-transitory computer-readable media of claim 9, further including instructions that, when executed by the one or more processors, cause the current node to operate such that each of a plurality of path nodes in the first region has a routing table for routing packets, based on the outside-scope identifier, to at least one node at least partially included in the second region.

11. The non-transitory computer-readable media of claim 9, further including instructions that, when executed by the one or more processors, cause the current node to operate such that the any node at least partially included in the second region is a border node having a first network interface for receiving packets from the first region and a second network interface positioned in the second region.

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

13. 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 first domain of a network, cause the current node to:

identify a packet; and

send the packet, via a path node in the first domain, toward a second domain so as to include, in a header of the packet, network path information identifying a sequence of identifiers including a second domain-identifier that identifies the second domain including a plurality of second-domain network nodes, the second domain-identifier identifying, for at least the path node, the second domain without identifying a single particular network node, a single particular interface, nor a single particular link, the second domain-identifier further identifying a plurality of second domain-border nodes at least partially included in the second domain from which a particular second domain-border node is capable of being selected by the current node for sending content of the packet including the second domain-identifier to the selected particular second domain-border node via a path segment that includes the path node in the first domain.

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

the network path information is predetermined by multiple topology nodes.

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

the network path information is predetermined by another node other than the current node.

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

a network path 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 13, further including instructions that, when executed by the one or more processors, cause the current node to operate such that:

a path segment is selected for sending the packet, without control signaling after the packet is identified.

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

the packet is capable of being sent by the current node along different ones of a plurality of path segments.

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

the packet is capable of being sent by the current node along different ones of a plurality of path segments based on a state of a network at a time when the packet is identified.

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

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

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

identify a particular packet; and

send the particular packet along with a header including therein network path information including a sequence of identifiers including a second domain-identifier that identifies a second MPLS domain including a plurality of second-domain network nodes without identifying a single particular network node, a single particular interface, nor a single particular link, the second domain-identifier causing an MPLS node, in the second MPLS domain and in response to receiving the sent particular packet, to forward data received in the particular packet by the MPLS node in an Internet Protocol (IP) packet.

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

the network path information is predetermined by multiple topology nodes.

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

the network path information is predetermined by another node other than the network node.

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

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

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

a path segment is selected for sending the packet, without control signaling after the packet is identified.

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

the packet is capable of being sent by the network node along different ones of a plurality of path segments.

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

the packet is capable of being sent by the network node along different ones of a plurality of path segments based on a state of a network at a time when the packet is identified.

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

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

29. A method, comprising:

performing at least one act that is configured to cause a border node, that is configured to have at least one network interface positioned in a first region of a network that includes a plurality of first-region network nodes, to;

receive, from a network node located in a second region of the network, a packet along with a header having therein network path information that includes, in the header, an outside-scope identifier that identifies the first region without identifying a single particular network node, a single particular interface, nor a single particular link;

responsive to receiving the packet, identify, in the header, a next indicator that identifies a next identifier in the network path information for the border node;

modify, in the header, the next indicator to identify, for another node, another identifier in the network path information; and

forward the packet according to the next identifier to deliver data in the packet to the another node via the at least one network interface in the first region.

30. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the first region is an Interior Gateway Protocol (IGP) area.

31. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the first region is a Border Gateway Protocol Autonomous System.

32. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the first region is a Border Gateway Protocol area.

33. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the first region is a geographic area.

34. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the first region and the second region are in different administrative domains.

35. The method of claim 29, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that;

the outside-scope identifier that identifies the first region is the next indicator for the border node when the packet is sent from the network node to the border node.

36. The method of claim 35, and comprising:

performing at least one additional act that is configured to cause the border node to operate such that at least one of;

the next indicator includes an active indicator;

the next indicator indicates which identifier to use;

the next indicator includes a pointer as to which identifier a particular node should use;

the next indicator initially identifies the next identifier for routing by the border node, and then is updated to identify the another identifier for routing by the another node;

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

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

the at least one act includes a configuration;

the at least one act includes a configuration of instructions;

the at least one additional act is performed at the border node;

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

the at least one additional act includes a configuration;

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

the at least one act and the at least one additional act are the same;

the at least one act and the at least one additional act are different;

the at least one act causes the border node to perform the receipt, the identification, the modification, and the forwarding;

the at least one act causes the border node to perform at least one of the receipt, the identification, the modification, or the forwarding;

the at least one act causes at least one operation to be performed other than the receipt, the identification, the modification, and the forwarding;

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

the method further comprises configuring the border node;

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

or

the method further comprises providing the border node.

37. A method, comprising:

performing at least one act that is configured to cause a current node, that is configured to be positioned in a first region of a network, to;

identify a packet; and

forward, via a path segment to a path node in the first region, the packet so as to include, in a header thereof, network path information with a plurality of identifiers including an outside-scope identifier that is indicated, in the header, to be a next identifier, for at least the path node, in the plurality of identifiers when the packet is forwarded and that identifies a second region that includes a plurality of second-region network nodes, the outside-scope identifier being an identifier that identifies the second region without identifying a single particular network node, a single particular interface, nor a single particular link, the path segment being selected based on the outside-scope identifier and from a plurality of path segments that communicatively couple the current node to any node at least partially included in the second region.

38. The method of claim 37, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

each of a plurality of path nodes in the first region has a routing table for routing packets, based on the outside-scope identifier, to at least one node at least partially included in the second region.

39. The method of claim 37, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the any node at least partially included in the second region is a border node having a first network interface for receiving packets from the first region and a second network interface positioned in the second region.

40. The method of claim 39, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the first network interface is included in the first region.

41. A method, comprising:

performing at least one act that is configured to cause a current node, that is configured to be positioned in a first domain of a network, to;

identify a packet; and

send the packet, via a path node in the first domain, toward a second domain so as to include, in a header of the packet, network path information identifying a sequence of identifiers including a second domain-identifier that identifies the second domain including a plurality of second-domain network nodes, the second domain-identifier identifying, for at least the path node, the second domain without identifying a single particular network node, a single particular interface, nor a single particular link, the second domain-identifier further identifying a plurality of second domain-border nodes at least partially included in the second domain from which a particular second domain-border node is capable of being selected by the current node for sending content of the packet including the second domain-identifier to the selected particular second domain-border node via a path segment that includes the path node in the first domain.

42. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the network path information is predetermined by multiple topology nodes.

43. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the network path information is predetermined by another node other than the current node.

44. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

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

45. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

a path segment is selected for sending the packet, without control signaling after the packet is identified.

46. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the packet is capable of being sent by the current node along different ones of a plurality of path segments.

47. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

the packet is capable of being sent by the current node along different ones of a plurality of path segments based on a state of a network at a time when the packet is identified.

48. The method of claim 41, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that;

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

49. A method, comprising:

performing at least one act that is configured to cause a network node, that is configured to be positioned in a first Multiprotocol Label Switching (MPLS) domain of a network, to;

identify a particular packet; and

send the particular packet along with a header including therein network path information including a sequence of identifiers including a second domain-identifier that identifies a second MPLS domain including a plurality of second-domain network nodes without identifying a single particular network node, a single particular interface, nor a single particular link, the second domain-identifier causing an MPLS node, in the second MPLS domain and in response to receiving the sent particular packet, to forward data received in the particular packet by the MPLS node in an Internet Protocol (IP) packet.

50. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

the network path information is predetermined by multiple topology nodes.

51. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

the network path information is predetermined by another node other than the network node.

52. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

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

53. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

a path segment is selected for sending the packet, without control signaling after the packet is identified.

54. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

the packet is capable of being sent by the network node along different ones of a plurality of path segments.

55. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

the packet is capable of being sent by the network node along different ones of a plurality of path segments based on a state of a network at a time when the packet is identified.

56. The method of claim 49, and comprising:

performing at least one additional act that is configured to cause the network node to operate such that;

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