KR100310288B1 - High performance forwarding engine for pipeline look-up processing in router system - Google Patents

Abstract

The present invention relates to a forwarding engine device for lookup processing in a router system. The present invention relates to scheduling and internet access for ATM cells flowing into multiple line matching units to maximize the lookup processing performance in an ATM router based on asynchronous transfer mode. A forwarding engine device capable of performing a protocol (IP) lookup process in a pipeline, and in a forwarding engine device for a lookup process in an ATM router system, switch matching controllers are connected to a plurality of ATM switches, respectively. A plurality of switch matching means for removing a routing tag from a received ATM cell and transferring it to a separation / recombination control unit or performing a reverse function thereof; And access arbitration means for arbitrating access to the routing tag information table of the plurality of switch matching means and for signaling arbitration between the switch matching means and the separation / recombination control means, wherein the separation / recombination control means includes a plurality of switch matching means; It includes a plurality of separation / recombination means connected in a one-to-one correspondence, the packet memory and the packet control unit is provided to correspond to a plurality of separation / recombination means and the look-up control unit while scheduling and simultaneously processing the packet header information received from the plurality of packet control unit It performs lookup function for packet header through and is used for ATM based router system.

Description

HIGH FORFORMANCE FORWARDING ENGINE FOR PIPELINE LOOK-UP PROCESSING IN ROUTER SYSTEM}

The present invention relates to a forwarding engine apparatus for pipeline lookup processing in a router system. In particular, the present invention relates to ATM cells flowing into various line matching units to maximize the lookup processing performance in an ATM router based on asynchronous transfer mode (ATM). The present invention relates to a forwarding engine apparatus capable of performing scheduling and Internet protocol (IP) lookup processing in a pipeline.

1 illustrates a conventional ATM based router structure.

The ATM based router includes a plurality of ATM matching devices 101, an ATM switch device 102, and a plurality of forwarding engine devices 103. The ATM matching device 101 receives an ATM cell, performs a function of changing a virtual channel identifier (VCI) / virtual path identifier (VPI) of an ATM header and transferring the same to a forwarding engine device, and forwards the cell received from the forwarding engine device. It performs the function of transmitting to the line. The forwarding engine apparatus finds an IP header, performs a lookup process, generates an appropriate VCI / VPI, and delivers it to the ATM matching apparatus 101. Such a structure has a structure in which the forwarding engine devices are divided as many as the ports occupied by the ATM subscriber matching device, thereby sharing the load.

FIG. 2 is a detailed block diagram of the conventional forwarding engine shown in FIG.

The conventional forwarding engine apparatus includes a switch matching controller 200, a separation and recombination (SAR) controller 201, a packet controller 202, a lookup controller 203, a lookup performer 204, and a lookup index that occupy a single port. An information table 205, a forwarding device main controller 206, and a routing tag information table 207.

The switch matching controller 200 has an ATM cell matching function from a switch, removes a routing tag for a cell received from the switch, and transfers a pure ATM cell to a segment and reassembly (SAR) control unit 201. The terminal receives the ATM cell from the SAR control unit 201 and inserts corresponding routing tag information and transmits the corresponding routing tag information to the switch. The SAR controller 201 performs a function of reassembling and disassembling an ATM cell, and stores and reads a packet in a packet memory through the packet controller 202. The lookup control unit 203 receives the packet header area including the packet information and the Internet protocol (IP) packet header from the packet control unit 202 and performs a header process to perform a lookup function. The lookup performer 204 receives the address in the IP header from the lookup controller 203, performs a lookup function, and outputs an address index of a corresponding entry. The lookup index information table 205 is a memory area for storing information corresponding to the address index output from the lookup performing unit 204. The routing tag information table 207 is a memory that stores switch output port information and connection identifier information corresponding to the VPI / VCI index. The forwarding device main controller 206 performs overall control of the forwarding device, and performs table construction, state management fault management, and the like.

In the conventional forwarding engine as described above, when a high-speed IP lookup engine is used for an IP packet flowing from one ATM line matching device, a processing of one packet is performed and a lookup process for the next packet is performed. Low efficiency That is, since only one IP packet reception matching unit (switch matching controller, SAR control unit, packet control unit) exists in one forwarding engine device, there is a problem in that lookup efficiency may not be fully utilized in IP packet processing.

Accordingly, the present invention is to solve the problems of the prior art as described above, in order to improve the efficiency of the lookup, the IP packet transmission and reception unit is provided, and each packet is processed in the form of a pipeline for scheduling and processing by priority It is an object of the present invention to provide a forwarding engine apparatus for pipeline lookup processing in a router system having improved lookup processing performance.

