System and method to support enhanced equal cost multi-path and link aggregation group

• US 8,619,587 B2
• Filed: 06/09/2010
• Issued: 12/31/2013
• Est. Priority Date: 01/05/2010
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Yong, Lucy, Peilin, Yang
• Primary Examiner(s): Harper, Kevin C
• Assistant Examiner(s): CHOUDHRY, SAMINA F
• Application Number:
  US12/797,010
• Publication Number:
  US 20110164503A1
• Time in Patent Office: 1,301 Days
• Field of Search: None
• US Class Current: 370/241
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

An apparatus comprising a small flow forwarding module configured to distribute and forward a plurality of packets that correspond to a plurality of small flows over a plurality of paths, a large flow forwarding module configured to distribute and forward a plurality of packets that correspond to a plurality of large flows over the paths, and a packet header checking module in communication with the small flow forwarding module and the large flow forwarding module, wherein the packet header checking module is configured to inspect a flow indication in an incoming packet and forward the packet to the small flow forwarding module if the flow indication corresponds to one of the small flows or to the large flow forwarding module if the flow indication corresponds to one of the large flows.

Claims

1. An apparatus comprising:

a small flow forwarding module configured to receive a plurality of first packets that correspond to a plurality of small flows and distribute the first packets over a plurality of paths;

a large flow forwarding module configured to receive a plurality of second packets that correspond to a plurality of large flows and distribute the second packets over the paths; and

a packet header checking module in communication with the small flow forwarding module and the large flow forwarding module,

wherein the packet header checking module is configured to inspect a flow indication in an incoming packet and forward the packet to the small flow forwarding module if the flow indication corresponds to one of the small flows or to the large flow forwarding module if the flow indication corresponds to one of the large flows,

wherein the large flow forwarding module is further configured to;

store a large flow table that comprises a list of large flows received at the apparatus;

determine if there is an entry in the large flow table for a flow for the incoming packet when the flow indication corresponds to one of the large flows;

adding an entry for the flow to the large flow table if there is no entry for the flow in the large flow table; and

updating a flow status to current when a flow indication in an incoming packet indicates that a flow for the incoming packet is a large flow and if an entry for the flow is found in the large flow table,

wherein adding the entry for the flow comprises assigning the flow to a component link and storing the mapping of the flow and the component link into the large flow table, and

wherein the entry for the flow comprises;

a flow identifier that indicates the identity of the flow;

a path identifier that indicates at least one path used to forward the flow; and

a status identifier that indicates whether the flow is transported over the path identified.

2. The apparatus of claim 1, wherein the large flows represent a plurality of first flows with high flow rates and the plurality of small flows represents a plurality of second flows with low flow rates, and wherein the high flow rates are substantially larger than the low flow rates, and wherein the small flow forwarding module and the large flow forwarding module are positioned between the packet header checking module and the plurality of paths.

3. The apparatus of claim 1, wherein the incoming packet is a pseudowire (PW) packet and the flow indication is a flow label that comprises a traffic class (TC) and a time to live (TTL) field.

4. The apparatus of claim 3, wherein the flow indication corresponds to a small flow if a bit of the TC is set to about zero, wherein the flow indication corresponds to a large flow if the bit is set to about one, and wherein the small flow forwarding module is further configured to distribute the small flows over the paths using hashing distribution.

5. The apparatus of claim 3, wherein the TTL field comprises a value equal to about zero to indicate that a bottom label of the packet is the flow label, and wherein the large flow forwarding module is further configured to distribute the large flows over the path by using the large flow table.

6. The apparatus of claim 1, wherein the incoming packet is a Label Switched Path (LSP) packet and a bottom label of the packet is an entropy label, wherein the large flows are distributed over only a subset of the paths, and wherein at least one path in the subset of the paths include both the large flows and the small flows.

7. The apparatus of claim 1, wherein the incoming packet is an Internet Protocol (IP) version 6 packet that comprises a flow label with a large flow classification in an IP header, and wherein the flow indication corresponds to a large flow if a bit in a traffic class (TC) field is set to about one.

8. The apparatus of claim 1, wherein the incoming packet is an Internet Protocol (IP) version 4 packet that comprises a flow label with a large flow classification in an IP header, and wherein the flow indication corresponds to a large flow if a bit in a type of service field is set to about one.

9. A method comprising:

receiving a packet that corresponds to a flow at an edge node in a network;

determining whether the flow corresponds to a large flow or a small flow;

inserting a large flow indication in the packet to indicate that the flow is the large flow or the small flow;

storing a large flow table that comprises a list of large flows received at an edge node;

determining if there is an entry for the flow in the large flow table;

adding an entry for the flow to the large flow table if there is no entry for the flow in the large flow table;

updating the flow status to current when the flow indication in the packet indicates that the flow is a large flow and if an entry for the flow is found in the large flow table; and

