CN100375463C - A Method of Realizing Longest Prefix Address Routing Lookup Using Segment Compression Table - Google Patents

Abstract

The invention relates to the technical field of data communication, and relates to a method for realizing longest prefix address routing search. This method establishes a two-level routing information table: a 64K section table and a compressed offset table, and compresses the routing index value in the offset table into the difference between the index value and the reference routing index of this section, and stores the routing lookup information through this method. When searching, first use the upper 16 bits of the target IPv4 address to be searched as the index value, and locate the entry in the 64K segment table: determine whether the compression offset table pointer in the entry is invalid? If so, the routing index in this entry is the next-hop routing index value corresponding to the target IPv4 address; if not, then the pointer value, reference value and compression table corresponding to the IPv4 address are obtained according to this entry The width of the table entry, access the corresponding compressed offset table entry with the lower 16 bits of the target IPv4 address as the offset, and obtain the next-hop routing index value of the IPv4 address through calculation.

Description

A Method of Realizing Longest Prefix Address Routing Lookup Using Segment Compression Table

technical field

The invention relates to the technical field of data communication. In particular, a method for realizing routing lookup of IPv4 longest prefix address by using segmentation and compression technology. The method can be used in routers, layer-3 switches, access servers and other devices in the IPv4 Internet that need to search for IPv4 address routing.

Background technique

Route lookup is one of the basic functions of routers, Layer 3 switches and other devices. The IP address is composed of <network identifier, host identifier>, and the forwarding of IP packets is performed according to the network identifier. In the early days, IP addresses were fixed at 8, 16, and 24 bits according to the length of the network identifier, corresponding to class A, B, and C addresses respectively. Classless Inter-Domain Routing (CIDR) allows address aggregation of any length, so that the network identification length of the IP address is no longer limited to 8 bits, 16 bits, and 24 bits, but can be any value from 8 to 32 bits. The routing information in the routing table is given by <address prefix/prefix length, next hop address (index)>. When performing an IPv4 address lookup, the original exact match is replaced by the longest prefix match (LPM), that is, it is necessary to search the routing prefix database for the entry with the longest matching prefix with the destination address of a given IP packet.

Due to the complexity of the longest prefix match search, the burden on the processor is greatly increased; coupled with the continuous improvement of the network's requirements on the forwarding speed of the router, the route search has become one of the main bottlenecks affecting the performance of the router.

When evaluating the performance of an IP address lookup method, it is necessary to comprehensively consider the search speed that this method can achieve (generally measured by the number of packet searches per second (pps)), and the memory capacity required to store a certain routing table item. , the update overhead and complexity of the lookup table, and the ease of implementation, power consumption, area, etc., among which the lookup speed, update overhead, and memory capacity of the lookup method are more important.

How to improve the search speed of the IP address search method, reduce the update overhead and memory capacity, and achieve a balance of performance in all aspects has become the research direction of some people in the industry, and they have proposed many different search methods.

Contents of the invention

(1) Technical problems to be solved

The purpose of the present invention is to provide a method for realizing routing lookup of IPv4 longest prefix address. The method has high-speed IPv4 longest prefix address routing lookup capability and forwarding table update capability, and requires less storage space.

(2) Technical solutions

In order to achieve the above object, technical solution of the present invention is achieved in that way:

A method for realizing the longest prefix address routing lookup by using segmented compression tables, selecting the bit width of the routing reference index field of the compressed offset table and the bit width of the pointer field of the compressed offset table, and establishing two-level tables in the memory: 64K segments The table (Segment Table) and the compressed offset table (Compressed OffsetTable) store the routing index information by compressing the routing index value of the original offset table in the compressed offset table into the difference between the index value and the reference routing index of this segment. When searching, first use the upper 16 bits (IP _H16 ) of the target IPv4 address to be searched as the index value, and locate the entry in the 64K segment table: judge whether the compressed offset table pointer value (pOffetTable) in the entry is invalid (all 1 value). If the pointer value is invalid, it means that the segment route index (NH _seg ) in this table entry is the next-hop route index value (NHI) corresponding to the target IPv4 address; The IPv4 address corresponds to the entry address of the compressed offset table, and the current next-hop routing index value (NHI _current ) is obtained from the value of the segment routing index field (NH _seg ). Use formula 1 to calculate the entry width EntryWidth of the compressed offset table, and use the lower 16 bits (IP _L16 ) of the IPv4 address and the width of the compressed offset table entry to calculate the entry width of the IPv4 address in the compressed offset table through formula 2 Word offset (Offset _word ), the bit offset (Offset _bit ) of the IPv4 address in the word is calculated by formula 3, and the compression offset table routing reference value (BaseIndex) is calculated. Accessing this IPv4 address corresponds to compression The word offset word in the offset table is used to obtain the next-hop routing index offset (Offset _NH ) whose bit width is EntryWidth. Determine whether the next-hop routing index offset value is all 1 (2 ^EntryWidth -1)? If yes, it means that the next-hop routing index (NHI) corresponding to this IPv4 address is equal to the current one-hop index value (NHI _current ); if not, the next-hop routing index value (NHI) of the IPv4 address is calculated by formula 4.