1 is a structural diagram of a conventional ATM based router.

2 is a configuration diagram of a forwarding engine device in the conventional router structure.

3 is a structural diagram of an ATM-based router to which the present invention is applied.

Figure 4 is a block diagram of a forwarding engine apparatus according to the present invention.

5 is a detailed configuration diagram of a multiple switch matching control unit according to the present invention.

6 is an arbitration timing diagram through a routing tag information table access arbitration unit according to the present invention;

Figure 7 is a detailed block diagram of a look-up control unit of the forwarding engine apparatus according to the present invention.

8 is a detailed block diagram of an IP header scheduler in accordance with the present invention.

9 is an IP header scheduling flowchart according to the present invention.

10 is a timing diagram of a lookup process in the form of a pipeline according to the present invention;

* Explanation of symbols for main parts of the drawings

400: multiple switch matching control unit 401: separation and recombination (SAR) control unit

402: packet controller 403: lookup controller

404: lookup performing unit 405: lookup index information table

406: main control unit forwarding unit 407: routing tag information table

In order to achieve the above object, the present invention provides a routing tag information table, a switch matching controller for accessing the routing tag information table and matching with an asynchronous transfer mode (ATM) switch, and performing separation and recombination of received ATM cells. A separation / recombination control unit for storing a packet, a packet memory for storing a packet, a packet control unit for controlling the packet memory, a lookup index information table, a lookup index information table, and a lookup control unit for controlling a lookup of a header; In a forwarding engine apparatus for a lookup process in an ATM router system including a lookup performing unit performing a lookup at a request of the lookup control unit and a forwarding device main control unit, the switch matching control unit may be configured to the plurality of ATM switches, respectively. Connected, removes the routing tag from the received ATM cell and forwards it to the separation / recombination control Or, a plurality of switch means for performing a matching thereof dysfunction; And access arbitration means for arbitrating access to said routing tag information table of said plurality of switch matching means and for signal arbitration between said switch matching means and said separation / recombination control means. And a plurality of separation / recombination means connected in a one-to-one correspondence with the plurality of switch matching means, wherein the packet memory and the packet controller are provided to correspond to the plurality of separation / recombination means, and the lookup control unit includes: Parallel processing of the packet header information received from the packet control unit of the control unit and performing a lookup function on the packet header through scheduling.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to FIG. 3.

3 is a block diagram of a router system to which the present invention is applied. As shown in FIG. 1, the forwarding engine of the router structure improves performance so that a single forwarding engine is connected to a plurality of switch ports to process ATM-based IP packets accommodated by a plurality of switch matching devices. That is, the router system includes a plurality of ATM matching devices 301, an ATM switch device 302, and a forwarding engine device 303 having a capability of processing IP packets from the plurality of ATM matching devices.

Figure 4 is a block diagram of a forwarding engine apparatus according to the present invention.

The forwarding engine device of the present invention is different from the conventional forwarding engine device, the switch matching control unit 400 is composed of a plurality of switch matching control unit, the SAR control unit 401 is also composed of a plurality of SAR control unit, the packet control unit 402 ) Is also composed of a plurality of packet control units connected to each SAR control unit 401. The lookup controller 403 receives the packet header information from the plurality of packet controllers 402, processes the header information in parallel, and schedules and processes the lookup function internally.

The forwarding device main controller 406, the routing tag information table 407, the lookup performer 404, and the lookup index information table 405 are the same as those of the conventional forwarding engine device.

5 is a detailed block diagram of a plurality of switch matching controllers for accessing a single common routing tag information by a plurality of switch matching controllers according to the present invention.

The routing tag information table access arbitration unit 501 performs an arbitration function to prevent a collision for mutual access when the plurality of switch matching controllers 502 access the routing tag information table 407. In the figure, 505 indicates an ATM cell flow transmitted and received to each SAR control unit 401, and 506 indicates signal control for arbitration with each SAR control unit 401.

The routing tag information table arbitration method is as follows.

The routing tag information table access arbitration unit 501 detects a transmission / reception split / recombination (SAR) control unit connected to each switch matching control unit 502 and a transmission control signal to perform an arbitration function. That is, the routing tag information table access arbitration unit 501 senses a transmission ready status signal of each transmission separation / recombination (SAR) control unit 401, latches the signals in a chronological order, and corresponds to the latched signals. When the data transmission preparation completion signal is transmitted to the switch matching control unit 502, the corresponding SAR control unit 401 transmits one cell to the switch matching control unit 502. Cell transmission arbitration may then be performed after the memory access time of the switch matching controller. If this function is expressed in time axis, it is as follows.

