ATM header compression using hash tables

• US 20040246966A1
• Filed: 11/07/2003
• Published: 12/09/2004
• Est. Priority Date: 06/05/2003
• Status: Active Grant

• Current Assignee: Ikanos Communications Incorporated (Qualcomm, Inc.)
• Original Assignee: Globespan Virata, Inc.
• Inventors: Wu, Yan, Bi, Song, Bornemisza, Timothy
• Granted Patent: US 7,400,627 B2
• Time in Patent Office: Days
• US Class Current: 370/395.1
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly

Abstract

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.

Claims

1. A method for communicating one or more asynchronous transfer mode (ATM) cells from a transmitting device to a receiving device via a network, 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, the first header table being maintained by the transmitting device and having a plurality of entries storing header data;

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 for receipt by the receiving device.

2. The method as in 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 as in claim 1, further comprising the steps of:

determining, for a second ATM, a second index based at least in part on a header of the second ATM cell;

identifying a second entry of the first header table using the second index;

transmitting the second ATM cell for receipt by the receiving device 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 as in claim 1, further comprising the step of clearing the first entry of the first header table when the header data stored at the first entry is used infrequently.

5. The method as in claim 1, further comprising the steps of:

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 for receipt by the receiving device, the second ATM cell including a data representative of at least part of the first header table including the first entry.

6. The method as in claim 5, further comprising the steps of:

updating one or more entries of a second header table maintained by the receiving device based at least in part on the data representative of at least part of the first header table, wherein the second header table is used by the receiving device to replace reduced headers with corresponding unreduced headers and is substantially equivalent to the first header table.

7. The method as in claim 1, further comprising the steps of:

identifying a first entry of a second header table maintained by the receiving device 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 at the receiving device, wherein the second ATM cell is substantially equivalent to the first ATM cell.

8. The method as in claim 7, further comprising the steps of:

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 to the receiving device, the third ATM cell including data representative of at least part of the first header table including the first entry.

9. The method as in claim 8, further comprising the step of 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 as in claim 9, wherein the second ATM cell is transmitted before the first ATM cell is transmitted.

11. The method as in claim 1, wherein the step of determining the index includes performing a hash function on at least part of the header of the first ATM cell.

12. The method as in claim 11, wherein the hash function is represented by an equation:

13. The method as in claim 1, wherein the reduced header further includes a flag field identifying the reduced header as a reduced header.

14. The method as in claim 1, wherein the reduced header includes a parity bit field.

15. The method as in claim 1, wherein the reduced header includes a least significant bit of a payload type indicator (PTI) field of the first ATM cell.

16. The method as in claim 1, wherein the transmitting device includes a digital subscriber line (DSL) modem.

17. The method as in claim 1, wherein the receiving device includes a digital subscriber line (DSL) modem.

18. The method as in claim 1, wherein the step of transmitting the reduced ATM cell for receipt by the receiving device includes transmitting the reduced ATM cell to the receiving device via an intermediary device.

19. A method for communicating one or more asynchronous transfer mode (ATM) cells from a transmitting device to a receiving device, the method comprising:

receiving, at the receiving device, a first reduced ATM cell having a reduced header from the transmitting device, the reduced header including index data;

identifying a first entry of a first header table using the index data, the first header table being maintained by the receiving device and having a plurality of entries storing header data; and

replacing the reduced header of the first reduced ATM cell with header data stored at the first entry of the first header table to generate an unreduced ATM cell.

20. The method as in claim 19, wherein the index data is derived at least in part from an unreduced representation of the reduced header of the first reduced ATM cell.

21. The method as in claim 19, wherein the index data is derived from an application of a hash function to at least part of the unreduced representation of the reduced header.

22. The method as in claim 21, wherein the hash function is represented by an equation:

23. The method as in claim 19, further comprising the steps of:

receiving, at the receiving device, 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.

24. A transmitting device for communicating one or more asynchronous transfer mode (ATM) cells for receipt by a receiving device via a network, 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;

determine, for a first ATM cell, an index based at least in part on a header of the first ATM cell;

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 cell for receipt by the receiving device.

25. The transmitting device as in claim 24, 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.

26. The transmitting device as in claim 24, wherein the compression module is further adapted to:

determine, for a second ATM cell, a second index based at least in part on a header of the 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.

27. The transmitting device as in claim 24, wherein the compression module is further adapted to clear the first entry of the header table when the header data stored at the first entry is used infrequently.

28. The transmitting device as in claim 24, wherein the compression module is further adapted to:

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.

29. The transmitting device as in claim 28, wherein the compression module provides the second ATM cell for transmission before providing the reduced ATM cell for transmission.

30. The transmitting device as in claim 24, 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.

31. The transmitting device as in claim 30, wherein the hash function is represented by an equation:

32. The transmitting device as in claim 24, wherein the transmitting device includes a digital subscriber line (DSL) modem.

33. The transmitting device as in claim 24, 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.

34. A receiving device for receiving one or more asynchronous transfer mode (ATM) cells from a transmitting device via a network, the receiving device comprising:

means for receiving a reduced ATM cell having a reduced header, the reduced header including index data;

