Efficient ipv4/ipv6 best matching prefix method and apparatus

• US 20050171959A1
• Filed: 02/14/2003
• Published: 08/04/2005
• Est. Priority Date: 02/14/2002
• Status: Active Grant

• Current Assignee: Transwitch Corporation
• Original Assignee: Transwitch Corporation
• Inventors: Deforche, Koen, Olbrechts, Jan, De Coster, Luc
• Granted Patent: US 7,433,871 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 61/25 of the same type
• CPC Class Codes: H04L 61/255 Maintenance or indexing of mapping tables
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention provides a data-structure to store a search database and provides techniques to build this datastructure given a list of prefixes (P) and to search this database efficiently for a best matching prefix for an address D. The data-structure can be stored in standard memory (14), where values are stored associated with memory address locations. The data structure includes representations of addressable linked tables (FIG. 3b). The representations are related to a binary search trie (FIG. 1) and each linked table (T) has at least one entry. Entries in a table span more than one level of the binary search trie. The spanning feature relates to compression of a binary search trie into a finite number of levels (and hence tables). The finite number is less than the number of levels in the binary search trie. Hence the search algorithm is restricted to a finite, and predetermined number of search accesses to the tables to obtain a best-match result.

Claims

1-28. -28. (canceled)

29. A memory for use in a search algorithm for addresses in a telecommunications system comprising:

a data structure stored in said memory, said data structure comprising representations of addressable linked tables, said representations being related to a search trie, each linked table comprising at least one entry, each entry comprising skip information, no-match result information and one of next table information and a match result.

30. The memory according to claim 29, wherein a linked table comprises information relating to at least one node of a binary search trie.

31. The memory according to claim 29, wherein the skip information includes a skip length and a skip value.

32. The memory according to claim 29, wherein the next table information includes a next table size and a next table address location.

33. The memory according to claim 30, wherein entries in a table span more than one level of the binary search trie.

34. The memory according to claim 30 wherein the skip information includes a skip length and a skip value, and

the next table information includes a next table size and a next table address location.

35. A data structure for use in a search algorithm for addresses in a telecommunications system comprising:

representations of addressable linked tables, said representations being related to a search trie, each linked table comprising at least one entry, each entry comprising skip information, no-match result information and one of next table information and a match result.

36. The data structure according to claim 35, wherein a linked table comprises information relating to at least one node of a binary search trie.

37. The data structure according to claim 35, wherein the skip information includes a skip length and a skip value.

38. The data structure according to claim 35, wherein the next table information includes a next table size and a next table address location.

39. The data structure according to claim 36, wherein entries in a table span more than one level of the search trie.

40. A network element of a telecommunications network, comprising:

memory means storing representations of addressable linked tables, said representations being related to a search trie, each linked table comprising at least one entry, each entry comprising skip information, no-match result information and one of next table information and a match result; and

a memory controller for accessing said table entries.

41. The network element according to claim 40, wherein the skip information includes a skip length and a skip value.

42. The network element according to claim 40, wherein the next table information includes a next table size and a next table address location.

43. The network element according to claim 40, wherein the memory controller comprises means for searching the search trie by sequentially accessing a set of table entries, each entry being from a different table and for outputting at least one of a match result and the last encountered valid no-match result.

44. The network element according to claim 40, wherein the memory controller comprises means for comparing at least one bit of an address to be searched with a skip value in a table entry.

45. The network element according to claim 44, further comprising means for taking one or more bits of an address and using it to index a table.

46. The network element according to claim 40, wherein the memory controller comprises means for comparing one or more bits of an address with a first or a second binary value depending upon the next table information.

47. The network element according to claim 40, further comprising a table entry determining means for determining values in the table entries in the memory.

48. The network element according to claim 47, wherein the table entry determining means determines the values in the table entries so that the memory controller outputs a match result or the last encountered valid no-match result for an address at least within a predetermined maximum number of accesses to the table entries.

49. The network element according to claim 40, wherein entries in a table span more than one level of the binary search trie.

50. The network element according to claim 40, wherein the element is a router.

51. A method for determining an address in a telecommunications network, comprising:

storing representations of addressable linked tables in a memory, said representations being related to a search trie, each linked table comprising at least one entry, each entry comprising skip information, no-match result information and one of next table information and a match result;

accessing said linked tables in accordance with the search trie; and

outputting one of a match result and the last encountered valid no-match result.

52. The method according to claim 51, wherein the skip information includes a skip length and a skip value.

53. The method according to claim 51, wherein the next table information includes a next table size and a next table address location.

54. The method according to claim 51, wherein the step of accessing the linked tables for searching the search trie includes sequentially accessing a set of table entries, each entry being from a different table.

55. The method according to any of claim 51, further comprising the step of comparing at least one bit of an address with a skip value in a table entry.

56. The method according to claim 55, further comprising taking one or more bits of an address and using it to index a table.

57. The method according to any of claim 51, further comprising comparing one or more bits of an address with a first or a second binary value depending upon the next table information.

58. The method according to any of claim 51, wherein entries in a table span more than one level of the search trie.