Routing methods, systems, and computer program products

• US 10,574,562 B1
• Filed: 06/26/2019
• Issued: 02/25/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): Kamara, Mohamed A
• Application Number:
  US16/454,030
• Time in Patent Office: 244 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 one embodiment, a system and apparatus are provided comprising: a first node configured to receive an index value, wherein the index value is globally unique within a network domain, receive a base value, wherein the base value comprises one of a plurality of segment routing values, and the plurality of segment routing values comprises a set of segment routing values configured to identify nodal segments, calculate a segment identifier (segment ID) based on the index value and the base value, and calculate a next hop segment ID based on the index value and a second base value.

Claims

1. A system comprising:

a first node comprising a memory and one or more processors, the first node configured to

receive an index value, wherein

the index value is globally unique within a network domain,

receive a base value, wherein

the base value comprises one of a plurality of segment routing values, and

the plurality of segment routing values comprises a set of segment routing values configured to identify nodal segments,

calculate a segment identifier (segment ID) based on the index value and the base value,

calculate, based on the index value and a second base value, a next hop segment ID associated with a packet, wherein the second base value comprises one of a second plurality of segment routing values reserved by a next-hop node, and

forwarding the packet based on the next hop segment ID.

2. The system of claim 1, wherein the segment ID comprises a locally-significant segment ID of the nodal segment, and the nodal segment is rooted at the first node.

3. The system of claim 1, wherein the first node is further configured to:

receive the packet comprising the segment ID; and

determine the next-hop node for the packet.

4. The system of claim 3, wherein calculating the next hop segment ID comprises calculating the index value based on the segment ID and a base value associated with a downstream node.

5. The system of claim 3, wherein the first node is further configured to:

remove the segment ID from the packet; and

insert the next hop segment ID into the packet.

6. The system of claim 1, wherein the first node is further configured to:

advertise the index value.

7. The system of claim 1, wherein the plurality of segment routing values comprises a plurality of disjoint subsets of segment routing values.

8. The system of claim 1, wherein the first node is further configured to:

store the index value in a data structure;

store the base value in the data structure; and

store the segment ID in the data structure.

19. The system of claim 3, wherein at least one of:

the index value includes a coordinate;

the base value includes an origin;

the segment routing values include at least one of;

path segments or segment identifiers;

the segment routing values include path segments and segment identifiers;

the nodal segments includes path segments or at least a portion of a path;

the nodal segments each includes a segment involving at least one node associated with the segment;

the segment ID includes an identifier configured being used to identify a segment;

the segment ID includes an identifier configured being used to identify a segment by including an identifier for the segment;

the segment ID includes an identifier configured being used to identify a segment by being used to look up an identifier for the segment;

the index value is globally unique within the network domain, by being assigned to one and only one node within the network domain;

the index value is globally unique within the network domain, by being assigned to one and only one node;

the terms;

first node, index value, base value, segment routing values, nodal segments, segment identifier, next hop segment identifier, and next-hop node all do not invoke U.S.C. 112, sixth paragraph;

the next hop node includes a node that is included with a next hop;

the next hop node includes a node that is included in a hop that is next;

the next hop segment ID includes a segment ID;

the next hop segment ID includes a segment ID that identifies a path segment that involves at least one hop that is next;

the next hop segment ID includes a segment ID that identifies a path segment that involves at least one next hop;

or

the next hop segment ID includes a segment ID that identifies a path segment that includes one or more hops.

20. The system of claim 1, wherein the system is configured 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.

21. The system of claim 1, wherein the system is configured such that data is capable of being transmitted by the first node along different ones of a plurality of path segments based on a policy and a current state of the network domain, where a first path segment of the plurality of path segments, via which the data is transmitted from the first node, is not selected when the packet is received and is therefore selected, in response to the receipt of the packet, based on the policy and the current state of the network domain, and without control signaling communications with another one or more nodes after the receipt of the packet.

22. The system of claim 1, wherein the system is configured such that a current state of the network domain is not maintained by the first node.

23. The system of claim 1, wherein the system is configured such that contents of a header of the packet includes everything necessary for routing data.

24. The system of claim 1, wherein the system is configured such that a number of protocols used to transmit data is reduced.

25. The system of claim 1, wherein the system is configured such that the segment ID is calculated regardless as to whether the segment ID and the next hop segment ID are identical or not.

