CN118282945B - IPv 6-based IP searching method and device - Google Patents

Abstract

The IPv 6-based IP searching method is applied to routing equipment, the routing equipment is provided with a lightweight cache, a plurality of IP addresses are stored in the lightweight cache, the plurality of IP addresses are all IPv 6-based addresses, the method comprises the steps of receiving network traffic, inquiring the lightweight cache based on the communication request to obtain a second IP address, wherein the communication request comprises a first IP address, the first IP address corresponds to the second IP address, the network traffic is used for representing a data packet transmitted by a network, the second IP address is obtained in the lightweight cache when the first IP address is successfully matched with any one of the plurality of IP addresses, the table item matched with the first IP address is obtained through a search tree when the first IP address is not successfully matched with any one of the plurality of IP addresses, and the search tree is constructed according to the network traffic. The method can improve the efficiency of IP searching.

Description

IPv 6-based IP searching method and device

Technical Field

The present invention relates to the field of communications technologies, and in particular, to an IP lookup method and apparatus based on IPv 6.

Background

In the internet, one of the main functions of routing devices (e.g., routers, switches, load balancers, etc.) is to determine the transmission path of a packet according to an internet protocol (internet protocol, IP) address. Thus, IP lookup (i.e., IP address lookup) is the core operation of the routing device. In the IP lookup process, it is mainly involved in checking the destination IP address of the incoming data packet to identify the longest prefix match in the forwarding information base (forward information base, FIB) of the routing device. The longest prefix match refers to an algorithm used by the routing device to select among routing tables in the IP protocol. In the routing table, a plurality of entries are included, each of which may include a destination network address, a subnet mask, a next hop address, a protocol type, and the like. Thus, an entry may also be referred to as a rule. Since each entry in the routing table specifies a network, a destination address may be matched to multiple entries. The most definite entry, the longest one of the subnet masks, is matched as the longest prefix. Assuming that two rules (entries) contained in a FIB table are "192.168.20.16/28" and "192.168.0.0/16", respectively, then when the IP address to be searched for is "192.168.20.19", both rules match (may also be referred to as corresponding). At this point, both entries contain the IP address to be looked up. In this case, the longest prefix route is "192.168.20.16/28" because its subnet mask (/ 28) is longer than the subnet mask (/ 16) of the other entry, making it more explicit, the router uses this rule to forward the packet of destination "192.168.20.19".

Although the concept of longest prefix matching is the same in internet communication protocol version four (internet protocol version, IPv 4) and internet communication protocol version six (internet protocol version, IPv 6), IPv6 routing tables may be larger because IPv6 addresses are four times longer than IPv4, requiring more efficient data structures and algorithms to achieve fast lookup. Therefore, how to perform IP lookup in an IPv6 device is a technical problem that needs to be solved.

Disclosure of Invention

In order to solve the problems in the prior art, embodiments of the present application provide a method, an apparatus, a computing device, a computer storage medium, and a product containing a computer program for searching for IP based on IPv6, which can improve efficiency of IP searching.

The embodiment of the application provides an IPv 6-based IP searching method, which is characterized in that the method is applied to routing equipment, the routing equipment is provided with a lightweight cache, a plurality of IP addresses are stored in the lightweight cache, the plurality of IP addresses are all IPv 6-based addresses, the method comprises the steps of receiving network traffic, inquiring the lightweight cache based on the communication request to obtain a second IP address, wherein the network traffic comprises a communication request, the communication request comprises a first IP address, the first IP address corresponds to the second IP address, the network traffic is used for representing a data packet transmitted by a network, the second IP address is obtained in the lightweight cache when the first IP address is successfully matched with any one of the plurality of IP addresses, a table item matched with the first IP address is obtained through a search tree when the first IP address is not successfully matched with any one of the plurality of IP addresses, and the search tree is constructed according to the network traffic.

In some possible implementations, the method further includes obtaining a temporal locality of the network traffic, the temporal locality including a high temporal locality, wherein the high temporal locality is expressed as a proportion of a number of most frequently accessed IP address hits to a total number of hash table entries within a period of time, and a low temporal locality is expressed as a proportion of a number of most frequently accessed IP address hits to a total number of hash table entries within a period of time, and querying a lightweight cache in the case of the high temporal locality and a search tree in the case of the low temporal locality.

In some possible implementations, the ratio is between 10% and 20%.

