WO2008028412A1 - A routing method, a routing apparatus and a method for storing routing information - Google Patents

Abstract

The invention provides a routing method, a routing apparatus and a method for storing routing information. The routing method includes the step as follows: receiving the data messages; acquiring the compressed index information of routing table according to index information of routing table in the data message; matching the compressed index information of routing table with the index information of routing table which locates in the Content Addressable Memory; routing the data message by the matched index information of routing table; a unit of Content Address Memory can contain one or one more index information of routing table which is compressed with the first compressed format. According to the compressed index information of every routing table, a unit of CAM can contain the multi compressed index information of routing table; the CAM can store more index information of routing table, the efficiency using CAM is improved; the capacity of routing table is enlarged. The invention overcome the shortcoming such as follows: when using the CAM in prior art, the cost of routing apparatus is high, and the capacity of routing table is limited a lot.

Description

 Description Routing method, routing device, and routing information storage method

 [1] Technical field

 [2] The present invention relates to the field of network communication technologies, and in particular, to a routing method, a routing device, and a routing information storage method.

[3] Background of the invention

 [4] Currently, there are two main types of IP in routing devices such as routers and Ethernet switches.

 Routing lookup method:

 [5] Method 1. Using HASH (Hash) algorithm, IP routing table lookup is realized by RAM (Random Access Memory). Low-end Ethernet switches generally use HASH lookup mode.

 [6] The advantages of Method 1 are: Routing implementation costs are low, however, HASH

 The main problem of the algorithm is: When different IP addresses pass HASH

 After the algorithm is compressed into a shorter address, there will always be an address duplication. To avoid address duplication, routing devices generally use multi-level HASH.

 Structure to solve this problem, so that the routing device in the IP lookup process, the actual number of RAM check is uncertain, in the worst case, the number of RAM check will be many, which makes the IP routing lookup efficiency is poor, ultimately leading to

 The forwarding performance of the routing device is poor. At the same time, because the routing device needs to be IP

 The address is searched by the longest matching field, so that the IP in the HASH process

 After the address is matched, it is required to check whether the matching of the IP address is the longest match, which further reduces the efficiency of IP routing table lookup, thereby further reducing the forwarding performance of the routing device.

[7] Method 2: In order to improve the performance of IP routing lookup table, CAM has been developed.

 (based on content lookup device) such as TCAM (Triple Content Address Memory), TCAM can be based on content such as IP

The address directly finds the corresponding entry index. In the middle and high-end chips, TCAM is generally used to implement IP routing lookup. [8] TCAM is a high-speed content-based device. Three-value matching allows an IP routing entry to be configured with an IP address and a domain to be matched.

 The longest match table is checked, and the result can be obtained in one lookup. At present, high-speed devices can achieve 266M/S, which is the unimaginable speed of HASH search, TCAM IP.

 The routing table is efficient. However, TCAM

 The higher the price, the higher the cost of the routing device. Moreover, the current maximum single-chip capacity is 18 Mbit, and the single-chip capacity is difficult to do. Therefore, the capacity of the routing table is greatly limited.

[9] Summary of the invention

 [10] The embodiment of the present invention provides a routing method, a routing device, and a routing information storage method, so that the CAM can store more routing entry index information and improve the CAM.

 Utilization of routing devices in a highly efficient CAM

 The performance of the routing table reduces the cost of the routing device.

[11] A routing method provided by an embodiment of the present invention includes:

[12] receiving data messages;

 [13] obtaining the compressed routing entry index information according to the routing entry index information in the data packet; [14] the compressed routing entry index information and the routing entry stored in the content lookup table device Index information is matched;

 [15] routing the data packet according to the matched index information;

 [16] The one unit in the content-based look-up table device accommodates one or more routing entry index information compressed in the first compression manner.

 [17] The embodiment of the present invention further provides a routing device, where the routing device is provided with a CAM

 , compression module and routing module;

[18] Based on content lookup device,

 And storing the compressed routing entry index information, and storing one or more compressed routing entry index information in the content-based table device unit;

[19] The compression module is configured to obtain the compressed routing entry index information according to the routing entry index information in the data packet, and compress the compressed routing entry index information and the routing entry in the content lookup table device. The index information is matched to obtain matching index information; [20] The routing module is configured to perform routing and forwarding processing on the data packet according to the matching routing entry index information obtained by the compression module.

