Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-05-18
2004-04-13
Vanderpuye, Kenneth (Department: 2732)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S364000
Reexamination Certificate
active
06721309
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data switching, and more particularly to data switching engines of the kind in which a processor array is used to switch data from a plurality of sources to a plurality of destinations in a data communication network.
In recent years, high-speed data communication switching has been accomplished mostly in application specific integrated circuits (ASICs). Programmable logic devices have generally been considered too slow to be relied upon as main switching engines. With recent improvements in programmable logic technology, however, a trend now appears to be emerging toward implementing multiple programmable logic devices in parallel, or parallel processor arrays, as primary data switching engines.
Processor array switching engines provide certain advantages over ASIC switching engines in terms of time-to-market, flexibility and scalability. Still, the “parallel” aspect of processor array switching engines creates technical challenges. Foremost among these is how to best allocate the resources of the array. One possibility is to strictly dedicate each processor in the array to a particular group of sources. However, such a dedicated processor array is inefficient since a processor is idle whenever the sources to which it is dedicated are not transmitting packets, even while other processors may be overburdened. A second possibility is to allow each processor in the array to be shared by all sources. Such a shared processor array might greatly increase overall switching efficiency, especially when implemented in conjunction with an efficient load balancing algorithm ensuring that inbound packets are transmitted to the processors presently being underutilized. However, a shared processor array gives rise to other problems, such as how to preserve packet order integrity.
A problem of preserving packet order integrity arises in shared processor arrays because at any given time in the operational cycle of such an array, the time required to process a packet will vary from processor-to-processor. Thus, packets may be switched out of the array in an order different from that in which they were transmitted to the array for switching. While a departure from strict “first in, first out” sequencing is not a problem for packets applicable to different conversations, it may be for packets applicable to the same conversation.
Accordingly, there is a need for a way to ensure in a processor array in which the processing elements are shared among all sources that packets from the same source leave the array in the sequence in which they arrived. And there is a need for preserving packet ordering for packets from a common source without imposing too high a tax on switching performance.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for preserving packet order integrity in a shared processor array. The order for packets relating to the same conversation is maintained by checking for each inbound packet whether a previous packet from the same source is pending at a processing element before forwarding the packet to the processor array. If the check reveals that such a packet is pending, the inbound packet is forwarded to the same processing element as the previous packet. If the check reveals that no packet from the same source is pending at any processing element, the inbound packet is forwarded to a processing element in accordance with a load balancing algorithm.
REFERENCES:
patent: 5020052 (1991-05-01), DePrycker
patent: 5127001 (1992-06-01), Steagall et al.
patent: 5793747 (1998-08-01), Kline
patent: 5864540 (1999-01-01), Bonomi et al.
patent: 5889764 (1999-03-01), Needham et al.
patent: 6011775 (2000-01-01), Bonomi et al.
patent: 6092115 (2000-07-01), Choudhury et al.
patent: 6175554 (2001-01-01), Jang et al.
patent: 0 859 492 (1998-08-01), None
Reader Scot A.
Stone Geoffrey C.
Alcatel
Cordeiro David A.
Michael Blaine Brooks P.C.
Naglestad Andrew S.
Vanderpuye Kenneth
LandOfFree
Method and apparatus for maintaining packet order integrity... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for maintaining packet order integrity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining packet order integrity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3230394