Opportunistic compression of routing segment identifier stacks

• US 9,537,769 B2
• Filed: 08/01/2014
• Issued: 01/03/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: Bryant, Stewart F., Frost, Daniel C.
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US14/449,632
• Publication Number:
  US 20140369356A1
• Time in Patent Office: 886 Days
• Field of Search: 370389-392, 370477-521, 709232-238
• US Class Current: 1/1
• 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/38 Flow based routing
• 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

Abstract

A method and device are disclosed for opportunistic compression of routing segment identifiers. In one embodiment, the method includes participating in routing of a first data packet through a first node in a network, and subsequently entering into an arrangement with an adjacent node in the network. The first data packet includes a first plurality of routing segment identifiers, and additional data packets to be routed through the first node also include the first plurality of routing segment identifiers. The arrangement entered into includes representation of the first plurality of routing segment identifiers by a single compression identifier. The method further includes participating in routing of at least one of the additional data packets using the compression identifier instead of the first plurality of routing segment identifiers. In an embodiment, the device includes one or more network interfaces and a processor configured to perform the steps of the method.

Claims

1. A method, comprising:

participating in routing of a first data packet through a first node in a segment routing enabled network, wherein

the first data packet comprises a first plurality of routing segment identifiers,

each of multiple additional data packets to be routed through the first node also comprises the first plurality of routing segment identifiers, and

one or more of the first plurality of routing segment identifiers is stored in a segment routing forwarding table at the first node;

subsequent to said participating in routing of the first data packet, entering into an arrangement with an adjacent node in the segment routing enabled network, wherein

the arrangement comprises representation of the first plurality of routing segment identifiers by a single compression identifier; and

participating in routing of at least one of said additional data packets, wherein

the at least one of said additional data packets as routed comprises the single compression identifier instead of the first plurality of routing segment identifiers, and

the compression identifier is stored in the segment routing forwarding table at the first node.

2. The method of claim 1, wherein said participating in routing comprises receiving.

3. The method of claim 1, wherein said participating in routing comprises sending.

4. The method of claim 1, wherein said routing segment identifiers comprise Multiprotocol Label Switching (MPLS) labels.

5. The method of claim 1, wherein the first data packet and the additional data packets comprise internet protocol (IP) extension headers.

6. The method of claim 1, further comprising:

subsequent to said participating in routing of a first data packet, and prior to said entering into an arrangement, determining that use of the single compression identifier to replace the first plurality of routing segment identifiers within one or more of said additional data packets is associated with a potential network improvement.

7. The method of claim 6, wherein said determining comprises evaluating network flow analysis information.

8. The method of claim 7, wherein said network flow analysis information comprises

a prevalence, among data packets routed through the first node, of data packets comprising the first plurality of segment identifiers.

9. The method of claim 7, wherein said network flow analysis information comprises

a quality of service parameter for data packets comprising the first plurality of segment identifiers.

10. The method of claim 1, wherein said arrangement further comprises

an expiration time for said use of the single compression identifier to represent the first plurality of routing segment identifiers.

11. The method of claim 1, wherein said entering into an arrangement with an adjacent node comprises sending to the adjacent node a proposal for representation of the first plurality of routing segment identifiers by the single compression identifier.

12. The method of claim 2, wherein said entering into an arrangement with an adjacent node comprises sending to the adjacent node a proposal for representation of the first plurality of routing segment identifiers by the single compression identifier.

13. The method of claim 3, wherein said entering into an arrangement with an adjacent node comprises sending to the adjacent node a proposal for representation of the first plurality of routing segment identifiers by the single compression identifier.

14. The method of claim 1, wherein said entering into an arrangement with an adjacent node comprises receiving from the adjacent node a proposal for representation of the first plurality of routing segment identifiers by the single compression identifier.

22. The method of claim 5, wherein the at least one of the additional data packets as routed comprises the single compression identifier written into an IP address field of the at least one of the additional data packets.

15. A network device associated with a node in a segment routing enabled network, the network device comprising:

one or more network interfaces;

a memory storing a segment routing forwarding table; and

a processor configured to;

participate in routing of a first data packet through the node in the segment routing enabled network via at least one of the network interfaces, wherein the first data packet comprises a first plurality of routing segment identifiers, each of multiple additional data packets to be routed through the node also comprises the first plurality of routing segment identifiers, and one or more of the first plurality of routing segment identifiers is stored in the segment routing forwarding table;

subsequent to said participating in routing of the first data packet, enter into an arrangement with an adjacent node in the segment routing enabled network, wherein the arrangement comprises representation of the first plurality of routing segment identifiers by a single compression identifier;

create an entry in the segment routing forwarding table reflecting the arrangement; and

participate in routing of at least one of said additional data packets using the forwarding table, wherein the at least one of said additional data packets as routed comprises the single compression identifier instead of the first plurality of routing segment identifiers, and the compression identifier is stored in the segment routing forwarding table.

16. The network device of claim 15, wherein the processor is further configured to, subsequent to said participating in routing of a first data packet, and prior to said entering into an arrangement, determine that use of the single compression identifier to replace the first plurality of routing segment identifiers within one or more of said additional headers is associated with a potential network improvement.

17. The network device of claim 16, wherein the processor is further configured to evaluate network flow analysis information to determine that use of the single compression identifier to replace the first plurality of routing segment identifiers within one or more of said additional headers is associated with the potential network improvement.

18. The network device of claim 17, further comprising a network flow analysis engine configured to provide network flow analysis information for data packets routed through the network node.

19. The network device of claim 15, further comprising a forwarding engine configured to send a data packet from the network node to another network node via at least one of the network interfaces.

20. The network device of claim 15, wherein the entry in the segment routing forwarding table comprises:

the single compression identifier; and

the plurality of routing segment identifiers represented by the single compression identifier.

21. The network device of claim 20, wherein the entry in the forwarding table further comprises an expiration time for the arrangement.