Data fragmentation identification in a data table

• US 8,671,334 B2
• Filed: 08/29/2008
• Issued: 03/11/2014
• Est. Priority Date: 12/11/2007
• Status: Expired due to Fees

• Current Assignee: Monument Bank of Intellectual Property, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Quarterhill Inc. (f/k/a Wi-LAN Inc.)
• Inventors: Nebat, Yoav, Zehedi, Sina
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US12/202,184
• Publication Number:
  US 20090150753A1
• Time in Patent Office: 2,020 Days
• Field of Search: 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H04L 1/0084 Formats for payload data
• CPC Class Codes: H04W 72/30 Resource management for broadcast services

Abstract

The subject matter disclosed herein provides a mechanism for identifying packet boundaries in a data table, such as a Reed-Solomon table. The method may include receiving one or more packets for insertion into a table. A first indicator may be inserted into the table. The first indicator may be associated with one or more rows of the table and may identify whether each of the one or more rows includes one or more fragments (e.g., a packet beginning, a packet ending, and the like). In each of the rows identified by the first indicator as including one or more fragments, a second indicator may be inserted. The second indicator may represent a length in bytes of at least one of the corresponding packet fragments. Related systems, apparatus, methods, and/or articles are also described.

Claims

1. A method of operating a station comprising a processor and a memory, the method comprising:

receiving one or more communication network packets for insertion by the processor into a table in the memory, wherein the table comprises a plurality of blocks each including a set of rows and a set of columns;

inserting, into the table, a first indicator into each of the plurality of blocks, each first indicator identifying a location of one or more fragments included in the table, wherein a fragment is a packet or a portion of a packet occupying part of a row; and

on a condition that a row in the table includes one or more corresponding fragments, inserting, into the row in the table, one or more second indicators, each of the one or more second indicators including a value representative of a length in bytes of the corresponding fragment.

2. The method of claim 1 further comprising:

using, as the first indicator, a bit-map indicator including a plurality of bits, each of the plurality of bits associated with a corresponding portion of the table and each bit indicating whether the corresponding portion includes at least one fragment.

3. The method of claim 1 further comprising:

identifying at least one fragment as at least one of a beginning of a communication network packet or an end of a communication network packet.

4. The method of claim 1 further comprising:

using, as the first indicator, a bit-map indicator including a plurality of bits, each of the plurality of bits corresponding to a portion of a block and identifying whether the one or more fragments are included in the portion of the block.

5. A method of operating a station comprising a processor and a memory, the method comprising:

receiving one or more communication network packets for insertion by the processor into a table in the memory, wherein the table comprises a plurality of blocks each including a set of rows and a set of columns;

inserting, into the table, a first indicator into each of the plurality of blocks, each first indicator identifying a location of one or more fragments included in the table;

inserting, into the table, for each of the plurality of blocks, one or more second indicators, when the first indicator identifies one or more fragments;

wherein the table comprises a plurality of rows;

wherein each first indicator is associated with one or more rows of the table and identifies whether each of the one or more rows includes one or more fragments; and

wherein inserting the one or more second indicators, comprises;

inserting, in each of the rows identified by the first indicator as including one or more fragments, a second indicator representative of a length in bytes of a corresponding fragment included in the row.

6. The method of claim 5, further comprising:

inserting the one or more communication network packets into a Reed-Solomon table; and

encoding at least a portion of the Reed-Solomon table using a Reed-Solomon code.

7. The method of claim 5 further comprising:

using, as the first indicator, a bit-map indicator including a plurality of bits, each of the plurality of bits corresponding to one of the rows and identifying whether one or more fragments are included in the corresponding row.

8. The method of claim 5 further comprising:

using 8-bits as the first indicator, a first bit of the 8-bits corresponding to a first row, and a second bit of the 8-bits corresponding to a second row, the first bit indicating whether one or more fragments are included in the first row, and the second bit Indicating whether one or more fragments are included in the second row.

9. The method of claim 5 further comprising:

arranging each of the one or more rows as a horizontal portion of the table.

10. The method of claim 5 further comprising:

arranging each of the one or more rows as a vertical portion of the table.

11. The method of claim 5, wherein the table comprises a plurality of sub-tables, each of the sub-tables including a set of one or more rows;

wherein inserting one or more first indicators comprises;

inserting a first indicator into each of the sub-tables wherein the first indicator identifies for each row of the sub-table whether the row includes one or more fragments; and

wherein inserting one or more second indicators comprises;

for each of the sub-tables, inserting one or more second indicators in at least one of the rows of the sub-table when the at least one row includes one or more fragments.

12. The method of claim 11, further comprising:

using, as the first indicator, a bit-map indicator including a plurality of bits, each of the plurality of bits corresponding to one of the rows and identifying whether one or more fragments are included in the corresponding row.

13. A method of operating a station comprising a processor and a memory, the method comprising:

inserting, by the processor, into a table in the memory, one or more received communication network packets, wherein the table comprises a plurality of blocks each including a set of rows and a set of columns;

reading from the table a first indicator from each of the plurality of blocks, wherein the first indicator identifies a location in the table in which a fragment is located, wherein a fragment is a packet or a portion of a packet occupying part of a row;

on a condition that a row in the table includes one or more corresponding fragments, reading from the row in the table one or more second indicators that identify a length in bytes of the one or more corresponding fragments;

reading at least one communication network packet from the table based on the first indicator and the one or more second indicators; and

providing the at least one read communication network packet.

14. The method of claim 13 further comprising:

decoding, using a Reed-Solomon forward-error correction code, the at least one communication network packet after inserting the at least one communication network packet into the table.

15. The method of claim 13, wherein reading the at least one communication network packet further comprises:

reading, based on the first and second indicators, a portion of the at least one communication network packet, the portion forming a fragment.

16. The method of claim 13, wherein reading the at least one communication network packet further comprises:

wherein the first indicator is a bit-map indicator including a plurality of bits, each of the plurality of bits corresponding to one of the rows of the table and identifying whether one or more fragments are included in the corresponding row; and

wherein the second indicator includes a value representative of a length of one of the fragments in the corresponding row.

17. The method of claim 13, wherein the first indicator is a bit-map indicator including a plurality of bits each of the plurality of bits associated with a corresponding portion of the table and each bit indicating whether the corresponding portion of the table includes at least one fragment.

18. A system comprising:

a station comprising a processor and a memory; and

a framer coupled to the station and operated by the processor, the framer configured to;

receive one or more communication network packets for insertion into a table in the memory, the table comprising a plurality of blocks each including a set of rows and a set of columns;

insert into the table a first indicator into each of the plurality of blocks each identifying a location of one or more communication network packet beginnings or endings in the table; and

insert into each of the plurality of blocks one or more second indicators, when the first indicator identifies one or more communication network packets, each identifying a length in bytes of a corresponding communication network packet fragment included in the table, wherein a packet fragment is a packet or a portion of a packet occupying part of a row.