FIELD OF THE INVENTION

The present invention relates to a method and a system for data processing system. In particular, the present invention relates to a method and a system for enabling dequeuing of data stored in a storage device.

BACKGROUND

Typical implementation of data storage on Integrated circuit (IC) chip is made by a queue structure that allows storing of the Head and Tail pointers on the memory residing on the chip, called as on-chip memory, while the Next pointers are embedded in the data. This way of implementing queue structures allows the on-chip data storage requirements to scale with the number of queues supported by ASIC (Application Specific Integrated Circuit) rather than the traffic patterns, packet sizes etc. However, access to data stored in such queue structures may be delayed due to data residing in the off-chip memory. For example, a delay is caused to access a second block of data since the first block of data has to be read before accessing the second block.
Latency of access is one of the characteristics of the memory (e.g. DDR''s have higher latencies of access compared to SRAM) and/or due to the system architecture (e.g. multiple clients sharing a given memory interface can lead to larger latencies). This delay limits the bandwidth of a port from where the data has to be fetched. To overcome the bandwidth limitations, existing solutions provide extra memory interfaces for pointers or extra on-chip memory. However the existing solutions scale with number of queues or packets, therefore making the implementation more expensive. Moreover, packets can be small or large in size and the packets originate from the same queue as well as from different queues, irrespectively.
Therefore there is a need for a system and method to enable dequeuing of data stored in a storage device in order to sustain the bandwidth of the ports.

SUMMARY OF THE INVENTION

Accordingly, the present invention provides a storage device configured to enable dequeuing of data. In one embodiment, the said storage device comprising a plurality of memory locations grouped together to form at least one 1st block; a plurality of memory locations grouped together to form a 2nd block; characterized in that: the 2nd block comprises at least one 3rd block; the at least one of the 1st block comprises a plurality of 5th blocks linked to each other by at least one explicit linkage; and each of the 5th blocks comprising a plurality of 6th blocks which are linked to each other by at least one implicit linkage and at least one of the 6th block contained in the at least one of the 1st block comprises at least one explicit linkage to the said at least one 3rd block.

In another embodiment of the present invention, the storage device comprises the said at least one 3rd block which in turn comprises at least one 4th block.

In yet another embodiment of the present invention, the storage device comprises the 3rd block which in turn comprises a plurality of 4th blocks linked to each other by at least one explicit linkage.

In still another embodiment of the present invention, the storage device comprises the 4th block comprising a plurality of 7th blocks which are linked to each other by at least one implicit linkage.

In one embodiment of the present invention, the storage device comprises at least one of the 4th block that comprises at least two explicit linkages, a first explicit linkage linking a first of the 4th block to a second of the 4th block and a second explicit linkage linking a first of the 4th block to a third of the 4th block.

In another embodiment of the present invention, the storage device comprises a non-self contained packet and in respect of a non-self contained packet, the data stored in the at least one of the 1st block comprises header related information.

In yet another embodiment of the present invention, the storage device comprises a self-contained packet and in respect of a self contained packet, the data stored in the at least one of the 1st block comprises the entire self contained packet.
In still another embodiment of the present invention, the storage device comprises a 2nd block and the data stored in the 2nd block represents body and tail related information of a packet.

Accordingly, the present invention provides a method to enable dequeuing of data stored in a storage device. In one embodiment, the said method comprising the steps of: reading data contained in a pre-selected first block of the 6th block contained in at least one of the 1st block; determining as to whether the data thus read in (b) comprises at least one of:
an explicit linkage to the at least one 3rd block;
an implicit linkage to a second block of the 6th block; and
an explicit linkage to at least one 5th block;
if presence of an explicit linkage to a 3rd block is detected in step (c), proceeding to reading data thus contained in the at least one 3rd block;
if presence of an implicit linkage is detected in step (c), proceeding to reading data thus contained in a second block of the 6th block; and
if presence of an explicit linkage to the at least one 5th block is detected in step (c), proceeding to reading data thus contained in the at least one 5th block.

