본 논문에서는, 인터넷 상에서의 에지 라우터에서 높은 대역폭의 플로우들을 찾아낼 수 있는 고대역폭 플로우 확인 알고리즘인 HBS (High Bandwidth Search) 알고리즘을 제안하고 있다. 모든 플로우에 대한 대역폭 사용 상태를 유지하는 것에 비해, HBS 알고리즘은 K ≥ 1인 상수인 대역폭이 가장 높은 K개의 플로우를 O(K)의 공간과 O(1)의 표본 처리 부하량으로 처리할 수 있다. HBS 알고리즘은 검증된 검사 방법론과 함께 사용하여 인터넷상에서 비정상적인 플로우를 찾아낼 수 있다. 이러한 플로우는 기존 검사 방법론과 연동하여 공평성 제어가 가능하다. 알고리즘에 대한 애플리케이션으로는 정체에 대해서 제대로 대응하지 못하는 멀티미디어 스트리밍 서비스와 플러딩 서비스 거부 공격를 줄여주는데 이용될 수 있다.
Alternative Abstract
In this thesis, we present a High-bandwidth Flow Search algorithm, titled HBS, which is designed for use by Internet edge routers to identify and control high-bandwidth flows. Rather than maintaining the bandwidth usage states of all flows, HBS is able to identify K highest-bandwidth flows, where K ≥ 1 is a constant, using O(K) space and incurring only O(1) per sample processing overheads. We show that HBS can be used in conjunction with well-established flow testing criteria to curb improperly behaving flows in the Internet. This can also be used for filtering purposes. Applications of HBS include identifying high-bandwidth multimedia streams that do not respond to congestion and mitigating the effects of flooding denial-of-service attacks. Our simulation shows that HBS performs the above tasks with high accuracy and low overheads.
