Routing methods, systems, and computer program products using a region scoped outside-scope identifier

• US 10,397,100 B1
• Filed: 10/05/2018
• Issued: 08/27/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/153,196
• Time in Patent Office: 326 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• 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/22 Alternate 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
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In various embodiments, an apparatus, a non-transitory computer-readable media, and a method are provided, involving a capability to: receive an indication of a receipt of a first packet that is specified according to an Internet Protocol (IP) network protocol; identify, from a header of the first packet, network path information that is based on a first policy and includes: a region scoped outside-scope identifier that: is in an identifier space having a scope that spans a first region of the network, does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and identifies, in the first region, a second region of the network, where the network path, along which first data is transmitted, includes: a first path segment that communicatively couples the current node and the second region, and a second path segment in the second region; and cause transmission, based on the region scoped outside-scope identifier, of the first data from the current node to a border node of the second region via the first path segment.

Claims

1. A non-transitory computer-readable media storing instructions that, when executed by one or more processors of a current node positioned in a first region of a network along a network path including a transmitting node and a receiving node, cause the one or more processors to:

receive an indication of a receipt of a first packet that is specified according to an Internet Protocol (IP) network protocol;

identify, from a header of the first packet, network path information that is based on a first policy and includes;

a region scoped outside-scope identifier that;

is in an identifier space having a scope that spans a first region of the network,

does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and

identifies, in the first region, a second region of the network, where the network path, along which first data is transmitted, includes;

a first path segment that communicatively couples the current node and the second region, and

cause transmission, based on the region scoped outside-scope identifier, of the first data from the current node to a border node of the second region via the first path segment that is selected, based on at least one of the first policy, a table, or a metric, from a plurality of path segments, including at least one multi-hop path segment, that are capable of communicatively coupling the current node and the second region, the border node having a first network interface in the first region and having a second network interface in the second 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 current node to operate such that:

the first network path is customized by a topology node.

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

the first network path is customized by the topology node so as to be different from that identified by a routing data structure of the current node.

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

at least one aspect of the first policy is included in the header of the first packet.

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

the at least one aspect of the first policy is not maintained at every node along the network path.

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

the IP network protocol includes an IP version six (IPv6) network protocol.

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

at least a portion of the network path other than the first path segment is predetermined by the network path information.

8. The non-transitory computer-readable media of claim 1, 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 the transmitting node.

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

the network path information is predetermined by a topology node for use by the current node to select the first path segment from the plurality of path segments.

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

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

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

the first policy is specified by the plurality of path segments.

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

the first policy is generated by multiple topology nodes.

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

the first path segment is selected in response to the receipt of the first packet.

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

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

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

a number or protocols used to transmit the data is reduced.

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

the first data is capable of being transmitted by the current node along different ones of the plurality of path segments.

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

the first data is capable of being transmitted by the current node along different ones of the plurality of path segments based on the first policy and a current state of the network.

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

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

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

the transmitting node is not in the first region.

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

the transmitting node is in a third region of the network, and the transmitting node is identified, within the third region, by an other scoped identifier in an other identifier space that spans the third region of the network.

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

the other scoped identifier includes an other scoped outside-scope identifier.

22. The non-transitory computer-readable media of claim 1, 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 determined by a border node of the first region, based on the first policy, and the network path information is received by the current node from the border node via the network path.

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

the transmitting node is in the first region of the network.

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

the transmitting node includes a border node of the first region of the network.

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

the receiving node is not in the first region.

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

a destination node is in a third region of the network, and the destination node is identified, within the third region, by an other scoped identifier in an other identifier space that spans the third region of the network.

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

the receiving node is identified in the first region by a scope-specific identifier in another identifier space specific to;

a particular region of the network, or one node in the particular region of the network; and

wherein at least one of;

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

said first path segment includes the at least one multi-hop path segment;

said first path segment does not include the at least one multi-hop path segment;

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

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

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

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

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

said first packet is received from the transmitting node;

said first packet is received from a particular node between the transmitting node and the current node;

said first region is based on a first domain;

said first region includes a first domain;

said first region includes a first area;

said second region is based on a second domain;

said second region includes a second particular domain;

said second region includes a second particular area;

said receiving node includes a destination node;

said receiving node does not include a destination node;

said transmitting node includes a source node;

said transmitting node does not include a source node;

said identification, from the header of the first packet, of the network path information is performed, by a detection thereof;

said receipt of the indication of the receipt of a first packet, includes receiving, at the one or more processors, a signal from an incoming network interface component upon receipt of the first packet by the incoming network interface component;

said one or more processors includes multiple processors that, when different subsets of the instructions are each executed by a corresponding one of the different multiple processors, each perform different ones of;