In some possible implementations, the search tree is a binary tree, the table items matched with the first IP address are obtained through the search tree, specifically, popularity of each node in the binary tree is determined according to the network traffic, the popularity represents possibility that the node is successfully matched, each node in the binary tree comprises at least one table item, the binary tree is built based on the popularity, and the table items matched with the first IP address are obtained through the binary tree.

In some possible implementations, popularity is calculated according to the following formula

Where α represents the weight of the rule number, β represents the weight of the hit count, R (N) represents the rule number associated with the storage node N, and F (N) represents the percentage of the historical network traffic that ultimately finds a matching packet at node N.

In some possible implementation manners, the search tree is a dictionary tree, and the step length is determined by a heuristic algorithm, wherein the step length represents the number of bits of nodes in the dictionary tree which are searched simultaneously, the dictionary tree is constructed based on the step length, and the table item matched with the first IP address is obtained by the dictionary tree.

In some possible implementations, the calculation formula for determining the step size by means of annealing simulation is as follows:

Where E [ T (S (N)) ] represents the expected average memory access times of the node at a given step size, N represents the storage node, nodes represents the total storage node, F (N) represents the access frequency of the node N, T _lookup (S (N), R (N)) represents the memory access times of performing a lookup operation on the node N, the function M _node (S (N), R (N)) represents the memory overhead of the node N, S (N) represents the step size, R (N) represents the number of rules associated with the storage node N, mmax represents the maximum memory capacity allowed, s.t. represents the constraint, and M (S (N)) represents the total memory overhead.

In some possible implementations, the plurality of IP addresses stored in the lightweight cache are updated.

In some possible implementations, the search tree is updated as network traffic changes.

The embodiment of the application provides an IPv 6-based IP searching device which is characterized in that the device is deployed in routing equipment, a lightweight cache is arranged in the routing equipment, a plurality of IP addresses are stored in the lightweight cache, the plurality of IP addresses are all addresses based on IPv6, the device comprises a receiving module, a searching module and a searching module, wherein the receiving module is used for receiving network traffic, the network traffic comprises a communication request, the lightweight cache is queried based on the communication request to obtain a second IP address, the communication request comprises a first IP address, the first IP address corresponds to the second IP address, the network traffic is used for representing a data packet transmitted by a network, the searching module is used for obtaining the second IP address in the lightweight cache when the second IP address is successfully matched with any one of the plurality of IP addresses, the searching module is also used for obtaining an item matched with the first IP address through a searching tree when the second IP address is not successfully matched with any one of the plurality of IP addresses, and the searching tree is constructed according to the network traffic.

In a third aspect, embodiments of the present application provide a computer-readable storage medium comprising computer-readable instructions which, when read and executed by a computer, cause the computer to perform the method of any of the first aspects.

In a fourth aspect, an embodiment of the present application provides a computing device comprising a processor and a memory, wherein the memory has stored therein computer program instructions which, when executed by the processor, perform the method according to any of the first aspects.

In a fifth aspect, embodiments of the present application provide a product comprising a computer program which, when run on a processor, causes the processor to perform the method according to any of the first aspects.

The method constructs a special search tree to adapt to the continuously-changing flow mode, and the flow characteristics are utilized to guide the construction of the search tree, so that the searching efficiency of network routing equipment is obviously improved, and the performance of a routing system is further improved.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings required for the description of the embodiments will be briefly described below, it being obvious that the drawings in the following description are only some embodiments of the present invention, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

Fig. 1 is a schematic diagram of a method for searching for IP by IPv6 according to an embodiment of the present application;

Fig. 2 is a schematic flow chart of an IP lookup method based on IPv6 according to an embodiment of the present application;

fig. 3 is a schematic flow chart of an IP lookup provided in an embodiment of the present application;

fig. 4 is a schematic structural diagram of an IP lookup device based on IPv6 according to an embodiment of the present application;

Fig. 5 is a schematic structural diagram of a computing device according to an embodiment of the present application.

Detailed Description

For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions of the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments of the present invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

The term "and/or" is used herein to describe an association relationship of associated objects, and means that there may be three relationships, for example, a and/or B, and that there may be three cases where a exists alone, while a and B exist together, and B exists alone. The symbol "/" herein indicates that the associated object is or is a relationship, e.g., A/B indicates A or B.