In another embodiment of the present invention, the method receives a request for reading data prior to reading data, wherein the request comprises a request for reading data contained in one or plurality of 6th blocks.

In yet another embodiment of the present invention, the method determines if the request is to read data contained in one 6th block, detecting the presence of an explicit linkage to the at least one 3rd block in step (b).

In still another embodiment of the present invention, the method comprises reading data contained in the at least one 3rd block, in particular the method comprising reading data contained in the first block of the 4rth block.

In an embodiment of the present invention, the method comprises reading data contained in the first block of the 4rth block, in particular the method comprising reading data contained in a first block of a 7th block.

In another embodiment of the present invention, the method upon reading the data contained in the first block of the 7th block, determining as to whether the data thus read comprises at least one of:
an implicit linkage to the at least one 7th block;
an explicit linkage to a second block of the 4th block; and
an explicit linkage to a third block of the 4th block.

In yet another embodiment of the present invention, the method upon determining the presence of an implicit linkage to a 7th block, reading data thus contained in the at least one 7th block.

In still another embodiment of the present invention, the method upon determining the presence of an explicit linkage to a second block of the 4th block, reading data thus contained in the second block of the 4th block.

In one embodiment of the present invention, the method upon determining the presence of an explicit linkage to a third block of the 4th block, reading data thus contained in the third block of the 4th block.

In another embodiment of the present invention, the method upon determining if the request is to read data contained in a plurality of 6th blocks contained in a single 5th block, detecting the presence of the implicit linkage in step (b).

In yet another embodiment of the present invention, the method upon determining if the request to read data contained in a plurality of 6th blocks contained in two or more 5th blocks, detecting the presence of the explicit linkage in step (c).

Accordingly, the present invention provides a system to enable dequeuing of data stored in a storage device. In one embodiment, the said system comprising: a storage device as configured to enable dequeuing of data; and a data reader configured to enable dequeuing of data stored in a storage device.

BRIEF DESCRIPTION OF THE DRAWINGS
The features of the present invention are set forth with particularity in the appended claims. The invention itself, together with further features and attended advantages, will become apparent from consideration of the following detailed description, taken in conjunction with the accompanying drawings. One or more embodiments of the present invention are now described, by way of example only, with reference to the accompanied drawings wherein like reference numerals represent like elements and in which:

Figure 1 illustrates a simplified structural diagram of a storage device to enable dequeuing of data in accordance with an embodiment of the present invention.

Figure 2 illustrates a flowchart of the method to enable dequeuing of data stored in the storage device in accordance with one embodiment of the present invention.

Figure 3 illustrates a flowchart of the method of dequeuing data of a packet in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION
The present disclosure relates to a method and a system for enabling dequeuing of data stored in a storage device. More particularly, the disclosure relates to a system-on-a-chip VLSI product to store ordered data in an off-chip memory such as DDR. Data in the memory is interchangeably referred to as packet comprising one or more fragments. A fragment can be either a Head fragment, a Body fragment, or a Tail fragment. A packet can be a self-contained packet containing one fragment indicating the entire data in the fragment. A packet can be a non-self contained packet containing multiple fragments comprising one head fragment, one or more body fragments and a tail fragment.
The present subject matter relates to a system and a method that enables to sustain a dequeue rate in the presence of latencies of fetching the data or packet from the memory. This is achieved by issuing a dequeue request without waiting for the data for the first request to have received completely. Therefore, latency of access to the off-chip memory is sustained by issuing a number of dequeue requests without waiting for the completion of arrival of data of the first request.

Figure 1 illustrates a simplified structural diagram of a storage device 100 in accordance with an embodiment of the present invention.

