Shared buffer management mechanism and method using multiple linked lists in a high speed packet switching system

• US 6,363,075 B1
• Filed: 01/23/1998
• Issued: 03/26/2002
• Est. Priority Date: 01/23/1998
• Status: Expired due to Term

• Current Assignee: A10 Networks Incorporated
• Original Assignee: Industrial Technology Research Institute
• Inventors: Fan, Kuo-Yen, Wang, Yao-Tzung, Tseng, Huan-Pin, Huang, Paul, Chang, Tai-Chung
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US09/012,225
• Time in Patent Office: 1,523 Days
• Field of Search: 370/389, 370/390-394, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/428, 370/375, 370/378, 370/379, 370/395, 711/147, 711/153, 711/170, 711/156, 709/213, 709/214, 709/215, 709/216
• US Class Current: 370/412
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A shared memory management mechanism and method for a high-speed network releases network packets efficiently and maintains the requirement of First In First Out. A series of linked lists including a linked list for each output queue and a linked list of used broadcast packets aids a buffer manager in efficiently managing the buffers in the shared memory. The linked lists include a special data format that encodes the broadcast status, links, and whether the next entry in the list is for unicast or broadcast frames. A scanning procedure scans the broadcast status to efficiently release the broadcast frame buffers. A dynamic scanning procedure consumes less bandwidth than the scanning procedure to efficiently release the broadcast frame buffers.

Claims

1. A system for managing the transfer of packets, comprising:

a plurality of ports for receiving and transmitting packets;

a shared memory subdivided into a plurality of buffers including unicast frame buffers and broadcast frame buffers;

a bus interconnecting said shared memory and said plurality of ports;

a linked list of free unicast packet buffers listing each of the unicast frame buffers that are currently free;

a linked list of free broadcast packet buffers listing each of the broadcast frame buffers that are currently free;

an output queue linked list for each of said plurality of ports, wherein each of said output queue linked lists includes a listing of the buffers utilized by the associated port to transmit a packet;

a linked list of used broadcast packet buffers listing all of the broadcast packet buffers currently in use; and

a buffer managed connected to said shared memory and to said plurality of ports via said bus;

said buffer manager accessing said linked list of free unicast packet buffers, said linked list of free broadcast packet buffers, said output queue linked lists and said linked list of used broadcast packet buffers to manage unicast and broadcast packet receiving and transmitting between the plurality of ports such that the packets are kept in a FIFO order.

2. The system for managing the transfer of packets according to claim 1,

said buffer manager accessing said linked list of free unicast packet buffers or the linked list of free broadcast packet buffers to designate a next free buffer before transmitting a packet from a first one of said ports to a second one of said ports, updating the linked list of free broadcast or unicast packet buffers to exclude the designated buffer, and updating the output queue linked list for the first port to include the designated buffer.

3. The system for managing the transfer of packets according to claim 2,

said buffer manager updating the linked list of used broadcast packet buffer to include the designated buffer.

4. The system for managing the transfer of packets according to claim 3,

wherein each entry in the linked list of used broadcast packet buffers includes a field indicating broadcast status.

5. The system for managing the transfer of packets according to claim 4, further comprising:

a scanner for scanning the broadcast status field to determine if an associated broadcast packet buffer can be released,

said buffer manager updating the broadcast status field after transmitting a corresponding broadcast packet;

said buffer manager releasing a broadcast packet buffer based on an output of said scanner.

6. The system for managing the transfer of packets according to claim 5,

said broadcast status field including a number of bits equal to the number of said ports,

said scanner scanning the broadcast status field in the linked list of used broadcast buffers and permitting release of the broadcast buffer if the scanned broadcast status field indicates that all ports have transmitted the broadcast packet.

7. The system for managing the transfer of packets according to claim 6,

said scanner scanning the linked list of used broadcast buffers for a predetermined scanning depth and permitting release of a broadcast buffer if a corresponding one of the scanned broadcast status fields indicates that all ports have transmitted the corresponding broadcast packet.

8. The system for managing the transfer of packets according to claim 7,

said scanner dynamically scanning the linked list of used broadcast buffers once every scanning period.

9. The system for managing the transfer of packets according to claim 8,

said buffer manager dynamically adjusting the scanning period according to results of a current scan by said scanner.

10. The system for managing the transfer of packets according to claim 8,

said buffer manager decreasing the scanning period if a current scan by said scanner finds a broadcast buffer to release.

11. The system for managing the transfer of packets according to claim 10,

said buffer manager maintaining the scanning period above a minimum scanning period value.

12. The system for managing the transfer of packets according to claim 8,