Formula 1: EntryWidth=2 ^WidthIndex

Formula 2: Offset _word = Int((EntryWidth×IP _L16 )/Width _word )

Formula 3: Offset _bit ＝((EntryWidth×IP _L16 ))-(Offset _word ×Width _word )

Formula 4: NHI=BaseValue+Offset _NH

Among them: Width _word is the bit width of the memory where the compressed offset table is located

Int means rounding

BaseValue is the route index base value obtained according to the route base index value (BaseIndex).

In the 64K segment table mentioned above, each entry consists of four segment routing index (NH _seg ), compression offset table pointer (pOffetTable), routing reference index (BaseIndex) and compression table entry width index (WidthIndex) field composition. See Figure 1 for illustration.

The segment routing index field has a bit width of 8 bits and is stored in the most effective position of the entry. It is initialized to 0xFF, indicating that there is no valid next-hop route.

The bit width index field of the compressed offset table entry is 2 bits, stored in the most significant bits adjacent to the compressed offset table pointer in the entry, and initialized to all 1s, that is, 0x3. According to the bit width index of the entry in the compression offset table, the number of bits occupied by each entry in the compression offset table can be calculated by formula 1.

The compressed offset table pointer field is stored in the least significant bits of the table entry. The bit width of the compressed offset table pointer field can be determined by the specific implementation plan, and the value is 16 bits or 14 bits, and is initialized to a value of all 1s, that is, initialized to 0xFFFF (the field bit width is 16 bits), 0x3FFF (the field bit width is 14 bits) and 0xFFFF (the field bit width is 14 bits). bit), indicating that it is invalid and no further search is required; when searching, if the pointer value is not equal to the initial value of all 1s (0x3FFF when the field bit width is 14 bits, and 0xFFFF when the field bit width is 16 bits), it means that further Search, and this pointer value is the starting address of the compressed offset table corresponding to the target IPv4 address.

The bit width of the routing reference index field is a corresponding length according to the bit width of the pointer field of the compression offset table, and is stored in the low-high effective position adjacent to the segment routing index in the entry. When the bit widths of the compression offset table pointer field are 14 and 16 bits respectively, the bit widths of the routing index reference field are 6 bits and 8 bits respectively.

In the above-mentioned compressed offset table, each entry is composed of a routing index difference field with a bit width of EntryWidth bits, indicating the difference between the routing index value and the segment routing index, as shown in Figure 2.

When the routing base index (BaseIndex) field bit width is 8 bits, the routing base value (BaseValue) is equal to the routing base index field value: when the routing base index field bit width is 6 bits, the routing base value is given by the following formula 5:

Formula 5: BaseValue=4×BaseIndex

Each entry of the 64K segment table is a 32-bit long word, composed of a segment routing index field (31:24 bits), a compression offset table routing index reference value field (23:18 bits or 23:16 bits ), a compressed offset table entry width index field (17:16 bits or 15:14 bits) and a compressed offset table pointer field (15:0 bits or 13:0 bits) consisting of four fields.

In the 64K section table, the highest 8-bit (31:24) section routing index of the entry is an index pointing to the routing table, and it is initialized to 0xFF to indicate that there is no valid next-hop route by default; if the section routing index is equal to the initial value of the routing index , indicating that there is no valid next-hop route; if the segment route index is not equal to the initial value of the route index, its value is the index value of the next-hop route corresponding to the IPv4 address.