The terms "first" and "second" and the like in the description and in the claims are used for distinguishing between different objects and not for describing a particular sequential order of objects. For example, the first response message and the second response message, etc. are used to distinguish between different response messages, and are not used to describe a particular order of response messages.

In embodiments of the application, words such as "exemplary" or "such as" are used to mean serving as an example, instance, or illustration. Any embodiment or design described herein as "exemplary" or "e.g." in an embodiment should not be taken as preferred or advantageous over other embodiments or designs. Rather, the use of words such as "exemplary" or "such as" is intended to present related concepts in a concrete fashion.

In the description of the embodiments of the present application, unless otherwise specified, the meaning of "plurality" means two or more, for example, a plurality of processing units means two or more processing units and the like, and a plurality of elements means two or more elements and the like.

For the purpose of facilitating an understanding of the embodiments of the present application, reference will now be made to the following description of specific embodiments, taken in conjunction with the accompanying drawings, which are not intended to limit the embodiments of the application.

First, technical terms related to the embodiments of the present application will be described:

1. Long tail distribution, a type of probability distribution, refers to a small number of categories that occupy a large portion of the number of samples, while most categories occupy only a small number of samples.

Next, the technical scheme provided by the embodiment of the application is described.

In routing devices, IP lookup may help the network device determine how to transfer a data packet from one network to another until the final destination is reached. Specifically, when the routing device receives a data packet, the destination IP address of the data packet is first checked. The routing device searches the routing table for the routing rule matched with the destination IP address, and selects the routing rule most specifically matched with the destination IP address. In the routing rules, the IP address of the next hop is typically included. After determining the next hop address, the routing device forwards the packet to this address. If the routing rule points to the final destination, the packet will be sent directly to the destination host, and if another router is pointed to, this router will again perform routing rule query and forwarding until the packet reaches its final destination. The process of IP lookup essentially looks up the routing rules that match the IP address. IP lookup mainly involves two key components, "traffic" and "rule set". Traffic refers to the actual packets transmitted through the network, and the rule set is the Forwarding Information Base (FIB) defining the rules for processing and forwarding packets according to their destination IP addresses. In searching for IP based on IPv6, rule searching may be performed by way of a dictionary tree-based manner and a binary search tree-based manner. After the rule is found, the data packet can be processed according to the found rule. Exemplary, fig. 1 shows a schematic diagram of a method for searching rules in IPv6 according to an embodiment of the present application. As shown in (a) of fig. 1, the dictionary tree-based IP lookup method uses a tree data structure of the dictionary tree to split and store the IPv6 address layer by bit. Each node represents a portion of an IP address from which the target entry can be efficiently located by traversing down constantly. As shown in fig. 1 (B), the binary search tree (i.e., binary tree) based IP lookup method may store IP prefixes of length into different hash tables and organize the hash tables into an asymmetric binary search tree.

The dictionary tree-based IP lookup method can precisely match each bit. The prefix length of the IP address determines its depth in the tree based on the IP lookup method of the binary search tree such that IP addresses having the same prefix length are located at the same depth of the tree.

But the focus of both modes is on how to find the design and optimization of the structure to construct an efficient find structure, and at the same time, the system cache mode is utilized to improve the find performance. Both of these are ideal cases where network traffic transmitted by the network is equal, and the characteristics of the network traffic are not considered. Network traffic refers to the actual data packets transmitted through the network and is typically used to describe how densely the data is transmitted or the usage of the network. Both of these implicitly assume that the network traffic is evenly distributed, implying that the probabilities of all rules being hit are equal. This is not the case in reality.

In view of this, the embodiment of the application provides an IP searching method based on IPv 6. The embodiment of the application utilizes the real flow data obtained from MAWI working groups of wide area Internet development projects to statistically analyze the access frequency of each IP address. After ranking the IP addresses according to frequency, a cumulative distribution function and a fitting diagram are generated, and the distribution of network traffic is found to show the characteristic of long-tail distribution, namely a few IP addresses generate most network traffic. Therefore, the application designs the search tree based on the network flow, queries the IP address in the mode of the search tree, and can fully utilize the characteristic of flow distribution. Note that IP hereinafter also means an IP address, unless otherwise specified, and the IP addresses are all IP addresses based on IPv 6.

