Back to results
US 6,714,553 B1Granted
System and process for flexible queuing of data packets in network switching
AssigneeTop Layer Networks, Inc.
InventorsNigel T. Poole, Joseph H. Brown, IV, Scott William Nolan, Barry A. Spinney, Richard L. Szmauz
Life of this patent
Estimating the term…
Abstract
A process and system for flexibly switching connections of data packet flows between nodes of data processing system networks by dividing data packets into cells and logically linking these cells on multiple queues of linked pointer lists.
Claims31
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet, wherein said logical linking is performed by setting pointers to said buffer locations containing said cells and setting linking pointers to point to and link said buffer location pointers;
- (e) maintaining in memory pointers to locations of buffers available for storing cells by setting a next free buffer pointer to the location of the pointer to a first available buffer and setting a pointer from said next free buffer pointer to the location of the pointer to a second available buffer and repeating the process until all available buffers are linked and by resetting said next free buffer pointer to said second available buffer pointer when a cell is stored in said first available buffer
- (f) scheduling said cells for transmission on said transmit physical path;
- and
- (g) transmitting said cells according to said logical linking.
5 more elements
A process for flexibly connecting between a receive physical path comprising one or more receive circuits and a transmit physical path comprising one or more transmit circuits the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) writing tags in said received cells identifying their source circuits;
- (f) scheduling said cells for transmission on said transmit physical path;
- (g) transmitting said cells according to said logical linking;
- and
- (h) maintaining a receive circuit table with an entry for each circuit logically linked to any buffer containing a cell received on said circuit while the data packet from which said received cell was divided has not been fully transmitted.
6 more elements
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) scheduling said cells for transmission on said transmit physical path;
- and
- (f) transmitting said cells according to said logical linking, further comprising the processes of extracting the first cells from said received data packets and placing said first cells in a register for pipelined processing with rotating send and receive pointers to a representation of the register such that when said receive pointer comes within a certain predefined distance of said transmit pointer, extraction is suspended.
4 more elements
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) scheduling said cells for transmission on said transmit physical path;
- (f) transmitting said cells according to said logical linking;
- and
- (g) maintaining a transmit context table with entries for each circuit holding respective counts of transmit credits, wherein said transmission is performed over a circuit only if the transmit context table entry for said circuit contains adequate transmit credits.
5 more elements
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) scheduling said cells for transmission on said transmit physical path;
- and
- (f) transmitting said cells according to said logical linking,
- wherein said receiving and transmitting are distributed between two or more media-independent interface integrated circuits each with multiple ports and wherein said media-independent interface integrated circuits share a common resource;
- said process further comprising
- arbitrating among said media-independent interface integrated circuits by passing in a chain a single token detected as a logical difference between a single token input signal and a single token output signal;
- and
- connecting the single token output signal of one device to the signal token input of the next device, with the token output signal of the last device inverted then sent to the first device in the passing chain.
9 more elements
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) scheduling said cells for transmission on said transmit physical path;
- and
- (f) transmitting said cells according to said logical linking,
- wherein said scheduling is performed by logically linking packets with a queue, and when said queue is selected, dequeueing a packet at the head of the queue and transmitting said packet one cell at a time.
5 more elements
An apparatus for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said apparatus comprising:
- (a) a receiver;
- (b) a packet to cell parser;
- (c) data buffers;
- (d) pointers to data buffers;
- (e) pointers to buffer pointers;
- (f) means for setting pointers to link cells from the same packet;
- (g) a scheduler;
- (h) means for reassembling cells from the same packet;
- and
- (i) a transmitter,
- said apparatus further comprising circuitry to write a tag on one of said received cells, parsed from a data packet received by said receiver, identifying its source circuit and to maintain a receive circuit table with an entry for each circuit logically linked to any buffer containing a cell received on said circuit while the data packet from which said received circuit was parsed has not been fully received.
8 more elements
Apparatus for controlling the transmitting of information cells from a sender to a receiver buffer, and where said receiver transmits the information to a communication interface, where said cells are of different lengths up to a known maximum, and said receiver of said information has limited buffer size, comprising:
- a head pointer that traverses the buffer addresses as the information is emptied from the buffer and transmitted;
- a tail pointer that traverses the buffer addresses as the information is received by the buffer;
- a virtual tail pointer that traverses the empty buffer addresses in increments of maximum cell length;
- means for determining when the virtual pointer has traversed a maximum cell size of empty buffer addresses;
- responsive to the virtual tail pointer traversing a maximum empty cell size, means for signaling said sender that a cell may be sent to the receiver;
- means for determining if the cell received was short of the maximum length cell;
- and
- means for decrementing said virtual tail pointer with the shortfall.
5 more elements
A DRAM memory controller, said DRAM® for retrievably storing words, and wherein said DRAM® is organized into at least two memory banks, comprising:
- means for selecting words from a contiguous streams of words to be written into or read from said memory;
- means for accessing alternately a location in one bank of said memory followed by a location in another bank of said memory;
- means for breaking said stream of words into groups, whereby said groups are stored in or read from the at least two banks in an interleaved fashion between the at least two banks;
- and
- means for precharging one bank while the other bank is being accessed, in an alternating fashion corresponding to the interleaving fashion.
2 more elements
A process for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said process comprising:
- (a) receiving data packets on said receive physical path;
- (b) dividing into cells said data packets as received;
- (c) storing said cells in individual data buffers;
- (d) linking logically the location of each buffer containing a cell with the location of the buffer containing any immediately subsequent cell divided from the same data packet;
- (e) maintaining a table of pointers to said data buffers wherein each said pointer is associated with a linking pointer and said received cell logical linking is performed by setting the linking pointer associated with the pointer to said data buffer (a) to point to the pointer to said data buffer for said subsequent cell, if any, or else (b) to point to the pointer to the data buffer containing the first cell of said same data packet to form a ring of links pointing to the cell or cells of said same data packet;
- (f) scheduling said cells for transmission on said transmit physical path;
- and
- (g) transmitting said cells according to said logical linking.
5 more elements
An apparatus for flexibly connecting between a receive physical path and a transmit physical path the flow of data packets, said apparatus comprising:
- (a) a packet to cell parser;
- (b) data buffers at defined memory locations adapted to receive cell information from said parser;
- (c) pointers at defined memory locations to said memory locations of said data buffers;
- (d) resettable pointers at memory locations each associated with each said data buffer pointer;
- and
- (e) a controller adapted to set a resettable pointer associated with data buffer pointer to stored cell information received from said parser (a) to point to said data buffer pointer for a subsequent cell of the same data packet, if any, or else (b) to point to the pointer to the data buffer containing the first cell of said same data packet to form a ring of links pointing to the cell or cells of said same data packet.
3 more elements
Dependencies are inferred from the claim text.