The Design and Implementation of Open vSwitch 3

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

 

5. Caching-aware Packet Classification

 여기서는 flow caching 기능에 적합하도록 위해서 tuple search algorithm을 어떻게 개선했는지 설명한다.

 

5.1 Problem

 Open vSwitch userspace가 openFlow table을 통해 packet 처리함에 따라, forwarding decision 과정에서 참고되는 packet bit들을 추적한다. 이 packet header field에 대한 bit단위 추적은 megaflow entry를 생성하기에 매우 효율적이다.

 예를들어, OpenFlow table이 Ethernet 주소만 참조하는 경우, megaflows는 오로지 Ethernet address만 참조하는 entry를 생성하면 된다. 이 상태에서 port scan이 오더라도 L3과 L4 header는 와일드 카드가 처리되어 있기 때문에, 해당 megaflow entry는 이상적인 결과에 가까운 cache hit rate를 보일 것이다 (일반적으로 port scan은 Ethernet address는 고정되어 있다.)

 

 우리는 최적의/최소의 조건을 갖는 megaflow를 온라인에 효율적으로 생성하는 알고리즘을 모르기에, 최대한 좋은 근사 결과를 생성하도록 개발하는 것에 초점을 맞히었다. 포함되어야 하는 field를 매치하는데 실패하여 잘못된 packet forwarding이 발생하면 심각한 버그이기에, 그 근사는 필요보다 더 많은 field를 매칭하는데 편향되어 있다. 이어지는 section에서는 Open vSwitch에 포함된 이러한 류의 개선을 설명한다.

 

5.2 Tuple 우선순위 정렬

 Tuple space search classifier를 조회하는 것은 일반적으로 모든 tuple을 검사해야 한다. 심지어는 조회 초기에 match를 찾더라도, 뒤에 더 우선순위가 높은 tuple이 존재할 수 있기에 전부 검사해야 한다. 저자는 이를 각 tuple T 내의 flows 중 가장 높은 우선순위 값을(T.pri_max = Tuple T 내에 속한 Flow F들에 대해 max(F.pri)) 를 추적함으로써 개선했다. 그리고 tuple을 검사할 때 가장 높은 우선순위를 지닌 tuple부터 검색을 시작하도록 하여 매칭되는 플로우를 찾으면 곧바로 종료하도록 하였다. 동일한 우선순위 Tuple 내에서 flow는 모두 검사를 진행하며, 그 중에서 F.pri가 가장 높은 matched flow F를 찾는다. 만약 그 F를 찾았다면, 다음 Tuple은 검사하지 않는다.

 

 저자들은 사례로 VMware의 NVP controller OpenFlow를 살펴봤는데, 해당 테이블은 29개의 tuples을 포함하고 있었다. 그 중, 26개의 tuples들은 단일 flow priority (1개의 Tuple 내에서 F.pri가 동일함으로 이해)를 갖고 있었고, 이는 각각의 tuple에서 packet 처리 목적을 공유한다는 점에서 동일한 priority를 갖는다는 부분에서 직관적이다. 여기서 flow를 찾으면 중단해도 된다. 다른 tuples 중에 2개의 tuple에는 각각 2개의 flow가 포함되어 있었고, 각 튜플 내에서 매칭을 찾았다면 종료가 가능하다. 마지막 하나의 튜플에는 32767 ~ 32866의 F.pri를 갖는 5개의 flows가 포함되어 있었다. 만약, 32767의 F.pri가 현재 packet의 정답 flow였다면, T.pri_max > 32767인 tuple들도 반드시 검사가 되어야한다. (해당 tuple의 T.pri_max는 32866이다. 다른 tuple중에 어느 tuple의 T.pri_max가 32800이었다면, 해당 tuple내에 packet과 매칭 가능성이 있는 더 높은 priority를 지닌 flow F가 존재할 수 있다. 따라서 32767의 F.pri가 매칭 되었더라도 그 이상의 T.pri_max를 지닌 tuple T는 모두 조사해야한다.) 

 

