Method, system and program product for equitable sharing of a CAM table in a network switch in an on-demand environment

• US 7,711,900 B2
• Filed: 03/05/2007
• Issued: 05/04/2010
• Est. Priority Date: 03/05/2007
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Booth, Bruce, Goodgion, Mark E., Zaghloul, Atef O., Zeiger, John H.
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US11/681,820
• Publication Number:
  US 20080222352A1
• Time in Patent Office: 1,156 Days
• Field of Search: 711129-131, 711/221, 709213-215, 709/232
• US Class Current: 711/130
• 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:

a processor of a computer system reserving a preset number of dedicated buffers for a respective user of the plurality of users and a subset number of shared buffers for all of said users in an address table in said network switch, said network switch comprising a plurality of ports, each port having a designated port number, said subset number of shared buffers forming a shared buffer pool for all of said users and said preset number of dedicated buffers in forming a dedicated buffer pool for said respective user, each shared buffer and each dedicated buffer in the address table configured to store a port number of a port of the plurality of ports and an associated address such that the network switch is configured to forward a packet received by the network switch to the port whose associated address in a buffer in the address table matches a destination address in the received packet;

said processor establishing, upon arrival at the network switch of a packet containing a destination address corresponding to said respective user, that said destination address is not listed in any buffer in said address table;

in response to said establishing, said processor determining whether or not an in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user

if said processor determines that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user, then adding the destination address in the packet and an associated port of the plurality of ports to an unallocated dedicated buffer in said dedicated buffer pool;

if said processor determines that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user, then either;

said processor determining that said subset number of buffers in said shared buffer pool is exhausted and sending to a network manager or an administrator a notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and not adding the destination address in the packet to any shared buffer in the shared buffer pool;

or

said processor determining that said subset number of buffers in said shared buffer pool is not exhausted and adding the destination address in the packet and an associated port of the plurality of ports to an unallocated shared buffer in said shared buffer pool.

2. The method of claim 1, wherein each user is a virtual local area network (VLAN) or a plurality of virtual local area networks (VLANs), and wherein said address table consists of a CAM (Content Addressable Memory) table for storing one or more MAC (Media Access Control) addresses.

3. The method of claim 1, wherein said processor determines that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user.

4. The method of claim 3, wherein the method comprises said processor incrementing by one a user-specific buffer counter that stores a count of said in-use number of said buffers being used by said respective user.

5. The method of claim 1, wherein said processor determines that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user.

6. The method of claim 5, wherein said processor determines that said subset number of buffers in said shared buffer pool is exhausted and sends to said network manager or said administrator said notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and does not add the destination address in the packet to any shared buffer in the shared buffer pool.

7. The method of claim 5, wherein said processor determines that said subset number of buffers in said shared buffer pool is not exhausted and adds the destination address in the packet and an associated port of the plurality of ports to said unallocated shared buffer in said shared buffer pool and decrements by one said shared buffer counter that stores said count of said number of buffers in said shared buffer pool that is not exhausted.

8. The method of claim 7, wherein the method comprises said processor decrementing by one a shared buffer counter that stores a count of a number of buffers in said shared buffer pool that is not exhausted.

9. A computer program product for equitable sharing of buffers between a plurality of users of a network switch, said computer program product comprising:

a computer readable storage medium;

first program instructions to reserve a preset number of dedicated buffers for a respective user of the plurality of users and a subset number of shared buffers for all of said users in an address table in said network switch, said network switch comprising a plurality of ports, each port having a designated port number, said subset number of shared buffers forming a shared buffer pool for all of said users and said preset number of dedicated buffers forming a dedicated buffer pool for said respective user, each shared buffer and each dedicated buffer in the address table configured to store a port number of a port of the plurality of ports and an associated address such that the network switch is configured to forward a packet received by the network switch to the port whose associated address in a buffer in the address table matches a destination address in the received packet;

second program instructions to establish, upon arrival at the network switch of a packet containing a destination address corresponding to said respective user, that said destination address is not listed in any buffer in said address table;

third program instructions to, in response to said second program instructions establishing that said destination address is not listed in any buffer in said address table, determine whether or not an in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user;

fourth program instructions to, if said third program instructions determines that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user, add the destination address in the packet and an associated port of the plurality of ports to an unallocated dedicated buffer in said dedicated buffer pool;

fifth program instructions, if said third program instructions determines that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user, to either;

