CN102739550A - Multi-memory flow routing architecture based on random duplication allocation - Google Patents

Abstract

The invention discloses a multi-memory pipeline routing architecture based on random copy allocation, which includes a routing buffer for caching data packets, a packet filter for preventing data packets with the same destination address from appearing in the routing buffer, and controlling the queued data packets and The scheduling unit of read and write access between the various memories, as well as the storage unit and the memory group, the prefix tree of the routing table is divided into a main tree and multiple sub-trees, the main tree contains the lower nodes of the prefix tree, and is converted into The index table stored in the index table storage unit, each subtree contains the high-level nodes of the prefix tree, each subtree has two copies, each copy is independently mapped to the memory group, and each arriving data packet generates a routing information Search request, the request includes one or more memory access operations, the target of each memory access operation is the memory where a node in the prefix tree is located, and each target node sequentially forms a link starting from the root node to a certain leaf node The ending lookup path.

Description

Multi-memory Pipeline Routing Architecture Based on Random Replica Allocation

technical field

The present invention relates to a routing architecture, in particular, to a random copy allocation technology and multiple memories to parallelize the routing information lookup operation of multiple data packets, thereby effectively improving the throughput of the routing system based on random Multi-memory pipeline routing architecture for replica allocation.

Background technique

An IP router implements two basic functions, which are routing function and switching function. When a data packet arrives at an input port of the router, it must go through the routing stage and the switching stage in turn. In the routing stage, the system obtains the destination address of the data packet , and look up the routing table accordingly to obtain the corresponding destination output port number; in the switching phase, the system switches the data packet to the designated output port through scheduling, so as to forward the data packet to the next hop site. Currently, prefix tree-based routing algorithms include Binary Trie (BT), Prefix Trie (PT) [1], Fixed-Stride Trie (FST) [2] and Multi-Prefix Trie (MPT) [3] and other algorithms.

The following terms are used in the presentations herein.

Destination address Under the IPv4/IPv6 Internet protocol, the destination address of a data packet can be expressed as a binary string with a length of 32/128.

A binary string with a length of n is an array S[0..n-1] formed by arranging n characters belonging to the character set ∑={0,1} according to their positions.

Binary prefix substring The prefix substring S[0.i] of the binary string S indicates a string from position 0 to position i in the S string, that is, S[0],S[1],...,S [i] string.

Routing table A routing table is composed of multiple records. One record is composed of a prefix sub-item and an output port number. A prefix sub-item is a binary string. The prefix sub-items of each record form a binary string set Π.

给定一个二进制字符串集合Π和字符串S[0..n-1]，若S′[0，..i]∈Π且则S'是S的一个匹配前缀。又若对S的任意匹配前缀S″[0..j]∈Π，有则我们称S'为S的关于Π的最长匹配前缀。The longest matching prefix For any two binary strings S ₁ [0..m-1], S ₂ [0..n-1], m<n, if S ₁ is the prefix substring of S ₂ , then We call S ₁ a matching prefix of length m of S ₂ , denoted as

Given a set of binary strings Π and strings S[0..n-1], if S′[0,..i]∈Π and Then S' is a matching prefix of S. And if any matching prefix S″[0..j]∈Π for S, we have Then we call S' the longest matching prefix of S with respect to Π.

Routing algorithm based on prefix tree In the routing stage, the system searches the routing table for the longest matching prefix that matches the destination address according to the destination address of the data packet. Intuitively, the system can sequentially compare the destination address with the prefix sub-items of each record in the table to obtain the longest matching prefix that meets the requirements. Obviously, this search method cannot obtain higher search efficiency. On the other hand, the strategy of transforming the routing table into a prefix tree to support fast routing lookup has been widely studied and extended to industrial production. Without loss of generality, in a prefix tree, a single prefix node can represent one or more records in the routing table, and the prefix nodes are connected by pointers. The routing lookup process of a data packet starts from the root node of the prefix tree and ends when it reaches a certain leaf node. During this process, the system matches the destination address of the data packet with the prefixes in all nodes on the search path, and records the longest matching prefix obtained among them. Finally, the system returns the output port number corresponding to the longest matching prefix, and the data packet then enters the switching stage.

