The Design and Implementation of Open vSwitch 2

 해당 포스트는 NSDI '15 https://www.usenix.org/system/files/conference/nsdi15/nsdi15-paper-pfaff.pdf 를 번역해서 정리한 포스트입니다.

 

3. 디자인

3.1 Overview

 Open vSwitch는 두 가지 구성 요소로 이루어져있다. (1) userspace 데몬이자 운영체제와 상관없이 동일한 ovs-vswitchd와 (2) 성능을 위해 OS 마다 작성된 datapath kernel module이다. Figure 1은 이 두 개의 OVS component가 어떻게 협동하여 pacekt을 전달하는지 나타낸다. Kernel datapath가 가장 먼저 physical NIC이나 VM의 virtual NIC으로부터 packet 수신한다. ovs-vswitchd는 datapath에게 그 수신한 packet을 어떻게 처리할 것인지 datapath에게 지시를 해놓거나 그렇지 않았을 수도 있다. 만약 지시를 해 놓은 상태라면, datapath module은 단순하게 해당 명령을 실행한다. 이 실행을 actions라고 칭하며, ovs-vswitchd에 의해 주어진다. 이 actions은 packet을 수정하거나, smapling하거나, drop을 지시하는 등을 의미할 수 있다. 만약 지시를 해 놓지 않은 상태라면, datapath kernel module은 userspace의 ovs-vswithcd에게 해당 packet을 전달하고 ovs-vswtichㅇ가 어떻게 처리할 지 결정한다. 그리고 다시 packet과 처리 방법을 datapath kernel module에게 전달하여 해결한다. 일반적으로 ovs-vswitchd는 datapath kernel module이 추후에 수신하는 비슷한 packet을 처리할 수 있도록 해당 action을 cache하라고 지시한다.

 

 Open vSwitch는 이 flow caching 기법을 굉장히 진화시켜왔다. 초기에는 microflow cache였으며, 시간이 지나 확장되어 megaflow cache가 추가되었다. 이는 section 4에서 설명한다. 

 Open vSwitch의 forwarding 룰을 제어하는 주요 방법은 OpenFlow이다. 간단한 binary protocol을 통해서 OpenFLow는 컨트롤러가 flow tables 및 그 flows들을 추가/제거/수정/감독 및 통계 수집 등을 수행할 수 있다. ovs-vswitchd는 OpenFlow의 flow tables를 SDN controller로부터 수신하여, 위에 서술한대로 packet 수신, action 결정, datapath에 cache를 수행한다. 이 방식은 datapath module과 상위의 OpenFlow protocol과 독립되어 있어서 구조를 간단하게 한다. OpenFlow 컨트롤러 입장에서는 ovs-vswithcd와 datapath의 user-kernel 분리와 caching기법에 관여하지 않기 때문. 컨트롤러 관점에서는 단순히 packet들이 OpenFlow flow table을 훑으며 actions을 결정해 실행하는 모습으로만 보인다.

 

3.2 Packet 분류

 Packet 분류 알고리즘은 범용 프로세서 위에서는 비용이 비싸다. 특히 match를 시켜야 하는 OpenFlow context에서의 packet 분류는 비용이 특히 비싼데, 이는 임의의 ethernet 주소, IPv4 / IPv6 주소, TCP / UDP port, ingress port 등 다른 많은 필드들을 테스트 해야하기 때문이다. 

 

 Open vSwitch는 packet 분류를 위해 kernel과 userspace 모두 tuple space search classifier 기법을 사용한다. Tuple space search classifier는 flow table을 하나의 hash table로서 구현했다. 만약, controller가 다른 형태의 match를 가진 새로운 flow를 추가한다면 classifier는 두 번째 hash table을 추가할 것이다. 하나의 search 과정은 이 두 개의 hash tables를 모두 봐야 한다. 만약 match 되는 내용이 없다면, 현 flow table은 해당 match를 포함하고 있지 않은 것이다. 하나의 hash table이 매치된다면 그 flow는 flow table에 있어서 매치된 것이다. 만약 두 개의 hash table에서 매치가 된다면 그 결과는 더 높은 우선순위를 갖고 있는 것이다. 컨트롤러가 지속적으로 새로운 match를 가진 flow를 추가함에 따라 이에 맞추어 classifier는 유사하게 hash table을 확장해 나갈 것이고, 하나의 search는 모든 hash table을 들여다보게 될 것이다. (완벽히 와닿지 않아서 추후에 알고리즘 이해가 조금 더 필요하다..)

 

