[네트워크] BGP Routing Table 에서 IP주소 탐색

 

 

BGP Routing Table Data를 읽어 IP주소를 탐색한다. 

1. 먼저 제공된 BGP Routing Table Data를 읽어 전처리를 한다.

2. 전처리된 파일을 읽어 Hash와 Trie 두 가지 알고리즘을 사용하여 input IP(입력된 ip)의 주소를 탐색하는 방법을 구현 한다.

3. 마지막으로 두 가지 알고리즘의 성능평가를 위해 그래프로 시각화하여 보여준다. 

 

두개다 하나의 파일에 구현하였다.

 

 

input파일은 다음과 같다.

 

 

 

 

 

먼저 전처리할 파일을 읽어온다.

 

 

 

 

파싱을 하고 같은 네트워크 아이피일 경우 Big Weight > High Local Pref > Short AS_PATH기준으로 하나의 아이피만 남기고 리스트에 저장한다.

 

 

 

 

 

전처리한 ip리스트를 pickle과 txt파일로 저장한다. (txt 파일은 추후 탐색에서 읽어오기 위해 저장했다. )

 

 

 

 

 

전처리한 파일을 불러오고 해시테이블에 저장한다. 그리고 탐색할(입력한) 텍 스트파일도 불러와 변수에 저장한다. 100000개의 input값이 들은 파일로 실행 했다. 저장하는 방식은 밑의 참고사진과 같다.

 

 

 

 

 

Hash탐색을 시작한다. 탐색과정은 위 사진과 같이 하면 된다. 탐색할 ip리스 트를 하나씩 불러와 앞서 해시테이블에 저장한 거와 비교해서 찾은 ip를 결과 리스트에 추가해주면 된다.

 단, Longet Prefix Matching 방법에 의하여 IP 주소 8부터 31까지 Masking 수행하고 Subnet Mask한 결과를 Hash화 하여 Hash 키에대한 모든 Value 를 찾아온 후 그 중 가장 긴 Subnet Mask를 가진 Network 주소의 Next Hop으로 결정하면 된다. 

Longet Prefix Matching 방법은 다음 사진과 같다. 결과값은 텍스트 파일로 저장하였다.

 

 

 

 

 

 

Hash(위)

---

Trie(아래)

Trie는 먼저 트리구조를 만들어 주고 초기화, 삽입, 탐색하는 기능을 구현해줬다.

 

 

 

 

 

앞서 Hash에서 했던 것처럼 ip 리스트들을 Trie에 넣어주고 찾을 ip를 search()를 통해 탐색하였다. search() 함수는 계속해서 자식노드를 타고내려가 해당 ip를 탐색한다.

그리고 Trie또한 결과를 텍스트 파일로 출력하였다. Trie 노드는 비트화한 ip를 차례대로 추가해주고 nextHop을 최종 노드에 저장해주면 된다. 탐색은 탐색할 ip를 비트로 변환하여 순차적으로 대입하고 찾아 맞는 일치한 비트까지의 노드를 탐색하여 nextHop을 알아낸다.

 

 

 

 

---

두 가지 알고리즘의 시간복잡도 시각화 비교

Hash와 Trie 탐색을 할 때 하나탐색할때마다의 시간을 time 리스트에 넣어주 었다. 그것을 시각화한 코드이다.

 

 

 

 

---

결과

 

 

 

 

 

전처리한 파일은 위와 같다.

 

 

 

 

 

밑은 Hash 탐색한 결과이다.

 

 

 

 

 

 

밑은 Trie 탐색한 결과이다. (결과는 당연히 Hash와 일치한다.)

 

 

 

 

 

두 알고리즘의 개수에 따른 시각화 비교이다.

 

 

 

 

 

 

 

10개일 때 빼고 Trie가 우수함을 알 수 있다. 입력데이터 100000개를 기준으로 실험하였다. Hash 탐색 시간 복잡도 : O(1) Trie 탐색 시간 복잡도 : O(m), m은 탐색하려는 문자열 길이이다.

 

 

 

 

파일:

HashBGP.py

0.00MB