Seamless segment routing

• US 9,450,829 B2
• Filed: 03/14/2014
• Issued: 09/20/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Ward, David D., Bryant, Stewart F., Frost, Daniel C., Nainar, Nagendra Kumar, Pignataro, Carlos M.
• Primary Examiner(s): Renner, Brandon
• Application Number:
  US14/210,837
• Publication Number:
  US 20140269699A1
• Time in Patent Office: 921 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/507 Label distribution
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets

Abstract

In one embodiment, a packet and a segment ID stack is received at a node. The segment ID stack includes a plurality of segment IDs, one or which is a first area-segment ID that identifies a first area of a subdivided network. One of a plurality of forwarding tables at the node is selected based on the first area-segment ID. Thereafter, the packet is forwarded based on information contained in the selected forwarding table.

Claims

1. A method comprising:

receiving a packet and a segment identifier (ID) stack at a segment routing enabled node, wherein

the segment ID stack comprises a plurality of segment IDs comprising a first area-segment ID,

the first area-segment ID identifies a first area of a subdivided segment routing enabled network, and

the first area comprises a first two or more nodes within the subdivided segment routing enabled network;

selecting one of a plurality of segment routing forwarding tables based on the first area-segment ID; and

forwarding the packet based on forwarding information contained in the selected forwarding table.

2. The method of claim 1 wherein each of the plurality of segment routing enabled forwarding tables is associated with a respective one of a plurality of area-segment IDs, including the first area-segment ID.

3. The method of claim 1 wherein:

the segment routing enabled node comprises an area border node connected to the first area and a second area of the subdivided segment routing enabled network; and

the second area comprises a second two or more nodes within the subdivided segment routing enabled network.

4. The method of claim 1 wherein the segment routing enabled node comprises an edge node contained in the first area, and wherein the edge node is coupled to another node in an access network.

5. The method of claim 3 wherein the plurality of segment IDs comprises a second area-segment ID that identifies the second area of the subdivided segment routing enabled network.

6. The method of claim 4 wherein:

the plurality of segment IDs comprises a second area-segment ID that identifies a second area of the subdivided segment routing enabled network; and

the second area comprises a second two or more nodes within the subdivided segment routing enabled network.

7. The method of claim 1 further comprising:

popping the first area-segment ID from the stack to expose an underlying segment ID;

accessing the selected forwarding table to read the forwarding information mapped in the selected forwarding table to the underlying segment ID.

8. The method of claim 7 wherein forwarding the packet comprises forwarding the packet and the underlying segment ID to another segment routing enabled node.

9. A non-transitory computer readable medium comprising executable instructions, wherein a method is implemented in response to executing the instructions, the method comprising:

receiving a packet and a segment identifier (ID) stack at a segment routing enabled node, wherein

the segment ID stack comprises a plurality of segment IDs comprising a first area-segment ID,

the first area-segment ID identifies a first area of a subdivided segment routing enabled network, and

the first area comprises a first two or more nodes within the subdivided segment routing enabled network;

selecting one of a plurality of segment routing forwarding tables based on the first area-segment ID; and

forwarding the packet based on forwarding information contained in the selected forwarding table.

10. The non-transitory computer readable medium of claim 9 wherein each of the plurality of segment routing enabled forwarding tables is associated with a respective one of a plurality of area-segment IDs, including the first area-segment ID.

11. The non-transitory computer readable medium of claim 9 wherein:

the segment routing enabled node comprises an area border node connected to the first area and a second area of the subdivided segment routing enabled network; and

the second area comprises a second two or more nodes within the subdivided segment routing enabled network.

12. The non-transitory computer readable medium of claim 9 wherein:

the plurality of segment IDs comprises a second area-segment ID that identifies a second area of the subdivided segment routing enabled network; and

the second area comprises a second two or more nodes within the subdivided segment routing enabled network.

13. The non-transitory computer readable medium of claim 9 wherein the method further comprises:

popping the first area-segment ID from the stack to expose an underlying segment ID;

accessing the selected forwarding table to read the forwarding information mapped in the selected forwarding table to the underlying segment ID.

14. The non-transitory computer readable medium of claim 13 wherein forwarding the packet comprises forwarding the packet and the underlying segment ID to another segment routing enabled node.

15. An apparatus comprising a segment routing enabled network node, the node comprising:

a memory for storing a plurality of segment routing forwarding tables; and

a processor adapted to

receive a packet and a segment identifier (ID) stack comprising a first area-segment ID,

select one of the plurality of segment routing forwarding tables based on the first area-segment ID, and

forward the packet based on forwarding information contained in the selected forwarding table, wherein

the first area-segment ID identifies a first area of a subdivided segment routing enabled network, and

the first area comprises a first two or more nodes within the subdivided segment routing enabled network.

16. The apparatus of claim 15, wherein each of the plurality of segment routing enabled forwarding tables is associated with a respective one of a plurality of area-segment IDs, including the first area-segment ID.

17. The apparatus of claim 15 wherein:

the segment routing enabled network node comprises an area border node connected to the first area and a second area of the subdivided segment routing enabled network; and

the second area comprises a second two or more nodes within the subdivided segment routing enabled network.

18. The apparatus of claim 17 wherein the segment ID stack further comprises a second area-segment ID that identifies the second area of the subdivided segment routing enabled network.

19. The apparatus of claim 15, wherein the processor is further adapted to:

remove the first area-segment ID from the stack to expose an underlying segment ID; and

access the selected forwarding table to read the forwarding information mapped in the selected forwarding table to the underlying segment ID.