Method and apparatus for performing link aggregation

• US 8,792,497 B2
• Filed: 11/29/2006
• Issued: 07/29/2014
• Est. Priority Date: 06/05/2006
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Rajagopalan, Balaji, Nubani, Samer I., Park, Charles C., Paturi, Sirisha
• Primary Examiner(s): Harold, Marsha D Banks
• Assistant Examiner(s): Houshmand, Hooman
• Application Number:
  US11/605,829
• Publication Number:
  US 20070280258A1
• Time in Patent Office: 2,799 Days
• Field of Search: None
• US Class Current: 370/395.3
• CPC Class Codes: H04L 2012/5624 Path aspects, e.g. path bundling
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 45/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/35 Switches specially adapted for specific applications
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

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.

Claims

1. A method of performing link aggregation in a network node, comprising:

mapping a given ingress flow to an egress flow identifier by searching for a match of a first key in a first lookup table and providing a result;

mapping the egress flow identifier to a member of an aggregated group associated with an egress interface of the network node based on information available in the given ingress flow using a globally-unique, node-wide, aggregate flow identifier by searching for a match of a second key in a second lookup table, the second key including at least part of the result; and

forwarding the given ingress flow, via the egress interface, to the member of the aggregated group associated with the egress interface;

wherein the number of entries in the first and second lookup tables combined is based on the number of ingress flows supported by an ingress interface plus the number of members of the aggregated group associated with the egress interface.

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 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.

4. The method according to claim 1 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.

5. The method according to claim 1 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 aggregated group associated with the egress interface based on the index value.

6. The method according to claim 1 further comprising identifying at least one parameter of the first key or the second key, the parameter being associated with the given ingress flow.

7. The method according to claim 1 wherein the number of entries in the first and second lookup tables combined is equal to the number of ingress flows supported by an ingress interface plus the number of members of the aggregated group associated with the egress interface.

8. The method according to claim 1 wherein searching the first and second lookup tables includes accessing Content Addressable Memory (CAM).

9. The method of claim 1, further comprising:

building the first key based on the given ingress flow; and

building the second key based on at least one of a hash value calculated from the given ingress flow, the egress flow identifier, and other key parameters.

10. The method of claim 9, further comprising calculating the hash value based on at least one of a source Media Access Control (MAC) address, destination MAC address, source Internet Protocol (IP) address, and destination IP address of the given ingress flow.

11. A network node, comprising:

a first mapping unit configured to map a given ingress flow to an egress flow identifier by searching a first lookup table for a match of a first key and providing a result;

a second mapping unit configured to map the egress flow identifier to a member of an aggregated group associated with an egress interface of the network node based on information available in the given ingress flow using a globally-unique, node-wide, aggregate flow identifier by searching a second lookup table for a match of a second key, the second key including at least part of the result; and

a flow forwarding unit configured to forward the given ingress flow, via the egress interface, to the member of the aggregated group associated with the egress interface;

wherein the number of entries in the first and second lookup tables combined is based on the number of ingress flows supported by an ingress interface plus the number of members of the aggregated group associated with the egress interface.

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 mapping unit uses the result of the hashing unit to determine the member of the 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.

14. The node according to claim 11, further comprising a linking unit configured to receive an index value from the first lookup table and provides at least part of the second key.

15. The node according to claim 14 wherein the linking unit is Static random Access Memory (SRAM) having entries addressed by the index value.

16. The node according to claim 11 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.

17. The node according to claim 11 wherein the number of entries in the first and second lookup tables combined is equal to the number of ingress flows supported by an ingress interface plus the number of members of the aggregated group associated with the egress interface.

18. The node according to claim 11 wherein the first and second lookup tables are Content Addressable Memory (CAM).

19. A non-transitory 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:

map a given ingress flow to an egress flow identifier by searching for a match of a first key in a first lookup table and providing a result;

map the egress flow identifier to a member of an aggregated group associated with an egress interface of a network node based on information available in the given ingress flow using a globally-unique, node-wide, aggregate flow identifier by searching for a match of a second key in a second lookup table, the second key including at least part of the result; and

forward the given ingress flow, via the egress interface, to the member of the aggregated group associated with the egress interface;

the number of entries in the first and second lookup tables combined is based on the number of ingress flows supported by an ingress interface plus the number of members of the aggregated group associated with the egress interface.