ATM header compression using hash tables
View Patent ↗Disclosed are exemplary techniques for compressing ATM cells by substituting reduced headers for the original headers. A header table may be maintained at the transmitting end whereby headers are stored in table entries based on a table index generated from a hash function applied to the headers. A copy of the header table may be maintained at the receiving end and may be updated by populating idle cells with header table contents. Upon receipt of a reduced ATM cell at the receiving end, the reduced header may be replaced with a full header obtained from the copy of the header table maintained at the receiving end. The present invention further provides techniques for registration and management of hash collisions.
1. A method for communicating one or more asynchronous transfer mode (ATM) cells, the method comprising:
determining, for a first ATM cell, an index based at least in part on a header of the first ATM cell;
identifying a first entry of a first header table using the index;
replacing the header of the first ATM cell with a reduced header to generate a reduced ATM cell based at least in part on a comparison of the header of the first ATM cell with header data stored at the first entry of the first header table, wherein the reduced header includes index data; and
transmitting the reduced ATM cell.
2. The method of claim 1 , wherein the header of the first ATM cell is replaced with the reduced header when the header of the first ATM cell substantially matches the header data stored at the first entry of the first header table.
3. The method of claim 1 , further comprising:
determining, for a second ATM, a second index based at least in part on a header of a second ATM cell;
identifying a second entry of the first header table using the second index;
transmitting the second ATM cell when the header of the second ATM cell does not substantially match header data stored at the second entry of the first header table.
4. The method of claim 1 , further comprising clearing the first entry of the first header table when the header data stored at the first entry is used infrequently.
5. The method of claim 1 , further comprising:
storing the header of the first ATM cell at the first entry of the first header table when the first entry is empty; and
transmitting a second ATM cell, the second ATM cell including data representative of at least part of the first header table including the first entry.
6. The method of claim 5 , further comprising:
updating one or more entries of a second header table based at least in part on data representative of at least part of the first header table, wherein the second header table is used to replace reduced headers with corresponding unreduced headers.
7. The method of claim 1 , further comprising:
identifying a first entry of a second header table using the index data of the reduced header of the reduced ATM cell, wherein the second header table is substantially equivalent to the first header table; and
replacing the reduced header of the reduced ATM cell with header data stored at the first entry of the second header table to generate a second ATM cell, wherein the second ATM cell is substantially equivalent to the first ATM cell.
8. The method of claim 7 , further comprising:
storing the header of the first ATM cell in the first entry of the first header table when the first entry is empty; and
transmitting a third ATM cell, the third ATM cell including data representative of at least part of the first header table including the first entry.
9. The method of claim 8 , further comprising updating one or more entries of the second header table based at least in part on the data representative of at least part of the first header table.
10. The method of claim 1 , wherein determining the index includes performing a hash function on at least part of the header of the first ATM cell, wherein the hash function is represented by an equation:
HASH
(
x
)
=
(
∑
i
-
1
4
B
i
&
0
×
70
)
⪢
4
where HASH(x) represents the index, B i represents byte i of the header of the first ATM cell for i=0 to 4.
11. The method of claim 1 , wherein the reduced header further includes at least one of the following: a flag field identifying the reduced header as a reduced header, a parity bit field, a least significant bit of a payload type indicator (PTI) field of the first ATM cell.
12. A method for communicating one or more asynchronous transfer mode (ATM) cells, the method comprising:
receiving, at a computing device, a first reduced ATM cell having a reduced header, the reduced header including index data;
identifying a first entry of a first header table using the index data;
replacing the reduced header of the first reduced ATM cell with header data to generate an unreduced ATM cell;
receiving a second ATM cell, the second ATM cell having data representative of at least part of a table of one or more headers; and
updating one or more entries of header table based at least in part on the data representative of at least part of the table of one or more headers.
13. The method of claim 12 , wherein the index data is derived at least in part from at least one of the following:
an application of a hash function to at least part of the header data of the unreduced ATM cell, wherein the hash function is represented by an equation:
HASH
(
x
)
=
(
∑
i
-
1
4
B
i
&
0
×
70
)
⪢
4
where HASH(x) represents the index data, B i represents byte i of the header for i=0 to 4.
14. The method of claim 12 , further comprising:
receiving a second ATM cell, the second ATM cell having data representative of at least part of a table of one or more headers; and
updating one or more entries of the header table based at least in part on the data representative of at least part of the table of one or more headers.
15. A transmitting device for communicating one or more asynchronous transfer mode (ATM) cells, the transmitting device comprising:
a header table having a plurality of entries for storing header data;
a compression module having access to the header table and being adapted to perform at least the following:
determine, for a first ATM cell, an index;
identify a first entry of the header table using the index; and
replace the header of the first ATM cell with a reduced header to generate a reduced ATM cell based at least in part on a comparison of the header of the first ATM cell and a header stored at the first entry of the header table, the reduced header including index data; and
means for transmitting the reduced ATM.
16. The transmitting device of claim 15 , wherein the header of the first ATM cell is replaced with the reduced header when the header of the first ATM cell substantially matches the header data stored at the first entry of the header table.
17. The transmitting device of claim 15 , wherein the compression module is further adapted to perform at least the following:
determine, for a second ATM cell, a second index based at least in part on a header of a second ATM cell;
identify a second entry of the header table using the second index; and
provide the second ATM cell for transmission to the receiving device when the header of the second ATM cell does not substantially match header data stored at the second entry of the header table.
18. The transmitting device of claim 15 , wherein the compression module is further adapted to perform at least the following:
clear the first entry of the header table when the header data stored at the first entry is used infrequently
store the header of the first ATM cell at the first entry of the header table when the first entry is empty; and
provide a second ATM cell for transmission to the receiving device, the second ATM cell including data representative of at least part of the header table including the first entry, wherein the compression module provides the second ATM cell for transmission before providing the reduced ATM cell for transmission.
19. The transmitting device of claim 15 , wherein the compression module is adapted to determine the index by performing a hash function on at least part of the header of the first ATM cell, wherein the hash function is represented by an equation:
HASH
(
x
)
=
(
∑
i
-
1
4
B
i
&
0
×
70
)
⪢
4
where HASH(x) represents the index, B i represents byte i of the header of the first ATM cell for i=0 to 4.
20. The transmitting device of claim 15 , wherein the transmitting device includes a digital subscriber line (DSL) modem.
21. The transmitting device of claim 15 , wherein the means for transmitting the reduced ATM cell for receipt by the receiving device includes means for transmitting the reduced ATM cell to the receiving device via an intermediary device.