FIELD OF THE INVENTION

The present invention relates to a method and a system for data processing. In particular, the present invention relates to a method and a system-on-a-chip VLSI product for enabling transmission of packet 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 data. However, access to data stored in such queue structures may be delayed due to next pointers 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.
Memory latency is one of the important performance bottlenecks in modern communication systems. Latency of access may occur due to 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 latency limits the bandwidth of a device output port to which the data is transmitted or fetched from. To overcome the bandwidth limitations, existing solutions provide pipelining of data dequeue requests to the memory such that the pipelining can reduce the impact of the latency of memory access, thus enabling to sustain the required bandwidth for a port. However, the said pipelining of dequeue requests may result in data fragments being read and received from the memory device in an order different from the order in which the data must be sent out on the network interface.
Therefore there is a need for a method and a system that enables to send out the data on the network interface in the correct order, even though the mechanism to reduce the impact of latencies of DDR access on the throughput may result in data being read from the DDR in a different order.

SUMMARY OF THE INVENTION

Accordingly, the present invention describes a storage device for enabling transmission of a packet stored in the storage device, said storage device comprising a plurality of memory locations grouped together to form at least one 1st block, each of the 1st block comprises one 2nd block and one 3rd block; the said 2nd block comprising a plurality of 4th blocks; and the said 3rd block comprising a plurality of 5th blocks, characterized in that data stored in a 4th block comprise header data and data stored in one or more 5th blocks comprise body and/or tail data corresponding to header data stored in the 4th block.
In one embodiment of the present invention, the storage device comprises the header stored in a 4th block for a packet or a SCP packet.
Accordingly, the present invention describes a method for retrieval of a packet from an external storage device for enabling transmission of the said packet, said method comprising the steps of: determining availability of an opportunity to read a body/tail fragment of the packet; if the opportunity to read a body/tail fragment is available, issuing a request to an external storage device for reading the said body/tail fragment of the packet; if the opportunity to read a body/tail fragment is not available, determining as to whether an opportunity to read a header fragment of a packet is available; and issuing a request to the external storage device for reading the said header fragment of the packet if an opportunity to read a header fragment is available.
In one embodiment of the present invention, the opportunity to read a body/tail fragment of the packet is determined to be available if a pointer to a body/tail fragment is available; and an empty 5th block is present in the 3rd block.
In one embodiment of the present invention, the said pointer to a body/tail fragment is available if: a corresponding head fragment is present in a 4th block; and the head fragment thus present is not an SCP.
In one embodiment of the present invention, the said pointer to a body fragment is available if an earlier body fragment is received.
In one embodiment of the present invention, in respect of a request issued to an external storage device for reading an ith body/tail fragment, receiving and storing the ith fragment in 5ith block.
In one embodiment of the present invention, the opportunity to read a header fragment of the packet is determined to be available if an empty 4th block is present in the 2nd block; and an address in the external storage device from which the head/SCP fragment is to be read is available.
In one embodiment of the present invention, in respect of a request issued to an external storage device for reading an ith head fragment, receiving and storing the ith fragment in 4ith block.
In one embodiment of the present invention, the method further comprises transmitting a token indicating availability of contiguous fragments for transmission.
In one embodiment of the present invention, the said token further indicates the total number of fragments available for transmission.
In one embodiment of the present invention, the said token is transmitted only when the token indicates availability of data that is in continuation of the previously available data, so as to enable in-order transmission of data.
In one embodiment of the present invention, the said token is transmitted if: number of contiguous fragments stored exceeds a predetermined threshold value; and/or the tail fragment is stored in a 5th block and/or contiguous fragments stored belong to an ongoing packet for which at least one token has been transmitted previously.
In another embodiment of the present invention, the method further comprising transmitting a token indicating availability of a fragment for transmission if: a head fragment is present in a 4ith block; and the head fragment thus present is for an SCP.
In one embodiment of the present invention, a token thus transmitted comprises: contiguous fragments belonging to a particular packet; contiguous fragments belonging to a first packet and a header fragment of at least one SCP; contiguous fragments belonging to a first packet and contiguous fragments belonging to at least one further packet; a header fragment of a SCP and contiguous fragments belonging to at least one further packet; or header fragments of a plurality of SCPs.
In one embodiment of the present invention, the method further comprising: in response to transmission of the token, receiving a request for fragments from an egress port; and transmitting available contiguous fragments in response to the said fragment request.
Accordingly, the present invention describes an apparatus for enabling transmission of a packet stored in a storage device, said apparatus comprising: a processing component (PC) configured to retrieve data constituting the packet from an external storage device; a buffering component (BC) for storing data thus retrieved prior to transmission of said data; wherein said processing component retrieves said data by: determining availability of an opportunity to read a body/tail fragment of said packet; if the opportunity to read a body/tail fragment is available, issuing a request to the external storage device for reading the said body/tail fragment of the packet; if the opportunity to read a body/tail fragment is not available, determining as to whether an opportunity to read a header fragment of the packet is available; and issuing a request to the external storage device for reading the said header fragment of the packet if the said opportunity to read the header fragment is available.
In another embodiment of the present invention, the said BC and said PC form part of a buffering and processing component (BPC).
In one embodiment of the present invention, the BPC is operatively connected to at least one port via a port interface.
In one embodiment of the present invention, the BPC is operatively connected to a queue scheduler for enabling sequencing of requests for data received for the said at least one port.
In one embodiment of the present invention, the sequencing is performed on a port-by-port basis, if the BPC is operatively connected to a plurality of ports.
In one embodiment of the present invention, the apparatus further comprising a storage of Queue numbers scheduled by the queue scheduler for the said at least one port, communicatively connected to BPC.
In one embodiment of the present invention, the said PC is configured to store a fragment read from the external storage device in the said BC.
In one embodiment of the present invention, the said PC transmits a token to the port whenever a sufficient number of contiguous fragments are available in BC.
In one embodiment of the present invention, the said token further indicates the total number of fragments available for transmission.
In one embodiment of the present invention, the said PC receives the fragment request from the port in response to transmission of the said token and further transmits the contiguous fragments available for transmission.

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 an exemplary functional block diagram of a system that enables transmission of packets to egress ports according to one embodiment of the present invention.

