JPH1070573A - Route information retrieving circuit - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a route information retrieving circuit retrieving route information faster by minimizing the number of accessing times to a memory storing a routing table. SOLUTION: An IP(internal protocol) address (32bits) is separated (102 to 106) into three parts (the common part of a high order, the route information referring part of an intermediate order and the subnet mask part of a smallest size IP network of a low order) from user's information (VPI)(virtual path identifier). Then the common part of the high order is used for collating arithmetic (108) for judging whether a sent cell is effective or ineffective. In addition, the intermediate-order bit is used as the memory address of route reference (107) with user information to assign route information to an area designated by the address. Thereby route information is obtained by once access to a memory.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route information retrieving circuit in a route sorting device used in an Internet system. The present invention relates to a route information retrieving circuit which manages route information based on destination information in transmitted communication information. The present invention relates to a route information search circuit that can check route information at high speed.

[0002]

2. Description of the Related Art In an Internet system, a device called a router for distributing transmission information according to a route determined from a route information management table using a destination IP address (internet protocl address) as a key is provided as a device for connecting networks. ing. In the conventional router, a table for managing the route information is provided, and the route information is checked from the destination information in the transmitted communication information and the table. Most of the circuits for checking the route information use a processor, sequentially read the information written in the table, and sequentially compare the information with the destination information (IP address) to find a matching IP address.
Thereby, the corresponding route information is determined.

[0003]

In the conventional router (route distribution device) as described above, the search of the route information is executed by the processing by the processor. And
Until a matching IP address is found by this search process, the routing table, that is, the memory is accessed many times.

Therefore, it is important to reduce the number of accesses to the memory in order to speed up the process of searching for the route information in the router. However, in the conventional search processing of searching for route information having the same IP address by comparing the transmitted IP address with the IP address read from the table, there is a limit to the reduction in the number of accesses. Further, in such conventional technology,
In the search processing, access to the same memory may be repeated, and it is not always suitable for a pipeline-like processing.

The present invention has been made in view of the above circumstances, and provides a route information search circuit capable of searching for route information at a higher speed by minimizing the number of accesses to a memory storing a routing table. The purpose is to do.

[0006]

According to the first aspect of the present invention,
A route information search circuit in a communication device that compares the transmitted transmission destination information with a table that manages the route information and searches for and determines the route information. A bit serving as a physical address in the written memory is cut out, and the memory is accessed based on the address.

According to a second aspect of the present invention, there is provided the route information search circuit according to the first aspect, wherein the transmitted transmission destination information is a matching part common to the registered transmission destination information. It is characterized in that a circuit is provided for cutting out necessary bits and determining whether or not the bits are registered.

According to a third aspect of the present invention, the internal processing in the route information search circuit according to the first or second aspect is sequentially performed in a pipeline manner.

[0009]

DESCRIPTION OF THE PREFERRED EMBODIMENTS In a communication apparatus to which the present invention is applied, route information (IP address-transmission VPI T) is referred to by referring to a table based on transmission destination information (a destination IP address).
able) is determined. The transmitted transmission destination information is, for example, a predetermined number of bits (for example, 32 bits).
In the search table, route information corresponding to each transmission destination information is included in the search table. Also, the transmission destination information registered in the search table often has a common upper bit portion.

Therefore, in the present invention, the transmission destination information is converted from user information (VPI: virtual path identifier) into three parts (an upper common part, an intermediate path information reference part, and a lower minimum size IP network subnet mask part). ), And the upper common part is used to determine whether the transmitted cell is valid or invalid. The middle bit is used as the memory address of the route reference together with the user information, and is routed to the area specified by the address. Assign information.

That is, the transmission destination information is divided into a coincident part and a non-coincidence part for each user information, and the coincidence part is used for comparison with the registered transmission destination information, and the non-coincidence part is used as a path information reference part in the address of the memory. Search in one shot.

As described above, when examining the table, instead of processing by the processor, dedicated hardware for performing the above-described processing is created, and this is incorporated to check the route information stored in the table. And the table (memory)
In order to perform the access only once, a part of the source user information and the transmission destination information is subjected to arithmetic processing using the address of the corresponding route information in the direct memory, and access is performed based on the address.

[0013] In this way, conventionally, the memory is accessed and compared a number of times by the processing of the processor to obtain the route information, and a match search is performed from the result. Can be greatly reduced.

Hereinafter, more specific embodiments of the present invention will be described. FIG. 1 shows a route information search circuit according to an embodiment of the present invention by a function over time.
The embodiment in the communication device including both the route reference portion and the valid transmission information determination portion is shown.

In the route information search circuit according to the embodiment of the present invention, first, two things are simultaneously performed from the start 101. One is extraction 102 of the IP address included in the transmission information, and the other is extraction 103 of the VPI.

