SYSTEM AND METHOD OF LOAD BALANCING ACROSS A MULTI-LINK GROUP

• US 20170295099A1
• Filed: 04/11/2016
• Published: 10/12/2017
• Est. Priority Date: 04/11/2016
• Status: Active Application

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Murphy, James
• Application Number:
  US15/096,148
• Publication Number:
  US 20170295099A1
• Time in Patent Office: Days
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

A method and apparatus of a device that queues an out-of-order packet received on a multi-link group is described. In an exemplary embodiment, the device receives a packet on a link of the multi-link group of a network element, where the packet is part of a data flow. The device further examines the packet, if the packet is associated with a re-orderable route. In addition, the device examines the packet by retrieving a packet sequence number from the packet and comparing the packet sequence number with the last received sequence number for this data flow. The device transmits the packet if the packet is a next packet in the data flow. If the packet is out-of-order, the device queues the packet.

Claims

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to queue an out-of-order packet received on a multi-link group, the method comprises:

receiving a packet on a link of the multi-link group of a network element, where the packet is part of a data flow of sequenced packets;

an

examining the packet if the packet is associated with a re-orderable route, wherein the examining includes,

retrieving a packet sequence number from the packet,

comparing the packet sequence number with the largest transmitted sequence number for this data flow,

transmitting the packet if the packet is a next packet in the data flow, and

queuing the packet if the packet is out-of-order.

2. The machine-readable medium of claim 1, wherein the packet is the next packet in the data flow if the packet sequence number is one greater than the largest transmitted sequence number.

3. The machine readable medium of claim 1, wherein the packet is out-of-order if the packet sequence number is two or more greater than the largest transmitted sequence number.

4. The machine readable medium of claim 3, wherein the examining further comprises:

transmitting the packet if the packet sequence number is less than the largest transmitted sequence number.

5. The machine readable medium of claim 1, wherein the data flow is a Transmission Control Protocol (TCP) session.

6. The machine readable medium of claim 5, wherein the packet is a TCP packet.

7. The machine readable medium of claim 1, wherein the multi-link group is an Equal Cost Multi-Path (ECMP) group.

8. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to advertise a re-orderable route from a network element, the method comprising:

determining that the route is the re-orderable route, wherein a re-orderable route is a route that is associated with a queue to store an out-of-order packet; and

advertising the route using a routing protocol from the network element to other network elements coupled to this network element in a network, wherein in the advertised route includes an indication that this route is the re-orderable route.

9. The machine readable medium of claim 8, wherein the route is selected from the group consisting of a local route for the network element and a route defined by a policy as re-orderable.

10. The machine readable medium of claim 8, wherein the route is a route to one or more hosts coupled to the network element.

11. The machine readable medium of claim 8, wherein the routing protocol includes an extension that is used to indicate that the route is a re-orderable route.

12. The machine readable medium of claim 8, wherein the routing protocol is selected from the group consisting of Open Shortest Path First (OSPF), Border Gateway Protocol (BGP), Intermediate System to Intermediate System (IS-IS), OpenFlow, and OpenConfig.

13. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to select a link from a multi-link group coupled to a network element, the method comprising:

receiving a packet on the network element;

determining a next hop route for the packet, wherein the next hop route includes multi-link group that include a plurality of interfaces;

designating a first link selection mechanism as a link selection mechanism if the next hop route is a re-orderable route;

designating a second link selection mechanism as the link selection mechanism if the next hop route is not a re-orderable route;

selecting a transmission interface from the plurality of interfaces using the link selection mechanism; and

transmitting the packet using the transmission interface.

14. The machine readable medium of claim 13, wherein the multi-link group is an Equal Cost Multi-Path (ECMP) group.

15. The machine readable medium of claim 13, wherein the packet is a Transmission Control Packet (TCP).

16. The machine readable medium of claim 13, wherein the re-orderable route is a route that is associated a queue to store an out-of-order packet after being transmitted across the selected transmission interface.

17. The machine readable medium of claim 13, wherein the first link selection mechanism is selected from the group consisting of a round robin and a load based link selection mechanism.

18. The machine readable medium of claim 13, wherein the second link selection mechanism is a hash based link selection mechanism.

19. A method to queue an out-of-order packet received on a multi-link group, the method comprises:

receiving a packet on a link of the multi-link group of a network element, where the packet is part of a data flow of sequenced packets;

an

examining the packet if the packet is associated with a re-orderable route, wherein the examining includes,

retrieving a packet sequence number from the packet,

comparing the packet sequence number with the largest transmitted sequence number for this data flow,

transmitting the packet if the packet is a next packet in the data flow, and

queuing the packet if the packet is out-of-order.

20. A method to advertise a re-orderable route from a network element, the method comprising:

determining that the route is the re-orderable route, wherein a re-orderable route is a route that is associated with a queue to store an out-of-order packet; and

advertising the route using a routing protocol from the network element to other network elements coupled to this network element in a network, wherein in the advertised route includes an indication that this route is the re-orderable route.

21. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to select a link from a multi-link group coupled to a network element, the method comprising:

receiving a packet on the network element;

determining a next hop route for the packet, wherein the next hop route includes multi-link group that include a plurality of interfaces;

designating a first link selection mechanism as a link selection mechanism if the next hop route is a re-orderable route;

designating a second link selection mechanism as the link selection mechanism if the next hop route is not a re-orderable route;

selecting a transmission interface from the plurality of interfaces using the link selection mechanism; and

transmitting the packet using the transmission interface.