Figure 2 illustrates an exemplary structure of buffering component in accordance with one embodiment of the present invention.

Figure 3A, 3B, and 3C illustrates exemplary examples illustrating logical order of accessing buffering component in accordance with various embodiments of the present invention.

Figure 4 illustrates a flowchart of the method of enabling transmission of a packet in accordance with an embodiment of the present invention.

Figure 5 illustrates a flowchart of the method of reading body/tail fragment of a packet in accordance with an embodiment of the present invention.

Figure 6 illustrates a flowchart of the method of reading head fragment of a packet in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

The present disclosure relates to a system and a method for enabling transmission of data stored in the storage device in the correct order in which the data must be sent out on the network interface. More particularly, the disclosure relates to an interface that issues a plurality of requests to read ordered data from an off-chip memory such as DDR. Data constituting packets thus read are stored in the storage device (data interchangeably referred to as fragments). A fragment can be either a Head fragment, a Body fragment, or a Tail fragment. A packet can be a self-contained packet (SCP) containing one fragment indicating the entire data in the packet. A packet can be a non-self contained packet (non-SCP) containing multiple fragments comprising one head fragment, optionally one or more body fragments, and a tail fragment.
Further, the interface stores the fragments thus read in a storage device such as an on-chip memory and transmits the stored fragments in the correct order such that fragments of at least two different packets do not mix with each other. This is achieved by transmitting the contiguous fragments of a first packet followed by contiguous fragments of a second packet, after the end of the first packet and so on. Therefore, the aspect of pipelining read requests in the correct order and transmitting a sufficient number of contiguous fragments in the order avoids mixing of fragments from two different packets and also ensures that under no circumstances intra-packet under-runs are created. Further the aspect of issuing at least one read request without waiting for the receipt of data in respect of the previously issued request assists in maximizing the utilization of the DDR interface and improves the data throughput of the overall system.

