Order-sensitive communications in packet reordering networks

• US 9,654,389 B2
• Filed: 12/19/2014
• Issued: 05/16/2017
• Est. Priority Date: 07/21/2014
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe, Hong, Wei
• Primary Examiner(s): Mui, Gary
• Application Number:
  US14/576,873
• Publication Number:
  US 20160021018A1
• Time in Patent Office: 879 Days
• Field of Search: None
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

In one embodiment, a device in a network determines that a particular packet flow in the network is sensitive to packet reordering. The device determines whether a particular packet of the packet flow is to be routed differently than an immediately prior packet in the packet flow, in response to determining that the particular packet flow is sensitive to reordering. The device marks the particular packet as taking a different route than the immediately prior packet in the packet flow, prior to forwarding the marked packet and in response to determining that the particular packet is to be routed differently than the immediately prior packet in the packet flow.

Claims

1. A method comprising:

determining, by a device in a network, that a particular packet flow in the network is sensitive to packet reordering;

wherein the device determines that the articular packet flow is sensitive to reordering based on a policy received from a supervisory device;

determining, by the device, whether a particular packet of the packet flow is to be routed differently than an immediately prior packet in the packet flow, in response to determining that the particular packet flow is sensitive to reordering; and

marking, by the device, the particular packet as taking a different route than the immediately prior packet in the packet flow, prior to forwarding, the marked packet and in response to determining that the particular packet is to be routed differently than the immediately prior packet in the packet flow.

2. The method as in claim 1, wherein at least one packet in the packet flow is marked as sensitive to reordering, and wherein the device determines that the particular packet flow is sensitive to reordering based on the at least one packet in the particular packet flow being marked as sensitive to reordering.

3. The method as in claim 2, wherein the at least one packet in the packet flow is marked as sensitive to reordering by one or more of:

a set bit in a packet header of the at least one packet, a packet classifier that routes the at least one packet, a set bit in a traffic class header of the at least one packet, a port number associated with the at least one packet, a network address associated with the at least one packet, a flow label associated with the at least one packet, or an IPv6 hop-by-hop option.

4. The method as in claim 2, wherein the at least one packet is sent via a protocol that does not include packet ordering information, and wherein the at least one packet is marked as sensitive to reordering by an indicated sequence number.

5. The method as in claim 1, wherein the device determines that the particular packet is to be routed differently than the immediately prior packet in the packet flow based on at least one of:

a failure to receive a link layer acknowledgement for the prior packet, a routing update, or a load balancing strategy used by the device.

6. The method as in claim 1, further comprising:

receiving, at the device, an indication from a router in the network that the router received packets of the particular packet flow out of order.

7. The method as in claim 6, wherein the indication is piggybacked in a data packet sent in a direction opposite that of the particular packet flow.

8. The method as in claim 6, further comprising:

adjusting, by the device, a routing strategy used by the device to route packet flows, in response to receiving a threshold number of indications from the router indicating that the router received packet flow packets out of order.

9. The method as in claim 8, wherein the device adjusts the routing strategy by stopping a load balancing mechanism used to balance path loads or by reducing a cost difference between two or more routing paths.

10. The method as in claim 1, wherein the device is an ingress router to the network.

11. The method as in claim 10, wherein the particular packet is received by the device via a first protocol, and wherein the method further comprises:

encapsulating, by the device, the particular packet in a message according to a second protocol, prior to sending the particular packet.

12. A method comprising:

determining, by a device in a network, that a particular packet flow is sensitive to packet reordering;

wherein the device determines that the particular packet flow is sensitive to reordering based on a policy received from a supervisory device;

determining, by the device, whether a particular packet of the packet flow received by the device is marked as having been routed differently than a previously received packet of the packet flow, in response to determining that the packet flow is sensitive to packet reordering;

buffering and delaying, by the device, the particular packet until either one or more out-of-order packets of the packet flow are received by the device subsequent to receiving the particular packet or upon expiration of a timeout period, in response to determining that the particular packet is marked as having been routed differently than the previously received packet of the packet flow; and

forwarding, by the device, all buffered packets of the packet flow in sequential order.

13. The method as in claim 12, further comprising:

decapsulating, by the device, the particular packet, prior to forwarding the packet.

14. The method as in claim 12, further comprising:

providing, by the device, an indication to a router that forwarded the particular packet to the device that an adjustment to a rerouting strategy used by the router is requested, based on the buffering and delaying.

15. The method as in claim 14, wherein the indication is piggybacked in a data packet sent in a direction opposite that of the particular packet flow.

16. The method as in claim 12, further comprising:

forwarding, by the device, the particular packet immediately, in response to determining that the particular packet is not marked as having been routed differently than the previously received packet of the packet flow.

17. An apparatus, comprising:

one or more network interfaces to communicate with a segment routed network;

a processor coupled to the one or more network interfaces and configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine that a particular packet flow in the network is sensitive to packet reordering;

wherein the apparatus determines that the particular packet flow is sensitive to reordering based on a policy received from a supervisory device;

determine whether a particular packet of the packet flow is to be routed differently than an immediately prior packet in the packet flow, in response to determining that the particular packet flow is sensitive to reordering; and

mark the particular packet as taking a different route than the immediately prior packet in the packet flow, prior to forwarding the marked packet and in response to determining that the particular packet is to be routed differently than the immediately prior packet in the packet flow.

18. The apparatus as in claim 17, wherein the at least one packet in the packet flow is marked as sensitive to reordering by one or more of:

a set bit in a packet header of the at least one packet, a packet classifier that routes the at least one packet, a set bit in a traffic class header of the at least one packet, a port number associated with the at least one packet, a network address associated with the at least one packet, a flow label associated with the at least one packet, or an IPv6 hop-by-hop option.

19. The apparatus as in claim 17, wherein the process when executed is further operable to:

receive an indication from a router in the network that the router received packets of the particular packet flow out of order.

20. The apparatus as in claim 17, wherein the process when executed is further operable to:

adjust a routing strategy used by the apparatus to route packet flows, in response to receiving a threshold number of indications from the router indicating that the router received packet flow packets out of order.

21. An apparatus, comprising:

one or more network interfaces to communicate with a segment routed network;

a processor coupled to the one or more network interfaces and configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine that a particular packet flow is sensitive to packet reordering;

wherein the apparatus determines that the particular packet flow is sensitive to reordering based on a policy received from a supervisory device;

determine whether a particular packet of the packet flow received by the apparatus is marked as having been routed differently than a previously received packet of the packet flow, in response to determining that the packet flow is sensitive to packet reordering;

buffer and delay the particular packet until either one or more out-of-order packets of the packet flow are received by the apparatus subsequent to receiving the particular packet or upon expiration of a timeout period, in response to determining that the particular packet is marked as having been routed differently than the previously received packet of the packet flow; and

forward all buffered packets of the packet flow in sequential order.

22. The apparatus as in claim 21, wherein the process when executed is further operable to:

provide an indication to a router that forwarded the particular packet to the apparatus that an adjustment to a rerouting strategy used by the router is requested, based on the buffering and delaying.

23. The apparatus as in claim 21, wherein the process when executed is further operable to:

forward the particular packet immediately, in response to determining that the particular packet is not marked as having been routed differently than the previously received packet of the packet flow.