Elastic-C: 카운터 기반 교체 방식을 이용한 Elastic Sketch
Elastic-C: Elastic Sketch Using Counter-Based Swapping
- 주제(키워드) Sketch , Elastic-C , Counter-based swapping , Traffic measurement , Estimation
- 주제(기타) 전자/정보통신공학
- 설명문(URI) https://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART002724829
- 관리정보기술 faculty
- 등재 KCI등재
- 발행기관 한국통신학회
- 발행년도 2021
- URI http://www.dcollection.net/handler/ewha/000000182811
- 본문언어 한국어
- Published As http://dx.doi.org/10.7840/kics.2021.46.6.929
초록/요약
네트워크 환경을 원활하게 유지하기 위해서는 데이터 스트림에서 혼잡제어, DoS 공격, 스캔 공격 등의 문제를유발하는 원인을 파악하는 것이 중요하다. 이를 해결하기 위해 데이터 스트림의 각 플로우의 빈도수를 측정하여문제를 유발하는 플로우를 찾는 작업이 요구되지만, 제한된 환경에서 데이터 스트림을 정확하고 신속하게 측정하는 것은 어려운 일이다. 최근 발표된 Elastic sketch는 기존 알고리즘과는 다르게 해시테이블을 카운터 앞에 두고빈도수 투표에 의한 추방 방법(이하 voting)을 사용하여 빈도수가 높은 플로우(elephant flow)를 해시테이블에 따로 저장한다. 그 결과 빈도수가 높은 플로우가 카운터에서 유발할 수 있는 측정오차가 줄어들기 때문에 상당수의빈도수가 작은 플로우(mouse flow)가 정확해진다. 그러나 이들이 사용한 voting이라는 방법은 해시테이블에서 수행되는 알고리즘이기 때문에 부가적인 메모리와 연산을 요구하는 등 여러 문제가 발생한다. 이 논문에서는 voting 알고리즘이 유발하는 문제점을 분석하고 이를 해결할 수 있는 새로운 방식인 Elastic-C를 소개한다.
more초록/요약
In order to keep the network environment smooth, it is important to identify the causes of problems such as congestion control, DoS attacks, and scan attacks in the data stream. To solve this problem, it is required to measure the frequency of each flow of the data stream to find the flow causing the problem, but it is difficult to accurately and quickly measure the data stream in a limited environment. Unlike existing algorithms, the recently announced Elastic Sketch uses a hash table in front of a counter and uses the expulsion method by frequency voting (hereinafter, voting) to separately store high-frequency flows in the hash table. As a result, since the measurement error that can be caused by a counter with a high frequency flow is reduced, a significant number of flows with a small frequency become accurate. However, since the voting method they used is an algorithm that is performed on a hash table, several problems arise, such as requiring additional memory and operation. In this paper, we analyze the problems caused by the voting algorithm and introduce Elastic-C, a new method that can solve them.
more