CN1173531C - At the same time, it supports routing search, IP packet classification, ARP search method and search system - Google Patents

Abstract

The present invention relates to a method which simultaneously supports routing search, IP packet classification and ARP search and a search system, which belongs to the field of internet route techniques. The method is characterized in that the routing search, the IP packet classification and the ARP search functions and optional combination functions thereof can be completed via the operation: a timing signal periodically controls an executive routing list, extraneous refreshing instructions of a classification rule base and ARP ageing refreshing instructions in the system. In addition, the routing research and the IP packet classification instructions are executed according to the packet head information of data packets, an ARP search instruction is executed according to an IP address for the ARP search, and an ARP list refreshing instruction is executed according to an extraneous ethernet address and an IP address used for refreshing an ARP list. The present invention reduces the complexity of router systems, and the configuration of systematic functions is more flexible simultaneously.

Description

At the same time, it supports routing search, IP packet classification, ARP search method and search system

technical field

The method and system for simultaneously supporting routing search, IP packet classification, and ARP search belong to the technical field of computer networks, and in particular relate to IPv4 and IPv6 search systems in the technical field of routing.

technical background

Routing lookup is the basic function of routers, and IP packet classification provides conditions for routers to support IP QoS (Quality of Service), which is an extended function of routers. In Ethernet, it is also necessary to perform an ARP lookup for each IP packet. Therefore, as people's requirements for Internet service quality are getting higher and higher, routers are required to perform a route lookup, IP packet classification, and an IP packet at the same time. ARP lookup. These three operations are similar, and they are all database lookup operations.

Routing lookup, IP packet classification and ARP table classification are three independent functions, and they are at different levels of the router. In the previous technology, they were realized by three independent modules, so the complexity of the entire router system is very high. In addition, the search rate is not high in the previous technologies, especially the IP packet classification technology, which is generally implemented by software algorithms. Due to the high complexity of IP packet classification, it cannot achieve a high rate.

Contents of the invention

The purpose of the present invention is to provide a method and a search system that simultaneously support routing search, IP packet classification, and ARP search to reduce the complexity of the router system.

The method proposed by the present invention is characterized in that:

1. It contains the following steps in order:

(1) Receive and cache the following information:

IP header information, TCP (Transmission Control Protocol) header information or UDP (User Datagram) header information;

Receive the IP address that ARP (Address Resolution Protocol) searches for, refresh the message of routing table and classification rule base, refresh the Ethernet address and IP address pair of ARP table and cache;

(2) Make the search system internally generate an ARP table aging message at regular intervals;

(3) The following combined processing is done to the message received and the aging message of the above-mentioned ARP table:

(3.1) refresh the message of routing table and classification rule storehouse, the message of above-mentioned ARP table aging is decomposed into the micro instruction message of specific format respectively and caches;

(3.2) Perform different operation steps according to the following specific situations:

When the signal regularly set in the search system is in an effective state, and when there is a micro-command message in a specific format, the micro-command message in this specific format is selected to correspond to the tri-state content addressable memory (TCAM) in the search system, and the TCAM Read and write operations on synchronous static memory (SSRAM);

When there is packet header information (including IP header information, TCP header information, and UDP header information), select the packet header information to perform routing lookup and IP packet classification search operations through TCAM and SSRAM;

When there is an IP address for ARP search, the IP address for ARP search is selected to perform ARP search operation through TCAM and SSRAM;

When there is an external Ethernet address and IP address pair used to refresh the ARP table, the pair of Ethernet address and IP address used to refresh the ARP table is selected to perform a lookup operation for refreshing the ARP table through the TCAM and SSRAM.

(4) The results of routing lookup, IP packet classification and ARP lookup are sent externally;

2. The specified format microcommand message is any one of the following two types:

Refresh microinstructions decomposed into refresh commands received from the refresh interface of the routing table and classification rule base;

The ARP aging and ARP refresh microinstructions are generated according to the request information sent by the generating ARP aging request counting circuit and the request information sent by the ARP refreshing control circuit.

The search system proposed by the present invention is characterized in that it contains: a control circuit module, a TCAM bidirectionally connected to the control circuit module, and an SSRAM whose input terminal is connected to the TCAM output and bidirectionally connected to the control circuit module; wherein the control circuit The module contains: the input end is respectively connected to the data packet header receiving interface, the ARP search receiving interface, and the ARP refresh interface to connect the operation selection circuit for scheduling, the input end is connected to the routing table and the classification rule base refresh interface, and the output end is connected to the above operation selection circuit In order to decompose the received refresh command into an instruction decomposition circuit of micro instructions, an ARP aging request counting circuit for outputting an ARP aging request signal to the above-mentioned instruction decomposition circuit, the input terminal is connected to the operation selection circuit and the output terminal is connected to the instruction decomposition circuit The ARP refresh control circuit, the TCAM control circuit whose input terminal is connected to the output terminal of the operation selection circuit and the output terminal is connected to the TCAM input terminal, and the search data that is connected to the SSRAM input/output connection and the TCAM output terminal and the output terminal is connected to the operation selection circuit The receiving circuit is a search data processing circuit whose input ends are respectively connected to the above-mentioned search data receiving circuit and the operation selection circuit, and whose output ends are respectively connected to the ARP refresh control circuit, the routing search and IP packet classification result sending interface, and the ARP search result sending interface.

