JP2000244570A - Network relay device and network relay method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To perform high-speed routing while guaranteeing high communication quality (QoS), high reliability, and security. A transfer engine stores a packet received via a network interface unit in a packet buffer, and stores header information in a header RAM.
To memorize. The search engine 14 searches for transfer control information such as transfer destination information and action information based on the header information, and writes the search control information into the header RAM 11. The transfer engine 13 creates an output packet based on the information stored in the packet buffer 12 and the header RAM 11, and outputs it to the transfer destination. The switch unit 20 switches the output packet to the destination routing processing unit 10. Header RA
The M11 can perform high-speed access independently of the packet buffer 12 asynchronously, and suppresses access competition between the transfer engine 13 and the search engine 14.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] The present invention relates to a network relay device and a network relay method. The present invention particularly relates to a network relay device and a network relay search method capable of searching a transfer destination of an input packet at high speed in a network relay device such as a router in a computer network system.

[0002]

2. Description of the Related Art Generally, in a network system, a network relay device such as a router or a bridge is used to connect a plurality of networks. The router determines the destination of the packet by checking the destination address of the packet received from the connected network or subnet, and transfers the packet to the network or subnet to which the destination router or host is connected.

FIG. 13 shows a configuration diagram of a conventional network relay device. In the figure, the router 100 includes a routing control unit (RM) 110, a router bus 120, a network interface unit (NIF) 130, a port 140, and the like. Each port 140 is connected to an appropriate network 150.

[0004] The network interface unit 130
A packet is received from the network connected to the port 140, and the received packet is transmitted to the routing control unit 110 via the router bus 120. The routing control unit 110 includes a routing table that holds routing information, and uses the routing information to change the destination of the packet received from the destination network 15 to the destination network 15.
0 is determined, and the packet is transmitted to the network interface unit 130 of the port 140 to which the network 150 is connected. Network interface unit 130 that has received a packet from routing control unit 110
Sends the packet to the transfer destination network 150. The routing control unit 110 updates and maintains the routing information stored in the routing table based on the header information of the received packet, and has a function of managing the entire router 100.

Here, a description will be given of a route search process for searching for an address to be transferred next and a port to output the packet when the router receives the packet. Normal,
For the route search, a route search table (routing table) created from configuration definition information, information obtained by transmission / reception between routers, and the like is used. The routing table is used to search for an output port, a next hop address, information as to whether or not the network is directly connected (next hop information), and the like, using a set of a network address and a network mask length as a search key. It is a table.

Another conventional technique is disclosed in Japanese Patent Application Laid-Open No. 05-2005.
Japanese Patent Application Publication No. 199230 (see US Pat. No. 5,434,863) describes an internetwork apparatus and a communication network system which can flexibly respond to the scale of a network without impairing the high-speed routing processing. I have. In this device and system, a router management unit and a plurality of routing accelerator modules for performing routing are connected by a high-speed bus. A plurality of communication ports are connected to each routing accelerator independently of each other. According to such prior art, high-speed routing is enabled by a plurality of routing accelerators,
Further, by adding a routing accelerator, it is possible to easily cope with a small to large network.

[0007]

In recent years, the need for dynamic routing for dynamically generating, adding, changing, and deleting relay information for routing processing while recognizing the configuration of the network during network operation has increased. Is coming. That is, the router uses a routing protocol (for example, RI in the TCP / IP protocol group) for exchanging information about the network between the routers.
P: Routing Information Protocol or OSPF: Open S
hortest Path First). Further, a network management protocol for communicating management information such as performance information of the router itself with a management master station on a network (for example, SNMP: Simple Network Management Protocol in the TCP / IP protocol group).
In the processing of ocol, etc., the means for performing routing in the conventional example must also be used, so that the original relay performance cannot be sufficiently exhibited. Therefore, it is difficult for the conventional router to cope with a high-speed line such as a high-speed LAN (Local Area Network), a broadband ISDN, and an ATM (Asynchronous Transfer Mode) that have recently emerged.

Further, in the router according to the prior art, since there is only one means for performing routing, routing processing becomes a bottleneck, and the number of ports that can be supported and communication traffic are limited. Therefore, it is difficult to smoothly expand the configuration of the router port menu and the like from small to large, and to improve the performance according to the traffic and the number of ports.

[0009] With the recent speeding up of networks, data processing devices used for routers and bridges have
It is also necessary for the network controller to read the transmission packet from the memory and write the reception packet to the memory at high speed. Furthermore, considering memory access conflicts with the processor, conventionally, in order to absorb the performance degradation caused by memory access conflicts, the number of network controllers that can be mounted is limited or the cost is inefficient. There is
A high-speed memory device or a dual-port memory that can be accessed asynchronously from a processor or a network controller has to be used.

