Method and apparatus for updating and synchronizing forwarding tables in a distributed network switch

• US 6,735,198 B1
• Filed: 12/21/1999
• Issued: 05/11/2004
• Est. Priority Date: 12/21/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Levenson, Herman, Sanzgiri, Ajit, Rajendran, Saravanakumar, Nguyen, Tuan Thanh, Surma, Claudette Lucille, Lue, Rong-Lung
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/469,062
• Time in Patent Office: 1,603 Days
• Field of Search: 370/389, 370/390, 370/392, 370/362, 370/400, 370/401, 370/419, 370/420, 370/423, 370/469, 370/471, 370/472, 370/428, 370/412, 370/422, 370/462, 370/463, 340/2.28, 709/238
• US Class Current: 370/389
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A mechanism and technique updates and synchronizes forwarding tables contained on line cards that are interconnected by a switch fabric of a distributed network switch. The network switch is preferably a L3 or L4 switch comprising a plurality of forwarding engines distributed among the line cards. Each forwarding engine has an associated forwarding table, which preferably includes a L2 portion and L3/L4 portions. The L2 portion of the table is used to execute forwarding decision operations for frames forwarded among ports of the line cards, whereas the L3/L4 portions of the table are used to execute shortcut and forwarding operations for frames routed among the ports. The mechanism comprises a media access control (MAC) notification (MN) frame for updating and synchronizing the location of a destination port stored in the L2 portions of the forwarding tables.

Claims

1. A method for updating and synchronizing forwarding tables contained on cards interconnected by a switch fabric of a distributed network switch, the forwarding tables including an ingress forwarding table associated with an ingress card and an egress forwarding table associated with an egress card of the switch, the method comprising the steps of:

switching a frame from the ingress card to the egress card, the switched frame containing a destination media access control (MAC) address and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address;

determining (i) whether a primary input (PI) indicator is asserted for an entry of the egress forwarding table associated with the destination MAC address and (ii) whether the ingress DI of the switched frame is different from an egress DI for the egress forwarding table entry;

generating a notification frame at the egress card for transfer to the ingress card, the notification frame including a source MAC address field and a source index field, the source index field having contents representative of a location within the switch associated with the source MAC address; and

updating the ingress forwarding table with the contents of the source MAC address and source index fields to thereby synchronize the ingress and egress forwarding tables.

2. The method of claim 1 wherein the notification frame is a MAC notification (MN) frame.

3. The method of claim 2 wherein the step of generating comprises the step of, when the PI indicator is asserted and the ingress DI is different from the egress DI, generating a positive MN frame.

4. The method of claim 3 wherein the contents of the source index field reflect a port and line card within the switch that originates the MN frame.

5. The method of claim 4 wherein the originating port and line card comprise an outgoing port on an egress card.

6. The method of claim 3 wherein the step of updating comprises the step of establishing an entry in the ingress forwarding table using the contents of the source MAC address and source index fields of the positive MN frame.

7. The method of claim 2 wherein the step of generating comprises the steps of, when the PI indicator is not asserted and the ingress DI does not match the egress DI:

generating a negative MN frame at the egress card;

setting the contents of the source index field of the negative MN frame to a predetermined value representative of a flood operation; and

sending the negative MN frame to the ingress card.

8. The method of claim 7 wherein the step of updating comprises the step of updating an entry associated with the destination MAC address in the ingress forwarding table with the predetermined value in the source index field of the negative MN frame.

9. The method of claim 8 wherein the predetermined value is representative of a flood-to-virtual local area network (VLAN) operation.

32. A computer readable media, comprising:

said computer readable media containing instructions for execution in a processor for the practice of the method of claim 1 or claim 21.

33. Electromagnetic signals propagating on a computer network, comprising:

said electromagnetic signals carrying instructions for execution on a processor for the practice of the method of claim 1 or claim 21.

10. Apparatus for updating and synchronizing forwarding tables contained on cards interconnected by a switch fabric of a distributed network switch, the forwarding tables including an ingress forwarding table associated with an ingress card and an egress forwarding table associated with an egress card of the switch, the apparatus comprising:

