METHOD AND APPARATUS FOR REDUCING FLOOD TRAFFIC IN SWITCHES

• US 20090219817A1
• Filed: 03/02/2009
• Published: 09/03/2009
• Est. Priority Date: 03/02/2008
• Status: Active Grant

• Current Assignee: Jeffrey Alan Carley
• Original Assignee: Jeffrey Alan Carley
• Inventors: Carley, Jeffrey Alan
• Granted Patent: US 8,279,867 B2
• Time in Patent Office: Days
• US Class Current: 370/235.100
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

An improved method and apparatus for making forwarding decisions in a switching device. The invention reduces the flooding of frames to particular network segments connected to the switch. To insure a device sees a frame addressed to it, if a switch does not know what segment a device address is connected to for a unicast frame, the switch typically floods the frame to all segments in the broadcast domain. This invention allows segments to be identified as having a predefined maximum number of device addresses that will be associated with it. When that number of addresses is already in the forwarding table the switch will not flood unicast frames to that segment since no more devices should be connected to that segment.

Claims

1. A method for limiting the flooding of unicast traffic on one or more logical network segment (LNS) operatively coupled with a switching device said switching device comprising one or more ports each said port capable of operatively coupling one or more of said LNSs and said switching device, said switching device capable of bridging and filtering data frames between said operatively coupled LNSS, said method comprising:

(i) identifying and selecting one or more limited flooding logical network segment (LFLNS) selected from the group consisting of said LNSs operatively coupled to said switching device wherein (a) a selected LFLNS has a predetermined maximum number of device addresses expected to be concurrently operatively associated with said LFLNS and (b) said method is to be utilized on said LFLNS;

(ii) for one or more first LFLNS selected from the group consisting of said LFLNSs on said switching device, identifying as a loaded LFLNS each said first LFLNS wherein the number of said device addresses currently operatively associated with said first LFLNS in a forwarding table of said switching device is equal to or greater then said predetermined maximum number of said device addresses expected to be concurrently operatively associated with said first LFLNS, said operative association of a first device address and said first LFLNS in said forwarding table indicating a reasonable expectation by said switching device that the device associated with said first device address is operatively coupled with said first LFLNS;

(iii) executing a forwarding decision operation on said switching device for a unicast frame to be forwarded by said switching device, said forwarding decision operation comprising (a) looking up the destination LNS said device address operatively associated with said unicast frame in said forwarding table of said switching device and (b) excluding each second LFLNS from selection as an LNS for the forwarding of said frame if (1) said destination device address was not operatively associated with said second LFLNS in said forwarding table and (2) said second LFLNS is currently identified as a loaded LFLNS.

2. The method of claim 1, wherein one or more of said LFLNSs are physical network segments.

3. The method of claim 1, wherein one or more of said LFLNSs is a segment of a Virtual Local Area Network (VLAN) operatively associated with a physical network segment.

4. The method of claim 1, wherein said predetermined maximum number of device addresses is one.

5. The method of claim 3, wherein said physical network segment supports the operation of only one LNS at a time.

6. The method of claim 3, wherein said physical network segment supports the operation of multiple LNSs at a time.

7. The method of claim 1, wherein determining when said number of said device addresses operatively associated with said first LFLNS in said forwarding table is equal to or greater than said predetermined maximum number of said device addresses comprises:

(a) initializing a counter for each first LFLNS;

(b) adjusting said counter in a set direction each time a said operative association between a said device address and said first LFLNS is added to said forwarding table;

(c) adjusting said counter in a reverse set direction from said set direction of (b) each time a said operative association between a said device address and said first LFLNS is removed from said forwarding table;

(d) indicating said first LFLNS is a loaded LFLNS whenever the number of net said increments in said set direction is equal to or greater than said predetermined maximum number of said device addresses.

8. The method of claim 1, wherein determining when said number of said device addresses operatively associated with said first LFLNS in said forwarding table is equal to or greater than said predetermined maximum number of said device addresses comprises:

(a) looking up all said operative associations with said first LFLNS in said forwarding table each time one or more of the functions from the group consisting of (1) adding an operative association between a said device address and said first LFLNS to said forwarding table and (2) removing an operative association between a said device address and said first LFLNS is performed and determining the number of operative associations with said first LFLNS in said forwarding table after said functions are performed;

(b) indicating said first LFLNS is a loaded LFLNS whenever said number of operative associations is equal to or greater than said predetermined maximum number of said device addresses.

9. The method of claim 1, wherein one or more bitmaps are maintained each bitmap representing the status of a group of one or more LNSs, a first bit value indicating the LNS is a loaded LFLNS and the reverse bit value indicating the LNS is not a loaded LFLNS.

10. The method of claim 9, wherein each bit in said bitmap corresponds to a port on said switching device.