The 64K section table, the compressed offset table routing reference index value (23:18 bits or 23:16 bits) of the entry is the reference index value of the compressed offset table routing index value, initialized to 0x3F (the field bit width is 6 bits) or 0xFF (when the field bit width is 8 bits), it is meaningful only when the compression offset table pointer in the same entry is not the initial value of the compression offset table pointer; when the field bit width is 6 bits, the compression offset table pointer The routing index reference value of the shift table is equal to 4 times the routing reference index value of the compressed offset table; when the field bit width is 8 bits, the routing index reference value of the compressed offset table is equal to the routing reference index value of the compressed offset table.

In the 64K segment table, the compressed offset table entry width index (17:16 bits or 15:14 bits) of the entry is an index value indicating the width of the compressed offset table entry, and is initialized to the compressed offset table entry The initial value of the width index is 0x3, which is meaningful only when the compression offset table pointer in the same entry is not the initial value of the compression offset table pointer.

The 64K segment table, the compression offset table pointer (15:0 bit or 13:0 bit) of the entry is a pointer pointing to the start address of the compression offset table corresponding to this entry, initialized to 0xFFFF (field bit width 16 bits) or 0x3FFF (when the field width is 14 bits), if the compression offset table pointer value is equal to the compression offset table pointer initial value, it means that there is no corresponding compression offset table for this entry, and no further search is required; If the value of the compression offset table pointer is not equal to the initial value of the compression offset table pointer, it means that there is a corresponding compression offset table for this entry, and further routing search is required, and the value of the compression offset table pointer is the compression offset table corresponding to this entry. The start address of the shift table.

The compressed offset table routing reference value represents the next hop routing reference value of the compressed offset table, and the compressed offset table routing reference value is equal to 4 times the compressed offset table routing reference index value (the compression offset table routing reference value in the 64K segment table When the bit width of the index field is 6 bits), or the routing reference value of the compression offset table is equal to the routing reference index value of the compression offset table (when the bit width of the routing reference index value field of the compression offset table in the 64K segment table is 8 bits).

Each entry in the compressed offset table is composed of a routing index offset field, and the bit width of the entry is equal to the power of the index value of the compressed offset table entry width of 2, indicating that the next hop routing index value corresponding to the entry is equal to The difference between the routing reference value of the compressed offset table, initialized to all 1 values, if the value of the compressed offset table entry is equal to the initial value of the compressed offset table entry, it means that the next-hop routing index value is equal to the 64K to which the compressed offset table belongs The segment routing index value in the segment table entry; if the value of the compression offset table entry is not equal to the initial value of the compression offset table entry, it means that the next hop routing index value is equal to the entry value and the compression offset table routing reference value Sum.

As shown in Figure 4, Figure 4 is the longest prefix address routing search method provided by the present invention, and the method has the following implementation steps:

(1), select the compression offset table pointer and the routing reference index field bit width and the compression offset table pointer field bit width in the selected specific embodiment 64K segment table entry.

(2), first expand, sort and group the original routing information table: expand the routing information with a prefix length of less than 16 bits in the original routing record into a record with a prefix length of 16; make the prefix length greater than 16 bits and less than 32 bits The route entries of the route are all expanded into a route prefix with a length of 32 bits, grouped according to the high 16 bits of the prefix, and arranged in groups according to the length of the route prefix from small to large;

Routing information extension refers to extending the IP address prefix in the original routing information from the original prefix to a group of address prefixes of the specified length, which is a group of address prefixes contained in the original address prefix, but the effective value of the prefix length in the expanded routing information is different from the next The jump index value does not change. For example, after expanding the routing item <8.0.0.0/8, 25> (prefix/prefix length, next hop address) to 16 bits, the routing item group that can be obtained is <8.0.0.0/8, 25>, <8.1. 0.0/8, 25>, <8.2.0.0/8, 25>...<8.254.0.0/8, 25>, <8.255.0.0/8, 25>.

According to the upper 16 bits of the target IPv4 address, the group is arranged according to the length of the route prefix from small to large.

Determine the bit width of the two fields of the compression offset table pointer (pOffetTable) and the routing reference index (BaseIndex) in the implementation scheme.