[21] The embodiment of the present invention further provides a routing information storage method, where the method includes:

[22] compressing the routing entry index information according to the length of one unit based on the content lookup table device, the number of routing table entry index information that a unit needs to store, and the length of the routing table entry index information;

[23] storing the compressed routing entry index information in a content-based table lookup device;

[24] The number of routing table entry index information that one unit needs to store is two or more.

[25] According to the description of the foregoing technical solution, by compressing the index information of each routing entry, one

CAM's unit width can accommodate multiple compressed routing entries index information, enabling CAM

 Ability to store more routing table entry index information, improve CAM

 The utilization of the routing table increases the capacity of the routing table, and overcomes the disadvantages of high cost of the routing device and large capacity limitation of the routing table when the CAM is used in the prior art; thus, the routing device can have the high efficiency of routing table lookup and large routing table capacity. , low cost of routing equipment and other characteristics.

 [26] BRIEF DESCRIPTION OF THE DRAWINGS

 [27] Figure 1 is a schematic diagram of a CAM in the prior art;

 2 is a schematic diagram of searching for a compressed IP address according to an embodiment of the present invention;

 3 is a schematic diagram of a CAM according to an embodiment of the present invention;

 4 is a flowchart of searching for routing entry index information according to an embodiment of the present invention.

 [31] Mode for carrying out the invention

 [32] In the prior art, when the routing device uses the HASH algorithm for RAM

 When the lookup table is used to implement route lookup, although it has the advantage of low cost, there is a problem of low route forwarding efficiency and poor route forwarding performance; when the routing device adopts TCAM

 In order to implement route lookup, although it has the advantage of high efficiency of route lookup, there is a problem that the routing table has low capacity and the cost of the routing device is high. If the two route lookup methods in the prior art are combined, one provides TCAM

 The high forwarding performance and the lower cost routing lookup method can overcome the shortcomings of high routing equipment cost and large routing table capacity limitation while overcoming the poor routing and forwarding performance.

[33] The embodiment of the present invention proposes a CAM based The fast routing method of indexing information compression of routing entries achieves high-speed, large-capacity, low-cost route lookup by utilizing the high-speed processing capability of CAM, such as TCAM devices, and the data organization method of combining routing table entry information.

 The technical solutions provided by the embodiments of the present invention are described in detail below.

 [35] In the technical solution of the embodiment of the present invention, a CAM such as a TCAM

 One unit can store more than one routing table entry index information, that is, a CAM

 The number of routing table entry index information stored in the unit should be greater than 1, such as a CAM

 The index information of an integer number of routing entries greater than 1 is stored in the unit. The number of index entries of the routing entries stored in a CAM unit may also be a non-integer greater than one.

 [36] When more than 1 is stored in a unit of CAM

 When an integer number of routing entry index information is used, the routing device should compress the index information of each routing entry so that a CAM unit width can accommodate multiple compressed routing entry index information. When a CAM unit needs to store index information of an integer number of compressed routing entries greater than 1, the routing table entry index information should be compressed according to the unit width of the CAM.

 . In this way, when the data packet needs to be routed, the routing device first compresses the routing entry index information in the data packet, and indexes the routing entry in the compressed data packet with the CAM.

 The routing table entry index information is matched. Then, the routing device forwards the data packet according to the matched index information.

 [37] In the actual application process, the index information of the routing entries before compression is generally: VPNID and IP.

 address. Thus, the routing device in the embodiment of the present invention needs to have a VPNID and an IP.

 The address is compressed. The specific compression process can be: IP

 The address information of the predetermined section of the address is compressed into address information of a predetermined bit width.

[38] Since the distribution of IP addresses is regular, that is, the number of network segments of Class A address and Class B address of a routing node on the network is small, and the change of IP address is mainly concentrated in the lower 16 bits. In this way, the address information of the predetermined interval of the IP address may be: a class A address or a class B address in the IP address, that is, the routing device may preferentially compress the class A address or the class B address in the IP address when performing compression processing. , such as IP address high 16bit IP The address is compressed. During the compression process, the specific compression algorithm can be set according to the specific conditions of the network. For example, the upper 16 bits of the IP address in the system only represents n.

 In different cases, the numbers 1 to n are set, and the different numbers correspond to different high 16 bits in the IP address. When compressing, compression can be performed according to the above compression algorithm.