6 is a time-axis diagram for generating a transmission ready signal detection and a transmission permission signal from a transmission SAR control unit on the time axis. The routing tag information table access arbitration unit 501 immediately generates a transmission permission signal for the first detected transmission ready signal, and if the second detected transmission ready signal is detected within the cell header detection and routing table access time dT, In this case, the transmission permission signal is generated after dT elapses after the previous transmission preparation signal generation. In this way, access arbitration is continuously performed.

7 is a detailed block diagram of a look-up control unit according to the present invention.

The lookup control unit 403 includes a plurality of IP header processing units 710, 720, and 730, an IP header scheduler 700, and an index information control unit 740 respectively connected to each packet memory controller. Each IP header processing unit 710, 720, and 730 includes a packet header storage unit, an IP packet header extractor / inspector, an IP header storage unit, an IP header update unit, and a packet header transmitter.

The header processing of the lookup controller is as follows.

Each IP header processing unit 710 is connected to each packet control unit 402 to receive a packet header 711. At this time, each packet controller transfers the packet header to the packet header storage unit of the IP header processing unit 710 when one packet reception is completed in the packet memory. Here, the packet header storage unit is configured in a FIFO form, and requests to wait when the lookup process for the previous packet header is not completed. The IP header extracting / checking unit in each IP header processing unit 710 detects the packet type in the packet header, extracts the header area, and checks the version, TTL, checksum, etc. in the IP header. If an error occurs after the test, the forwarding device main control unit 406 notifies the corresponding error information, and extracts the IP header with respect to the next pending packet header without proceeding for further lookup for the IP header where the error occurred. And perform the inspection. If no error occurs in the IP header, the IP header extractor / checker stores the IP destination address and source address in the IP header storage and sets the ready signal for lookup.

The IP header scheduler 700 detects a signal set in the IP header storage unit, fetches an IP address in the IP header storage unit, and delivers the IP address to the lookup performer 404. At this time, when a plurality of simultaneous lookup ready signals are detected, scheduling is performed by priority, and when the same priority is performed, the robin is performed in the order of 1, 2, 3, ..n in the order of round robin.

8 is a detailed block diagram of an IP header scheduler according to the present invention.

The IP header scheduler 700 includes an IP address scheduler 800, an IP address transfer unit 810, a round robin control unit 820, a lookup timer 830, an index information fetch and transfer unit 840.

The IP address scheduler 800 detects lookup ready signals input from each port and selects a port to be looked up. The IP address transfer unit 810 reads the IP address of the selected port and transfers it to the lookup performer 404. The plurality of round robin control unit 820 performs a function of controlling the priority count so that the round robin type scheduling is performed when scheduling. The lookup timer 830 indicates the progress of the port entering the lookup phase, and is divided into a lookup and an index address fetch step at 0x01, and an index information fetch step at 0x02. The index information fetch and transfer unit 840 receives an index address and reads index information corresponding thereto from the lookup index information table and transmits the index information.

9 illustrates an IP header scheduling algorithm according to the present invention.

Initially, the priority control counters are set with respective port values (901). Priority has a highest priority of 0, and a higher value has a lower priority. If a lookup ready signal is detected from the packet controller port (902), and if the detected lookup ready signal is plural (903), it is checked whether a priority port exists (904). If there is one lookup ready signal (903) or if there is no priority port (904), a lookup valid signal is generated (909) for that port (908). When a packet is given priority (904), the IP header of the packet controller is scheduled first, and when there are a plurality of lookup ready signals having the same priority, the packet controller having a small round robin count value is preferentially selected. 905, 906). The round robin count value corresponding to the port of the selected packet controller is changed to the largest value, and among other round robin count values, the round robin has a value larger than the previous count value of the round robin count value changed to the largest value. The count values are decremented by 1 to increase the priority step by step, and the count value having a value smaller than the previous value of the round robin count value changed to the largest value maintains the previous count value (907). At this time, the lookup progress signal becomes valid, and the IP address corresponding to the port of the selected packet controller is read. A valid lookup progress signal and a lookup count of the corresponding port may be operated to determine the lookup progress state (908). That is, if the lookup progress signal is valid and the lookup count is 0x00, the IP address is read. If the lookup count signal is 0x01, the lookup and index address fetch phase is 0x02. Therefore, the lookup process may be performed in the form of a pipeline of the above three stages.