(3) Initialize the 64K segment table and construct the 64K segment table: Fill the information items with prefix length less than or equal to 16 bits in each group of routing information into the corresponding entries of the 64K segment table in order of prefix length from small to large , Construct a 64K segment table. Each entry in the table consists of four fields: segment routing index (NHseg), compression offset table pointer (pOffetTable), routing base index (BaseIndex) and compression table entry width index (WidthIndex), among which the routing base index field, The compression offset table pointer field, the compression table entry width index field, and the segment routing index field are filled with initial values (all 1s).

The 64K segment table has 64K entries and occupies a storage space of

64K×Width _word bits

(4), the initialization operation of the compression offset table, construct the compression offset table corresponding to each entry in the 64K section table: count the next-hop routing index value corresponding to the information whose prefix length is greater than 16 bits in each group of routing information Take the minimum value NH _min and the maximum value NH _max as the next hop routing index value (BaseValue). If the routing reference index field selected in 1 is 6, then calculate the routing reference index value according to formula 6; if the routing reference index field selected in 1 has a bit width equal to 8 bits, then select the routing reference index value equal to the routing reference value.

Formula 6: BaseIndex=Int(BaseValue/4)

Select the width index value WidthIndex of the compression offset table entry so that it satisfies the following conditions at the same time:

WidthIndex＝log EntryWidth ①

EntryWidth＝{min(i)|BaseValue+2 ⁱ -1＞NH _max ，i∈N}②

Apply for a memory space whose size is EntryWidth×64K bits, and fill its head address into the compressed offset table pointer field in the 64K segment table. Fill the routing base value index BaseIndex and compression offset table entry width index value WidthIndex into the corresponding fields in the 64K segment table.

Initialize the compressed offset table with all 1s. Calculate the difference between the next hop route index value and the route reference value in each group of route information entries with a prefix length greater than 16, and fill in the compressed offset with the bit width EntryWidth in the order of prefix length from small to large Corresponding bit ranges in the table.

(5), get the upper 16 bits of the target IPv4 address as the index value, and locate the entry in the 64K section table: judge whether the compression offset table pointer value (pOffetTable) in the entry is invalid (all 1 values). If the compression offset table pointer is invalid, transfer to 6; if the compression offset table pointer value is valid, transfer to 7.

(6) Determine whether the route index field value in the entry is invalid (0xFF)? If the segment routing index (NH _seg ) value is 0xFF (all 1s), then the target IPv4 address does not have a corresponding valid next-hop route; if not, the routing index value in the entry is the next hop corresponding to the target IPv4 address Routing index value (NHI). end of search

(7), obtain the entry address of this IPv4 address corresponding compression offset table, route benchmark index value (BaseIndex) and compression table entry width index value (WidthIndex) according to the compression offset table pointer value in this entry, make current next The hop routing index value (NHI _current ) is equal to the segment routing index (NH _seg ). Use formula 1 to calculate the entry width EntryWidth of the compressed offset table, and use the lower 16 bits (IP _L16 ) of the IPv4 address and the width of the compressed offset table entry to calculate the entry width of the IPv4 address in the compressed offset table through formula 2 word offset (Offset _word ), calculate the bit offset (Offset _bit ) of the IPv4 address in the word by formula 3, and calculate the routing reference value of the compressed offset table.

(8), visit the offset _word in this IPv4 address corresponding compression offset table with offset offset word, obtain the next hop routing index value offset (Offset _NH ) that bit width is EntryWidth. Determine whether the next-hop routing index offset value is 2 ^EntryWidth -1. If yes, the next-hop routing index (NHI) corresponding to this IPv4 address is equal to the current one-hop index value (NHI _current ); if not, the next-hop routing index value (NHI) is calculated by formula 4. If the NHI is a value of all 1s, there is no next-hop route corresponding to this IPv4 address; if not, the next-hop route corresponding to this IPv4 address is NHI, and the search ends.

(3) Beneficial effects

As can be seen from the foregoing technical solutions, the present invention has the following beneficial effects:

The method of the present invention can have high-speed searching ability and updating ability, and needs less storage space at the same time. The feature of the method for realizing the IPv4 routing search in the present invention is that only two forwarding tables with simple structures and a compressed offset table need to be established. The operation steps of the table construction process are simple, fast and effective. Compared with the existing IPv4 route query methods of various segments and compressions, the method has the following advantages: the search speed is relatively fast, and only two memory accesses are required; the storage space required by the implementation method is small; and the update cost is small.