Using the above terms, we give an example of routing lookup based on prefix tree. For the convenience of description, we choose BT routing algorithm to organize the prefixes in the routing table, as shown in Figure 1 and Figure 2:

According to the routing table shown in Figure 1, Figure 2 shows a prefix tree constructed using the BT routing algorithm, and each prefix node of the prefix tree contains at most one prefix. Assuming that the high-order 8 bits of the destination address of the data packet arriving at the router are 10101010, the route lookup process of the data packet can be described as follows: the data packet visits the root node of the prefix tree, the prefix of the root node is empty, and the matching is unsuccessful, and the Search the prefix tree according to the 0th bit of the destination address; if the 0th bit of the destination address is 1, the data packet visits the right child of the root node, the prefix of the node is empty, and the match is unsuccessful. Branch search prefix tree; the first bit of the destination address is 0, then the data packet visits the left child of the current node, the node prefix is 10*, the match is successful, the longest matching prefix is updated to 10*, and then according to the destination address The 2nd branch searches the prefix tree. Repeat the above steps, and finally find out that the routing table prefixes matching the destination address are 10* and 1010*. According to the definition of the longest matching prefix, the system returns the output port number R ₇ corresponding to 1010*.

There are many routing algorithms based on prefix tree, please refer to [1-15] for details. These algorithms can be further divided into serial prefix tree routing algorithms and parallel prefix tree routing algorithms. In the serial algorithm, the route lookup process of each data packet is executed strictly in sequence, so the processing speed of the system is slow and the throughput is low. To this end, a lot of research is devoted to designing an efficient multi-memory pipeline routing architecture, which can realize the parallel execution of multiple routing lookup processes by reasonably scheduling and arranging the access operations of memory resources, thereby greatly improving the overall performance of the system 【12-15】.

references:

[1]M.Berger, "IP lookup with low memory requirement and fast update," in Proc.IEEEHPSR,Jun2003,287-291.

[2] S.Sahni and K.Kim, "Efficient construction of multibit tries for IP lookup", IEEE/ACM Trans.on Networking, pp.650-662, Aug2003.

[3]S.Hsieh, Y.Huang and Y.Yang, "A novel dynamic router-tables design for IP lookup and update," in IEEE Int.Con.on Future Information Technology, May2010, pp.1-6.

[4] V. Srinivasan and G. Varghese, "Faster IP lookups using controlled prefix expansion," ACM Trans. on Computer Systems, pp.1–40, Feb1999.

[5] S.Nilsson and G.Karlsson, "IP-address lookup using lc-tries," IEEE J. on Selected Areas in Communications, pp.1083–1092, Jun1999.

[6] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for fastrouting lookups,” in Proc.ACM SIGCOMM, 1997, pp.3–14.

[7]V.Ravikumar, R.Mahapatra, and J.Liu, “Modified lc-trie based efficient routing lookup,” in Proc.IEEE Int.Symp.on MASCOTS,Jan2003,pp.177–182.

[8]S.Sahni and K.Kim, "Efficient construction of fixed-stride multibit tries for IPlookup," in IEEE Workshop on Future Trends of Distributed Computing Systems, Nov2001, pp.178–184.

[9]——,"Efficient construction of variable-stride multibit tries for IP lookup," in Proc.Symp.on Applications and the Internet, Feb2002, pp.220–227.

[10]S.Sahni and H.Lu, “Dynamic tree bitmap for IP lookup and update,” in IEEE Int.con.on Networking, April2007, pp.79–84.

[11] Y.Chang, Y.Lin, and C.Su, "Dynamic multiway segment tree for IP lookups and the fast pipelined search engine," IEEE Trans. on Computers, pp.492–506, Feb2010.