[0010] The router is connected to a plurality of networks and relays packets without connection. For this reason, packets may be concentrated in the router, and conventionally, QoS such as bandwidth control, priority control, discard control, etc.
(Quality of Service, service quality) cannot be guaranteed (specifically, for example, a band cannot be guaranteed, a packet cannot be delivered within a specified time, and the like).

SUMMARY OF THE INVENTION In view of the above, it is an object of the present invention to provide a network relay apparatus and method for performing high-speed routing while guaranteeing high communication quality (QoS), high reliability, and security. In addition, the present invention provides a network relay device and a method that have high applicability and expandability, can respond to various lines and various scales, and can easily improve system performance. Another object of the present invention is to provide a network relay device and a method capable of increasing the types of protocols that can be processed and enabling easy connection with existing devices.

A further object of the present invention is to execute a search such as a route search at a high speed by dividing a storage device and using a high-speed memory for a part thereof. The present invention limits the number of network controllers that can be installed,
An object of the present invention is to improve packet processing capability by suppressing access competition of a memory storing a packet without using a memory device with a higher speed or a dual-port memory device than necessary.

[0013]

According to a first aspect of the present invention, there is provided a network relay device for connecting a plurality of networks and outputting a packet input from the network to a next transfer destination based on path information. A network interface unit that is connected to a network and controls an interface with the network, has a packet buffer and a high-speed read / write header memory, is connected to one or a plurality of the network interface units, A routing processing unit for routing a packet input from the interface unit, a routing management unit for managing the inside of the device, and a connection unit for connecting the routing management unit and each of the plurality of routing processing units; Network interface The source unit outputs an input packet from the network to a first routing processing unit to which the first network interface unit is connected, and the first routing processing unit stores the input packet in a packet buffer and By storing header information about an input packet in a header memory and accessing the header memory, a transfer destination of the input packet stored in the packet buffer is searched based on the stored header information, and An output packet is created based on the stored input packet and the header information stored in the header memory, and when the route to the searched transfer destination passes through another routing processing unit, the output packet is output to the connection unit. , The connection unit outputs an output packet from the first routing processing unit. , It provides a network relay apparatus that transmitted to the second routing processor of the retrieved destination.

According to a second solution of the present invention, a network interface unit connected to a network,
A routing processing unit for routing a packet input from the network interface unit; a routing management unit for managing the inside of the device; and a connection unit for connecting each of the routing management unit and the plurality of routing processing units. In a network relay device, a network relay method for outputting an input packet input from a network to a transfer destination, wherein a first network interface unit is connected to the first network interface unit for input packets from the network. A first routing processing unit that stores the input packet in a packet buffer, and outputs a header information relating to the input packet at a high speed readable and writable independently of the packet buffer; Memory, and by accessing the header memory, searches for the transfer destination of the input packet stored in the packet buffer based on the stored header information, and stores the input packet and the header stored in the packet buffer. An output packet is created based on the header information stored in the memory, and if the route to the searched transfer destination passes through another routing processing unit, the output packet is output to the connection unit. 1
The output packet input from the routing processing unit of
There is provided a network relay method adapted to transmit the searched transfer destination to a second routing processing unit.

[0015]

FIG. 1 shows a configuration diagram of a network relay device according to the present invention. In this figure, router 1
Is a routing processor (RP, Routing Processor)
10, switch section (CS, Crossbar Switch) 20, network interface section (NIF, Network Interface)
ce) 30, port 40, routing management unit (RM, Ro
utingManager) 60, power supply (PS, Power Supply) 70
Etc. are provided. Each port 40 is connected to an appropriate network 50
Connected to. Examples of the network 50 include a LAN such as Ethernet, a WAN, and an ATM. In order to improve the reliability of the device, the power supply 70 and the common unit can be appropriately duplicated.

The functions for routing control are divided into a routing processing unit 10 for executing a routing function and a routing management unit 60 for managing the router 1.
Further, the router 1 includes a routing processing unit 10 having one or more network interface units 30.
Are provided. The routing management unit 60 has a management function for the entire router 1, executes a route calculation process, transmits and receives routing information to and from other routers, and sends routing information to each routing processing unit 10 in the router. Distribute. Here, the routing management unit 60 adopts a duplex configuration. The switch unit 20 includes a switch such as a crossbar switch, and is provided between the routing processing units 10 or between the routing processing units 1.
0 and the routing management unit 60 perform communication and exchange. Here, the switch unit 20 adopts a duplex configuration. Note that a connection may be made by a bus or the like instead of the switch unit 20. When a crossbar switch is used, the routing management unit 60 and the plurality of routing processing units 1
A plurality of sets can transmit and receive at the same time without occupying the connection path by one set of 0s.