In one embodiment, the storage device (interchangeably referred to as device) 100 is configured to enable dequeuing of data stored in the device 100. In one embodiment, the device 100 comprises a group of one or more 1st blocks of memory such as 11, 12, … , 1n (commonly referred to as block 1x), wherein each of the 1st block comprises a plurality of memory locations grouped together. In one embodiment, the block 1x is referred to as a Traffic Queue (TQ)- x, where ‘x’ denotes the identification number of the traffic queue. A plurality of traffic queues are mapped to a single transmitting communication connection or a transmitting port for dequeuing the packets stored in the device 100 to a receiving communication connection or a receiving port. The port can be for example, a network port like Gigabit Ethernet port. A scheduler selects the order in which the packets from different traffic queues are needed to be dequeued for a given port. In one embodiment, scheduling the order of selection of dequeuing packets is performed by the scheduler via a round robin scheduling method. In another embodiment, the scheduling is performed by the scheduler via any scheduling methods known in the art.
In one embodiment, each of the 1st block 1x comprises a plurality of 5th blocks such as 51, 52, …, 5n (commonly referred to as block 5x) linked to each other by an explicit linkage indicated as 8 in Fig.1. Each of the 5th block is a temporary buffer and a linkage from one buffer to another buffer is referred to as an explicit linkage 8 or a next pointer. Each of the 5th block comprises one or more 6th blocks such as 61, 62, …, 6n (commonly referred to as block 6x), each of the 6th blocks are referred to as fragments linked to each other by an implicit linkage indicated as 9 in Fig.1. Fragments within a buffer are stored in a contiguous manner, whereas the buffers are stored anywhere in the memory space in the device 100. The fragments in a buffer are linked implicitly in a sequential manner so that if the address of the buffer is known, then the addresses of all the fragments in that particular buffer is derived using the fragment offsets. In one embodiment, the fragment offset is the size of the fragment. Each fragment or block 6x stored in the at least one buffer (block 5x) is either a head fragment or a SCP fragment. The head fragment stores header related information such as the size of the packet and the number of fragment pointers or linkages those are available for that particular fragment, whereas the SCP fragment stores the entire data belonging to a packet.
The device 100 further comprises a plurality of memory locations grouped together to form a block 2. In one embodiment, the block 2 or 2nd block is a temporary buffer comprising one or more 3rd blocks such as 31, 32, …, 3n (commonly referred to as block 3x), the block 3x is a buffer configured to store all body/tail fragments excluding the head or SCP fragment of a packet. Each block 3x is interchangeably referred to as a headless floating packet storing body fragments and/or a tail fragment of the packet. Each of the 3rd blocks comprises one or more 4th blocks or buffers such as 41, 42, …, 4n (commonly referred to as block 4x) for storing fragments of the headless floating packet. Each of the block 4x comprises one or more 7th blocks such as 71, 72, …, 7n (commonly referred to as block 7x). Each block 7x is either a body fragment or a tail fragment. Fragments indicated as ‘E’ denotes an empty fragment which is neither a body fragment nor a tail fragment.
Two blocks of the 7th block contained in the block 4x are linked to each other by an implicit linkage 10 indicated in Fig. 1. For example, a block 7x is linked to a block 7y via an implicit linkage 10, if the blocks 7x and 7y are successively stored in the same 4th block. A block 4x comprises at least two explicit linkages. A first explicit linkage is a next pointer by which two blocks of 4th block in a 3rd block are linked to each other. For example, a block 4x is linked to a block 4y via an explicit linkage indicated as 11 in Fig. 1, if the blocks 4x and 4y are successively stored in the same 3rd block. A second explicit linkage is a next-to-next pointer by which two blocks of 4th block in a 3rd block are linked to each other. For example, a block 4x is linked to another block 4z via an explicit linkage indicated as 12 in Fig. 1, if the blocks 4x, 4y and 4z are stored successively in the same 3rd block.
In one embodiment, the one or more 6th blocks in the at least 1st block are linked to at least one 3rd block via an explicit linkage, indicated as 13 in Fig. 1. The implicit linkages 9, 10 and the explicit linkage 8, 11, 12 and 13 are set by an enqueuing process. The enqueuing process enables storing of received data or packets in the device 100 such that dequeuing of stored data enables sustaining of a dequeue rate in the presence of latencies of fetching the data or packet from the memory. In one embodiment, the enqueuing process is any known enqueuing process existing in the art. In another embodiment, the enqueue process is a process as described in the following paragraphs.
In one embodiment, the enqueue process is configured to store data or packets in the appropriate memory locations in the device 100. In particular, the enqueue process is configured to store the packets in the at least one traffic queue or at least one 1st block. As already described in the foregoing paragraphs, a packet is a collection of one or more fragments. In one embodiment, a packet is either a SCP or a non-SCP packet. The non-SCP packet comprises at least one head, one body and one tail fragment. When a packet to be enqueued is received, the packet is analyzed and determined as to whether the packet is a SCP or a non-SCP packet.
Enqueuing of a non-SCP packet into a traffic queue depends on the order of receiving the packet or fragments of the packet. For example, in one embodiment, the order of receiving the fragments of the packet is one or more body fragments, the tail fragment and the head fragment, known as Head-Is-Last (HIL) order. HIL order receives the head fragment only after receiving the body fragments and the tail fragment. When a body or tail fragment is received during the enqueue process, a reassembly queue ID or a port number on which the packet was received is stored in that body or tail fragment which identifies the corresponding reassembly queue or buffer for storing the fragments. If the fragment received is a tail fragment, the process of storing the fragments in the reassembly queue is complete once the tail fragment is stored.
Each of the body or tail fragment includes a fragment offset within the buffer. Fragments within the buffer belong to a single packet and size of the buffer is determined based on the number of fragments that can be stored in the buffer. When the fragments are stored in more than two buffers, a pointer to the next buffer (indicated as 11 in Fig.1) and a pointer to the next-to-next buffer (indicated as 12 in Fig.1) are added to the fragment based on their requirement. The reassembly queue storing the body fragments and the tail fragment is a headless floating packet, (indicated as 3rd block in Fig.1) as the reassembly queue do not store the corresponding head fragment. Finally according to HIL order of receiving fragments, the head fragment (6th block) arrives after arrival of the body and tail fragments and after the completion of packet processing by a packet processor. An explicit pointer to the 1st body fragment (1st block of 7th block) and the size of the packet stored in the reassembly queue are inserted into the head fragment. Following this, the head fragment is appended in the corresponding traffic queue specified by the packet processor. The head fragment thus appended includes an explicit linkage 13 to the headless floating packet 3rd block as shown in Fig.1
In another embodiment, the order of receiving the fragments of the packet is the head fragment, one or more body fragments, and the tail fragment, known as Head-Is-First (HIF) order. When the head fragment is received, a single buffer is allocated to store only the head fragment. Therefore when all the fragments are received, the head fragment is processed by the packet processor to identify the traffic queue to which the head fragment is to be enqueued.
Enqueuing of a SCP packet into a traffic queue is similar to enqueuing of the head fragment. However there is no explicit pointer to the 3rd block or headless floating packet as the SCP packet do not have any body or tail fragment.