forwarding the packet to an internal node in the network,

wherein adding the entry for the flow comprises assigning the flow to a component link and storing the mapping of the flow and component link into the large flow table, and

wherein the entry for the flow comprises;

a flow identifier that indicates the identity of the flow;

a path identifier that indicates at least one path used to forward the flow; and

a status identifier that indicates whether the flow is transporting over the path identified,

wherein the large flow indicates the flow has a high flow rate, and

wherein the small flow indicates the flow has a low flow rate that is less than the high flow rate.

10. The method of claim 9 further comprising temporarily caching the packets if the flow of the packet is determined to be a large flow and mapping the flow to a path to guarantee forwarding the packet in proper sequence.

11. A network component comprising:

a packet header checking module configured to;

receive a plurality of incoming packets that corresponds to at least one data flow;

detect a flow indication for each incoming packet of the plurality of incoming packets;

forward the incoming packets that correspond to a first data flow with a low flow rate to a small flow forwarding module when the flow indication designates the corresponding data flows as a small flow; and

forward the incoming packets that correspond to a second data flow with a high flow rate to a large flow forwarding module when the flow indication designates the corresponding data flow as a large flow, wherein the high flow rate is greater than the low flow rate,

wherein the small flow forwarding module is coupled to the packet header checking module,

wherein the large flow forwarding module is coupled to the packet header checking module and is configured to;

forward the incoming packets that correspond to the large flows over a plurality of aggregated paths based on a large flow table;

store the large flow table that comprises a list of large flows received by the network component;

determine if there is an entry in the large flow table for a flow for one of the incoming packets that correspond to one of the large flows;

add an entry for the flow to the large flow table if there is no entry for the flow in the large flow table; and

update a flow status to current when a flow indication in an incoming packet indicates that a flow for the incoming packet is a large flow and if an entry for the flow is found in the large flow table,

wherein adding the entry for the flow comprises assigning the flow to a component link and storing the mapping of the flow and the component link into the large flow table, and

wherein the entry for the flow comprises;

a flow identifier that indicates the identity of the flow;

a path identifier that indicates at least one path used to forward the flow; and

a status identifier that indicates whether the flow is transported over the path identified.

12. The network component of claim 11, wherein the incoming packets that correspond to the second data flow that are assigned to the congested path are discarded or redirected to a second path in the aggregated paths, wherein the small flow forwarding module is configured to use a hashing function in distributing the flows to the aggregated paths, and wherein the large flow forwarding module is further configured to forward the incoming packets that correspond to the large flow that is assigned to a path in the aggregated paths that becomes substantially congested to other paths in the aggregated paths that are uncongested by mapping the large flows to the uncongested paths in the large flow table or drop the incoming packets.

13. The network component of claim 11, wherein the incoming packets that correspond to the second data flow that are assigned to the congested path are temporarily cached and subsequently forwarded to another uncongested path to avoid the packet re-ordering.

14. The network component of claim 11, wherein the small flow forwarding module is further configured to forward the incoming packets that correspond to the first data flow to one of the plurality of aggregated paths based on a hashing algorithm.

15. The network component of claim 14, wherein the first forwarding algorithm is an equal cost multi-path (ECMP) algorithm or a Link Aggregation Group (LAG) forwarding algorithm that uses hashing.

16. The network component of claim 14, wherein the large flow forwarding module is further configured to receive a plurality of second packets and forward the plurality of second packets based on a second flow forwarding algorithm, and wherein the second forwarding algorithm uses a flow forwarding table to assign the large flow to one of the aggregated paths.

17. The network component of claim 16, wherein the large flow forwarding module is further configured to:

check each entry in a flow forwarding table for an active status value, wherein the active status value indicates a large flow corresponding to the entry is transporting data;

replace the active status value with an aging status value if the active status value is found in any entry, wherein the aging status indicates the large flow corresponding to the entry has not been received for a period of time; and

remove the entry from the flow forwarding table if the aging status value is found in any entry.

18. The network component of claim 16, wherein the large flow forwarding module is further configured to:

obtain a flow identifier (ID) in the packet, wherein the flow ID identifies the data flow that corresponds to the packet;

determine whether there is an entry for the flow ID in the flow forwarding table;

add to the flow forwarding table a new entry that comprises the flow ID, a path ID that corresponds to one of the aggregated paths assigned to the large flow, and an active status value if the flow ID is not found in the flow forwarding table; and

update the active status value in the entry for the flow ID if the flow ID is found in the flow forwarding table,

wherein the active status value indicates the large flow corresponding to the entry is transporting data over one of the aggregated paths indicated by the path ID.

19. The network component of claim 11, wherein the small flow forwarding module and the large flow forwarding module are positioned between the packet header checking module and the plurality of aggregated paths.