The routing processing unit 10 performs packet transfer by the connected network interface unit 30. When transferring a packet to the network 50 connected to another routing processing unit 10, the routing processing unit 10 transfers the packet to the corresponding routing processing unit 10 via the switch unit 20. The routing processing unit 10 is designed so that each function operates at a high speed by a hardware configuration. Routing processing unit 1
0 is more specifically, for example, switching processing, route search, forwarding, filtering, Qo
It has functions such as S and IP multicast. The routing processing unit 10 includes the ports 40 of the network interface unit 30 in the routing processing unit 10 itself, the other routing processing units 10, and the routing management unit 60.
And the like are provided with an input buffer and an output buffer as appropriate. The network interface unit 30 has one or a plurality of ports 40 and controls an interface between the network 50 and the routing processing unit 10.

FIG. 2 is an explanatory diagram of the operation of the network relay device showing the internal configuration of the routing processing unit. The route search and the operation of transferring the packet to the destination obtained as a result of the route search will be described with reference to the internal configuration diagram of the routing processing unit 10 using this figure. The routing processing unit 10 includes a transfer engine 13, a search engine 14,
Header RAM 11, packet buffer 12, route table 15, ARP table (address search table) (AR
P, Address Resolution Protocol) 16, Filter / Q
An oS table (flow search table) 17 is provided. The transfer engine 13 performs, for example, packet input / output processing. The search engine 14 mainly performs flow search processing such as path search processing and QoS control based on packet header information. The search engine 14 uses a dedicated LSI or the like,
It is composed of hardware capable of high-speed processing.

The packet buffer 12 includes the transfer engine 1
The input packets are stored until the packet 3 is transferred to the routing processing unit 10.
The header RAM 11 extracts and stores only the header of the input packet. The header RAM 11 reads /
Use a memory with a high writing speed. In this embodiment, a header RAM 11 that can be accessed asynchronously with a packet buffer 12 is provided separately from a buffer memory that stores a packet received from a network or a packet transferred from another data processing device. At the same time, the header of the packet is also stored (copied) in the header RAM 11.
Each processor such as the transfer engine 13 and the search engine 14 uses the header RAM 11 to fetch the header portion of the packet, and while analyzing the header portion, can read and write the packet from and to the packet buffer 12. A parallel operation such as a header analysis process and a transfer process of another packet is achieved.

Therefore, while the processor of the search engine 14 is reading the header information from the header RAM 11, the packet buffer 12 is not used by the processor, so that the transfer engine 13 can access the packet for transmission or transfer. Access competition between the engine 14 and the transfer engine 13 for the packet buffer 12 can be prevented. The area for storing the packet received from the network side and its header part and the area for storing the transfer packet from the switch part 20 and its header part may be different from each other. Such a separate configuration facilitates packet management.

The route table 15, the ARP table 16, and the filter / QoS table 17 are configured by being independently divided. Thereby, search engine 1
4 accesses each table individually and performs reading or writing, so that routing information, QoS, and the like can be searched at high speed. Further, pipeline processing can be executed to realize high-speed routing processing. Details of each table and pipeline processing will be described later.

FIG. 3 is a sequence diagram showing an outline of the operation of the network relay device. First, when a packet is input to the first network interface unit 30 from a network via a port, the first network interface unit 30 transmits the packet to the transfer engine 13.
The transfer engine 13 stores the received packet in the packet buffer 12. The transfer engine 13 extracts only the header of the input packet, adds an internal header to form header information, and stores the header information in the header RAM 11. The internal header will be described later.

The search engine 14 accesses the header RAM 11 and reads out header information. Note that the transfer engine 13 may transmit the header information stored in the header RAM 11 to the search engine 14. The search engine 14 uses the header information to determine the destination router / R
Information about the next transfer path, such as each P or port number or address, MAC address, and the like, and information about communication quality control, such as QoS control information, are retrieved as appropriate. The search engine 14 writes in the header RAM 11 transfer control information including transfer destination information such as each searched number and address information and action information such as QoS information. Note that the search engine 14 may transmit the transfer control information to the transfer engine 13.

