• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The path search system is more effective than the conventional binary tree search in the IP transmission apparatus. The route retrieval system determines the node to transmit next based on the destination address specifying the communication destination. In this system, each node entry information and path data of the hierarchical structure is set in a tree structure, and the tree structure is an M branch tree structure in which N bits (N is an integer of 2 or more) are checked from the upper bits of the destination address (M = 2). A path memory having N ); And route retrieving means for retrieving the node entry information of the memory sequentially from the initial layer to the lower layer based on the destination address to derive the corresponding route data.
    公开号:KR20020006464A
    申请号:KR1020010041465
    申请日:2001-07-11
    公开日:2002-01-19
    发明作者:가네하라후미까즈
    申请人:가네꼬 히사시；닛본 덴기 가부시끼가이샤；
    IPC主号:
    专利说明:

    ROUTE RETRIEVING SYSTEM, METHOD THEREFOR AND A ROUTER DEVICE TO BE USED IN THE SAME}
    [32] The present invention generally relates to a route retrieval system, and a method thereof, and a storage medium for recording the router apparatus to be used therein and the control program thereof. In particular, the present invention relates to a route retrieval system for determining a node for transmitting a received packet based on a destination address specifying a communication counterpart.
    [33] In the Internet, when an IP (Internet Protocol) packet is transmitted by a relay device such as a router device, the relay device (router device) refers to the next transmission destination by referring to a target (destination) address (hereinafter referred to as "DA"). IP address (hereinafter referred to as "NH" (Next Hop address)) is determined. This is called path search. This relay device has a route table (path information memory) associated with "DA" and "NH". "NH" corresponding to "DA" is retrieved from the route table for each input IP packet.
    [34] 16 shows an example of a route table of IPv4 (IP version 4). In Figure 16, "NA" and "mask length" indicate that "DA" belongs to the network. On the other hand, the mask length indicates that when the value is "N", the upper N bits of the 32 bits are "1". That is, in the case of 24, it corresponds to "0xFFFFFF00" in hexadecimal notation. This is called a net mask. For example, if "DA" is "11.1.1.5", it belongs to the network represented by the entry of entry number three. It is determined that the AND (logical product) of the net mask represented by "DA" and the mask length coincides with "NA" of the same entry.
    [35] Here, it is assumed that an IP packet having a "DA" of "10.1.0.1" is input to the relay apparatus having the route table shown in FIG. This relay device takes the entry with the longest mask length among the entries with the NA to which "DA": 10.1.0.1 belongs. This is Longest Prefix Matching (LPM). In this example, entries 1 and 2 are considered as candidates for the search results. Since entries have a longer mask length, entry 2 is selected as the relay result. Therefore, the relay device transmits the IP packet to the IP address of "21.1.1.1" indicated by "NH".
    [36] As described above, when searching for an IP path, there is a possibility that a plurality of candidates satisfying a search criterion exist in one search, and a result needs to be derived by the LPM. This is because "NA" to which "DA" belongs cannot be seen only from "DA" of an input IP packet. With the above problems in mind, there are several proposals on how to implement route tables and search processing. The proposals can typically be classified into two types.
    [37] One of these two methods is to implement with dedicated hardware that can be processed in parallel. For example, by providing a retrieval circuit for each entry in the route table, all entries in the route table are retrieved in parallel. This method is fast by accessing each entry in the route table in parallel, while the cost is expensive.
    [38] Another method is applicable when parallel access to the route table is not possible. This corresponds to mounting hardware or software that uses general-purpose memory or a field programmable gate array (FPGA). While this method can be implemented at low cost by using existing equipment, it is not as fast as parallel processing.
    [39] These methods can be optionally used depending on the use or purpose. The former method is applicable to a device that is directed to a large-scale backbone network and requires a large capacity of transmission. On the other hand, for a device used in a relatively medium or small network period, the latter may be sufficient.
    [40] Next, a specific method will be described for the latter method. The latter method may be classified into a hash method and a binary tree structure search method. As a method using a hash method, there is a method for lowering "DA" and searching for a key by using an arbitrary hash function. In the case of IPv4, since the address is 32 bits, fast searching is enabled if an entry space of 32 powers 2 12 of 2 can be provided in advance. However, it is not realistic in terms of cost. By using a hash function, the entry space can be made small. However, by using the hash method, collision of entries may occur. In addition, in the case of IPv4, each hash method should simply be applied to 31 net mask patterns.
    [41] Binary tree structures are common in software installations. In Japanese Unexamined Patent Publication No. Hei 11-191781, a mounting method of hardware is proposed. An example of a binary tree structure is shown in FIG. In Fig. 17, each sphere is referred to as a node of a binary tree. On the other hand, in the expression "xxxxxxxx / y" written in each node, "x" is "NA" in hexadecimal notation and "y" is a mask length.
    [42] For example, when "DA" is "0x800AC091", since "y" of node 1 is "0", the most significant bit of "DA" branches to the right when the most significant bit is "1" and the most significant bit is " 0 "is checked to branch to the left. In this case, branching to the right side selects node 2 as the next search target. At node 2, since the mask length is 8, the AND of "0xFF000000" and "DA" checks whether the result matches "NA" written at node 2. If it does not match, the search ends because there is no entry corresponding to "DA". In the given example, since the result matches "NA" in node 2, it checks whether check bit 8 (high ninth bit) is "1" or "0" and affects further branches. The above process is repeated until no further branches exist or the "NA" in the node does not match.
    [43] The binary tree structure is applicable to the LPM and is more effective than the hash method. However, all 32 bits should be checked by the registered entry in the worst case. In particular, in IPv6 (IP version 6) with an address space of 128 bits, the efficiency is degraded.
    [44] An object of the present invention is to provide a path search system that is more effective than conventional binary tree search in an IP transmission device.
    [45] According to a first aspect of the present invention, in a path search system for determining a node to be transmitted next based on a destination address specifying a communication destination,
    [46] Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Path memory with; And
    [47] Path search means for retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data.
    [48] The node entry information specifies path data presence information indicating the presence or absence of the path data at a corresponding node, link presence information indicating the presence or absence of a link to a lower layer, a layer value indicating the lower layer, and a node of the lower layer. And a node ID, a path data ID for specifying the path data, and a network address corresponding to the node entry. The entry information of the route data may have at least an address value of a node to be transmitted next.
    [49] The route retrieving means sets the initial layer of the tree structure and the node ID of the root node as initial values, reads the upper N bits of the destination address corresponding to the initial layer, and reads the upper N bits and the root node. Address generating means for generating an address for reading the path memory using a node ID, and determining the link presence information of the node entry information, and hierarchical information of the node entry information read when the link exists and the node. And child node determining means for instructing generation of a read address of the node entry information of the next lower layer by sending an ID to the address generating means.
    [50] Further, the path retrieving means includes address determination means for determining the correspondence between the network address of the read node entry information and the destination address, and path data presence or absence for judging the path data presence information of the read node entry information. And a judging means and control means for controlling the reading of the memory in accordance with the judging result of the address judging means, the path data presence judging means and the child node judging means.
    [51] According to a second aspect of the present invention, in the path search method for determining a node to be transmitted next based on a destination address specifying a communication destination,
    [52] Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Providing a path memory having a); And
    [53] And retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding route data.
    [54] The node entry information specifies path data presence information indicating the presence or absence of the path data at a corresponding node, link presence information indicating the presence or absence of a link to a lower layer, a layer value indicating the lower layer, and a node of the lower layer. A node ID, a path data ID for specifying the path data, and a network address corresponding to the node entry. The entry information of the route data may have at least an address value of a node to be transmitted next.
    [55] In the path retrieving step, the initial layer of the tree structure and the node ID of the root node are initial values, the upper N bits of the destination address corresponding to the initial layer are read, and the upper N bits of the root node are read. An address generating step of generating an address for reading the path memory using a node ID, and determining the link presence information of the node entry information, and when the link exists, the hierarchical information of the read node entry information and the And sending a node ID to the address generation step, which may involve generating a child node instructing generation of a read address of the node entry information of a next lower layer.
    [56] The path retrieving step includes: an address judging step of judging the correspondence of the network address and the destination address of the read node entry information, and a path data presence judging step of judging the path data presence information of the read node entry information; And a control step of controlling the reading of the memory in accordance with the determination result of the address determination step, the path data presence determination step, and the child node determination step.
    [57] According to a third aspect of the present invention, in a router apparatus for determining a node to be transmitted next based on a destination address specifying a communication destination,
    [58] Each node entry information and path data of the hierarchical structure are set in a tree structure, wherein the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Path memory with; And
    [59] Path search means for retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data.
    [60] According to a fourth aspect of the present invention, a storage medium having recorded thereon a control program of a path search method for determining a node to be transmitted next based on a destination address specifying a communication destination, the control program comprising:
    [61] Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Providing a path memory having a); And
    [62] And retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding route data.
    [63] The operation of the present invention will be described. Unlike the conventional binary tree check that checks the target address every bit, by using the M branch tree structure that checks every N bits (N> 1), the number of accesses of the lookup table is reduced. Note that M is the power of (N) of 2. Next, check every N bits and longest match check per bit.
    [1] 1A is a conceptual explanatory diagram showing a conventional binary tree search method.
    [2] 1B is a conceptual explanatory diagram showing a method for searching an M branch (M> 2).
    [3] 2 is an explanatory diagram showing an example of the tree structure of a route table according to the present invention;
    [4] 3 is an explanatory diagram showing a relationship between an IP address and a node;
    [5] 4 is an explanatory diagram showing an example of a node entry;
    [6] 5 is an explanatory diagram showing an example of a path data entry structure;
    [7] 6 is an explanatory diagram illustrating a configuration of a path search circuit.
    [8] 7 is a flowchart showing the operation of the child node determination processing unit 606.
    [9] 8 is a flowchart showing the operation of the validity determination processing unit 607;
    [10] 9 is a flowchart showing the operation of the NA determination processing unit 608;
    [11] 10 is a flowchart showing the operation of the L field determination processing unit 609;
    [12] 11 is a flowchart showing processing logic of the control unit 611.
    [13] 12A and 12B are explanatory diagrams for explaining the necessity of the NA determination processing unit 608.
    [14] Fig. 13 is an explanatory diagram showing the structure of a node entry in another embodiment of the present invention.
    [15] 14 is an explanatory diagram showing a configuration of a route data entry according to another embodiment of the present invention;
    [16] 15 is an explanatory diagram showing a configuration of a path search circuit 600 according to another embodiment of the present invention.
    [17] 16 is an explanatory diagram for explaining an example of Longest Prefix Matching (LPM).
    [18] 17 is an explanatory diagram for explaining an example of a normal binary tree structure.
    [19] <Explanation of symbols for main parts of drawing>
    [20] 600: path search circuit
    [21] 601: DA holding unit
    [22] 602: address generator
    [23] 603: node reader
    [24] 604: external memory
    [25] 605: memory controller
    [26] 606: child node determination processing unit
    [27] 607: validity determination processing unit
    [28] 608: NA judgment processing unit
    [29] 609: L field judgment processing unit
    [30] 610: result output unit
    [31] 611 control unit
    [64] In the following, the present invention will be described in detail with respect to a preferred embodiment of the route search system of the present invention with reference to the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding. However, as will be apparent to one of ordinary skill in the art, the present invention may be practiced without these specific details.
    [65] FIG. 1A is a conceptual explanatory diagram showing a conventional binary tree search method, and FIG. 1B is a conceptual explanatory diagram of a "M" branch (M> 2) search method. 1A and 1B, rectangular blocks are nodes and circular blocks are data regions. The node has information for searching. The result data (path information) to be output to the data area is stored. In practice, the node and data area reside on memory and store the address of the data area in the node.
    [66] For example, when the IP address which is the search key is " 0x80E10001 ", the nodes 101, 102, and 103 are candidates. Of these nodes, the node with the longest matching length is the final result and outputs to the data area 104. On the other hand, assuming that the IP address is " 0x80000001 " and that a matching node does not exist under node 107, node 106 becomes a search result output to data area 108. Here, it should be noted that nodes 101, 102 and 103 in the previous example and nodes 105 and 106 in the later example should be examined for the binary tree.
    [67] 1B shows an example of replacing a binary tree structure with the "M" branch tree structure proposed in the present invention. Here, assume that "M" is "8" and "N" is "3". Primarily, by checking the ninth, tenth, and eleventh bits of the IP address in a lump, a branching destination can be determined. In this case, since no node has a net mask length of "9" or "10", an entry with a net mask length of "9" and "10" cannot be retrieved. Therefore, as shown in Fig. 1B, the data area is linked to the node from one having a longer net mask length within the bit width range of " N ".
    [68] For example, in the case of "0x80E10001", the node 109 becomes a candidate and the data area becomes the reference number "110". Here, the data area 111 corresponds to the data area of the node 102, but since the data area is linked to the node in descending order of the net mask length, the data area linked to the node 109 is the result, and is linked to the node. The data areas 111 and 112 need not be read. Similarly, in the case of "0x80000001", since there is no entry corresponding to the net mask length 11 at the node 113, in particular, if the result does not exist at the next node, the data area to which data is output is a reference number. "114". In this method of the present invention as compared to the conventional binary tree structure, the number of node-ends can be reduced, and LPM (Longest Prefix Matching) can be more easily achieved.
    [69] In the following, an embodiment of the case of sixteen branch trees adapted to IPv4 is discussed. 2 is an explanatory diagram conceptually illustrating a tree structure of the illustrated embodiment. The tree is divided into eight hierarchical stages L0 to L7. The tree consists of node and path data. Each node is identified by a unique node identifier (NID). Each node has 16 node entries. Nodes include root nodes, leaf nodes, and branch nodes. The root node is a fixed node in the hierarchy stage L0. The branch node is located at a different hierarchical stage than the hierarchical stage L0. One of the node's entries has a branch linked to another node at the lower hierarchy. Each leaf node is one node, and one of the node entries of the node has path data. The branch node may be a leaf node. Each node and path data occupies each area on the memory.
    [70] 3 shows the relationship between an IPv4 address and a tree structure. 32 bits of the IPv4 address are divided into a plurality of blocks in units of 4 bits, and each block is identified by B0 to B7. B0 to B7 correspond to each hierarchical stage of L0 to L7 in FIG. For example, the relationship between node A and node B in FIG. 2 becomes the relationship shown in FIG. 3. Primarily, the node entry of node B occurs by adding a bit string of blocks corresponding to the hierarchical stage of node A required for " NID " of node A, and adding several bits of " 0 ". do. This is the address of the node entry forming node B.
    [71] 4 shows the configuration of a node entry. In FIG. 4, "V" indicates whether a node entry is valid, "1" is a valid node, and "0" is a null node. If the node is null, the information in the other fields is meaningless at all. "L" indicates whether the associated node entry has path data. Therefore, it may be one bit configuration indicating "1" or "0". However, in the illustrated embodiment, 4 bits are allocated for the following reasons. If the "L" field is not "0000", the node has path data. "C" represents the presence or absence of a link to a lower hierarchy. When " C " is " 1 ", the node entry indicates a link to the node at the lower hierarchal stage.
    [72] "CL" represents "1" and the hierarchy of nodes in the lower hierarchical stage that is valid when linked. When "C" is "1", "NID" represents a node ID of a valid lower hierarchy. "EID" is an identifier of the route data. By "EID", the memory address storing the route data is uniquely identified. When "L" is not "0000", "EID" is valid. Finally, "NA" is the network address corresponding to the node entry.
    [73] In the following, the use of "L" is discussed. The tree consists of 4 bit blocks of IPv4. Therefore, when the net mask length is not 4 bit boundary, the "L" field is used. In the illustrated embodiment, the block consists of 4 bits. In addition, the "L" field is composed of 4 bits. Referring to the example of Fig. 3, when "L" is "1 ***", there is path data corresponding to the net mask length of "12". Similarly, when "L" is "* 1 **", the net mask length is "11", and when "L" is "** 1 *", the net mask length is "10". At this time, according to the LPM, the identifier of the LPM path data is set as "EID". For example, when "L" is "1010", the identifier of the path data corresponding to the net mask length of "12" becomes "EID".
    [74] 5 shows an example of the configuration of the route data. When "A" is "1", it indicates that the route data is valid. When "P" is "1", it indicates that there is a link to other path data. At "NEID", "EID" of the route data for the link destination is stored. "NH" and "OP" are the IP address and output port of the destination, respectively. Considering the example of FIG. 1, in the "NEID" field of the route data 110, the "EID" of the route data 111 is stored. The path search circuit 600 in the relay equipment (router device) based on the tree structure described above will be described in block diagram form in FIG.
    [75] First, in the path search circuit 600, 32 bits of the target IP address DA, an initial hierarchal stage (corresponding to LO in FIG. 2), and an ID of the root node of FIG. 2 are input. The value of the initial hierarchal stage is "0" and the root node ID is a fixed value. The input "DA" is stored in the DA holding unit 601. The address generator 602 reads a block (B2 in the example of FIG. 3) corresponding to " CL " (indicative of the lower hierarchical stage of the node) supplied by the child node determination processing unit 606, and determines the child node. The address shown in FIG. 3 is generated using the bit string of the block supplied from the processing unit 606 and " NID " (indicating the node ID of the lower hierarchical stage) and output to the node reading unit 603. FIG.
    [76] The address generator 602 holds a read layer value indicating a layer value (B0 to B7 in Fig. 3) for reading from " DA " and the node ID. First, the input initial layer value is used as the read layer value, and the root node ID (fixed value) is used as the node ID. The node reading unit 603 receives a node reading request from the control unit 601, reads a node entry of the address output from the address generating unit 602, and determines the child node determination processing unit 606, the validity determination processing unit 607, and NA. Output to the decision processing unit 608 and the L field decision processing unit 609, respectively.
    [77] As shown in the operation flowchart of Fig. 7, the child node determination processing unit 606 checks the "C" bit of the node entry (step S1). When "C" is "1", the "CL" field value and the "NID" field value are output to the address generator 602 (step S2). The address generator 602 generates the next address using the "CL" value and "NID" value. The child node determination processing unit 606 simultaneously outputs the "C" bit value to the control unit 611 (step S3). As shown in the operation flowchart of Fig. 8, the validity determination processing unit 607 extracts the "V" bit of the node entry (step S21) and outputs it to the control unit 611 (step S22).
    [78] As shown in the operation flowchart of FIG. 9, the NA determination processing unit 608 ANDs the " DA " field held by the DA holding unit 601 and the " NA " field of the node entry (step S31), and as a result. It is checked whether it is the same as the "NA" field of the node entry (step S32). If it is the same, " 1 " is output to the control unit 611 (step S33), and if it is not the same, " 0 " is output to the control unit 611 (step S34). As shown in the operation flowchart of FIG. 10, the L field determination processing unit 609 checks the "L" field of the node entry (step S41). If the "L" field is not "0000", the "EID" field value of the node entry is output to the result output unit 610 (step S42). On the other hand, when "L" is "0000", "0" is output to the control unit 611 (steps S33 and S34), and when "L" is not "0000", "1" is the control unit 611. ) Is output (step S45).
    [79] The processing contents of the control unit 611 are shown in FIG. The inputs from the child node determination processing unit 606, the validity determination processing unit 607, the NA determination processing unit 608, and the L field determination processing unit 609 are represented by one bit so as to form a 4-bit value as shown in FIG. do. By the combination of the 4-bit input values, the control section 611 outputs the node read request signal to the node reading section 603, and outputs a result output request signal and an "EID" request signal to the result output section 610. FIG.
    [80] Only when receiving the "EID" update request from the control unit 611, the result output unit 610 holds the "EID" output from the L field determination processing unit 609. FIG. If there is already a "EID" already held, the "EID" held is updated. On the other hand, when a result output request from the controller 611 is received, the path data is read from the external memory 604 through the memory controller 605, and the " OP " and " NH " values of the read path data are read. Output In the case where the holding " EID " does not exist, a search error indication signal is output.
    [81] Through the above-described processing, tree nodes established as memory areas are sequentially tracked to find desired path information.
    [82] Here, in Fig. 8, the necessity of the determination processing of the NA determination processing unit 608, mainly, of the input " DA " value held in the DA holding unit 601 by logical multiplication and the node entry read by the node reading unit 609 The necessity of determining the agreement of "NA" values is discussed with reference to FIG. For example, when the "DA" value is "0x11223344" and the "DA" value of one node entry is "0x1122E344", the tree structure shown in Fig. 12B is mainly considered.
    [83] At this time, in the illustrated embodiment in which the decision processing is performed at the initial hierarchal stages L0 to L7 per 4-bit block, the node entry corresponding to NA = 0x1122E344 is read out at the hierarchical stage L4. If this value of "NA" differs from "DA" in the hierarchical stage L4, this entry that does not satisfy the condition should be discarded. Therefore, the NA decision processing unit 608 is provided to process the coincidence determination by comparing all bit values of " DA " and " NA ".
    [84] As another embodiment, the case where "NA" is present in the path data information and not in the node entry information is discussed. In the method of the present invention, the memory size of the node can be unnecessarily large. In particular, when IPv4 having a large number of bits in a block or a large address length is handled, the memory size must be controlled.
    [85] In this embodiment, take an IPv6 address. In IPv6, the network address is upper 64 bits. This information is not provided in the node entry but in the path data. As a result, the memory size of the node entry is reduced. In this case, the configuration of the node entry is shown in FIG. 13, and the structure of the path data is shown in FIG.
    [86] 15 is a block diagram showing the configuration of the illustrated embodiment of the path search circuit 600. Components similar to those of FIG. 6 are identified by like reference numerals. In FIG. 15, a component different from that in FIG. 6 is the NA determination processing unit 608. When the NA determination processing unit 608 determines that the route data exists in the L field determination processing unit 609, the NA determination processing unit 608 receives "EID" from the L field determination processing unit 609 and stores the memory controller 605. The " NA " value in the path data is read out from the external memory 604 by using &lt; RTI ID = 0.0 &gt; 1, &lt; / RTI &gt; and processes similar to the NA determination processing unit 608 in FIG. The other circuit configuration handles the same process as the circuit configuration of FIG. In order to simplify the description and facilitate a clear understanding of the present invention, redundant descriptions of processes and processes common to those shown in FIG. 6 are omitted.
    [87] The structures other than the DA holding unit 601, the memory 604, and the memory controller 605 shown in Figs. 6 and 15 preliminarily store the control program in a read-only storage medium and control it with a computer (CPU). It should be noted that the program can be implemented by reading and processing the control operation.
    [88] The present invention implements a method of dividing an IP address into blocks using an M branch tree (M &gt; 2) and simultaneously checking a plurality of bits without checking each bit. Therefore, the number of accesses to the lookup table can be reduced compared to binary tree lookup. In addition, in checking a plurality of bits in the lump, there is a problem that the net mask length can be treated in units of a plurality of bits. However, the present invention enables the handling of the net mask length per bit by using the configuration when the path data is linked.
    [89] The retrieval method that handles IP addresses on a block-by-block basis is particularly effective when dealing with IPv6 packets having addresses of 128 bits in length, four times the IPv4 address.
    [90] As will be appreciated by those of ordinary skill in the art, the present invention has been shown and described with respect to embodiments, but various other changes, omissions, and additions as described above can be made without departing from the spirit and scope of the invention. Can be done on. Therefore, it is intended that the invention not be limited to the particular embodiments described above but rather that the invention encompasses all possible embodiments that may be embodied within the scope and equivalent equivalents included in the invention with respect to the features on the appended claims. It must be understood.
    权利要求:
    Claims (20)
    [1" claim-type="Currently amended] A path search system for determining a node to be transmitted next based on a destination address specifying a communication destination,
    Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Path memory with; And
    Path search means for retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data;
    Route search system, characterized in that.
    [2" claim-type="Currently amended] The node entry information of claim 1, wherein the node entry information includes path data presence information indicating presence or absence of the path data at a corresponding node, link presence information indicating presence or absence of a link to a lower layer, and a hierarchy value indicating the lower layer. And a network address corresponding to the node entry, and a node ID for specifying a node of a lower layer, a path data ID for specifying the path data, and a network address corresponding to the node entry.
    [3" claim-type="Currently amended] 3. The route retrieval system according to claim 2, wherein the entry information of the route data has at least an address value of a node to be transmitted next.
    [4" claim-type="Currently amended] The method of claim 2, wherein the path retrieving means sets the initial layer of the tree structure and the node ID of the root node as initial values, reads the upper N bits of the destination address corresponding to the initial layer, and the upper N. Address generating means for generating an address for reading the path memory using a bit and a node ID of the root node, and
    By determining the link presence information of the node entry information and transmitting the hierarchical information of the node entry information read in the presence of a link and the node ID to the address generating means, the read address of the node entry information of the next lower layer is determined. Child node determining means for instructing creation
    Route search system, characterized in that.
    [5" claim-type="Currently amended] 5. The apparatus as claimed in claim 4, wherein the path retrieving means comprises: address determination means for determining the correspondence between the network address of the read node entry information and the destination address, and determining the path data presence information of the read node entry information. And path control means for controlling the reading of the memory in accordance with determination results of the address determination means, the path data existence determination means, and the child node determination means.
    [6" claim-type="Currently amended] A path search method for determining a node to be transmitted next based on a destination address specifying a communication destination,
    Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Providing a path memory having a); And
    A path retrieval step of retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data;
    Route search method, characterized in that.
    [7" claim-type="Currently amended] 7. The method of claim 6, wherein the node entry information includes path data presence information indicating presence or absence of the path data at a corresponding node, link presence information indicating presence or absence of a link to a lower layer, a layer value indicating the lower layer, and And a node ID specifying a node of a lower layer, a route data ID for specifying the route data, and a network address corresponding to the node entry.
    [8" claim-type="Currently amended] The method of claim 7, wherein the entry information of the route data has at least an address value of a node to be transmitted next.
    [9" claim-type="Currently amended] 8. The method of claim 7, wherein the path retrieving step uses the initial layer of the tree structure and the node ID of the root node as initial values, reads the upper N bits of the destination address corresponding to the initial layer, and the upper N. An address generating step of generating an address for reading the path memory using a bit and a node ID of the root node, and
    The read address of the node entry information of the next lower layer by determining the link presence information of the node entry information and transmitting the layer information of the read node entry information and the node ID to the address generation step when a link exists. Determining a child node instructing generation of
    Route search method, characterized in that.
    [10" claim-type="Currently amended] 10. The method of claim 9, wherein the path retrieving step comprises: an address determination step of determining a correspondence between the network address of the read node entry information and the destination address, and determining the path data presence information of the read node entry information. And a control step of controlling the reading of the memory in accordance with the determination result of the path data existence step to be performed, and the determination result of the address determination step, the path data presence determination step, and the child node determination step.
    [11" claim-type="Currently amended] A router apparatus for determining a node to be transmitted next based on a destination address specifying a communication destination,
    Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Path memory with; And
    Path search means for retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data;
    Router device, characterized in that.
    [12" claim-type="Currently amended] 12. The method of claim 11, wherein the node entry information includes path data presence information indicating presence or absence of the path data at a corresponding node, link presence information indicating presence or absence of a link to a lower layer, hierarchical value indicating the lower layer, and And a node ID for specifying a node of a lower layer, a path data ID for specifying the path data, and a network address corresponding to the node entry.
    [13" claim-type="Currently amended] 13. The router apparatus according to claim 12, wherein the entry information of the route data has at least an address value of a node to be transmitted next.
    [14" claim-type="Currently amended] 13. The method of claim 12, wherein the path retrieving means sets the initial layer of the tree structure and the node ID of the root node as initial values, reads the upper N bits of the destination address corresponding to the initial layer, and the upper N. Address generating means for generating an address for reading the path memory using a bit and a node ID of the root node, and
    By determining the link presence information of the node entry information and transmitting the hierarchical information of the node entry information read in the presence of a link and the node ID to the address generating means, the read address of the node entry information of the next lower layer is determined. Child node determining means for instructing generation
    Router device, characterized in that.
    [15" claim-type="Currently amended] 15. The apparatus according to claim 14, wherein the path retrieving means comprises: address determination means for determining the correspondence between the network address of the read node entry information and the destination address, and determining the path data presence information of the read node entry information. And control means for controlling reading of the memory in accordance with determination results of the path data existence determining means and the address determining means, the path data existence determining means, and the child node determining means.
    [16" claim-type="Currently amended] A storage medium having recorded thereon a control program of a path search method for determining a node to be transmitted next based on a destination address specifying a communication destination,
    The control program,
    Each node entry information and path data of the hierarchical structure are set in a tree structure, and the tree structure is an M branch tree structure (M = 2 N ), which is checked every N bits (N is an integer of 2 or more) from the upper bits of the destination address. Providing a path memory having a); And
    A path retrieval step of retrieving the node entry information of the memory sequentially from an initial layer to a lower layer based on the destination address to derive corresponding path data;
    Storage medium, characterized in that.
    [17" claim-type="Currently amended] The method of claim 16, wherein the node entry information includes path data presence information indicating the presence or absence of the path data at a corresponding node, link presence information indicating the presence or absence of a link to a lower layer, a layer value indicating the lower layer, and And a node ID specifying a node of a lower layer, a path data ID for specifying the path data, and a network address corresponding to the node entry.
    [18" claim-type="Currently amended] 18. The storage medium of claim 17, wherein the entry information of the route data has at least an address value of a node to be transmitted next.
    [19" claim-type="Currently amended] 18. The method of claim 17, wherein the path retrieving step sets the initial layer of the tree structure and the node ID of the root node as initial values, reads the upper N bits of the destination address corresponding to the initial layer, and the upper N. An address generating step of generating an address for reading the path memory using a bit and a node ID of the root node, and
    The read address of the node entry information of the next lower layer by determining the link presence information of the node entry information and transmitting the layer information of the read node entry information and the node ID to the address generation step when a link exists. Determining a child node instructing generation of
    Storage medium, characterized in that.
    [20" claim-type="Currently amended] 20. The method of claim 19, wherein the path retrieving step comprises: an address determination step of determining a match between the network address of the read node entry information and the destination address, and determining the path data presence information of the read node entry information. And a control step of controlling the reading of the memory in accordance with the determination result of the path data existence step to be performed, and the determination result of the address determination step, the path data presence determination step, and the child node determination step.
    类似技术:
    公开号 | 公开日 | 专利标题
    US9627063B2|2017-04-18|Ternary content addressable memory utilizing common masks and hash lookups
    US9245626B2|2016-01-26|System and method for packet classification and internet protocol lookup in a network environment
    US8880554B2|2014-11-04|Method and apparatus for high performance, updatable, and deterministic hash table for network equipment
    US9280609B2|2016-03-08|Exact match lookup scheme
    US7633960B2|2009-12-15|Dense mode coding scheme
    KR100477391B1|2005-03-17|Full match| search algorithm implementation for a network processor
    US5425026A|1995-06-13|Multi-protocol packet switching network
    JP2539155B2|1996-10-02|Method and apparatus for message routing
    CN101421991B|2011-04-06|Hardware filtering support for denial-of-service attacks
    US6775737B1|2004-08-10|Method and apparatus for allocating and using range identifiers as input values to content-addressable memories
    US7924833B2|2011-04-12|Packet transfer unit
    US6457061B1|2002-09-24|Method and apparatus for performing internet network address translation
    US7668160B2|2010-02-23|Methods for performing packet classification
    US6553002B1|2003-04-22|Apparatus and method for routing data packets through a communications network
    CN1179523C|2004-12-08|Method and apparatus for four-way hash table
    US7984038B2|2011-07-19|Longest prefix match | algorithm implementation for a network processor
    Zane et al.2003|CoolCAMs: Power-efficient TCAMs for forwarding engines
    Tzeng et al.1999|On fast address-lookup algorithms
    US7234019B1|2007-06-19|Method and apparatus for implementing a search engine using an SRAM
    US7193997B2|2007-03-20|Packet classification
    US6782382B2|2004-08-24|Prefix search method and data structure using compressed search tables
    US9680747B2|2017-06-13|Internet protocol and Ethernet lookup via a unified hashed trie
    US7212529B2|2007-05-01|System for retrieving destination of a packet with plural headers
    JP4336625B2|2009-09-30|Packet transfer device
    US6212184B1|2001-04-03|Fast scaleable methods and devices for layer four switching
    同族专利:
    公开号 | 公开日
    EP1172971A2|2002-01-16|
    US20020009056A1|2002-01-24|
    CN1333616A|2002-01-30|
    KR100472275B1|2005-03-08|
    JP2002026973A|2002-01-25|
    EP1172971A3|2004-04-21|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2000-07-12|Priority to JP2000210654A
    2000-07-12|Priority to JPJP-P-2000-00210654
    2001-07-11|Application filed by 가네꼬 히사시, 닛본 덴기 가부시끼가이샤
    2002-01-19|Publication of KR20020006464A
    2005-03-08|Application granted
    2005-03-08|Publication of KR100472275B1
    优先权:
    申请号 | 申请日 | 专利标题
    JP2000210654A|JP2002026973A|2000-07-12|2000-07-12|Path retrieval system and its method, and router used for it|
    JPJP-P-2000-00210654|2000-07-12|
    [返回顶部]