Figure 1 illustrates an exemplary functional block diagram of a system 100 that enables transmission of packets to egress ports according to one embodiment of the present invention.
In one embodiment, the system 100 includes an interface 102 communicatively connected to one or more egress ports 104-1, 104-2,.., 104-N (commonly referred to as ports 104), an external storage (interchangeably referred to as DDR) 106, and Queue scheduler (QS) 108. The interface 102 includes an external storage interface (interchangeably referred to as DDR interface) 110 communicating with the DDR 106, a buffering and processing component (BPC) 112, and a queue scheduler interface (QSI) 114 communicating with QS 108. The interface 102 further includes Queue ID (QID) storage 116 operatively connected to QS 108 and BPC 112. QID storage stores sequence of queue identification numbers (QIDs) of queues indicating the order in which the packets must be read for each port 104.
The interface 102 further includes a port interface 118 communicatively connected to BPC 112. BPC 112 comprises a buffering component (BC) 120 and a processing component (PC) 122. BC 120 is a storage device that comprises a group of buffers maintained for each port, each group of buffers includes a head buffer and a body buffer. The head buffer is configured to store a plurality of header fragments and the body buffer is configured to store a plurality of tail and/or body fragments. The structure of BC 120 is explained in figure 2 described below.
PC 122 is configured to pipeline and issue one or more requests for reading data from DDR 106 when requested by the port interface 118. PC 122 is also configured to receive and store the data thus read from DDR 106 in BC 120. Further, PC 122 is configured to dispatch the data thus available in BC 120 in the correct order to the requesting port 104.
In one embodiment, an egress port 104 would issue a data request to the interface 102 based on tokens. The data request is serviced from the data stored in the BC 120. The port interface 118 in the interface 102 receives the request and determines the presence of opportunities for issuing DDR requests for the port 104. For a given port, there is a max count of the requests that can be outstanding. For each request issued, this count is decremented. For each Fragment that is actually transmitted to the port 104, this count is incremented. All the ports that have non-zero counts are scheduled for DDR request opportunity in a manner such as a weighted round robin manner.
QSI 114 determines the availability of space in the QID storage 116 for storing QIDs corresponding to the port 104. If the availability of space is determined, then the QSI 114 issues a request for a QID to the QS 108. The number of pending requests to the scheduler QS 108 is restricted to a maximum of number of Queue ID’s that can be stored for that port 104. The mechanism to decide when a request is issued to scheduler is for e.g. a round robin at start and thereafter, each time a Tail or SCP is received, a request is issued to QS 108 for that port 104. The QS 108 responds to the pending request any time later whenever the QS 108 determines the presence of a packet in a queue that can be scheduled. QID of the queue that can be scheduled is then responded to the interface 102 and stored in the QID storage 116 for the port 104.
After the determination of the availability of an opportunity to make DDR request for the port 104, the port interface 118 forwards the data request to PC 122. PC 122 determines availability of an opportunity to issue a request for reading a body/tail fragment from the DDR 106. In one embodiment, PC 122 determines the availability of an opportunity to read a body/tail fragment based on the presence of a pointer to the body/tail fragment to be read, and presence of an empty body buffer in BC 120 for storing the fragment thus read. If the presence of the pointer to body/tail fragment and presence of an empty body buffer is determined, then PC 122 issues a request for reading data. In particular, PC 122 issues requests for reading data associated with the queue having QID selected from the sequence. After the issue of requests, PC 122 updates states information such as pointer to the next buffer, offset of the next fragment within the buffer and the status of the packet completion etc.
On the other hand, if PC 122 determines that the opportunity to issue a read request for a body/tail fragment is not available, then PC 122 determines availability of an opportunity to issue a request for reading a head fragment from DDR 106. In one embodiment, PC 122 determines the availability of an opportunity to issue a read request for a head fragment based on the presence of a pointer to the head fragment to be read, and presence of an empty head buffer in the BC 120 for storing the fragment thus read. Requests for reading head fragments from the queue having the selected QID is pipelined and issued in the order in which the header fragments are stored in the selected queue such that request for a second header is issued only after the request for first or previous header is issued.
If PC 122 determines that the opportunity to issue a read request for a head fragment or a body/tail fragment is not available, then PC 122 goes into an idle state. The aspect of issuing a read request for a head fragment of a subsequent packet when the read request for a body/tail fragment cannot be made reduces the impact of latency and therefore supports high bandwidth for the port even in the case when the packets may be small in size.
When PC 122 receives the fragment thus read from DDR 106, PC 122 stores the fragment in the respective buffer available in BC 120. If a sufficient number of contiguous fragments are available in BC 120, PC 122 transmits at least one token to the requested port 104, each token indicating the availability of the fragments. PC 122 transmits the token to the requested port 104 via the port interface 118. In one embodiment, the token indicates the total number of contiguous fragments available for transmission. The port 104 receives the token and issues a further request for transmission of fragments available in BC 120.
PC 122 transmits a token when PC 122 determines that the number of contiguous fragments thus stored exceeds a predetermined threshold value and/or if a tail fragment is available in the BC 120 and/or contiguous fragments thus stored belong to an ongoing packet for which at least one token has been transmitted previously. If the tail fragment is not still available, the PC 122 transmits a further token for transmission of one or more contiguous body/tail fragments available in BC 120. The aspect of transmitting contiguous fragments thus available in BC 120 ensures that the fragments of a packet are transmitted to the port 104 in the correct order in which the fragments have been requested from DDR. Also, the aspect of transmitting a sufficient number of fragments available ensures that intra packet under-runs are not created. Therefore the interface 102 enables the transmission of packets out to the ports in the correct order and also supports high bandwidth.

Figure 2 illustrates an exemplary structure of a buffering component in accordance with one embodiment of the present invention.
In one embodiment, BC 120 comprises a plurality of memory locations grouped together to form at least one 1st block such as 11, 12, 13.., one 1st block for each port 104. Each of the 1st blocks comprises a 2nd block (also referred to as the head buffer) and a 3rd block (also referred to as the body buffer). 2nd block comprises a plurality of 4th blocks such as 41, 42, 43, .., and 3rd block comprises a plurality of 5th blocks such as 51, 52, 53,... The number of 4th blocks or number of 5th blocks are determined as ‘L’ such that the aspect of issuing ‘L’ read requests reduces the impact of the latency of the memory access for a port 104. Data stored in a 4th block comprise header data whereas data stored in a 5th block comprise body and/or tail data corresponding to header data stored in the 4th block.
In one embodiment, PC 122 issues a request for reading a fragment from DDR 106. A request includes metadata such as at least a pointer to an empty 4th block or a pointer to an empty 5th block where the fragment is stored, type of the fragment such as either head or body and PID of the port for which the fragment is read. In one embodiment, PC 122 issues a request for reading body/tail fragment based on the availability of an empty 5th block and pointer to the body/tail fragment that is to be read. A pointer to the first body or a tail fragment is available if a corresponding head fragment is available in a 4th block and the said head fragment is for a non-SCP. A pointer to the subsequent body fragment is available if the previous body fragment is available in the 3rd block.
Further PC 122 allocates an empty 5th block for storing the fragment for which the request is issued. When the fragment is received from DDR 106, PC 122 allows the received fragment to be stored in the allocated 5th block. Therefore in respect of a request issued to DDR 106 for reading an ith body/tail fragment, PC 122 receives and stores the ith fragment in 5ith block.
If availability of an empty 5th block or pointer to body/tail fragment is not determined, then a request for reading head fragment is issued. PC 122 issues a request to DDR 106 for reading a head fragment from the selected queue. In one embodiment, PC 122 issues the read request based on the availability of an empty 4th block and pointer to the head fragment that is to be read. Further PC 122 allocates an empty 4th block for storing the fragment for which the request is issued. When the fragment is received from DDR 106, PC 122 allows the received fragment to be stored in the allocated 4th block. Therefore in respect of a request issued to DDR 106 for reading an ith head fragment, PC 122 receives and stores the ith fragment in 4ith block. PC 122 further determines whether the head fragment thus stored is for an SCP or for a non-SCP. If the head fragment is determined for an SCP, PC 122 issues request for reading the next head fragment from the DDR 106. If the head fragment is determined for a non-SCP then PC 122 issues requests for reading the corresponding tail and/or body fragments.
If sufficient number of fragments is available in the 1st block and/or the tail fragment is available and/or contiguous fragments thus stored belong to an ongoing packet for which at least one token has been transmitted previously, then PC 122 generates and transmits a token to the port and triggers the transmission process. After the fragments are transmitted, buffers are freed up for storing further fragments.

