Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
 
www.netmanias.com      www.nmcgroups.com 
  About NMC Consulting Group 
NMC Consulting Group was founded on year 2002 and is advanced, professional network consulting company which is specialized for IP Network area like FTTH,
 
Metro Ethernet and IP/MPLS, Service area like IPTV and IMS lastly, Wireless network area like Mobile WIMAX and LTE.
 
Copyright ⓒ 1999-2011 NMC Consulting Group. All rights reserved.
 
 
Tutorials on High-Speed Multiservice IP Router
1999년 10월 19일 
www.netmanias.com 
손 장 우 (010-3460-5747, son@netmanias.com) 
Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
기존 라우터의 문제점 (Problems of the traditional routers)
[그림1]에 현재 인터넷상의 존재하는 전형적인 라우터의 구조가 나타나있다. 라인카드에 frame(2계층 프로토콜 데이터 유닛)이 도착하면 이로부터 IP 패킷을 추출하고 이 IP의 destination에 대한 next-hop이 cache에 있는가를 살핀다.
Cache에 없으면 이 패킷은 공유 버스를 통해 라우트 프러세서(Route Processor, RP)로 보내지고 RP는 라우팅 테이블을 lookup해(Longest Prefix Match를 찾아) 이 destination prefix에 대한 next-hop을 찾는다.
이 패킷은 다시 공유 버스를 통해 해당 outgoing interface로 전송되며 여기서 FIFO방식으로 서비스되어 output Port로 전송된다(Slow Path).
이 라우팅 정보는 해당 line card로 보내지며 이후 동일 목적지를 가진 패킷이 도착하면 cache만을 보면 next-hop을 찾을 수 있어 RP를 거치지 않고 한번에 해당 outgoing interface로 전송된다(Fast Path).
(a) Slow Path
1
Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
(b) Fast Path
그림 1. Two Switching Paths of the Traditional Routers
이상의 패킷 포워딩 과정에서 다음과 같은 문제점을 도출할 수 있다.
������
Cache에 route가 없는 경우 RP로 전송되는 패킷이 많은 경우 RP로의 접근이 라우터 성능을 제한한다.
������
RP에서 해당 outgoing line card로의 패킷 전송하므로 두 번의 공유 버스 경유가 이루어져야 하므로 추가 지연이 발생하며 또한 이로 인해 공유 버스 대역폭이 비효율적으로 사용된다.
������
라우트 프러세스가 소프트웨어 기반으로 LPM를 찾으므로 이 시간이 라우터 성능의 병목이 된다.
������
Cache의 사용은 기본적으로 traffic의 지역성(locality)에 크게 의존한다. 그러나 인터넷 백본망처럼 locality가 적용되지 않는 상황에서는 cache miss rate이 증가하여 fast path로 포워딩될 확률이 떨어진다. 또한 현재 인터넷 백본망의 라우팅 테이블에는 보통 500,000개의 라우트가 존재하는 데 cache를 이 정도로 크게 만들면 구현이 어렵고 비용이 매우 크다.
������
공유 버스는 대개 1Gbps정도의 대역폭을 보인다. 수십 Gbps의 대역폭을 갖는 공유 버스를 구현하기는 불가능하며 따라서 공유 버스의 대역폭이 line card의 최대 전송율의 합보다 적은 경우 line card에서의 패킷의 지연과 손실을 초래한다.
������
현재 인터넷 라우터에서는 최선형(best-effort) 서비스만 제공한다. 즉, 포워딩시에 destination prefix(best-effort routing)만 이용, QoS가 반영되지 않으며(QoS가 반영된 route를 선택할 수 없다.), outgoing interface 에서 FIFO 큐잉을 하므로 어떠한 서비스 차등화도 불가능하며 모든 패킷을 동일하게 처리한다. 따라서, ISP가 서비스 차등화를 통한 과금을 통해 더 나은 이익을 얻을 수 없으며 인터넷을 통해 가상 사설망의 제공도 불가능하다.
2
Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
멀티서비스 초고속 IP 라우터의 요구 사항
������
Scalability(확장성)
������
Performance: 포워딩 엔진, 스위칭 패브릭, 멀티캐스트 지원
������
Wire-speed로 QOS 제공: Int-Serv/RSVP, Diff-Serv 지원
그림 2. 멀티 서비스 초고속 IP 라우터의 구조와 기능 요소
[그림2]에 초고속 라우터의 구조와 기능이 나타나 있다. 초고속 라우터의 핵심 요소로 크게 네트워크 프로세서(Network Processor), 포워딩 엔진(Forwarding engine), 라인 카드(Line Interface Card,네트워크 인터페이스) 그리고 스위칭 패브릭(Switching Fabric)을 들 수 있으며 그림 2는 포워딩 엔진이 각 라인 카드에 있는 경우이며 별도의 보드에 구성할 수 도 있다.
라인 카드에는 layer 2/3 기능부, 포워딩 엔진, queue 그리고 스케쥴러가 존재한다. 여기서 포워딩 엔진은 초고속 라우터 구현의 핵심 요소로 도착 패킷에 대한 헤더 프러세싱(wirespeed 패킷 필터링, wirespeed IP table lookup 등)의 기능을 수행한다. 스케쥴러는 차별화된 서비스 개념이 실제로 구현해주는 요소이다.
네트워크 프러세서는 라우팅 프로토콜(OSPF, RIP, BGP 등) 참여, 라우팅 테이블 생성 및 갱신, 각 라인 카드나 별도의 보드에 분산되어 있는 포워딩 엔진에 포워딩 테이블 갱신, 관리 기능 등을 수행한다.
스위칭 패브릭은 초고속 라우터 구현의 필수 요소로 기존의 공유 버스를 사용하지 않고 고성능 스위칭 능력을 제공하는 공간 분할형 스위칭 패브릭이 흔히 고려된다. 백본 라우터의 스위칭 패브릭은 수십 Gbps ~ 수 Tbps의 처리율을 보여야 하고 확장성(scalability), 견고성(robustness)을 제공해야 한다. 또한 멀티캐스트를 효율적으로 지원해야 한다.
3
Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
4
본 절에서는 각 부분별로 초고속 스위칭과 멀티서비스을 제공하기 위한 요구 사항을 구체적으로 생각해 본다.
(1) 확장성
인터넷 사용자의 증가와 각 용용의 요구 대역폭의 증가로 인터넷 트래픽은 현재 6개월에 두 배로 증가하고 있으며, 이를 감당하기 위해 현재 인터넷 백본 링크는 기존의 45Mbps급에서 OC-3(155Mbps)급으로 교체되었으며 최근에는 OC-12(622Mbps) 및 OC-48(2.5Gbps)로 교체중에 있다.
향후 대역폭 요구에 대한 지속적인 필요와 DWDM기술의 발달로 OC-48(2.4Gbps)가 확산되고, OC-192(10Gbps) 링크가 새로이 포설될 것으로 예측되고 있다.
따라서 이러한 추세를 따라가기 위해 확장성 있는 라우터가 요구되며 라우터 설계(스위칭 패브릭 및 버퍼링 방식, 포워딩 알고리즘)시 이와 같은 경향이 반영되어야 한다. 인터넷 서비스도 기존의 최선형 서비스에서 현재 통합 서비스 및 차별화 서비스가 도입되고 있으며 이러한 서비스 파라다임도 네트워크의 성장을 고려해 설계되어야 한다.
(2) Wire-speed IP table lookup
라우터의 가장 기본적인 기능은 라우팅 테이블 검색을 통해 패킷의 next-hop을 찾는 것이다. 이러한 과정이 초고속 라우터 구현의 핵심 기술이며 lookup engine 설계시 고려 사항은 다음과 같다.
- Lookup 알고리즘: LPM(longest prefix matching)
- 인터넷 백본 라우터의 라우트수: 50,000~200,000 routes
- 포트 스피드: OC-12, OC-48
- 라우트 엔트리 평균 갱신 주기: 2분
라우터는 가장 작은 크기의 패킷(TCP 의 경우 약 40바이트)이 연속해서 도착하는 경우에도 한 패킷에 대한 포워딩 결정이 다음 패킷도착전에 끝나야 하므로 IP table lookup이 wirespeed로 수행되어야 한다.
링크 대역폭이 1.2Gbps인 경우 1.2 x 109 (bit/sec) / 40 x 8 (bit/packet) = 266 nsec/packet의 시간내에 포워딩 결정(LPM)이 수행되어야 한다(이 경우 포워딩율은 3.7Mpps). 또한 차별화된 서비스를 제공하기 위해서는 포워딩 결정시 패킷의 destination prefix외에도 다른 인자(TCP/UDP port number, protocol ID, etc)를 이용해야 하며 이 경우에 destination prefix만을 이용하는 경우보다 더 긴 시간이 소요되며 이를 반영해야 한다.
라우터내에서 포워딩 결정이 끝나고 해당 큐에 저장되는 데 이 때 패킷에게 제공되는 서비스에 따라 달리 저장되고 서비스 받는다. 그런데 포워딩 시간이 길어지게 되면 포워딩을 기다리는 패킷의 지연 시간이 길어지게되고 이 동안은 어떠한 서비스 차별화도 제공될 수 없으므로 패킷의 포워딩은 wirespeed로 수행되어야 한다.
IP table lookup 속도는 메모리 access회수와 메모리 스피드에 의해 결정된다. lookup을 위해 요구되는 memory access 횟수는 lookup 알고리즘에 따라 다르며 예를 들어 기존의 대표적인 매치 알고리즘인
Netmanias Report: Tutorials on High-Speed Multiservice IP Router 
5
Patricia tree 방법의 경우 최대 32(IPv4)번의 메모리 access가 필요하다. 메모리 스피드는 DRAM의 경우 60-100 nsec이며 SRAM의 경우 10-20nsec가 소요된다. Patricia tree 알고리즘으로 longest prefix를 찾고 메모리로 DRAM을 사용하는 경우 패킷당 최대 100nsec×32=3.2μsec시간이 소요되며 따라서 기가급 라우터에서 적용될 수 없다.
따라서 lookup엔진에 대한 새로운 설계가 필요하며 두 가지 측면-lookup엔진의 물리적인 동작 속도 향상, 매칭 알고리즘 개선-에서 접근할 수 있으며 실제로는 두 가지가 병행된다.
첫 번째로 lookup엔진의 물리적인 동작 속도 향상은 소프트웨어 기반 방법과 하드웨어 기반 방법으로 나눌 수 있다. 소프트웨어 기반 방법은 고속의 RISK CPU를 사용하고 개선된 LPM 알고리즘을 통해 IP lookup을 위한 메모리 access횟수를 최소화함으로써 처리 속도를 증가시키는 방법으로 BBN의 MGR(Alpha 21164사용)이 있다. 초기 개발 비용이 적고 매칭 알고리즘에 유연성을 줄 수 있다는 장점은 있지만 고속의 CPU 가격이 비싸다는 단점과 cache hit율(즉, 트래픽 패턴)에 따라 라우터 성능이 좌우된다는 문제가 있다. 하드웨어 기반 방법은 매칭 알고리즘을 ASIC화하거나 매칭 알고리즘 로직과 메모리를 one chip화함으로써 고속의 lookup을 수행하는 접근방식으로 처리 속도가 빠르고 양산시 포워딩 엔진의 가격이 저렴해진다는 장점이 있다. Torrent사와 Rapid city사에서 이 방법을 취하고 있다. 하드웨어 기반 방법으로 CAM을 사용하는 방법도 사용되고 있으나 확장성 문제로 인해 백본용 라우터에는 적합지 않다.
두 번째로 최소한의 메모리 access로 longest match를 찾도록 알고리즘을 개선하는 방법이 있다. 기존의 검색 알고리즘인 Patricia tree, hashing, indexing 방법은 메모리 access횟수가 많고 확장성 결여(address prefix bit수 증가, 라우팅 테이블내 엔트리 증가시 검색 시간 증가)의 문제가 있어 기가급 라우터에서 적용될 수 없다. 최근에 검색 시간을 줄일 수 있는 새로운 알고리즘으로 학계에서 binary search on prefix length algorithm, compressed multi tries algorithm, single-level prefix expansion, controlled prefix expansion 등이 제시되고 있으나 대부분 특허 출원을 한 상태로 직접적인 활용은 어렵고 업계에서는 이 알고리즘에 대한 `vendor-proprietary\' solution을 가지고 있으나 이것이 현재 핵심 이슈이므로 공개를 하지 않고 있다. 따라서, 초고속 라우터의 핵심 기술인 포워딩 알고리즘의 개발이 시급하다.
(3) 초고속 스위칭
패킷 스위치 구조는 스위칭 패브릭 구조와 버퍼의 위치에 따라 구분할 수 있다. 기존 라우터에서 사용되던 버스 방식의 패브릭은 1Gbps급의 용량에는 적합하나 그 이상의 처리율을 제공하기 곤란하다. 따라서, 버스 접근 자체가 라우터의 성능에 병목이 된다. 스위칭 능력을 향상시키기 위해서는 ATM 스위치나 Gigabit Ethernet 스위치에서 널리 사용되는 크로스바 스위치가 적합하다.
즉, 패킷의 병렬적(동시) 전송이 가능한 공간 분할형 패브릭 사용하여 패브릭의 교환 속도는 링크의 전송율 수준을 유지하면서도 수십 Gbps의 처리율을 얻을 수 있다. 버퍼링 방식은 링크 속도가 기가급임을 감안하면 출력 버퍼링 방식이나 공유 버퍼링 방식은 거의 구현 불가능하다. 링크 속도가 2.4Gbps이고 포트수가 16이면 출력 버퍼와 공유 버퍼의 요구 대역폭은 38.4 Gbps가 된다. 라우터에서는 128Mbyte정도의 ATM 스위치보다 큰 버퍼가 필요하므로(셀저장이 아니고 패킷저장이므로) 이러한 버퍼의 구현은 불가능하거나 비용이 크다.
Netmanias Report: Tutorials on High‐Speed Multiservice IP Router 
  About NMC Consulting Group 
NMC Consulting Group was founded on year 2002 and is advanced, professional network consulting company which is specialized for IP Network area like FTTH, Metro 
Ethernet and IP/MPLS, Service area like IPTV and IMS lastly, Wireless network area like Mobile WIMAX and LTE.
 
Copyright ⓒ 1998‐2011 NMC Consulting Group. All rights reserved.
 
 
6
또한 포트수를 확장하려 할 때 버퍼 대역폭은 포트수에 비례하게 되어 확장에 어려움이 있다. 이에 반해 입력 버퍼링 방식은 스위칭 패브릭과 버퍼 메모리가 포트수에 상관없이 링크의 속도와 같으면 되므로 위의 예에서 2.4 Gbps의 대역폭만 제공하면 된다. 이러한 탁월한 확장성으로 인해 입력 버퍼링 방식이 고속의 스위치나 라우터의 구현에 가장 적합하다.
그러나 입력 버퍼링 방식은 HOL차단 현상으로 인해 최대 수율이 58.6%로 제한되며 이를 해소하기 위해 윈도우 방식, 목적지별 큐잉 방식, 가상 출력 버퍼링 방식, 입력단 확장 방식, 출력단 확장 방식 등 또는 이들을 함께 사용하는 방식등을 적용해 처리율을 높일 수 있다. 가상 출력 버퍼링 방식은 100%의 처리율을 보임이 최근 증명되어 졌고 윈도우 방식도 윈도우 크기에 따라 높은 처리율을 얻을 수 있다.
가상 출력큐를 두는 경우 그림 5에서 보듯이 입력단 충돌(input conflit)와 출력단 충돌(output conflict)가 발생하며 입력 버퍼 스케쥴링 엔진(중재기)이 이를 해소해 전송될 입출력단쌍을 결정한다. cisco 12000 GSR는 SLIP알고리즘으로 중재를 수행하며 MGR은 GWFA알고리즘으로 중재를 수행한다. 입력 버퍼 스케쥴링은 포트 속도가 2.4Gbps이고 패킷 크기가 64바이트로 가정하면 205 nsec이내에 수행되어야 하며 고성능 스위치에서 이 중재 알고리즘과 입력 버퍼 스케쥴링 엔진 구현이 핵심 기술이 된다. 또한 이 스케쥴러 설계시 멀티캐스트를 효과적으로 지원할 수 있도록 반영이 되어야 한다.
(4) Wire-speed, full-featured QoS
지금까지 인터넷은 망 내의 모든 트래픽을 동일하게 처리하는 \"best-effort\"라 불리는 단일 서비스 모델만을 제공하고 있으며, 응용별로 차별화된 QoS를 제공하지 않는다. 인터넷이 best-effort라는 단일 서비스 모델만을 제공했던 이유는 인터넷 응용의 특성이 유동적이기 때문이다. 즉 대부분의 인터넷 응용들은 어느 정도의 패킷 전송 지연이나 패킷 손실에 영향을 받지 않으므로 이와 같은 best-effort 서비스 모델만으로 인터넷 응용들을 지원할 수 있었다.
그러나 최근 들어 이와 같은 best-effort 모델로는 지원이 어려운 새로운 멀티미디어 응용들이 등장하고 있다. 음성이나 영상과 같은 이런 새로운 응용들은 종단간 지연과 지연 변이에 매우 엄격한 상한값을 요구 한다. 예를 들어 interactive한 음성 응용의 경우 종단간 지연은 150ms이내로 엄격하게 제한되어야 하며, 종단간 지연이 150ms를 넘어서 도착한 음성 패킷은 폐기된다.
이처럼 새로이 등장하고 있는 멀티미디어 응용들은 기존의 인터넷 데이터 응용과는 매우 상이한 특성을 가진다. 일반적으로 멀티미디어 응용들은 지연과 지연 변이 및 패킷 손실에 매우 민감하므로 현재의 인터넷 모델로는 이와 같은 실시간 멀티미디어 응용을 효과적으로 지원할 수 없으므로, 인터넷에서 서비스 품질 보장을 위한 노력인 Internet Engineering Task Force(IETF)를 중심으로 활발하게 진행 중에 있다.
인터넷에서 QOS 제공을 지원하기 위한 IETF의 대표적인 표준은 크게 두 가지로 Int-Serv와 Diff-Serv가 있으며 현재는 Diff-Serv에 비중이 넘어간 것 같고 Internet 2의 Qbone에서 이 Diff-Serv를 시험하고 있다.