Figure 2 illustrates a flowchart of the method 200 to enable dequeuing of data stored in the storage device in accordance with one embodiment of the present invention.
The method 200 (shown in Figures 2 and 3) enables the dequeuing of data stored in the storage device 100 following an enqueue process. In one embodiment, the enqueue process can be a process for storing packets with head fragments in the traffic queue and body and/or tail fragments in a headless floating packet as illustrated in Fig.1. In another embodiment, the enqueue process can be a well known enqueue process known in the art. The method 200 for dequeuing of data or packets stored in the device 100 begins at block 210.
At block 210, receiving a request for reading data contained in at least one 6th block. For example, a request for dequeuing data or packet stored in the device 100 is issued by a scheduler, the request comprises request for reading data contained in one fragment such as one 6th block or a plurality of 6th blocks. The scheduler selects the order in which the packets from different traffic queues are dequeued for a given port. In one embodiment, scheduling the order of selection of dequeuing packets is performed by the scheduler via a round robin scheduling method. In another embodiment, the scheduling is performed by the scheduler via any scheduling methods known in the art. Following the selection of the packets to be dequeued, the scheduler issues a dequeue request with a specified traffic queue id for dequeuing the data from the specified traffic queue –x. The dequeue request thus received for reading the data or packet such as the 6th block stored in the traffic queue- x (for example, block 11).
At block 220, reading data from a pre-selected 6th block of at least one 1st block. In one embodiment, data or packet pre-selected by the scheduler is a 6th block of at least one 1st block or traffic queue –x. In response to receiving the request for reading data contained in the pre-selected 6th block, a data reader or any data reading device reads the head/SCP fragment stored in the 6th block. The head fragment stores header related information such as the size of the packet and the number of fragment pointers or linkages (such as explicit and implicit linkages) those are available for that particular fragment, whereas the SCP fragment stores the entire data belonging to a packet.
One or more head/SCP fragment such as the 6th block stored in a buffer such as 5th block are stored in a contiguous manner, whereas the buffers are stored anywhere in the memory space in the device 100. The fragments in a buffer are linked implicitly in a sequential manner so that if the address of the buffer is known, then the addresses of all the fragments in that particular buffer is derived using the fragment offsets. In one embodiment, the fragment offset is the size of the fragment.
At block 230, determining as to whether an explicit linkage is present or not. In an embodiment, the method 200 determines as to whether an explicit linkage or an implicit linkage is present in the 6th block read by the data reader. In particular, the method 200 determines as to whether the currently read 6th block is either a head fragment or a SCP fragment. If the determination of presence of an explicit linkage is not made, then the presence of an SCP fragment (indicated as SCP in Fig.1) in the currently read 6th block and the presence of an implicit linkage (such as 9, shown in Fig.1) from the SCP fragment to the next fragment (or the next 6th block) is detected, thus the method 200 proceeds from block 230 to block 240 (via the “NO” path). If the determination of presence of an explicit linkage (such as 8 or 13 shown in Fig.1) is made, then the method 200 proceeds from block 230 to block 250 (via the “YES” path).
At block 240, reading data from a second block of the 6th block of at least one 1st block. In one embodiment, based on the determination of presence of the implicit linkage (such as 9, shown in Fig.1) in one block of the 6th block, indicating that the one block of the 6th block is a SCP fragment and the request comprises request for reading data contained in a plurality of 6th blocks within a single 5th block, the method 200 proceeds from block 230 to block 240 via the “NO” path. The method 200 enables the data reader to read data thus contained in the second or next block of the 6th block (such as 63, shown in Fig.1). Data thus contained in the second or next block of the 6th block is read and the method 200 proceeds to block 230 for determination of linkages or pointers in the currently read 6th block to continue dequeuing of data as requested by the scheduler.
At block 250, determining as to whether an explicit linkage to 3rd block is present or not. For example, the method 200 determines as to whether an explicit linkage to at least one 3rd block is present in the 6th block to enable read by the data reader. If the determination of presence of an explicit linkage to the at least one 3rd block is not made, then it implies that presence of an explicit linkage (such as 8, shown in Fig.1) to the next buffer or 5th block is made, and the method 200 proceeds from block 250 to block 260 (via the “NO” path). If the determination of presence of an explicit linkage to the at least one 3rd block (such as 13 shown in Fig.1) is made, then the method 200 proceeds from block 250 to block 270 (via the “YES” path).
At block 260, reading data contained in a next 5th block of at least one 1st block. In one embodiment, based on the determination of presence of the explicit linkage (such as 8, shown in Fig.1) to the next buffer or 5th block, indicating that the request comprises request for reading data contained in a plurality of 6th blocks present in two or more 5th blocks, the method 200 proceeds from block 250 to block 260 via the “NO” path. The method 200 enables the data reader to read data thus contained in the second or next block of the 5th block (such as 52, shown in Fig.1). Data thus contained in the second or next block of the 5th block is read in the block 220 and the method 200 continues the reading data contained in the 6th block as requested by the scheduler.
At block 270 (as shown in Fig.3), reading data contained in a 4th block of at least one 3rd block. In one embodiment, based on the determination of presence of the explicit linkage (such as 13, shown in Fig.1) to the 3rd block, indicating that the first block of the 4th block in the at least one 3rd block is to be dequeued, the method 200 proceeds from block 250 to block 270 via the “YES” path. The method 200 enables the data reader to read data thus contained in the 4th block of the 3rd block (such as 41, shown in Fig.1). Data thus contained in the 4th block of the 3rd block such as 71 is read in the block 270.
At block 280, determining as to whether an explicit linkage is present or not. In an embodiment, the method 200 determines as to whether an explicit linkage or an implicit linkage is present in the 7th block thus read by the data reader. If the determination of presence of an implicit linkage (such as 10, shown in Fig.1) linking one 7th block to the next 7th block is detected, then the method 200 proceeds from block 280 to block 290 (via the “NO” path). If the determination of presence of an explicit linkage (such as 11 or 12 shown in Fig.1) is made, then the method 200 proceeds from block 280 to block 300 (via the “YES” path).
At block 290, reading data from a next block of the 7th block of at least one 3rd block. In one embodiment, based on the determination of presence of the implicit linkage (such as 10, shown in Fig.1) in one block of the 7th block, indicating the presence of next 7th block, where 7th block is either a body/tail fragment, the method 200 proceeds from block 280 to block 290 via the “NO” path. The method 200 enables the data reader to read data thus contained in the next block of the 7th block (such as 72, shown in Fig.1). Data thus contained in the next block of the 7th block is read and the method 200 proceeds to block 280 for determination of linkages or pointers in the currently read 7th block to continue dequeuing of data as requested by the scheduler.
At block 300, determining as to whether an explicit linkage to second block of the 4th block is present or not. For example, the method 200 determines as to whether an explicit linkage to second block of the 4th block is present in the 7th block. If the determination of presence of an explicit linkage to the second block of the 4th block is present is not made, then it implies that presence of an explicit linkage (such as 12, shown in Fig.1) to the third block of the 4th block is made, and the method 200 proceeds from block 300 to block 310 (via the “NO” path). If the determination of presence of an explicit linkage to the second block of the 4th block is present (such as 11 shown in Fig.1) is made, then the method 200 proceeds from block 300 to block 320 (via the “YES” path).
At block 310, reading data contained in a third block of the 4th block. In one embodiment, based on the determination of presence of an explicit linkage or a next-to-next pointer (such as 12, shown in Fig.1) to the third block of the 4th block is made, and the method 200 proceeds from block 300 to block 310 (via the “NO” path). The method 200 enables the data reader to read data thus contained in the third block of the 4th block (such as 43, shown in Fig.1). Data thus contained in the third block of the 4th block is read in the block 310 and the method 200 continues the reading data contained in the 4th block as requested by the scheduler.
At block 320, reading data contained in a second 4th block of at least one 3rd block. In one embodiment, based on the determination of presence of the explicit linkage or next pointer (such as 11, shown in Fig.1) to the second block of the 4th block is made, and the method 200 proceeds from block 300 to block 320 (via the “YES” path). The method 200 enables the data reader to read data thus contained in the second block of the 4th block (such as 42, shown in Fig.1). Data thus contained in the second block of the 4th block is read in the block 320 and the method 200 continues the reading data contained in the 4rth block as requested by the scheduler.
The method 200 proceeds from block 270 till all the 7th blocks in the at least one 3rd block is read completely indicating the dequeuing of a complete packet from the traffic queue or 1st block. Next-to-next pointer or the explicit linkage to the third block of the 4th block enables dequeuing of 7th blocks from the third block. In parallel next pointer or the explicit linkage to the second block of the 4th block enables dequeuing of 7th blocks from the second block. Therefore the waiting time for the completion of dequeuing of 7th blocks from the second block is utilized by dequeuing of 7th blocks from the third block simultaneously. This reduces the latencies of fetching data from memory, therefore sustaining the dequeue rate and high bandwidth for a given port.
In one embodiment, a system to enable dequeuing of data includes the device 100 for storing data and the data reader for dequeuing data stored in the device 100 by implementing the method 200 already explained in the above paragraphs.
While the particular preferred embodiments of the present invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications may be made without departing from the teachings of the invention. It is therefore contemplates that the present invention cover any and all modifications, variations or equivalents that fall within the scope of the basic underlying principles disclosed above and claimed herein.