Compared with the existing IPv4 address fast lookup algorithms realized by various segmentation and compression, the method has higher comprehensive performance, and better solves the contradiction between search speed and update speed, search speed and memory capacity. An IPv4 address lookup requires at most 2 memory accesses; the compression of the second-level table reduces a large amount of memory space; meanwhile, due to the simplicity of the compression algorithm, the compression of the second-level table does not increase the update overhead of the traditional segment table. The 64K segment table entry structure is simple but the amount of information is rich, which solves the phenomenon of routing lookup backtracking that may occur in the segmentation algorithm.

The content of the present invention is simple and easy to realize. The required storage capacity is small, and the algorithm is simple and easy to implement. It can be implemented by FPGA in hardware, or can be implemented in software by using an ordinary PC or access server. The invention can be applied to three-layer switches, routers and other devices that need to complete IP network route search.

Description of drawings

FIG. 1 is a schematic diagram of a configuration method of a 64K segment table entry in the present invention.

Fig. 2 is a schematic diagram of the second configuration mode of the 64K segment table entry in the present invention.

Fig. 3 is a schematic diagram of the structure of the compression offset table entry in the present invention.

Fig. 4 is a flow chart of the operation steps of implementing the method of the present invention.

Fig. 5 is a structural diagram of the hardware implementation system of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be described in further detail below in conjunction with specific embodiments and with reference to the accompanying drawings.

In the 64K segment table and the compression offset table, each field is initialized to all 1 values, which means invalid (except for the entry width field of the compression offset table). When searching, if the segment routing index field value in the 64K segment table is all 1, it indicates an invalid route; the compression offset table pointer field value in the 64K segment table is all 1, indicating that there is no compression offset table in this segment; If the value of an entry in the table is all 1s, it means that the corresponding next-hop route index value is a segment route index, and formula 4 is not used for calculation.

During specific implementation, firstly, the bit width of the routing reference index field of the compression offset table and the bit width of the pointer field of the compression offset table are selected according to the actual application environment.

When searching, first use the upper 16 bits (IP _H16 ) of the target IPv4 address to be searched as the index value, and locate the entry in the 64K segment table: judge whether the compressed offset table pointer value (pOffetTable) in the entry is invalid (all 1 value). If the pointer value is invalid, then the segment route index (NH _seg ) in this entry is the next-hop route index value (NHI) corresponding to the target IPv4 address; if not, it is obtained according to the compressed offset table pointer value in this entry The IPv4 address corresponds to the entry address of the compression offset table, the routing base index value (BaseIndex) and the compression table entry width index value (WidthIndex), so that the current next-hop routing index value (NHI _current ) is equal to the segment routing index (NH _seg ). Calculate the entry width EntryWidth of the compressed offset table, use the lower 16 bits (IP _L16 ) of the IPv4 address and the entry width of the compressed offset table to calculate the word offset (Offset _word ), bit offset (Offset _bit ), access the word offset word in the compressed offset table corresponding to this IPv4 address, and obtain the next-hop routing index value offset (Offset _NH ) whose bit width is EntryWidth. Determine whether the next-hop routing index offset value is all 1s (2 ^EntryWidth -1). If yes, the next-hop routing index (NHI) corresponding to this IPv4 address is equal to the current one-hop index value (NHI _current ); if not, the next-hop routing index value (NHI) of the IPv4 address is calculated by formula 4.

According to the difference in the bit width of the next hop routing reference index field and the compression offset table pointer field in the selected 64K segment table during the specific implementation of the method, the implementation of the method can be specifically divided into two situations: the next hop routing reference index field The width is 6 bits, and the bit width of the compressed offset table field is 16 bits; the width of the next hop routing reference index field is 8 bits, and the bit width of the compressed offset table pointer field is 14 bits.

The width of the next hop routing reference index field in the 64K segment table is 6 bits

The segment routing index field in the 64K segment table has a bit width of 8 bits, the next hop routing reference index field has a bit width of 6 bits, the compressed offset table entry width index field has a bit width of 2 bits, and the compressed offset table pointer field has a 16-bit bit width . The field definitions are:

Data bit (bit) Field bit width (bits) Field name (FieldName) Description 31:24 8 Segment routing index (NH_seg) Point to the index value of the next-hop route; initialized to 0xFF; when the field value is 0xFF, it means that there is no valid next-hop route; when the field value is not 0xFF, it means the index value of the next-hop route