In the transfer engine 13, based on the packet stored in the packet buffer 12 and the header information (including the transfer control information) stored in the header RAM 11,
Create an output packet. And the transfer engine 13
Outputs the created output packet to the transfer destination. At this time, if the transfer route belongs to another routing processing unit 10, the transfer engine 13 queues the transfer route in a buffer for the corresponding other routing processing unit 10,
If it belongs to the network interface unit 30 of its own routing processing unit 10, it is queued in the buffer of the corresponding port 40.

It should be noted that the number of transfer routes searched by the routing processing unit 10 is not limited to one, and a plurality of routes may be used for the broadcast transfer to each route. In this case, the data is queued in an appropriate buffer for each of the plurality of paths.

The detailed configuration and operation of the routing processing unit will be described below. First, each memory will be described. FIG. 4 is an explanatory diagram of the packet buffer 12 and the header RAM 11.

FIG. 4A shows an example of the format of a packet stored in the packet buffer 12. The packet is input to the packet buffer 12 from the network 50 or the switch unit 20 or the like. The format of this packet is, for example, an IP packet,
An AC header 401 is added. The IP packet includes, for example, a layer 3 IP header 402, a layer 4
-Includes header 403 and payload 404.

The layer 2 MAC header 401 includes, for example, a source MAC address (SourceAddress Media Access Control, SAMAC) which is a physical address (hardware address) of a router which immediately transmitted a packet,
Destination MAC address, which is the physical address of the router that will receive the packet next
Control, DAMAC). The layer 3 IP header 402 includes a source IP address (Source IP Address: hereinafter referred to as “SI”) which is a source address (address of the transmission terminal).
P ". ) And a destination IP address (Destination IP Addres)
s: Hereinafter referred to as “DIP”. ). The layer 4 header 403 includes a source port (Source Port: hereinafter referred to as “SPORT”) indicating a protocol (= upper application) and a destination port (Destination Port: hereinafter “DPOR”).
T ". ). Payload 404 includes user data. As each header, information such as a TOS (Type of Service) indicating priority and an upper protocol of the IP protocol may be stored in addition to the above-mentioned headers.

FIG. 4B shows an example of the format of the header information stored in the header RAM. The header information is, for example, the layer 2M in the packet format.
In the AC header 401 and the layer 3 / IP header 402,
An internal header 405 is added as control information. The internal header 405 includes, for example, an input line number,
It has an output line number, QoS control information, and the like. In the internal packet format inside the router, an internal header 405 is added to the format of the network packet. At that time, an internal packet can be formed by the information stored in the packet buffer 12 and the information stored in the header RAM 11. Further, the internal packet may be stored in the packet buffer 12 in the format of the internal packet format including the internal header 405, and the internal packet may be transferred from the information of the packet buffer 12 alone. Further, transfer control information such as transfer destination information and action information searched by the search engine 14 can be written in the internal header 405.

Next, FIG. 5 is an explanatory diagram of each table used for the route search. As shown in FIG. 5A, each entry of the routing table 15 includes, for example, a destination IP address 501, an IP address 502 of the next router, a transmission RP number 503 of the own router, a transmission port number 504, and the like. As shown in FIG. 5B, each entry of the ARP table 16 includes, for example, an IP address 502 of the next router, a MAC address 506 of the next router, and the like. Further, as shown in FIG. 5C, each entry of the filter / QoS table 17 includes, for example, an IP header / layer 4
A header value (range) 507 and an action 508 are included. Here, the action 508 includes a filter that is a process of passing or discarding, a tunnel that is a process of encapsulating or not encapsulating, a QoS, and the like. Particularly, QoS will be described later.

FIG. 6 is an explanatory diagram of the high-speed processing by the routing processing unit. With reference to this figure, a description will be given of a method of realizing packet transfer capable of following a high-speed line speed such as gigabit. Here, parallel processing / pipelining of routing processing realizes high-speed processing. The operation will be described below with reference to the formats shown in FIGS.

The routing process mainly includes a reception process,
It is divided into input search processing, output search processing, and transmission processing. First, in the receiving process, the transfer engine 13 receives a received packet from the network interface unit 30. As described above, the packet buffer 12 stores an input packet or a packet in an internal packet format to which an internal header is added. Further, an internal header 405 is added to the layer 2 MAC header 401 and the layer 3 IP header 402 of the input packet to make header information, and the header information is stored in the header RAM 11. The header RAM 11 can read and write at high speed independently of the packet buffer 12, and by storing only the header information, the storage capacity can be reduced and the processing can be performed at higher speed. The search engine 14 can access the extracted header information at an appropriate timing.