Trials have proved that the present invention reduces the complexity of the router system, and at the same time allows the system to flexibly configure the above-mentioned functions according to needs.

Description of drawings

Figure 1. Functional schematic of the lookup system.

Figure 2. Circuit block diagram of the lookup system.

Figure 3. The functional block diagram of the control circuit module and its external circuit and connection block diagram of various interfaces.

Figure 4. Multilayer encapsulation format for network packets.

Detailed ways

The search system completes three independent but similar functions. Figure 1 is a functional schematic diagram of the search system. Maintain the routing table, classification rule base and ARP table in the system to complete routing lookup, IP packet classification lookup, ARP lookup functions, and complete routing refresh, classification rule base refresh, ARP refresh and ARP aging. These functions can be divided into three parts: routing table function, IP packet classification function, and ARP table function. Each function can be turned on or off independently, so that the system can meet the needs of various applications.

The interfaces provided by the search system include:

1. Data packet header receiving interface (1-1): Receive data packet header information, which is the basis for routing lookup and IP packet classification;

2. ARP search receiving interface (1-2): Receive IP address, which is the basis for ARP search;

3. Routing table and classification rule base refresh interface (1-3): receive the refresh command of routing table and classification rule base;

4. ARP refresh interface (1-4): receive refresh information of ARP table;

5. Routing lookup and IP packet classification result sending interface (1-5): send the result of routing lookup and IP packet classification;

6. ARP search result sending interface (1-6): send the result of ARP search.

Figure 2 is a block diagram of the circuit principle of the search system, which consists of the following three parts:

1. Control circuit module (2-1): It is implemented by a programmable device, which mainly provides the external interface of the search system and controls the work of other modules in the system. It is the control center of the system.

2. TCAM (2-2): It is a content addressable memory, which stores a part of data in the routing table, classification rule base and ARP table in the system, and this part is mainly the basis for finding decisions.

3. SSRAM (2-3): It is used in conjunction with TCAM (2-2) to store another part of data in the routing table, classification rule base and ARP table, which is the result of the search.

The connection relationship of these three parts is: the control circuit module (2-1) is connected with the TCAM (2-2), controls the reading and writing and searching operations of the TCAM (2-2), and the TCAM (2-2) and the SSRAM (2 -3) connected, the control circuit module (2-1) controls the read and write operations of the SSRAM (2-3) through the TCAM (2-2), and the data line of the SSRAM (2-3) is directly connected to the control circuit module (2-1 ) connected.

Routing lookup, IP packet classification, and ARP lookup are all lookup processes. Fig. 4 is the multi-layer encapsulation format of the network data packet and the formats of the Ethernet header, the IP header and the transport layer header (taking the TCP protocol as an example). ARP search is the search process of the link layer. In this process, the destination Ethernet address of the Ethernet frame is obtained by searching the ARP table through the IP address; the routing search is to search the routing table according to the destination IP address of the IP packet to obtain the IP packet forwarding information, including the address of the next hop, forwarding port, etc.; IP packet classification is an extended function of the router, which can be based on IP headers, transport layer headers (such as TCP headers, UDP headers, etc.) or even higher-level protocols The data (commonly used data include destination IP address, source IP address, TOS, protocol of IP header, destination port and source port of TCP or UDP, etc.) Such as realizing the filtering of data packets, or setting the priority of this data packet, etc.).

The processing process in the search system includes: route search, IP packet classification, ARP search, routing table refresh, classification rule base refresh, ARP table refresh, ARP table aging.

Routing search: the control circuit module (2-1) receives the destination IP address through the IP header receiving interface (1-1), and then sends the destination IP address as a keyword to the TCAM (2-2) for searching, and the TCAM (2-2 ) search in the routing table, control the SSRAM (2-3) according to the result of the search, read the route search result from the SSRAM (2-3), send it to the control circuit module (2-1), and the control circuit module (2-2 -1) Send the route search result through the route search and IP packet classification result sending interface (1-5).

IP packet classification: the control circuit module (2-1) receives the specified packet header field (specified by the user of the search system, which can be the packet header field and the transport layer field) through the IP packet header receiving interface (1-1), and then these IP The packet header field is sent to TCAM (2-2) as a keyword for searching, and TCAM (2-2) searches in the classification rule base, and controls SSRAM (2-3) according to the result of searching, from SSRAM (2-3) Read out the IP packet classification result and send it to the control circuit module (2-1), and the control circuit module (2-1) sends the IP packet classification result through the routing search and the IP packet classification result sending interface (1-5).