Fig. 2 is a schematic flow chart of an IP lookup method based on IPv6 according to an embodiment of the present application, where the method may be applied to a routing device, and a lightweight cache is provided in the routing device, where a plurality of IP addresses are stored in the lightweight cache. As shown in fig. 1, the IP lookup method may include the steps of:

and S21, receiving network traffic, wherein the network traffic comprises a communication request, and inquiring the lightweight cache based on the communication request to acquire a second IP address. The communication request includes a first IP address, and the first IP address corresponds to the second IP address.

In this embodiment, the IP address entry of the data item with the larger partial traffic contribution is stored in the lightweight cache, and implemented based on the hash table. Lightweight caching (L IGHTWE IGHT CACHE) is a caching mechanism in a computing device that aims to reduce latency in accessing data by a system, improve system performance, and speed up data retrieval by storing frequently accessed data in memory. Stored in the lightweight cache are primarily IP addresses that occur more frequently in network traffic. These IP addresses are obtained by traffic sampling and statistics and may represent the flow direction of most of the network traffic in the network. The lightweight cache is implemented based on a hash table, where each IP address entry has a corresponding location. When a packet arrives, the system maps the IP address to a location in the hash table via a hash function. And the routing equipment obtains the actual data packet after receiving the network traffic. The communication request of the data packet includes a first IP address to which the data packet needs to be communicated, and the routing device needs to route the data packet to the first IP address according to the first IP address. In this process, the routing device needs to know how to forward the packet to the next hop, or directly to the final destination (if the computing device of the first IP address is in the same network as the routing device), and therefore the routing device needs to find the IP address that best matches the first IP address, i.e. the second IP address.

S22, under the condition of cache hit, the second IP address is acquired in the lightweight cache.

In this embodiment, the cache hit refers to that the first IP address matches any one of the plurality of IP addresses stored in the lightweight cache successfully, which may be referred to as a cache hit. In case of a hit, the second IP address can be directly obtained in the lightweight cache.

S23, under the condition of no cache hit, obtaining the table item matched with the first IP address through a search tree, and constructing the search tree according to the network traffic.

In this embodiment, the second IP address corresponding to the network traffic is not stored in the cache, so that matching between the first IP address and the plurality of IP addresses stored in the lightweight cache is not successful. At this time, the routing device needs to find an entry in the search tree that matches the first IP address. At this time, by constructing the search tree with reference to the network traffic, the search tree can be more in line with the characteristics of the network traffic, and the search is faster and more efficient when searching for the IP address. The search tree may be constructed as a dictionary tree or as a binary tree. In building the search tree, a rule set may be referenced simultaneously in addition to the characteristics of the network strength.

In some possible embodiments, the search tree is a dictionary tree, and the routing device looks up the IP address based on the dictionary tree.

In this embodiment, no IP address is allocated in the lightweight cache, and at this time, the routing device needs to find the IP address based on the dictionary tree, that is, find an entry matching the first IP address. In the dictionary tree-based IP address lookup method, each dictionary tree node represents a decision point, which may cover multiple bits of information. During an IP address prefix lookup, traversal begins with the root node, each node examines several bits of the address to determine the next child node or retrieve associated next hop information. In the application, the step length represents the number of bits of the simultaneous checking node, which is marked as S (N), and the balance between the searching efficiency and the memory utilization is obtained. In general, nodes with larger steps check more bits at the same time, facilitating faster lookups, but because there are more children, the larger steps are at the cost of increased memory consumption. In some approaches, research has focused mainly on data structures, prefix extension techniques, and compressors that efficiently store child pointers and next-hop information, but ignores the traffic characteristics in the dictionary tree construction process. Therefore, in this embodiment, a flow-based adaptive method is used for the step size. In the embodiment of the application, for the node with higher flow density, the searching efficiency can be improved by increasing the step length, and for the node with lower flow density, the memory can be saved by reducing the step length. In step size design, step size is calculated based on the expected average memory access times at a given step size, the memory usage of information in the storage node N, and the maximum memory capacity, and step size values are determined by a method employing heuristic algorithms (e.g., simulated annealing, bayesian optimization, etc.). Based on the obtained step size, a dictionary tree is constructed. The routing equipment searches the IP address required by the network traffic based on the constructed dictionary tree, thereby realizing the high-speed searching of the IP address.

Specifically, the step size can be calculated according to the following formula:

Where E [ T (S (N)) ] represents the expected average memory access times of the node at a given step size, N represents the storage node, nodes represents the total storage node, F (N) represents the access frequency of the node N, T _lookup (S (N), R (N)) represents the memory access times of performing a lookup operation on the node N, the function M _node (S (N), R (N)) represents the memory overhead of the node N, S (N) represents the step size, R (N) represents the number of rules associated with the storage node N, mmax represents the maximum memory capacity allowed, s.t. is constrained, represents a constraint condition, and M (S (N)) represents the total memory overhead.

In some possible embodiments, the search tree is a binary tree, and the routing device looks up the IP address based on the binary tree.

In this embodiment, no IP address is allocated in the lightweight cache, at which point the routing device may look up the IP address based on a binary tree. In Binary Search Tree (BST) based IP address lookup schemes, the IP addresses are typically divided into different subsets according to their prefix lengths, and each subset is maintained using a hash table. These hash tables are then stored in different nodes of a Binary Search Tree (BST) to perform a binary search for prefix lengths during the search process. In each node, a plurality of rules may be included. In some approaches, BST-based algorithms typically place more regular hash tables closer to the root because they have a higher probability of rule matching, so that the search process can be terminated early, and thus the average search time can be reduced. But the rule matching probability is affected not only by the number of rules but also by the flow distribution. Thus, in the present embodiment, the likelihood that each node is matched is evaluated by evaluating the popularity of that node. Popularity is used to characterize the likelihood that nodes are matched, denoted P (N). Popularity may include the number of rules and the number of times a node is accessed. The higher the popularity, the greater the chance that the node rule matches, i.e., the node is placed near the root of the binary tree. Based on popularity, a binary tree is thus constructed. The routing equipment searches the IP address required by the network traffic based on the constructed binary tree, thereby realizing the high-speed searching of the IP address.

Specifically, popularity may be calculated according to the following formula:

Where α represents the weight of the rule number, β represents the weight of the hit count, R (N) represents the rule number associated with the storage node N, and F (N) represents the percentage of the historical network traffic that ultimately finds a matching packet at node N. The weight alpha and the weight beta can be set according to the needs.

In some possible embodiments, the IP lookup method may further comprise querying the lightweight cache if the locality of network traffic is high, and querying the search tree if the locality of network traffic is low.

In this embodiment, a flow selector is further provided in the routing device, and the flow selector may determine the locality of the network traffic. The locality of network traffic may include temporal locality and spatial locality. A high temporal locality means that traffic is considered to have a high temporal locality if certain IP addresses are found to be frequently accessed over a period of time. The high spatial locality means that if a set of IP addresses are found to be accessed together frequently, the search tree structure can be optimized, organizing the IP addresses together for faster lookup. Specifically, taking time locality as an example, for time locality incoming, in a scenario where network traffic locality is low, an accurate matching cache may result in additional access queries for each packet. Therefore, the routing equipment can perform regular query on the accurate matching cache, and when the hit count of the first M most frequently accessed IP addresses in a period of time is a certain proportion of the total number of hash table entries, the network traffic is considered to have higher time locality, and the query is performed in the lightweight cache when the IP addresses are queried. If the above criteria are not met, indicating that the network traffic is low in locality, redirecting the packet query directly to the search tree for query. Fig. 3 is a schematic flow chart of IP lookup according to an embodiment of the present application. Referring to fig. 3, after receiving the network traffic, the flow selector may determine the locality of the traffic according to the network traffic. Under the condition of high flow locality, IP searching is carried out in the lightweight cache, and when matching is not successful in the lightweight cache, matching is carried out in the search tree. In the case of low traffic locality, matching is performed directly through the search tree.

In some possible embodiments, the ratio may be between 10% and 20% (inclusive).

In some possible embodiments, the method further comprises updating the search tree when the network traffic distribution changes.

In this embodiment, a search tree updating module is further provided in the routing device, and the search tree is updated by the search tree updating module. In view of the possible change in the distribution of network traffic, the traffic characteristics are changed (i.e., the long tail distribution of traffic is changed). At this time, the existing search tree is used for searching, which may have a certain influence on the searching efficiency. Therefore, the search tree needs to be updated. Specifically, two time windows t1 and t2 are determined, respectively. The first J IP entries in t1 and t2 are obtained. J may be 0.1% of the total IP entry number. If more than half of the prefixes in the IP entries at t1 and t2 are inconsistent, this indicates that the search tree needs to be updated. The original search tree is referred to as search tree a. When updating, a new search tree B can be established according to the current network flow. After search tree B is established, pointers to search tree a are redirected to search tree B and the memory space of search tree a is freed. Thus, the continuity of the searching process can be ensured, and the searching efficiency is not influenced.

