인터넷 트래픽의 급증과 포워딩 테이블 항목의 빠른 증가로 인해, 인터넷 라우터에서 와이어 속도의 패킷 포워딩을 달성하기 위해서는 알고리즘적 개선과 하드웨어 혁신이 모두 요구된다. 본 논문에서는 리프-푸싱 trie에 접두사를 저장하는 Bloom filter를 결합한 longest-first 탐색 알고리즘을 제안한다. 제안하는 방법은 on-chip Bloom filter를 활용하여 trie 내 접두사의 존재 여부를 표시하고, off-chip 해시 테이블을 통해 각 접두사에 대한 대응 출력 포트 정보를 저장한다. 유입되는 각 IP 주소에 대해 Bloom filter 질의는 최장 길이부터 시작하며, 음성 결과가 나올 때마다 질의되는 비트 수를 1씩 감소시킨다. Bloom filter에 대한 질의 결과가 양성일 때만 off-chip 해시 테이블에 접근하므로, 합리적인 Bloom filter 크기를 가정하면 느린 off-chip 메모리에 대한 접근이 최대 한 번으로 최소화된다. 제안하는 접근은 C++를 사용해 시뮬레이션하였고, 필드 프로그래머블 게이트 어레이(field programmable gate array, FPGA) 구현을 위해 Verilog로 구성하였다. 실험 결과에 따르면, 제안하는 방법은 100MHz의 클록 주파수에서 초당 0.8백만 패킷의 처리량을 달성한다.

본 논문은 라우터가 유입되는 각 패킷에 대해 적절한 출력 링크를 결정하기 위한 핵심 작업인 IP 주소 조회를 위한 새로운 알고리즘을 제안한다. 클래스리스 인터도메인 라우팅(CIDR) 체계의 도입과 함께, IP 주소 조회 문제는 와이어 속도에서 최장 일치 접두사(LMP)를 효율적으로 찾는 데 어려움을 수반한다. 이를 위해 오프칩 삼중치 콘텐츠 주소 지정 메모리(TCAM)가 흔히 사용되지만, 전력 소비와 큰 비용 측면에서 단점이 있다. 이에 대응하여 본 연구는 온칩 메모리에 저장된 블룸 필터(BF)와 오프칩 메모리에 저장된 해시 테이블을 활용하는 데 초점을 맞춘 알고리즘적 대안을 탐구한다. 우리는 각 접두사를 리프 푸싱(trie)에서 저장하는 방식으로 블룸 필터에 대해 최장 우선(longest-first) 탐색을 수행할 것을 제안한다. 리프 푸싱 절차에 따라 trie의 리프에만 접두사가 위치하므로, trie의 최장 수준부터 BF를 조회하는 것이 매우 효과적이다. 온칩 BF는 존재하지 않는 노드에 대해 음성 결과를 생성함으로써 불필요한 오프칩 해시 테이블 접근을 회피하는 역할을 한다. 제안한 알고리즘은 C++ 코드로 구현하였고 백본 라우터의 실제 라우팅 데이터에 대해 시험하였다. 그 결과, 충분한 크기의 블룸 필터가 주어지면 제안한 알고리즘은 각 IP 주소 조회마다 평균적으로 오프칩 해시 테이블 접근을 단 한 번만 요구함을 보여준다.