ARP search: the control circuit module (2-1) receives the IP address through the ARP search receiving interface (1-2), and then sends the IP address as a keyword to the TCAM (2-2) for search, and the TCAM (2-2) is in Search in its ARP table, control SSRAM (2-3) according to the result of search, read the result of ARP search from SSRAM (2-3), send to control circuit module (2-1), control circuit module (2 -1) Send the ARP search result through the ARP search result sending interface (1-6).

Refresh the routing table: the control circuit module (2-1) receives the routing refresh command through the routing table and classification rule base refresh interface (1-3), and then refreshes the corresponding routing in the TCAM (2-2) and SSRAM (2-3) entry.

Classification rule base refresh: the control circuit module (2-1) receives the classification rule refresh command through the routing table and classification rule base refresh interface (1-3), then refreshes the corresponding The classification rule base entry.

ARP table refresh: the control circuit module (2-1) receives the ARP refresh command (Ethernet, IP address pair) through the ARP refresh interface (1-4), and then sends it to the TCAM (2-2) with the IP address as the key , TCAM (2-2) searches in the ARP table, controls SSRAM (2-3) according to the result of searching, reads the result of ARP searching from SSRAM (2-3), sends to control circuit module (2-1 ), the control circuit module (2-1) refreshes the corresponding ARP entry in the TCAM (2-2) and the SSRAM (2-3) according to the result of the search.

ARP table aging: there is a timer inside the control circuit module (2-1), which sends commands regularly to make the control circuit module (2-1) read an ARP table entry from the TCAM (2-2), and the ARP table entry Subtract one from the survival time, and then write the result after subtracting one to TCAM(2-2). If the lifetime becomes zero, the control TCAM (2-2) deletes the entry.

The control circuit module (2-1) of the present invention is the control center of the system, and Fig. 3 is a block diagram of the control circuit module (2-1) principle and a specific external circuit and a connection block diagram of various interfaces, and it can use a field programmable gate array (FPGA) or Application Specific Integrated Circuit (ASIC) implementation. All external interfaces of the system are provided through the control module. Inside the control module is an operation selection circuit (3-1), an instruction decomposition circuit (3-2), a TCAM control circuit (3-3), a search data receiving circuit (3-4), and a search data processing circuit (3-5) , ARP refresh control circuit (3-6), ARP aging request counting circuit (3-7) consists of 7 modules in total. For the refresh of the routing table and classification rule base, the instruction decomposition circuit (3-2) decomposes the refresh command received from the routing table and classification rule base refresh interface (1-3) into micro-instructions, and the instruction decomposition module is also aged according to ARP The request of the request counting circuit (3-7) and the request of the ARP refresh control circuit (3-6) generate microinstructions for ARP aging and ARP refresh. The operation selection circuit (3-1) decomposes the microinstruction according to the instruction decomposition circuit (3-2), the packet header information received by the IP packet header receiving interface (1-1), the IP address received by the ARP search receiving interface (1-2), ARP refresh interface (1-4) receives Ethernet address and IP address to choose a kind of operation, wherein the microinstruction is read and write operation, and the last three are search operations, and three kinds of search operations can be carried out in pipeline. After the operation selection circuit (3-1) selects the operation, it notifies the TCAM control circuit (3-3), and the TCAM control circuit (3-3) implements the corresponding sequence to access the TCAM (2-2) and SSRAM (2-3) . For both read and lookup operations, results are returned from the TCAM (2-2) or SSRAM (2-3) to the lookup data receiving circuit (3-4). If it is a read operation, the search data receiving circuit (3-4) sends the read-out result to the operation selection circuit (3-1), and provides parameters for performing other microinstructions; if it is a search operation, search the data receiving circuit (3-1) 4) Send the search result to the search data processing circuit (3-5). For the search operation, if it is an IP packet classification or route search, the search data processing circuit (3-5) sends out the IP packet classification result or the route search result through the routing search and the IP packet classification result sending interface (1-5); if For ARP search, the search data processing circuit (3-5) sends the ARP search result through the ARP search result sending interface (1-6); if it is the search operation carried out when ARP is refreshed, the search data processing circuit (3-5) Notify the ARP refresh control circuit (3-6). The ARP refresh control circuit (3-6) also receives the control of the operation selection circuit (3-1), sends a request to the instruction decomposition circuit (3-2), and requires the instruction decomposition module to generate micro instructions to complete the ARP refresh operation.

