Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-03-24
2001-04-03
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S415000, C710S220000
Reexamination Certificate
active
06212165
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data communication systems and more particularly relates to an apparatus for and a method of collapsing multiple ports to a single queue in a switching device.
BACKGROUND OF THE INVENTION
Currently, data networks are experiencing tremendous growth in both business and consumer areas. Corporate use of data networks is growing at a furious rate while at the same time more and more consumers are staking out their place in cyberspace. Corporations are realizing the utility and importance of maintaining an up to date, fast and reliable network. To that end, network equipment manufacturers are constantly striving to improve their current offerings of equipment, e.g., hubs, switches, routers, bridges, multiplexors, etc.
In connection with switch design, the architecture of the typical prior art switch, generally referenced
20
, is as shown in
FIG. 1. A
plurality of ports
12
pass input data, e.g., frames, to their associated queues
14
which are of a finite size. The ports represent the link layer components, i.e., the MAC layer. Each queue
14
is of the first in first out (FIFO) type. Four ports and queues are shown for illustrative purposes only. The output of each queue
14
is input to a four input multiplexor
16
. The output of the multiplexor
16
is input to the switching fabric
18
. Note that a switching fabric is shown for illustrative purposes only. The switching fabric can be replaced with any other type of resource that must be shared such as data buses, switch cores, processing cores, external ports, memory devices, etc. The output of the switching fabric
18
is input to an output demultiplexor
22
which demultiplexes the output of the switching fabric to the original four data paths. The output of the demultiplexor
22
is input to downstream processing elements (if any).
This scheme works fine when the bandwidth of the switching fabric is more than the combined bandwidth of the input ports
12
. A problem arises when the bandwidth of the switching fabric is less than the combined bandwidth of the input ports
12
. For example, a problem exists if the bandwidth of the switching fabric is 300 Mbps and each port is capable of clocking in data at 100 Mbps. In this case, the input multiplexor
16
uses a time division multiplexing (TDM) technique to time slice data from each input port. Thus, a round robin approach would be used to share the limited resources of the switching fabric. Using a round robin approach gives each input port equal priority. A disadvantage of this approach is that all ports ‘suffer’ equally with no priority being given to any port over another port. The problem is that a time slot is allocated to a port on a static basis regardless of whether the port has any data to input to the switching fabric. This approach is wasteful of bandwidth and leads to lower performance of the network device.
SUMMARY OF THE INVENTION
The present invention attempts to solve the problems associated with the prior art by providing an apparatus for and a method of collapsing multiple ports to a single queue. The invention has applications in switching devices, for example, whereby several external ports share the same resource, e.g., data buses, switching fabrics, etc. In order to allocate the resources to all the ports, a scanning method is used to allocate the division of the resources to the ports during each time slot. This scanning method is useful in cases where the bandwidth of the switch resources is less then the combined bandwidth of the external ports. In this case, a queue is required to be established and integrated into the scanning method. The present invention discloses such a scanning method whereby frames are passed to the shared resource, i.e., the switching fabric, in accordance with their arrival order and without regard to the source port the frame came in on.
There is provided in accordance with the present invention a method of allocating a shared resource among a plurality of external ports, the method comprising the steps of providing an input queue, the input queue divided into a plurality of segments each capable of holding a frame of data, scanning the plurality of external ports in a predetermined manner for data ready to be input, writing frame data from the plurality of external ports to the next free segment in the input queue wherein the order of writing frames to the segments is in accordance with their arrival over the plurality of external ports and reading frame data from the input queue to the shared resource wherein the order of reading frames is in accordance with their arrival over the plurality of external ports.
The step of writing comprises the step of maintaining a plurality of write pointers wherein each write pointer points to a segment of the input queue holding frame data or comprises the step of maintaining a write pointer which points to the next free segment within the input queue to be written to with frame data from an external port.
The step of reading comprises the step of maintaining a single read pointer which points to the next segment of frame data to be read to the shared resource. The steps of scanning, writing and reading are performed sufficiently quick enough to allocate the shared resource in the case when the bandwidth of the shared resource is less than the aggregate bandwidth of the plurality of external ports.
The method also comprises the step of queuing the frame data input from each external port before being written to the input queue. In addition, frame data from the plurality of external ports is written to the next free segment in the input queue without regard to the particular external port the frame originated on. Also, the step of scanning comprises scanning the plurality of external ports in a round robin fashion.
There is also provided in accordance with the present invention an apparatus for allocating a shared resource among a plurality of external ports, the apparatus comprising an input queue, the input queue divided into a plurality of segments each capable of holding a frame of data, scanning means for scanning the plurality of external ports in a predetermined manner for data ready to be input, write means for writing frame data from the plurality of external ports to the next free segment in the input queue wherein the order of writing frames to the segments is in accordance with their arrival over the plurality of external ports and read means for reading frame data from the input queue to the shared resource wherein the order of reading frames is in accordance with their arrival over the plurality of external ports.
The write means is adapted to write frame data from the plurality of external ports to the next free segment in the input queue without regard to the particular external port the frame originated on. The scanning means comprises means for scanning the plurality of external ports in a round robin fashion. The apparatus further comprises an output queue for receiving data from the shared resource directed to the plurality of external ports.
In addition, the input queue comprises random access memory (RAM) configured as a circular buffer thus creating a first in first out (FIFO) queue. The apparatus further comprises an input buffer for performing rate adaptation between the input queue and the shared resource. The apparatus further comprises an output buffer for performing rate adaptation between the output queue and the shared resource.
REFERENCES:
patent: 4672536 (1987-06-01), Giroir et al.
patent: 5274644 (1993-12-01), Berger et al.
patent: 5293486 (1994-03-01), Jordan et al.
patent: 5446737 (1995-08-01), Cidon et al.
patent: 5491694 (1996-02-01), Oliver et al.
patent: 5719854 (1998-02-01), Choudhury et al.
patent: 6021124 (2000-02-01), Haartsen
patent: 6075772 (2000-06-01), Brown et al.
Honig Yoav
Mann Eytan
3Com Corporation
Hsu Alpus H.
Qureshi Afsar M.
Weitz David J.
Wilson Sonsini Goodrich & Rosati
LandOfFree
Apparatus for and method of allocating a shared resource... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for and method of allocating a shared resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for and method of allocating a shared resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438829