[39] When a CAM unit needs to store more than 1

 When an integer number of compressed routing table entry index information, the above predetermined bit width should be determined according to the cell width in the CAM, such as when a CAM

 When two routing table entries need to be stored in the unit, the width of the index information of one routing entry is CAM.

 One-half of the width of the unit, so that when determining the predetermined bit width, the width of the routing table item before compression is required to be the width of the CAM.

 Compared with one-half of the cell width, it is determined that the width of the index information of the routing table item before compression is more than the width of the CAM unit width, and the width of the address information of the predetermined interval is set to K1.

 The bit position, the index of the routing table item before compression is more than one-half K2 bit wider than the width of the CAM unit. At this time, the pre-positioning width is: the difference between K1 and K2.

[40] In the CAM

 After the routing information of the routing table entries is compressed and stored, the routing device compresses the routing entries in the data packets by using the same compression method when receiving the data packets that need to be forwarded. The matching process of the index information of the compressed routing entry is performed.

[41] The embodiment of the present invention may also pre-set the correspondence between the uncompressed routing entry index information and the compressed routing entry index information, and the corresponding relationship may be stored in the routing device, such as the RAM stored in the routing device.

 Of course, it can also be stored independently of the routing device. The above correspondences can also be stored in other storage media other than RAM.

 [42] After the above correspondence is set, the routing device receives the need for route forwarding processing.

In the case of a data packet, first, the uncompressed routing entry index information is obtained from the data packet, and then the linear matching is performed to match the uncompressed routing entry index information in the data packet. Routing entry index information, after finding the matching compressed routing entry index information , will find the compressed routing table entry index information and CAM

 The routing table entry index information is matched. Finally, the routing device performs routing and forwarding processing on the data packet by using the matching routing entry index information in the CAM.

 [43] When a CAM unit stores more than 1

 In the process of matching the index information of the compressed routing entry and the routing information of the routing entry in the CAM, the routing device may match the lower-order entry in the CAM unit width to the index entry of the compressed routing entry in the CAM. The order of the high-order entries matches the found index information of the compressed routing entries with the routing table entry index information in the CAM, for example, when a CAM

 When two routing table entry index information is stored in the cell width, the routing device first performs a matching operation in the lower table entry of the CAM. If the matching succeeds, the matching process ends, and if the matching fails.

, then the matching operation is performed in the high order entry of the CAM.

 [44] When routing devices are capable of handling many different types of datagrams such as IPv4, IPv6

 When data packets are routed and forwarded, CAM

 The index information of different types of routing entries should be stored correspondingly. At this time, CAM

 The type identifier information should also be stored. The type identifier information is used to indicate the type of the index information of the routing entry. The type of the index information of the routing entry is the index information of the routing entry of the IPv4, and the index information of the routing entry of the IPv6.

 [45] In the embodiment of the present invention, type identification information, such as IPv4 and IPv6, may be set for each routing entry index information.

 The routing table entry index information is set with the type identification information. You can also set the type identification information for the partial routing entry index information. For example, only the IPv6 routing entry index information is used to set the type identification information.

IPv4 routing entry index information does not set type identification information.

[46] When type identification information is stored in the CAM, and a CAM unit stores more than 1

 When indexing information of an integer number of routing entries, when compressing the routing table entry index information, the width of the CAM unit and the bit width information occupied by the type identification information should be considered.

[47] in CAM

When the type identifier information is stored, the routing device needs to obtain the uncompressed routing entry index information from the data packet, and also needs to determine the route. The type of table entry index information, and then, the routing device queries the RAM

 The table and the like determine the index information of the compressed routing entry corresponding to the index information of the uncompressed routing entry, and the routing device uses the compressed route after determining the compressed routing entry index information corresponding to the data packet. Entry index information and type identification information in CAM

 The matching entry is found, and the data packet is forwarded and processed according to the matching routing entry index information.

 [48] The routing method provided by the embodiment of the present invention is described in detail below with a specific example.

[49] In routing devices, IPv4 routing entry index information is generally determined by VPNID and IP.

 Address composition, that is, the routing device is based on VPNID and IP

 Address to find routing index information. Set a unit width of the TCAM in units of 72 bits. Since the index information of the IPv4 routing entries is generally not exactly 72 bits,

A lot of storage space in TCAM is wasted.

