KR100317991B1 - Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router - Google Patents
Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router Download PDFInfo
- Publication number
- KR100317991B1 KR100317991B1 KR1020000003493A KR20000003493A KR100317991B1 KR 100317991 B1 KR100317991 B1 KR 100317991B1 KR 1020000003493 A KR1020000003493 A KR 1020000003493A KR 20000003493 A KR20000003493 A KR 20000003493A KR 100317991 B1 KR100317991 B1 KR 100317991B1
- Authority
- KR
- South Korea
- Prior art keywords
- packet
- controller
- routing
- lookup
- processing
- Prior art date
Links
- 238000000034 method Methods 0.000 title claims abstract description 34
- 238000012545 processing Methods 0.000 claims abstract description 53
- 239000000872 buffer Substances 0.000 claims abstract description 22
- 238000003672 processing method Methods 0.000 claims abstract description 10
- 230000008569 process Effects 0.000 claims description 19
- 230000004048 modification Effects 0.000 claims description 18
- 238000012986 modification Methods 0.000 claims description 18
- 230000009977 dual effect Effects 0.000 claims description 8
- 238000003860 storage Methods 0.000 claims description 8
- 238000012544 monitoring process Methods 0.000 claims description 2
- 230000009467 reduction Effects 0.000 claims description 2
- 238000012937 correction Methods 0.000 claims 1
- 230000000694 effects Effects 0.000 abstract description 2
- 238000010586 diagram Methods 0.000 description 6
- 238000005516 engineering process Methods 0.000 description 4
- 230000006872 improvement Effects 0.000 description 2
- 230000004913 activation Effects 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000003780 insertion Methods 0.000 description 1
- 230000037431 insertion Effects 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000000737 periodic effect Effects 0.000 description 1
- 238000004904 shortening Methods 0.000 description 1
- 239000012536 storage buffer Substances 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
- H04L45/04—Interdomain routing, e.g. hierarchical routing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/66—Layer 2 routing, e.g. in Ethernet based MAN's
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/74—Address processing for routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
본 발명은 기가비트 이더넷 기반 라우터에서의 패킷 포워딩 처리에 관한 것으로서, 기가비트 이더넷 시스템에서 기가비트 속도의 트래픽을 만족하는 빠른 포워딩을 구현하기 위해 기가비트 와이어스피드(wired-speed)를 보장하는 룩업의 결과에 대해 듀얼 포트메모리를 버퍼로 사용하고 하드웨어 방법에 의한 병렬처리형 패킷 포워딩 처리를 함으로써 실시간의 패킷 포워딩을 가능하게 하여 라우터 시스템 성능을 향상시키는 병렬처리형 3계층 패킷 포워딩 처리 방법 및 장치를 제공한다.The present invention relates to packet forwarding processing in a Gigabit Ethernet-based router. The present invention relates to a result of a lookup that guarantees gigabit wire-speed for implementing fast forwarding that satisfies gigabit-speed traffic in a Gigabit Ethernet system. The present invention provides a parallel processing type 3 layer packet forwarding processing method and apparatus for enabling packet forwarding in real time by using a port memory as a buffer and performing parallel processing type packet forwarding by a hardware method to improve router system performance.
본 발명은 프로세싱 시간을 단축하여 기가비트 속도처리가 가능하게 하고, 룩업의 결과에 의한 패킷처리를 프로세서의 개입없이 일정 시간지연내로 보장할 수 있으며, 또 입력 프로세싱과는 별도로 병렬 처리하므로 회로의 간단화를 통한 비용 절감의 효과가 있다.The present invention can reduce the processing time to enable gigabit speed processing, guarantee the packet processing by the result of the lookup within a certain time delay without the involvement of the processor, and simplify the circuit by parallel processing separately from the input processing. There is a cost saving effect through.
Description
본 발명은 기가비트 이더넷 기반 라우터에서의 패킷 포워딩 처리에 관한 것으로서, 상세하게는 기가비트 이더넷 시스템에서 기가비트 속도의 트래픽을 만족하는 빠른 포워딩을 구현하기 위해 기가비트 와이어스피드(wired-speed)를 보장하는 룩업의 결과에 대해 듀얼 포트메모리를 버퍼로 사용하고 하드웨어 방법에 의한 병렬처리형 패킷 포워딩 처리를 함으로써 실시간의 패킷 포워딩을 가능하게 하여 라우터 시스템 성능을 향상시키는 병렬처리형 3계층 패킷 포워딩 처리 방법 및 장치에 관한 것이다.The present invention relates to packet forwarding processing in a gigabit Ethernet-based router. Specifically, the present invention relates to a result of a lookup that guarantees gigabit wire-speed to implement fast forwarding that satisfies gigabit-speed traffic in a gigabit Ethernet system. The present invention relates to a parallel three-layer packet forwarding processing method and apparatus for improving router system performance by enabling packet forwarding in real time by using dual port memory as a buffer and performing parallel packet forwarding processing by a hardware method. .
최근 급격한 증가 추세에 있는 복잡하면서도 다양한 데스크탑 컴퓨팅 어플리케이션들간의 통신은 주로 LAN(Local Area Network )에 의존하고 있으며, 인터넷과 인트라넷의 활성화와 함께 트래픽 량의 증가에 기인한 신호 대역폭의 증가가 요구 되고 있다. 그러나, 기존에 공유매체를 기반으로 연결된 LAN망에서는 정체(Congestion) 문제를 해결할 수 없으므로 특정 대역폭을 제공하는 장점을 가진 스위치 형태의 장치로 발전하였으며, 스위치 형태의 장치 또한 100Mbps의 대역폭을 가진 고속 이더넷을 이용한 네트워크 기술로 발전되었다. 그런데 서버 또는 데스크탑간의 100Base-T 기술을 이용한 네트워킹 기술이 보편화 됨에 따라 백본과 서버 레벨에서는 이 보다도 더 고속의 네트워크 기술이 요구 되었고 1.25Gbps의 대역폭을 제공하는 기가비트 이더넷(Gigabit Ethernet )시스템이 개발 되었다. 서브네트간 트래픽의 증가는 또한 기가비트 이더넷 시스템에서의 브리지 및 라우터 기능의 성능 향상을 필수적으로 요구하게 된다. 그런데 이러한 라우터의 성능 향상의 가장 큰 문제점은 기가비트 속도의 패킷 포워딩 문제이다. 이러한 기가비트 속도의 패킷 포워딩 문제를 해결하는 방법으로서 기가비트 속도의 트래픽을 만족하는 빠른 룩업(Lookup)을 구현하기 위해 CAM(Content-Addressable Memory)이나 캐쉬 메모리등을 적용하여 3계층 레벨인 IP 어드레스의 룩업을 처리하고, 그 결과를 패킷에 적용하여 기가비트 와이어드 속도(wired-speed)의 포워딩을 하도록 한다.The communication between complex and diverse desktop computing applications, which are rapidly increasing in recent years, mainly depends on LAN (Local Area Network), and it is required to increase signal bandwidth due to the increase of traffic volume with the activation of Internet and intranet. . However, in the LAN network connected based on the shared media, congestion problem cannot be solved, so it has developed into a switch type device having an advantage of providing a specific bandwidth, and the switch type device also has a high speed Ethernet having a bandwidth of 100 Mbps. Has been developed into network technology. However, as networking technology using 100Base-T technology between servers or desktops has become commonplace, higher speed network technology has been required at the backbone and server levels, and a Gigabit Ethernet system has been developed that provides 1.25Gbps of bandwidth. Increasing traffic between subnets also necessitates performance improvements in bridge and router functionality in Gigabit Ethernet systems. However, the biggest problem of the performance improvement of the router is the problem of packet forwarding at the gigabit speed. As a method to solve the gigabit-rate packet forwarding problem, to implement a fast lookup that satisfies the gigabit-rate traffic, the CAM (Content-Addressable Memory) or the cache memory is applied to the lookup of the three-layer IP address. And then apply the result to the packet for Gigabit wired-speed forwarding.
현재 기가비트 속도를 보장하기위한 룩업기능을 위해서는 많은 발명들이 제안되고 있다. 그러나 이러한 룩업처리 결과를 포워딩하고자 하는 패킷에 적용하고자 할 때 패킷처리 방식에 따라 많은 지연을 갖게 된다.Currently, many inventions have been proposed for the lookup function to guarantee the gigabit speed. However, when applying the lookup processing result to the packet to be forwarded, there is a large delay depending on the packet processing method.
종래에는 빠른 프로세서가 캐쉬같은 다른 메모리에 패킷을 저장해 놓고 패킷갱신등을 처리하는 포워딩 알고리즘을 사용하거나 헤더 부분만을 처리하는 별도의 큐를 두어 패킷 갱신후에 저장해둔 데이터 부분과 결합(MUX) 해서 포워딩하는 하드웨어 기반의 패킷 포워딩 처리 방법등을 적용 하였다.Conventionally, a fast processor stores a packet in another memory such as a cache, and uses a forwarding algorithm that handles packet updating, or a separate queue that handles only a header part and combines (MUX) and forwards the data part stored after the packet update. Hardware based packet forwarding processing method is applied.
이러한 종래의 패킷 포워딩 처리는 프로세서에 의한 메모리 액세스 시간이나분리된 패킷의 결합등에 따른 지연시간등에 의해 기가비트 와이어 속도의 빠른 룩업이 처리되어도 그 결과에 대한 패킷처리와 포워딩 시키는 과정에서 많은 시간이 소요되어 기가비트 와이어 속도의 포워딩 구현이 불가능한 문제점이 있다.This conventional packet forwarding process takes a lot of time in the process of packet processing and forwarding the result even if a fast lookup of the gigabit wire speed is processed by the delay time due to the memory access time by the processor or the combination of the separated packets. There is a problem in that it is impossible to implement gigabit wire speed forwarding.
도 1은 일반적으로 많이 구성하고 있는 기존 이더넷 기반의 라우터 구조도로서, 전체 구성으로 볼 때 이더넷의 매체 제어기(Media Access Controller : 11)를 통해 들어오는 패킷 스트림 데이터(17)는 포워딩 처리 장치(10)에 의해 포워딩 처리되는데, 입력된 패킷 스트림 데이터(17)는 수신버퍼(12)에 저장하고 인터럽트등의 방식으로 프로세서(13)에게 통보하면 프로세서(13)는 수신 버퍼(12)를 통해 패킷 포워딩부(15)의 패킷 저장 메모리(152)로 패킷 프레임을 저장한다.FIG. 1 is a schematic diagram of a conventional Ethernet-based router. In general, the packet stream data 17 received through the Ethernet Media Access Controller 11 is transferred to the forwarding processing apparatus 10. Referring to FIG. When the packet stream data 17 is stored in the reception buffer 12 and notified to the processor 13 by an interrupt or the like, the processor 13 transmits the packet forwarding unit ( A packet frame is stored in the packet storage memory 152 of 15).
프로세서(13)는 패킷 포워딩부(15)의 패킷 저장 메모리(152)를 액세스하여 IP 헤더에서 읽어낸 목적지 어드레스를 룩업처리부(16)에 보내어 룩업제어기(161)에 의한 룩업테이블 메모리(162) 검색 작업에 들어가도록 한다. 이때 프로세서(13) 인접한 곳에 캐쉬메모리(14)를 두어 한번의 히트(Hit)에 의한 룩업 검색시간의 단축을 기한다.The processor 13 accesses the packet storage memory 152 of the packet forwarding unit 15 and sends the destination address read from the IP header to the lookup processing unit 16 to retrieve the lookup table memory 162 by the lookup controller 161. Get to work. At this time, the cache memory 14 is placed near the processor 13 to shorten the lookup search time by one hit.
룩업과정이 완료되면 프로세서(13)는 그 결과인 넥스트 홉 및 포트 정보를 라우팅 제어기(151)에 넘겨 패킷저장 메모리(152)에 있는 패킷 데이터를 수정 하도록 한다. 이때의 수정 정보로는 넥스트 홉 변경, TTL 감소, 체크섬 재계산등이 있으며 라우팅 제어기(151)는 라우팅 처리가 끝난 패킷을 포워딩용 버퍼(153)에 실어 그 패킷이 포워딩 되도록 한다.When the lookup process is completed, the processor 13 passes the resulting next hop and port information to the routing controller 151 to modify the packet data in the packet storage memory 152. At this time, the modified information may include a next hop change, a TTL reduction, a checksum recalculation, and the like. The routing controller 151 loads the completed packet into the forwarding buffer 153 to forward the packet.
이와 같이 종래의 소프트웨어 기반의 패킷 포워딩 처리 방법은 메모리에 패킷을 저장해 놓은 뒤 룩업처리를 하고, 그 결과를 갖고 패킷의 넥스트 홉(Next HOP) 어드레스 변경, TTL(Time too Live) 감소, 체크섬(Checksum) 재계산등의 패킷 라우팅 처리를 위해 메모리에 저장된 패킷을 프로세서가 다시 액세스 하여 패킷 가공을 하게 되므로 이러한 프로세싱 과정중에 많은 시간의 지연을 갖게 된다.In the conventional software-based packet forwarding method, the packet is stored in a memory and then looked up, and the result is changed to a next hop address of the packet, a time too live (TTL) decrease, and a checksum Since the processor accesses the packet stored in the memory again for packet routing such as recalculation, packet processing is delayed.
때문에 이와 같은 소프트웨어 기반의 패킷 포워딩 처리 방법은 기가비트 이더넷 시스템 같은 대역폭과 속도에는 적합하지 못하며 패킷의 손실을 초래하게 된다. 이러한 문제를 개선하기 위해 고속의 리스크 프로세서(RISC processor)를 사용하는 것이 제안 되었는데, 이 방법은 시스템 제작 비용의 증가를 가져 오게 된다.This software-based packet forwarding process is not suitable for bandwidth and speed, such as Gigabit Ethernet systems, resulting in packet loss. In order to remedy this problem, it has been proposed to use a high-speed RISC processor, which leads to an increase in system fabrication cost.
이와는 다른 하드웨어 기반의 패킷 포워딩 처리 방법이 있는데, 이는 패킷 포워딩 처리가 필요한 헤더 부분만을 데이터 영역 큐와 분리해서 별도의 큐를 두고 포워딩시에 헤더 정보를 갱신하고 출력시에 데이터 큐와 결합해서 처리하는 방법을 사용한다. 이 경우 헤더 큐와 데이터 큐의 동기상태를 관리하는 별도의 큐 관리 프래그(Flag)를 두어야 하므로 회로의 복잡성을 더하게 되어 실시간 포워딩에 많은 부담을 초래 하게 된다.There is a different hardware-based packet forwarding method, which separates only the header part that needs packet forwarding from the data area queue, puts a separate queue, updates header information when forwarding, and combines it with data queue when outputting. Use the method. In this case, a separate queue management flag (flag) that manages the synchronization state of the header queue and the data queue must be provided, which adds to the complexity of the circuit and causes a lot of burden on real-time forwarding.
본 발명은 상기한 종래 기술의 문제점을 해결하기 위해 안출된 것으로, 기가비트 속도의 이더넷 기반의 라우터에서 패킷 프레임의 송수신과 3계층 라우팅을 담당하는 기가비트 이더넷 라우터에 적용 가능한 병렬처리형 3계층 패킷 포워딩 처리 방법 및 장치를 제공하는 데 그 목적이 있다.The present invention has been made to solve the above problems of the prior art, a parallel processing type three-layer packet forwarding process applicable to a gigabit Ethernet router that is responsible for transmitting and receiving packet frames and three-layer routing in a gigabit Ethernet-based router Its purpose is to provide a method and apparatus.
도 1은 기존의 일반적인 이더넷 기반 라우터 구조도1 is a conventional general Ethernet-based router structure diagram
도 2는 본 발명에 따른 병렬처리형 3계층 패킷 포워딩 처리 방법을 구현한 장치의 구조도2 is a structural diagram of an apparatus implementing the parallel processing type 3 layer packet forwarding processing method according to the present invention.
도 3은 듀얼포트 메모리의 접속 관계도3 is a connection relationship diagram of the dual port memory.
도 4는 본 발명에 따른 병렬처리형 3계층 패킷 포워딩 처리 장치의 기능 흐름도4 is a functional flowchart of a parallel processing-type three-layer packet forwarding processing apparatus according to the present invention.
도 5는 본 발명에 따른 병렬처리형 3계층 패킷 포워딩 처리 장치의 패킷 포워딩 과정을 보인 절차도5 is a flowchart illustrating a packet forwarding process of a parallel processing-type three-layer packet forwarding processing apparatus according to the present invention.
* 도면의 주요부분에 대한 부호의 설명 *Explanation of symbols on the main parts of the drawings
201 : 기가비트 이더넷 매체 제어기 202 : 패킷 쓰기 제어기201: Gigabit Ethernet Media Controller 202: Packet Write Controller
203 : 패킷 라우팅 중앙 제어기 204 : 룩업 제어기203: packet routing central controller 204: lookup controller
205 : 룩업 테이블 206 : 패킷 수정 제어기205: lookup table 206: packet modification controller
207 : 패킷 읽기 제어기 208 : 포인터 중재기207: packet read controller 208: pointer arbiter
209 : 버퍼209: buffer
상기한 목적을 달성하기 위한 본 발명은 기가비트 속도의 패킷 포워딩을 보장하기 위해 듀얼 포트 메모리(Dual Port memory)를 버퍼(Buffer)로 사용하여 패킷의 순간 저장과 라우팅 처리를 위한 헤더 정보의 수정이 같은 저장 버퍼에서 독립적으로 병렬 처리될 수 있도록 하여 프로세싱 시간을 기가비트 속도처리가 가능하게 하고, 룩업의 결과에 의한 패킷처리를 프로세서의 개입 없이 동시발생적으로 처리함으로써 회로의 간단화를 통한 비용의 절감을 가져오게 한 것을 특징으로 한다.In order to achieve the above object, the present invention uses a dual port memory as a buffer to guarantee packet forwarding at a gigabit speed, and the header information for the instantaneous storage and routing processing of the packet is the same. By allowing parallel processing independently in the storage buffer, Gigabit speed processing is possible, and packet processing resulting from the lookup can be processed concurrently without processor intervention, resulting in cost savings through simplified circuits. It is characterized by coming.
이하, 본 발명의 바람직한 실시예를 첨부도면을 참조하여 상세하게 설명한다.Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings.
도 2는 기가비트 이더넷 기반의 라우터에서 기가비트 속도의 라우팅 패킷 처리를 실현하기 위해 본 발명에 따른 병렬처리형 3계층 패킷 포워딩 처리 방법을 적용한 패킷 포워딩 처리 장치의 구조도이다.2 is a structural diagram of a packet forwarding processing apparatus applying the parallel processing type 3 layer packet forwarding processing method according to the present invention to realize a gigabit-rate routing packet processing in a gigabit Ethernet-based router.
앞서 설명한 도 1의 기존 이더넷 라우터의 구조와는 달리, 본 발명의 패킷 포워딩 처리 장치는 프로세서의 개입이 필요없이 전체 라우팅 과정을 제어하는 패킷 라우팅 중앙 제어기(203); 상기 패킷 라우팅 중앙 제어기(203)의 요구에 의해 룩업 테이블(205)을 통해 목적지 IP 어드레스에 대한 룩업 검색을 하는 룩업 제어기(204); IP 어드레스에 대한 정보를 저장하고 있는 룩업 테이블(205); 입력 패킷의 저장 포인터를 지정하는 패킷 쓰기 제어기(202); 룩업결과에 의한 패킷 수정위치를 지정하는 패킷 수정 제어기(206); 호스트로 읽어갈 패킷의 번지를 지정하는 패킷 읽기 제어기(207); 상기 패킷 수정 제어기(206)와 패킷 읽기 제어기(207)에서 입력되는 수정쓰기 포인터와 읽기 포인터를 중재하는 포인터 중재기(208); 입력되는 패킷을 저장하며, 공용 데이터의 읽기와 쓰기를 서로 다른 포트에서 할 수 있는 양방향 듀얼포트 메모리로 된 버퍼(209)로 구성된다.Unlike the structure of the conventional Ethernet router of FIG. 1 described above, the packet forwarding processing apparatus of the present invention includes a packet routing central controller 203 for controlling the entire routing process without the need for processor intervention; A lookup controller 204 for performing a lookup search for a destination IP address through a lookup table 205 at the request of the packet routing central controller 203; A lookup table 205 which stores information on an IP address; A packet write controller 202 for designating a storage pointer of an input packet; A packet modification controller 206 for designating a packet modification position based on the lookup result; A packet read controller 207 which designates the address of a packet to be read to the host; A pointer arbiter (208) for arbitrating a modification write pointer and a read pointer input from the packet modification controller (206) and the packet read controller (207); It consists of a buffer 209, which is a bi-directional dual-port memory that stores incoming packets and allows reading and writing of common data on different ports.
이와 같은 구성에서, 기가비트 이더넷 매체 제어기(201)를 통해 들어오는 기가비트 밴드폭을 만족하는 31.25MHz 속도의 32비트 데이터 패킷 스트림(210)은 버퍼(209)에 시간 지연없이 저장되고, 이때 저장할 위치는 패킷 쓰기 제어기(202)에서 제공되는 쓰기 포인터가 지정하는 번지이다.In such a configuration, a 31.25 MHz rate 32-bit data packet stream 210 that satisfies the gigabit bandwidth coming through the gigabit Ethernet media controller 201 is stored in the buffer 209 with no time delay, where the packet is stored. The address designated by the write pointer provided by the write controller 202.
한편, 입력되고 있는 패킷을 모니터링하고 있던 패킷 라우팅 중앙 제어기(203)는 목적지 IP 어드레스를 갖고 룩업처리기(204)에게 검색 요청을 하고 룩업처리기(204)는 룩업테이블(205)을 검색하여 라우팅 결과를 얻는다.On the other hand, the packet routing central controller 203, which is monitoring the incoming packet, makes a search request to the lookup processor 204 with the destination IP address, and the lookup processor 204 searches the lookup table 205 to retrieve the routing result. Get
이러한 라우팅 결과에 대해 패킷 라우팅 중앙 제어기(203)은 패킷 쓰기 제어기(202)로부터 현재 버퍼(209)에 쓰고있는 패킷 스트림의 시작 번지를 얻어와 패킷 수정 제어기(206)에게 넘겨준다.For this routing result, the packet routing central controller 203 obtains the start address of the packet stream currently being written to the buffer 209 from the packet write controller 202 and passes it to the packet modification controller 206.
그러면 패킷 수정 제어기(206)는 패킷 읽기 제어기(207)에게 출력 포트로 패킷을 읽어나가고 있는 동작을 멈추게 하고, 수정쓰기 포인터를 포인터 중재기(208)로 넘겨주어 포인터 중재기(208)의 중재에 의해 지정된 위치에 필요한 데이터를 써서 라우팅 패킷 수정을 한다. 이러한 과정은 입력된 하나의 패킷이 모두 저장되는 동안 즉, 다음 패킷이 입력되기 전에 모두 이루어져야 하고 이러한 실시간 처리를 위해 듀얼포트 메모리로 구성되는 버퍼(209)와 읽기/쓰기의 병렬 처리 방법을 사용한다.The packet modification controller 206 then stops the packet read controller 207 from reading the packet to the output port, and passes the modification write pointer to the pointer arbiter 208 for arbitration of the pointer arbiter 208. The routing packet is modified by writing the necessary data in the designated location. This process uses a parallel processing of read / write and buffer 209, which consists of dual-port memory, while all the input packets are stored, that is, before the next packet is input. .
패킷 읽기 제어기(207)는 이전 읽기 번지를 간직하고 있다가 패킷 수정과정이 끝나면 다시 읽기 포인터를 포인터 중재기(208)에 전달하여 포워딩 처리된 패킷을 출력 포트로 전달해 준다.The packet read controller 207 retains the previous read address and transfers the read pointer to the pointer arbiter 208 again when the packet modification process is completed, and forwards the forwarded packet to the output port.
도 3은 본 발명에서 제안하는 병렬처리형 3계층 패킷 포워딩 처리 방법을 구현하기 위해 버퍼로 사용한 듀얼포트 메모리의 접속 관계를 보인 것이다.Figure 3 shows the connection relationship between the dual port memory used as a buffer to implement the parallel processing layer 3 packet forwarding processing method proposed in the present invention.
듀얼 포트 메모리(301)는 두 개의 포트(302, 305)에서 읽기 및 쓰기가 가능한 공용 메모리로 구성되어 있고, 패킷의 크기(64-1518바이트 이더넷 패킷)에 따라 가변적으로 세그먼트를 할당 할 수 있으며, 양쪽의 쓰기 포인터(303)와 읽기/쓰기 포인터(306)로 제어되는 링구조의 버퍼를 구성한다. 포트1(302)로 들어오는 입력 패킷(304)은 쓰기 포인터(303)에 의해 저장할 번지를 지정 받고, 포트2(305)에서 입출력 되는 데이터 및 패킷(307)은 읽기/쓰기 포인터(306)에 의해 저장 또는 읽어나갈 번지를 지정 받는다. 링구조의 버퍼 특성으로 포트1의 쓰기 포인터(303)와 포트2의 읽기 포인터(306)의 일치 여부에 따라 버퍼의 찬(full) 상태(308)와 빈(empty) 상태(309)를 표시해 준다.Dual port memory 301 is composed of a common memory that can be read and written in the two ports (302, 305), it is possible to allocate segments variably according to the size of the packet (64-1518 bytes Ethernet packet), A buffer having a ring structure controlled by both write pointers 303 and read / write pointers 306 is formed. The input packet 304 entering port 1 302 is designated by the write pointer 303 to store, and the data and packets 307 input / output at the port 2 305 are read / write pointer 306. Address to save or read is specified. The buffer structure of the ring structure shows the full (308) and empty (309) states of the buffer, depending on whether the write pointer 303 on the port 1 and the read pointer 306 on the port 2 match. .
도 4는 본 발명에 따른 병렬처리형 3계층 패킷 포워딩 처리 장치의 기능 흐름도를 시간대로 보인 것이다.Figure 4 shows a functional flow diagram of a parallel processing layer 3 packet forwarding processing apparatus according to the present invention in time zone.
기존의 라우팅 패킷 방법을 이용하는 도 1의 구성과 다른 점은 들어오는 입력 패킷(41)에 대해 프로세서의 개입이나 로컬 메모리로의 복사과정을 거치지 않고 패킷의 라우팅 처리 및 패킷 포워딩이 시간 지연없이 하드웨어에 의해 병렬적으로 처리 된다는 것이다.Unlike the configuration of FIG. 1 using the conventional routing packet method, the routing process and packet forwarding of the packet are performed by hardware without time delay without the processor's intervention or copying to the local memory for the incoming input packet 41. It is processed in parallel.
기가비트 이더넷 매체 제어기(201)로부터 32비트 스트림의 첫번째 입력 패킷1이 저장되고 있는 동안(411) 목적지 IP 어드레스가 저장되는 시점이 되면 패킷 저장과는 별도로 패킷라우팅 중앙 제어기(203)는 룩업제어기(204)에게 목적지 IP 어드레스를 넘겨주며(421) 룩업 처리 요구(422)를 한다. 프로세서나 하드웨어에 의한 방법으로 룩업 제어기(204)는 실시간의 룩업검색을 하여 검색 결과를 패킷라우팅 중앙 제어기(203)에게 전달한다.While the first input packet 1 of the 32-bit stream from the Gigabit Ethernet media controller 201 is being stored (411), when the destination IP address is stored, the packet routing central controller 203 separates the lookup controller 204 from the packet storage. ) Is passed to the destination IP address (421) and a lookup processing request (422) is made. In a processor or hardware method, the lookup controller 204 performs a real-time lookup search and transmits the search result to the packet routing central controller 203.
이 시점에서 패킷 쓰기 제어기(202)는 패킷라우팅 중앙 제어기(203)로부터 현재 버퍼(209)에 쓰고있는 패킷 스트림의 시작 번지를 넘겨 받아 출력 패킷에 대해 패킷 1의 헤더 수정(431)을 하고, 이어 패킷 읽기 제어기(207)의 포인팅에 의한 패킷1 읽기(441)를 수행한다.At this point, the packet write controller 202 receives the start address of the packet stream currently being written to the buffer 209 from the packet routing central controller 203, and then modifies the header 1 of the packet 1 to the output packet. Packet 1 read 441 by the pointing of the packet read controller 207 is performed.
듀얼포트 메모리 버퍼(209)의 공용 메모리에 저장된 입력 패킷들(411, 412, 413, 414)은 룩업결과에 의한 패킷 포워딩 처리(431, 432, 433, 434)가 끝나기 전까지는 패킷 읽기 과정(441, 442, 451, 452, 461, 462)에 들어 갈 수 없다. 그러나 각 패킷에 대한 패킷 헤더 수정과정(431, 432, 433, 434)이 일정한 시간대에 끝나므로 패킷 입력 후 일정한 시간 지연(401, 402, 403, 404) 뒤에 주기적인 패킷 읽기가 가능하다.The input packets 411, 412, 413, and 414 stored in the common memory of the dual port memory buffer 209 may read the packet until the packet forwarding process 431, 432, 433, 434 based on the lookup results. , 442, 451, 452, 461, 462. However, since the packet header modification process (431, 432, 433, 434) for each packet ends at a certain time, periodic packet reading is possible after a certain time delay (401, 402, 403, 404) after packet input.
도 5는 도 2의 구조도와 도 4의 기능 흐름도에서 본 발명의 병렬처리형 3계층 패킷 포워딩 처리 장치의 처리 절차를 어드레스와 데이터 그리고 제어 신호 단위로 나타낸 것이다.FIG. 5 illustrates the processing procedure of the parallel processing type 3 layer packet forwarding processing apparatus of the present invention in the structure of FIG. 2 and the functional flow chart of FIG. 4 in units of address, data, and control signal.
쓰기 제어 신호(53)에 의해 저장되고 있는 입력패킷(51)의 MAC 헤더와 IP헤더 중 32비트 단위의 9번째 세그먼트인 목적지 IP 어드레스는(511) 룩업 검색의 입력 요소로 사용되어 룩업 제어기(204)로부터 출력포트 위치 및 패킷 상태정보를 실어주는 패킷의 헤더정보(561), 넥스트 홉 어드레스정보(562, 563)를 얻게 한다. 해당 패킷의 읽기(57)가 시작되기 전에 이들 정보와 IP 헤더의 TTL 감소정보(564), 체크섬 워드값 감소정보(565)가 헤더 삽입을 위해 한 칸씩 밀린 어드레스(541, 542, 543, 544, 545)로 쓰여진다.The MAC header of the input packet 51 stored in the write control signal 53 and the destination IP address, which is the ninth segment of the 32-bit unit of the IP header, are used as the input element of the lookup search (511). Packet header information 561 and next hop address information 562 and 563 carrying output port position and packet status information are obtained. Before the information 57 is started to be read, these information, the TTL decrement information 564 of the IP header, and the checksum word value decrement information 565 are pushed by one space for the header insertion (541, 542, 543, 544). 545).
이때, 라우팅 패킷처리 정보를 교체할 출력 패킷의 IP 헤더 번지(541, 542, 543, 544, 545)를 스트림 형태로 일시에 지정하고, 스트림(561,562,563,564,565)형태의 데이터를 일시에 교체 함으로써 시간단축과 포워딩 효율을 높인다.At this time, the IP header address 541, 542, 543, 544, 545 of the output packet to replace the routing packet processing information is temporarily designated in the form of a stream, and the data of the stream (561, 562, 563, 564, 565) is temporarily replaced. Increase forwarding efficiency.
이 과정의 완료에 이어 다시 추가로 삽입된 처음 번지로부터 패킷 데이터들(57)이 출력된다.After the completion of this process, packet data 57 is outputted from the first inserted address again.
상술한 바와 같이 본 발명에 의한 병렬처리형의 패킷 처리는 모든 과정을 하드웨어로 간결하게 구현하여 프로세서의 운영과 메모리의 복사에 의한 지연요인을 없애고, 매체 제어기로부터 입력되는 하나의 패킷 타임 슬롯(Slot) 내에 포워딩이 완료될 수 있도록 공용 메모리를 갖는 듀얼포트 메모리방식의 버퍼를 사용한 패킷 포워딩을 처리한다. 또한 버퍼에 저장된 출력 패킷에 대해 중재에 의한 포인터 조정으로 라우팅 결과에 대한 패킷 처리(쓰기)와 읽기가 같은 포트에서 일어나므로서 기존의 패킷처리 방식에서 부수적으로 들어갔던 메모리의 복사과정을 없앨 수 있다.As described above, the packet processing of the parallel processing according to the present invention implements all processes in hardware concisely, eliminating delay factors caused by the operation of the processor and copying of the memory, and one packet time slot inputted from the media controller. Packet forwarding using a dual-port memory type buffer with a common memory is processed so that forwarding can be completed. In addition, mediation of pointers to the output packets stored in the buffer allows packet processing (writing) and reading of the routing result to occur on the same port, thus eliminating the copying process of memory that has been incidental to the conventional packet processing. .
따라서 본 발명은 프로세싱 시간을 단축하여 기가비트 속도처리가 가능하게 하고, 룩업의 결과에 의한 패킷처리를 프로세서의 개입 과정이 없이 일정 시간지연내의 보장된 패킷처리를 가능하게 하며 입력 프로세싱과는 별도로 병렬 처리하게 함으로써 회로의 간단화를 통한 비용의 절감을 가져오는 효과가 있다.Therefore, the present invention enables processing of gigabit speed by shortening the processing time, and guarantees processing of packets within a certain time delay without processing of the processor by processing the packet by the result of the lookup and parallel processing separately from the input processing. By doing so, there is an effect of reducing the cost through the simplification of the circuit.
이상에서 본 발명에 대한 기술사상을 첨부도면과 함께 서술하였지만 이는 본 발명의 바람직한 실시예를 예시적으로 설명한 것이지 본 발명을 한정하는 것은 아니다. 또한, 이 기술분야의 통상의 지식을 가진 자라면 누구나 본 발명의 기술사상의 범주를 이탈하지 않는 범위 내에서 다양한 변형 및 모방이 가능함은 명백한 사실이다.The technical spirit of the present invention has been described above with reference to the accompanying drawings, but this is by way of example only and not intended to limit the present invention. In addition, it is obvious that any person skilled in the art can make various modifications and imitations without departing from the scope of the technical idea of the present invention.
Claims (4)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020000003493A KR100317991B1 (en) | 2000-01-25 | 2000-01-25 | Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020000003493A KR100317991B1 (en) | 2000-01-25 | 2000-01-25 | Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20010076079A KR20010076079A (en) | 2001-08-11 |
| KR100317991B1 true KR100317991B1 (en) | 2001-12-22 |
Family
ID=19641322
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020000003493A KR100317991B1 (en) | 2000-01-25 | 2000-01-25 | Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR100317991B1 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100456671B1 (en) * | 2001-11-24 | 2004-11-10 | 주식회사 케이티 | Parallel lookup engine and method for fast packet forwarding in network router |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100798926B1 (en) * | 2006-12-04 | 2008-01-29 | 한국전자통신연구원 | Apparatus and method for forwarding packet in packet switch system |
| KR100739222B1 (en) * | 2007-02-07 | 2007-07-13 | 어헤드컴(주) | Ethernet based industrial communication system for using dual buffer |
| US8407367B2 (en) * | 2007-12-26 | 2013-03-26 | Intel Corporation | Unified connector architecture |
| US8700821B2 (en) | 2008-08-22 | 2014-04-15 | Intel Corporation | Unified multi-transport medium connector architecture |
| US9565132B2 (en) | 2011-12-27 | 2017-02-07 | Intel Corporation | Multi-protocol I/O interconnect including a switching fabric |
| US8775713B2 (en) | 2011-12-27 | 2014-07-08 | Intel Corporation | Multi-protocol tunneling over an I/O interconnect |
| US9697159B2 (en) | 2011-12-27 | 2017-07-04 | Intel Corporation | Multi-protocol I/O interconnect time synchronization |
| US9252970B2 (en) | 2011-12-27 | 2016-02-02 | Intel Corporation | Multi-protocol I/O interconnect architecture |
| US8953644B2 (en) | 2011-12-27 | 2015-02-10 | Intel Corporation | Multi-protocol I/O interconnect time synchronization |
| US8856420B2 (en) | 2011-12-27 | 2014-10-07 | Intel Corporation | Multi-protocol I/O interconnect flow control |
| US8782321B2 (en) | 2012-02-08 | 2014-07-15 | Intel Corporation | PCI express tunneling over a multi-protocol I/O interconnect |
| US8880923B2 (en) | 2012-03-29 | 2014-11-04 | Intel Corporation | Link power management in an I/O interconnect |
| CN109587084A (en) * | 2015-12-30 | 2019-04-05 | 华为技术有限公司 | A kind of message storage forwarding method and circuit and equipment |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5333270A (en) * | 1992-12-29 | 1994-07-26 | National Semiconductor Corporation | FDDI configuration management state machine controller |
| JPH07320419A (en) * | 1994-05-25 | 1995-12-08 | Toshiba Corp | Device for converting bit stream into byte |
| KR950035184A (en) * | 1994-05-12 | 1995-12-30 | 이헌조 | Synchronous Error Compensation Circuit of Serial Bit Stream |
| JPH08237293A (en) * | 1995-02-24 | 1996-09-13 | Hitachi Cable Ltd | Frame relay router |
| JPH0998189A (en) * | 1995-09-29 | 1997-04-08 | Toshiba Corp | Network repeater system |
| KR970024725A (en) * | 1995-10-17 | 1997-05-30 | 정장호 | High speed data exchange device in ethernet system |
| KR19990011174A (en) * | 1997-07-22 | 1999-02-18 | 윤종용 | Parallel Data Transmission Method in Fast Ethernet |
-
2000
- 2000-01-25 KR KR1020000003493A patent/KR100317991B1/en not_active IP Right Cessation
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5333270A (en) * | 1992-12-29 | 1994-07-26 | National Semiconductor Corporation | FDDI configuration management state machine controller |
| KR950035184A (en) * | 1994-05-12 | 1995-12-30 | 이헌조 | Synchronous Error Compensation Circuit of Serial Bit Stream |
| JPH07320419A (en) * | 1994-05-25 | 1995-12-08 | Toshiba Corp | Device for converting bit stream into byte |
| JPH08237293A (en) * | 1995-02-24 | 1996-09-13 | Hitachi Cable Ltd | Frame relay router |
| JPH0998189A (en) * | 1995-09-29 | 1997-04-08 | Toshiba Corp | Network repeater system |
| KR970024725A (en) * | 1995-10-17 | 1997-05-30 | 정장호 | High speed data exchange device in ethernet system |
| KR19990011174A (en) * | 1997-07-22 | 1999-02-18 | 윤종용 | Parallel Data Transmission Method in Fast Ethernet |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100456671B1 (en) * | 2001-11-24 | 2004-11-10 | 주식회사 케이티 | Parallel lookup engine and method for fast packet forwarding in network router |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20010076079A (en) | 2001-08-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6847645B1 (en) | Method and apparatus for controlling packet header buffer wrap around in a forwarding engine of an intermediate network node | |
| JP3777161B2 (en) | Efficient processing of multicast transmission | |
| US6128666A (en) | Distributed VLAN mechanism for packet field replacement in a multi-layered switched network element using a control field/signal for indicating modification of a packet with a database search engine | |
| US7017020B2 (en) | Apparatus and method for optimizing access to memory | |
| US10778612B2 (en) | Variable TCAM actions | |
| US7065050B1 (en) | Apparatus and method for controlling data flow in a network switch | |
| US6032190A (en) | System and method for processing data packets | |
| US6731652B2 (en) | Dynamic packet processor architecture | |
| US7480310B2 (en) | Flexible DMA descriptor support | |
| US6643261B2 (en) | High performance self balancing low cost network switching architecture based on distributed hierarchical shared memory | |
| KR100317991B1 (en) | Layer3 packet forwarding handling method and apparatus in gigabit Ethernet based router | |
| US6246680B1 (en) | Highly integrated multi-layer switch element architecture | |
| US6430188B1 (en) | Unified table for L2, L3, L4, switching and filtering | |
| US6732184B1 (en) | Address table overflow management in a network switch | |
| US7688825B2 (en) | Filtering frames at an input port of a switch | |
| US7248586B1 (en) | Packet forwarding throughput with partial packet ordering | |
| US6813620B2 (en) | Binary search engine and method | |
| US10284502B2 (en) | Dynamic optimization for IP forwarding performance | |
| US10938720B2 (en) | Network element with improved cache flushing | |
| KR100441033B1 (en) | Switching database cache management system | |
| US12034650B1 (en) | Distributed storage of packet transformation information in forwarding hardware | |
| EP1507368A1 (en) | High speed pipeline architecture with high update rate of associated memories |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A201 | Request for examination | ||
| E701 | Decision to grant or registration of patent right | ||
| GRNT | Written decision to grant | ||
| FPAY | Annual fee payment |
Payment date: 20101201 Year of fee payment: 10 |
|
| LAPS | Lapse due to unpaid annual fee |