METHOD, SYSTEM AND PROGRAM PRODUCT FOR EQUITABLE SHARING OF A CAM TABLE IN A NETWORK SWITCH IN AN ON-DEMAND ENVIRONMENT

• US 20080222352A1
• Filed: 03/05/2007
• Published: 09/11/2008
• Est. Priority Date: 03/05/2007
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Zaghloul, Atef O., Zeiger, John H., Booth, Bruce, Goodgion, Mark E.
• Granted Patent: US 7,711,900 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A method, system and program product for equitable sharing of a CAM (Content Addressable Memory) table among multiple users of a switch. The method includes reserving buffers in the table to be shared, the remaining buffers being allocated to each user. The method further includes establishing whether or not an address contained in a packet from a user is listed in a buffer in the table, if the address is listed, updating a time-to-live value for the buffer for forwarding the packet and, if the address is not listed, determining whether or not the user has exceeded its allocated buffers and whether or not the reserved buffers have been exhausted, such that, if the user has exceeded its allocated buffers and the reserved buffers have been exhausted, the address is not added to the table and the user is precluded from using any additional buffers in the network switch.

Claims

1. A method for equitable sharing of buffers between a plurality of users of a network switch, said method comprising the steps of:

reserving a subset number of buffers in an address table in a network switch, said subset number of buffers forming a shared buffer pool and a remaining number of buffers in said data table forming a dedicated buffer pool;

establishing, upon arrival of a packet containing an address corresponding to a respective user of a plurality of users, whether or not said address is listed in a buffer in said data table;

if said address is listed in said buffer in said data table, updating a preset time-to-live value for said buffer in said data table and forwarding said packet; and

if said address is not listed in said buffer in said data table, determining whether or not said respective user of said plurality of users has exceeded a preset number of buffers allocated from said dedicated buffer pool and whether or not said subset number of buffers reserved in said shared buffer pool have been exhausted;

wherein if said preset number of buffers allocated to said respective user from said dedicated buffer pool and said subset number of buffers reserved in said shared buffer pool have been exhausted, said respective user is precluded from using any additional buffers in said network switch.

2. The method according to claim 1, further comprising the steps of:

ascertaining said plurality of users to be supported by said network switch; and

allocating to each user of said plurality of users a preset number of buffers from said dedicated buffer pool in said network switch.

3. The method according to claim 2, further comprising the steps of:

upon expiration of said preset time-to-live value for said buffer in said data table, deleting said address entered in said buffer; and

returning said buffer to said shared buffer pool.

4. The method according to claim 3, wherein said determining step further comprises the steps of:

maintaining for each user of said plurality of users a running tally of a total number of buffers in said data table being used by said each user;

keeping a running tally of buffers remaining in said shared buffer pool in said data table being used by said plurality of users; and

comparing said running tally of said total number of buffers maintained for said respective user to said preset number of buffers allocated to said respective user from said dedicated buffer pool.

5. The method according to claim 4, wherein said determining step further comprises the steps of:

if said running tally of said total number of buffers used by said respective user does not exceed said preset number of buffers allocated to said respective user from said dedicated buffer pool, incrementing by one said running tally of said total number of buffers maintained for said respective user and adding said address to said data table in order to forward said packet;

if said running tally of said total number of buffers used by said respective user exceeds said preset number of buffers allocated to said respective user from said dedicated buffer pool, verifying whether or not said subset number of buffers reserved in said shared buffer pool have been exhausted; and

if it is verified that said subset number of buffers reserved in said shared buffer pool have not been exhausted, allowing said respective user to borrow a buffer from said shared buffer pool to add said address to said data table in order to forward said packet.

6. The method according to claim 5, wherein said returning step further comprises the steps of:

if said running tally of said total number of buffers for said respective user is greater than said preset number of buffers allocated to said respective user from said dedicated buffer pool, adding one to said running tally of buffers remaining in said shared buffer pool; and

deleting one from said running tally of said total number of buffers for said respective user.

7. The method according to claim 5, wherein said returning step further comprises the steps of:

if said running tally of said total number of buffers for said respective user is not greater than said preset number of buffers allocated to said respective user from said dedicated buffer pool, deleting one from said running tally of said total number of buffers for said respective user; and

deleting said address entered in said buffer.

8. The method according to claim 7, wherein said preventing step further comprises the steps of:

determining whether or not a prior notification has been sent regarding said subset numbers of buffers reserved in said shared buffer pool being exhausted; and

if it is determined that said prior notification has not been sent, sending notification regarding said subset numbers of buffers reserved in said shared buffer pool being exhausted;

wherein a user of said plurality of users comprises at least one of;

a port, a plurality of ports, a virtual local area network (VLAN) and a plurality of virtual local area networks (VLANs); and

wherein said data table comprises a CAM (Content Addressable Memory) table for storing one or more MAC (Media Access Control) addresses.

9. A system for mitigating flooding of an address table in a network switch, comprising:

a network switch configured to support a number of users connected on a network, said network switch having an address table with a finite number of buffers for storing therein a plurality of addresses corresponding to addresses available on respective ports in said network switch, each address of said plurality of addresses stored therein having a respective preset time-to-live value; and