[50] For example, the IPv4 IP address information is 32 bits, the VPNID is 10 bits, and the TCAM unit width is as shown in Figure 1.

[51] In Figure 1, the TCAM unit has a width of 72 bits, and the width of the IP address and VPNID is 42 bits. Thus, the high 30 bits of the TCAM unit are not fully utilized.

[52] In order to make full use of TCAM, the routing device can compress the VPNID+IP address information into 36bit, thus a 72bit TCAM

 Two compressed routing entry index information can be placed in the unit, thereby making the TCAM

 The routing table entry capacity has doubled.

[53] Considering IP when compressing VPNID+IP address information

 The law of address distribution is that the number of network segments of an 8-bit Class A address and a 16-bit Class B address of a routing node on the network is small, and the change of the IP address is mainly concentrated in the latter 16 bits.

 . In this way, the routing device can compress the upper 16-bit IP address and compress the upper 16-bit IP address to lObit. Thus, a routing entry index information can be 36 bits.

 Composition, including: lObit VPNID, compressed lObit high address index information, and low

16bit IP address. Therefore, a TCAM

Two routing table entry index information can be stored in the unit. [54] RAM can be used in routing devices to store uncompressed high 16bit IP

 Correspondence between the address information and the compressed IP address information of the high lObit, as shown in Figure 2, RAM

 The above correspondence is stored in the foregoing, so that the routing device can directly use the high 16-bit IP address as the index in the RAM when constructing the routing entry index information.

 Perform a linear lookup table to obtain a compressed lObit high-order address index information.

 [55] The routing device uses the lObit high-order address index information, the lower 16-bit IP address information, and the VPNID obtained by the above linear lookup table to construct a CAM routing entry, as shown in FIG. 2, because each routing table in the TCAM The item width is reduced to 36 bits. Therefore, each 72-bit unit in the TCAM can store two routing table entry index information.

 [56] Set up the above RAM and TCAM

 After the routing device needs to forward and forward the data packet, first, obtain the IP address information and the VPNID information from the data packet, and then, the high address of the IP address and the RAM.

 The entries in the match are matched, and the compressed lObit in the matching entry is obtained.

 High-order address index information, using the index information together with low 16-bit IP address information and VPNID to TCAM

 The matching process of the routing entry index information is performed, and the data packet is forwarded and processed by using the matching index information of the routing entry. The route forwarding process in the embodiment of the present invention is the same as the route forwarding process in the prior art, and will not be described in detail herein.

[57] The routing device uses the RAM and TCAM to route and forward data packets as shown in Figure 4.

[58] In FIG. 4, in step 400, the routing device receives the data packet and starts the routing process.

[59] In step 410, the routing device obtains IP address information from the data packet, and uses the IP

 The upper 16 bits of the address are matched with the entries in the RAM to obtain the compressed high-order address index information of the lObit in the matching entry.

[60] In step 420, the routing device composes the compressed lObit high-order address index information with the lower 16-bit IP address information and the VPN ID to form the search information.

[61] Go to step 430, the routing device uses the retrieved information to the lower 36 bits of the TCAM.

The matching process of the routing entry index information is performed, and the routing device determines the low 36 bit of the TCAM. Whether there is routing table entry index information matching the retrieval information, if any, to step 440.

[62] At step 430, the routing device determines the low 36 bit of the TCAM.

 When there is no routing entry index information matching the retrieval information, go to step 450.

 , the routing device uses the retrieved information to the TCAM high 36bit

 The matching process of the routing entry index information is performed, and the routing device determines whether there is a routing entry index information matching the retrieval information in the high 36 bits of the TCAM, and if yes, executing step 440.

[63] At step 440

 The routing device performs routing and forwarding processing on the data packet by using the matching routing entry index information, and ends the process.

 [64] At step 450, if the routing device determines the high 36bit of the TCAM

 If there is no routing entry index information matching the search information, it is determined that the route does not match. To step 451, the routing device uploads information such as the IP address of the packet to the CPU.

 The address analysis is performed by the software, and then the software configures the corresponding compression entry, CAM.

 Table entries and routing entries ensure that packets with the same address can be forwarded correctly.

The routing device provided by the embodiment of the present invention is provided with a CAM, a compression module, and a routing module.

