Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-02-22
2002-08-27
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S428000
Reexamination Certificate
active
06442162
ABSTRACT:
FIELD OF THE INVENTION
This invention generally relates to packet-based communication systems and more particularly to enabling communication between devices, such as individual chips, at very high rates of data transfer.
BACKGROUND TO THE INVENTION
When data transfer at very high rates is required between devices, and particularly between integrated circuits in a multi-chip design, such as a gigabit switch, standard communication techniques have drawbacks which affect performance. In packet-switched systems, data which is temporarily stored in a particular device is very often destined for one of many ‘ports’ in a destination device. It is critical that when the time comes to transfer such temporarily stored data, the source device should possess an indication that there is space available in the memory of the destination device. The customary way of achieving this requirement is to interrogate the destination device to discover whether such space exists, at the time the data transfer needs to occur. At low rates of throughput, such a preliminary operation, or ‘handshake’, does not necessarily impose any unacceptable delay on the speed of transfer. At very high rates of transfer, such as above 100 megabits per second and typically at 1 gigabit per second or more, the time required to perform the preliminary interrogation and response to it becomes significant compared with the data rate and represents non-recoverable ‘dead’ time and generally degrades the performance of the system.
BRIEF SUMMARY OF THE INVENTION
In general terms, the present invention is based on the maintenance of a system of credits, representing units of memory space which is reserved in respect of each of the ports of a destination device. At a source device, a count is maintained of such credits or units of space available. Provided that there are enough credits available at a source device to fit the quantity of data which needs to be transferred to a given port of a particular destination device, data transfer from the source to the destination device may be initiated immediately. As data is transferred from source to destination, the credit counts are diminished whereas when data is transmitted from a given destination port, the respective count maintained at the source device may be incremented. It should be appreciated that the incrementing and decrementing of the counts of units of available space will be made to occur ‘off-line’, namely not on the critical path for data transfer. In effect, provided that sufficient initial credits are allocated data transfer between devices may occur with a minimum of unnecessary latency.
The invention is particularly intended for a network switch which comprises a multiplicity of chips (such as four) each of which can receive data packets at any one of a set of ports and can direct packets to ports either on the same chip or to ports on any other of the chips. Thus any of the chips can be a ‘source device’ and any can be a ‘destination device’ for the purposes of the invention.
In a preferred form of the invention, the or each source chip includes memory space for data packets which can be transmitted to a destination chip by way of a high-speed bus. At the destination chip there is an input buffer or store for data received by way of the bus from the source chip and in general a respective input buffer store for each source chip connected to the destination chip. It is desirable that in any event there is a check made on each input buffer for sufficient storage space for a packet or frame of maximum size and an enabling signal confirling the availability of such space may be conveyed to the source chip by way of a data channel other than the aforementioned data bus. The or each destination chip includes a store such as a fifo buffer for each port from which data is to be transmitted. Initially, there is allocated a certain space in each transmit fifo buffer, the allocation representing a particular number of units of storage space in the buffer. A credit count is maintained for each port at each source chip. Each time the destination chip transmits a quantity of data (equivalent to the relevant storage space), the destination chip signals the source chip to enable the source chip to increment the respective count maintained in relation to the port in the destination chip. For each transmission of data corresponding to the unit of memory space, the respective port space count is decremented.
Several advantages accrue from the scheme envisaged herein. In particular, there is no necessity to reserve space in the transmit stores for the case where a packet is destined for it from each source chip simultaneously. Further, the system enables a decoupling of the ‘fullness’ of the pipeline from the status of a transmit buffer. There is no need to reserve space in the transmit buffers for packets currently in the pipeline. Further, packets in the input buffers of the destination device are always guaranteed space in the transmit buffers and therefore cannot normally block the data path.
These and other features and advantages of the invention will be apparent from consideration of the following description of a preferred embodiment of the invention.
REFERENCES:
patent: 4475192 (1984-10-01), Fernow et al.
patent: 4780889 (1988-10-01), Ley et al.
patent: 5528591 (1996-06-01), Lauer
patent: 5550860 (1996-08-01), Georgiou et al.
patent: 5642386 (1997-06-01), Rocco, Jr.
patent: 5757297 (1998-05-01), Ferraiolo et al.
patent: 5923852 (1999-07-01), Lee et al.
patent: 5950115 (1999-09-01), Momtaz et al.
patent: 5970103 (1999-10-01), Townshend
patent: 6154816 (2000-11-01), Steely et al.
patent: 6252849 (2001-06-01), Rom et al.
patent: 0 153 107 (1985-08-01), None
patent: 0 365 337 (1990-04-01), None
patent: 0 424 741 (1991-05-01), None
patent: 0 465 201 (1992-01-01), None
patent: 0 508 886 (1992-10-01), None
patent: 0 603 916 (1994-06-01), None
patent: 0 841 782 (1998-05-01), None
patent: 0 853 441 (1998-07-01), None
patent: 2 283 645 (1995-05-01), None
patent: 2 311 700 (1997-10-01), None
patent: 2 336 075 (1999-10-01), None
patent: 2 337 674 (1999-11-01), None
patent: 2 343 816 (2000-05-01), None
patent: 2 344 030 (2000-05-01), None
patent: WO 96/34474 (1996-10-01), None
U.S. patent Application Ser. No. 09/286,470 filed Apr. 6, 1999, Copending.
U.S. patent Application Ser. No. 09/417,102 filed Oct. 13,1999, Copending.
U.S. patent Application Ser. No. 09/645,569 filed Aug. 25, 2000, Copending.
WPI Abstract Accession No. 97-269820/1997 & JP090098171 (Hitachi) Aug. 4, 1997.
WPI Abstract Accession No. 93-390998/1993 & JP05292091 (Mitsubishi Electric) May 11, 1993.
O'Connell Anne G.
O'Neill Eugene
Quinlan Una
3Com Technologies
Chin Wellington
Nixon & Vanderhye P.C.
Pham Brenda
LandOfFree
Credit-based scheme for high performance communication... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Credit-based scheme for high performance communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Credit-based scheme for high performance communication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926861