역방향(복원 가능한) 블룸 필터(invertible Bloom filter, IBF)는 다양한 네트워크 응용에서 유용한 자료구조이다. 이는 서로 다른 두 집합에 의해 각각 프로그래밍된 두 개의 IBF의 차이(difference IBF, d-IBF)가 각 집합에 고유한 서로 다른 원소들을 효과적으로 식별하기 때문이다. d-IBF는 공통 원소를 제거하며, 각 셀에 단일 원소를 저장하는 ‘순수 셀(pure cell)’을 활용하는 디코딩 과정으로 고유 원소들을 나열한다. 그러나 IBF의 디코딩을 위해 사용되는 순수 셀의 정의는 d-IBF를 디코딩하기에는 불충분하다. d-IBF의 복합 셀(composite cells) 또한 IBF에 대해 정의된 순수 셀 조건을 만족할 수 있으며, 복합 셀을 디코딩하는 것은 d-IBF 성능에 불리하게 작용한다. 본 연구는 d-IBF에서 디코딩 오류가 발생할 확률을 수학적으로 분석하고, 이러한 오류를 해결하기 위한 새로운 디코딩 방법을 제안한다. 실험 결과는 제안한 디코딩 방법이 디코딩 오류를 성공적으로 검출하고 해결함을 확인하였다. 이를 통해 집합의 크기에 무관하게, IBF의 셀 수가 m = $2d$ (여기서 m은 IBF의 셀 수이고 d는 두 집합의 차이의 크기임)처럼 작더라도, 어떤 잘못된 원소도 생성하지 않으면서 두 집합 간의 차이를 정확하게 식별할 수 있다.

서로 다른 호스트 간에 동일한 데이터셋을 보유하도록 재정합(set reconciliation)하는 것은 수많은 분산 애플리케이션에서 중요한 선행 조건이다. 각 호스트가 보유한 데이터의 대부분이 서로 동일하다면, 집합 재정합을 달성하기 위해 전체 데이터셋을 전송하는 것은 비효율적이다. 각 호스트는 통신 복잡도를 최소화하기 위해 자신의 집합에만 독특하게 포함된 배타적 요소를 다른 호스트에게 보내야 한다. 본 논문은 ternary Bloom filter의 재귀적 비교를 이용하여 호스트가 자신의 배타적 요소를 식별하는 효율적인 알고리즘을 제안한다. ternary Bloom filter는 요소의 부분집합에 대한 서명을 나타내며, 동일한 요소를 포함한 부분집합을 걸러내는 데 사용된다. 따라서 배타적 요소를 포함한 부분집합이 식별되고, 해당 부분집합에 포함된 요소는 반전 가능 블룸 필터(invertible Bloom filter, IBF)에 프로그래밍되어 다른 호스트로 전송된다. 그 결과 IBF에 프로그래밍되는 요소의 수가 크게 감소한다. 시뮬레이션 결과는 동일한 데이터 통신량이라는 제약 하에서, 제안된 알고리즘이 기존 집합 재정합 알고리즘에 비해 우수한 성능을 제공함을 보여준다.

이름 기반 데이터 네트워킹(Named Data Networking, NDN)을 구현하는 핵심 구성 요소로서, 보류 이자 테이블(Pending Interest Table, PIT)은 확장 가능하고 빠른 PIT 조회를 위해 효율적인 정확 일치(exact-matching) 알고리즘을 필요로 한다. 블룸 필터(Bloom filter, BF)는 정확 일치 연산을 수행하는 데 메모리 효율적인 자료구조이다. 본 논문에서는 BF 기반 PIT 아키텍처 3가지를 제안한다. 즉 기능적 블룸 필터(PIT using functional Bloom filters, FBF-PIT)를 사용하는 PIT, 반환 값을 갖는 카운팅 블룸 필터(PIT using counting Bloom filters with return values, rCBF-PIT)를 사용하는 PIT, 서명이 포함된 정제 rCBF-PIT(R-rCBF-PIT)이다. 제안된 BF 기반 PIT는 동일한 콘텐츠 이름을 갖는 Interest 패킷의 다중 수신 얼굴(face)을 저장하기 위해, 새로운 BF를 점진적으로 할당한다. Data 패킷 조회를 위해, 제안된 PIT 아키텍처는 일치하는 얼굴을 찾기 위해 모든 BF 구조에 동시에 접근하고(즉, 일치하는 Interest 패킷 정보), 그 얼굴을 삭제한다. FBF-PIT에 사용되는 기능적 블룸 필터(FBF)는 키 없이 값만 저장하는 키-값 자료구조이다. 그러나 FBF-PIT에서 저장되는 패킷 수가 증가함에 따라 FBF의 재사용 불가능한 충돌 셀(non-reusable conflict cells) 수가 증가하므로, 판별 불가능률(indeterminable rate)이 증가한다. 판별 불가능률을 낮추기 위해, 재사용 가능한 충돌 셀을 허용하는 반환 값을 갖는 카운팅 블룸 필터(rCBFs)를 사용하는 rCBF-PIT를 제안한다. Interest 패킷에 대한 오탐(false positive)은 잘못된 삭제를 초래하여, 수신 Data 패킷에 대한 오탐(즉 false negatives)을 유발할 수 있다. 대부분의 오탐은 첫 번째 BF 구조에서 발생하므로, 최종적으로 첫 번째 rCBF를 서명 필드가 포함된 rCBF로 대체한 R-rCBF-PIT를 제안한다. 또한 제안된 PIT는 항목 만료를 위한 유효 비트(valid bit)와 히트 비트(hit bit)를 사용하여 에이징(aging) 메커니즘을 제공한다. 시뮬레이션 결과, rCBF-PIT와 R-rCBF-PIT 모두 FBF-PIT에 비해 판별 불가능률을 81% 이상 감소시키는 것으로 나타났다. 또한 R-rCBF-PIT는 첫 번째 rCBF에 서명 필드를 포함함으로써, 잘못된 삭제로 인해 발생하는 false negatives를 해결함을 보여준다.

