Routing methods, systems, and computer program products

• US 10,841,198 B1
• Filed: 05/20/2019
• Issued: 11/17/2020
• 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): Louie, Oscar A
• Assistant Examiner(s): Gidado, Oluwatosin M
• Application Number:
  US16/417,631
• Time in Patent Office: 547 Days
• Field of Search: 709238
• 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, a current node, system, method, and non-transitory computer-readable media are provided to: allow receipt of a first packet with first data, and a first header including a first segment identifier that is associated with a first algorithm and that identifies at least one of a particular node, a particular network interface, or a particular region; process the first segment identifier to identify a first path based on the first algorithm; cause transmission, via the first path, of the first data toward the at least one of the particular node, the particular network interface, or the particular region; allow receipt of a second packet with second data, and a second header including a second segment identifier that is different from the first segment identifier, that is associated with a second algorithm, and that identifies the at least one of the particular node, the particular network interface, or the particular region; process the second segment identifier to identify a second path based on the second algorithm; and cause transmission, via the second path, of the second data toward the at least one of the particular node, the particular network interface, or the particular region.

Claims

1. A non-transitory computer-readable media storing instructions that, when executed by one or more processors of a current node, cause the current node to:

allow receipt of a first packet with first data, and a first header including a first path segment identifier that is associated with a first algorithm and that identifies at least one of a particular node, a particular network interface, or a particular region;

process the first path segment identifier to identify a first path in an Internet Protocol version 6 (IPv6) network, based on the first algorithm, the first path including a physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region;

cause transmission, via the first path, of the first data toward the at least one of the particular node, the particular network interface, or the particular region;

allow receipt of a second packet with second data, and a second header including a second path segment identifier that is different from the first path segment identifier, that is associated with a second algorithm, and that identifies the at least one of the particular node, the particular network interface, or the particular region, the first header and the second header being IPv6 headers;

process the second path segment identifier to identify a second path in the IPv6 network, based on the second algorithm, the second path including another physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region; and

cause transmission, via the second path, of the second data toward the at least one of the particular node, the particular network interface, or the particular region.

2. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes a scoped identifier.

3. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes an outside scoped identifier.

4. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes a scope-specific identifier.

5. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first packet and the second packet are received from different previous nodes.

6. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first packet and the second packet are received from the same previous node.

7. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier and the second path segment identifier both identify, for a same region, the at least one of the particular node, the particular network interface, or the particular region.

8. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular node.

9. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular network interface.

10. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular region.

11. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier is the only path segment identifier included in the first header.

12. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier is included in a list of path segment identifiers included in the first header, and is selected from the list of path segment identifiers.

13. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first algorithm includes a default algorithm.

14. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first algorithm includes a shortest path algorithm.

15. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first algorithm includes a shortest path algorithm, and the second algorithm is not the shortest path algorithm.

16. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first algorithm or the second algorithm involves at least one of a metric, a policy, or a rule.

17. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first data is caused to be transmitted, via the first path, to the at least one of the particular node, the particular network interface, or the particular region.

18. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first data is caused to be transmitted, via the second path, to the at least one of the particular node, the particular network interface, or the particular region.

19. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier and the second path segment identifier are each encoded in at least one of the IPv6 headers.

20. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier is included in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is included in a destination address field of the second header that includes another one of the IPv6 headers.

21. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier is encoded in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is encoded in a destination address field of the second header that includes another one of the IPv6 headers.

22. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier identifies only the particular region.

23. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of:

the first path segment identifier identifies the first path by identifying only the particular region, or the second path segment identifier identifies the second path by identifying only the particular region.

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

the first path segment identifier identifies the first path by identifying only the particular region, and the second path segment identifier identifies the second path by identifying only the particular region.

25. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes an outside scoped identifier with no network interface identifying portion.

26. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that both the first path segment identifier and the second path segment identifier includes an outside scoped identifier that has no network interface identifying portion and that identifies only the particular region.

27. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that both the first path segment identifier and the second path segment identifier includes a same identifier that identifies only the particular region.

28. The non-transitory computer-readable media of claim 1, comprising instructions that, when executed by the one or more processors of the current node, cause the current node to operate such that the first path segment identifier is encoded as a single identifier in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is encoded as the same single identifier in a destination address field of the second header that includes another one of the IPv6 headers.

29. A system, comprising:

receiver means for allowing receipt of a first packet with first data, and a first header including a first path segment identifier that is associated with a first algorithm and that identifies at least one of a particular node, a particular network interface, or a particular region;

processor means for processing the first path segment identifier to identify a first path in an Internet Protocol version 6 (IPv6) network, based on the first algorithm, the first path including a physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region; and

transmitter means for causing transmission, via the first path, of the first data toward the at least one of the particular node, the particular network interface, or the particular region;

said receiver means for allowing receipt of a second packet with second data, and a second header including a second path segment identifier that is different from the first path segment identifier, that is associated with a second algorithm, and that identifies the at least one of the particular node, the particular network interface, or the particular region, the first header and the second header being IPv6 headers;

said processor means for processing the second path segment identifier to identify a second path in the IPv6 network, based on the second algorithm, the second path including another physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region; and

said transmitter means for causing transmission, via the second path, of the second data toward the at least one of the particular node, the particular network interface, or the particular region.

30. A method, comprising:

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

allow receipt of a first packet with first data, and a first header including a first path segment identifier that is associated with a first algorithm and that identifies at least one of a particular node, a particular network interface, or a particular region,

process the first path segment identifier to identify a first path in an Internet Protocol version 6 (IPv6) network, based on the first algorithm, the first path including a physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region,

cause transmission, via the first path, of the first data toward the at least one of the particular node, the particular network interface, or the particular region,

allow receipt of a second packet with second data, and a second header including a second path segment identifier that is different from the first path segment identifier, that is associated with a second algorithm, and that identifies the at least one of the particular node, the particular network interface, or the particular region, the first header and the second header being IPv6 headers,

process the second path segment identifier to identify a second path in the IPv6 network, based on the second algorithm, the second path including another physical communication path that is physically coupled to the at least one of the particular node, the particular network interface, or the particular region, and

cause transmission, via the second path, of the second data toward the at least one of the particular node, the particular network interface, or the particular region; and

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

31. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes a scoped identifier.

32. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes an outside scoped identifier.

33. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes a scope-specific identifier.

34. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first packet and the second packet are received from different previous nodes.

35. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first packet and the second packet are received from the same previous node.

36. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier and the second path segment identifier both identify, for a same region, the at least one of the particular node, the particular network interface, or the particular region.

37. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular node.

38. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular network interface.

39. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the at least one of the particular node, the particular network interface, or the particular region includes the particular region.

40. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier is the only path segment identifier included in the first header.

41. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier is included in a list of path segment identifiers included in the first header, and is selected from the list of path segment identifiers.

42. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first algorithm includes a default algorithm.

43. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first algorithm includes a shortest path algorithm.

44. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first algorithm includes a shortest path algorithm, and the second algorithm is not the shortest path algorithm.

45. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first algorithm or the second algorithm involves at least one of a metric, a policy, or a rule.

46. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first data is caused to be transmitted, via the first path, to the at least one of the particular node, the particular network interface, or the particular region.

47. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first data is caused to be transmitted, via the second path, to the at least one of the particular node, the particular network interface, or the particular region.

48. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier and the second path segment identifier are each encoded in at least one of the IPv6 headers.

49. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier is included in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is included in a destination address field of the second header that includes another one of the IPv6 headers.

50. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier is encoded in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is encoded in a destination address field of the second header that includes another one of the IPv6 headers.

51. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier identifies only the particular region.

52. The method of claim 30, and comprising:

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

the first path segment identifier identifies the first path by identifying only the particular region, or the second path segment identifier identifies the second path by identifying only the particular region.

53. The method of claim 30, and comprising:

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

the first path segment identifier identifies the first path by identifying only the particular region, and the second path segment identifier identifies the second path by identifying only the particular region.

54. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that at least one of the first path segment identifier or the second path segment identifier includes an outside scoped identifier with no network interface identifying portion.

55. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that both the first path segment identifier and the second path segment identifier includes an outside scoped identifier that has no network interface identifying portion and that identifies only the particular region.

56. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that both the first path segment identifier and the second path segment identifier includes a same identifier that identifies only the particular region.

57. The method of claim 30, and comprising:

performing at least one additional act that is configured to cause the current node to operate such that the first path segment identifier is encoded as a single identifier in a destination address field of the first header that includes one of the IPv6 headers, and the second path segment identifier is encoded as the same single identifier in a destination address field of the second header that includes another one of the IPv6 headers.