WE CLAIM:

1. A storage device (100) configured to enable dequeuing of data, said storage device (100) comprising:
a plurality of memory locations grouped together to form at least one 1st block;
a plurality of memory locations grouped together to form a 2nd block;
characterized in that:
the 2nd block comprises at least one 3rd block;
at least one of the 1st block comprises a plurality of 5th blocks linked to each other by at least one explicit linkage; and each of the 5th blocks comprising a plurality of 6th blocks which are linked to each other by at least one implicit linkage and at least one of the 6th block contained in the at least one of the 1st block comprises at least one explicit linkage to the said at least one 3rd block.

2. The storage device as claimed in claim 1, wherein the said at least one 3rd block comprises one 4th block.

3. The storage device as claimed in claim 1, wherein the said 3rd block comprises a plurality of 4th blocks.

4. The storage device as claimed in claim 1, wherein when the said 3rd block comprises “n” number of 4th blocks, at most of “n-1” explicit linkages are present between the said “n” number of 4th blocks.

5. The storage device as claimed in claim 4, wherein if the number “n-1” is equal to or greater than 2, a first of the said at least two explicit linkages linking a first 4th block to a second 4th block, a second of the said at least two explicit linkages linking a second 4th block to a third 4th block.

6. The storage device as claimed in any of claims 2 or 3, wherein the 4th block comprising a plurality of 7th blocks which are linked to each other by at least one implicit linkage.