[12]K.Kim and S.Sahni, "Efficient construction of pipelined multibit-trie router-tables," IEEE Trans. on Computers, pp.32–43, Jan2007.

[13]M.Bando and H.J.Chao, "Flashtrie: Hash-based prefix compressed trie for IP routelookup beyond 100Gbps," in Proc.IEEE INFOCOM, March2010, pp.1–9.

[14]W.Jiang and V.Prasanna, "A memory-balanced linear pipeline architecture fortrie-based IP lookup," in IEEE Symp.on High-Performance Interconnects, Aug2007, pp.83–90.

[15]S.Kumar, M.Becchi, P.Corwley, and J.Turner, "CAMP:fast and efficient IP lookup architecture," in ACM/IEEE Symp.on Architecture for Networking and Communications Systems,2006,pp.51–60 .

[16] T. Anderson, S. Owicki, J. Saxe, and C. Thacker, "High-speed switch scheduling for local area networks," ACM Trans. Comput. Syst., pp.319–352, Nov1993.

[17] N.McKeown, "The iSLIP scheduling algorithm for input-queued switches," IEEE/ACM Trans.on Networking, pp.188–201, April1999.

[18]P.Sanders, S.Egner, and J.Korst, "Fast concurrent access to parallel disks," in Proc.11th annual ACM-SIAM symposium on Discrete algorithms,2000,pp.849–858.

[19]J.Vitter and E.Shriver, "Algorithms for parallel memory I: Two level memories."pp.110–147,1994.

[20] R.Barve, E.Grove, and J.Vitter, "Simple randomized mergesort on parallel disks," Paral.Comput.,pp.601631,1997.

Contents of the invention

In view of the above deficiencies, the present invention provides a multi-memory based on random copy allocation that effectively improves the throughput of the routing system by using random copy allocation technology and multiple memories to parallelize the routing information lookup operation of multiple data packets. Pipeline routing architecture, which includes a routing buffer for caching data packets, a scheduling unit for controlling read and write access between queued data packets and various memories, and a set of prefix tree structures for storing routing tables point memory.

The routing table prefix tree node realizes the mapping to the memory in the storage mode of random copy allocation.

It also includes an index table storage unit, the routing table prefix tree is divided into a main tree and multiple sub-trees, the main tree contains the low-level nodes of the prefix tree, and is converted into an index table, which is stored in the index In the table storage unit, each subtree contains high-level nodes of the prefix tree, and each subtree has two copies, and each copy is independently mapped to the storage group.

The index table includes several sub-items, and each sub-item consists of a prefix field and one or more node pointer fields.

Also included is a packet filter for checking each packet arriving at the routing architecture and preventing packets with the same destination address from appearing in the routing buffer.

The queuing policy of the data packets is as follows: 1) the system time is divided into time slots of fixed size, each time slot is defined as a storage access cycle, and each time slot is equally divided into M clock cycles; 2) every The length of the data packets arriving at the routing buffer is fixed, and the number of data packets arriving in each clock cycle is at most 1, that is, at most M data packets reach the routing architecture in each time slot; 3) At the end of each time slot, the scheduling unit Select a conflict-free set of data packets from the queued data packets in the routing buffer, all selected data packets access the memory bank in parallel to find the routing information stored in each memory, if a selected data packet completes its route information lookup task, then it will leave the routing buffer immediately; 4) Each memory can only be accessed once in a time slot.

Each arriving data packet generates a routing information lookup request, and the routing information lookup request includes one or more memory access operations. The target of each memory access operation is the memory where a node in the routing table prefix tree is located. Each target node The nodes in turn constitute a search path starting from the root node and ending at a certain leaf node.

The scheduling strategy of the scheduling unit is: Step 1) request: each queued data packet that has not been matched successfully sends a request to the root storage that has not been successfully matched; step 2) authorization: each requested storage sends a request to its Select one of the requested data packets to grant access permission; Step 3) Accept: Each authorized data packet selects one from all authorized storages to accept its access permission. Wherein, the root storage means the storage where the root node of each subtree is located.