Next, in the input search processing, the search engine 14 extracts the layer 3 IP header 402 from the header information.
The destination IP address inside the router is extracted, and based on this address, the IP address 502 of the next router, the transmission RP number 503 and the transmission port number 504 of the own router are searched by referring to the routing table 15. Furthermore, search engine 1
4 is a layer 3 IP header 4 based on the received header information.
02 and the comparison information such as the layer 4 header 403 and the like, referring to the filter / QoS table 17, and
, Etc. on the input side. These input side filter / QoS search and route search can be performed in parallel because each table is provided separately.

Next, in the output search process, the search engine 14 determines the IP address of the next router determined in the input search process.
The address is extracted, and based on this address, the MAC address 506 of the next router is searched by referring to the ARP table 16 and the various actions 508 on the output side such as QoS are searched by referring to the filter / QoS table 17. I do. These output side filter / QoS search and circuit table / ARP search can be executed in parallel because each table is provided separately. The transfer control information including the transfer destination information such as the number and address information regarding the next transfer destination and the action information such as the QoS control information is stored in the header RAM 11. The transfer control information can be appropriately written in, for example, the internal header 405 or another position in the header information.

Next, in the transmission process, the header information including the transfer control information retrieved by the output retrieval process is transferred to the header RA.
Read from M11, header information and packet buffer 1
2, the output packet is created and queued in a buffer for the network interface unit 30 or another routing processing unit 10 or the routing management unit 60.

FIG. 7 shows an example of a configuration diagram of a search engine using hardware. The search engine 14 can search, for example, a tree structure search for necessary data for each table such as the route table 15, the ARP table 16, the filter / QoS table 17, and the like. Here, as an example of the processing unit of the search engine 14 configured by hardware, a path search processing unit for searching a transfer destination path using the path table 15 will be described.

The path search processing section 213 includes a tree structure search circuit 2130, a read address generation circuit 2131, and a path search processing control circuit 2132. The tree structure search circuit 2130 searches for a 2 p-th tree structure stored in each table such as the path table 15, generates a pointer of a node to be read next, and checks the check bit value of the destination IP address of the received packet. It performs extraction, determines the end of the tree structure search, updates route information candidates as search results, and the like. Further, the read address generation circuit 2131 includes a tree structure search circuit 213.
According to the pointer to the node to be read output from 0 and the check bit value, the memory address of a part of the word of the node to be actually read is generated. The path search processing control circuit 2132 controls the entire path search processing unit 213 (operation timing and operation state management of each circuit).
I do.

Next, the operation of the route search processing section 213 will be described. The tree structure search circuit 2130 includes a header RAM
11 receives the destination IP address of the received packet,
A pointer to the next node is generated from the destination IP address and the value of the mask length of the node, and passed to the read address generation circuit 2131. Also, the tree structure search circuit 2130
The value of the check bit position (check bit value) of the destination IP address indicated by the mask length of the node is extracted and passed to the read address generation circuit 2131.

The read address generation circuit 2131 generates a memory address at which node data to be read is stored, using the pointer to this node, the check bit value, and the timing signal from the path search processing control circuit 2132. The memory control circuit 2132 generates a memory control signal using the memory address and the timing signal from the path search processing control circuit 2132, and transfers the signal to the path table 15. The path table 15 that has received the above memory control signal transfers the corresponding node data to the tree structure search circuit using the signal line 215.

The tree structure search circuit 2130 performs a search using this node data, and when it is determined that the tree structure search is to be ended, a tree structure search end signal is sent to the path search processing control circuit 2130.
132, the path search processing control circuit 2132 checks the entry presence flag of the path information held in the tree structure search circuit 2130, and if the value is 0, terminates the path search processing; 13 etc. is notified that there is no search result. When the value of the entry presence flag is 1, the route information is output, the search process is terminated, and the control of the next packet process is performed.

FIG. 8 is an explanatory diagram of high-speed processing by pipeline control. As shown in the figure, the processing of reception processing, input search, output search processing, and transfer processing is processed in a pipeline, and control is performed so that each processing unit always operates, thereby speeding up the routing processing. it can. Here, further, in input search, input filter processing (input filter / QoS search)
And the routing table search (route search) is executed in parallel.
Also, output search processing, output filter processing (output filter / QoS search), and output circuit table search (output circuit table / A
RP search) in parallel. The pipeline configuration is not limited to this diagram, and can be executed in an appropriate order.

In the pipeline processing, when the processing unit 1 of the above-described processing units completes the processing 1 of the entry N, the processing unit 2 that performs the processing 2 after the processing 1 becomes the processing 2 of the entry N.
Processing unit 1 determines whether entry N +
1 is started. By performing such a pipeline process, the time for processing the entry N becomes the time for one process, and the processing speed is quadrupled. In the example above,
The flow search is divided into four processes and pipeline processing is performed. However, if the process is divided into P processes and pipeline processing can be performed, the performance will be P times higher.