23:18 6 Compressed offset table routing base index (BaseIndex) The index of the next hop routing reference value in the compression offset table; initialized to 0xFF; only meaningful when the compression offset table pointer is valid; the routing reference value is equal to 4 times the routing reference index value 17:16 2 Compression offset table entry width index (WidthIndex) The index of the bit width occupied by each entry in the compressed routing table; initialized to 0xFF; only meaningful when the pointer of the compressed offset table is valid; the width of the compressed offset table entry is the WidthIndex power of 2 15:0 16 Compression offset table pointer Point to the first address of the compression offset table; initialized to all 1 values (0xFFFF); when the value is 0xFFFF, it means invalid, and there is no corresponding compression offset table; when the value is not 0xFFFF, it means that this entry corresponds to

Head address of compression offset table

The width of the next hop routing index reference field in the 64K segment table is 8 bits

The segment routing index field in the 64K segment table has a bit width of 8 bits, the next hop routing reference index field has a bit width of 8 bits, the compression offset entry width index field has a bit width of 2 bits, and the compression offset table pointer field has a bit width of 14 bits. The next-hop routing reference value in the compression offset table is equal to the next-hop routing reference index value in the segment table.

Data bit (bit) Field bit width (bits) Field name (FieldName) Description 31:24 8 Segment routing index (NH_seg) Point to the index value of the next-hop route; initialized to 0xFF; when the field value is 0xFF, it means that there is no valid next-hop route; when the field value is not 0xFF, it means the index value of the next-hop route 23:16 8 Compressed offset table routing base index (BaseIndex) The index of the next hop routing reference value in the compressed offset table; initialized to 0xFF; only meaningful when the compressed offset table pointer is valid;

The routing reference value is equal to the routing reference index value 15:14 2 Compression offset table entry width index (WidthIndex) The index of the bit width occupied by each entry in the compressed routing table; initialized to 0xFF; only meaningful when the pointer of the compressed offset table is valid; the width of the compressed offset table entry is the WidthIndex power of 2 13:0 14 Compression offset table pointer Point to the first address of the compression offset table; initialized to all 1 values (0x3FFF); when the value is 0x3FFF, it means invalid, and there is no corresponding compression offset table; when the value is not 0x3FFF, it means that this entry corresponds to the first address of the compression offset table

If the specific implementation plan selects the bit width of the pointer field of the compression offset table as 16 bits, and the reference index field of the compression offset table is 6 bits: the value range of the pointer field of the compression offset table is 0-65535, and a value 65535 representing an invalid pointer is removed (0xFFFF), this field can still distinguish 65535 different compression offset tables; at the same time, the compression offset table reference index field is limited by the bit width, and the value range is 0-63, which cannot fully represent the possible values of the routing index. This method adopts a 4 times value algorithm to expand the routing reference index value into the routing reference value. In some cases, the compression efficiency of offset tables is limited.

If the specific implementation plan selects the bit width of the pointer field of the compression offset table as 14 bits, and the reference index field of the compression offset table is 8 bits: the reference index field of the compression offset table can represent any value in 0-255, and the compression efficiency of the offset table is obtained Improve; the value range of the compression offset table pointer field is changed to 0-16383. After removing a value 16383 (0x3FFF) indicating an invalid pointer, the number of different compression offset tables that can be distinguished by this field is 16383.

It can be seen from the above analysis that the combination of the two field bit width definitions has its own advantages and disadvantages. When this method is actually implemented, it should be selected according to the actual network routing conditions to which the method is applied.

The compression offset table corresponding to each entry of the 64K segment table is composed of routing index offset fields sequentially, and each entry represents a routing index offset field.

The present invention can be realized by software programming on an ordinary PC or server, the process of table construction and longest prefix search is completed by software, and the 64K segment table and compressed offset table are stored in the computer memory.

The present invention can also be realized in hardware by using FPGA, and the specific implementation system structure diagram is shown in FIG. 5 . The table construction and the longest prefix lookup process are completed by the hardware logic unit, and the 64K segment table and compressed offset table are stored in static random access memory (SRAM) or dynamic dynamic access memory (DRAM).

Claims (9)

1. longest-prefix address method for searching route is characterized in that this method comprises:

Selected compression deviation table route benchmark index field bit wide and compression deviation list index field bit wide are set up 64K segment table and compression deviation table two-stage form and are stored routing index information by the method that compression deviation table Central Plains offset table routing index value is compressed into this index value and the accurate routing index difference of this segment base in memory;