the receiving, the identification, and the causation;

said one or more processors includes a single processor that, when the instructions are executed, performs each of;

the receiving, the identification, and the causation;

said first data is transmitted from the current node in another packet that is a copy of the first packet;

said first data is transmitted from the current node in another packet that is at least partially similar to the first packet;

said region scoped outside-scope identifier identifies, only in the first region of the network, the second region;

said region scoped outside-scope identifier globally identifies, in the first region of the network, the second region;

said non-transitory computer-readable media is included as part of an apparatus that further comprises the current node;

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

or

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

28. An apparatus, comprising:

a particular node configured to be positioned in a network path along which first data is capable of being transmitted from a transmitting node to a receiving node which are both in the network path along which the first data is transmitted in a network, the particular 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 particular node to;

receive a first packet that is specified according to an Internet Protocol (IP) network protocol;

identify, in a header of the first packet, network path information that is based on a first policy and includes;

a region scoped outside-scope identifier that;

is in an identifier space having a scope that spans a first region of the network,

does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and

globally identifies, in the first region, a second region of the network, where the network path, along which the first data is transmitted, includes;

 

a first path segment that communicatively couples the particular node and the second region, and

 

a second path segment in the second region;

select the region scoped outside-scope identifier in the header of the first packet; and

transmit, based on the region scoped outside-scope identifier, the first data from the particular node to a border node of the second region via the first path segment that is selected, based on at least one of the first policy, a table, or a metric, from a plurality of path segments, including at least one multi-hop path segment, that are capable of communicatively coupling the particular node and the second region, the border node having a first network interface in the first region and having a second network interface in the second region.

29. A method, comprising:

at a particular node in a network path along which first data is transmitted in a network from a transmitting node to a receiving node which are both in the network path;

receiving a first packet that is specified according to an Internet Protocol (IP) network protocol, the first packet including a header with network path information that is based on a first policy and includes;

a region scoped outside-scope identifier that;

is in an identifier space having a scope that spans a first region of the network,

does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and

globally identifies, in the first region, a second region of the network, where the network path, along which the first data is transmitted, includes;

 

a first path segment that communicatively couples the particular node and the second region, and

 

a second path segment in the second region; and

transmitting, based on the region scoped outside-scope identifier in the header of the first packet, the first data from the particular node to a border node of the second region via the first path segment that is selected, based on at least one of the first policy, a table, or a metric, from a plurality of path segments, including at least one multi-hop path segment, that are capable of communicatively coupling the particular node and the second region, the border node having a first network interface in the first region and having a second network interface in the second region.

30. A particular node configured to be positioned in a network path along which first data is capable of being transmitted from a transmitting node to a receiving node which are both in the network path along which the first data is transmitted in a network, the particular node comprising:

means for receiving a first packet that is specified according to an Internet Protocol (IP) network protocol, the first packet including a header with network path information that is based on a first policy and includes;

a region scoped outside-scope identifier that;

is in an identifier space having a scope that spans a first region of the network,

does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and

identifies, in the first region, a second region of the network, where the network path, along which the first data is transmitted, includes;

a first path segment that communicatively couples the particular node and the second region, and

a second path segment in the second region; and

means for transmitting, based on the region scoped outside-scope identifier in the header of the first packet, the first data from the particular node to a border node of the second region via the first path segment that is selected, based on at least one of the first policy, a table, or a metric, from a plurality of path segments, including at least one multi-hop path segment, that are capable of communicatively coupling the particular node and the second region, the border node having a first network interface in the first region and having a second network interface in the second region.

31. 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 along a network path including a transmitting node and a receiving node, to;

receive an indication of a receipt of a first packet that is specified according to an Internet Protocol (IP) network protocol,

identify, from a header of the first packet, network path information that is based on a first policy and includes;

a region scoped outside-scope identifier that;

is in an identifier space having a scope that spans a first region of the network,

does not include a network interface identifier portion specified by the IP network protocol for identifying any network interface, and

identifies, in the first region, a second region of the network, where the network path, along which first data is transmitted, includes;

 

a first path segment that communicatively couples the current node and the second region, and

 

a second path segment in the second region, and

cause transmission, based on the region scoped outside-scope identifier, of the first data from the current node to a border node of the second region via the first path segment that is selected, based on at least one of the first policy, a table, or a metric, from a plurality of path segments, including at least one multi-hop path segment, that are capable of communicatively coupling the current node and the second region, the border node having a first network interface in the first region and having a second network interface in the second region; and

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

32. The method of claim 31, and comprising:

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

the first network path is customized by a topology node.

33. The method of claim 32, and comprising:

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