In some possible embodiments, J may be 0.1% of the total IP entry number.

In some possible embodiments, the method further comprises updating the plurality of IP addresses stored in the lightweight cache.

In this embodiment, the lightweight cache is used to accelerate the lookup efficiency of the high-locality traffic, store the data item with a larger contribution of part of the traffic, and implement based on the hash table. In the lightweight cache, a counter associated with the IP address entry is also included for recording how often the IP address was accessed over a period of time. The value of the counter is updated in response to the change in the traffic pattern. In order to solve the problem of cache table jitter caused by long wake traffic distribution and network traffic burstiness, the lightweight cache only stores specific data items contributing to most of traffic, and timely deletes entries which are no longer popular. Specifically, by sampling the network traffic, for each sampled packet, a hash operation is performed on its first IP address to find the corresponding location in the hash table. If the location is empty, a new IP address entry (second IP address) is created and the counter is set to 1. If the location is not null and the first IP address matches the second IP address, the counter is incremented. If the location is not null and the first IP address does not match the second IP address, the counter is multiplied by the decay factor alpha. The decay factor alpha is used to adjust the value of the counter. When the IP address is no longer flowing, its counter value is reduced according to the decay factor to reflect the decrease in popularity. When the counter is below 1, the IP address stored in the lightweight cache will be evicted and replaced. This eviction policy ensures that the current important visitors remain in the cache because their counters will often increment, while old important visitors are removed in time due to the exponential decay of the counters. The design purpose of the lightweight cache is to quickly respond to those lookup requests that contribute most to the flow of IP addresses, thereby improving the efficiency of the overall lookup system. By dynamically updating the entries in the cache, the system can adapt to the real-time change of network traffic and maintain the timeliness and accuracy of the cache content.

In some possible embodiments, the attenuation factor α is 0.99.

The above is the IP searching method based on IPv6 provided by the embodiment of the present application, which can use the characteristics of network traffic to guide the construction of a data structure (search tree) during IP address searching. Therefore, the characteristics of network traffic are considered in the construction of the search tree, the locality of traffic distribution can be fully utilized, and the traffic with high flow measurement is ensured to hit at the position close to the leaf node, so that the efficiency of IP searching is improved.

It should be understood that, the sequence numbers of the steps in the foregoing embodiments do not mean the order of execution, and the execution order of the processes should be determined by the functions and the internal logic, and should not limit the implementation process of the embodiments of the present application. In addition, in some possible implementations, each step in the foregoing embodiments may be selectively performed according to practical situations, and may be partially performed or may be performed entirely, which is not limited herein. All or part of any features of any embodiment of the application may be freely combined without contradiction. The combined technical scheme is also within the scope of the application.

Based on the method in the above embodiment, the embodiment of the present application further provides an IP lookup device based on IPv 6.

Fig. 4 is a schematic structural diagram of an IP lookup device based on IPv6 according to an embodiment of the present application, where the IP lookup device is deployed in a routing device, and a lightweight cache is provided in the routing device, where a plurality of IP addresses are stored in the lightweight cache, and the plurality of IP addresses are all addresses based on IPv 6. As shown in fig. 4, the IPv6 based IP lookup apparatus 400 may include a receiving module 401 and a lookup module 402.

The receiving module 401 is configured to receive a network traffic, where the network traffic includes a communication request, and query the lightweight cache based on the communication request to obtain a second IP address, where the communication request includes a first IP address, and the first IP address corresponds to the second IP address;

A lookup module 402, configured to obtain the second IP address from the lightweight cache if the second IP address matches any one of the plurality of IP addresses successfully;

The searching module 402 is further configured to obtain the second IP address through a search tree when the second IP address is not successfully matched with any one of the plurality of IP addresses, where the search tree is constructed according to the network traffic.

It should be understood that, the foregoing apparatus is used to perform the method in the foregoing embodiment, and corresponding program modules in the apparatus implement principles and technical effects similar to those described in the foregoing method, and reference may be made to corresponding processes in the foregoing method for the working process of the apparatus, which are not repeated herein.