The extracted VPI value is r-bit information, a
The address of the first memory in which the bit information and the IPv bit string are stored, and r,
a of each bit information and a bit string of IPv4 are read out as data (Memory VPI T 104 in FIG.
able access).

Here, the r-bit information is bit information used for performing a process (105) of separating a path information reference unit (IPr bit string), which will be described later, from the IP address extracted in “IP address extraction 102”. It is. For example, an IP address (3
2 bits)

[0018]

In this case, the r-bit information becomes ***. *. ***. *: 01011101.00000011.11101111.00000000... R. That is, r-bit information refers to all registered I
A point where the value of each bit of the P address matches “1” or “0” is “0”, the value of a bit of a certain IP address is “1”, and another IP address is “0”. That is, the place where the bit value is different is set to "1". Therefore, the bits required for the route reference information are
This is the portion of the value in the r bit information that is "1".

On the other hand, the a-bit information is used to separate a matching portion (IPa bit string), which will be described later, from the IP address extracted in the “IP address extraction 102” (1).
06). For example,
If the r-bit information is ***. *. ***. *: 01011101.00000011.11101111.00000000... r, the a-bit information is ***. *. ***. *: 10100010.11111100. 00010000.00000000 ... a That is, the a-bit information has the inverse relationship between the r-bit information and exactly "1" and "0" at each bit position, except for the lower few bits of the maximum subnet mask length (here, tentatively 8 bits). It is in.

The IPv bit string is an AN at each bit position of all registered IP addresses and a-bit information.
D indicates the value obtained by comparing the IP for verification in the process described later.
Used as an address. For example, IPv4 in the above example
The bit string is 192.1.4.0:11000000.00000001.00000100.00000000 ***. *. ***. *: 10100010.11111100.00010000.00000000… a ***. *. ***. *: 1 * 0 *** 0 * .000000 * *. *** 0 ****. ********… IPv157.2.101.0: 10011101.00000010.01100101.00000000 ***. *. ***. *: 10100010.11111100.00010000.00000000… a ***. * . ***. *: 1 * 0 *** 0 * .000000 **. *** 0 ****. ******** ... IPv In the following description, the r-bit information, a-bit information, and IPv bit string will be used as appropriate.

Next, a process of outputting the IPr bit string in the route information reference section and outputting the IPa bit string in the matching part (10)
5, 106) are performed. Now, to explain these processes, suppose that the value of the IP address obtained in “IP address extraction 102” is as follows. 157.2.1.3:10011101.00000010.00000001.00000011… IP

At this time, in the “extraction of path information reference portion 105”, only the bit position of “1” of the r bit information is extracted from the value of the IP address, and this is used as an IPr bit string. Therefore 157.2.1.3:10011101.00000010.00000001.00000011 ... IP ***. *. ***. *: 01011101.00000011.11101111.00000000 ... r ***. *. ***. *: * 0 * 11101. ****** 10.000 * 0001. ******** ... It becomes IPr.

On the other hand, in "matching portion extraction 106", only the bit position of "1" of the a-bit information is extracted from the value of the IP address, and this is set as an IPa bit sequence. Therefore, 157.2.1.3:10011101.00000010.00000001.00000011… IP ***. *. ***. *: 10100010.11111100.00010000.00000000… a ***. *. ***. *: 1 * 0 *** 0 * .000000 **. *** 0 ****. ******** ... It becomes IPa.

Subsequently, the route information table is accessed, and information such as the output port is read (M in FIG. 10).
emory Routing Table Access)
At the same time, a collation operation is performed by the collation operation unit using the IPv bit string and the IPa bit string (collation operation of 108).

Here, "Memory Routing"
In the memory access in the “table access 107”, an address obtained by combining the IPr bit string excluding a bit portion unnecessary for referring to the path information with the VPI and the VPI is used. For example, if the VPI is 00001001, the access address is as follows. VPI: 00001001 ***. *. ***. *: * 0 * 11101. ****** 10.000 * 0001. ********… IPr 00001001.011101.10.0000001… Address

For this reason, in the route information table, information such as an output port is written in advance from a registered IP address to an address given by the above-described arithmetic processing. An example of the configuration of the route information table will be described below. In the following example, V at the time of input is
The PI is set to 00001001, and each row represents “IP address: address of route information table → data in route information table (output VPI)”.