26. The system of claim 1, wherein the system is configured such that the next hop segment ID is calculated regardless as to whether the segment ID and the next hop segment ID are identical or not.

27. The system of claim 1, wherein the system is configured such that the calculation of the next hop segment ID results in a modification of the next hop segment ID without changing a network path.

28. The system of claim 1, wherein the system is configured such that the calculation of the segment ID results in a modification of the segment ID without changing a network path.

29. The system of claim 1, wherein the system is configured such that a first virtual identifier space for a first plurality of nodes in the network domain is realized by configuring each node in the first plurality to have a respective identifier space that includes a particular identifier that identifies, for the each node in the first plurality, the first node, where the particular identifier in the respective identifier space for the each node in the first plurality matches the particular identifier in the respective identifier space for every other node in the first plurality.

30. The system of claim 29, wherein the system is configured such that the first node is included in the first plurality;

and the first virtual identifier space includes the particular identifier that takes the form of a scoped identifier with a scope that spans within the first plurality, and that identifies the first node within a span of the first virtual identifier space.

31. The system of claim 1, wherein the system is configured such that the index value and the base value are predetermined by a topology service.

32. The system of claim 1, wherein the system is configured such that the index value and the base value are predetermined by a transmitting node from which the index value and the base value are received.

33. The system of claim 1, wherein the system is configured such that a first path segment, via which data is transmitted from the first node, is not known when the index value and the base value are received and therefore determined in response to the receipt thereof.

34. The system of claim 1, wherein the system is configured such that a first path segment, via which data is transmitted from the first node, is not known when the index value, the base value, and the second base value are received and therefore determined in response to the receipt thereof.

35. The system of claim 1, wherein the system is configured such that a network path segment, via which data is transmitted from the first node, is selected without network-based control signaling after the receipt of the index value and the base value.

61. The system of claim 1, wherein the first node is further configured to:

advertise the index value; and

advertise a range of segment routing values, wherein

the plurality of segment routing values comprises the range of segment routing values.

62. The system of claim 1, wherein the first node is further configured to utilize the next hop segment ID as a replacement for the segment ID in the packet.

9. A method comprising:

receiving an index value at a node, wherein

the index value is globally unique within a network domain, and

receiving a base value at the node, wherein

the base value comprises one of a plurality of segment routing values, and

the plurality of segment routing values comprises a set of segment routing values configured to identify nodal segments;

calculating a segment identifier (segment ID) based on the index value and the base value;

calculating, based on the index value and a second base value, a next hop segment ID associated with a packet, wherein the second base value comprises one of a second plurality of segment routing values reserved by a next-hop node; and

forwarding the packet based on the next hop segment ID.

10. The method of claim 9, wherein the segment ID comprises a locally-significant segment ID of the nodal segment, and the nodal segment is rooted at the node.

11. The method of claim 9, further comprising:

receiving a packet comprising the segment ID; and

determining the next-hop node for the packet.

12. The method of claim 11, wherein calculating the next hop segment ID comprises calculating the index value based on the segment ID and a base value associated with a downstream node.

13. The method of claim 11, further comprising:

removing the segment ID from the packet; and

inserting the next hop segment ID into the packet.

14. The method of claim 9, further comprising:

advertising the index value.

15. The method of claim 9, further comprising:

assigning the index value.

16. The method of claim 9, wherein the plurality of segment routing values comprises a plurality of disjoint subsets of segment routing values.

17. The method of claim 9, further comprising:

storing the index value in a data structure;

storing the base value in the data structure; and

storing the segment ID in the data structure.

43. The method of claim 13, wherein 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.

44. The method of claim 13, wherein data is capable of being transmitted by the node along different ones of a plurality of path segments based on a policy and a current state of the network domain, where a first path segment of the plurality of path segments, via which the data is transmitted from the node, is not selected when the packet is received and is therefore selected, in response to the receipt of the packet, based on the policy and the current state of the network domain, and without control signaling communications with another one or nodes after the receipt of the packet.

45. The method of claim 13, wherein a current state of the network domain is not maintained by the node.

46. The method of claim 13, wherein contents of a header of the packet includes everything necessary for routing data.

47. The method of claim 13, wherein a number of protocols used to transmit data is reduced.

48. The method of claim 13, wherein the segment ID is removed and the next hop segment ID is inserted regardless as to whether the segment ID and the next hop segment ID are identical or not.