a buffer allocation tool configured to reserve a subset number of buffers from said finite number of buffers for creating a shared buffer pool, a remaining number of said finite number of buffers forming a dedicated buffer pool, said buffer allocation tool being further configured to allocate to each user of said number of users a total number of buffers in said address table that comprises a preset number of buffers from said dedicated buffer pool and a preset percentage of buffers from said shared buffer pool, said buffer allocation tool being further configured to establish upon arrival of a packet containing an address therein whether or not said address is listed in a buffer in said address table, if said address is listed in said buffer in said address table, said buffer allocation tool being configured to update a preset time-to-live value for said buffer and to forward said packet, and if said address is not listed in said buffer in said address table, said buffer allocation tool being configured to determine whether or not said respective user has exceeded said total number of buffers allocated in said address table, wherein if said respective user has exceeded said total number of buffers allocated in said address table, said buffer allocation tool being configured to prevent said respective user from borrowing any additional buffers in said address table in said network switch.

10. The system according to claim 9, wherein said buffer allocation tool is further configured to maintain a running tally of said total number of buffers in said address table used by each user and to keep a running tally of buffers remaining in said shared buffer pool and is configured to send a notification when said respective user has used up said total number of buffers allocated in said address table.

11. The system according to claim 10, wherein said buffer allocation tool is further configured to compare said running tally of said total number of buffers in said address table used by said respective user to said preset number of buffers from said dedicated buffer pool allocated to said respective user and, if said running tally of said total number of buffers is less than said preset number of buffers allocated from said dedicated buffer pool to said respective user, to increment by one said running tally of said total number of buffers for said respective user and to add said address to said address table in order to forward said packet.

12. The system according to claim 11, wherein if said running tally of said total number of buffers for said respective user is greater than said preset number of buffers allocated from said dedicated buffer pool to said respective user, said buffer allocation tool is further configured to verify whether or not said subset number of buffers reserved in said shared buffer pool have been exhausted and, if said shared buffer pool have not been exhausted, to decrease by one said running tally for said shared buffer pool in order to allow said respective user to use a buffer from said shared buffer pool to add said address in said buffer in said address table and to increase by one said running tally of said total number of buffers for said respective user.

13. The system according to claim 12, wherein said buffer allocation tool is configured to delete said address stored in said buffer in said address table upon expiration of said preset time-to-live value for said buffer and to return said buffer to said shared buffer pool.

14. The system according to claim 13, wherein said buffer allocation tool is configured to determine whether or not a prior notification has been sent regarding said shared buffer pool being exhausted and, if it is determined that said prior notification has not been sent, sending notification regarding said shared buffer pool being exhausted;

wherein a user of said plurality of users comprises at least one of;

a port, a plurality of ports, a virtual local area network (VLAN) and a plurality of virtual local area networks (VLANs); and

wherein said address table comprises a CAM (Content Addressable Memory) table for storing one or more MAC (Media Access Control) addresses.

15. A computer program product for equitable sharing of an address table in a network switch shared by a plurality of users, said computer program product comprising:

a computer readable medium;

first program instructions to reserve a subset number of buffers in an address table in a network switch, said subset number of buffers reserved forming a shared buffer pool and a remaining number of buffers in said address table forming a dedicated buffer pool, said address table storing therein a plurality of addresses corresponding to addresses available on respective ports in said network switch, each address of said plurality of addresses stored therein having a respective preset time-to-live value;

second program instructions to allocate to each user of a plurality of users a total number of buffers in said address table that comprises a preset number of buffers from said dedicated buffer pool and a preset percentage of buffers from said shared buffer pool;

third program instructions to determine for an address in a packet sent by a respective user among said plurality of users, whether said respective user has exceeded said total number of buffers in said address table allocated and, if yes, to prevent said respective user from using any additional buffers in said address table, said third program instructions comprising instructions to send a notification when said respective user has exceeded said total number of buffers in said address table;

wherein said first, second and third program instructions are stored on said computer readable medium.

16. The computer program product according to claim 15, wherein said second program instructions further comprise instructions to maintain for each user of said plurality of users a running tally of said total number of buffers used by said each user in said address table and to keep a running tally of buffers remaining in said shared buffer pool in said address table.

17. The computer program product according to claim 16, wherein said third program instructions further comprise instructions to compare said running tally of said total number of buffers maintained for said respective user to said preset number of buffers allocated to said respective user from said dedicated buffer pool and, if said running tally of said total number of buffers used by said respective user exceeds said preset number of buffers allocated to said respective user from said dedicated buffer pool, to verify that said subset number of buffers in said shared buffer pool has not been exhausted before allowing said respective user to borrow a buffer from said shared buffer pool for adding said address in said address table.

18. The computer program product according to claim 17, wherein if said running tally of said total number of buffers used by said respective user exceeds said preset number of buffers allocated to said respective user from said dedicated buffer pool and said subset number of buffers in said shared buffer pool has not been exhausted, said third program instructions further comprise instructions to decrease by one said running tally of buffers remaining in said shared buffer pool and to increase by one said running tally of said total number of buffers for said respective user.

19. The computer program product according to claim 18, wherein if said running tally of said total number of buffers for said respective user is less than said total number of buffers allocated to said respective user from said dedicated buffer pool, said third program instructions further comprise instructions to determine to increment by one said running tally of said total number of buffers for said respective user and to add said address to said address table.

20. The computer program product according to claim 19, wherein said third program instructions further comprise instructions to delete a respective address entered in a respective buffer, upon expiration of a respective preset time-to-live value for said respective address entered in said respective buffer in said address table and to return said respective buffer to said shared buffer pool;

wherein a user of said plurality of users comprises at least one of;

a port, a plurality of ports, a virtual local area network (VLAN) and a plurality of virtual local area networks (VLANs); and

wherein said address table comprises a CAM (Content Addressable Memory) table for storing one or more MAC (Media Access Control) addresses.