[66] The CAM stores the compressed index entries of each routing entry, and a CAM

 More than one routing entry index information is stored in the unit. The CAM here is like TCAM. When a unit of CAM is stored greater than 1

 When the index information of an integer number of routing entries is used, the length of the index information of the compressed routing entry should be determined according to the unit width of the CAM. For example, the index information of the routing entry is: The upper 16 bits of the IP address is compressed into the address index information of lObit. , the lower 16bit of the IP address and the VPNID. When CAM

 When you need to store different types of routing table entry index information, CAM

 The storage type identification information is also required, as described in the above method embodiment.

[67] The compression module is used to: when the routing device needs to route data packets, compress the routing entry index information in the data packet, and compress the compressed routing entry index information with the CAM.

 The routing table entry index information is matched, and the matched index information is sent to the routing module.

[68] The compression module consists of a lookup submodule, a corresponding relational storage submodule, and a matching submodule.

[69] The corresponding relationship storage submodule is mainly used to: store uncompressed routing table entry index information and compressed path The correspondence between the index information of the entry. The corresponding relation storage submodule can be RAM. The correspondence stored in the RAM can be: the upper 16 bits of the IP address and the compressed lObit

 Correspondence between address index information. Specifically, it is as described in the above method embodiment.

[70] The search sub-module is mainly used to: obtain the uncompressed routing entry index information from the data packet when the routing device needs to forward the data packet, and then the routing entry in the data packet. The index information is matched and searched in the corresponding relationship storage sub-module to obtain the corresponding compressed routing entry index information, and the searched compressed routing entry index information is transmitted to the matching sub-module, such as the search sub-module. The RAM searches for the lObit search information matching the upper 16 bits of the IP address in the data packet, and searches for the lObit search information, the lower 16 bits of the IP address in the data packet, and the VPNID in the data packet.

 The information is transferred to the matching submodule. Specifically, it is as described in the above method embodiment.

[71] The matching submodule is mainly used to: according to the routing table entry index information and CAM received by it

 The routing table entry index information is matched and searched, and the matched index information is sent to the routing module. The search sub-module can be searched in the order from low to high in the matching search process. For example, when two 72-bit units in the CAM store two routing table index information, the matching search is performed from the lower 36-bit unit. At low 36bit

 When no matching routing entry index information is found in the unit, a matching search is performed from the high 36-bit unit of the CAM. And, when CAM

 When the type identification information is also stored, the search sub-module also needs to determine the type of the routing table item information in the data packet, and when the matching search is performed, the matching of the type identification information is added, as described in the above method. .

 [72] The routing module is mainly used to: receive the index information of the routing entry transmitted by the matching sub-module, and perform routing and forwarding processing on the data packet according to the index information of the routing entry. The route forwarding processing operation performed by the routing module may be the same as the routing forwarding processing operation in the prior art, and will not be described in detail herein.

 [73] According to the above description, due to the speed of linear look-up table than TCAM

The routing performance of the embodiment of the present invention is the same as that of the TCAM in the prior art. . Considering the distribution of IP addresses, IP There are few combinations of high-order addresses in the address, there is a lot of compression space, and the index information of the routing entries is

When the CAM bit width is not matched, the storage space of the CAM is fully utilized by adjusting the width of the index information of the routing entry. Moreover, adjusting the width of the index information of the routing entry does not cause the degradation of the routing forwarding performance.

 [74] Based on TCAM and RAM proposed by embodiments of the present invention

 Fast routing entry index information lookup algorithm, CAM's high-speed processing capability and IP

 The data organization method of the address is combined to realize a high-speed, large-capacity, low-cost route forwarding process. Embodiments of the present invention have been verified by hardware and are indeed feasible.

 [75] According to the description of the foregoing implementation manner, by compressing the index information of each routing entry, the unit width of one CAM can accommodate multiple compressed routing entry index information, so that CAM

 Ability to store more routing table entry index information, improve CAM

 Utilization, expanding the capacity of the routing table, overcoming the use of CAM in the prior art

 When the cost of the routing device is high and the capacity of the routing table is limited, the correspondence between the index information of the uncompressed routing entry and the index information of the compressed routing entry is set, such as in RAM.

 Store the correspondence, enabling the routing device to utilize the linear lookup of RAM and CAM

 The combination of technologies to implement routing and forwarding overcomes the disadvantages of low efficiency of routing table lookup and poor routing and forwarding performance when RAM is used alone in the prior art. By setting type identification information for index information of different types of routing entries, CAM can enable CAM to Routing and forwarding of multiple types of data packets, such as Ipv4 and Ipv6

 The data packet is forwarded by the data packet. The technical solution provided by the embodiment of the present invention enables the routing device to have the characteristics of high efficiency of routing table lookup, large routing table capacity, and low cost of the routing device.

 While the invention has been described by the embodiments of the invention, it is understood that