정보통신부, 한국;정보기술평가원;한국관광공사;한국방송공학회

전통적인 자료구조를 학습된 모델로 대체하려는 도전적인 시도로서, 본 논문은 키-값 저장을 위한 학습 기반 함수형 블룸 필터(learned functional Bloom filter, L-FBF)를 제안한다. 제안된 L-FBF의 학습 모델은 주어진 데이터의 특성과 분포를 학습하고, 각 입력을 분류한다. 이론적 분석을 통해, L-FBF는 동일한 메모리 크기에서 단일 FBF보다 더 낮은 탐색 실패율을 제공함과 동시에 동일한 의미적 보장을 제공함을 보인다. 모델 학습을 위해 문자 수준의 신경망을 사용하되, 사전 학습된 임베딩(pretrained embeddings)을 활용한다. 실험에서는 서로 다른 문자 수준 신경망의 네 가지 유형을 학습한다: 단일 게이트 순환 유닛(single gated recurrent unit, GRU), GRU 2개, 단일 장단기 기억(single long short-term memory, LSTM), 그리고 단일 1차원 합성곱 신경망(single one-dimensional convolutional neural network, 1D CNN)이다. 실험 결과는 이론적 결과의 타당성을 입증하며, 동일한 메모리 사용량에서 단일 FBF와 비교할 때 L-FBF가 탐색 실패를 82.8%에서 83.9%까지 감소시킴을 보여준다.

해시 기반 자료구조는 많은 응용 분야에서 널리 사용되어 왔다. 해싱의 본질적인 문제는 충돌(collision)인데, 이는 둘 이상의 원소가 동일한 값으로 해시되는 경우를 말한다. 해시 테이블이 과도하게 적재(loaded)되어 있으면 더 많은 충돌이 발생한다. 충돌로 인해 해시 테이블에 저장할 수 없었던 원소들은 탐색 실패를 유발한다. 충돌의 수를 줄이기 위해 많은 변형 구조들이 연구되어 왔으나, 어떤 구조도 충돌 문제를 완전히 해결하지는 못한다. 본 논문에서는 기능성 블룸 필터(functional Bloom filter; FBF)가 해시 테이블이 과도하게 적재되어 있을 때 해시 테이블보다 더 낮은 탐색 실패율을 제공한다고 주장한다. 즉, FBF는 제한된 크기의 메모리에 대량의 데이터를 저장할 때 탐색 실패율 측면에서 해시 테이블보다 더 효과적이므로, 해시 테이블을 FBF로 대체할 수 있다. 해시 테이블은 각 입력 키와 더불어 그 반환값(return value)을 저장해야 하는 반면, 기능성 블룸 필터는 입력 키 없이 반환값을 저장하는데, 이는 각 입력 키에 따라 서로 다른 인덱스 조합을 사용하여 입력 키를 식별할 수 있기 때문이다. 탐색 실패율에 관하여, 본 연구는 FBF를 다중 해시 테이블(multi-hash table), 큐쿠 해시 테이블(cuckoo hash table), d-좌측 해시 테이블(d-left hash table)과 같은 해시 기반 자료구조와 이론적으로 비교한다. 또한, 본 이론적 결과의 타당성을 입증하기 위해 시뮬레이션 결과도 제시한다. 시뮬레이션 결과는 적재 계수(load factor)가 0.6보다 클 때 해시 테이블의 탐색 실패율이 기능성 블룸 필터의 탐색 실패율보다 더 크다는 것을 보여준다.