5.3 Staged Lookup

 Tuple space search는 hash table을 lookup하여 각 tuple을 조사한다. 단, OVS 알고리즘은 megaflow matching 조건을 구성하기에, 이 hash table lookup은 tuple 검색이 실패하더라도 tuple에 포함된 모든 field가 megaflow의 조건을 match해야 한다. 해당 field와 bit가 현재까지의 조회에 영향을 주었을 수 있기 때문 (잘 이해가 가지 않는 문장). 만약 tuple이 TCP source port와 같이 자주 변화하는 field에 매치된다면, 생성된 megaflow는 microflow보다 성능이 좋지 않을 수 있다. (여기서는 L2 ~ L4 통으로 보관하는 megaflow가 자주 변화하는 TCP source port때문에 갈아 치워진다면 낭비라는 것을 말하고 싶은 것 같다.) 이 부분은 개선의 여지가 있다. 만약 일부 field에 대해서만 tuple을 조회하는데 실패할 가능성이 있는 tuple이라면, 이는 생성된 megaflow에 대해서 일부에 대해서만 match를 체크해도 괜찮을 것이다.  

 

 모든 field를 hash하여 하나의 hash table을 구성하는 방법은 앞서 언급한 방법의 최적화를 어렵게 한다. 일부 원하는 field만 골라내어 key로 삼을 수 없기 때문. 그래서 하나의 field를 노드로 하는 trie 자료구조를 고려했으나, memory access가 기존에 상수였던 O(1)에서 field 개수만큼인 O(n)으로 증가한다. 따라서 per-field 해시 테이블은 이 부분에서 단점이 있었고, OpenFlow는 수십만개의 flow를 갖고 있기에 이는 부적합하다고 판단했다.

 

 그래서 고른 해결책은 metadata (in_port), L2, L3, L4로 정적으로 분리하는 것이었다. 그리고 tuple들을 하나의 해시 테이블이 아니라, 각각 stage라고 불리는 4개의 해시 테이블을 통해 관리하도록 하였다. 각각은 metadata / metadata + L2 / metadat + L2 + L3 / 그리고 마지막 해시 테이블은 모두를 포함한 내용을 갖고 있다. 이들은 순차적으로 조회가 이루어진다. 만약 특정 부분에서 match가 실패하면, 조회를 시도하던 튜플 자체의 결과는 실패가 되며, 마지막에 조회했던 데이터만 megaflow match에 추가하면 된다.

 

 이 방식은 L2 ~ L4 와 같은 layer-based 말고도 어떠한 종류의 field 집합에도 적용이 가능하다. 다만, 저자들이 이렇게 나눈 이유는 L4가 L2, L3 등의 바깥 정보보다 더 자주 바뀌기 때문이라고 한다. 각 stage들은 이전 stage들을 모두 포함하고 있다. 이러한 배열을 취한 이유는 hash 연산을 차례로 수행하가며 hash 연산 비용을 줄이기 위함이라고 한다.

 

 기존의 hash lookup은 1회를 요구했으나 현재는 4회가 되어서, 성능이 4배 느려졌을 것이라고 예상할 수 있다. 하지만 실제 실험은 조회를 early stage에서 중단하여 full hash를 연산할 필요가 사라져버린 경우때문에 성능이 미약하게 상승하는 결과를 보였다. 

 

5.4 Prefix Tracking

 OpenFlow의 Flow들은 routing을 결정하기 위하여 IPv4 또는 IPv6의 subnet을 매치해야 한다. 만약 동일한 필드의 같은 크기만큼에 대해서 매치 (e.g., /16)하는 것이라면 megaflow를 생성해도 될 것이다. 반면에, 만약 일반 subnet routing처럼 서로 다른 flow를 다른 subnet size에 매치하는 것은 megaflow로 하여금 longest subnet prefix를 매치하도록 요구한다. (일반적인 routing에서는 longest prefix의 우선순위가 높다.) 

 예를 들어, 10/8과 10.1.2.3/32의 flow가 존재하는 상태에서 10.5.6.7의 packet이 도착한다면, 사실 10.5/16의 megaflow를 datapath에 추가하는 것은 안전할 것이다. 10.5/16과 10.1.2.3/32가 겹치지 않기 때문. 하지만 Open vSwitch만의 최적화 없이는 OvS가 10.5.6.7/32를 추가하게 된다. (/8, /16, /24, /32 단위는 예시이고, ovs는 bit-wise subnet mask를 지원)

 

 그래서 OvS는 IPv4와 IPv6의 fields에 대해 trie 자료구조를 이용하여 최적화를 시도했다. 만약 flow table에서 IP address에 대해 매치가 된다면, classifier는 skip 가능한 tuple을 알아내고 megaflow의 최대 prefix 길이를 알아내기 위해서 tuple space search 전에 해당 field에 대해 LPM (Longest Prefix Match)를 수행한다. 예시로 다음과 같은 IPv4 field 대상 OpenFlow table이 있다고 가정하자.