49. The method of claim 13, wherein the next hop segment ID is used instead of the segment ID in the packet regardless as to whether the segment ID and the next hop segment ID are identical or not.

50. The method of claim 13, wherein the calculation of the next hop segment ID results in a modification of the next hop segment ID without changing a network path.

51. The method of claim 13, wherein the calculation of the segment ID results in a modification of the segment ID without changing a network path.

52. The method of claim 13, wherein a first virtual identifier space for a first plurality of nodes in the network domain is realized by configuring each node in the first plurality to have a respective identifier space that includes a particular identifier that identifies, for the each node in the first plurality, the node, where the particular identifier in the respective identifier space for the each node in the first plurality matches the particular identifier in the respective identifier space for every other node in the first plurality.

53. The method of claim 52, wherein the node is included in the first plurality;

and

the first virtual identifier space includes the particular identifier that takes the form of a scoped identifier with a scope that spans within the first plurality, and that identifies the node within a span of the first virtual identifier space.

54. The method of claim 13, wherein the index value and the base value are predetermined by a topology service.

55. The method of claim 13, wherein the index value and the base value are predetermined by a transmitting node from which the index value and the base value are received.

56. The method of claim 13, wherein a first path segment, via which data is transmitted from the node, is not known when the index value, the base value, and the second base value are received and therefore determined in response to the receipt thereof.

57. The method of claim 13, wherein a first path segment, via which data is transmitted from the node, is not known when the index value and the base value are received and therefore determined in response to the receipt thereof.

58. The method of claim 13, wherein a network path segment, via which data is transmitted from the node, is selected without network-based control signaling after the receipt of the index value and the base value.

59. The method of claim 9, further comprising:

advertising the index value; and

advertising a range of segment routing values, wherein

the plurality of segment routing values comprises the range of segment routing values.

60. The method of claim 9, further comprising:

assigning the index value, wherein

assigning the index value comprises verifying that a total number of assigned index values does not exceed a limit, and

the limit corresponds to a size of a smallest range of segment IDs advertised by any node in the network domain.

18. An apparatus, comprising:

at least one non-transitory memory configured to store instructions; and

one or more processors in communication with the at least one non-transitory memory, wherein the one or more processors is configured to execute the instructions to;

receive an index value, wherein

the index value is globally unique within a network domain,

receive a base value, wherein

the base value comprises one of a plurality of segment routing values, and

the plurality of segment routing values comprises a set of segment routing values configured to identify nodal segments, and

calculate a segment identifier (segment ID) based on the index value and the base value,

calculate, based on the index value and a second base value, a next hop segment ID associated with a packet, wherein the second base value comprises one of a second plurality of segment routing values reserved by a next-hop node, and

forward the packet based on the next hop segment ID.

36. The apparatus of claim 18, wherein the apparatus is configured such that the segment ID comprises a locally-significant segment ID of the nodal segment, and the nodal segment is rooted at the apparatus.

37. The apparatus of claim 18, wherein the apparatus is configured to:

receive the packet comprising the segment ID; and

determine the next-hop node for the packet.

38. The apparatus of claim 37, wherein the apparatus is configured such that calculating the next hop segment ID comprises calculating the index value based on the segment ID and a base value associated with a downstream node.

39. The apparatus of claim 37, wherein the apparatus is configured to utilize the next hop segment ID as a replacement for the segment ID in the packet.

40. The apparatus of claim 18, wherein the apparatus is configured to:

advertise the index value and the base value.

41. The apparatus of claim 18, wherein the apparatus is configured such that the plurality of segment routing values comprises a plurality of disjoint subsets of segment routing values.

42. The apparatus of claim 18, wherein the apparatus is configured to:

store the index value in a data structure;

store the base value in the data structure; and

store the segment ID in the data structure.

63. An apparatus comprising:

a first node comprising;

a first means for receiving an index value, wherein the index value is globally unique within a network domain,

a second means for receiving a base value, wherein

the base value comprises one of a plurality of segment routing values, and

the plurality of segment routing values comprises a set of segment routing values configured to identify nodal segments,

a third means for calculating a segment identifier (segment ID) based on the index value and the base value, and

a fourth means for

determining a next hop node for a packet,

calculating a next hop segment ID associated with the packet based on the index value and a second base value, and

forwarding the packet based on the next hop segment ID.