Next, FIG. 9 is an explanatory diagram of the flow search processing. Generally, network relay devices such as routers
Since the connection is not set in advance, the ATM switch does not have the connection information table or the QoS control information in the connection information table (packet type communication). Therefore, in order to perform QoS control in the router, a flow search means for searching for QoS control information based on information in a header or the like for each input packet is required in addition to the priority transfer function similar to the ATM exchange. Here, as an example, the priority transfer function is applied to the searched QoS control information by the flow search means. Here, a packet identification condition created by combining information such as information in a header is called a flow condition, a series of traffic that matches the flow condition is called a flow, and an input packet matches the flow condition. Detecting the action information such as the QoS control information and the transfer enable / disable information by judging whether or not the information is referred to as flow search.

In this embodiment, the QoS control is provided in the input-side routing processing section 10-1 and the output-side routing processing section 10-2, respectively, and the switch section 20 is provided.
Has a QoS function. The input routing processing unit 10-1 includes a filter flow search 911, a tunnel flow search 912, and a QoS flow search 913 as input search flows. Similarly, the output routing processing unit 10-2 includes a filter flow search 921, a tunnel flow search 922, and a QoS flow search 923 as output search flows. The switch unit 20 has a QoS function by providing an arbitration function for selecting an order of transmission according to the priority. In addition,
The switch unit 20 can also include a filter flow search, a tunnel flow search, and a QoS flow search similarly to the routing processing units 10-1 and 10-2.

In the filter flow searches 911 and 921, it is determined whether the packet is passed or discarded.
In the tunnel flow searches 912 and 922, it is determined whether or not to encapsulate the packet.
Perform encapsulation software processing.

In the QoS flow search 913 and 923,
For example, there are packet priority control, discard control, band control, and the like. The priority control is a control that preferentially transmits data with high importance, real-time data, and the like. Discard control is used when there is a lot of traffic or when a failure occurs.
This is a control for preventing loss of important data by discarding data of low importance. Also, bandwidth control is
This is control for dividing the inside of a line into a plurality of bands or changing the bandwidth. For example, by controlling traffic using a matrix of a priority class and a discard class, priority and discard control can be performed. In this case, depending on the priority class, for example, control can be performed such that HNA / SNA, voice, moving image, and the like have a small delay and FTP, mail, WWW web, and the like have a large delay. Further, according to the discard class, for example, it is possible to control the control packet so as to reduce the discard rate, and to control the voice and the moving image to increase the discard rate.

Next, the QoS control in the switch unit 20 will be described. The packet sent from the routing processing unit 10 includes QoS control information in the control information. In the switch unit 20, especially on the output side,
Priority control or the like based on the QoS information is performed. Actually, for example, control can be performed by providing output control with a queue for each priority. Thereby, communication and transfer with higher quality can be performed.

FIG. 10 is an explanatory diagram of the flow search table. This flow search table is based on the filter / Q
This corresponds to the oS table 17. Here, as an example, as shown in the figure, as the comparison field 101, the transfer source IP address, the destination IP address, the packet length, the IP priority, the IP upper protocol, the delivery confirmation flag, the transfer destination TCP / UDP port, the destination TCP / UDP
Including ports. The action field 102 stores a filter (pass / discard), a tunnel (encapsulation / non-encapsulation), and QoS (delay class, discard class, band, etc.).

Next, a specific method of QoS flow search will be described. Here, the QoS flow search will be described as an example, but a filter flow search or a tunnel flow search can be similarly performed. It should be noted that the control information of each of these flows may be mixed and stored in the action field 102,
A flow search table may be provided for each flow.

First, the linear search method will be described. When judging the QoS control information of a packet as one of the actions, predetermined entries are read in order from the top of the entry table. Then, it is determined whether or not all the valid flow conditions in the comparison field 101 of the entry and the value of the header portion of the packet match. In addition,
Action field 1 in entry if matched
02 is determined as the QoS control information of the packet, and the QoS flow search ends. When a case that matches the flow condition is searched, the action field 10
2 is determined as the QoS control information, and the flow search is terminated without executing the search for the next entry.

In the above-described linear search method, it may be difficult to execute QoS control and filtering at high speed in a network in which a large number of entries are set. Therefore, in the flow search method according to the present embodiment, even when a large number of entries are set, it is preferable to adopt an input line limitation method or the like that can perform a flow search faster than the linear search method. Hereinafter, an outline of the input line limiting method will be described. In the input line limiting method, only the entry that matches the input line number that forms the comparison field of the linear search method is searched to increase the speed.