a header table having a plurality of entries for storing header data;

a decompression module operably connected to the means for receiving the reduced ATM cell and having access to the header table, the decompression module adapted to;

identify a first entry of the header table using the index data from the reduced header, the first entry storing header data; and

replace the reduced header of the first reduced ATM cell with the header data stored by the first entry to generate an unreduced ATM cell.

35. The receiving device as in claim 34, wherein the index data is derived at least in part from an unreduced representation of the reduced header.

36. The receiving device as in claim 35, wherein the index data is derived from an application of a hash function to at least part of the unreduced representation of the reduced header.

37. The receiving device as in claim 36, wherein the hash function is represented by an equation:

38. The receiving device as in claim 34, further comprising means for receiving a second ATM cell, the second ATM cell including data representative of at least part of a table of one or more headers and wherein the decompression module is further adapted to update 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.

39. A system for communicating one or more asynchronous transfer mode (ATM) cells via a network, the system comprising:

a transmitting device including;

a first header table having a plurality of entries for storing header data;

a compression module having access to the first header table and adapted to;

determine, for a first ATM cell, an index based at least in part on a header of the first ATM cell;

identify a first entry of the first 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 with header data stored at the first entry of the first header table, the reduced header including index data; and

means for transmitting the reduced ATM cell via the network; and

a receiving device operably connected to the transmitting device via the network and comprising;

means for receiving the reduced ATM cell via the network;

a second header table having a plurality of entries for storing header data, the second header table being substantially equivalent to the first header table;

a decompression module operably connected to the means for receiving the first reduced ATM cell and having access to the second header table, the decompression module adapted to;

identify a first entry of the second header table using the index data from the reduced header of the reduced ATM cell, the first entry of the second header table storing header data; and

replace the reduced header of the reduced ATM cell with the header data stored at the first entry of the second header table to generate a second ATM cell substantially equivalent to the first ATM cell.

40. The system as in claim 39, 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.

41. The system as in claim 39, wherein the compression module is further adapted to:

determine, for a third ATM cell, a second index based at least in part on a header of the third ATM cell;

identify a second entry of the first header table using the second index; and

provide the third ATM cell for transmission via the network when the header of the third ATM cell does not substantially match header data stored at the second entry of the first header table.

42. The system as in claim 39, wherein the compression module is further adapted to:

store the header of the first ATM cell in the first entry of the first header table when the first entry is empty; and

provide a third ATM cell for transmission to the receiving device, the third ATM cell having data representative of at least part of the first header table including the first entry.

43. The system as in claim 42, wherein the decompression module is further adapted to update 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.

44. The system as in claim 39, 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.

45. The system as in claim 44, wherein the hash function is represented by an equation:

46. The system as in claim 39, 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.

47. A computer readable medium for communicating one or more asynchronous transfer mode (ATM) cells from a transmitting device to a receiving device via a network, the computer readable medium comprising a set of executable instructions adapted to manipulate a processor to:

determine, for a first ATM cell, an index based at least in part on a header of the first ATM cell;

identify a first entry of a first header table using the index, the first header table being maintained by the transmitting device and having a plurality of entries storing header data;

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 with header data stored at the first entry of the first header table, wherein the reduced header includes index data; and

provide the reduced ATM cell for transmission to receiving device.

48. The computer readable medium as in claim 47, 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.

49. The computer readable medium as in claim 47, further comprising executable instructions adapted to manipulate the processor to:

determine, for a second ATM, a second index based at least in part on a header of the second ATM cell;

identify a second entry of the first header table using the second index;

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 first header table.

50. The computer readable medium as in claim 47, further comprising executable instructions adapted to manipulate the processor to:

store the header of the first ATM cell at the first entry of the first 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 a data representative of at least part of the first header table including the first entry.

51. The computer readable medium as in claim 47, wherein the executable instructions adapted to manipulate the processor to determine the index include executable instructions to manipulate the processor to perform a hash function on at least part of the header of the first ATM cell.

52. The computer readable medium as in claim 51, wherein the hash function is represented by an equation:

53. A computer readable medium for communicating one or more asynchronous transfer mode (ATM) cells from a transmitting device to a receiving device, the computer readable medium comprising a plurality of executable instructions adapted to manipulate a processor to:

receive, at the receiving device, a first reduced ATM cell having a reduced header from the transmitting device, the reduced header including index data;

identify a first entry of a first header table using the index data, the first header table being maintained by the receiving device and having a plurality of entries storing header data; and

replace the reduced header of the first reduced ATM cell with header data stored at the first entry of the first header table to generate an unreduced ATM cell.

54. The computer readable medium as in claim 53, wherein the index data is derived at least in part from an unreduced representation of the reduced header of the first reduced ATM cell.

55. The computer readable medium as in claim 53, wherein the index data is derived from an application of a hash function to at least part of the unreduced representation of the reduced header.

56. The computer readable medium as in claim 55, wherein the hash function is represented by an equation:

57. The computer readable medium as in claim 53, further comprising executable instructions adapted to manipulate the processor to:

receive, at the receiving device, a second ATM cell, the second ATM cell having data representative of at least part of a table of one or more headers; and

update 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.