7. The storage device as claimed in claim 1, wherein in respect of a non-self contained packet, the data stored in the at least one of the 1st block comprises header related information.

8. The storage device as claimed in claim 1, wherein in respect of a self contained packet, the data stored in the at least one of the 1st block comprises the entire packet.

9. The storage device as claimed in claim 1, wherein the data stored in the 2nd block represents body and tail fragments of a packet.

10. The storage device as claimed in claim 1, wherein each of the 6th block contains either a header fragment of a packet or a SCP packet; the 2nd block comprises headless body fragments and/or tail fragments.

11. A method of dequeuing data stored in a storage device as claimed in claim 1, said method comprising the steps of:
• receiving a plurality of header requests, wherein the headers are stored in at least one 1st block;
• reading header data corresponding to each of the said plurality of header requests, wherein each of the header data is stored in a separate 6th block in the said at least one 1st block;
• transmitting each of the header data thus read; and
• based on the data thus contained in each of the “n” number of 6th blocks, receiving further requests for reading data.

12. The method as claimed in claim 11, wherein a second of the header request is receivable prior to transmission of the header data in respect of the first header request.

13. The method as claimed in claim 11, wherein the plurality of the header requests thus received can correspond to headers, all of which are stored in a single first block.

14. The method as claimed in claim 11, wherein the plurality of the header requests thus received can correspond to headers, no two of which are stored in a single first block.