FIG. 11 is an explanatory diagram of the first input line limiting system. In the first input line limiting method, an entry 511-i in which the input line number and the input line number valid bit are deleted from the comparison field of the linear search method is set for each input line. The flow condition unit 521-i includes:
For example, the condition for identifying the source or destination user is SI
P and DIP upper and lower limits, SIP upper limit 501, SIP lower limit 502, DIP upper limit 503, DIP lower limit 504, SI
An IP valid bit 562 indicating that the upper and lower limits of P and DIP are valid, a SPORT 505 as a source port,
DPORT 506 which is a destination port, and SPORT 505 and DP
Port valid bit 5 indicating that ORT 506 is valid
63 and the like. The QoS control information section 530-i includes, for example, QoS control information used in the priority transfer function.
S control information 507 is included. Since only the entry 511-i whose input line number matches the flow condition is searched, the input line number is not required in the entry 511-i. At the time of the flow search, only the entry 511-i assigned to the input line to which the packet is input is searched.

Here, in the above-mentioned first input line limiting method, an entry 511-i irrelevant to the input line number is set (for example, "Teln input from all input lines").
In this case, it is necessary to set the number of input lines (= N) in the entry 511-i, and the efficiency of the memory for implementing the entry table may be reduced. Therefore, an even faster input line limiting method will be described below.

FIG. 12 is an explanatory diagram of the second input line limiting system. In the second input line limitation method, a list 540 that is an address of the entry table 750 is set in the list table 760 for each input line. For example, the list 540-11 having the list table address “1” is the address of the entry 511-1, and the list 540-12 having the list table address “2” is the entry 51.
1-H. At the time of the flow search, only the list 540 assigned to the input line to which the packet is input is read, and the entry 511-i to which the list 540 points is read. List 540 with small bit width
(For example, about 10 bits even when having 1024 entries) for each input line, and sharing the entry 511-i having a large bit width with each input line, the memory for realizing the entry table can be used effectively. it can. Therefore, while realizing high-speed operation, a large number of entries 511-
i can be set.

Another embodiment of the flow detection system is an output line limitation system. In the output line limitation method, only the entry 511-i having the same output line number as the flow condition is processed in the same manner as the above-described input limitation method, thereby realizing high-speed flow detection. In addition, there is a SAMAC limited system in which SAMAC is used as a flow condition instead of the input line number in the header information. In the SAMAC limitation method, a flow search can be executed in the same manner as the above-described input limitation method by defining a SAMAC group, which is a SAMAC group, and limiting entries with a SAMAC identifier, which is an identifier of the SAMAC group.

[0056]

As described above, according to the present invention, it is possible to provide a network relay apparatus and method for performing high-speed routing while ensuring high communication quality (QoS), high reliability, and security. Further, according to the present invention, it is possible to provide high applicability and expandability, to support various lines and various scales, and to easily improve the system performance. Further, according to the present invention, the types of protocols that can be processed are increased, and connection with existing devices can be facilitated.

Further, according to the present invention, a search such as a route search can be executed at a high speed by dividing a storage device and using a high-speed memory for a part thereof. According to the present invention, without restricting the number of network controllers that can be originally mounted or using an unnecessarily high-speed memory device or a dual-port memory device, access competition of a memory storing a packet is suppressed, Packet processing capability can be improved. Further, according to the present invention, the processor of the search engine stores the header information in the header R
While reading from the AM, the packet buffer is not used by the processor, so that the transfer engine can access the packet for transmission or transfer, so that the search engine and the transfer engine do not compete for access to the packet buffer. can do.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a network relay device according to the present invention.

FIG. 2 is an operation explanatory diagram of a network relay device showing an internal configuration of a routing processing unit.

FIG. 3 is a sequence diagram of an operation outline of the network relay device.

FIG. 4 is an explanatory diagram of a packet buffer and a header RAM.

FIG. 5 is an explanatory diagram of each table used for a route search.

FIG. 6 is an explanatory diagram of a speed-up process by a routing processing unit.

FIG. 7 is a configuration diagram of a search engine using hardware.

FIG. 8 is an explanatory diagram of high-speed processing by pipeline control.

FIG. 9 is an explanatory diagram of a flow search process.

FIG. 10 is an explanatory diagram of a flow search table.

FIG. 11 is an explanatory diagram of a first input line limiting system.

FIG. 12 is an explanatory diagram of a second input line limiting system.

