Electrical computers and digital processing systems: memory – Address formation – Generating a particular pattern/sequence of addresses
Reexamination Certificate
2001-12-21
2004-01-27
Ellis, Kevin L. (Department: 2180)
Electrical computers and digital processing systems: memory
Address formation
Generating a particular pattern/sequence of addresses
Reexamination Certificate
active
06684317
ABSTRACT:
FIELD
The present invention relates to systems and techniques for assigning memory storage addresses to sequential data packets from pluralities of input data line cards, or other sources, being more particularly directed to such addressing for writing the data packets into shared memory selections preferably of an output-buffered switch fabric as of the type described in copending U.S. patent application Ser. No. 09/941,144, entitled: METHOD OF SCALABLE NON-BLOCKING SHARED MEMORY OUTPUT-BUFFERED SWITCHING OF VARIABLE LENGTH DATA PACKETS FOR PLURALITIES OF PORTS AT FULL LINE RATE, AND APPARATUS THEREFOR, filed Aug. 28, 2001 and of common assignee herewith, and such that there is no overlap among the packets and no holes or gaps between adjacent data packets.
BACKGROUND
While the addressing methodology of the invention may be of more general application as well, it will be illustratively described herein with reference to its preferred and best mode use with output-buffered switch fabrics of the above-mentioned type, wherein a central shared memory architecture is employed, comprised of a plurality of similar successive data memory channels defining a memory space, with fixed limited times of data distribution from the input ports successively into the successive memory cells of the successive memory channels, and in striped fashion across the memory space. This enables non-blocking shared memory output-buffered data switching, with the data stored across the memory channels uniformly. By so limiting the times of storing data from an input port in each successive memory channel, the problem is admirably solved of guaranteeing that data is written into memory in a non-blocking fashion across the memory space and with bounded delay.
This technique, as explained in said copending application, embraces a method of receiving and outputting a plurality m of queues of data traffic streams to be switched from data traffic line card input ports to output ports. A plurality n of similar successive data memory channels, is provided, each having a number of memory cells defining the shared memory space assigned to the m queues. Buffering is effected for m memory cells, disposed in front of each memory channel to receive and buffer data switched thereto from line card traffic streams, and providing sufficient buffering to absorb a burst from up to n line cards. Successive data is distributed in each of the queues during fixed limited times only to corresponding successive cells of each of the successive memory channels and, as before stated, in striped fashion across the memory space, thereby providing the non-blocking shared memory output-buffered data switching I/O (input/output) ports. Each packet from an input port gets an address in the destination queue from an address generator, defining the location in the shared memory in which the packet will be stored. Such use of an output-buffered switch fabric enables packets destined for a queue to come from all input ports; and all these packets are written into the shared memory such that, as before mentioned, there is no overlap among packets and no holes or gaps between adjacent packets. The address of every packet, accordingly, depends upon all the packets that have been previously assigned an address, and the packets must be assigned sequentially.
As an example, the system embodying the shared memory operating with the address generating methodology of the present invention can support minimum 40 byte packets with no impact on the switch fabric performance, receiving from each 10 Gbps port, a 40 byte packet every 40 ns fixed time slot, and with capability to assign addresses for 64 packets every 40 ns, as where all these packets belong to the same queue.
The invention accomplishes this without attempting to push technology as has been proposed in other prior approaches. To the contrary, the present invention develops a parallel processing algorithm, as later detailed, with its address generator being scalable for both port count and bandwidth.
OBJECT OF INVENTION
A principal object of the present invention, therefore, is to provide a new and improved address generating methodology particularly, though not exclusively, suited to enable packet addressing in an output-buffered shared memory switch fabric, and by a novel parallel processing scalable approach, and without overlap among the sequentially addressed packets, and with no holes or gaps between adjacent packets.
A further object is to provide a novel address generator for carrying out the method of the addressing technique of the invention, and embodying a ring structure of successively connected subaddress generators, with memory allocation effected sequentially from subaddress generator to subaddress generator along the ring.
Still another object is to provide such novel address generation with successive addressing effected at successive subaddress generators of the ring by adding the current size of packets thereat to the address assignment of the preceding subaddress generator, and with the address of a packet thus depending upon all packets that have previously been assigned an address, and with such assignment occurring sequentially.
Other and further objects will be explained hereinafter and are more particularly detailed in the accompanying claims.
REFERENCES:
patent: 4748618 (1988-05-01), Brown et al.
patent: 6622232 (2003-09-01), Schroeder
Marshall Benjamin
Pal Subhasis
Soman Satish
Wang Xiaolin
Axiowave Networks, Inc.
Ellis Kevin L.
Rines and Rines
LandOfFree
Method of addressing sequential data packets from a... 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 of addressing sequential data packets from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of addressing sequential data packets from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3227724