157.1.1.0:00001001.011101.01.0000001 → 00000001 (VPI No.1) 157.1.2.0:00001001.011101.01.0000010 → 00000001 (VPI No.1) 157.1.3.0:00001001.011101.01.0000011 → 00000001 (VPI No.1) 157.2. 0.0: 00001001.011101.10.0000000 → 00000000 (VPI No.0) 157.2.1.0:00001001.011101.10.0000001 → 00000000 (VPI No.0) 157.2.2.0:00001001.011101.10.0000010 → 00000000 (VPI No.0) 157.2.100.0:00001001.011101.10.0110100 → 00000100 (VPI No.4) 157.2.101.0:00001001.011101.10.0110101 → 00000100 (VPI No.4) 157.2.200.0:00001001.011101.10.1101000 → 00000101 (VPI No.5) 157.3.0.0:00001001.011101.11.0000000 → 00010010 (VPI No. .18) 192.1.1.0:00001001.100000.01.0000001 → 00000010 (VPI No.2) 192.1.2.0:00001001.100000.01.0000010 → 00000010 (VPI No.2) 192.1.3.0:00001001.100000.01.0000011 → 00000010 (VPI No.2) 192.1. 4.0: 00001001.100000.01.0000100 → 00001000 (VPI No.8) ・ ・ ・ ・ ・ ・ ・ ・ ・ ・

The above "Memory Routi"
ng Table access 107 ", if the IP address is registered in the memory,
The address of the route information table corresponding to the IP address is accessed, and if the IP address is not registered, data indicating that the IP address is invalid is read.

On the other hand, in the "collation operation 108", the value of each bit position of the IPv bit sequence and the IPa bit sequence is E
Take the value of xplus OR (represented by $) and output the OR value of all bits of this value. Therefore, in this example, ***. *. ***. *: 1 * 0 *** 0 * .000000 **. *** 0 ****. ******* *… IPv ***. *. ***. *: 1 * 0 *** 0 * .000000 **. *** 0 ****. ********… IPa *** . *. ***. *: 0 * 0 *** 0 * .000000 **. *** 0 ****. ******** ... IPvＩＰIPa and OR of all bits The value is "0".

Next, in "route information determination 109", route information is determined based on the route information obtained from the route information table. However, the determined route information is valid only when it is determined that the predetermined condition is satisfied in “valid IP address determination 110”. Here, in the “valid address determination 110”, the “Memory Routing Table” is used.
A determination is made as to whether data indicating an invalid IP address has not been read out in “Access 107” and whether a match between the IPa bit string and the IPv bit string has been confirmed in “Collation operation 108”. Is made. In other words, the route information is valid only for "Me
more Routing Table Access 10
7), the desired route information is read out, and
This is only when the output value of the collation operation unit in the “collation operation 108”, that is, when the OR value of all bits is “0”.

Next, a description will be given of an embodiment in which the respective processes shown in FIG. 1 are divided into time-dependent stages, and the route information is determined by performing the processes of the sequentially received packets in the sequentially shifted stage. .

FIG. 2 is a diagram showing an example in which the processing shown in FIG. 1 is handled in five stages and executed in a pipeline. At each stage in this figure, the following processing is performed. First stage: extraction of transmission information (IP address, VPI) This corresponds to the “extraction of IP address 102” and the “extraction of VPI 103”. 2nd stage: Acquisition of r and a bit information and IPv bit string. This is the same as the "Memory VPI Table"
Access 104 ". Third stage: IPr, IPa bit string extraction. This corresponds to the above-described “cutout 105 of route information reference portion” and “cutout 106 of matching portion”. Fourth stage: Route management table access and IP address verification. This is described in the above "Memory Routin
g Table access 107 "and" collation operation 10 "
8 ". -Fifth stage: determination of validity / invalidity of transmission information and determination of route information. This corresponds to the “route information determination 109” and the “valid IP address determination”.

As shown in FIG. 2, these five steps are performed on the M-th packet received at a certain time as follows. First, the first step "extraction of transmission information (IP address, VPI)" is performed in N step (21
1) In the N + 1 step, the second stage "acquisition of r, a bit information, IPv bit string" is performed (212). Next, in the N + 2 step, the third stage “cutout of the IPr and IPa bit strings” is performed (213), and the N + 3 step is performed.
p, the fourth stage "route management table access and IP
Address collation "is performed (214). And N + 4 s
In the step, the fifth step “determination of validity / invalidity of transmission information and determination of route information” is performed (215), and the processing for the Mth received packet is completed.

On the other hand, for the next (M + 1) th received packet, the first to fifth processings (221 to 22) are performed.
5) is executed in steps (N + 1 step to N + 5 step) one step after the M-th packet. In other words, from the “transmission information (IP address, VPI) extraction 211” for the Mth received packet executed in N steps, the “transmission information (M + 1) received packet for the (M + 1) th received packet in N + 1 steps shifted by 1 step” IP address, VPI)
Extraction 221 ". At this time, the transmission information extraction unit in the circuit has completed the first-stage processing for the M-th packet, and thus can perform the first-stage processing for the (M + 1) -th packet.