The present application also provides a computing device 500. As shown in FIG. 5, computing device 500 includes a bus 502, a processor 504, a memory 506, and a communication interface 508. Communication between processor 504, memory 506, and communication interface 508 is via bus 502. Computing device 500 may be a server or a terminal device. It should be understood that the present application is not limited to the number of processors, memories in computing device 500.

Bus 502 may be a peripheral component interconnect standard (PERIPHERAL COMPONENT INTERCONNECT, PCI) bus, or an extended industry standard architecture (extended industry standard architecture, EISA) bus, among others. The buses may be divided into address buses, data buses, control buses, etc. For ease of illustration, only one line is shown in fig. 5, but not only one bus or one type of bus. Bus 504 may include a path to transfer information between various components of computing device 500 (e.g., memory 506, processor 504, communication interface 508).

The processor 504 may include any one or more of a central processing unit (central processing unit, CPU), a graphics processor (graphics processing unit, GPU), a Microprocessor (MP), or a digital signal processor (DIGITAL SIGNAL processor, DSP).

The memory 506 may include volatile memory (RAM), such as random access memory (random access memory). The processor 504 may also include non-volatile memory (non-volatile memory), such as read-only memory (ROM), flash memory, mechanical hard disk (HARD DISK DRIVE, HDD) or solid state disk (SSD STATE DRIVE).

The memory 506 has stored therein executable program code that is executed by the processor 504 to implement the functions of the aforementioned receiving module 401 and the finding module 402, respectively, to implement all or part of the steps of the method in the aforementioned embodiments. That is, the memory 506 has instructions stored thereon for performing all or part of the steps of the methods of the embodiments described above.

Or the memory 506 has stored therein executable code that is executed by the processor 504 to implement the functions of the aforementioned IPv6 based IP lookup apparatus 400, respectively, to implement all or part of the steps in the method of the aforementioned embodiments. That is, the memory 506 has instructions stored thereon for performing all or part of the steps of the methods of the embodiments described above.

Communication interface 508 enables communication between computing device 500 and other devices or communication networks using a transceiver module such as, but not limited to, a network interface card, transceiver, or the like.

Based on the methods in the above embodiments, the embodiments of the present application provide a computer-readable storage medium storing a computer program that, when executed on a processor, causes the processor to perform the methods in the above embodiments.

Based on the methods in the above embodiments, embodiments of the present application provide a computer program product that, when run on a processor, causes the processor to perform the methods in the above embodiments.

It is to be appreciated that the processor in embodiments of the application may be a central processing unit (central processing unit, CPU), but may also be other general purpose processors, digital signal processors (DIGITAL SIGNAL processors, DSPs), application Specific Integrated Circuits (ASICs), field programmable gate arrays (field programmable GATE ARRAY, FPGAs), or other programmable logic devices, transistor logic devices, hardware components, or any combination thereof. The general purpose processor may be a microprocessor, but in the alternative, it may be any conventional processor.

The method steps in the embodiments of the present application may be implemented by hardware, or may be implemented by executing software instructions by a processor. The software instructions may be comprised of corresponding software modules that may be stored in random access memory (random access memory, RAM), flash memory, read-only memory (ROM), programmable ROM (PROM), erasable programmable ROM (erasable PROM, EPROM), electrically Erasable Programmable ROM (EEPROM), registers, hard disk, removable disk, CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC.

In the above embodiments, it may be implemented in whole or in part by software, hardware, firmware, or any combination thereof. When implemented in software, may be implemented in whole or in part in the form of a computer program product. The computer program product includes one or more computer instructions. When loaded and executed on a computer, produces a flow or function in accordance with embodiments of the present application, in whole or in part. The computer may be a general purpose computer, a special purpose computer, a computer network, or other programmable apparatus. The computer instructions may be stored in or transmitted across a computer-readable storage medium. The computer instructions may be transmitted from one website, computer, server, or data center to another website, computer, server, or data center by a wired (e.g., coaxial cable, fiber optic, digital Subscriber Line (DSL)), or wireless (e.g., infrared, wireless, microwave, etc.). The computer readable storage medium may be any available medium that can be accessed by a computer or a data storage device such as a server, data center, etc. that contains an integration of one or more available media. The usable medium may be a magnetic medium (e.g., floppy disk, hard disk, tape), an optical medium (e.g., DVD), or a semiconductor medium (e.g., solid State Drive (SSD)), etc.