Beneficial effects of the present invention: at first, routing architecture of the present invention provides a routing buffer to buffer the data packet that arrives, thereby supports the backbone network bandwidth demand that increases day by day, if the packet loss rate of routing buffer is less than that of switching buffer packet loss rate, then the performance of the routing architecture of the present invention can reach the performance of a routing system without a routing buffer; in addition, the present invention can not only avoid routing redundancy through the packet filter, but also prevent any two data with the same destination address The packet will be routed to the same output port, and the same data packets with the destination address can also be kept in the order of first-in-first-out; moreover, the present invention reduces memory in the pipeline routing architecture by using additional storage space through random copy allocation technology The frequency of access violations is higher, and the feasibility is higher.

Description of drawings

Figure 1 is an example diagram of a routing table;

FIG. 2 is a schematic diagram of a BT tree corresponding to the routing table;

Fig. 3 is a schematic diagram of the routing architecture of the present invention;

Fig. 4 is the structural representation of the queuing policy of the data packet of the present invention;

Fig. 5 is a schematic diagram of a two-way graph matching model;

Fig. 6 is the schematic diagram of the initial state of the present invention and the data packet that reaches;

FIG. 7 is a schematic diagram of the result of the pipeline parallel scheduling of a given data packet according to the present invention.

Detailed ways

The present invention will be further elaborated below in conjunction with accompanying drawing.

As shown in Figure 3, the multi-memory pipeline routing architecture based on random copy assignment of the present invention includes a routing buffer, a scheduling unit and a memory group, the routing buffer is used to cache the data packets entering the routing architecture, and the scheduling unit is used to control The read and write access between the queued data packet in the routing buffer and each memory, the memory group is used to store the memory of the prefix tree node of the routing table. A design assumption of traditional routers is that routers can provide real-time routing services for data packets arriving at any possible rate, so routers do not need to provide buffers to cache arriving data packets during the routing phase. In order to improve the throughput of the system, the routing architecture provides a routing buffer to buffer the arriving data packets, thereby supporting the ever-increasing bandwidth demand of the backbone network, and if the packet loss rate of the routing buffer is less than the packet loss rate of the switching buffer , then the performance of the routing architecture proposed by the present invention can reach the performance of the routing system without routing buffer. In addition, the present invention can also increase a packet filter, and the packet filter checks each data packet arriving at the routing architecture to prevent the same data packets with the destination address from appearing in the routing buffer. Using the packet filter has two purposes: one , to avoid routing redundancy, any two data packets with the same destination address will be routed to the same output port; second, keep the data packets with the same destination address in the first-in-first-out order.

In addition, the present invention realizes the mapping from routing table prefix tree nodes to storage by using a random copy allocation (RDA (Random Duplicate Allocation)) storage allocation technology. The tree nodes are evenly mapped to all the memory of the pipeline system. Compared with other existing pipeline routing design schemes, the Random Copy Allocation (RDA) technology reduces the access conflict frequency of the memory in the pipeline system by using additional storage space. The technique was first used for parallel disk data access management [18-20]. In detail, any routing table prefix tree is split into a main tree and multiple subtrees. The main tree contains the low-level nodes of the prefix tree and is converted into an index table. Each subtree contains part of the high-level nodes of the prefix tree. Points are mapped to memory groups. Further, each subtree has two copies, and each copy is independently mapped to memory groups. Thus, if the packet's route lookup process can access either of the two replica trees, it can proceed. We consider using RDA technology based on the following factors: In the process of building a high-performance routing system, it is easier, cheaper and feasible to increase the capacity of a single memory than to increase the number of memories.

For the convenience of description, we first give several proper nouns and their definitions as follows: When we refer to a subtree of a data packet, the subtree is the target subtree that the system needs to traverse to obtain the routing information of the data packet , for each subtree, the memory where its root node is located is called the root memory of the subtree. Furthermore, given a data packet, the root memory of its corresponding subtree can also be considered as the root memory of the data packet Root storage, since the RDA storage allocation technique provides two independent copies of each subtree in the storage group, there are two subtrees and two root storages per packet.