20	/8
10.1	/16
10.2	/16
10.1.3	/24
10.1.4.5	/32

위 flow들은 다음과 같은 trie로 구성된다. 여기서 실선 원은 위에 표에서 실제로 존재하는 subnet을 의미하고, 점선 원은 오로지 child를 위해서만 존재하는 node를 의미한다.

 match bit을 결정하기 위해서, Open vSwitch는 위 trie를 root부터 차례로 조사한다.

 

(1) 만약 조사가 leaf node에 도달하면, megaflow는 남은 address bit을 매치할 필요가 없게 된다. 예를 들어, 10.1.3.5의 경우에는 10.1.3/24를 의미하고, 20.0.5.1의 경우에는 20/8을 의미한다.

 

(2) 만약 조사를 시행했는데 실선 원에 없는 경우에는 찾지 못한 bit를 포함하여 적절한 megaflow를 생성해야 한다. 예를 들어, 10.3.5.1의 경우에는 10.3/16을, 30.1.5.2의 경우에는 30/8을 구성해야 한다.

 

(3) 만약 조사를 시행했으나 중간에서 멈춘 경우에는 flow table 내에서 그 이상의 prefix matching을 요구하지 않는 경우이다. 따라서 classifier는 /24나 /32 prefix에 대한 tuple 조사는 시행하지 않아도 된다. 예를 들어, 10.1.6.1은 node ①에서 끝날 것이다. 

 

 Figure 3은 위에서 설명했던 prefix matching algorithm의 의사코드를 보여준다. 각 노드는 bits라는 member를 갖고 있고, child node를 연결하기 위한 left와 right, 그리고 노드에 관련되어 있는 rule의 개수를 저장하는 n_rules를 갖고 있다. 위 알고리즘은 match되어야 하는 bit의 수와 tuple searching skip이 가능한지 여부를 의미하는 bit-array가 담긴 값을 반환한다.

 

 해당 알고리즘은 LPM 조회를 최적화하면서도, IP prefix를 명시적으로 match를 시도하지 않는 megaflow의 성능도 개선한다. OpenFlow에서는 LPM을 구현하기 위하여, 긴 prefix는 더 높은 우선순위를 가져야 한다. 이는 Section 5.2의 tuple priority sorting 최적화와 맞물려서 tuple search를 몇 개 skip할 수 있도록 해준다. 하지만 이는 가장 높은 우선순위에 longest prefix가 위치하게 됨에 따라 megaflow를 약화시키는 결과를 가져온다. 여기서 위 알고리즘의 장점으로는 ACL과 같이 특정 호스트에 적용되는 정책에 대한 megaflow들이 full IP address를 매칭하도록 하는 것을 방지한다. 그리고 megaflow entry들이 host를 구분하기에 충분한 high order bits만에 대해 매치만 하면 되도록 해준다. (추가 이해 필요)

 

5.5 Classifier Partitioning

 Tuple space search 조회는 match 가능성이 없는 tuple들을 스킵함으로써 더더욱 줄일 수 있다. Openflow는 packet이 흐르는 동안 classifier를 통해 metadata field의 값을 설정할 수 있고, match 조건으로서 활용할 수도 있다. Open vSwitch는 이 classifier를 특정 metadata field를 기준으로 분리한다. 만약 field에 있는 현재 값이 특정 tuple의 어느 값에도 매치되지 않는다면 모두 스킵할 수 있다.

 