Next, “r, a bit information, I” for the Mth received packet in the N + 1 step
From “Pv bit string acquisition 212”, “r, a bit information, IPv bit string acquisition 2” for the (M + 1) th received packet in N + 2 step shifted by 1 step
22 ". Also at this time, in the first memory or the like in the circuit, the second-stage processing for the (M + 1) -th packet can be performed because the second-stage processing for the M-th packet has been completed. is there.

Similarly, "extraction of bit sequence 223 of IPr and IPa" is N + 3 steps, and "route management table access and IP address collation 224" is N + 4.
Step and "determination of validity / invalidity of transmission information and determination of route information 225" are executed in N + 5 steps. As described above, the processing of each stage is executed for the (M + 1) th packet so as to follow the completion of the processing of each stage for the Mth packet.

Further, for the next (M + 2) received packet, the first to fifth processing (23
1 to 235), the next step (N + 2 step to 1 step) after the (M + 1) th packet for each step.
N + 6 step). That is, this M + 2
The processing of each stage for the Nth packet is executed after the completion of the processing of each stage for the (M + 1) th packet.

As described above, the internal processing of the route search and the determination of the validity / invalidity of the transmission information can be executed in a pipeline manner. Also, each internal process does not have the content of a process that loops back, and it is unlikely that the pipeline process will be stuck at some stage.

[0040]

As described above, the processing progress of the route information search circuit according to the present invention is performed again, especially by accessing the same memory many times for each transmission information or using the information obtained by the access. There is no need to return to processing. As a result, access to the memory storing the routing table can be performed only once, and the effect of increasing the speed of route information retrieval can be obtained.

Further, such one-sided processing can be executed in a pipeline manner in the route information search circuit according to the present invention. Therefore, even if the transmission destination information is sent in a concentrated and continuous manner, the processing can be performed without storing the transmission information.

[Brief description of the drawings]

FIG. 1 is a diagram showing a route information search circuit according to an embodiment of the present invention by a function over time.

FIG. 2 is a diagram illustrating an example of a case where the processing illustrated in FIG. 1 is handled in five stages.

[Explanation of symbols]

101 START 102 Extraction of VPI, extraction of IP address 104 Memory VPI Table access 105 Extraction of path information reference part (IPr bit string) 106 Extraction of matching part (IPa bit string) 107 Memory Routing Table access 108 Matching operation (IPa bit string and IPr bit string) 109 Route information determination 110 Valid IP address determination 111, 112 END 211 Extraction of transmission information (IP address, VPI) for Mth received packet 212 r, a bit information, IPv bit string for Mth received packet 213 IPr for the Mth received packet,
Extraction of IPa bit string 214 Route management table access and IP address collation operation for Mth received packet 215 Validity / invalidity determination of transmission information and determination of route information for Mth received packet 221 M + 1st reception Extraction of transmission information (IP address, VPI) for the received packet 222 r, r for the (M + 1) th received packet
Acquisition of a-bit information and IPv bit sequence 223 M + 1
Extraction of r, IPa bit string 224 Access to route management table and IP address collation operation for M + M first received packet 225 Determination of valid / invalid transmission information and determination of route information for M + M received first packet 231 M + 2 Extraction of transmission information (IP address, VPI) for the received packet 232 M + r, r, for the second received packet
Acquisition of a-bit information and IPv bit string 233 M + IP of second received packet
Extraction of r, IPa bit string 234 Access to route management table and IP address collation for M + 2nd received packet 235 Determination of validity / invalidity of transmission information and determination of route information for M + 2nd received packet

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Hiroshi Watanabe 3-19-2 Nishi-Shinjuku, Shinjuku-ku, Tokyo Inside Nippon Telegraph and Telephone Corporation (72) Inventor Hiroyuki Fujiwara 3- 192-1 Nishishinjuku, Shinjuku-ku, Tokyo No. Japan Telegraph and Telephone Corporation

Claims (3)

[Claims] 1. A route information search circuit in a communication apparatus for comparing transmitted sent destination information with a table for managing route information and searching for and determining route information, comprising: And extracting a bit serving as a physical address in the memory in which the table is written, and accessing the memory based on the address. 2. The route information search circuit according to claim 1, wherein a bit which is a matching part common to registered transmission destination information and is necessary for collation is cut out from the transmitted transmission destination information. A route information search circuit, comprising: a circuit for determining whether or not the information is registered. 3. A route information search circuit according to claim 1, wherein internal processes in the route information search circuit according to claim 1 or 2 are sequentially performed in a pipeline manner.