Figure 10 shows a picture on the time axis in the form of a pipeline of lookup according to the invention. In the drawing, 1000 indicates that the IP header scheduling is P1 (packet controller 1), P2 (packet controller 2), P4 (packet controller 4), Pi (packet controller i), and Pk (packet controller k) in the IP address scheduler. 1010 shows a time slot for reading an IP address, and 1010 shows a lookup performance and an index address fetching step on the time axis, which are delayed by one time slot than the IP address reading step. 1020 illustrates an index information fetch step on the time axis. Therefore, when there are consecutive address lookups, different processes of lookups for different packets may be simultaneously performed in one time slot. That is, for example, at the time t3, an IP address reading step of P4, a lookup and an index fetching step of P2, and an index information fetching step of P1 may be simultaneously performed.

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and various substitutions, modifications, and changes can be made in the art without departing from the technical spirit of the present invention. It will be apparent to those of ordinary knowledge.

According to the present invention made as described above, in an ATM based router, an IP packet cell is received through a plurality of switch ports in one router device, and IP packets are processed in parallel in a packet memory for each port, and an IP header is used in a lookup process. Using the scheduler, IP lookups in the form of priority and round robin are performed, and this process is divided into IP address reading, lookup and index fetching stages, and index information fetching stages. The lookup process may be performed in the form of a pipeline to improve the efficiency and processing performance of the lookup performance that one forwarding engine may have.

Claims (7)

A routing tag information table, a switch matching control unit for accessing the routing tag information table and matching with an asynchronous transfer mode (ATM) switch, a separation / recombination control unit for separating and reassembling a received ATM cell, and storing a packet A packet memory to control the packet memory, a packet controller for controlling the packet memory, a lookup index information table, a lookup index information table, a lookup controller for controlling a lookup of a header, and a lookup at a request of the lookup controller. A forwarding engine apparatus for lookup processing in an ATM router system including a lookup performing unit and a forwarding unit main controller, The switch matching control unit, A plurality of switch matching means connected to the plurality of ATM switches, respectively, for removing a routing tag from a received ATM cell and transmitting the removed routing tag to the separation / recombination control unit or performing a reverse function thereof; And Access arbitration means for arbitrating access to said routing tag information table of said plurality of switch matching means and for signal arbitration between said switch matching means and said separation / recombination control means, The separation / recombination control means, It includes a plurality of separation / recombination means connected in a one-to-one correspondence with the plurality of switch matching means, The packet memory and the packet controller are provided to correspond to the plurality of separation / recombination means, The look-up control unit, And a parallel processing of the packet header information received from the plurality of packet controllers and a lookup function for the packet header through scheduling. The method of claim 1, And the access arbitration means latches the request signals in a chronological order and then gives priority to the latched request signals first. The method of claim 1, The lookup control means, A plurality of IP header processing means; And IP header scheduling means for scheduling the lookup ready signal generated by the plurality of IP header processing means for each priority to deliver an Internet Protocol (IP) address to the lookup performer, Each of the plurality of IP header processing means, First storage means for storing a packet header transmitted from the packet controller; Second storage means for storing the IP destination address and the source address; Detects the type of packet header stored in the first storage means, extracts the header area, performs an error check, stores the IP destination address and the source address in the second storage means, and looks up to the IP header scheduling means. IP header extraction and inspection means for transmitting a ready signal; Updating means for receiving routing information from the lookup performing unit and updating the IP header through the IP header scheduling means; Packet header transmission means for transmitting the updated IP header to the packet controller Forwarding engine device for the lookup processing in the ATM router system comprising a. The method of claim 3, wherein And said first storage means is a first-in first-out (FIFO) type memory. The method of claim 3, wherein The IP header scheduling means, An IP address scheduler which senses a plurality of lookup preparation signals transmitted from the plurality of IP header processing means and selects one IP header processing means to be looked up by a round robin method; IP address transfer means for reading the IP address of the IP header processing means selected by the IP address scheduler and delivering the IP address to the lookup performer; A plurality of first counting means provided in one-to-one correspondence with the plurality of IP header processing means and providing a count value for priority determination; Second counting means for counting a lookup performance state; And And index information fetching and delivery means for reading index information corresponding to the index address input from the lookup performing unit from the lookup index information table under the control of the IP address scheduler and delivering the index information to the IP header processing means. A forwarding engine device for lookup processing in an ATM router system. The method of claim 5, The IP address scheduler, When there are a plurality of lookup preparation signals having the same priority, among the first counting means corresponding to the IP header processing means having the same priority, the IP header processing means having the smallest value is selected, and the count A forwarding engine device for lookup processing in an ATM router system, characterized by updating a value. The method of claim 6, Update of the count value of the IP header scheduler, The count value of the first counting means corresponding to the selected IP header processing means is changed to the largest value, and the count has a value greater than the count value before the change of the changed count value among the remaining count values of the first counting means. The value is decreased by one to increase the priority by one step, and the look-up process in the ATM router system, wherein the count value having a value smaller than the change value of the changed count value is kept as it is. Forwarding engine device for.