Background technology
Route querying belongs to the part of route forerunner engine.Network interface packet, sends to forerunner's engine by interchanger after receiving packet.The major function of forerunner's engine is at first CRC (cyclic redundancy check (CRC) code) verification to be carried out in data packet header, and the destination address according to packet carries out route querying then, inquires this and wraps next jumping port numbers.Therefore, route querying is the essential step of data forwarding.Because the data traffic of routing forwarding constantly increases at present, this inevitable requirement improves constantly the efficient of route querying, also makes route querying become the bottleneck that improves data forwarding efficient day by day.
About route querying, start with from pure technical standpoint on the one hand at present and improve the existing system of searching; On the other hand, be to utilize the existing system of searching to realize route querying in conjunction with novel equipment and the complexity that reduces computing.Present route querying mainly is to carry out the longest matched and searched on the basis of the address structure of CIDR (classless inter-domain routing).CIDR address structure use＜address/prefix length〉to representing route entry.
Through existing literature search is found, the Chinese patent publication number is: CN1362822.A, name is called: the high speed route lookup system of content-based addressable memory, this technology comprises: Content Addressable Memory, synchronous static memory, route querying coprocessor and drive circuit, wherein: Content Addressable Memory links to each other with the route querying coprocessor by drive circuit, is read and is write by the route querying coprocessor control.Though this method effectively raises the speed of route querying, this method relates to the complex protocol of static memory read-write, and simultaneously, SOC (system on a chip) will be obtained memory address by bus, utilizes bus to carry out read-write operation again, causes crossing of bus resource to utilize.
Find by retrieval again, the Chinese patent publication number is: CN1863169.A, name is called: the route searching result processing method of processor Network Based, this technology sets up and safeguards a route querying cache table in the high-speed memory on the sheet of network processing unit, carrying out principle that order adjusts according to least-recently-used principle manages the list item of cache table, effectively raise seek rate, but, the existence of cache table must cause taking in a large number of storage resources, especially in the application of backbone network, its coverage rate belongs to tens0000 to IP up to a million, and its resources occupation rate also is very big so.
Summary of the invention
The objective of the invention is to overcome above shortcomings in the prior art, a kind of system that improves speed of route lookup is provided.The present invention has realized searching fast of route system by the combination of SOC (system on a chip) (SOC) and hardware searching module, not only have seek rate soon, realize simple advantage, but also have easy transplanting and extendible characteristics.
The present invention is achieved by the following technical solutions:
The present invention includes: driver module, interface module, initialization module, route memory module, human-computer interaction module and search module, wherein: driver module links to each other with human-computer interaction module and transmits activation bit, human-computer interaction module links to each other with interface module and transmits interactive information, interface module links to each other with initialization module and transmits initialization information, interface module with search the module transmission interactive information that links to each other, search module and link to each other with the route memory module and transmit routing iinformation to be found.
Described initialization module comprises: flag bit initialization submodule, memory address initialization submodule and state machine initialization submodule, wherein: flag bit initialization submodule links to each other with state machine initialization submodule with memory address initialization submodule respectively and transmits effective control information, memory address initialization submodule links to each other with interface module and transmits the initialization storage address information, and state machine initialization submodule links to each other with interface module and transmits the init state machine information.
Described route memory module comprises: four master meter sub module stored and four sublist sub module stored, wherein: each master meter sub module stored and each sublist sub module stored respectively with search the module routing address information that transmission searches that links to each other.
The described module of searching comprises: cut apart submodule, addressing submodule, read submodule, write submodule and judge submodule, wherein: cut apart submodule link to each other with interface module the transmission human-machine interactive information, cut apart submodule link to each other with the addressing submodule transmission effective address information, addressing submodule and judge the affirmation information that submodule links to each other and transmits routing address to be found is read submodule and is write submodule and link to each other with the route memory module respectively and transmit routing iinformation to be read and routing iinformation to be written.
Compared with prior art, the invention has the beneficial effects as follows:
1, speed height: average seek rate can reach 50M bar/second;
2, complexity is low: do not relate to the operation on other agreements, effectively improved total line use ratio of read-write;
3, the data space that takies is few: improved utilization of space by addressing of address efficient in operation ground;
4, broken away from binary tree structure: make the additions and deletions of memory space have more flexibility;
5, be fit to the route storage of low capacity, when there is suitable big capacity storage hardware device the outside, this system also can expand to jumbo route table items at an easy rate, more than the 10M bar.
Embodiment
Below system of the present invention is further described: present embodiment is being to implement under the prerequisite with the technical solution of the present invention, provided detailed execution mode and concrete operating process, but protection scope of the present invention is not limited to following embodiment.
Embodiment
Present embodiment comprises: driver module, interface module, initialization module, route memory module, human-computer interaction module and search module, wherein: driver module links to each other with human-computer interaction module and transmits activation bit, human-computer interaction module links to each other with interface module and transmits interactive information, interface module links to each other with initialization module and transmits initialization information, interface module with search the module transmission interactive information that links to each other, search module and link to each other with the route memory module and transmit routing iinformation to be found.
Described initialization module comprises: flag bit initialization submodule, memory address initialization submodule and state machine initialization submodule, wherein: flag bit initialization submodule links to each other with state machine initialization submodule with memory address initialization submodule respectively and transmits effective control information, memory address initialization submodule links to each other with interface module and transmits the initialization storage address information, and state machine initialization submodule links to each other with interface module and transmits the init state machine information.
The flag information that the utilization of described flag bit initialization submodule receives is effectively controlled with information memory address initialization submodule and state machine initialization submodule and is revised.
Described memory address initialization submodule carries out initialization to the content of a large space address.
Described state machine initialization submodule makes whole system enter and treats the operation state.
Described route memory module comprises: four master meter sub module stored and four sublist sub module stored, wherein: each master meter sub module stored and each sublist sub module stored respectively by the conflict situation flag bit with search the module routing address information that transmission searches that links to each other, separate between the master meter sub module stored, separate between the sublist sub module stored.
The route memory module is the read-write RAM (random access memory) of a 64KB in the present embodiment, and this RAM is divided into 4, and corresponding respectively IP prefix length is 1～20,21～24,25～28 and 29～32.For each block RAM memory block, in order to overcome the collision problem that HASH (hash) brings effectively, be provided with two memory blocks respectively---master meter sub module stored and sublist sub module stored, wherein: the master meter sub module stored has write down IP prefix, IP prefix length, collision flag position and the relevant routing iinformation of self; The sublist sub module stored has write down IP prefix, IP prefix length and relevant routing iinformation.
The described module of searching comprises: cut apart submodule, addressing submodule, read submodule, write submodule and judge submodule, wherein: cut apart submodule link to each other with interface module the transmission human-machine interactive information, cut apart submodule link to each other with the addressing submodule transmission effective address information, addressing submodule and judge the affirmation information that submodule links to each other and transmits routing address to be found is read submodule and is write submodule and link to each other with the route memory module respectively and transmit routing iinformation to be read and routing iinformation to be written.
The described submodule of cutting apart separates the routes/prefixes length information that human-computer interaction module obtains.
Described addressing submodule locks corresponding master meter sub module stored and sublist sub module stored to the prefix length information of cutting apart submodule and obtaining.
Described judgement submodule guarantees that the routing address of being searched is the address of really storing routing iinformation.
Describedly read submodule and the described submodule of writing is made amendment to route information and fed back.
The addressing of RAM is 14 in the present embodiment, the information of each bar address storage 32bits, each bar routing iinformation is formed by 64, comprises self IP prefix prefix of 32bits, the mixed information of 32bits (prefix length, conflict normal bit and next hop information).
According to the prefix of each node, try to achieve one 14 long address address by HASH, routing iinformation is deposited in the corresponding address.
Know that in the write operation to routing table what native system distributed is the address space of 16K*4Byte, and every routing iinformation comprises the data of 2*4Byte, therefore, this system's maximum can only be stored 8K bar information.Distribution (1: 8, promptly a master meter routing iinformation may conflict with it by potential 8 routing iinformations, and the routing iinformation that will occur conflicting is assigned in the sublist) according to parallel HASH method of the IPV4 of prefix optimization and master meter sublist.Identical when the space that each sublist sub module stored and master meter sub module stored are distributed, then each table can only be stored 1K bar routing iinformation at most.But master meter and sublist exist 1: 8 corresponding relation, so with respect to the sublist routing iinformation of 1K bar, the master meter sub module stored can only be stored 128 routing iinformations.Therefore, the real effective address figure place of herein calculating by HASH has only 7bits.
The HASH that adopt in this place utilizes XOR to realize, is example with first memory partitioning A here, and the core address is prefix[31:25], prefix[26:20] and prefix[21:15] the resultant A of XOR by turn between three items.When carrying out storage, this moment is for the master meter of first memory block, its address be 00000A00 (A front herein " 00000 " with " 00 " be respectively that the author is according to allocation space and definition voluntarily, each memory space is had nothing in common with each other, and it is also different between each master meter sublist), after searching the address, at first read operation is carried out in this address, when reading routing iinformation, then show and stored data in the master meter sub module stored, new data need be stored in the sublist sub module stored, the collision flag position in the master meter is set simultaneously.
For the search procedure of route, be exactly to adopt above-mentioned address computation method to obtain optimum IP address and obtain next hop information in fact in conjunction with the principle of long coupling.
The time of searching that the present embodiment method obtains is 16 * 10-9S, thus the seek rate of present embodiment method remains more than the 51M/s, and accurately obtained the address of next jumping.