15. The method as claimed in claim 11, wherein the plurality of the header requests thus received can correspond to headers, some of which are stored in a single first block.

16. The method as claimed in claim 11, wherein the data thus contained in a particular 6th block thus read indicates presence of only a tail fragment in the 2nd block.

17. The method as claimed in claim 11, wherein the data thus contained in a particular 6th block thus read indicates presence of a tail fragment and at least one body fragment in the 2nd block.

18. The method as claimed in claim 11, wherein the data thus contained in a particular 6th block thus read indicates absence of both of the tail fragment and a body fragment in the 2nd block.

19. The method as claimed in claim 11, wherein the data thus contained in a particular 6th block thus read can indicate any of the following:

20. A method of dequeuing data stored in a storage device as claimed in claim 1, said method comprising the steps of:
(a) reading data contained in a 6th block contained in a pre-selected 1st block;
(b) determining as to whether the data thus read in (a) comprises at least one of:
i. an explicit linkage to the at least one 3rd block;
ii. an implicit linkage to a second block of the 6th block; and
iii. an explicit linkage to at least one 5th block;
(c) if presence of an explicit linkage to a 3rd block is detected in step (b), proceeding to reading data thus contained in the at least one 3rd block;
(d) if presence of an implicit linkage is detected in step (b), proceeding to reading data thus contained in a second block of the 6th block; and
(e) if presence of an explicit linkage to the at least one 5th block is detected in step (b), proceeding to reading data thus contained in the at least one 5th block.