When searching, use earlier the Target IP v4 address of desiring to search high 16 as index value, in the 64K segment table, locate list item, judge whether compression deviation list index value is invalid in this list item, if pointer value is invalid, then this list item stage casing routing index is corresponding next the jumping routing index value of this Target IP v4 address institute; If not, obtain the initial address of the corresponding compression deviation table in this IPv4 address according to compression deviation list index value in this list item, route benchmark index value and compaction table list item width index value, section routing index value, calculate this compression deviation table list item width, compression deviation table route fiducial value, use low 16 and the compression deviation table list item width gauge of this IPv4 address to calculate the word offset amount of this IPv4 address in the compression deviation table, the bit offset amount, visit word offset amount word and bit offset scale item in the corresponding compression deviation table in this IPv4 address, obtain next and jump routing index value side-play amount, do you judge that next jumps the routing index offset value is complete 1 value? if then corresponding next the jumping routing index in this IPv4 address promptly equals when the previous dive index value; If not, calculate next jumping routing index value of this IPv4 address by formula.

2. longest-prefix according to claim 1 address method for searching route, it is characterized in that: each bar list item of described 64K segment table all is the long word of one 32 bit, by section routing index field, compression deviation table routing index fiducial value field, compression deviation table list item width index field and compression deviation list index field totally four fields constitute, described section routing index field is positioned at 31 to 24 bits, described compression deviation table routing index fiducial value field is positioned at 23 to 18 bits or 23 to 16 bits, described compression deviation table list item width index field is positioned at 17 to 16 bits or 15 to 14 bits, and described compression deviation list index field is positioned at 15 to 0 bits or 13 to 0 bits.

3. longest-prefix according to claim 2 address method for searching route, it is characterized in that: described 64K segment table, the highest 8 bits of list item, i.e. 31 to 24 bits, the section routing index is the index that points to routing table, is initialized as 0xFF and represents that acquiescence do not have that effectively next jumps route; When if the section routing index equals the routing index initial value, effectively next jumps route to the expression nothing; If the section routing index is not equal to the routing index initial value, its numerical value is the index value of corresponding next the jumping route in IPv4 address.

4. longest-prefix according to claim 2 address method for searching route, it is characterized in that: described 64K segment table, the compression deviation table route benchmark index value of list item, promptly 23 to 18 bits or 23 to 16 bits are benchmark index values of compression deviation table routing index value; When the field bit wide is 6 bits, be initialized as 0x3F, perhaps when the field bit wide is 8 bits, be initialized as 0xEF, meaningful when only the compression deviation list index is not compression deviation list index initial value in list item; When the field bit wide is 6 bits, the compression deviation table route benchmark index value that compression deviation table routing index fiducial value equals 4 times; When the field bit wide was 8 bits, compression deviation table routing index fiducial value equaled compression deviation table route benchmark index value.

5. longest-prefix according to claim 2 address method for searching route, it is characterized in that: described 64K segment table, the compression deviation table list item width index of list item, 17 to 16 bits or 15 to 14 bits, it is the index value that indicates compression deviation table list item width, be initialized as compression deviation table list item width index initial value 0x3, meaningful when only the compression deviation list index is not compression deviation list index initial value in list item.

6. longest-prefix according to claim 2 address method for searching route, it is characterized in that: described 64K segment table, the compression deviation list index of list item, 15 to 0 bits or 13 to 0 bits, be point to this list item the pointer of corresponding compression deviation table initial address, when being 16 bits, the field bit wide is initialized as 0xFFFF, perhaps when being 14 bits, field width is initialized as 0x3FFF, if compression deviation list index value equals compression deviation list index initial value, represent that there is not corresponding compression deviation table in this list item, does not need further to search; If compression deviation list index value is not equal to compression deviation list index initial value, represent that there is corresponding compression deviation table in this list item, need carry out further route querying, and the value of compression deviation list index is the initial address of the compression deviation table of this list item correspondence.

7. longest-prefix according to claim 1 address method for searching route, it is characterized in that: compression deviation table route fiducial value is represented next jumping route fiducial value of compression deviation table, the compression deviation table route benchmark index value that compression deviation table route fiducial value equals 4 times when compression deviation table route benchmark index field bit wide is 6 bits in the 64K segment table, perhaps compression deviation table route fiducial value equals compression deviation table route benchmark index value when compression deviation table route benchmark index value field bit wide is 8 bits in the 64K segment table.

