Method for routing of data packets and routing apparatus

• US 20060106940A1
• Filed: 08/05/2003
• Published: 05/18/2006
• Est. Priority Date: 08/07/2002
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Jagannathan, Sankar Narayan, Lin, Jinan, Nie, Xiaoning
• Granted Patent: US 8,046,487 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503

Abstract

In order to be able to use a smaller routing table (4) and, thus, to reduce the costs and power consumption and to improve the performance of an IP router, it is proposed to extract a destination address identifier (ADR) from a data packet to be forwarded by the IP router, compress the extracted destination address identifier (ADR) by using a lossless data compression algorithm, and compare the compressed destination address identifier with entries stored in the routing table (4) so as to find a correspondence between the destination address identifier and one of the entries of the routing table (4). Each entry of the routing table (4) corresponds to a possible or available forwarding address of the IP router, the forwarding addresses having been compressed with the same data compression algorithm as the destination address identifier. After having found a correspondence between the destination address identifier and one of the compressed forwarding addresses stored in the routing table (4), a switch (6) of the IP router switches the respective data packet to one of its output links (OUT) which is associated with the respective forwarding address matching the destination address identifier (ADR).

Claims

1-17. -17. (canceled)

18. A method for routing of data packets, comprising the steps:

(a) extracting a destination address identifier from a data packet to be forwarded,

(b) compressing the destination address identifier using a compression algorithm,

(c) comparing the compressed destination address identifier with entries of a routing table, each entry corresponding to a forwarding address available for routing, and

(d) if a positive comparison between the compressed destination address identifier and an entry stored in the routing table is found in step (c), then switching the data packet to an output link associated with the forwarding address corresponding to the entry.

19. The method according to claim 18, wherein each of the entries of the routing table comprises a forwarding address compressed using the compression algorithm.

20. The method according to claim 18, wherein the compression algorithm comprises a lossless data compression algorithm configured to reduce redundancy in the destination address identifier.

21. The method according to claim 20, wherein the lossless data compression algorithm is selected from a group comprising Huffman algorithms, Arithmetic algorithms, and Lempel-Ziv algorithms.

22. The method according to claim 18, further comprising adjusting at least one parameter of the data compression algorithm in dependence upon data characteristics of the destination address identifier.

23. The method according to claim 19, wherein step (c) further comprises comparing the compressed destination address identifier with entries of the routing table taking into account a similarity between the compressed destination address identifier and a compressed destination address identifier of a preceding data packet.

24. The method according to claim 19, wherein step b) further comprises compressing the destination address identifier using a code table that associates a code word to a symbol of the destination address identifier and to a symbol of each forwarding address, respectively.

25. The method according to claim 24, wherein each symbol of the destination address identifier and each symbol of a forwarding address, respectively, comprises a plurality of bits of the destination address identifier and a plurality of bits of the forwarding address, respectively.

26. The method according to claim 25, wherein each symbol of the destination address identifier and each symbol of the forwarding addresses comprises four successive bits of the destination address identifier and the forwarding address, respectively.

27. The method according to claim 24, wherein step b) further comprises compressing the destination address identifier using the code table that associates the code word to the symbol of the destination address identifier, the length of each code word being inversely related to an appearance probability of a corresponding symbol in the code table.

28. The method according to claim 24, wherein step b) further comprises compressing the destination address identifier using the code table that associates the code word to the symbol of the destination address identifier, the length of each code word being inversely related to an appearance probability of a corresponding symbol in the destination address identifier of an input data packet.

29. The method according to claim 18, wherein step (a) further comprises extracting the destination address identifier from an IPv6 data packet to be forwarded.

30. A routing apparatus for routing of data packets, comprising:

a first data compressor configured to receive a destination address identifier of a data packet to be forwarded and generate a compressed destination address identifier therefrom,

a routing table store configured to store a plurality of entries, each entry corresponding to a forwarding address available for routing,

a routing unit configured to compare the compressed destination address identifier with the entries stored in the routing table store means for finding a correspondence between the compressed destination address identifier and one of the entries, each entry corresponding to a forwarding address, and

a switch configured to switch the data packet to an output link associated with a forwarding corresponding to a entry corresponding to the compressed destination address identifier.

31. The routing apparatus according to claim 30, further comprising a second data compressor configured to compress the forwarding addresses according to said data compression algorithm, and wherein the entries in the routing table store comprise compressed forwarding addresses.

32. The routing apparatus according to claim 30, wherein the first data compressor is configured to use a lossless data compression algorithm which reduces redundancy in the destination address identifier.

33. The routing apparatus according to claim 32, wherein the first data compressor is configured to use a data compression algorithm being selected from a group comprising Huffman algorithms, Arithmetic algorithms, and Lempel-Ziv algorithms.

34. The routing apparatus according to claim 30, further comprising a compression parameter adjuster configured to adjust at least one parameter of the first data compressor in dependence upon data characteristics of the destination address identifier.

36. A routing apparatus for routing of data packets, comprising:

extraction means for extracting a destination address identifier from a data packet to be forwarded,

routing table storing means for storing a plurality of entries, each entry corresponding to a forwarding address available for routing,

a routing unit for comparing the destination address identifier with the entries stored in the routing table storing means for finding a correspondence between the destination address identifier and one of the forwarding addresses, and

switch means for switching the data packet to an output link associated with the respective forwarding address matching the destination address identifier,

wherein first data compression means are provided for compressing the destination address identifier extracted by the extraction means according to a data compression algorithm, and

wherein second data compression means are provided for compressing the forwarding addresses according to said data compression algorithm and storing the compressed forwarding addresses in the routing table storing means, the routing unit being configured such that it compares the compressed destination address identifier with the compressed forwarding addresses stored in the routing table storing means.

37. The routing apparatus according to claim 36, wherein the first and second data compression means are configured such that they use a lossless data compression algorithm which reduces redundancy in the destination address identifier and the forwarding addresses, respectively, without losing any information content.