Opportunistic compression of routing segment identifier stacks

Patent metadata

Field	Value
Publication number	US-9537769-B2
Application number	US-201414449632-A
Country	US
Kind code	B2
Filing date	Aug 1, 2014
Priority date	Mar 15, 2013
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

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.

First claim

What is claimed is:

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.

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.

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.

Assignees

• Cisco Tech Inc

Inventors

• Bryant Stewart F
• Frost Daniel C

Classifications

• H04L45/745 Primary

  Address table lookup; Address filtering · CPC title

• H04L45/46

  Cluster building · CPC title

• H04L45/50 Primary

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L45/54

  Organization of routing tables · CPC title

• H04L45/507

  Label distribution · CPC title