As shown in Figure 3, the present invention adds an index table storage unit for storing the index table, and the index table storage unit is generally a small and fast memory (such as SRAM), that is, the main tree of the routing table prefix tree is expressed as An index table, which is stored in a small, fast memory. Each subtree starts from the root node and is mapped to the memory group in layers. Without loss of generality, if the root node is stored in the memory numbered as i, then the jth layer node is stored in the numbered ( i+j) In the memory of modM, for each data packet newly arriving at the routing architecture, it will go through two processing stages to obtain the longest matching prefix of the data packet destination address, namely: a single-step matching of the lookup index table phase and a lookup phase involving multiple memory accesses. The index table contains 2 ^r sub-items, and each sub-item is composed of a prefix domain and one or more node pointer domains. Therefore, the execution flow of the routing information lookup process of a data packet is as follows: first, the system obtains the destination address of the data packet The highest r bits, and use it as the index of the i-th sub-item of the index table, if the node pointer of the i-th sub-item is empty, then this routing search is completed; otherwise, the system will start from the node pointer Starting from the root node of the subtree pointed to by , the subtree is traversed to complete the routing information lookup request.

In order to maintain the total throughput of the memory at a high level, the scheduling goal of the system is to select a data packet set as large as possible from the queued data packets. The root memory of any two data packets in this set is different, and the root memory Different packets can perform memory access operations simultaneously. For each subtree, its root node is randomly stored in any memory, and its descendant nodes are cyclically mapped to the subsequent memory of the root memory. Therefore, in the process of routing information lookup for data packets, the target The traversal of the subtree begins with the access to the root memory until it reaches the end of the memory where a certain leaf node is located. During this process, the routing information lookup request visits a node in each layer and a layer in each memory, thus , the access operation of the corresponding subtree of the selected data packet set can be executed in parallel in a batch manner. Here, the term batch means that the traversal process of all selected subtrees starts at the same moment, and the batch process ends when all traversal processes are completed.

Below, we give the following assumptions and parameter declarations to establish the packet queuing strategy for the routing architecture:

1) The system time is divided into time slots of fixed size, and each time slot is defined as a storage access cycle, further, each time slot is equally divided into M clock cycles.

2) The length of each data packet arriving at the routing buffer is fixed, and the number of arriving data packets per clock cycle is at most 1, in other words, at most M data packets arrive at the routing architecture in each time slot.

3) At the end of each time slot, the scheduling unit selects a non-conflicting data packet set from the queued data packets, and all selected data packets access the memory bank in parallel to find the routing information stored in each memory. If the data packet completes its routing information lookup task, it will leave the routing buffer immediately.

4) Each memory can only be accessed once in a time slot.

For the convenience of expression, we introduce the following two parameters:

N: The number of queued data packets in the routing buffer, and the capacity of the buffer is L data packets.

M: Amount of available memory. We use the symbols m ₁ , m ₂ ,...,m _M to denote the memory, and for the convenience of expression, we assume that M is an integer power of 2.

Based on the above assumptions and parameter definitions, we present the queuing strategy of the routing architecture involved in Figure 4. In this model, each arriving data packet generates a routing information lookup request, and the routing information lookup request contains one or more For memory access operations, the target of each memory access operation is the memory where a certain node in the prefix tree is located, and each target node sequentially forms a search path starting from the root node and ending at a certain leaf node.

Scheduling strategy

For each newly arrived data packet, the system searches the index table through the first r bits of the data packet address to locate the position of the root node of its subtree in the memory bank, then, the system sets up a routing information lookup request for the data packet, The lookup request traverses the target subtree layer by layer to obtain routing information. We also use a multi-dimensional tuple of the form R(s ₁ ,s ₂ ,...,s _i ,...,s _t ) to represent a routing information Find requests.