Figure 3A, 3B, and 3C illustrates exemplary examples illustrating logical order of accessing buffering component in accordance with various embodiments of the present invention.
Fig 3A illustrates a logical order in which the fragments are transmitted out to the ports 104. In the figure, a head fragment is stored in a 42 block and the corresponding body/tail fragments are stored in the 5th blocks. For example, the first body fragment is stored in block 52 and the subsequent fragments are stored in blocks 53 , 54 , and 51. The solid arrows in the figure establish the order in which the fragments are stored in BC 120. The order in which the fragments are transmitted in response to requests from the ports 104 is H-B0-B1-B2-B3-B4-B5-….
Fig 3B shows two head fragments H and H` stored in blocks 42 and 43 respectively. Body/tail fragments corresponding to the header H (stored in block 42) are stored in the 5th blocks. For example, the first body fragment is stored in block 53 and the subsequent fragments are stored in blocks 54, 51, and 52. The solid arrows in the figure establish the order in which the fragments are stored in BC 120. Body/tail fragments corresponding to the next header H` stored in block 43 are stored with the first body fragment being stored in block 52 and the subsequent fragments are stored in blocks 53, 54, and 51. The order in which the fragments are transmitted in response to requests from the ports 104 is H-B0-B1-T-H`-B0`-B1`-B2`-….
Fig 3C shows three fragments H, SCP and H` stored in blocks 42,43 and 44 respectively. In the figure, the first head fragment (H) is stored in a 42 block and the corresponding body/tail fragments are stored in the 5th blocks. For example, the first body fragment is stored in 53 and the subsequent fragments are stored in blocks 54, 51, and 52. The solid arrows in the figure establish the order in which the fragments are stored in BC 120. The next fragment stored in block 43 is a header for a SCP and therefore no body/tail fragments are stored in the 5th blocks. Further, body/tail fragments corresponding to the next header H` stored in block 44 are stored with the first body fragment being stored in block 52 and the subsequent fragments are stored in blocks 53, 54, and 51. The order in which the fragments are transmitted in response to requests from the ports 104 is H-B0-B1-T-SCP-H`-B0`-B1`-B2`-B3`….

Figure 4 illustrates a flowchart of the method of enabling retrieval of data in accordance with an embodiment of the present invention.
In particular, the method 400 enables pipelining a plurality of requests for reading data stored in the external storage device such as DDR 106. The method 400 begins at block 405.
At block 405, identify an opportunity to service a request for a port. In one embodiment, the port interface 118 identifies an opportunity to issue a read request to BPC 112 . In particular, the port interface 118 determines the maximum count of the requests that can be outstanding. For each request issued, this count is decremented and for each fragment that is transmitted to egress port 104, this count is incremented. Based on the determination of the maximum count, the port interface 118 identifies an opportunity to service a request for the port 104. On identification, the port interface 118 forwards the received request to PC 122 for further processing.
QSI 114 in the interface 102 determines the availability of space in the QID storage 116 for storing QIDs corresponding to the port 104. If the availability of space is determined, then the QSI 114 issues a request for a QID to the QS 108. The number of pending requests to the scheduler QS 108 is restricted to a maximum of number of Queue ID’s that can be stored for that port 104. The mechanism to decide when a request is issued to the QS 108 is e.g. a round robin at start and thereafter, each time a Tail or SCP is received, a request is issued to QS 108 for that port 104. The QS 108 responds to the pending request any time later whenever the QS 108 determines the presence of a packet in a queue that can be scheduled. QID of the queue that can be scheduled is then responded to the interface 102 and stored in the QID storage 116 for the port 104.
At block 410, determine whether an opportunity to issue a request for reading a body/tail fragment is available. In one embodiment, PC 122 determines the availability of said opportunity based on the presence of a pointer to the body/tail fragment to be read, and presence of an empty 5th block in BC 120 for storing the fragment thus read. A pointer to the first body or a tail fragment is determined to be available if a corresponding head fragment is available in a 4th block and the said head fragment is for a non-SCP. A pointer to the subsequent body fragment is available if the previous body fragment is available in the 3rd block. If the opportunity to issue a request for reading a body/tail fragment is determined to be available, then the method 400 proceeds to block 415 (along the YES path), or otherwise to the block 420 (along the NO path).
At block 415, issue request to external storage for reading tail and/or body fragments and update the states. In one embodiment, if the opportunity to issue a request for reading a body/tail fragment is determined to be available, then PC 122 issues a request to DDR 106 for reading a body/tail fragment. In particular, PC 122 issues a request for reading data associated with the queue having QID selected from the sequence maintained for the port. The request includes metadata such as at least a pointer to an empty 5th block where fragment is stored, type of fragment such as body and the port number of the port 104 that issued the request. Following the issue of request, PC 122 allocates the empty 5th block for storing the fragment when received from DDR 106.
Whenever the fragment is received from DDR 106, PC 122 allows the received fragment to be stored in the allocated 5th block. Therefore in respect of a request issued to DDR 106 for reading an ith body/tail fragment, PC 122 receives and stores the ith fragment in 5ith block. After issuing the request for the fragment, PC 122 updates the states that include information such as pointer to the next fragment to be read from the external storage device, status information indicating that the packet is complete or not(‘TRUE’ or ‘FALSE’). After updating the states, the method 400 proceeds to block 405 indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.
At block 420, determine whether an opportunity to issue a request for reading a head fragment is available. In one embodiment PC 122 determines the availability of an opportunity to read a head fragment based on the presence of a pointer to the head fragment to be read, and presence of an empty 4th block in BC 120 for storing the fragment thus read. Further PC 122 allocates an empty 4th block for storing the fragment for which the request is issued. When the head fragment is received from DDR 106, PC 122 allows the received fragment to be stored in the allocated 4th block. If the opportunity to issue a request for reading the head fragment is determined to be available, then the method 400 proceeds to block 425 (along the YES path) for issuing the request to read the head fragment. Otherwise the method 400 proceeds to the block 405 indicated by connector (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.
At block 425, issue a request for reading head fragment and update the states. In one embodiment, if the opportunity to issue a request for reading a head fragment is determined to be available, then PC 122 issues a request to DDR 106 for reading a head fragment. The request includes metadata such as at least a pointer to an empty 4th block where fragment is stored, type of fragment such as head and the port number of the port 104 that issued the request. Following the issue of request, PC 122 allocates the empty 4th block for storing the fragment when received from DDR 106. Requests for reading head fragments are issued in the order in which the selected QID’s are received from the Scheduler such that request for a header from the next selected QID is issued only after issuing the request for header from the previous one.
When the fragment is received from DDR 106, PC 122 allows the received fragment to be stored in the allocated 4th block. Therefore in respect of a request issued to DDR 106 for reading an ith head fragment, PC 122 receives and stores the ith fragment in 4ith block. After issuing the request for the head fragment, PC 122 updates the states that include information such as pointer to the first body/tail fragment to be read from the external storage device for the corresponding head fragment, status information indicating that the packet is complete or not (‘TRUE’ or ‘FALSE’). After updating the states, the method 400 proceeds to block 405 indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.

Figure 5 illustrates a flowchart of the method of reading body/tail fragment of a packet in accordance with an embodiment of the present invention.
The method 500 illustrates the method of reading a body/tail fragment of a packet from the DDR when an opportunity to issue a DDR request is identified by the port interface 118. The method begins at block 502.
At block 502, determine whether the previous packet is complete. For example, PC 122 determines the completion of the previous packet based on the status information of the previous packet. If the status information indicates that the previous packet is complete when the value is ‘TRUE’ i.e. no further read requests need to be issued for Body/Tail of the said previous packet,, then the method proceeds to block 505. Otherwise if the value of the status information of the previous packet is ‘FALSE’ indicating that the previous packet is not complete, then the method proceeds to block 515 for reading the remaining body/tail fragments of the said previous packet before proceeding to read the next packet.
At block 505, determine the presence of a head fragment. In one embodiment, for determining the availability of opportunity to read a body/tail fragment of a packet when the previous packet is complete, PC 122 determines the presence of the head fragment of the next packet stored in a 4th block in BC 120 for processing the packet. If the head fragment is determined to be stored in the 4th block, then the method 500 proceeds to block 510 (along the YES path); otherwise the method 500 proceeds to block 420 indicated by (C) along the NO path for identifying an opportunity to issue a request to read the head fragment.
At block 510, determine whether the head fragment thus present is an SCP i.e. whether the said next packet is complete. In one embodiment, for determining the availability of opportunity to read a body/tail fragment, PC 122 further determines whether the head fragment stored in the 4th block is an SCP or not. If it is determined that the head fragment is an SCP, then PC 122 updates the states such as the pointer to the next head fragment (or next packet) and the method proceeds to block 505 along the “YES” path. Otherwise if it is determined that the head fragment is not an SCP, then the method proceeds to block 515 along the “NO” path for reading the body/tail fragments corresponding to the head fragment.
At block 515, determine the presence of an empty 5th block. In one embodiment, for determining the availability of opportunity to read a body/tail fragment, PC 122 further determines the presence of an empty 5th block for storing a body/tail fragment prior to issuing a request for the same. If the presence of an empty 5th block is determined, then the method proceeds to block 520 along the “YES” path or proceeds to block 420 along the “NO” path indicated by (C) for identifying an opportunity to issue a request to read a head fragment.
At block 520, issue a request for reading body/tail fragment. In an embodiment, PC 122 issues a request for reading a body/tail fragment, using the pointer obtained from the stored 4th block The request includes metadata such as at least a pointer to an empty 5th block where fragment is stored, type of fragment such as body/tail, and the port number of the port 104 for which DDR request is made.
At block 525, determine whether the request is issued for a tail fragment. In an embodiment, PC 122 determines the type of fragment by keeping track of number of body requests issued and subtracting the same from the size of the packet obtained from the metadata in the Head fragment of the packet. If the fragment type is determined to be tail, then the method proceeds to block 530 along the “YES” path. On the other hand if the fragment type is not determined to be tail, then the method proceeds to block 535 along the “NO” path.
At block 530, update states and proceed further to the next packet. In one embodiment, if it is determined that the request is issued for a tail fragment, PC 122 updates the states and proceeds further for processing the next packet. The states include information such as pointers to the next head fragment in the external storage device, status information indicating that the packet is complete by storing the value ‘TRUE’. After updating the states, the method 500 proceeds to block 405 indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.
At block 535, update states. In one embodiment, if it is determined that the request is not issued for a tail fragment, PC 122 updates the states and proceeds further for issuing requests for the remaining body/tail fragments. The states include status information indicating that the packet is not complete by storing the value ‘FALSE’. After updating the states, the method 500 proceeds to block 405 indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.

Figure 6 illustrates a flowchart of the method of reading a head fragment of a packet in accordance with an embodiment of the present invention.
The method 600 illustrates the method of retrieving data of a packet when an opportunity to issue a DDR request is identified by the port interface 118. The method 600 begins if the opportunity to issue a read request for a body/tail fragment is not available and the PC 122 is idle. Rather than being idle, PC 122 issues DDR requests for reading head fragment if an opportunity to issue a request for the head fragment is available. The method 600 begins at block 605.
At block 605, determine the presence of an empty 4th block. In one embodiment, for determining the availability of an opportunity to issue a request for reading a head fragment, PC 122 determines the presence of an empty 4th block in which the head fragment is to be stored. If the presence of the empty 4th block is determined, then the method proceeds to block 610 along the “YES” path; otherwise proceeds to block 405 along the “NO” path indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.
At block 610, determine the presence of an address to the head fragment which is to be read. In one embodiment, for determining the availability of an opportunity to issue a request for reading a head fragment, PC 122 further determines the presence of a pointer to the head fragment for which a read request is issued. If the presence of the pointer is determined, then the method proceeds to block 615 along the “YES” path. If the presence of pointer to the head fragment is not determined, then the method 600 proceeds to block 405 along the “NO” path indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.
At block 615, issue a request for reading a head fragment. In one embodiment, PC 122 issues a request for reading a head fragment based on the availability of an empty 4th block and pointer to the head fragment that is to be read. The request includes metadata such as a pointer to an empty 4th block where fragment is to be stored, type of fragment such as head, and the port number of the port for which the DDR request is made.
At block 620, update states. In one embodiment, when the request is issued for the head fragment PC 122 updates the states and proceeds further. The states include pointer to the next 4th block where the next head fragment is stored in BC 120. After updating the states, the method 600 proceeds to block 405 indicated by (A) for identifying a next opportunity to service a port 104 scheduled by the port scheduler.

Figure 7 illustrates a flowchart of the method of transmission of contiguous fragments of packets to an egress port. The method 700 illustrates the method of transmitting a sufficient number of contiguous fragments to the egress port 104 in the correct order. The method 700 begins at block 705.
At block 705, receive any fragment for a port. In one embodiment, PC 122 receives one or more fragments read from the external storage device and stores thus received fragments in BC 120.
At block 710, determine if SCP or tail fragment is available i.e. the current first packet that needs to be transmitted to the egress port is complete. For example, PC 122 determines the availability of a SCP fragment or tail fragment in BC 120 in the available fragments starting from fragment ‘ZZ’ for which the token is yet to be transmitted. If the presence of either a SCP or a tail fragment is determined, then the method proceeds to block 715; otherwise the method proceeds to block 720.
At block 715, identify the number of contiguous SCP fragments or fragments up to and including tail based on the determination in block 710. In one embodiment, the PC 122 identifies the contiguous fragments of successive complete packets available starting from the said fragment ‘ZZ’. If the said fragment ‘ZZ’ of the current packet is identified as SCP packet, then the total number of contiguous fragments (TC) is determined as one. On the other hand, if the presence of the tail fragment starting from the specific fragment ‘ZZ’ is identified, then the total number of contiguous fragments from the fragment ‘ZZ’ up to and including the tail fragment is determined as TC. PC 122 further proceeds to count the contiguous fragments of the next packet, starting with its head fragment. PC 122 determines the availability of the next head fragment in BC 120. If the next available head fragment is determined as an SCP, then ‘TC’ is incremented by one and PC 122 proceeds to determine the availability of the next head fragment in BC 120. If the fragment is determined as non-SCP and the packet is complete i.e. all its fragments starting from Head till the Tail are available, then the number of these fragments is added to TC. This process of determining TC continues until the next head fragment is determined as non-SCP and the packet is not complete i.e. all its fragments up to the Tail are not available. If the head fragment is determined as non-SCP, and the packet is not complete, then the method 715 proceeds to block 725.
At block 725, identify the number of contiguous fragments of a next available packet, that is not complete, that are ready for transmission. In one embodiment, if the head fragment thus available is determined as non-SCP, then the number of contiguous fragments starting from the head fragment and including the contiguous fragments from the first body fragment onwards is determined and indicated as ‘X’. The method then proceeds to block 730.
At block 730, determine the sufficiency of the contiguous fragments ready for transmission. In one embodiment, PC 122 determines whether the total number of contiguous fragments thus identified is sufficient for transmission. The sufficiency of the number of contiguous fragments ready for transmission is determined based on the comparison of ‘TC+X’ with a predetermined threshold value. If it is determined that ‘TC+X’ exceeds or equals the said predetermined threshold value, then the method proceeds to block 735; otherwise the method proceeds to block 740.
At block 735, generate a token indicating TC and X fragments for transmission. In one embodiment, when PC 122 determines that ‘TC+X’ exceeds or equals the said predetermined threshold value, PC 122 generates a token indicating the total number of fragments (TC+X). The method proceeds to block 755.
At block 740, generate a token indicating TC fragments for transmission. In one embodiment, when PC 122 determines that ‘TC+X’ does not exceeds or equals the said predetermined threshold value, PC 122 generates a token indicating the total number of fragments (TC). The method proceeds to block 755.
At block 720, identify number of contiguous body fragments. In one embodiment, if the availability of a SCP packet or tail fragment is not determined in the block 710, then the fragments available in BC 120 indicate the body fragments starting from ‘ZZ’. PC 122 determines the number of contiguous fragments (‘X’) available starting from ‘ZZ’.
At block 745, determine the inclusion of a head fragment in the ‘X’ fragments i.e. it is the start of a new packet. In an embodiment, PC 122 determines the presence of a head fragment in the ‘X’ fragments. If it is determined that the head fragment is present in ‘X’ fragments, then the method proceeds to block 747 along the “YES” path. On the other hand, if it is determined that the head fragment is not included in ‘X’ fragments, then the ‘X’ fragments are body/tail fragments of of an ongoing packet that are ready for transmission and the method proceeds to block 750 along the “NO” path.
At block 747, determine the sufficiency of the ‘X’ contiguous fragments for transmission. In one embodiment, PC 122 determines whether the total number of contiguous fragments ‘X’ identified in block 720 is sufficient or not. The sufficiency of the number of contiguous fragments available for transmission is determined based on the comparison of ‘X’ with a predetermined threshold value. If it is determined that ‘X’ exceeds or equals the said predetermined threshold value, then the total number of contiguous fragments ready for transmission is determined as ‘X’ fragments and the method proceeds to block 750; otherwise the method proceeds to block 705 along the “NO” path indicated by connector (D) for receiving further fragments for the port in order to meet the sufficiency.
At block 750, generate a token indicating X fragments for transmission. In one embodiment, when PC 122 determines that ‘X’ exceeds or equals the said predetermined threshold value, PC 122 generates a token indicating the total number of contiguous body fragments (X). The method proceeds to block 755.
At block 755, transmit the token thus generated. In one embodiment, the token thus generated by PC 122 after the identification of the contiguous fragments that are sufficient is transmitted to the port that issued the data request.
As mentioned above, the interface 102 enables the pipelining of the read requests issued to the external storage device and transmitting the data in the correct order with the aid of tokens. The aspect of pipelining the requests issued to DDR reduces the impact of the latencies of fetching data from the DDR, and the aspect of transmitting the data in the correct order avoids the mixing of packets. Further the aspect of transmitting a sufficient number of contiguous fragments avoids the possibility of intra packet under-runs being created and therefore supporting the high bandwidth for a given port.
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 contemplated 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 for enabling transmission of a packet stored in the storage device, said storage device comprising:
a plurality of memory locations grouped together to form at least one 1st block, each of the 1st block comprises one 2nd block and one 3rd block; the said 2nd block comprising a plurality of 4th blocks; and the said 3rd block comprising a plurality of 5th blocks,
characterized in that
data stored in a 4th block comprise header data and data stored in one or more 5th blocks comprise body and/or tail data corresponding to header data stored in the 4th block.

2. The storage device as claimed in claim 1, wherein the header stored in a 4th block is a head fragment of a packet or a SCP packet.

3. A method of retrieval of a packet from an external storage device for enabling transmission of the said packet, said method comprising the steps of:
(a) determining availability of an opportunity to read a body/tail fragment of the packet;
(b) if the opportunity to read a body/tail fragment is available, issuing a request to an external storage device for reading the said body/tail fragment of the packet;
(c) if the opportunity to read a body/tail fragment is not available, determining as to whether an opportunity to read a header fragment of a packet is available; and
(d) issuing a request to the external storage device for reading the said header fragment of the packet if an opportunity to read a header fragment is available.

4. The method as claimed in claim 3, wherein the opportunity to read a body/tail fragment of the packet is determined to be available if
(a) a pointer to a body/tail fragment is available; and
(b) an empty 5th block is present in the 3rd block.

5. The method as claimed in claim 4, wherein said pointer to a body/tail fragment is available if:
(a) a corresponding head fragment is present in a 4ith block; and
(b) the head fragment thus present is not an SCP.

6. The method as claimed in claim 4, wherein said pointer to a body fragment is available if an earlier body fragment is received.

7. The method as claimed in claim 3, wherein in respect of a request issued to an external storage device for reading an ith body/tail fragment, receiving and storing the ith fragment in 5ith block.

8. The method as claimed in claim 3, wherein the opportunity to read a header fragment of the packet is determined to be available if
(a) an empty 4th block is present in the 2nd block; and
(b) an address in the external storage device from which the head/SCP fragment is to be read is available.

9. The method as claimed in claim 3, wherein in respect of a request issued to an external storage device for reading an ith head fragment, receiving and storing the ith fragment in 4ith block.

10. The method as claimed in claim 3, further comprising transmitting a token indicating availability of contiguous fragments for transmission.

11. The method as claimed in claim 10, wherein said token further indicates the total number of fragments available for transmission.

12. The method as claimed in claim 10, wherein the said token is transmitted only when the token indicates availability of data that is in continuation of the previously available data, so as to enable in-order transmission of data.

13. The method as claimed in claim 10, wherein the said token is transmitted if:
(a) number of contiguous fragments stored exceeds a predetermined threshold value; and/or
(b) the tail fragment is stored in a 5th block and/or
(c) contiguous fragments stored belong to an ongoing packet for which at least one token has been transmitted previously.

14. The method as claimed in claim 3, further comprising transmitting a token indicating availability of a fragment for transmission if:
(a) a head fragment is present in a 4ith block; and
(b) the head fragment thus present is for an SCP.

15. The method as claimed in claim 10, wherein a token thus transmitted comprises:
(a) contiguous fragments belonging to a particular packet;
(b) contiguous fragments belonging to a first packet and a header fragment of at least one SCP.
(c) contiguous fragments belonging to a first packet and contiguous fragments belonging to at least one further packet;
(d) a header fragment of a SCP and contiguous fragments belonging to at least one further packet; or
(e) header fragments of a plurality of SCPs.

16. The method as claimed in claim 3, further comprising:
(a) in response to transmission of the token, receiving a request for fragments from an egress port; and
(b) transmitting available contiguous fragments in response to the said fragment request.

17. An apparatus for enabling transmission of a packet stored in a storage device, said apparatus comprising:
(a) a processing component (PC) configured to retrieve data constituting the packet from an external storage device;
(b) a buffering component (BC) for storing data thus retrieved prior to transmission of said data;
wherein said processing component retrieves said data by:
(a) determining availability of an opportunity to read a body/tail fragment of said packet;
(b) if the opportunity to read a body/tail fragment is available, issuing a request to the external storage device for reading the said body/tail fragment of the packet;
(c) if the opportunity to read a body/tail fragment is not available, determining as to whether an opportunity to read a header fragment of the packet is available; and
(d) issuing a request to the external storage device for reading the said header fragment of the packet if the said opportunity to read the header fragment is available.

18. The apparatus as claimed in claim 18, wherein the said BC and said PC form part of a buffering and processing component (BPC).

19. The apparatus as claimed in claim 19, wherein the BPC is operatively connected to at least one port via a port interface.

20. The apparatus as claimed in claim 18, wherein the BPC is operatively connected to a queue scheduler for enabling sequencing of requests for data received for the said at least one port.

21. The apparatus as claimed in claim 21, wherein the sequencing is performed on a port-by-port basis, if the BPC is operatively connected to a plurality of ports.

22. The apparatus as claimed in claim 18, further comprising a QID storage communicatively connected to BPC.

23. The apparatus as claimed in claim 18, wherein said PC is configured to store a fragment read from the external storage device in the said BC.

24. The apparatus as claimed in claim 18, wherein said PC transmits a token to the port whenever a sufficient number of contiguous fragments are available in BC.

25. The apparatus as claimed in claim 26, wherein said token further indicate the total number of fragments available for transmission.

26. The apparatus as claimed in claim 26, wherein said PC receives the fragment request from the port in response to transmission of the said token and further transmits the contiguous fragments available for transmission.

27. A method of retrieval of a packet from an external storage device for enabling transmission of the said packet substantially as herein described with reference to the foregoing paragraphs and the accompanying drawings.

28. A storage device for enabling transmission of a packet stored in the storage device substantially as herein described with reference to the foregoing paragraphs and the accompanying drawings.

29. An apparatus for enabling transmission of data stored in a storage device substantially as herein described with reference to the foregoing paragraphs and the accompanying drawings.

Dated this 25th day of March 2009.

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

ABSTRACT

A METHOD AND A SYSTEM TO ENABLE TRANSMISSION OF PACKET STORED IN A STORAGE DEVICE

The present invention relates to a method and a system that enables transmission of packet stored in a storage device to one or more ports. In one embodiment, an interface is configured to issue a plurality of pipelined requests for reading data from an external storage device. The interface is further configured to store the data in the storage device. Whenever a sufficient amount of data is available in the storage device, the interface begins the transmission of data in the correct order in which the data is requested for reading. Therefore, the mechanism of pipelining requests for reading data and maintaining the order in which the data is transmitted out to the ports reduces the impact of access latencies occurred during fetching of data from the external storage device and also supports the high bandwidth of the ports.