Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-01-23
2002-03-26
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S428000, C370S390000
Reexamination Certificate
active
06363075
ABSTRACT:
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.
REFERENCES:
patent: 5274642 (1993-12-01), Widjaja et al.
patent: 5361372 (1994-11-01), Rege et al.
patent: 5406556 (1995-04-01), Widjaja et al.
patent: 5432908 (1995-07-01), Heddes et al.
patent: 5528588 (1996-06-01), Bennett et al.
patent: 5535197 (1996-07-01), Cotton
patent: 5610914 (1997-03-01), Yamada
patent: 5825773 (1998-10-01), Shutoh et al.
patent: 5898687 (1999-04-01), Harriman et al.
patent: 6021132 (2000-02-01), Muller et al.
Chang Tai-Chung
Fan Kuo-Yen
Huang Paul
Tseng Huan-Pin
Wang Yao-Tzung
Hyun Soon-Dong
Industrial Technology Research Institute
Nguyen Chau
LandOfFree
Shared buffer management mechanism and method using multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared buffer management mechanism and method using multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared buffer management mechanism and method using multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838065