TSS 알고리즘 예제 (http://www.wenjunli.com/CutTSS/CutTSS.pdf)

 이 방식은 은근 복잡하고 최신 기법과는 조금 거리가 있지만, 실 사용에서 잘 동작하며 다음과 같은 3가지의 매력 포인트를 갖고 있다. (1) 이는 상수 시간의 flow table update를 지원한다. Flow table의 업데이트는 하나의 single table 수정과 같기때문. 이는 중앙화된 컨트롤러가 flow를 추가/제거를 자주 발생시키는 가상화 환경에 적합하다. (2) tuple space search 기법은 알고리즘의 수정 없이 수많은 packet header field들을 일반화하여 처리할 수 있다. (3) tuple space search 기법은 flow의 수에 따라 메모리 사용량이 선형 비례한다. 

 

3.3 프로그래밍 모델로서의 OpenFlow

 초기에는 Open vSwitch가 reactive (반응적인) flow programming model에 집중했었다. 즉, 컨트롤러가 트래픽에 응답하고, 지원하는 OpenFlow field에 대해 microflow를 설치하는 방식이었다. 이 방식은 software switch와 컨트롤러를 지원하기 쉽고, 초기 연구에서도 이 방식은 충분하다고 제안했었다. 하지만 점차 규모가 커지자, microflow reactive 방식은 비실용적임을 깨달았고, Open vSwitch는 성능 비용을 줄이기 위해 proactive 모델을 채택해야만 하게 되었다.

 

 OpenFlow 1.0에서는 microflow가 약 275 bit의 정보를 갖고 있었다. 따라서 모든 microfvlow에 대한 flow table은 2^275 혹은 그 이상의 엔트리를 가질 수 있었다. (flow table을 작성할 때 총 275개의 bit 각각에 대해 0 혹은 1이 가능하므로 2^275의 엔트리가 가능하다고 이해) 따라서, proactive 접근을 위해서는 모든 가능한 packet을 커버할 수 있도록 wildcard matching 지원을 필요로 했다. 이를 단일 테이블로 실행하기에는 "cross-product problem"의 문제가 있었다. Packet header의 A field가 n1의 값을 갖는 조건과 B field가 n2의 값을 갖는 조건을 만들기 위해서는, single table에서 n1 X n2를 동시에 조건으로 하는 flow entry를 넣어야 한다. 이들은 독립된 field인데도 불구하고 말이다. Open vSwitch에서는 이를 해결하고자 multiple flow tables 구성할 수 있도록 하였다. 그리고 resubmit action을 도입하여 하나의 packet이 여러 tables을, 심지어는 같은 table을 여러번 거쳐갈 수 있도록 하였으며, 결과 action을 aggregate 하도록 하였다. 위 언급된 사례에서는 table 1에 A field를 처리하는 n1 flow를, table 2에 B field를 처리하는 n2 flow를 넣을 수 있게 됨으로써 "cross-product problem"을 해결할 수 있었다. 더 나아가, resubmit action은 branch 역할을 가능케 만들었다. OpenFlow 1.1에서는 mutli-table support 기능을 추가하긴 했지만, Open vSwitch에서는 backward compatibility (이전 버전 호환성)을 위해 resubmit action을 그대로 두었다.

 

 이제 controller는 Open vSwitch의 multiple flow table을 chaining을 구성하면서 다양한 프로그램을 구현할 수 있게 되었다. 하지만 컨트롤러는 잠시 데이터를 보관하기 위한 임시 저장소에 대한 접근이 불가능했다. 이를 해결하기 위해서 Open vSwitch는 OpenfFlow의 기능을 색다르게 확장하였다. Flow table의 추가 field로서 "register"라고 불리는 meta-data field를 추가하였으며, 이 "register"는 flow table에서 조건으로서 사용이 가능하고 actions을 이용해 "register" 값을 수정하거나 복사할 수 있다. 

 

 OpenFlow는 flow를 제어하기 위해 특화되어있다. 이는 OpenFlow switch를 생성하거나 삭제할 수 없으며, port를 추가하거나 제거, QoS queue 설정, OpenFlow controller와 switch 연결, STP (Spanning Tree Protocol)을 활성 혹은 비활성 등을 할 수 없다. Open vSwitch에서는 이들을 별도의 configuration database라는 구성 요소에서 관리한다. 이 db에 접근하기 위해서는 Figure 1에 나타나있는 것 처럼, SDN controller가 ovsdb-server와 OVSDB protocol을 이용해 통신해야 한다. 일반적으로 Open vswitch에서는 데이터를 오래 보관하고 관리해야하는 ovsdb와는 다르게 OpenFlow는 빠르게 변화하고 수명이 짧은 flow tables을 컨트롤하는 역할을 담당한다. 

 

4. Flow Cache Design

4.1 Microflow Caching

 2007년, Linux에서 시작된 Open vSwitch의 개발 코드는 모든 것을 kernel에서 구현했었고, 좋은 성능을 얻을 수 있었다. NIC 혹은 VM에서 packetㅇ르 수신하고, OpenFlow table을 이용해 분류한 뒤, 최종적으로 다른 port로 보냈다. 하지만 이 방식은 곧 kernel 개발 및 배포, 수정의 어려움 때문에 비실용적인 방법이 되었다. 또한, in-kernel OpenFlow 구현은 Linux upstream으로서 수용하기 어려웠다. 

 

 그래서 우리의 해결책은 kernel module을 OpenFlow의 packet header를 지원하는 microflow cache, 정확히 일치해야하는 하나의 cache로서 재구현하는 것을 택했다. 이는 kernel module을 하나의 단순한 해쉬 테이블로 재구현하면 됐으므로, 기존의 복잡하던 packet classifier, 임의 field 지원 및 masking 등의 기능을 필요로 하지 않아 kernel module을 극단적으로 간단하게 만들었다. 이 디자인에서는 cache entry의 정보가 매우 자잘하게 세분화 되어있고, 하나의 connection에서 최대한의 packet을 매치할 수 있도록 하였다. 만약 네트워크 상에서 전송 경로가 바뀌어 TTL값이 기존과 달라지는 경우에도 cache miss 판정을 내렸으며, userspace로 packet을 보내서 OpenFlow의 결정을 받도록 하였다. 이 구현에서는 성능 핵심 결정 요소는 flow setup time, 그리고 userspace에게 microflow miss를 전달하고 userspace의 응답을 기다리는 것에 있다.

 

  Open vSwitch의 버전이 증가함에 따라 flow setup time을 줄이기 위한 노력들이 많이 있었다. 예를 들어 Flow setup을 batching (한번에 모아서 처리)하여 처리하는 것은 system call 횟수를 줄여 24%의 성능 향상을 가져올 수 있었다. 그리고 flow setup 작업을 userspace에서 multi-thread로 처리하도록 하여 multi-core의 이점을 얻을 수 있도록 하였다. Cuckoo switch 영감을 받아 concurrent cuckoo hashing을 도입한다던가, RCU 기술등을 도입하여 flow table에 대해 nonblocking multiple-reader, single-writer등을 도입하는 등의 최적화도 포함하였다.

 

4.2 Megaflow Caching

 Microflow cache가 대부분의 트래픽 패턴에서 잘 동작하기는 했으나, short lived connection이 많은 경우에 성능 저하를 심하게 겪었다. 많은 packet들이 cache miss를 겪었고, 결국 kernel-userspace 경계를 넘나들며 비싼 packet classification 과정을 처리해야 했다. 앞서 언급한 batching과 multithreading이 어느정도 부담을 완화하기는 했지만, 충분하지는 못했다.

 

OVS PPT in NSDI

 그래서 저자들은 microflow를 megaflow로 교체했다. megaflow cache는 일반화된 matching을 지원하는 lookup table이다. 즉, 하나의 cache entry가 단 하나의 connection을 처리하는 것이 아니라, 수많은 트래픽을 처리할 수 있도록 한 것이다. 사실 어떻게 보면 일반적인 packet field matching을 결정한다는 점에서 OpenFlow와 비슷하지만, megaflow cache가 다음과 같은 두가지 이유로 runtime에 훨씬 단순했다. (1) Priority가 없다. 따라서 packet 분류를 빠르게 할 수 있었다. Kernel 내부의 packet 분류는 기존의 priority를 따라 쭉 훑어야 했던 방식과는 달리, match를 찾는 순간 바로 종료할 수 있었다. (2) 단 하나의 megaflow classifier만 존재한다. 즉, packet을 분류하는 과정에서 여러 megaflow classifier를 거쳐야 하는 pipeline이 존재하지 않는다. 

 

 Megaflow lookup 비용은 flow priority를 지원하지 않음에도 불구하고 일반 packet classifier와 비슷하다. Megaflow classifier에서 찾는 과정은 hash table에서 match를 찾을 때까지 일일이 뒤져야 한다. 만약 각 hash table이 균등하게 match를 갖고 있다고 가정하면, matching을 찾기까지 평균적으로 (n+1) / 2 table을 검사해야할 것이고, 만약 match가 없는 packet이라면 n개의 hash table을 검사해야 할 것이다. 일반적으로 n > 1이므로 mega flow가 micro flow보다 table lookup 을 더 요구하는 편이다. 즉, microflow cache miss가 발생해서 userspace를 한 번 다녀오는 과정이 megaflow lookup 비용보다 비싸다는 가정 하에서 megaflow는 이익을 얻을 수 있다.

 

 Open vSwitch는 이 megaflow의 비용을 줄이기 위해서 microflow cache를 megaflow보다 앞선 first-level cache로 두었다. 이 microflow cache는 megaflow와 매핑된다. 따라서 microflow로 들어오는 첫 번째 packet은 kernel의 meagflow table을 거쳐서 엔트리를 찾으며, 그 다음 EMC (Exact Match Cache)는 연속으로 들어오는 packet에 대해 동일한 megaflow로 바로 향할 수 있도록 한다. (action은 microflow에 포함이 안되어있나..?) 이는 megaflow의 비용을 per-packet에서 per-microflow로 줄인다. (microflow가 없는 경우에는 매 packet마다 megaflow를 모두 훑어야 했으나, 이제는 microflow가 바뀔 때만 훑으면 된다.) 이 EMC는 성능 향상을 제외하고는 활동이 userspace에게 보이지 않는 진정한 cache이다.

 

 Megaflow의 flow table은 userspace OpenFlow flow의 모든 가능성을 product한 결과의 일부일 것이다. 하지만 사전에 미리 이러한 megaflow flow table을 생성하여 놓는 것은 굉장한 연산을 필요로 한다. 따라서 이를 피하고, 오로지 현재 흐르는 traffic에 필요한 entry들로만 구성하기 위하여 Open vSwitch의 userspace daemon은 cache entry를 점진적으로, 그리고 반응적으로 준비한다 (lazy computation). Open vSwitch는 userspace flow table에서 packet 처리하고 분류하는데, 이 과정에서 검사되는 bit들을 추적한다. 그리고 생성된 megaflow의 결과에서 유효한 필드 (userspace flow table을 훑으면서 검사에 사용된 bit)는 이후 검사에서 반드시 일치해야 한다 (상단 OVS PPT in NSDI 그림 참고). 예를 들어, 만약 classifier가 OpenFlow table pipeline 과정에서 IP destination field를 확인했다면, megaflow cache entry도 destination IP field를 조건으로 포함해야 한다.