determine that said subset number of buffers in said shared buffer pool is exhausted and send to a network manager or an administrator a notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and not add the destination address in the packet to any shared buffer in the shared buffer pool;

or

determine that said subset number of buffers in said shared buffer pool is not exhausted and add the destination address in the packet and an associated port of the plurality of ports to an unallocated shared buffer in said shared buffer pool,

wherein the first program instructions, the second program instructions, the third program instructions, the fourth program instructions, and the fifth program instructions are stored on the computer readable storage medium for execution by a processor of a computer system via a computer readable memory of the computer system.

10. The computer program product of claim 9, wherein said third program instructions determine that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user.

11. The computer program product of claim 10, wherein said third program instructions increment by one a user-specific buffer counter that stores a count of said in-use number of said buffers being used by said respective user.

12. The computer program product of claim 9, wherein said third program instructions determine that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user.

13. The computer program product of claim 12, wherein said fifth program instructions determine that said subset number of buffers in said shared buffer pool is exhausted and sends to said network manager or said administrator said notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and does not add the destination address in the packet to any shared buffer in the shared buffer pool.

14. The computer program product of claim 12, wherein said fifth program instructions determine that said subset number of buffers in said shared buffer pool is not exhausted and adds the destination address in the packet and an associated port of the plurality of ports to said unallocated shared buffer in said shared buffer pool and decrements by one said shared buffer counter that stores said count of said number of buffers in said shared buffer pool that is not exhausted.

15. The computer program product of claim 14, wherein said fifth program instructions decrement by one a shared buffer counter that stores a count of a number of buffers in said shared buffer pool that is not exhausted.

16. A computer system for equitable sharing of buffers between a plurality of users of a network switch, said computer system comprising:

a processor;

a computer readable memory;

a computer readable storage medium;

first program instructions to reserve a preset number of dedicated buffers for a respective user of the plurality of users and a subset number of shared buffers for all of said users in an address table in said network switch, said network switch comprising a plurality of ports, each port having a designated port number, said subset number of shared buffers forming a shared buffer pool for all of said users and said preset number of dedicated buffers forming a dedicated buffer pool for said respective user, each shared buffer and each dedicated buffer in the address table configured to store a port number of a port of the plurality of ports and an associated address such that the network switch is configured to forward a packet received by the network switch to the port whose associated address in a buffer in the address table matches a destination address in the received packet;

second program instructions to establish, upon arrival at the network switch of a packet containing a destination address corresponding to said respective user, that said destination address is not listed in any buffer in said address table;

third program instructions to, in response to said second program instructions establishing that said destination address is not listed in any buffer in said address table, determine whether or not an in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user;

fourth program instructions to, if said third program instructions determines that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user, add the destination address in the packet and an associated port of the plurality of ports to an unallocated dedicated buffer in said dedicated buffer pool;

fifth program instructions, if said third program instructions determines that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user, to either;

determine that said subset number of buffers in said shared buffer pool is exhausted and send to a network manager or an administrator a notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and not add the destination address in the packet to any shared buffer in the shared buffer pool;

or

determine that said subset number of buffers in said shared buffer pool is not exhausted and add the destination address in the packet and an associated port of the plurality of ports to an unallocated shared buffer in said shared buffer pool,

wherein the first program instructions, the second program instructions, the third program instructions, the fourth program instructions, and the fifth program instructions are stored on the computer readable storage medium for execution by the processor via the computer readable memory.

17. The computer system of claim 16, wherein said third program instructions determine that said in-use number of said dedicated buffers being used by said respective user is less than said preset number of dedicated buffers allocated to said respective user.

18. The computer system of claim 16, wherein said third program instructions determine that said in-use number of said dedicated buffers being used by said respective user is not less than said preset number of dedicated buffers allocated to said respective user.

19. The computer system of claim 18, wherein said fifth program instructions determine that said subset number of buffers in said shared buffer pool is exhausted and sends to said network manager or said administrator said notification bit denoting that said subset number of buffers in said shared buffer pool is exhausted and does not add the destination address in the packet to any shared buffer in the shared buffer pool.

20. The computer system of claim 18, wherein said fifth program instructions determine that said subset number of buffers in said shared buffer pool is not exhausted and adds the destination address in the packet and an associated port of the plurality of ports to said unallocated shared buffer in said shared buffer pool and decrements by one said shared buffer counter that stores said count of said number of buffers in said shared buffer pool that is not exhausted.