8. require 1 described longest-prefix address method for searching route according to the root profit, it is characterized in that: each bar list item of described compression deviation table is made of the routing index offset field, the compression deviation table list item width index value time power that the list item bit wide equals 2, next of expression list item correspondence jumped the difference of routing index value and compression deviation table route fiducial value, be initialized as complete 1 value, if compression deviation table list item value equals compression deviation table list item initial value, represent that next jumping routing index value equals the section routing index value in the affiliated 64K segment table list item of this compression deviation table; If the value of compression deviation table list item is not equal to compression deviation table list item initial value, represent that next jumping routing index value equals list item value and compression deviation table route fiducial value sum.

9. longest-prefix according to claim 1 address method for searching route, it is characterized in that: this method has following implementation step:

(1), the bit width of compression deviation list index and two fields of route benchmark index in the selected implementation;

(2), the primary routing information table is expanded, sorted and divides into groups: it is 16 record that prefix length in the primary routing record all is extended to prefix length less than the routing iinformation of 16 bits; Prefix length all is extended to the route prefix that length is 32 bits greater than 16 bits and less than the route entry of 32 bits,, discharges from small to large according to the length of route prefix in the group according to high 16 bit groupings of prefix;

(3), the initialization behaviourization of 64K segment table, make up the 64K segment table: prefix length in every group of routing iinformation is inserted the corresponding list item of 64K segment table smaller or equal to the item of information of 16 bits successively according to the ascending order of prefix length, structure 64K segment table.Every list item is by section routing index NH in the table _Seg, compression deviation list index, route benchmark index and four fields of compaction table list item width index form, wherein route benchmark index field, compression deviation list index field and compaction table list item width index field and section routing index field are inserted initial value, have 64K bar list item altogether, the memory space that takies is 64K * 32 bits;

(4), the initialization operation of compression deviation table, make up the compression deviation table: count in every group of routing iinformation prefix length greater than the information institute of 16 bits corresponding next jump minimum value NH in routing index value _MinWith maximum NH _MaxGet its minimum value and jump the routing index value for next, calculate route benchmark index value, choose compression deviation table list item width index value, application is of a size of the storage space of EntryWidth * 64K bit, its first address is inserted compression deviation list index field in the 64K segment table, route base value index BaseIndex and compression deviation table list item width index value WidthIndex are inserted in the 64K segment table corresponding field separately, use complete 1 initialization compression deviation table, respectively prefix length in every group of route is calculated greater than 16 routing iinformation clauses and subclauses that next jumps the difference between routing index value and route fiducial value in the routing iinformation, insert corresponding bit scope in the compression deviation table with bit wide EntryWidth according to prefix length order from small to large;

(5), get Target IP v4 address high 16 as index value, in the 64K segment table, locate list item: judge whether compression deviation list index value invalid in this list item, promptly whether complete 1 value? if invalid, change (6) over to; If compression deviation list index value is effective, change (7) over to

(6), judge this list item stage casing routing index NH _SegIs value 0xFF? if then this Target IP v4 address is unmatchful should effectively next jump route; If not, then in the list item routing index value be this Target IP v4 address institute corresponding next jump routing index value NHI;

(7), obtain entry address, route benchmark index value and compaction table list item width index value and the section routing index value of the corresponding compression deviation table in this IPv4 address according to compression deviation list index value in this list item, calculate this compression deviation table list item width, use low 16 IP of this IPv4 address _L16Calculate word offset amount and the bit offset amount of this IPv4 address in the compression deviation table with compression deviation table list item width gauge;

(8), with side-play amount Offset _WordVisit the side-play amount word in the corresponding compression deviation table in this IPv4 address, obtaining bit width is next jumping routing index value side-play amount of EntryWidth, do you judge that next jumps the routing index offset value is complete 1 value? if then corresponding next the jumping routing index NHI in this IPv4 address promptly equals as previous dive index value NHI _CurrentIf not, calculate next and jump routing index value NHI, if NHI is complete 1 value, then this IPv4 address does not have corresponding next jumping route; If not, then corresponding next the jumping route in this IPv4 address is NHI.

Images