6. Cache Invalidation

 Cache 시스템의 장점은 성능, 단점은 관리에 있다. Open vSwitch cache는 몇 가지 이유로 인해 업데이트를 필요로 한다. 명백한 이유로는 컨트롤러가 OpenFlow의 table을 변경한 경우일 것이다. Feature 활성화 / 비활성화, 포트 추가 제거 등의 다양한 재설정은 packet handling에 영향을 줄 수 있다. CFM, BFD와 같이 연결 감지를 위한 프로토콜, spanning tree protocol과 같이 루프 감지 및 회피 등등도 영향을 줄 수 있다. 즉, 몇몇 OpenFlow 활동과 Open vSwitch의 확장은 네트워크 상태에 영향을 줄 수 있다.

 

 이상적인 상태에서 Open vSwitch는 명확하게 영향을 받는 megaflow를 찾아낼 수 있다. MAC learning 포트 변경과 같이 직관적인 event에서는 datapath에서 해당 MAC을 사용중이던 flow를 찾아 update를 진행하면 된다. 하지만 OpenFlow 모델의 범용성은 몇몇 사례에서 정확하게 flow를 찾아내는 것을 어렵게 만든다. 예를 들어, OpenFlow table에 새로운 flow를 추가한 경우를 들 수 있다. 이미 기존 datapath에 동일하게 매치되는 flow가 있었고, 이들이 새롭게 추가되는 flow보다 우선순위가 낮다면 기존 dp flow들의 행동 양상이 달라질 것이다. 하지만 이들을 효율적으로 모두 추출해내는 방법이 의문이다. 결국 저자는 일반적인 케이스에서 명확하게 추출하는 방법들은 실용적이지 못하다라고 결론을 맺었다.

 

 Open vSwitch 초창기 버전은 datapath flow의 행동에 변화를 요구하는 event의 종류를 크게 2가지로 나누었다. (1) 변화의 영향이 너무 광범위해서 정확하게 flow를 뽑아낼 수 없는 경우, (2) 변화의 영향을 좁힐 수 있는 경우.

 

 (1) 변화의 영향이 너무 광범위해서 정확하게 flow를 뽑아낼 수 없는 경우: 이 경우에는 Open vSwitch가 datapath flow들을 전수조사 해야한다. 각 flow들은 OpenFlow flow table을 처음 구성된 양 모두 거치며, 현재 datapath에 있는 flow와 비교를 수행한다. 만약 datapath에 flow가 많았다면 굉장한 시간을 필요로 하겠지만 실 상황에서 문제가 있었던 적은 없었다고 한다. 이는 datapath에 flow가 많은 상황 자체는 network의 부하가 많은 경우밖에 없고, 이 상황에서 CPU를 많이 사용하는 것은 합리적이기 때문이라고 이야기한다. 다만 실제 문제는 Open vSwitch가 single-threaded였어서, flow 전수조사는 새로이 오는 packet의 upcall을 처리하는데 blocking을 한다는 문제가 있었다. 이는 해당 packet들에 대하여 flow setup하는데 엄청난 latency 증가를 가져왔고, 결국 flow setup rate에 한계를 만들어버리는 원인이 되었다. 이러한 문제를 최소화하기 위해서 Open vSwitch 2.0부터는 datapath에 cache되는 flow의 최대 개수를 약 1,000개로 제한하였고, 몇몇 최적화와 함께 2,500개로 증가시켜 제한하도록 하였다.

 

 (2) 변화의 영향을 좁힐 수 있는 경우: 해당 예시로는 MAC learning table이 바뀐 경우가 있다. 초창기 Open vSwitch 버전에서는 tags 라고 불리는 기법을 이용해서 최적화하여 구현하였다. 만약 변화가 발생하여 megaflow 수정이 필요한 속성들은 tag를 하나씩 갖고 있다. 또한, 각 megaflow는 actions이 의존하는 속성들에 대한 tags와 연결되어 있다. 만약, action이 packet을 port x로 보내는 것일 경우, 해당 port x에 대해 destination MAC address가 학습되어 있을 것이고 megaflow는 학습된 이와 관련하여 tag와 연결되어 있다. 추후에 MAC learned port가 변경된다면, Open vSwitch는 해당 megaflow에 tag를 추가하여 변화를 누적한다. 그리고 Open vSwitch는 event가 발생한 경우에, megaflow table을 훑어서 각 megaflow entry가 해당 event와 관련된 tag를 갖고 있는지 검사한 뒤, 실제로 action을 수정해야 하는 경우 작업을 진행한다.

 

 시간이 지남에 따라 controller는 점차 정교해지고 flow table은 복잡해졌다. 그리고 Open vSwitch는 더 많은 actions을 추가해왔고 각 datapath flow들은 더 많은 tag들을 갖게 되었다. 그래서 저자는 앞서 이야기한 tag를 Bloom filter로서 구현했다. 이는 각 추가적인 tag가 "false positivs"를 발생시킬 소 있고, 결국 현재는 상태 변화가 발생할 때 대부분 혹은 모든 flow들이 검사를 필요로 하게 되었다. 최종적으로 Open vSwitch 2.0부터는 tag의 효율이 저하되었고, 코드를 간단히 만들기 위해 tags 기능을 제거, 항상 모든 datapath flow table을 revalidating 하도록 재구현하였다 (실제로 Open vSwitch architecturd에서 revalidator라고 칭하는 듯 하다). 

 

 Open vSwitch 2.0에서는 flow setup latency는 줄이되 기존의 tags 기법을 대체할 방법을 적용하려 노력했다. 저자는 userspace에 thread 적용하고, flow setup 작업을 각 thread에게 배분하여 revalidation뒤에 기다릴 필요가 없도록 하였다. 다만, datapath flow 제거는 여전히 single thread로 남아있어 flow setup을 수행하는 multi-thread의 속도를 따라갈 수 없었다. Flow setup 작업이 상당할 때에는 그만큼 flow 제거 성능도 중요하다. Datapath flow 공간이 넘치지 않도록 새롭게 추가되는 flow들을 위한 공간을 만들어야 하기 때문. 그래서 Open vSwitch 2.1부터는 cache revalidation을 위하여 multiple dedicated thread 도입했다. 이 multi-thread의 도입은 revalidation의 성능을 flow setup 작업량 부하에 맞추어서 자유롭게 조절할 수 있도록 하였으며, 그 결과 kernel의 cache maximum size를 200,000개까지 늘릴 수 있었다. 실제 최대값은 revalidation time이 1초 이하로 수행되도록 runtime에 조절된다.

 

 Open vSwitch의 userspace는 kernel module을 폴링하면서 datapath의 모든 flow에 대한 packet 개수와 byte 개수를 cache 통계를 주기적 (약 1초에 1회)으로 얻어온다. 이 통계는 어떤 datapath flow가 유용하고 kernel에 남아있어야 할 지, 그리고 어떤 datapath가 적정량의 packet을 처리하지 못해 방출해도 되는지 결정하는데 주로 사용된다. Table의 최대 크기에 많이 미치지 못하는 경우에는 10초간 dp에 존재하도록 기본값으로 설정되어 있으며, 이 값은 조절할 수 있다. (단, table의 최대값을 넘어가는 순간 Open vSwitch는 table의 규모가 최대한 빠르게 줄어들 수 있도록 이 값을 줄인다.) Kernel module을 polling함으로써 얻어온 통계는 per-flow packet과 byte count 통계를 구현하는데 사용될 수 있고, flow idle timeout feature를 구현하는데 사용될 수 있다. 이는 OpenFlow 통계가 주기적으로 업데이트 됨을 의미한다.

 

 지금까지 userspace가 datapath megaflow cache를 어떻게 invalidate 시키는지 설명했다. Microflow cache를 관리하는 방법은 훨씬 간단하다. Microflow cache entry는 tuple space search 조회하기 위한 first hash table의 힌트 역할을 한다. 그러므로 packet이 처음 들어왔을 때 microflow cache entry가 stale 상태인지 감지가 가능하고 수정된다. Microflow cache는 그 크기가 고정되어 있으며, 새로운 entry의 추가는 기존의 entry를 교체하는 방식으로 이루어진다. 따라서 주기적으로 old entry를 제거할 필요가 없다. 기존 entry 선택 방식은 단순함을 위해 랜덤으로 뽑으며, 이 방식이 실 사용에 효과적인 것으로 나타났다.