Method and apparatus for performing link aggregation

Abstract

A network node or corresponding method of performing link aggregation reduces a number of Content Addressable Memory (CAM) entries required to make a forwarding decision for a given ingress flow, reducing cost, size, and power consumption of the CAM and accompanying static RAM. In one embodiment, an ingress flow is mapped to an egress flow identifier. Subsequently, the egress flow identifier is mapped to a member of an aggregated group associated with an egress interface based on information available in a given ingress flow. Finally, the given ingress flow is forwarded to the member of the aggregated group associated with the egress interface. A hashing technique or two lookups may be used alone or in combination in mapping the ingress flow to the egress flow identifier to reduce CAM memory usage.

1 . A method of performing link aggregation, comprising:
 forwarding a given ingress flow to an egress interface; and   at least one of:   prior to the forwarding, mapping the given ingress flow associated with a member of a first aggregated group to an ingress flow identifier based on information available in the given ingress flow; and   prior to the forwarding, mapping the given ingress flow to an egress flow identifier and mapping the egress flow identifier to a member of a second aggregated group associated with the egress interface based on information available in the given ingress flow.   
     
     
         2 . The method according to  claim 1  wherein mapping the egress flow identifier includes hashing a unique identifier available in the given ingress flow and using a result of the hashing in determining the member of the second aggregated group. 
     
     
         3 . The method according to  claim 2  wherein the unique identifier includes source and destination Media Access Control (MAC) addresses, or source and destination Internet Protocol (IP) addresses, or a Multiprotocol Label Switching (MPLS) label. 
     
     
         4 . The method according to  claim 1  wherein (i) mapping the given ingress flow includes searching for a match of a first key in a first lookup table and (ii) mapping the egress flow identifier to the member of the second aggregated group includes searching for a match of a second key in a second lookup table. 
     
     
         5 . The method according to  claim 4  wherein mapping the given ingress flow provides at least part of the second key for searching the second lookup table. 
     
     
         6 . The method according to  claim 4  wherein searching for a match of the first key results in an index value and mapping the given ingress flow further includes identifying the egress flow identifier based on the index value. 
     
     
         7 . The method according to  claim 4  wherein searching for a match of the second key results in an index value and mapping the egress flow identifier further includes identifying the member of the second aggregated group associated with the egress interface based on the index value. 
     
     
         8 . The method according to  claim 4  further comprising identifying at least one parameter of the first key or the second key, the parameter being associated with the given ingress flow. 
     
     
         9 . The method according to  claim 4  wherein a number of entries in the first and second lookup tables combined is equal to a number of ingress flows supported by the ingress interface plus a number of members of the second aggregated group 
     
     
         10 . The method according to  claim 4  wherein searching the first and second lookup tables includes accessing Content Addressable Memory (CAM). 
     
     
         11 . A node, comprising:
 a flow forwarding unit configured to forward a given ingress flow to an egress interface; and   at least one of:   an ingress mapping unit configured to map, prior to the forwarding, the given ingress flow associated with a member of a first aggregated group to an ingress flow identifier based on information available in the given ingress flow; and   a first egress mapping unit configured to map, prior to forwarding, the given ingress flow to an egress flow identifier and a second egress mapping unit configured to map the egress flow identifier to a member of a second aggregated group associated with the egress interface based on information available in the given ingress flow.   
     
     
         12 . The node according to  claim 11  further comprising a hashing unit configured to hash a unique identifier available in the given ingress flow, wherein the second egress mapping unit uses the result of the hashing unit to determine the member of the second aggregated group. 
     
     
         13 . The node according to  claim 12  wherein the unique identifier includes source and destination Media Access Control (MAC) addresses, or source and destination Internet Protocol (IP) addresses, or a Multiprotocol Label Switching (MPLS) label. 
     
     
         14 . The node according to  claim 11  wherein (i) the first egress mapping unit searches a first lookup table for a match of a first key and (ii) the second egress mapping unit is configured to map the egress flow identifier to the member of the second aggregated group and the second egress mapping unit searches a second lookup table for a match of a second key. 
     
     
         15 . The node according to  claim 14  further comprising a linking unit that links the search of the first lookup table to the search of the second lookup table. 
     
     
         16 . The node according to  claim 15  wherein the linking unit receives an index value from the first lookup table and provides at least part of the second key. 
     
     
         17 . The node according to  claim 15  wherein the linking unit is Static Random Access Memory (SRAM) having entries addressed by the index value. 
     
     
         18 . The node according to  claim 14  further comprising an identification unit configured to identify at least one parameter of the first key or the second key, the parameter being associated with the given ingress flow. 
     
     
         19 . The node according to  claim 14  wherein the number of entries in the first and second lookup tables combined is equal to a number of ingress flows supported by the ingress interface plus the number of members of the second aggregated group. 
     
     
         20 . The node according to  claim 14  wherein the first and second lookup tables are Content Addressable Memory (CAM). 
     
     
         21 . A computer-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions, when executed by a digital processor, that cause the processor to:
 forward a given ingress flow to an egress interface; and   at least one of:   prior to the forwarding, map the given ingress flow associated with a member of a first aggregated group to an ingress flow identifier based on information available in the given ingress flow; and   prior to forwarding, map the given ingress flow to an egress flow identifier and map the egress flow identifier to a member of a second aggregated group associated with the egress interface based on information available in the given ingress flow.   
     
     
         22 . The method according to  claim 1 , wherein the first aggregated group includes one or more ingress ports and the second aggregated group includes one or more egress ports. 
     
     
         23 . The method according to  claim 1 , wherein the forwarding is based upon hashing on one or more labels or one or more Internet Protocol (IP) addresses or one or more Media Access Control (MAC) addresses. 
     
     
         24 . The method according to  claim 1 , wherein a user may modify, add, or remove at least one of: one or more members of the first aggregate group and one or more members of the second aggregate group. 
     
     
         25 . The method according to  claim 1 , wherein the forwarding includes sending the given ingress flow to at least one member of the second aggregated group. 
     
     
         26 . The method according to  claim 3  wherein the source and destination IP addresses include at least one of: IP version 4 (IPv4) addresses and IP version 6 (IPv6) addresses. 
     
     
         27 . The method according to  claim 1 , further comprising:
 prior to the forwarding, mapping the given ingress flow associated with the member of the first aggregated group to the ingress flow identifier based on information available in the given ingress flow.   
     
     
         28 . The method according to  claim 1 , further comprising:
 prior to the forwarding, mapping the given ingress flow to the egress flow identifier and mapping the egress flow identifier to the member of the second aggregated group associated with the egress interface based on information available in the given ingress flow.   
     
     
         29 . The method according to  claim 1  wherein mapping the given ingress flow includes searching for a match of a first key in a lookup table and mapping the member of the first aggregated group to the ingress flow identifier. 
     
     
         30 . The method according to  claim 29  wherein searching for a match of the first key results in an indexed value which is identical for members of the first aggregated group and mapping the ingress flow includes further identifying the egress interface based on the index value. 
     
     
         31 . The method according to  claim 29  wherein searching for a match of the first key results in an indexed value which is different for members of the first aggregated group and mapping the ingress flow includes further identifying the egress interface based on the index value. 
     
     
         32 . The method according to  claim 29  wherein searching the lookup table includes accessing Content Addressable Memory (CAM). 
     
     
         33 . The node according to  claim 11  wherein a mapping unit is configured to map the given ingress flow including searching for a match of a first key in a lookup table and mapping the member of the first aggregated group to the ingress flow identifier. 
     
     
         34 . The node according to  claim 33  further comprising a linking unit that links search results of the lookup table for the member of the first aggregated group to subsequent lookups. 
     
     
         35 . The node according to  claim 34  wherein the linking unit receives an index value from the lookup table and provides at least part of a subsequent key. 
     
     
         36 . The node according to  claim 34  wherein the linking unit is Static Random Access Memory (SRAM) having entries addressed by the index value. 
     
     
         37 . The method according to  claim 1  wherein the forwarding includes sending the given ingress flow associated with the first aggregated group to either an egress interface associated with the second aggregated group or to another egress interface.