21. The method as claimed in claim 10, wherein each of the 6th block contains either a header fragment of a packet or a SCP packet; the 2nd block comprises headless body fragments and/or tail fragments.

22. The method as claimed in claim 10, wherein a method of dequeuing a packet having a header fragment stored in a 6th block of a single 1st block comprises the steps of:
(a) receiving a request for reading a 6th block contained in a 1st block;
(b) reading data contained in the said 6th block;
(c) determining as to whether the data thus read contains an explicit linkage to a 3rd block; and
(d) proceeding to read data thus contained in the said 3rd block, if an explicit linkage to the said 3rd block is detected.

23. The method as claimed in claim 10, wherein the method of successively dequeuing two packets having respective header fragments stored in two successive 6th blocks of a single 5th block comprises the steps of:
(a) receiving a request for reading a first 6th block contained in the said 5th block;
(b) receiving a request for reading a second 6th block contained in the said 5th block, wherein said request is sent based on an implicit linkage; and
(c) reading data contained in the said first said 6th block followed by reading data contained in the said second said 6th block.

24. The method as claimed in claim 10, wherein reading data contained in the at least one 3rd block comprising reading data contained in a first 7th block contained in a first 4rth block.

25. The method as claimed in claim 14, wherein upon reading the data contained in the first block of the 7th block, determining as to whether the data thus read comprises at least one of:
i. an implicit linkage to the at least one 7th block;
ii. an explicit linkage to a second block of the 4th block; and
iii. an explicit linkage to a third block of the 4th block.

26. The method as claimed in claim 15, wherein upon determining the presence of an implicit linkage to a 7th block, reading data thus contained in the at least one 7th block.

27. The method as claimed in claim 15, wherein upon determining the presence of an explicit linkage to a second block of the 4th block, reading data thus contained in the second block of the 4th block.

28. The method as claimed in claim 15, wherein upon determining the presence of an explicit linkage to a third block of the 4th block, reading data thus contained in the third block of the 4th block.

Dated 31st day of December 2008

G. Deepak Sriniwas
Of K & S Partners
Attorney for the Applicants

ABSTRACT

SYSTEM AND METHOD TO ENABLE DEQUEUING OF DATA STORED IN A STORAGE DEVICE

The present invention relates to a method and a system to enable dequeuing of data stored in a storage device. In one embodiment, a storage device (100) is configured to store data with implicit and explicit linkages such as next and next-to-next pointers included within the data. The explicit linkages enable dequeuing of data from a buffer without waiting for the dequeuing of data from the first buffer to complete. Therefore, such dequeuing mechanism reduces the access latencies of fetching data from the device (100) and thus sustaining the bandwidth of a dequeue port.

Figure 1.