키-값 데이터 구조는 다양한 응용 분야에서 광범위하게 사용되어 왔다. 대량의 데이터를 고정된 메모리 크기 내에 압축적으로 저장해야 할 때, 기능적 Bloom 필터(functional Bloom filter)는 공간 효율적인 키-값 구조이다. 본 서한에서는 1차 기능적 Bloom 필터(primary functional Bloom filter)와 2차 기능적 Bloom 필터(secondary functional Bloom filter)로 구성된 2단계 기능적 Bloom 필터 구조를 제안하여, 1차 기능적 Bloom 필터에서 발생하는 부정확한(indeterminables) 결과를 해결하고자 한다. 두 Bloom 필터 각각에 할당되는 메모리 비율을 분석적으로 제시함으로써 탐색 실패율을 최저로 달성하는 방법을 도출한다. 이러한 분석 결과는 실험을 통해 검증되었으며, 2차 기능적 Bloom 필터가 전체 메모리의 3%를 사용할 때 최적 성능이 구현됨을 보여준다.

인터넷 트래픽의 급증과 포워딩 테이블 항목의 빠른 증가로 인해, 인터넷 라우터에서 와이어 속도의 패킷 포워딩을 달성하기 위해서는 알고리즘적 개선과 하드웨어 혁신이 모두 요구된다. 본 논문에서는 리프-푸싱 trie에 접두사를 저장하는 Bloom filter를 결합한 longest-first 탐색 알고리즘을 제안한다. 제안하는 방법은 on-chip Bloom filter를 활용하여 trie 내 접두사의 존재 여부를 표시하고, off-chip 해시 테이블을 통해 각 접두사에 대한 대응 출력 포트 정보를 저장한다. 유입되는 각 IP 주소에 대해 Bloom filter 질의는 최장 길이부터 시작하며, 음성 결과가 나올 때마다 질의되는 비트 수를 1씩 감소시킨다. Bloom filter에 대한 질의 결과가 양성일 때만 off-chip 해시 테이블에 접근하므로, 합리적인 Bloom filter 크기를 가정하면 느린 off-chip 메모리에 대한 접근이 최대 한 번으로 최소화된다. 제안하는 접근은 C++를 사용해 시뮬레이션하였고, 필드 프로그래머블 게이트 어레이(field programmable gate array, FPGA) 구현을 위해 Verilog로 구성하였다. 실험 결과에 따르면, 제안하는 방법은 100MHz의 클록 주파수에서 초당 0.8백만 패킷의 처리량을 달성한다.