a switch fabric for switching a frame from the ingress card to the egress card, the switched frame containing a destination media access control (MAC) address and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address in the switch;

means for determining (i) whether a primary input (PI) indicator is asserted for an entry of the egress forwarding table associated with the destination MAC address and (ii) whether the ingress DI of the switched frame is different from an egress DI for the egress forwarding table entry;

means for generating a notification frame at the egress card for transfer to the ingress card, the notification frame including a source MAC address field and a source index field, the source index field having contents representative of a location within the switch associated with the source MAC address; and

means for updating the ingress forwarding table with the contents of the source MAC address and source index fields to thereby synchronize the ingress and egress forwarding tables.

11. The apparatus of claim 10 wherein the means for generating comprises a forwarding engine associated with the egress card.

12. The apparatus of claim 11 wherein the notification frame is a MAC notification (MN) frame.

13. The apparatus of claim 12 wherein the MN frame includes a port-of-exit field, a destination index field, a virtual local area network field and a destination MAC address field.

14. The apparatus of claim 13 wherein the MN frame further includes a don'"'"'t forward (DF) bit which, when asserted, specifies forwarding of the MN frame only through the switch fabric.

15. The apparatus of claim 10 wherein the PI indicator is one of a single bit and a plurality of bits.

16. The apparatus of claim 15 wherein the PI indicator denotes a primary input MAC address directly attached to a port of the egress card associated with the entry of the egress forwarding table.

17. A computer readable medium containing executable program instructions for synchronizing forwarding tables contained on cards interconnected by a switch fabric of a distributed network switch, the forwarding tables including an ingress forwarding table associated with an ingress card and an egress forwarding table associated with an egress card of the switch, the executable program instructions comprising program instructions for:

switching a frame from the ingress card to the egress card, the switched frame containing a destination media access control (MAC) address and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address;

determining (i) whether a primary input (PI) indicator is asserted for an entry of the egress forwarding table associated with the destination MAC address and (ii) whether the ingress DI of the switched frame is different from an egress DI for the egress forwarding table entry;

generating a notification frame at the egress card for transfer to the ingress card, the notification frame including a source MAC address field and a source index field, the source index field having contents representative of a location within the switch associated with the source MAC address; and

updating the ingress forwarding table with the contents of the source MAC address and source index fields to thereby synchronize the ingress and egress forwarding tables.

18. The computer readable medium of claim 17 wherein the notification frame is a MAC notification (MN) frame and wherein the program instruction for generating comprises the program instruction for, when the PI indicator is asserted and the ingress DI is different from the egress DI, generating a positive MN frame.

19. The computer readable medium of claim 18 wherein the program instruction for updating comprises the program instruction for establishing an entry in the ingress forwarding table using the contents of the source MAC address and source index fields of the positive MN frame.

20. The computer readable medium of claim 17 wherein the notification frame is a MAC notification (MN) frame and wherein the program instruction for generating comprises the program instructions for, when the PI indicator is not asserted and the ingress DI does not match the egress DI:

generating a negative MN frame at the egress card;

setting the contents of the source index field of the negative MN frame to a predetermined value representative of a flood operation; and

sending the negative MN frame to the ingress card.

21. A method for updating and synchronizing forwarding tables contained on cards interconnected by a switch fabric of a distributed network switch, the method comprising the steps of:

providing a forwarding table on each card;

receiving a frame at a first card, hereinafter an ingress card;

switching the frame from the ingress card to an egress card, the switched frame containing a media access control (MAC) address associated with a destination end station and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address, the ingress DI determined by the ingress card using its forwarding table;

determining whether the ingress DI of the switched frame is different from an egress DI, the egress DI determined by the egress card using its forwarding table;

generating, in response to a difference between the ingress DI and egress DI, a notification frame at the egress card for transfer to the ingress card; and

updating, responsive to the notification frame, the ingress forwarding table to match the egress forwarding table.

22. The method of claim 21 further comprising:

matching the contents of a source MAC address and source index fields in the ingress and egress forwarding tables.

23. The method of claim 22 further comprising:

determining whether a primary input (PI) indicator field in a forwarded frame is asserted, the PI indicator asserted for a forwarding table entry having a MAC address that is learned from a frame sourced through one of the ports of a source line card associated with a particular forwarding engine, and not asserted for an address that is learned through the switching fabric.

24. The method of claim 23 further comprising:

making the notification frame a MAC notification (MN) frame.

25. The method of claim 24 further comprising:

generating a positive MN frame when the PI indicator is asserted and the ingress DI is different from the egress DI.

26. The method of claim 25 further comprising:

indicating, by the source index field, a port and line card within the switch that originates the MN frame.

27. The method of claim 25 further comprising:

indicating, by the source index field, an outgoing port on an egress card within the switch that originates the MN frame.

28. The method of claim 25 further comprising:

establishing an entry in the ingress forwarding table using the contents of the source MAC address and source index fields of the positive MN frame.

29. The method of claim 24 further comprising, when the PI indicator is not asserted and the ingress DI does not match the egress DI:

generating a negative MN frame at the egress card;

setting the contents of the source index field of the negative MN frame to a predetermined value representative of a flood operation; and

sending the negative MN frame to the ingress card.

30. The method of claim 29 further comprising:

updating an entry associated with the destination MAC address in the ingress forwarding table with the predetermined value in the source index field of the negative MN frame.

31. The method of claim 30 further comprising:

making the predetermined value be representative of a flood-to-virtual local area network (VLAN) operation.

34. A distributed network switch, comprising:

an ingress card for receiving frames, the ingress card having an ingress forwarding table;

an egress card to send received frames, the egress card having an egress forwarding table; and

a forwarding engine for (i) switching the frame from the ingress card to an egress card, the switched frame containing a media access control (MAC) address associated with a destination end station and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address, the ingress DI determined by the ingress card using its forwarding table, (ii) determining whether the ingress DI of the switched frame is different from an egress DI, the egress DI determined by the egress card using its forwarding table, (iii) generating, in response to a difference between the ingress DI and egress DI, a notification frame at the egress card for transfer to the ingress card, and (iv) updating, responsive to the notification frame, the ingress forwarding table to match the egress forwarding table.

35. The apparatus of claim 34 further comprising:

a source MAC address and source index fields in the ingress and egress forwarding tables to be updated responsive to the notification frame.

36. The apparatus of claim 35 further comprising:

the forwarding engine is to determine whether a primary input (PI) indicator field in a forwarded frame is asserted, the PI indicator asserted for a forwarding table entry having a MAC address that is learned from a frame sourced through one of the ports of a source line card associated with a particular forwarding engine, and not asserted for an address that is learned through the switching fabric.

37. The apparatus of claim 36 further comprising:

a MAC notification (MN) frame as the notification frame.

38. The apparatus of claim 37 further comprising:

a port-of-exit field, a destination index field, a virtual local area network field, and a destination MAC address field, each contained within the MN frame.

39. The apparatus of claim 38 further comprising:

a don'"'"'t forward (DF) bit within the MN frame, which, when asserted, specifies forwarding of the MN frame only through the switch fabric.

40. The apparatus of claim 36 further comprising:

a PI indicator, which is one of a single bit and a plurality of bits.

41. The apparatus of claim 36 further comprising:

a PI indicator, which is one of a single bit and a plurality of bits, the PI indicator denoting a primary input MAC address directly attached to a port of the egress card associated with the entry of the egress forwarding table.

42. An apparatus for updating and synchronizing forwarding tables contained on cards interconnected by a switch fabric of a distributed network switch, comprising:

means for providing a forwarding table on each card;

means for receiving a frame at a first card, hereinafter an ingress card;

means for switching the frame from the ingress card to an egress card, the switched frame containing a media access control (MAC) address associated with a destination end station and an ingress destination index (DI) representative of a location within the switch that is associated with the destination MAC address, the ingress DI determined by the ingress card using its forwarding table;

means for determining whether the ingress DI of the switched frame is different from an egress DI, the egress DI determined by the egress card using its forwarding table;

means for generating, in response to a difference between the ingress DI and egress DI, a notification frame at the egress card for transfer to the ingress card; and

means for updating, responsive to the notification frame, the ingress forwarding table to match the egress forwarding table.