FIG. 13 is a configuration diagram of a conventional network relay device.

[Explanation of symbols]

 Reference Signs List 1 network relay device 10 routing processing unit 20 switch unit 30 network interface unit 40 port 50 network 60 routing management unit

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Takeshi Aimoto 1-280 Higashi-Koigabo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd. (72) Takemi Yazaki 1-280 Higashi-Koigabo, Kokubunji-shi, Tokyo Hitachi Central Research Laboratory (72) Inventor Nobuhito Matsuyama 1 Horiyamashita, Hadano-shi, Kanagawa Prefecture Inside Nichi Information Technology Co., Ltd. (72) Inventor Yoshito Sako 1 Horiyamashita, Hadano-shi, Kanagawa Prefecture Inside General-purpose Computer Business Division, Hitachi Ltd. (72) Inventor Tomohiko Tabe 1 Horiyamashita, Hadano-shi, Kanagawa F-term, General-purpose Computer Division, Hitachi, Ltd. F-term (reference) KK56 LL01 LL03 LL09

Claims (6)

[Claims] 1. A network relay device for connecting a plurality of networks and outputting a packet input from the network to a next transfer destination based on path information, the network relay device being connected to the network and controlling an interface with the network. A routing interface that has a packet buffer and a high-speed readable and writable header memory, is connected to one or more of the network interface units, and performs routing of packets input from the network interface unit. A routing management unit that manages the inside of the device; and a connection unit that connects each of the routing management unit and the plurality of routing processing units. The first network interface unit receives an input packet from a network. The first network interface unit is connected to a first routing processing unit, and the first routing processing unit stores the input packet in a packet buffer and stores header information on the input packet in a header memory. Then, by accessing the header memory, a transfer destination of the input packet stored in the packet buffer is searched based on the stored header information, and the input packet stored in the packet buffer and stored in the header memory. An output packet is created based on the header information obtained, and when the route to the searched transfer destination passes through another routing processing unit, the output packet is output to the connection unit. The output packet from the processing unit is transferred to the second routing process of the searched transfer destination. Network relay device for transmitting to the control unit. 2. The method according to claim 1, wherein the first routing processing unit transfers the output packet to the route of the network interface unit connected to the own routing processing unit when the searched route to the transfer destination passes through the own routing processing unit. The network relay device according to claim 1, wherein the output is output to a connected port. 3. The second routing processing unit stores an input packet from the connection unit in a packet buffer, stores header information on the input packet in a header memory, and accesses the header memory, Based on the stored header information, search for a transfer destination of the input packet stored in the packet buffer, and create an output packet based on the input packet stored in the packet buffer and the header information stored in the header memory And outputting the output packet to a port connected to the path of the network interface unit connected to the own routing processing unit.
Or the network relay device according to 2. 4. The routing processing unit according to claim 1, further comprising a transfer engine independently configured by hardware for performing packet reception and transmission processing, and independently configured by hardware for performing route search processing. A search engine, wherein the transfer engine stores an input packet received from the network interface unit or the connection unit in the packet buffer, and stores header information regarding the input packet in the header memory. Searching for transfer destination information according to the header information received from the header memory, writing the searched transfer destination information to an internal header of the header memory, the transfer engine stores the input packet and the header stored in the packet buffer. Output packet is determined by the header information stored in the memory. Form, the network relay device according to any one of claims 1 to 3 outputs packets and outputs to the connection or the network interface unit. 5. The routing processing unit according to claim 1, wherein the routing processing unit searches a plurality of routes as transfer destinations, and broadcasts an output packet to each of the searched routes. Network relay device. 6. A network interface unit connected to a network, a routing processing unit for routing a packet input from the network interface unit, a routing management unit for managing the inside of the device, the routing management unit and a plurality of A network relay device comprising: a connection unit for connecting each of the routing processing units; and a network relay method for outputting an input packet input from the network to a transfer destination, wherein the first network interface unit comprises: To the first routing processing unit to which the first network interface unit is connected, the first routing processing unit stores the input packet in a packet buffer, and outputs a header related to the input packet. Information is stored in a header memory that can be read and written at high speed independently of the packet buffer. By accessing the header memory, a transfer destination of an input packet stored in the packet buffer is stored based on the stored header information. , And creates an output packet based on the input packet stored in the packet buffer and the header information stored in the header memory. If the route to the searched transfer destination passes through another routing processing unit, A network relay method for outputting a packet to the connection unit, wherein the connection unit transmits the output packet input from the first routing processing unit to the second routing processing unit of the searched transfer destination. .