본 논문은 라우터가 유입되는 각 패킷에 대해 적절한 출력 링크를 결정하기 위한 핵심 작업인 IP 주소 조회를 위한 새로운 알고리즘을 제안한다. 클래스리스 인터도메인 라우팅(CIDR) 체계의 도입과 함께, IP 주소 조회 문제는 와이어 속도에서 최장 일치 접두사(LMP)를 효율적으로 찾는 데 어려움을 수반한다. 이를 위해 오프칩 삼중치 콘텐츠 주소 지정 메모리(TCAM)가 흔히 사용되지만, 전력 소비와 큰 비용 측면에서 단점이 있다. 이에 대응하여 본 연구는 온칩 메모리에 저장된 블룸 필터(BF)와 오프칩 메모리에 저장된 해시 테이블을 활용하는 데 초점을 맞춘 알고리즘적 대안을 탐구한다. 우리는 각 접두사를 리프 푸싱(trie)에서 저장하는 방식으로 블룸 필터에 대해 최장 우선(longest-first) 탐색을 수행할 것을 제안한다. 리프 푸싱 절차에 따라 trie의 리프에만 접두사가 위치하므로, trie의 최장 수준부터 BF를 조회하는 것이 매우 효과적이다. 온칩 BF는 존재하지 않는 노드에 대해 음성 결과를 생성함으로써 불필요한 오프칩 해시 테이블 접근을 회피하는 역할을 한다. 제안한 알고리즘은 C++ 코드로 구현하였고 백본 라우터의 실제 라우팅 데이터에 대해 시험하였다. 그 결과, 충분한 크기의 블룸 필터가 주어지면 제안한 알고리즘은 각 IP 주소 조회마다 평균적으로 오프칩 해시 테이블 접근을 단 한 번만 요구함을 보여준다.

역방향(복원 가능한) 블룸 필터(invertible Bloom filter, IBF)는 다양한 네트워크 응용에서 유용한 자료구조이다. 이는 서로 다른 두 집합에 의해 각각 프로그래밍된 두 개의 IBF의 차이(difference IBF, d-IBF)가 각 집합에 고유한 서로 다른 원소들을 효과적으로 식별하기 때문이다. d-IBF는 공통 원소를 제거하며, 각 셀에 단일 원소를 저장하는 ‘순수 셀(pure cell)’을 활용하는 디코딩 과정으로 고유 원소들을 나열한다. 그러나 IBF의 디코딩을 위해 사용되는 순수 셀의 정의는 d-IBF를 디코딩하기에는 불충분하다. d-IBF의 복합 셀(composite cells) 또한 IBF에 대해 정의된 순수 셀 조건을 만족할 수 있으며, 복합 셀을 디코딩하는 것은 d-IBF 성능에 불리하게 작용한다. 본 연구는 d-IBF에서 디코딩 오류가 발생할 확률을 수학적으로 분석하고, 이러한 오류를 해결하기 위한 새로운 디코딩 방법을 제안한다. 실험 결과는 제안한 디코딩 방법이 디코딩 오류를 성공적으로 검출하고 해결함을 확인하였다. 이를 통해 집합의 크기에 무관하게, IBF의 셀 수가 m = $2d$ (여기서 m은 IBF의 셀 수이고 d는 두 집합의 차이의 크기임)처럼 작더라도, 어떤 잘못된 원소도 생성하지 않으면서 두 집합 간의 차이를 정확하게 식별할 수 있다.

서로 다른 호스트 간에 동일한 데이터셋을 보유하도록 재정합(set reconciliation)하는 것은 수많은 분산 애플리케이션에서 중요한 선행 조건이다. 각 호스트가 보유한 데이터의 대부분이 서로 동일하다면, 집합 재정합을 달성하기 위해 전체 데이터셋을 전송하는 것은 비효율적이다. 각 호스트는 통신 복잡도를 최소화하기 위해 자신의 집합에만 독특하게 포함된 배타적 요소를 다른 호스트에게 보내야 한다. 본 논문은 ternary Bloom filter의 재귀적 비교를 이용하여 호스트가 자신의 배타적 요소를 식별하는 효율적인 알고리즘을 제안한다. ternary Bloom filter는 요소의 부분집합에 대한 서명을 나타내며, 동일한 요소를 포함한 부분집합을 걸러내는 데 사용된다. 따라서 배타적 요소를 포함한 부분집합이 식별되고, 해당 부분집합에 포함된 요소는 반전 가능 블룸 필터(invertible Bloom filter, IBF)에 프로그래밍되어 다른 호스트로 전송된다. 그 결과 IBF에 프로그래밍되는 요소의 수가 크게 감소한다. 시뮬레이션 결과는 동일한 데이터 통신량이라는 제약 하에서, 제안된 알고리즘이 기존 집합 재정합 알고리즘에 비해 우수한 성능을 제공함을 보여준다.