The method for decomposing instructions by the instruction decomposition circuit (3-2) is: the refresh command includes multiple commands such as adding, deleting, reading, moving routing and classification rules, the parameters of various commands, lengths and formats are inconsistent, and the instruction decomposition circuit ( 3-2) Decompose these commands into multiple microinstructions with fixed length and format, and cache these microinstructions, and these microinstructions complete the read and write operations to TCAM (2-2) and SSRAM (2-3). In addition, ARP aging and ARP update also need to read and write access to TCAM (2-2) and SSRAM (2-3). These read and write operations are completed in the form of micro instructions, that is, the instruction decomposition circuit (3-2) Aging and refresh requests generate and cache micro-instructions, which are consistent with the micro-instructions decomposed by routing and classification rule refresh commands, and are uniformly scheduled and processed by the operation selection circuit (3-1).

The method for operation selection circuit dispatching is: a signal (Signal) is set to valid in operation selection circuit (3-1) internal timing, when operation selection circuit (3-1) checks TCAM control module (3-2) idle time, If Signal is effective and microinstruction is arranged, select microinstruction to carry out processing so, and Signal is made invalid; Otherwise if there is the packet header information that receives interface (1-1) from IP packet header, carry out routing search and IP packet classification; Otherwise If there is an IP address received from the ARP lookup receiving interface (1-2), then perform an ARP lookup; otherwise, if there is an Ethernet address and IP address pair received from the ARP refresh interface (1-4), then perform an ARP refresh Find operations.

Claims (3)

1. support the method that the classification of route querying, IP bag, ARP search simultaneously, it is characterized in that it contains following steps successively:

(1) receive following data packet head information and buffer memory:

IP header packet information, TCP header packet information or UDP header packet information;

The message in routing table and classifying rules storehouse is refreshed in the IP address that receiver address analysis protocol ARP searches, refresh the ethernet address of ARP table and IP address to and buffer memory;

(2) make and search internal system and regularly produce the aging message of ARP table;

(3) message and the aging message of above-mentioned ARP table that receive are done following combined treatment:

(3.1) the message that refreshes routing table and classifying rules storehouse, the aging message of above-mentioned ARP table is decomposed into the microcommand message and the buffer memory of specific format separately;

(3.2) carry out different operating procedures respectively by following concrete condition:

When being in effective status searching the signal that internal system regularly is provided with, and when having specific format microcommand message to exist, just choose this specific format microcommand message correspondence to search three-state content addressable memory TCAM in the system, and synchronous static memory SSRAM is done read-write operation by TCAM;

When having the packet header packet information, choose the packet header packet information to do the search operation of route querying, the classification of IP bag by TCAM and SSRAM; Described packet header packet information comprises IP header packet information, TCP header packet information, UDP header packet information;

When existence was used to carry out IP address that ARP searches, the ARP search operation was done by TCAM and SSRAM in the IP address of just choosing ARP to search;

When existence be used for refreshing the external ethernet address of ARP table and IP address to the time, just choose the ethernet address that is used to refresh the ARP table and IP address to do the search operation that refreshes the ARP table by TCAM and SSRAM;

(4) externally send the result that route querying, the classification of IP bag and ARP search.

2. the method for supporting that simultaneously the classification of route querying, IP bag, ARP search as claimed in claim 1 is characterized in that: described specific format microcommand message is any in following two kinds:

The refresh command of receiving from routing table and classifying rules bank refresh interface resolves into refreshes microcommand;

Refresh microcommand according to producing the aging and ARP of ARP that solicited message that solicited message that the aging request of ARP counting circuit sends and ARP refresh control circuit send produces.

3. according to claim 1ly support the method that the classification of route querying, IP bag, ARP search simultaneously and the system that proposes, it is characterized in that it contains: control circuit module, with the two-way TCAM that is connected of this control circuit module, and input is connected with the TCAM output and with the two-way SSRAM that is connected of this control circuit module; Wherein control circuit module contains: input respectively with packet packet header receiving interface, ARP searches receiving interface, the function selector circuit that the ARP refresh interface links to each other and is used for dispatching, input termination routing table is with classifying rules bank refresh interface and output selects circuit to link to each other with aforesaid operations so that the refresh command that handle receives resolves into the instruction decomposition circuit of microcommand, be used for the aging request of ARP counting circuit to the aging request signal of above-mentioned instruction decomposition circuit output ARP table, input links to each other with function selector circuit and the continuous ARP refresh control circuit of output and instruction decomposition circuit, input links to each other with the function selector circuit output and TCAM control circuit that output links to each other with the TCAM input, I/O is connected and the TCAM output links to each other and output links to each other with function selector circuit searches data receiver circuit with SSRAM, input respectively with the above-mentioned data receiver circuit of searching, function selector circuit link to each other and output respectively with the ARP refresh control circuit, route querying and IP bag classification results transmission interface, ARP lookup result transmission interface links to each other searches data processing circuit.

Images