보고서 정보
주관연구기관 |
국민대학교 KookMin University |
보고서유형 | 최종보고서 |
발행국가 | 대한민국 |
언어 |
한국어
|
발행년월 | 2014-05 |
과제시작연도 |
2013 |
주관부처 |
미래창조과학부 Ministry of Science, ICT and Future Planning |
등록번호 |
TRKO201500004064 |
과제고유번호 |
1711005984 |
사업명 |
중견연구자지원 |
DB 구축일자 |
2015-05-23
|
키워드 |
멀티코어.자료구조.해시테이블.해시함수.블룸필터.스트리밍 알고리즘.트래픽측량.네트워크 관리.multi-core.data structure.hash table.hash function.bloom filter.streaming algorithm.traffic measurement.SRAM.network management.
|
DOI |
https://doi.org/10.23000/TRKO201500004064 |
초록
▼
연구의 목적 및 내용
멀티코어 환경에 적합한 다중해시 기반의 자료구조에 대하여 연구를 수행하였다. 다중해시는 동시에 상호 독립적으로 연산이 될 수 있기 때문에 멀티코어의 장점을 최대한 이용할 수 있다. 첫째, 블룸필터의 성능향상과 네트워크 응용기술에 대해서 연구한다. 둘째, 새로운 트래픽측량 문제를 정의하고 다양한 트래픽측량도구를 개발한다. 셋째, 기존의 해시테이블보다 두 배 이상 빠르며 메모리 사용 효율도 동시에 향상되는 새로운 해시테이블에 대해서 연구한다. 연구논문을 국제 최고수준의 컨퍼런스에 발표하거나, SCI 저널에 투
연구의 목적 및 내용
멀티코어 환경에 적합한 다중해시 기반의 자료구조에 대하여 연구를 수행하였다. 다중해시는 동시에 상호 독립적으로 연산이 될 수 있기 때문에 멀티코어의 장점을 최대한 이용할 수 있다. 첫째, 블룸필터의 성능향상과 네트워크 응용기술에 대해서 연구한다. 둘째, 새로운 트래픽측량 문제를 정의하고 다양한 트래픽측량도구를 개발한다. 셋째, 기존의 해시테이블보다 두 배 이상 빠르며 메모리 사용 효율도 동시에 향상되는 새로운 해시테이블에 대해서 연구한다. 연구논문을 국제 최고수준의 컨퍼런스에 발표하거나, SCI 저널에 투고하는 것을 목표로 한다.
연구결과
연구결과는 컴퓨터 분야 최고 컨퍼런스 중 하나인 IEEE Infocom’14 메인 컨퍼런스에서 발표되었으며, 현재까지 5편의 SCI논문이 발표되었고 2편이 심사 중에 있다. 우리 연구팀은 블룸필터와 트리구조를 융합한 블룸트리를 연구개발하고, 네트워크 분야 최고 권위의 학회인 INFOCOM에서 발표를 하였다. 블룸트리는 다중 집합에 대한 쿼리를 처리하기 위한 자료구조로써, 기존의 가장 좋은 자료구조보다 메모리 사용량을 줄이는 동시에 더욱 효율적으로 동작한다. 또한, 우리는 최초로 블룸필터를 비대칭형으로 디자인하여 처리 속도 향상과 전력 감소효과를 갖는 방식에 대한 연구를 성공적으로 수행했다. 새롭게 제안하는 고속 해시테이블은 SRAM내에 고속 처리가 가능한 블룸필터와 비트 배열을 사용한다. 느린 DRAM에는 해시테이블이 상주하게 된다. k개의 해시함수가 사용되어서 메모리 사용량의 낭비를 막는데, 이렇게 되면 k번 확인 작업이 필요해서 속도가 느려진다. 새롭게 디자인한 블룸필터가 바로 이 문제를 해결해 준다. Spread estimator는 네트워크 트래픽에서 spread 값을 측정하는 도구로 사용된다. 기존의 estimator는 빠른 네트워크 속도에서 동작하기 위해서, 작지만 접근 속도가 빠른 SRAM에서 동작할 수 있도록 간결한 자료구조로 디자인되어 왔다. 하지만 SRAM의 크기가 워낙 작기 때문에 처리할 수 있는 트래픽 양이 제한되어 왔다. 우리 연구팀은 최근 많은 연구가 진행되고 있는 GPU를 이용해서 spread estimator를 소프트웨어적으로 구현했다. 구현된 estimator는 SRAM 기반의 기존 방식보다 빠르게 동작하며, 대학교 백본 라우터에서 수집한 실제 네트워크 트래픽을 사용해서 실험을 통해 우수성을 검증하였다. 마지막으로, 우리는 새로운 트래픽 특성을 정의하고, 정의된 특성을 측정할 수 있는 도구를 연구개발함으로써 기존에는 탐지할 수 없었던 네트워크 장애나 공격을 새롭게 탐지할 수 있게 하였다.
연구결과의 활용계획
멀티코어 환경에서 블룸필터의 처리 속도가 큰 폭으로 개선된다. 블룸필터는 현재 다양한 분야에서 응용되고 있으며 계속해서 새로운 응용기술이 연구되고 있다. 이번 연구과제를 통해서 블룸필터 자체의 처리 속도를 높이는 방법이 연구개발 되었고, 블룸필터가 많이 사용되는 분야(OS, DB, 네트워크, 아키텍처 등)에 미치는 긍정적 효과는 매우 크다. 속해시테이블은 컴퓨터공학의 모든 분야에서 사용되는 기본이 되는 자료구조이며, 특히 고속 처리가 많이 요구되는 운영체제, 네트워크, DB, 리얼타임시스템 등에서 많이 사용된다.
새로운 트래픽측량도구는 그동안 정의조차 되지 않았던 트래픽의 의미있는 특성들이 분석되고 활용된다. 또한, 기존의 트래픽측량도구의 성능이 큰 폭으로 향상되어 지금보다 더 빠른 네트워크 환경에서도 잘 동작하게 된다.
Abstract
▼
Purpose&contents
This research examines the problem of optimizing multiple-hash data structure to multi-core environment. Multiple-hash can exploit the advantages of multi-core hardware, because the hash functions can be computed independently and concurrently. This research focuses on three main
Purpose&contents
This research examines the problem of optimizing multiple-hash data structure to multi-core environment. Multiple-hash can exploit the advantages of multi-core hardware, because the hash functions can be computed independently and concurrently. This research focuses on three main topics: (1) improving bloom filter functions and network application technologies; (2) defining new traffic measurement metrics and studying the measurement tools to the new problems; (3) studying new a hash table which is not only at least twice faster than existing hash tables but also makes more efficient use of memory. We aim at presenting research papers at world-class conferences or being published in SCI journals.
Result
One research result was presented at the main conference of IEEE Infocom’14, one of the best conferences in computer science, and others have been published in five SCI journals. Two papers are currently reviewed by other SCI journals.
We have studied and developed a Bloom tree, which combines bloom filters and search trees. The study result was presented at Infocom’14. A Bloom tree, the data structure optimized for processing multiple queries, reduces the use of memory and at the same time makes more efficient use of memory than other existing data structures.
We became the first to find the way to improve processing speed and to reduce electric power consumption by designing asymmetric bloom filters. The newly designed high-speed hash table uses bloom filter and a bit array that can accelerate the processing speed in SRAM. A hash table resides in a slow DRAM. The newly designed Bloom filter can solve the problem of slow DRAM accesses of “k” times. A spread estimator is used as a tool for measuring a spread value in network traffic. Existing estimators’ data structures were designed as compact as possible to be used in high-speed SRAM, small in size but with faster access speed. However, due to the small size of SRAM, only limited volume of traffic has been processed. We realized spread estimator in software form by utilizing GPU, which is now being studied in many fields. The implemented estimator performed much faster than the existing ones used in SRAM, and was proven to be effective during a test using real network traffic collected through the University’s backbone router. Lastly, we succeeded in detecting network errors and attacks that were impossible to detect, in a whole new way by defining new traffic characteristics and developing tools that can measure defined values.
Expected Contribution
The process speed of Bloom filter improves greatly in a multi-core environment. Bloom filters are now being applied to a variety of fields, and new technologies using Bloom filters are being studied. In this study, we successfully found the way to improve the speed of Bloom filter, and we believe the result will have an enormously positive impact on the research areas using Bloom filters (e.g. OS, DB, Networks, Architecture, and etc.) A hash table, one of the most fundamental data structure in almost every area of computer engineering, is especially widely used in areas requiring high-speed processing such as OS, network, DB, and real-time system. The new series of traffic measurement tools based on multiple-hash will detect new types of network problems and cyber-attacks. Therefore network and security administrators will be the direct beneficiaries. Our research on Bloom filter will be efficiently used in network environment that requires high-speed and small space.
목차 Contents
- 핵심연구사업 최종보고서(평가용) ... 1
- 목 차 ... 3
- 연구계획 요약문 ... 4
- 연구결과 요약문 ... 5
- 한글요약문 ... 5
- SUMMARY ... 6
- 연구내용 및 결과 ... 7
- 1. 연구개발과제의 개요 ... 7
- 2. 국내외 기술개발 현황 ... 11
- 3. 연구수행 내용 및 결과 ... 15
- 4. 목표달성도 및 관련분야에의 기여도 ... 22
- 5. 연구결과의 활용계획 ... 29
- 6. 연구과정에서 수집한 해외과학기술정보 ... 29
- 7. 주관연구책임자 대표적 연구실적 ... 30
- 8. 참고문헌 ... 30
- 9. 연구성과 ... 31
- 10. 기타사항 ... 34
- 끝페이지 ... 49
※ AI-Helper는 부적절한 답변을 할 수 있습니다.