장룡호
(Inha University Computer Science Engineering)
,
정창훈
(Inha University Computer Science Engineering)
,
김근영
(Inha University Computer Science Engineering)
,
양대헌
(Inha University Computer Science Engineering)
,
이경희
(The University of Suwon Electrical Engineering)
인터넷 트래픽양의 급증에 따라 고속 라우터의 수요가 많아졌다. 트래픽 통계 또는 보안 등의 목적으로 라우터에서 패킷을 측정해야 하는데 고속 라우터의 특성상 메모리공간이 제한적이다. RCC는 적은 메모리로 트래픽을 정확하고 효율적으로 측정하는 방법을 제시했다. RCC에서는 트래픽을 측정하는데 큰 Flow를 추가적인 Quadratic Probing 기반 해시 테이블에 누적하는 방법 사용한다. 그런데 Quadratic Probing은 적은 메모리 또는 메모리 사용률이 많은 상황에서 연산량이 많으며, 특히 갱신 또는 실시간 조회가 자주 발생하는 시스템에서 오버헤드가 크다. 이 논문에서는 RCC의 특성을 분석하고 실험을 통해 Quadratic Probing의 문제점을 증명하며 갱신 또는 조회에 효율적인 Cuckoo Hashing을 사용하여 RCC의 성능을 개선한다. 실험 결과에 따르면 RCC에서 Cuckoo Hashing을 사용할 때 메모리 사용률이 높은 상황에서도 높은 정확도를 보여주었고, 효율적으로 트래픽을 측정할 수 있었다.
인터넷 트래픽양의 급증에 따라 고속 라우터의 수요가 많아졌다. 트래픽 통계 또는 보안 등의 목적으로 라우터에서 패킷을 측정해야 하는데 고속 라우터의 특성상 메모리공간이 제한적이다. RCC는 적은 메모리로 트래픽을 정확하고 효율적으로 측정하는 방법을 제시했다. RCC에서는 트래픽을 측정하는데 큰 Flow를 추가적인 Quadratic Probing 기반 해시 테이블에 누적하는 방법 사용한다. 그런데 Quadratic Probing은 적은 메모리 또는 메모리 사용률이 많은 상황에서 연산량이 많으며, 특히 갱신 또는 실시간 조회가 자주 발생하는 시스템에서 오버헤드가 크다. 이 논문에서는 RCC의 특성을 분석하고 실험을 통해 Quadratic Probing의 문제점을 증명하며 갱신 또는 조회에 효율적인 Cuckoo Hashing을 사용하여 RCC의 성능을 개선한다. 실험 결과에 따르면 RCC에서 Cuckoo Hashing을 사용할 때 메모리 사용률이 높은 상황에서도 높은 정확도를 보여주었고, 효율적으로 트래픽을 측정할 수 있었다.
According to rapidly increasing of network traffics, necessity of high-speed router also increased. For various purposes, like traffic statistic and security, traffic measurement function should performed by router. However, because of the nature of high-speed router, memory resource of router was l...
According to rapidly increasing of network traffics, necessity of high-speed router also increased. For various purposes, like traffic statistic and security, traffic measurement function should performed by router. However, because of the nature of high-speed router, memory resource of router was limited. RCC proposed a way to measure traffics with high speed and accuracy. Additional quadratic probing hashing table used for accumulating elephant flows in RCC. However, in our experiment, quadratic probing performed many overheads when allocated small memory space or load factor was high. Especially, quadratic requested many calculations in update and lookup. To face this kind of problem, we use a cuckoo hashing which performed a good performance in update and loop for enhancing the RCC. As results, RCC with cuckoo hashing performed high accuracy and speed even when load factor of memory was high.
According to rapidly increasing of network traffics, necessity of high-speed router also increased. For various purposes, like traffic statistic and security, traffic measurement function should performed by router. However, because of the nature of high-speed router, memory resource of router was limited. RCC proposed a way to measure traffics with high speed and accuracy. Additional quadratic probing hashing table used for accumulating elephant flows in RCC. However, in our experiment, quadratic probing performed many overheads when allocated small memory space or load factor was high. Especially, quadratic requested many calculations in update and lookup. To face this kind of problem, we use a cuckoo hashing which performed a good performance in update and loop for enhancing the RCC. As results, RCC with cuckoo hashing performed high accuracy and speed even when load factor of memory was high.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
앞서 3장에서 제시한 것처럼 Quadratic Probing 또는 Cuckoo Hashing은 충돌이 발생할 때 마다 연산이 발생하기 때문에, 테이블에서 충돌이 발생하는 횟수가 성능을 좌우한다고 볼 수 있다. 따라서 이 실험에서는 두 Counter B를 조작(삽입, 갱신, 조회)하는 과정에서 발생하는 메모리 접근 횟수를 각각 기록하여 Quadratic Probing과 Cuckoo Hashing의 성능을 비교 및 분석하려고 한다. 또한 데이터 셋의 모든 Flow를 조회하여 측정된 값과 실제 Flow의 양을 비교하여 Counter A 또는 두 Counter B의 구현 정확도를 확인한다.
그리고 테이블과 해시함수를 세 개 이상 사용하지 않는 이유는 Cuckoo Hashing에서 조회가 발생할 때 최악의 경우에는 테이블 개수만큼 메모리 액세스를 하기 때문에, 많은 조회가 발생하는 실시간 트래픽 측정환경에서는 테이블 개수를 최소로 사용하는 것이 좋은 성능을 기대할 수 있으므로 테이블을 세 개만 사용을 하였다. 우리는 이를 RCC에 적용하여 성능을 개선하려고 한다.
이 논문에서는 RCC(recyclble counter with confinement)의 특성에 대해 분석 및 재현하고 실험을 통해 Quadratic Probing기법을 이용했을 때 RCC의 성능이 저하되는 것을 확인하였다. 그리고 이 문제를 해결하기 위해서 Cuckoo Hashing을 RCC에 적용했다.
이 논문에서는 RCC에서 Counter B로 누적을 할 때 Quadratic Probing 대신 Cuckoo Hashing을 이용하여 Counter B의 성능을 향상시키려고 한다. Cuckoo Hashing은 뻐꾸기의 습성과 유사한 형태를 이용한 테이블 충돌 방지기법이다.
5에 불과 했다. 하지만 이 논문에서는 테이블과 해시함수의 개수를 추가하므로 Cuckoo Hashing의 Load Factor가 향상되는 것을 실험으로 증명하려고 한다. 따라서 Cuckoo Hashing을 이용한 RCC가 네트워크 측정 또는 실시간 조회에 대하여 좋은 성능을 보여주는 것을 기대한다.
제안 방법
Nyang 등은 Linear Counting[9]과 CSE[10] 기반으로 한 RCC(Recyclable Counter with Confinement)를 소개했다[11]. RCC는 Counter A와 B로 구성되어 있으며, Counter A에서는 Small-but-recyclable Counter를 이용하여 측정의 정확도뿐만 아니라 메모리의 절약효과도 얻었다. 또한 메모리 블록을 1 워드 내에 감금(Confinement)함으로서, 한 번에 메모리 액세스로 삽입(Insertion)과 조회(Lookup)가 가능하며, 이를 통해 측정 속도를 향상시켰다.
우리는 Counter A가 포화되었을 때 Counter B에 누적되는 연산에 대하여 성능을 향상시키려고 하는 것이 목적이기 때문에, Counter A의 성능은 이 논문에서 고려하지 않는다. 그리고 Quadratic Probing을 이용하는 Counter B와 Cuckoo Hashing을 이용하는 Counter B를 같은 실험 조건에서 평가하기 위해 이 둘을 하나의 Counter A와 병렬로 동작하도록 구현했다. 따라서 Counter A에서 포화된 가상 벡터가 있을 때 동시에 두 Counter B에 누적되며 두 Counter B에 저장된 Flow들의 정보는 서로 같다.
RCC에서는 각 Flow에 대해 한 가상 벡터를 할당하고 Linear Counting 이용해 측정하고 있으며, 정확한 측정을 위해 작은 크기의 가상 벡터를 사용한다. 그리고 가상 벡터의 포화를 방지하기 위해서 사용량이 70%가 되었을 때, 측정된 Flow의 예상 값을 계산한다. 그 다음에는 가상 벡터의 공유된 부분에 대한 노이즈를 제거하고, Quadratic Probing 해시 테이블에 계산한 예상 값을 누적함으로서 가상 벡터를 재활용(Recycle)한다.
9까지 올라가는 것을 증명했다. 그리고 테이블과 해시함수를 세 개 이상 사용하지 않는 이유는 Cuckoo Hashing에서 조회가 발생할 때 최악의 경우에는 테이블 개수만큼 메모리 액세스를 하기 때문에, 많은 조회가 발생하는 실시간 트래픽 측정환경에서는 테이블 개수를 최소로 사용하는 것이 좋은 성능을 기대할 수 있으므로 테이블을 세 개만 사용을 하였다. 우리는 이를 RCC에 적용하여 성능을 개선하려고 한다.
또한 Cuckoo Hashing에서 세 개의 테이블과 세 개의 해시함수를 사용할 때의 Load Factor를 실험을 통해 알아보려고 한다.
또한 데이터 셋의 모든 Flow를 조회하여 측정된 값과 실제 Flow의 양을 비교하여 Counter A 또는 두 Counter B의 구현 정확도를 확인한다.
RCC는 Counter A와 B로 구성되어 있으며, Counter A에서는 Small-but-recyclable Counter를 이용하여 측정의 정확도뿐만 아니라 메모리의 절약효과도 얻었다. 또한 메모리 블록을 1 워드 내에 감금(Confinement)함으로서, 한 번에 메모리 액세스로 삽입(Insertion)과 조회(Lookup)가 가능하며, 이를 통해 측정 속도를 향상시켰다. Counter A에서는 작은 블록을 사용하기 때문에 포화 현상이 자주 발생하는데, RCC에서는 이것을 해결하기 위해서 포화된 블록의 값을 Counter B에 누적하고 블록을 재활용하는 방법을 사용한다.
이 실험에서는 데이터 셋의 패킷이 기록된 순서대로 하나씩 읽어서 발송지 주소(Source IP)의 해시 값을 이용해 Counter A에서 해당 Flow의 가상 벡터를 찾아 누적한다. 그리고 Counter A의 가상 벡터가 포화되면 Counter B에 누적한다.
9가되며 Quadratic Probing과 Cuckoo Hashing의 메모리 사용률이 높을 때의 성능을 분석할 수 있다. 이 실험에서는 주어진 데이터 셋[19]에 대해 Counter B의 Load Factor가 0.5부터 0.9까지 되도록 메모리공간을 할당하여 비교 및 분석한다.
이 장에서는 RCC에서 Quadratic Probing과 Cuckoo Hashing을 사용할 때의 성능차이에 대하여 비교 및 분석을 한다. 또한 Cuckoo Hashing에서 세 개의 테이블과 세 개의 해시함수를 사용할 때의 Load Factor를 실험을 통해 알아보려고 한다.
대상 데이터
Quadratic Probing과 Cuckoo Hashing는 모두 .NET에서 제공하는 SHA256를 사용한다(표 1).
또한 Cuckoo Hashing에서 세 개의 테이블과 세 개의 해시함수를 사용할 때의 Load Factor를 실험을 통해 알아보려고 한다. 실험에서는 CAIDA 데이터 셋[19]을 사용했다. 이 데이터 셋은 2013년 11월 21일 13:10-13:11사이에 Equinix Chicago Data Center에서 기록된 트래픽이며 264K개의 Flow를 담고 있다.
이론/모형
RCC는 여러 Linear Counter를 이용해 트래픽을 Flow 별로 측정한다. 그리고 메모리 공간을 절약하기 위해서 Randomized Counter Sharing 기법을 사용했으며 Counter가 포화되었을 때 큰 Flow를 추가적인 테이블에 누적함으로서 Counter가 사용하는 블록을 재활용하는 방법을 사용했다. RCC는 CSE와 PMC보다 높은 정확도로 트래픽을 측정할 수 있을 뿐만 아니라 Counter를 1 워드 내에 감금함으로서 한 Flow에 대해서 메모리 액세스를 한 번만 하는 방법으로 빠른 측정 속도를 보여주었다.
이 논문에서는 RCC(recyclble counter with confinement)의 특성에 대해 분석 및 재현하고 실험을 통해 Quadratic Probing기법을 이용했을 때 RCC의 성능이 저하되는 것을 확인하였다. 그리고 이 문제를 해결하기 위해서 Cuckoo Hashing을 RCC에 적용했다. 그리하여 Quadratic Probing과의 비교를 통해 Cuckoo Hashing이 작은 메모리 공간 또는 메모리 사용률이 높은 상황에서 더 적은 연산 또는 메모리 액세스로 트래픽을 측정할 수 있다는 것을 증명했다.
성능/효과
그리고 메모리 공간을 절약하기 위해서 Randomized Counter Sharing 기법을 사용했으며 Counter가 포화되었을 때 큰 Flow를 추가적인 테이블에 누적함으로서 Counter가 사용하는 블록을 재활용하는 방법을 사용했다. RCC는 CSE와 PMC보다 높은 정확도로 트래픽을 측정할 수 있을 뿐만 아니라 Counter를 1 워드 내에 감금함으로서 한 Flow에 대해서 메모리 액세스를 한 번만 하는 방법으로 빠른 측정 속도를 보여주었다.
를 이용해 측정하는 기법이다. 그 결과로 PMC는 MRSCBF보다 좋은 측정 정확도를 보여주었다.
그리고 이 문제를 해결하기 위해서 Cuckoo Hashing을 RCC에 적용했다. 그리하여 Quadratic Probing과의 비교를 통해 Cuckoo Hashing이 작은 메모리 공간 또는 메모리 사용률이 높은 상황에서 더 적은 연산 또는 메모리 액세스로 트래픽을 측정할 수 있다는 것을 증명했다. 이를 통해 Flow에 대한 누적 또는 실시간 조회가 자주 발생하는 네트워크 트래픽 측정에서는 RCC에 Quadratic Probing을 사용하는 것보다 Cuckoo Hashing을 사용하는 것이 더 적합하다는 것을 알 수 있었다.
9인 상황에서도 좋은 성능을 보여준다. 따라서 Cuckoo Hashing은 메모리 사용량이 높을수록 Quadratic Probing보다 더 적은 연산으로 트래픽을 측정할 수 있다는 것을 보여준다.
9인 상황에서도 실패율을 0으로 기록했다. 따라서 두 기법이 Load Factor 0.9까지 정확하게 동작한다는 것을 알 수 있었으며, Cuckoo Hashing이 세 개의 테이블과 세 개의 해시함수를 사용해도 메모리의 90%까지 사용할 수 있다는 것을 알 수 있었다.
Counter B는 Quadratic Probing을 이용하는 해시 테이블이며, 삽입, 조회, 갱신이 모두 같은 연산량으로 이루어지기 때문에, 갱신 또는 조회가 자주 발생하는 상황 또는 테이블의 사용량이 많은 상황에서 좋은 성능을 보여줄 수 없다. 따라서 이 논문에서는 갱신 또는 조회에 있어서 좋은 성능을 보여준 Cuckoo Hashing[12]을 이용해 Counter B를 구성하고, 실험을 통해 Cuckoo Hashing을 이용한 RCC가 메모리 사용량이 높을수록 Quadratic Probing보다 더 적은 연산으로 트래픽을 측정할 수 있다는 것을 보여준다.
트래픽 측정에서는 갱신 또는 실시간 조회가 자주 발생하는 특성이 있다. 따라서 이 논문에서는 갱신 또는 조회에 좋은 성능을 보여주는 Cuckoo Hashing[12]을 이용해 RCC가 더 작은 메모리 공간 또는 메모리 사용량이 높은 상황에서 효율적으로 동작하는 것에 기여한다.
5에 불과하다고 주장했다[12]. 이 논문에서는 실험을 통하여 기존 모델에서 테이블과 해시함수를 한 개씩 추가하여 Load Factor가 0.9까지 올라가는 것을 증명했다. 그리고 테이블과 해시함수를 세 개 이상 사용하지 않는 이유는 Cuckoo Hashing에서 조회가 발생할 때 최악의 경우에는 테이블 개수만큼 메모리 액세스를 하기 때문에, 많은 조회가 발생하는 실시간 트래픽 측정환경에서는 테이블 개수를 최소로 사용하는 것이 좋은 성능을 기대할 수 있으므로 테이블을 세 개만 사용을 하였다.
그리하여 Quadratic Probing과의 비교를 통해 Cuckoo Hashing이 작은 메모리 공간 또는 메모리 사용률이 높은 상황에서 더 적은 연산 또는 메모리 액세스로 트래픽을 측정할 수 있다는 것을 증명했다. 이를 통해 Flow에 대한 누적 또는 실시간 조회가 자주 발생하는 네트워크 트래픽 측정에서는 RCC에 Quadratic Probing을 사용하는 것보다 Cuckoo Hashing을 사용하는 것이 더 적합하다는 것을 알 수 있었다.
후속연구
하지만 이 논문에서는 테이블과 해시함수의 개수를 추가하므로 Cuckoo Hashing의 Load Factor가 향상되는 것을 실험으로 증명하려고 한다. 따라서 Cuckoo Hashing을 이용한 RCC가 네트워크 측정 또는 실시간 조회에 대하여 좋은 성능을 보여주는 것을 기대한다.
질의응답
핵심어
질문
논문에서 추출한 답변
PMC는 무엇인가?
PMC(Probabilistic Multiplicity Counting)는 하이브리드 구조를 기반으로 하여, 큰 Flow에 대해서는 FM Sketch[18]를 이용해 측정하고 작은 Flow은 HitCounter[9]를 이용해 측정하는 기법이다. 그 결과로 PMC는 MRSCBF보다 좋은 측정 정확도를 보여주었다.
Quadratic Probing의 단점은 무엇인가?
RCC에서는 트래픽을 측정하는데 큰 Flow를 추가적인 Quadratic Probing 기반 해시 테이블에 누적하는 방법 사용한다. 그런데 Quadratic Probing은 적은 메모리 또는 메모리 사용률이 많은 상황에서 연산량이 많으며, 특히 갱신 또는 실시간 조회가 자주 발생하는 시스템에서 오버헤드가 크다. 이 논문에서는 RCC의 특성을 분석하고 실험을 통해 Quadratic Probing의 문제점을 증명하며 갱신 또는 조회에 효율적인 Cuckoo Hashing을 사용하여 RCC의 성능을 개선한다.
샘플링의 대표적인 예는 무엇인가?
네트워크 트래픽을 측정하는 가장 간단한 방법은 샘플링(Sampling)다. Cisco의 Netflow[2]와 InMon의 Sflow[3]가 대표적인 예이다. 그러나 샘플링 기법은 Flow 별로 트래픽을 정확하게 측정하지 못하며, 특히 작은 Flow에 대해 정확하지 않다[4].
참고문헌 (19)
Cisco, Cisco Visual Networking Index: Forecast and methodology, 2012-2017, Retrieved May, 29, 2013, from http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_c11-481360_ns827_Networking_Solutions_White_Paper.html.
Cisco, NetFlow systems, from http://www.cisco.com/en/US/products/ps6601/products_ios_protocol_group_home.html.
InMon Corp, sFlow accuracy & billing, Retrieved 2003, from http://www.sflow.org/sFlowOverview.pdf.
P. Lieven and B. Scheuermann, "High-speed per-flow traffic measurement with probabilistic multiplicity counting," in Proc. IEEE INFOCOM, pp. 1-9, San Diego, USA, Apr. 2010.
A. Kumar, J. JimXu, and J. Wang, "Space-code bloom filter for efficient per-flow traffic measurement," in Proc. IEEE INFOCOM, pp. 1762-1773, Hong Kong, China, Mar. 2004.
Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani, "Counter braids: A novel counter architecture for per-flow measurement," in Proc. ACM SIGMETRICS, pp. 121-132, Annapolis, USA, Jun. 2008.
Y. Lu and B. Prabhakar, "Robust counting via counter braids: An error-resilient network measurement architecture," in Proc. IEEE INFOCOM, pp. 522-530, Rio de Janeiro, Brazil, Apr. 2009.
T. Li, S. Chen, and Y. Ling, "Fast and compact per-flow traffic measurement through randomized counter sharing," in Proc. IEEE INFOCOM, pp. 1799-1807, Shang Hai, China, Apr. 2011.
K. Y. Whang, B. Vander-Zanden, and H. Taylor, "A linear-time probabilistic counting algorithm for database applications," ACM Trans. Database Syst., vol. 15, no. 2, pp. 208-229, Jun. 1990.
M. Yoon, T. Li, S. Chen, and J. K. Peir, "Fit a compact spread estimator in small high-speed memory," IEEE/ACM Trans. Netw., vol. 19, no. 5, pp. 1253-1264, Oct. 2011.
C. Estan and G. Varghese, "New directions in traffic measurement and accounting," in Proc. ACM SIGCOMM, pp. 323-336, Pittsburgh, USA, Aug. 2002.
R. Karp, S. Shenker, and C. Papadimitriou, "A simple algorithm for finding frequent elements in streams and bags," ACM Trans. Database Syst., vol. 28, no. 1, pp. 51-55, Mar. 2003.
N. Kamiyama and T. Mori, "Simple and accurate identification of high rate flows by packet sampling," in Proc. IEEE INFOCOM, pp. 1-13, Barcelona, Spain, Apr. 2006.
X. Dimitropoulos, P. Hurley, and A. Kind, "Probabilistic lossy counting: An efficient algorithm for finding heavy hitters," Comput. Commun. Rev., vol. 38, no. 1, pp. 7-16, Jan. 2008.
S. Cohen and Y. Matias, "Spectral bloom filters," in Proc. ACM SIGMOD, pp. 241-252, San Diego, USA, Jun. 2003.
P. Flajolet and G. Nigel Martin, "Probabilistic counting algorithms for database applications," J. Comput. Syst. Sci., vol. 31, pp. 182-209, Apr. 1985.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.