Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-01-28
2003-06-03
Vincent, David (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S389000, C370S392000
Reexamination Certificate
active
06574194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to data communication systems. More specifically, the present invention relates to an architecture and method for facilitating data flow with low latency through a multiple port switch system for data unicast and broadcast communication.
2. Description of the Related Art
In data communications, a switch system is a network device that selects a path or circuit for sending a unit of data to its next destination. A switch system may also include the function of a router, a device or program that can determine the route and specifically what adjacent network point the data should be sent to. In general, a switch system is a simpler and faster mechanism than a router, which requires knowledge about the network and how to determine the route.
On larger networks, the trip from one switch point to another in the network is called a hop. The time a switch system takes to figure out where to forward a data unit is called the latency which is typically measured between the first bit of an input (inbound) packet and the first bit of a corresponding output (outbound) packet. In a multi-port switch system, the latency is measured between the first bit of an input packet and the first bit of a corresponding output packet to the last one of the multiple output ports. In reality, one of the factors that determines the cost and performance of a switch system is largely the latency. A system with low latency generally warrants a high price tag. There is therefore a great need for a switch system that has minimum latency but is low cost.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above described problems and needs and has particular applications to local area networks. Switch systems employing the present invention will have the minimum latency but be of low cost and may be advantageously used in high speed networks.
According the present invention, a switch system comprises a group of queue managers that further comprise a free queue manager, an enqueue controller, a multicast queue manager, and a port queue manager. The free queue manager provides a mechanism to monitor the number of free buffers remaining in an external memory and to assign free queue buffer, if there are any, to an input port that receives an inbound packet and hence requests for a free space in the external memory. In addition, the free queue manager maintains a free queue linked list (registers) for a next free queue buffer address and updates the free queue linked list after a packet is delivered. The enqueue controller arbitrates between requests for enqueuing from the ports. The multicast queue manager maintains a multicast queue linked list and manages multicast queue entries to the list. The port queue manager manages output queues of each of the output ports and ensures that a packet is correctly routed to the appropriate ports for subsequent delivery.
When a data packet is received at one of the ports in the switch system; the free queue manager examines the linked list maintained by the free queue manager to determine if there are any space available in the external memory to accommodate the newly arrived data packet. If the linked list indicates that there is no more space available, the packet is simply dropped. Otherwise, the free queue manager inserts an element into the linked list and the element comprises address information as to where the packet is stored in the external memory. The free queue manager also ensures that the element is removed from the linked list upon the data packet is delivered from one of the ports in the switch system. As a result, the external memory is effectively and efficiently managed.
When the data packet is for multicast or broadcast, the multicast queue manager inserts an element to the multicast queue linked list if the linked list does not exceed a certain length. The structure of the multicast queue linked list is similar to that of the free queue linked list. The element inserted in the multicast queue linked list comprises identification information related to the ports to which the data packet is designated. Similarly, the element is removed from the multicast queue linked list upon the multicast packet delivered through each of the designated ports.
There are many advantages and benefits in the present invention. One of them is the reduced latency time achieved by using the queue manages to manage simultaneously location addresses, ports for multicast packets and timely recycle the locations from which packets have been successfully delivered. As a result, the time it takes to forward an arrived packet to a right output port or ports for delivery is minimized as described and appreciated herein.
According to one embodiment, the present invention is a method for facilitating packets to be delivered to designated ports with a minimum latency, the method comprising:
receiving a data packet at a first port of the ports;
storing the data packet in a location of an external memory; the location addressable by an address;
enqueuing the address in a free queue linked list; and
dequeuing the address from the free queue linked list upon the data packet being delivered.
According to another embodiment, the present invention is an architecture for facilitating packets to be delivered to designated ports with a minimum latency, the architecture comprises:
a plurality of ports;
an external memory interface coupled between the ports and an external memory and facilitating data communication therebetween; wherein the external memory has a plurality of locations, one of the locations accommodating a packet received from one of the ports and addressable by an address;
a free queue linked list; and
a free queue manager communicating with the ports and the external memory interface and further maintaining the free queue linked list corresponding to the locations in the external memory; the free queue manager inserting the address in the free queue linked list and removing the address after the packet is delivered through another one of the ports.
Other objects, together with the foregoing are attained in the exercise of the invention in the following description and resulting in the embodiment illustrated in the accompanying drawings.
REFERENCES:
patent: 6073158 (2000-06-01), Nally et al.
patent: 6400715 (2002-06-01), Beaudoin et al.
patent: 6457059 (2002-09-01), Kobayashi
Lin Wallace
Sun Peter C. P.
Chang C. P.
Cypress Semiconductor Corporation
Sam Phirin
Vincent David
Zheng Joe
LandOfFree
Architecture of data communications switching system and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Architecture of data communications switching system and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture of data communications switching system and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103880