The routing information lookup process of a data packet is divided into two stages: the scheduling stage and the access stage. In the former stage, the system selects a data packet set with different root memories; in the latter stage, the system simultaneously traverses the selected The corresponding subtrees of the data packets are used to obtain routing information, and the root storages of the data packet collections obtained in the scheduling stage are different, so the search requests corresponding to these data packets can be executed in parallel. In the access phase, each selected data packet will traverse its target subtree. In detail, without loss of generality, assume that R _i , R _j are the routing information lookup requests of any two selected data packets, M _i , M _j is the target root memory of the two search requests, then in the access phase, the search request R _i will cyclically visit the numbers M _i , M _(i+1)modM , M _(i+2)modM , .. . The memory sequence until it reaches a certain leaf node ends, and the same is true for R _j . Therefore, the search requests R _i and R _j are conflict-free during the entire access phase, and each corresponding search step can be executed in parallel.

As shown in Figure 5, the arbitration problem in the scheduling stage can be transformed into a two-way graph matching problem, where the two vertex sets are N queued packets and M memories respectively, if there is an arc between the packets and the memory , it means that the root node of the subtree of the data packet is located in this memory. Note that each subtree has two replica trees, thus, we have two replica trees independently distributed in the memory group, and two distributed By visiting any copy of the subtree at the root node in a different memory, we can get the required routing information. Therefore, each packet vertex in the graph has two edges. In general, we can use any two-way graph matching algorithm to find the largest matching set between memory banks and queued packets, these matching algorithms include FCFS (First Come First Served), PIM (Parallel Iterative Matching) [16], iSLIP [17] and so on, the goal of scheduling is to find a maximum match between the queued data packets eligible to participate in scheduling and all available memory, we give an algorithm framework for this scheduling problem in the following. Note that at the beginning of each round of scheduling, all queued data packets and memory are in an unmatched state, and the system iteratively performs the following three steps until a maximum match is found.

Step 1) Request: Each queued data packet that has not been successfully matched sends a request to the root memory that has not been successfully matched;

Step 2) Authorization: Each requested memory selects one of the requested data packets to grant access permission;

Step 3) Accept: Each authorized data package selects one of all authorized storages to accept its access permission.

In order to help understand the routing information search process under the scheduling policy framework, we give a simple scheduling example in Figure 6 and Figure 7. Note that the scheduling unit adopts a first-come-first-served scheduling policy to control the relationship between the storage group and the data packet set. access operations. Here, we assume that the available memory quantity is M=4, and the initial buffer data packet number N=0, the system time is divided into equal-sized time slots, each time slot is further subdivided into M clock cycles, each At most one data packet arrives at the routing buffer in each clock cycle. For the convenience of expression, we assume that each unmatched queued data packet randomly selects one of its unmatched root memories and sends an access request to it.

At time slot 0, P ₀ -P ₃ arrives at the routing buffer, and the system generates routing information lookup requests R ₀ -R ₃ for each data packet. Here, R ₀ corresponds to P ₀ , R ₁ corresponds to P ₁ , and so on. Because R ₂ and R ₃ request access to m ₂ at the same time, the system has a memory access conflict. According to the first-come-first-served arbitration policy, m ₂ is granted to P ₂ who arrived earlier. As a result, the lookup request {R ₀ , R ₁ , R ₂ } for the packet {P ₀ , P ₁ , P ₂ } is elected. The set of lookup requests {R ₀ , R ₁ , R ₂ } is a conflict-free access set that can be executed in parallel by the system. As shown in the table, the batch job continuously consumes slots 1-3 to perform memory access operations. It is obvious that the duration of the visit phase is determined by the R ₀ that requires the most visits.

The system initiates the next round of scheduling in time slot 4, and the search request {R ₃ , R ₅ , R ₆ , R ₈ } is selected, and the system consumes three consecutive time slots 5-7 to execute the memory access operation of the selected routing information search request, Approximately, in slot 8 and slot 12, lookup requests {R ₇ R ₉ R ₁₀ } and {R ₁₁ } are elected respectively. Note that we don't have to create a lookup request R ₄ , because the routing information of P ₄ has been directly determined in the fast matching stage of the index table.

