Indexed segment ID

• US 9,559,954 B2
• Filed: 01/15/2014
• Issued: 01/31/2017
• Est. Priority Date: 03/11/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Previdi, Stefano B., Bashandy, Ahmed R.
• Primary Examiner(s): Haile, Awet
• Application Number:
  US14/155,601
• Publication Number:
  US 20140254596A1
• Time in Patent Office: 1,112 Days
• US Class Current: 1/1
• 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/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

An apparatus and method for using indexed segment identifiers in segment routing. An example method involves receiving a globally unique index value at a node. The method also involves receiving a base value at the node, where the base value comprises a segment routing value configured to identify a nodal segment. The method then involves calculating a segment identifier based on the index value and the base value.

Claims

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

2. The method 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 node.

3. The method of claim 1, further comprising:

receiving the packet comprising the segment ID; and

determining the next-hop node for the packet.

4. The method of claim 1, 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 method of claim 3, further comprising:

removing the segment ID from the packet; and

inserting the next hop segment ID into the packet.

6. The method of claim 1, 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.

7. The method of claim 1, 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.

8. The method of claim 7, further comprising:

receiving, by an administrative entity, a configuration request from the node;

determining an available range of segment routing values on the node; and

allocating the plurality of segment routing values based on the available range of segment routing values.

9. The method of claim 1, wherein

the plurality of segment routing values comprises a plurality of disjoint subsets of segment routing values.

10. The method of claim 1, 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.

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

12. The system of claim 11, wherein

the segment ID comprises a locally-significant segment ID of the nodal segment, and

the nodal segment is rooted at the first node.

13. The system of claim 11, wherein the first node is further configured to:

receive the packet comprising the segment ID; and

determine the next-hop node for the packet.

14. The system 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.

15. The system of claim 13, 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.

16. The system of claim 11, 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.

17. The system of claim 11, further comprising:

an administrative entity configured to

receive a configuration request from the first node,

determine an available range of segment routing values on the first node, and

allocate the plurality of segment routing values based on the available range of segment routing values.

18. The system of claim 11, wherein

the plurality of segment routing values comprises a plurality of disjoint subsets of segment routing values.

19. The system of claim 11, 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.

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