High speed data switching systems, including ATM switching systems, are characterized by switches which have switching fabrics or other routing mechanisms for redirecting the flow of data packets from a plurality of inputs to a plurality of outputs. It is not uncommon for incoming data packets to pass through a switching fabric along different paths in accordance with one of many methodologies designed to reliably route those data packets to their proper destination with minimal blocking. Because of the varying time that a particular data packet may take to traverse the routing network, it is not uncommon for data packets to appear at the outputs in a sequence different from their sequence at the input side. This unintentional reordering of packets in an unpredictable fashion can cause problems in some applications which require that the same sequence in data be preserved.
In order to solve the sequencing problem inherently present in high speed data switches which misorder data packets, the inventor herein has succeeded in designing and developing a resequencer for a packet processor I/C which reorders the data packets into their proper time sequence after exiting the switching fabric and prior to transmission to the next switching system on the path to the ultimate destination. With the resequencer of the present invention, data packets may be replaced in proper order for all but a vanishingly small fraction of misordered packets while introducing only a very small delay. For example, the inventor estimates that for a 64 port switch, packets may be delayed between about 15-20 packet times to ensure a misordering probability of less than 10.sup.-6.
The resequencer of the present invention includes a resequencer buffer which receives the data packets after they exit from the switch, and its associated buffer controller which controls the buffer to output the data packets in time sequence as opposed to the strict sequence in which they are received from the switch. Additionally, a time stamp circuit at the input side of the switch stamps the data packets with the current time as they enter the switch. Therefore, as the data packets exit the switch, they contain a time stamp representative of their sequence as they entered the switch. As the data packet exits the switch and enters the resequencing buffer, its time stamp is compared with the then current time to generate a delta T which is equivalent to the time lapse for that particular packet to traverse the switch. This delta T equates to the "age" of the packet. The packets are then stored in the slots of the buffer and a corresponding entry is made in the buffer controller of the slot number and the age for each data packet. These ages are regularly incremented so that as a data packet sits in the buffer, its age remains representative of the delta T from the time that the data packet entered the switch. The buffer controller then compares the ages of all of the data packets in order to determine the oldest data packet contained in the buffer. This age is then compared with an age threshold and, if it is sufficiently old, indicates that the data packet is available for transmission. Additional output circuitry of conventional design then either grants or denies the request to transmit and the data packet is transmitted.
The buffer controller provides many unique advantages in its approach to resequencing the data packets. The first of these is that the buffer controller works with a delta T representative of the age of the data packet computed as the time required for that data packet to traverse the switch. Therefore, time is used to determine the sequencing of the data packets so that they are reordered in real time sequence. Still another feature of the buffer controller is the technique of storing the data packets in a buffer until an appropriate age threshold has been reached. This provides a second level of control over the data packets in that the data packets are not merely spewed out of the switch in an approximated reordered sequence but instead are output in a controlled manner. Furthermore, adjustment of the age threshold may also be used to increase the reliability of resequencing. Still another advantage of the buffer controller is its use of a wire OR contention bus which interconnects a plurality of bi-directional shift registers (BSRs), each BSR being used to contain a data packet's age and slot number. This circuitry provides an elegantly simple means for comparing the ages and slot numbers of the data packets in order to select the oldest packet for potential output. This wire OR contention bus circuitry permits cascading of a number of groups of BSRs in order to facilitate contention between a larger number of data packets than would be possible in a single grouping, because of capacitive loading. Still another advantage to the buffer controller of the present invention is that it uses bi-directional shift registers for storing the age and slot number such that the slot numbers themselves may be used to break ties between data packets which are of equal age. This conveniently prevents blocking of the buffer controller by data packets of equal age and eliminates the requirement for additional circuitry for making additional comparisons or using some other technique for resolving ties.
While the principal advantages and features of the invention have been briefly described above, a more thorough understanding may be attained by referring to the drawings and description of the preferred embodiment which follow.
USPTO Backgrounds
USPTO Backgrounds