From this example, we notice that the routing information lookup process of a data packet includes two processing stages: the scheduling stage and the following access stage. The former phase lasts for one slot and the latter phase lasts for one or more slots. In the scheduling phase, the system selects a set of queued data packets to perform routing information lookup tasks. The lookup request of each selected data packet needs to consume multiple consecutive time slots. We can also see that for any two routing information lookup processes that are executed continuously, we can execute the access phase of the previous lookup process and the scheduling phase of the latter lookup process in parallel to further improve system efficiency. However, to simplify the description, we assume in this example that routing processing is performed sequentially, non-overlappingly.

The above description is only a preferred embodiment of the present invention, the present invention is not limited to the above embodiment, there may be local minor structural changes during the implementation process, if the various changes or modifications of the present invention do not depart from the spirit of the present invention and scope, and belong to the claims and equivalent technical scope of the present invention, the present invention also intends to include these changes and modifications.

Claims (8)

1. A multi-memory pipeline routing architecture based on random copy allocation, which includes a routing buffer for buffering data packets, a scheduling unit for controlling read-write access between queued data packets and each memory, and a set of memories for storing the routing table prefix tree nodes. 2. The multi-memory pipeline routing architecture based on random copy allocation according to claim 1, wherein the routing table prefix tree node realizes the mapping to the memory in a storage manner of random copy allocation. 3. The multi-memory pipeline routing architecture based on random replica allocation according to claim 2, further comprising an index table storage unit, the routing table prefix tree is divided into a main tree and multiple subtrees, The main tree contains the low-level nodes of the prefix tree and is converted into an index table. The index table is stored in the index table storage unit. Each sub-tree contains the high-level nodes of the prefix tree. Each sub-tree has two copies. Each copy are independently mapped into memory banks. 4. The multi-memory pipeline routing architecture based on random copy allocation according to claim 3, wherein the index table includes several sub-items, and each sub-item is composed of a prefix domain and one or more node pointer domains . 5. according to claim 1, based on the multi-memory pipeline routing architecture of random copy distribution, it is characterized in that, also comprising a data packet for checking each arrival routing architecture, preventing the occurrence of the same destination address in the routing buffer. Packet filter for packets. 6. according to the described multi-memory pipeline routing architecture based on random copy distribution according to claim 3, it is characterized in that, the queuing strategy of the data packet is: 1) The system time is divided into time slots of fixed size, each time slot is defined as a storage access cycle, and each time slot is equally divided into M clock cycles; 2) The length of each data packet arriving in the routing buffer is fixed, and the number of data packets arriving in each clock cycle is at most 1, that is, at most M data packets reach the routing architecture in each time slot; 3) At the end of each time slot, the scheduling unit selects a non-conflicting data packet set from the queued data packets in the routing buffer, and all selected data packets access the memory bank in parallel to find the routing information stored in each memory, If an elected data packet completes its routing information lookup task, it will leave the routing buffer immediately; 4) Each memory can only be accessed once in a time slot. 7. The multi-memory pipeline routing architecture based on random copy assignment according to claim 6, wherein each arriving data packet generates a routing information lookup request, and the routing information lookup request includes one or more memory access operations , the target of each memory access operation is the memory where a certain node in the prefix tree of the routing table is located, and each target node sequentially forms a search path starting from the root node and ending at a certain leaf node. 8. The multi-memory pipeline routing architecture based on random copy assignment according to claim 6, wherein the scheduling strategy of the scheduling unit is: Step 1) Request: Each queued data packet that has not been successfully matched sends a request to the root memory that has not been successfully matched; Step 2) Authorization: Each requested memory selects one of the requested data packets to grant access permission; Step 3) Accept: Each authorized packet selects one of all authorized storages to accept its access permission, Wherein, the root storage means the storage where the root node of each subtree is located.

Images