It will be appreciated that the various numerical numbers referred to in the embodiments of the present application are merely for ease of description and are not intended to limit the scope of the embodiments of the present application.

Claims (8)

1. An IPv6-based IP lookup method, characterized by being applied to a routing device, wherein the routing device is provided with a lightweight cache, wherein the lightweight cache stores multiple IP addresses, wherein the multiple IP addresses are all IPv6-based addresses, wherein the IP addresses stored in the lightweight cache are IP addresses that are dynamically updated based on a hit count and a decay factor, the method comprising: receiving network traffic, the network traffic including a communication request, and querying the lightweight cache based on the communication request to obtain a second IP address; wherein the communication request includes a first IP address, the first IP address corresponding to the second IP address; and the network traffic is used to represent data packets transmitted over the network; When the first IP address successfully matches any one of the multiple IP addresses, obtaining the second IP address from the lightweight cache; When the first IP address fails to match any of the multiple IP addresses, obtaining a table entry matching the first IP address through a search tree; the search tree is constructed according to the network traffic, and the search tree is a binary tree or a dictionary tree; When the search tree is a binary tree, obtaining the table entry that matches the first IP address through the search tree specifically comprises: determining, based on the network traffic, the popularity of each node in the binary tree, wherein the popularity represents the probability of a node being successfully matched; each of the nodes includes at least one table entry; constructing a binary tree based on the popularity; and obtaining the table entry that matches the first IP address through the binary tree; When the search tree is a dictionary tree, obtaining the second IP address through the search tree is specifically: determining the step length through a heuristic algorithm, including: calculating the step length based on the expected average number of memory accesses at a given step length, the memory usage of the information stored in the node N, and the maximum memory capacity, the step length representing the number of bits of the nodes in the dictionary tree that are searched simultaneously; constructing a dictionary tree based on the step length; and obtaining a table entry that matches the first IP address through the dictionary tree. 2. The method according to claim 1, further comprising: Obtaining temporal locality of network traffic, where temporal locality includes high temporal locality and low temporal locality; wherein high temporal locality is indicated by the number of hits to the most frequently accessed IP address within a time period reaching a certain ratio to the total number of hash table entries; and low temporal locality is indicated by the number of hits to the most frequently accessed IP address within a time period not reaching a certain ratio to the total number of hash table entries; In case of high temporal locality, the lightweight cache is queried, and in case of low temporal locality, the search tree is queried. 3. The method according to claim 2, wherein the ratio is between 10% and 20%. 4. The method according to claim 1, wherein the popularity is calculated according to the following formula Where α represents the weight of the number of rules, β represents the weight of the hit count, R(N) represents the number of rules associated with storage node N, and F(N) represents the percentage of packets in historical network traffic that ultimately find a match at node N. 5. The method according to claim 1, wherein the calculation formula for determining the step length by annealing simulation is as follows: where e[T(S(N))] represents the expected average number of memory accesses to a node at a given step size, N represents the storage node, Nodes represents the total storage nodes, F(N) represents the access frequency of node N, T _lookup (S(N), R(N)) represents the number of memory accesses to perform a lookup operation on node N, the function M _node (S(N), R(N)) represents the memory overhead of node N, S(N) represents the step size, R(N) represents the number of rules associated with storage node N, Mmax represents the maximum allowed memory capacity, st represents the constraint, and M(S(N)) represents the total memory overhead. 6 . The method according to claim 1 , further comprising updating the multiple IP addresses stored in the lightweight cache. 7. The method according to claim 1, characterized in that the search tree is updated when the network traffic changes. 8. An IPv6-based IP lookup device, characterized in that it is deployed in a routing device, the routing device is provided with a lightweight cache, the lightweight cache stores multiple IP addresses, and the multiple IP addresses are all IPv6-based addresses, the device comprising: a receiving module, configured to receive network traffic, the network traffic including a communication request, and query the lightweight cache based on the communication request to obtain a second IP address; wherein the communication request includes a first IP address, the first IP address corresponding to the second IP address; and the network traffic is used to represent data packets transmitted over the network; a search module, configured to obtain the second IP address from the lightweight cache if the second IP address successfully matches any one of the multiple IP addresses; The search module is further configured to obtain a table entry matching the first IP address through a search tree when the second IP address fails to match any of the multiple IP addresses; the search tree is constructed based on the network traffic.