the first network path is customized by the topology node so as to be different from that identified by a routing data structure of the current node.

34. The method of claim 31, and comprising:

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

at least one aspect of the first policy is included in the header of the first packet.

35. The method of claim 34, and comprising:

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

the at least one aspect of the first policy is not maintained at every node along the network path.

36. The method of claim 31, and comprising:

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

the IP network protocol includes an IP version six (IPv6) network protocol.

37. The method of claim 31, and comprising:

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

at least a portion of the network path other than the first path segment is predetermined by the network path information.

38. The method of claim 31, 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 the transmitting node.

39. The method of claim 31, 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 a topology node for use by the current node to select the first path segment from the plurality of path segments.

40. The method of claim 31, and comprising:

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

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

41. The method of claim 31, and comprising:

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

the first policy is specified by the plurality of path segments.

42. The method of claim 31, and comprising:

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

the first policy is generated by multiple topology nodes.

43. The method of claim 31, and comprising:

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

the first path segment is selected in response to the receipt of the first packet.

44. The method of claim 31, and comprising:

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

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

45. The method of claim 31, and comprising:

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

a number or protocols used to transmit the data is reduced.

46. The method of claim 31, and comprising:

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

the first data is capable of being transmitted by the current node along different ones of the plurality of path segments.

47. The method of claim 31, and comprising:

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

the first data is capable of being transmitted by the current node along different ones of the plurality of path segments based on the first policy and a current state of the network.

48. The method of claim 31, and comprising:

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

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

49. The method of claim 31, and comprising:

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

the transmitting node is not in the first region.

50. The method of claim 49, and comprising:

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

the transmitting node is in a third region of the network, and the transmitting node is identified, within the third region, by an other scoped identifier in an other identifier space that spans the third region of the network.

51. The method of claim 50, and comprising:

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

the other scoped identifier includes an other scoped outside-scope identifier.

52. The method of claim 31, 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 determined by a border node of the first region, based on the first policy, and the network path information is received by the current node from the border node via the network path.

53. The method of claim 31, and comprising:

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

the transmitting node is in the first region of the network.

54. The method of claim 53, and comprising:

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

the transmitting node includes a border node of the first region of the network.

55. The method of claim 31, and comprising:

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

the receiving node is not in the first region.

56. The method of claim 55, and comprising:

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

a destination node is in a third region of the network, and the destination node is identified, within the third region, by an other scoped identifier in an other identifier space that spans the third region of the network.

57. The method of claim 56, and comprising:

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

the receiving node is identified in the first region by a scope-specific identifier in another identifier space specific to;

a particular region of the network, or one node in the particular region of the network; and

wherein at least one of;

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

said first path segment includes the at least one multi-hop path segment;

said first path segment does not include the at least one multi-hop path segment;

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

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

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

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

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

said first packet is received from the transmitting node;

said first packet is received from a particular node between the transmitting node and the current node;

said first region is based on a first domain;

said first region includes a first domain;

said first region includes a first area;

said second region is based on a second domain;

said second region includes a second particular domain;

said second region includes a second particular area;

said receiving node includes a destination node;

said receiving node does not include a destination node;

said transmitting node includes a source node;

said transmitting node does not include a source node;

said identification, from the header of the first packet, of the network path information is performed, by a detection thereof;

said receipt of the indication of the receipt of a first packet, includes receiving, at one or more processors, a signal from an incoming network interface component upon receipt of the first packet by the incoming network interface component;

said first data is transmitted from the current node in another packet that is a copy of the first packet;

said first data is transmitted from the current node in another packet that is at least partially similar to the first packet;

said region scoped outside-scope identifier identifies, only in the first region of the network, the second region;

said region scoped outside-scope identifier globally identifies, in the first region of the network, the second region;

said at least one act is performed at the current node;

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

said at least one act and the at least one additional act are performed at the current node;

said at least one act and the at least one additional act are performed at a certain node other than the current node;

said at least one act and the at least one additional act are performed at a certain node other than the current node;

said at least one act and the at least one additional act are performed at a certain node other than the current node;

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

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

said at least one act causes the current node to perform the receipt, each instance of the receipt, the identification, and the causation of the transmission;

said at least one act causes the current node to perform at least one of the receipt, the identification, or the causation of the transmission;

said at least one act causes at least one operation to be performed other than the receipt, the identification, and the causation of the transmission;

said causing storage includes causing storage of at least portion of 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;

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

said causing storage includes causing storage of at least portion of 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;

said causing storage includes installation;

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

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

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

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

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

said method further comprises configuring the current node;

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

said method further comprises providing the current node;

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

said method further comprises providing one or more processors;

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

or

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