Claims

Claim  [1] 1. A routing method, comprising:  Receiving data packets;  And obtaining, according to the routing entry index information in the data packet, the compressed routing entry index information, and matching the compressed routing entry index information with the routing table entry information stored in the content lookup table device;  Routing the data packet according to the matched index information;  The unit based on the content lookup table device accommodates more than one routing entry index information compressed in the first compression manner.  [2] 2, as claimed in claim 1  The routing method is characterized in that: the index information of the compressed routing entry obtained according to the index information of the routing entry of the data packet is:  The routing entry information of the data packet is compressed in the first compression manner to obtain the compressed routing entry index information. [3] 3, as claimed in claim 1  The routing method of the routing table item stored in the content lookup table device includes: a VPN ID and a compressed IP address.  The first compression mode compression includes: compressing address information of a predetermined area in the IP address according to the content of the table lookup device unit. [4] 4, as claimed in claim 3  The routing method of the foregoing, wherein the address information of the predetermined area includes: type A address information and class B address information. [5] 5, as claimed in claim 1  The routing method is characterized in that: the index information of the compressed routing entry obtained according to the index information of the routing entry of the data packet is: Querying the correspondence table according to the routing entry index information of the data packet, and obtaining the corresponding index information of the compressed routing entry; The correspondence table stores the correspondence between the uncompressed routing entry index information and the compressed routing entry index information compressed in the first compression manner. [6] 6 , as claimed in claims 1 to 5  The routing method according to any one of the preceding claims, wherein the step of matching the compressed routing entry index information with the routing entry index information stored in the content lookup table device comprises:  Matching the compressed routing entry index information with the routing table entry index information based on the content lookup table device according to the order of the lower-order entry to the upper-order entry in the device unit width based on the content lookup table [7] 7 , as claimed in claims 1 to 5  The routing method according to any one of the preceding claims, wherein the compressed routing entry index information is obtained according to the routing entry index information of the data packet, and the compressed routing entry index information is The matching is performed based on the index information of the routing entry stored in the content lookup device:  Querying the correspondence table according to the routing entry index information of the data packet, and obtaining the corresponding index information of the compressed routing entry;  Matching the type of the routing entry index information of the data packet and the compressed routing entry index information with the routing entry index information in the content lookup table device; the correspondence relationship table stores the type identifier The correspondence between the information, the uncompressed routing entry index information, and the compressed routing entry index information compressed in the first compression manner. [8] 8 . A routing device, wherein: the routing device is configured with:  Based on content lookup device,  And storing the compressed routing table entry index information, and storing, by the content lookup table device unit, one or more compressed routing entry index information;  The compression module is configured to obtain the compressed routing entry index information according to the routing entry index information in the data packet, and perform the compressed routing entry index information and the routing entry index information in the content lookup device. Match, get matching index information; a routing module, configured to use the matching routing table entry index information obtained by the compression module Route forwarding processing is performed according to the message. [9] 9 as in claim 8  The routing device is characterized in that: the compression module includes:  a corresponding relationship storage submodule, configured to store a correspondence between the index information of the uncompressed routing entry and the index information of the compressed routing entry;  The locating sub-module is configured to search, according to the uncompressed routing entry index information in the data packet, the compressed routing entry index information from the corresponding relationship storage sub-module;  a matching sub-module, configured to receive the compressed routing entry index information obtained by the searching sub-module and the content-based table lookup device  The routing entry index information is matched, and the matched index information is sent to the routing module.  [10] 10, a routing information storage method, characterized in that the method comprises:  The routing entry index information is compressed according to the length of a unit based on the content lookup table device, the number of routing table entry index information that a unit needs to store, and the length of the routing entry index information;  And storing the compressed routing entry index information in the content-based table lookup device; the number of routing entry index information to be stored in the one unit is two or more. [11] 11 , as claimed in claim 10  The method of the present invention, wherein the step of compressing routing table entry index information includes: : The address information of the predetermined area in the IP address of the routing entry index information is compressed.