11. The method of claim 10, wherein there is one bitmap for each logical network (LN) and a first bit values indicates the port is operatively coupled to a loaded LFLNS associated with said LN and the reverse value indicates the port is not a loaded LFLNS associated with said LN.

12. The method of claim 11 wherein excluding each second LNLFS from selection comprises:

(a) selecting a group of ports associated with the logical network (LN) associated with the LNS from which said frame was received; and

(b) utilizing said bitmap associated with said LN to deselect said loaded LFLNS ports identified by said bitmap from said group of ports;

13. The method of claim 1, further comprising:

(a) identifying when an operative association between a said device address and said first LFLNS in said forwarding table will soon be removed from said forwarding table;

(b) generating a frame on said switching device, said frame associating said device address as the destination address for said frame;

(c) communicating said frame on said first LFLNS;

(d) if a response frame from said device is received on said first LFLNS with said device address as the source address for said response frame said device address will have been seen as a source address on said first LFLNS and will not currently be aged out;

(e) if no response frame from said device or any other frame from said device is received then said device address will not have been seen as a source address on said frame and normal aging of said operative association of said device address and said first LFLNS in said forwarding table will take place.

14. An apparatus with limited flooding of unicast traffic on one or more logical network segment (LNS) said apparatus comprising:

(i) one or more ports each said port capable of communicatively coupling with one or more logical network segment (LNS);

(ii) one or more forwarding table said forwarding table capable of associating one or more device addresses with a said port;

(iii) one or more processor capable of executing a forwarding decision operation;

wherein said ports comprise a means of sending and receiving frames over said one or more LNS; and

wherein when a frame is received on a said LNS, said forwarding decision operation selects a group of zero or more LNSs on which to forward said frame; and

wherein one or LNSs are identified as limited flooding LNSs (LFLNSs), said LFLNSs having a predetermined maximum number of device addresses expected to be concurrently operatively associated with said LFLNS; and

wherein when a said LFLNS is associated with at least said maximum number of said device addresses in said forwarding table, said LFLNS is identified as a loaded LFLNS; and

wherein when said forwarding decision operation does not find the destination device address in said forwarding table for a unicast destination addresss and said forwarding decision operation selects to flood said frame to a group of ports, said LFLNS are excluded from said group of LNSs for flooding.

15. The apparatus of claim 14, wherein one or more bitmap is maintained said bitmap tracking said identified loaded LFLNS for a logical network (LN) said loaded LFLNSs assigned a first bit value and all LNSs that are a part of the LN but are not loaded LFLNSs assigned the opposite bit value and wherein said excluding of said loaded LFLNSs can be accomplished by applying said bitmap to said selected group of LNSs for flooding.

16. The apparatus of claim 14, wherein on or more of said LFLNS is a segment of a Virtual Local Area Network (VLAN) operatively associated with a physical network segment operatively associated with a said port.

17. The apparatus of claim 16, wherein one or more of said LFLNSs are identified by identifying (i) said port operatively associated with said LFLNS and (ii) a VLAN Identifier (VLAN ID) for said LFLNS.

18. The apparatus of claim 14, wherein determining when said number of said device addresses operatively associated with a first LFLNS in said forwarding table is at least equal to said predetermined maximum number of said device addresses for said first LFLNS comprises:

(a) a counting means for said first LFLNS said counting means initialized to a first value;

(b) an adjustment means for adjusting said counting means in a set direction each time a said operative association between a said device address and said first LFLNS is added to said forwarding table;

(c) an adjustment means for adjusting said counting means in a reverse set direction from said set direction of (b) each time a said operative association between a said device address and said first LFLNS is removed from said forwarding table;

(d) an indicating means for indicating said first LFLNS is a loaded LFLNS whenever the number of net said increments in said set direction is equal to or greater than said predetermined maximum number of said device addresses.

19. The apparatus of claim 14, wherein determining when said number of said device addresses operatively associated with a first said LFLNS in said forwarding table is at least equal to said predetermined maximum number of said device addresses for said first LFLNS comprises:

(a) a means of looking up all said operative associations with said first LFLNS in said forwarding table each time one or more of the functions from the group consisting of (1) adding an operative association between a said device address and said first LFLNS to said forwarding table and (2) removing an operative association between a said device address and said first LFLNS is performed and determining the number of operative associations with said first LFLNS are in said forwarding table after said functions are performed;

(b) indicating said first LFLNS is a loaded LFLNS whenever said number of operative associations is at least equal to said predetermined maximum number of said device addresses for said first LFLNS.

20. The apparatus of claim 14, further comprising said apparatus:

(a) a means of generating a frame with an associated destination device address of a device address for which an operative association between said first LFLNS and said device address is about to be removed from said forwarding table; and

(b) a means of communicating said frame on said first LFLNS.