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.

Description:
BACKGROUND OF THE INVENTION 
     1. Technical Field of the Invention 
     This invention generally relates to managing multi-port access to a shared memory in a packet switching system. More particularly, this invention relates to a mechanism for sharing a memory of a packet switching system using multiple linked lists. The invention also relates to a multiple linked list data structure for efficiently sharing a memory in a packet switching network. 
     2. Description of Related Art 
     Recently, internetworking technology has been developing at a rapid pace. The problems of internetworking traffic which include data transfer bottlenecks are increasing which causes a concomitant reduction in the internetworking service quality. To overcome the data transfer bottleneck, various approaches have been taken to speed up the rate of communications and to increase the speed of processing data. 
     One such approach is disclosed in the Heddes et al. patent (U.S. Pat. No. 5,432,908) that issued on Jul. 11, 1995. Heddes et al. disclose a buffer management technique that utilizes a buffer manager that includes a request manager, a stack manager and a first-in/first-out manager (FIFO manager). 
     Heddes et al. grant a buffer request by accessing a free buffer linked list stored in a buffer control record (BCR) memory. Allocated buffers are kept in different logical queues, one for each user, by adding its BCR to a FIFO linked list. The FIFO manager then manages the allocated buffers during packet receiving and transmitting. 
     Heddes et al. does not, however, disclose a technique for handling multicast or broadcast packets wherein a packet is transmitted from one user to a group of users (multicast) or to all other users (broadcast). 
     Heddes et al. also does not efficiently release or relinquish buffers which are no longer being used especially for broadcast or multicast packet buffers. 
     OBJECTS AND SUMMARY OF THE INVENTION 
     As mentioned above, there are three types of packets (unicast, multicast, and broadcast) in the network system. The system must manage the sending and receiving of these types of data between the network ports efficiently while increasing the utilization of the memory and reducing data loss. The present invention provides a method to achieve these requirements. 
     In the shared memory of the data switch networking system, to implement software protocol and to utilize the goals of high speed data switching, there are two primary issues that are considered by the invention: 
     (1) After the unicast or broadcast packet has been processed, the invention must retain the order in which it was received. In short, the packets received by port #i must be kept in the same order when they are transmitted to the port #j. 
     (2) When the broadcast packets are stored in the shared memory, the system is able to manage the shared memory effectively. In short, the invention configures and releases the broadcast packet buffer quickly. 
     It is an object of the present invention to provide a high efficiency data switch in a high-speed network system, and at the same time, keeping it economical and available. 
     It is another object of the present invention to efficiently manage a shared memory in a packet switching network for multicast and broadcast packets as well as unicast packets. 
     It is yet another object of the invention to provide a data structure for linked lists that aids in the management of a shared memory. 
     It is still another object of the present invention to efficiently release a buffer after use and prevent a delayed release. 
     It is still yet another object of the present invention to provide a dynamic method of releasing buffers in an efficient manner. 
     To achieve the above objects, the present invention provides a data switching network system having a shared memory for managing the transfer of packets, including 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 the shared memory and the plurality of ports; a linked list of free unicast packets listing each of the unicast frame buffers that are currently free; a linked list of free broadcast packets 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 the 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 packets listing all of the broadcast packet buffers currently in use; and a buffer manager connected to the shared memory and to the plurality of ports via the bus; the buffer manager accessing the linked list of free unicast packets, the linked list of free broadcast packets, the output queue linked lists and the linked list of used broadcast packets to manage unicast and broadcast packet receiving and transmitting between the plurality of ports such that the packets are kept in a FIFO order. 
     To further achieve these objects, the invention discloses a method of sharing a memory in a packet switching network having a plurality of ports connected to the memory via a bus, including 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 the first port in the buffer requested in the requesting step, and receiving the unicast packet from the buffer requested in the requesting step with the second port; releasing the buffer utilized in the transmitting step; and updating the linked list of free unicast buffers. 
     To still further achieve these objects, the invention discloses a method which further includes the steps 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. 
     To still further achieve the objects of the invention, the scanning step may scan the linked list of used broadcast buffers once every scanning period and dynamically adjust the scanning period according to present and/or past scanning results. 
     Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description. 
    
    
     BRIEF DESCRIPTION OF DRAWINGS 
     The present invention will become more fully understood from the detailed description given hereinbelow and the accompanying drawings which are given by way of illustration only, and thus are not limitative of the present invention, and wherein: 
     FIG. 1 is a block diagram of a shared buffer system according to the invention; 
     FIG. 2 is a diagram illustrating the relationship between a linked list for output queue of port #j, a linked list of used broadcast frame buffers, and a linked list for output queue of port #i according to the invention; 
     FIG. 3 is an example of port #i receiving (RX) a frame and linking to port #j including a linked list of used broadcast frame buffers and a linked list for output queue of port #j according to the invention; 
     FIG.  4 ( a ) is an example of port #i receiving (RX) a frame and linking to port #j including inserting a unicast frame buffer to the linked list for output queue of port #j and illustrating the associated linked list of used broadcast frame buffers according to the invention; 
     FIG.  4 ( b ) is an example of port #i receiving (RX) a frame and linking to port #j including inserting a broadcast frame buffer to the linked list for output queue of port #j and illustrating the associated linked list of used broadcast frame buffers according to the invention; 
     FIG. 5 is an example of port #i transmitting (TX) a unicast frame and including a before and after illustration of the linked list of used broadcast frame buffers and the linked list for output queue of port #i before and after a unicast frame buffer is released according to the invention; 
     FIG. 6 is an example of the invention illustrating port #i transmitting (TX) a broadcast frame and including a before and after illustration of the linked list of used broadcast frame buffers and the linked list for output queue of port #i before and after the broadcast frame buffer is released; 
     FIG. 7 is continuation of the example shown in FIG. 6 after the broadcast frame buffer is released according to the invention; 
     FIG. 8 is a data structure format of linked lists for unicast frame buffers and broadcast frame buffers according to the invention; 
     FIG. 9 is an example of a data structure format of linked lists including unicast and broadcast frame buffers entries according to the invention; 
     FIG. 10 is a high-level flowchart describing the receiving and transmitting of a unicast frame according to the invention; 
     FIG. 11 is a high-level flowchart describing the receiving and transmitting of a broadcast frame according to the invention; 
     FIG. 12 illustrates the phenomenon of delayed release of a broadcast frame buffer using a time-sequence of three drawings; 
     FIG. 13 illustrates the release of a broadcast frame buffer by scanning the buffer according to the invention; 
     FIG. 14 is a high-level flowchart illustrating the scanning range procedure according to the invention; 
     FIG. 15 is a high-level flowchart illustrating the dynamic scanning range procedure according to the invention; and 
     FIGS.  16 ( a )-( c ) illustrate an example of the dynamic scanning range procedure according to the invention. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     FIG. 1 illustrates a computer system including an data bus  120  interconnecting a shared buffer memory  110  and a plurality of ports  130 ,  132 ,  134  (also labelled port # 1 , port # 2  . . . port #n). A control signal bus  125  interconnects a buffer manager  100  and the plurality of ports  130 ,  132 ,  134 . The buffer manager  100  is also connected to the shared buffer memory  110 . 
     The shared buffer memory  110  is subdivided, physically and/or virtually, into a plurality of packet buffers. As further described below, each packet buffer may store a packet containing frame data  360  and header data ( 305  or  355 ). 
     As known in the art, the ports  130 ,  132  and  134  communicate with each other and with the shared buffer memory  110  using packets which may be unicast, multicast or broadcast packets. 
     This detailed description primarily refers to broadcast packs to explain the elements and operations of the present invention. It should be understood that these explanations also apply to multicast packets because these two types of packets are similar. 
     To efficiently and effectively manage packet transfer and the shared buffer memory  110 , the buffer manager  100  utilizes multiple linked lists. Before describing the operation of the present invention, the four types of linked lists used by the invention are introduced as follows: 
     (1) The linked list of free unicast packet buffers will be referred to as the linked list of free unicast packets. The linked list of free unicast packets keeps track of which unicast packet buffers are unused so that the system can efficiently locate and manage free unicast packet buffers. 
     (2) The linked list of free broadcast packet buffers will be referred to as the linked list of free broadcast packets. The linked list of free broadcast packets keeps track of which broadcast packets buffers are unused so that the system can efficiently locate and manage free broadcast packet buffers. 
     (3) The set of linked lists, one for each output queue, will be referred to as the linked list for output queue. When referring to an output queue for port #i, the nomenclature used will be the linked list for output queue of port #i. The linked list for output queue of port #i keeps track of each output packet sent from port #i and is used to maintain FIFO packet order. 
     (4) The linked list of used broadcast packet buffers will be referred to as the linked list of used broadcast packets. The linked list of used broadcast packets is used by the invention to keep track of which broadcast packet buffers are currently being used and to efficiently release or relinquish such used broadcast packet buffers when they are no longer needed. 
     In general, when a network port (eg. port  130 ) receives a packet, port  130  requests a buffer from the linked list of free unicast packets or the linked list of free broadcast packets by sending a signal to the buffer manger  100  via control signal bus  125 . Once granted a free packet buffer, the port  130  then stores the packet in the designated buffer. 
     After the packet has been stored into the designated buffer, the buffer manager  100  adds an entry to the linked list of output queue for port  130  to refer to the designated buffer and removes the entry for the designated buffer from linked list of free unicast (or broadcast) packets. 
     If the packet is a broadcast packet, then the buffer manager  100  also adds an entry to the linked list of used broadcast packets  220  to refer to the designated buffer. As further described below, the linked list of used broadcast packets  220  is used to efficiently process the release of broadcast buffers. 
     FIG. 2 describes the relationship between the linked list for output queue  200  and the linked list of used broadcast packets  220 . More particularly, FIG. 2 describes the relationship between the linked list for output queue  200  of port #j, the linked list of used broadcast frame buffers  220 , and the linked list for output queue  200  of port #i. 
     In FIG. 2, “B 1 ” indicates a first broadcast frame buffer; “B 2 ” indicates a second broadcast frame buffer; “Uj 1 ” indicates a first unicast frame buffer for port #j; “Ui 2 ” indicates a second unicast frame buffer for port # 1 , etc. 
     On the left side of FIG. 2, the linked list for output queue  200  of port #j includes a first broadcast frame buffer B 1  which is linked to a first unicast frame buffer for port #j (Uj 1 ) which, in turn, is linked to a second broadcast frame buffer B 2  which, in turn, is linked to a second unicast frame buffer for port #j (Uj 2 ), which, in turn, is linked to a third broadcast frame buffer B 3  which , in turn, is linked to a third unicast frame buffer for port #j (Uj 3 ), etc. 
     On the right side of FIG. 2, the linked list for output queue  240  of port #i includes a first unicast frame buffer for port #i (Ui 1 ) which is linked to the second broadcast frame buffer B 2  which, in turn, is linked to the third broadcast frame buffer B 3  which, in turn, is linked to a second unicast frame buffer for port #i (Ui 2 ), which, in turn, is linked to a third unicast frame buffer for port #i (Ui 3 ), etc. 
     The left and right sides of FIG. 2, showing the linked list for output queue  200  of port #j and the linked list for output queue  240  of port #i, are related to the used broadcast frame buffers  220  shown in portion C of FIG. 2 (between the “=” signs). As shown, the linked list of used broadcast frame buffers  220  includes a first broadcast frame buffer B 1  having a link to unicast frame buffer Uj 1  which, in turn is linked to broadcast frame buffer B 2 . 
     As further shown in section C of FIG. 2, the first broadcast frame buffer B 1  is also linked to the second used broadcast frame buffer B 2  which, in turn, is linked to unicast frame buffer Uj 2  and to the third used broadcast frame buffer B 3 . 
     Also, the unicast frame buffer Ui 1  is linked to used broadcast frame buffer B 2  and unicast frame buffer Uj 2  is linked to broadcast frame buffer B 3 . In addition broadcast frame buffer B 3  is linked to unicast frame buffer Ui 2 . 
     FIG. 3 illustrates an example describing how to establish the relationship between the linked lists shown in FIG.  2 . More particularly, FIG. 3 further describes the relationship between the linked list of used broadcast frame buffers  220  and the linked list for output queue  200  of port #j. 
     The linked list of used broadcast frame buffers  220  shown in FIG. 3 includes broadcast frame buffer  222  linked to broadcast frame buffer  224  which, in turn, is linked to broadcast frame buffer  226 . 
     The linked list for output queue  200  of port #j shown in FIG. 3 includes frame buffer  202  linked to broadcast frame buffer  224  which indicates that the packet from port #j to port #i was sent via broadcast frame buffer  224 . Broadcast frame buffer  226  also has a link to frame buffer  204  in the linked list of output queue  200  for port #j which is the next frame buffer of the output queue  200  of port #j. 
     In FIG. 4, suppose that when port #i receives a unicast packet, it then requests a buffer from the linked list of free unicast packets to store the received packet. At the same time, port #i determines the destination port for the unicast packet (suppose port #j). Then, the packet requires entrance to the destination port #j. 
     FIG.  4 ( a ) illustrates inserting a unicast frame buffer to the linked list for output queue for port #j. More particularly, FIG.  4 ( a ) illustrates inserting unicast frame buffer  206  into the linked list for output queue  200  of port #j (the destination port) including a link from frame buffer  204 . 
     According to the same principle illustrated in FIG.  4 ( a ), if port #k receives a broadcast packet, then it requests a buffer from the linked list of free broadcast packets for storage. Then, the broadcast packet requires entrance to the destination port and the linked list of used broadcast packets  220 . 
     FIG.  4 ( b ) illustrates inserting a broadcast frame buffer after port #i receives a broadcast packet. More particularly, FIG.  4 ( b ) illustrates inserting broadcast frame buffer  228  into the linked list of used broadcast frame buffers  220 , adding frame buffer  208  to the linked list for output queue  200  of port #j, and creating a link from frame buffer  208  of the linked list for output queue  200  of port #j (the destination port) to broadcast frame buffer  228 . 
     The major difference between the process illustrated in FIG.  4 ( b ) for inserting a broadcast frame buffer into the linked list of used broadcast frame buffers  220  and inserting the buffer for unicast packets in FIG.  4 ( a ) is that the invention not only puts the buffer into linked list for output queue  200 , but also puts the buffer into the linked list of used broadcast packets  220 . 
     Buffer Release Mechanism and Procedure 
     The present invention includes unique and efficient strategies for releasing or relinquishing used unicast and broadcast frame buffers. These strategies release portions of the shared memory by processing the packets with a series of linked lists. 
     The simplest release mechanism is for releasing unicast packet buffers. After the first packet (unicast) in the linked list for output packets has been transmitted successfully, the invention releases the buffer immediately and puts an indication of the released buffer into the linked list of free unicast packets, as shown in FIG.  5 . Then, continue to transmit the next packets (broadcast). 
     More particularly, FIG. 5 includes a before and after illustration of the inventive linked lists before an after the release of a unicast frame buffer. In the “before” illustration, the head pointer (ptr)  410  points to the beginning address of frame buffer  242 . In other words, the head pointer  410  is used to point to the first frame buffer of output queue  200  of port #i. Immediately after transmission of unicast frame buffer, and as shown in the “after” illustration, the unicast frame buffer  242  is released by moving the head pointer  410  to frame buffer  224 . 
     The broadcast buffers must be released after all of the packets in all of the ports have been transmitted. To keep track of this information, the invention utilizes a broadcast status (BS) in the linked list data structure. The BS is used to indicate which ports have finished transmitting the packet and has a word length equal to the number of ports  130 ,  132 ,  134  in the system. If there are a large number of ports, then multiple words can be used for BS. 
     In general, the invention sets a bit in the BS to a designated value (eg. one) after the corresponding port has finished transmitting the packet. When all of the bits of BS have been set to the designated value, then the system is finished transmitting the packet to all of the ports  130 ,  132 ,  134 . 
     Although the broadcast buffers have been moved out from each linked list for output queue, the broadcast buffers still stay in the linked list of used broadcast packets for a while until they are identifies by the inventive scanning process. 
     FIG.  6  and FIG. 7 illustrate releasing a broadcast frame buffer according to the invention. More particularly, FIG. 6 shows a before and after illustration before and after the broadcast buffer is released. 
     As diagrammatically shown in FIG. 6, the invention utilizes scanner  400  of buffer manager  100  to scan the broadcast status associated with each broadcast frame buffer (scanner.bs). The i-th bit position of scanner.bs indicates whether the i-th port has transmitted the associated broadcast packet. In the “before” illustration of FIG. 6, the i-th port has not yet finished transmitting broadcast frame buffer  224  as indicated by the “0” stored in the i-th bit position of scanner.bs. 
     After transmitting, the scanner  400  again checks the scanner.bs field of frame buffer  224 . Because the i-th port was the last of the ports  130 ,  132 ,  134  to transmit the broadcast frame buffer, when port #i completes the transmission and updates the i-th position of scanner.bs accordingly then the broadcast frame buffer  224  can be released from the linked list of used broadcast frame buffers  220 . 
     This completion is identified by scanner  400  in the “after” illustration of FIG. 6 which shows the i-th position of scanner.bs updated to “1” as scanned by scanner  400 . The release of broadcast frame buffer  224  is accomplished by updating the head pointer  410  to point to the address of the next frame buffer (buffer  226 ) in the linked list of used broadcast frame buffers  220 . 
     FIG. 7 shows the final step of releasing the broadcast frame buffer which includes updating the scanner  400  so as to point to the next frame buffer (buffer  226 ) in the linked list of used broadcast frame buffers  220 . 
     If the BS receives the message that all output ports have transmitted the data stored in the buffers to the network, then release the buffer. Otherwise, the scanner  400  will point to the next frame buffer. So, in FIG. 5, when a used unicast frame buffer (that is pointed by head pointer) is transmitted to the network, then, the head pointer points to the next frame buffer. When the output queue #i transmits the frame buffer (that is pointed by head pointer) to the network, the output queue #i will set the BS of the broadcast frame buffer  224  to 1 (as shown in FIG.  6 ). After that, the scanner  400  will check the BS from time to time, if all the relative BSs of the output ports are set to 1, then, release the frame buffer, otherwise, the scanner will point to the next used broadcast frame buffer (as shown in FIG.  7 ). 
     In short, the present invention uses a centralized scheme controlled by buffer manager  100  to release the buffers no longer used by broadcast packets. Hence, the invention reduces the complexity of the system and reduces the size of the circuits used to implement the invention. 
     In rare cases, there are few buffers that are not in use and cannot be used by the ports  130 ,  132 ,  134 . As long as the implementation supplies enough buffers and controls the scan range properly, the problem can be reduced to a minimum. 
     According to the description in the previous sections, when the packets (broadcast or multicast) have been received, as long as the initial broadcast status is set properly, the method provided by the present invention can release the buffers. In other words, when processing the broadcast packets, as long as the initial broadcast status that corresponds to the receiving ports is one, the rest should be zero. 
     When processing multicast packets, the invention sets the initial broadcast status corresponding to the ports that are not transmittable (or otherwise not included in the group of ports being sent the multicast packet) to one. After that, the operations will be the same as broadcast packet transfer and subsequent buffer release. 
     Data Format of Linked Lists 
     As mentioned above, the invention utilizes a series of linked lists to manage packet transfer and buffer release. FIG. 8 illustrates the preferred data format of linked lists according to the invention. 
     More particularly, FIG. 8 shows the data structure format of linked lists for unicast and broadcast frame buffers. The data structure format  300  of linked lists for unicast buffers includes a header data field  305  and a frame data field  360 . The header data field includes an NUB field that is a binary indication of whether the next frame buffer in the linked list is a unicast or broadcast and an NPtr field that is a pointer to the next frame buffer in the linked list. 
     The data structure format  350  of linked lists for broadcast frame buffers  350 , as shown in FIG. 8, includes a header data field  355  and a frame data field  360 . The header data field  355  includes a BS (broadcast status) field, an NPtr field that is a pointer to the next frame buffer in the linked list, and n additional fields where n is equal to the number of ports  130 ,  132 ,  134 . The n additional fields each have an NUBi subfield that is a binary indication of whether the next frame buffer in port #i is unicast or broadcast and an NPtri field that is a pointer to the next frame buffer of port #i in the linked list. 
     FIG. 9 illustrates an example of a linked list for output queue that utilizes the data structure of FIG.  8 . Because the NUB of the first buffer  300 A is zero, the next buffer  350 A in the linked list is for storing broadcast packets. The location of the next buffer  350 A is stored in the NPtr field of the first buffer  300 A. 
     As further shown for the second buffer  350 A in the linked list, for the port # 1 , NUB 1  is zero, so that the next buffer  350 B in the linked list for output queue is a broadcast buffer. The address of the next buffer  350 B is stored in the NPtr 1  associated with NUB 1  as indicated by the link connecting NPtrl and the next buffer  350 B 
     The NUB 1  for the next buffer  350 B is one, which indicates that the following buffer  300 B is for storing a unicast packet and so on. 
     In summary, FIG.  10  and FIG. 11 are used to describe how the received packets in the system are transmitted to the destination port. FIG. 10 shows the operational flowchart for the unicast packet in the system and FIG. 11 shows the operational flowchart for the broadcast packet in the system. 
     As shown in FIG. 10, the typical transmission of a unicast packet begins with a request for a free unicast frame buffer from port #i. The unicast buffer management section  102  of buffer manager  100  acknowledges the request and sets UPtr (pointer of unicast frame buffer) to the head pointer and head=head.NPtr. 
     The following identifies the variables utilized in FIGS. 10 and 11. 
     head: head pointer of linked list 
     tail: tail pointer of linked list 
     head NPtr: next buffer pointer of head 
     tail NPtr: next buffer pointer of tail 
     In FIGS. 10 and 11, if port #i ( 136 ) didn&#39;t receive the frame, port #i will request the unicast buffer manager ( 102 ) and broadcast buffer manager ( 104 ) to give the frame buffer individually. 
     As illustrated in FIG. 10, when port #i ( 136 ) receives unicast data, use UPtr to write the receiving data to frame buffer sequentially. Then, give this pointer of the frame buffer to the destination port #j ( 138 ). The output queue #j ( 138 ) will link this pointer to the tail of the output queue port #j ( 138 ) and will read the data from the frame buffer pointed by head pointer. When the transmission is done, if the frame buffer pointed by head pointer is a unicast frame buffer, port #j ( 138 ) will give this pointer to unicast buffer management ( 102 ) and then link it to tail of “free unicast frame buffer.” That is, to release unicast frame buffer to unicast buffer manager ( 102 ). This is shown in FIG.  10 . 
     Whereas, the frame buffer, port #j ( 138 ) will let RPtr.BSj=1 (RPtr.BSj is the BS of the frame buffer pointed by RPtr). The used broadcast buffer ( 220 ) will check the BS of broadcast frame buffer periodically. If BS is all ones, used broadcast buffer ( 220 ) will give this pointer to broadcast buffer management  104  and release it. Then, the scanner  400  will point to the next used broadcast frame buffer. This is shown in FIG.  11 . 
     There is a problem that needs to be solved when receiving and transmitting broadcast packets. FIG. 12 describes the problem. To better understand the problem, suppose there are three ports in the system as indicated by the three bit positions in the broadcast status for the frame buffer (FB.BS). At the time of T 0 , port # 1  and port # 2  receive the packets individually and the broadcast status (FB.BS) is shown in the left part of the figure for each packet. 
     At the time T 1 , port # 3  sends the first broadcast packet, and port # 1  sends the second broadcast packet. The broadcast status for each of the broadcast packets is set to one, as shown in the middle of FIG. 12 under T 1 . 
     Then at the time T 2 , suppose that port # 2  is busy, therefore, the first packet cannot be transmitted. Port # 3 , however, is not busy and transmits the second packet successfully as shown in the right of FIG. 12 under T 2 . Then, the buffer used by the second packet can be released. 
     However, if the scanner  400  only checks the broadcast status for the first packet in the linked list of used broadcast buffers, the disadvantageous situation as shown in FIG. 12 occurs. The buffer for the second packet which has been successfully transmitted by all ports (FB.BS=111) should be released, but it is not. This failure to release a broadcast buffer reduces the utilization of the shared memory  110 . 
     In order to overcome this problem, the present invention uses a scanning method to scan the broadcast status for each packet to determine if it is necessary to release the associated buffer or not. 
     As shown in FIG. 13, the scanning method utilizes a scan range for scanner  400  which is from the beginning of the linked list to a given depth within the list. Then, it returns, as shows in FIGS. 13 and 14. The reason the scanning method proceeds in this fashion is that most of packets that are received early will be transmitted first. Thus, the invention only scans the part in the front of the list to find the buffers ready for release and then releases that buffer. 
     FIG. 14 utilizes the following variables to describe the scanning range procedure: 
     max_depth: maximum scanning depth. That is, in the “used broadcast frame buffer” linked list. The scanning range is from head pointer to max_depth. 
     In Step S 520 , the symbol != should be interpreted as ≠ 
     Scanner NPtr: the next frame buffer pointer of the scanner. 
     Because of the phenomenon of delayed release shown in FIG. 12, the invention utilizes the scanning range procedure shown in FIG. 14 to solve this problem. Whereas, if all the frame buffers are scanned, it is not efficient in memory bandwidth. Therefore, the invention scans a range of the “used broadcast frame buffer” from the head pointer the max_depth. When the scanner reaches max_depth or tail pointer, the scanner will return to head pointer. FIG. 14 further illustrates an exemplary method for this process. 
     More particularly, the scanning range procedure illustrated in FIG. 14 begins with Step S 500  wherein the scanning depth is set to zero and the variable scanner is set to the head of the linked list. Then, step S 510  scans the broadcast status as indicated by check scanner.BS. Thereafter, decision step S 520  checks whether the depth is less than the maximum depth and whether the scanner is not equal to the tail address of the linked list. If yes, step S 530  updates the variable scanner so as to permit scanning of the next entry in the list and also increases the depth of the scan. If the answer to decision step  520  is no, then step S 540  is performed which resets the variable scanner back to the head address of the list and which resets the scanning depth to zero. After either steps  530  or  540 , then the method loops back to step S 510  which is described above. 
     Dynamic Scan of Broadcast Status 
     Although the scanning procedure shown in FIG. 13 and 14 is simple and easy to implement, it consumes valuable bandwidth for accessing the shared memory  110 . In other words, each access to shared memory  110  to scan the broadcast status consumes valuable bandwidth. 
     Therefore, the invention also seeks to reduce the number of unnecessary scans as much as possible. To accomplish this goal, the present invention provides a dynamic scanning procedure as shown in FIG.  15 . 
     In short, the dynamic scanning procedure dynamically adjusts the scan period according to the following rules: (1) when the dynamic scanning procedure does not find a buffer to release after scanning twice, it doubles the scan period and (2) when a buffer is found which is ready to release, the scan period is halved. By using a dynamic scanning procedure, the invention increases the bandwidth utilization of the memory. 
     FIG. 15 illustrates an implementation of the dynamic scanning procedure using a flow chart and pseudo code. In step S 600 , the scanning period (sp) is set to an initial scan period (init_sp). 
     Step S 610 , follows step S 600  and waits for the scanning period before proceeding to step S 620 . 
     Step S 620  tests whether the next buffer in the linked list of used broadcast buffers  220  is ready to be released by examining the broadcast status (scanner.BS ==11 . . . 1?). If yes, then step S 660  is performed. If no, then step S 630  is performed. 
     Step S 630  checks whether the last two scans have not resulted in a buffer release (2 continuous FB.BS !==11 . . . 1?). If no, then the procedure loops back to step S 610  to wait another scan period. If yes, then step S 640  checks whether the scanning period is within an acceptable limit or maximum scanning period (sp&lt;max_sp?) before doubling the scanning period in step S 650 . If the scanning period is within the maximum scanning period, then step S 650  doubles the scanning period. Then, the method loops back to step S 610  to wait another scan period. 
     Following a yes from step S 620  (current buffer being released), step S 660  checks whether the scanning period is within an acceptable limit or minimum scanning period (sp&gt;min_sp?). If yes, then the scanning period is halved (sp=sp/2). If no, then the method loops back to step S 610  to wait another scan period. 
     These values of init_sp, max_sp, min_sp are different for different networks. By properly setting the values of these variables, better utilization of the memory bandwidth can be achieved. For example, if a 10M Ethernet is used, then unit_sp should be about 50 μs (this is the shortest packet transmitting in the network); max_sp=200 μs, and min_sp=12.5 μs. If a different network is utilized, then one of ordinary-skill could optimize the values of these variable after routine experimentation. 
     FIGS.  16 ( a )-( c ) illustrate an example of the dynamic scanning procedure showing changes to the scan period. 
     The series of illustrations in FIG.  16 ( a ) begins with an initial exemplary scanning period of 50 μs. After two scans with no buffer release, the scanning period is doubled (100 μs). The third scan discovers a broadcast status have all ones indicating a buffer ready to release. 
     FIG.  16 ( b ) is a continuation of the example shown in FIG.  16 ( a ) wherein the buffer discovered in the third scan has been released. Because the scanner  400  has discovered a buffer to release, the scanning period is halved as shown in the middle of FIG.  16 ( b ). The following two scans, however, are unsuccessful and the dynamic scanning procedure is doubled as shown by the first scan of FIG.  16 ( c ). 
     Is to be understood that doubling and halving the scanning period are illustrative examples of the invention. Although doubling and halving of a scanning period has implementation advantages because a simple bit shift operation can perform this calculation efficiently, one of ordinary skill in the art could use other scanning period factors (such as three or four) and could additionally require three or four unsuccessful scans before doubling the scanning period. 
     The invention being thus described, it will be obvious that the same may be varied in many ways. Such variations are not to be regarded as a departure from the spirit and scope of the invention, and all such modifications as would be obvious to one skilled in the art are intended to be included within the scope of the following claims.