Seamless segment routing

• US 9,722,878 B2
• Filed: 08/11/2016
• Issued: 08/01/2017
• 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: Frost, Daniel C., Filsfils, Clarence, Ward, David D., Bryant, Stewart F., Nainar, Nagendra Kumar, Pignataro, Carlos M.
• Primary Examiner(s): RENNER, BRANDON M
• Application Number:
  US15/234,794
• Publication Number:
  US 20160352654A1
• Time in Patent Office: 355 Days
• Field of Search: None
• 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

A method, apparatus, and computer readable medium are disclosed. In one embodiment of the method, a packet and a segment ID stack is received at a first segment routing enabled 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 segment routing network. An egress interface of the first segment routing enabled node is selected based on the first area-segment ID. Thereafter, the packet is forwarded via the selected egress interface.

Claims

1. A method comprising:

receiving a packet and a segment identifier (ID) stack at a first 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, but does not comprise the first segment routing enabled node;

selecting an egress interface of the first segment routing enabled node based on the first area-segment ID; and

forwarding the packet via the selected egress interface.

2. The method of claim 1, wherein:

a second area of the subdivided segment routing enabled network comprises the first segment routing enabled node and one or more additional nodes; and

forwarding the packet via the selected egress interface comprises forwarding the packet toward an area border node connected to the second area and to an additional area of the subdivided segment routing enabled network.

3. The method of claim 2, wherein the additional area of the subdivided segment routing enabled network comprises a backbone area.

4. The method of claim 2, wherein the additional area of the subdivided segment routing enabled network comprises the first area.

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

6. The method of claim 1, wherein forwarding the packet comprises accessing a forwarding table mapping the first area-segment ID to the selected egress interface.

7. The method of claim 4, wherein the area border node is adapted to:

receive the packet; and

select one of a plurality of segment routing forwarding tables based on the first area-segment ID.

8. 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 first 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, but does not comprise the first segment routing enabled node;

selecting an egress interface of the first segment routing enabled node based on the first area-segment ID; and

forwarding the packet via the selected egress interface.

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

a second area of the subdivided segment routing enabled network comprises the first segment routing enabled node and one or more additional nodes; and

forwarding the packet via the selected egress interface comprises forwarding the packet toward an area border node connected to the second area and to an additional area of the subdivided segment routing enabled network.

10. The non-transitory computer readable medium of claim 9, wherein the additional area of the subdivided segment routing enabled network comprises a backbone area.

11. The non-transitory computer readable medium of claim 9, wherein the additional area of the subdivided segment routing enabled network comprises the first area.

12. The non-transitory computer readable medium of claim 9, wherein the first segment routing enabled node comprises an edge node contained in the second area, and wherein the edge node is coupled to another node in an access network.

13. The non-transitory computer readable medium of claim 8, wherein forwarding the packet comprises accessing a forwarding table mapping the first area-segment ID to the selected egress interface.

14. An apparatus comprising a first segment routing enabled node, the first segment routing enabled node comprising:

a processor adapted to

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

select an egress interface of the first segment routing enabled node based on the first area-segment ID; and

forward the packet via the selected egress interface, 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, but does not comprise the first segment routing enabled node.

15. The apparatus of claim 14, wherein:

a second area of the subdivided segment routing enabled network comprises the first segment routing enabled node and one or more additional nodes; and

the processor is further adapted to forward the packet toward an area border node connected to the second area and to an additional area of the subdivided segment routing enabled network.

16. The apparatus of claim 15, wherein the additional area of the subdivided segment routing enabled network comprises a backbone area.

17. The apparatus of claim 15, wherein the additional area of the subdivided segment routing enabled network comprises the first area.

18. The apparatus of claim 15, wherein the first segment routing enabled node comprises an edge node contained in the second area, and wherein the edge node is coupled to another node in an access network.

19. The apparatus of claim 14, wherein:

the first segment routing enabled node further comprises a memory adapted for storing one or more segment routing forwarding tables; and

the processor is further adapted to access a forwarding table mapping the first area-segment ID to the selected egress interface, in the process of forwarding the packet via the selected egress interface.

20. The apparatus of claim 17, wherein the area border node is adapted to:

receive the packet; and

select one of a plurality of segment routing forwarding tables based on the first area-segment ID.