Patent Document

BACKGROUND OF THE INVENTION  
         [0001]    1. Technical Field of the Invention  
           [0002]    This invention is related to network switch fabrics, and more specifically, to data control and retrieval from the buffering mechanisms contained therein.  
           [0003]    2. Background of the Art  
           [0004]    The evolution of the Internet and other global communication networks continue to attract an ever-increasing number of nodal entities which place strategic importance on the viability of such networks for the communication of information for commercial and personal use. Such information places higher demands on the network infrastructure to ensure not only that the information arrives at the desired destination, but that it arrives in a timely manner.  
           [0005]    Most modern switching devices can move information at wire speed and it is a goal is to ensure that the switching device is not the bottleneck of network data flow. However, with network bandwidth requirements pushing the development and implementation of faster transmission technologies e.g., Gigabit Ethernet, internal data flow of such switching devices becomes more important in order to maintain data throughput at such wire speeds.  
           [0006]    Many switching devices utilize queues for the temporary storage of data while processing logic has time to sort out the destination information, and to send the data on its way. Consequently, queuing performance is very important.  
           [0007]    What is needed is an architecture that provides efficient queuing performance that ensures overflow will not occur in Gigabit Ethernet implementations.  
         SUMMARY OF THE INVENTION  
         [0008]    The present invention disclosed and claimed herein, in one aspect thereof, comprises an architecture for data retrieval from a plurality of coupling queues. At least first and second data queues are provided for receiving data thereinto. The data is read from the at least first and second data queues with reading logic, the reading logic reading the data according to a predetermined queue selection algorithm. The data read from by reading logic and forwarded to an output queue.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings in which:  
         [0010]    [0010]FIG. 1 illustrates a block diagram of the coupling queue architecture, according to a disclosed embodiment;  
         [0011]    [0011]FIG. 2 illustrates a flow chart for the general algorithm of the retrieval logic, in accordance with a disclosed embodiment; and  
         [0012]    [0012]FIG. 3 illustrates a more detailed flow chart of the algorithm for monitor and control of data in both input queues.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0013]    Referring now to FIG. 1, there is illustrated a block diagram of a coupling queue architecture, according to a disclosed embodiment. The disclosed architecture provides two input coupling queues: a first coupling queue  100  (also denoted as Queue A), and a second coupling queue  102  (also denoted as Queue B) which share (or support) one virtual output queue  104 . A first input port  106  is connected to provide 32-bit data into the first coupling queue  100 , and a second input port  108  connects to provide 32-bit data into the second coupling queue  102 . Thus each input port  106  and  108  has a corresponding and independent input coupling queue  100  and  102  which temporarily stores the input data.  
         [0014]    Retrieving (or reading) logic  110  operates to retrieve (or read) the contents of the coupling queues  100  and  102  according to a predetermined selection algorithm, and pass the retrieved contents on to the virtual output queue  104 . Thus the retrieving logic  110  connects to the output of the first coupling queue  100  to retrieve data therefrom across an associated 64-bit data bus  112  at a speed which is approximately twice the speed in which 32-bit data is being input to (or written into) the first coupling queue  100 . Similarly, the retrieving logic  110  connects to the output of the second coupling queue  102  to retrieve data therefrom across a corresponding 64-bit data bus  114  at a speed which is approximately twice the speed in which 32-bit data is being input to the second coupling queue  102 . In general, the reading speed for retrieving data from the coupling queue  100  (or  102 ) is approximately twice the speed in which the data is being written into the coupling queue  100  (or  102 ).  
         [0015]    Writing to the virtual output queue  104  from the retrieving logic  110  is fragment-based, i.e., when reading commences from one of the input coupling queues  100  (or  102 ), the read operation does not stop until the end of the current data fragment is detected. The reading logic  110  then forwards the 64-bit data across a connection  116  to the virtual output queue  104  at approximately twice the speed at which the data was written into the coupling queue. Data latency is minimized such that once a data fragment enters the coupling queue, the read/write process to the virtual output queue  104  begins. Additionally, the enqueued data is read as fast as possible to prevent the occurrence of an overflow state in either of the coupling queues  100  and  102 .  
         [0016]    The size of each input coupling queue size is approximately twice the maximal data fragment size. The minimal data fragment size is preferably approximately {fraction (1/16)} th  of the maximal data fragment size. The size of the input data fragment preferably ranges from approximately {fraction (1/16)} th  of the maximal data fragment size up to and including the maximal data fragment size.  
         [0017]    The reading algorithm neither utilizes a traditional ping-pong method based on the fragment size to read the enqueued data nor reads the enqueued data based upon which input queue ( 100  or  102 ) has more data. Either implementation causes increased latency for certain types of data resulting in the overflow of one or both coupling queues  100  and  102 . For example, use of the traditional simple ping-ping method where the first queue  100  buffers short data fragments and the second queue  102  buffer long data fragments will ultimately result where the first queue  100  will be reach an overflow state. In another example, if there is a 256-byte data fragment being written into the first coupling queue  100 , 64 bytes are already in the first queue  100 , and a 32-byte fragment is already in the second queue  102 , then the data in the first queue  100  is longer than data in the second queue  102 . Thus if the reading method utilized is that which operates based on which queue has more data, the first queue would be chosen for reading. However, in this case, it is preferable to first read the data from the second queue  102  since reading from the first queue  100  cannot end until the complete fragment is read. The read operation of the second queue  102  for the smaller fragment would start and complete in a much shorter period of time, and reduce the potential for latency in that second queue  102 . On the other hand, the read operation of the first queue  100  would initially be at approximately twice the input writing speed for the beginning of the fragment data, but would slow down to the same speed as the writing speed for the remaining data of the larger fragment as the read operation catches up to the input write speed. If time t 1  is the total time for reading data from both the first and second queues  100  and  102 , and time t 2  is the total time required if first reading from the second queue  102 , then apparently t 1 &gt;t 2 .  
         [0018]    Referring now to FIG. 2, there is illustrated a flow chart of the general algorithm of the retrieval logic, in accordance with a disclosed embodiment. Flow begins at a starting point  200  and continues to a decision block  202  to determine if both of the coupling queues  100  and  102  are empty. If so, flow is out the “Y” path to the input of the decision block  202  to continue monitoring for such a condition. If either the first queue  100  or the second queue  102 , or both queues  100  and  102  have enqueued data, flow is out the “N” path of decision block  202  to function block  204  to interrogate and selectively read the queues  100  and  102  according to predetermined criteria. The queue read operation, which includes all processing necessary to extract one or more complete data fragments from the queue being read, continues until both the first queue  100  and the second queue  102  are empty, at which time flow is from function block  204  to the input of decision block  202 . Note also that the size of the data fragments vary according to the particular application. Thus the disclosed architecture can read enqueued data fragments of varying sizes. The queue selection operation occurs only after finishing the current fragment reading.  
         [0019]    Referring now to FIG. 3, there is illustrated a more detailed flow chart of the algorithm for monitor and control of data in both input queues. Flow begins at a Start block and continues to a decision block  300  to determine if both coupling queues  100  and  102  are empty. If so, flow is out the “Y” path and loops back to the input to continue monitoring the status of both queues  100  and  102 . If either one has a enqueued data, flow is out the “N” path of decision block  300  to a decision block  302  to determine if the first queue  100  is empty. If not, flow is out the “N” path to a function block  304  to read the first queue  100 . Flow continues then to a decision block  306  to determine if the amount of data enqueued in the second queue  102  has exceeded 25% of its total queue capacity. If so, flow is out the “Y” path to a function block  307  to read the enqueued data fragments from the second queue  102 . Detailed discussion of this portion of the flow chart will continue hereinbelow after completion of the discussion for the first queue  100 .  
         [0020]    As indicated hereinabove, the disclosed architecture efficiently moves data from the two input coupling queues to the virtual output queue with good data latency and minimal input coupling queue size, and never allows input coupling queue overflow. This is accomplished by ensuring that overflow in either input queue  100  or  102  is prevented. Thus it is important to first check on parameters indicating that a particular queue is reaching capacity. To that end, the disclosed algorithm first checks on the 25%-full trigger, and then the full-fragment criteria. These or any other criteria can be adjusted to the particular application, as desired, as well as the order, so long as overflow is prevented.  
         [0021]    If the amount of data in the second queue  102  has not exceeded 25% of the queue capacity, flow is out the “N” path of decision block  306  to a decision block  308  to determine if the amount of data enqueued in the first queue  100  has exceeded 25% of the total queue capacity. If so, flow is out the “Y” path to function block  304  to then read the first queue  100  until it is empty. If not, flow is out the “N” path to a decision block  310  to determine if the second queue  102  has enqueued therein a full data fragment. If a full fragment is enqueued, flow is out the “Y” path to function block  307  to read the second queue  102  until it is empty. If a full fragment is not enqueued, flow is out the “N” path to a decision block  312  to determine if the first queue  100  has enqueued therein a full data fragment. If so, flow is out the “Y” path to function block  304  to read the first queue  100  until it is empty. If not, flow is out the “N” path of decision block  312  to a decision block  314  to determine if the second queue  102  has enqueued therein any data. If the second queue  102  has any data, flow is out the “Y” path to function block  307  to read the second queue  102  until it is empty. If not, flow is out the “N” path to a decision block  316  to determine if the first queue  100  has enqueued therein any data. If so, flow is out the “Y” path to function block  304  to read the first queue  100  until it is empty. If not, flow is out the “N” path of decision block  316  to a decision block  318  to determine if the second queue  102  is empty. If it is not empty, flow is out the “N” path to function block  307  to read the second queue  102  until it is empty. If it is empty, flow is out the “Y” path to a decision block  320  to determine if the first queue  100  is empty. If so, flow is out the “Y” path, and loops back to the input of decision block  318  to again determine of the second queue  102  is empty. On the other hand, if the second queue  102  is empty, but the first queue  100  is not empty, flow is out the “N” path of decision block  320  to function block  304  to read the first queue  100  until it is empty.  
         [0022]    Note that if any of the criteria are met in decision blocks  306 ,  310 ,  314 , or  318 , flow jumps over to function block  307  read data from the second queue  102 . Continuing with the flowchart from function block  307 , flow is then to a decision block  309  to determine if the amount of data enqueued in the first queue  100  has exceeded 25% of its total queue capacity. If so, flow is out the “Y” path to function block  304  to read the enqueued data fragments from the first queue  100 . If the amount of data in the first queue  100  has not exceeded 25% of the queue capacity, flow is out the “N” path of decision block  309  to a decision block  311  to determine if the amount of data enqueued in the second queue  102  has exceeded 25% of its total queue capacity. If so, flow is out the “Y” path to function block  307  to then read the second queue  102  until it is empty. If not, flow is out the “N” path to a decision block  313  to determine if the first queue  100  has enqueued therein a full data fragment. If so, flow is out the “Y” path to function block  304  to read the first queue  100  until it is empty. If not, flow is out the “N” path to a decision block  315  to determine if the second queue  102  has enqueued therein a full data fragment. If so, flow is out the “Y” path to function block  307  to read the second queue  102  until it is empty. If not, flow is out the “N” path of decision block  315  to a decision block  317  to determine if the first queue  100  has enqueued therein any data. If so, flow is out the “Y” path to function block  304  to read the first queue  100  until it is empty. If not, flow is out the “N” path to a decision block  319  to determine if the second queue  102  has enqueued therein any data. If so, flow is out the “Y” path to function block  307  to read the second queue  102  until it is empty. If not, flow is out the “N” path of decision block  319  to a decision block  321  to determine if the first queue  100  is empty. If not, flow is out the “N” path to function block  304  to read the first queue  100  until it is empty. If so, flow is out the “Y” path to a decision block  323  to determine if the second queue  102  is empty. If so, flow is out the “Y” path, and loops back to the input of decision block  321  to again determine of the first queue  100  is empty. On the other hand, if the first queue  100  is empty, but the second queue  102  is not empty, flow is out the “N” path of decision block  323  to function block  307  to read the second queue  102  until it is empty.  
         [0023]    The disclosed architecture utilizes an algorithm which reads the data based upon both the status of the data fragment and which queue has more data, and which is exemplified as follows. 
         
         
         
         
         
 
         [0024]    Although the preferred embodiment has been described in detail, it should be understood that various changes, substitutions and alterations can be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

Technology Category: h