said buffer manager adjusting the scanning period according to results of at least one previous scan step and a current scan by said scanner.

13. The system for managing the transfer of packets according to claim 12,

said buffer manager increasing the scanning period if a current scan and at least one previous scan by said scanner do not find a broadcast buffer to release.

14. The system for managing the transfer of packets according to claim 13,

said buffer manager maintaining the scanning period below a maximum scanning period value.

15. A method of sharing a memory in a packet switching network having a plurality of ports connected to the memory via a bus, the method comprising the steps of:

dividing the memory into a plurality of buffers including unicast frame buffers;

requesting a buffer from a linked list of free unicast buffers;

transmitting the unicast packet from a first port to a second port of the packet switching network by

storing the unicast packet from a first port in the buffer requested in said requesting step, and

receiving the unicast packet from the buffer requested in said requesting step with the second port,

releasing the buffer utilized in said transmitting step; and

updating the linked list of free unicast buffers,

wherein if a broadcast packet is to be transferred;

said dividing step further divides the memory into a plurality of broadcast frame buffers;

said requesting step requests a buffer from a linked list of free broadcast buffers; and

said transmitting step transmits the broadcast packet from a first port to all of the other ports of the packet switching network by

storing the broadcast packet from the first port in the broadcast buffer requested in said requesting step,

updating the linked list of free broadcast buffers,

updating an output queue linked list to include the broadcast buffer utilized in said storing step,

updating a linked list of used broadcast buffers to include the broadcast buffer utilized in said storing step, and

receiving the broadcast packet from the buffer requested in said requesting step with the other ports of the packet switching network.

16. The method according to claim 15,

determining if the broadcast buffer utilized in said transmitting step can be released; and

releasing the broadcast buffer utilized in said transmitting step based on said determining step.

17. The method according to claim 16,

said determining step including a substeps of scanning a broadcast status field in the linked list of used broadcast buffers and permitting release of the broadcast buffer if the scanned broadcast status field indicates that all ports have transmitted the broadcast packet.

18. The method according to claim 17,

said scanning substep scanning the linked list of used broadcast buffers for a predetermined scanning depth,

said permitting step permitting release of a broadcast buffer if a corresponding one the scanned broadcast status fields indicates that all ports have transmitted the corresponding broadcast packet.

19. The method according to claim 17,

said scanning substep dynamically scanning the linked list of used broadcast buffers once every scanning period.

20. The method according to claim 19, further comprising the steps of:

adjusting the scanning period according to results of a current scanning step.

21. The method according to claim 20,

said adjusting step decreasing the scanning period if a current scanning step finds a broadcast buffer to release.

22. The method according to claim 21, further comprising the step of:

maintaining the scanning period above a minimum scanning period value.

23. The method according to claim 19, further comprising the steps of:

adjusting the scanning period according to results of at least one previous scanning step and a current scanning step.

24. The method according to claim 23,

said adjusting step increasing the scanning period if a current scanning step and at least one previous scanning step do not find a broadcast buffer to release.

25. The method according to claim 24, further comprising the step of:

maintaining the scanning period below a maximum scanning period value.

26. In a packet switching network having a plurality of ports and a shared memory subdivided into a plurality of unicast packet buffers and broadcast packet buffers, a data structure for sharing the memory, comprising:

a linked list of free unicast packet buffers wherein each entry includes a link to a next available unicast packet buffer in the shared memory;

a linked list of free broadcast packet buffers wherein each entry includes a link to a next, available broadcast packet buffer in the shared memory;

a linked list for each output queue wherein each entry in each linked list for output queue includes a next buffer pointer pointing to a next buffer in the linked list for output queue and a field indicating whether the next buffer is a broadcast or unicast packet buffer; and

a linked list of used broadcast packet buffers wherein each entry includes a link to a next used broadcast packet buffer.

27. The packet switching network having the plurality of ports and the shared memory subdivided into the plurality of unicast packet buffers and broadcast packet buffers and the data structure according to claim 26, wherein for broadcast packets,

each entry in each linked list for output queue further includes a field indicating broadcast status, and a plurality of fields having a first subfield pointing to a next buffer for port #i and a second subfield indicating whether the next buffer for port #i is a broadcast or unicast packet buffer.

28. The packet switching network having the plurality of ports and the shared memory subdivided into the plurality of unicast packet buffers and broadcast packet buffers and the data structure according to claim 26,

wherein each entry in the linked list of used broadcast packet buffers includes a field indicating broadcast status.

29. The packet switching network having the plurality of ports and the shared memory subdivided into the plurality of unicast packet buffers and broadcast packet buffers and the data structure according to claim 28, said broadcast status field indicating a number of bits equal to the number of ports.