[네트워크] 5. 라우팅 알고리즘 - Static Routing, Dynamic Routing, Hierarchical routing

 

 

 

[네트워크] 5. 라우팅 알고리즘 - Static Routing, Dynamic Routing, Hierarchical routing

 

 

 

1. 라우팅 알고리즘

• Link-State Routing Algorithm : 네트워크 정보가 글로벌 할 경우
• Distance vector algorithm : 네트워크 정보가 지엽적인 경우

 

1. Link-State Routing Algorithm (글로벌 알고리즘)

• 각 라우터는 자기에게 인접한 링크들에 대해 Link-State를 broadcasting 해서 (나머지 사람들에게 알림) 네트워크 전체에 대한 토폴로지 정보를 알고 있다.
• 각 라우터는 Network 전체에 대한 정보를 수집하게 됨
• 이걸 이용해 다익스트라 알고리즘을 실행해서 길찾기를 진행한다.. 

 

다익스트라 알고리즘

• 최단 거리를 이용한 알고리즘
• 소스 노드에서 알고리즘을 돌리면, 네트워크에 있는 다른 모든 데스티네이션에 대해 최솟값을 계산
• 효율성 O(n2)

 

 

2. Distance vector algorithm (거리벡터 알고리즘)

• 자기 근처만의 정보를 이용
• Bellman-Ford equation(dynamic programming) 개념을 사용
• 모든 라우터가 거리에 의존하는 방식

 

거리벡터 알고리즘 특징

• 각 노드는 직접 연결된 이웃들이 보내는 정보로부터 계산하고 그 계산결과(자신의 거리벡터 계산 복사본)를 이웃에게 알림
• 이웃끼리 라우팅 정보를 반복적으로 주고받음
• 모든 노드가 비동기적으로 제각각 동작하며 계산
• 이웃에서 보내준 경로 예측 값들과 자신이 가지고 있는 경로 예측 값을 비교하여 적은 값을 최적 경로로 삼게됨

 

 

 

2. Link-State Routing Algorithm(LS) VS Distance vector algorithm(DV)

 

1. message 복잡도 : 한 노드가 감당해야하는 양 

• LS : 네트워크에 있는 모든 노드로부터 데이터를 받아야하기 때문에 네트워크에 노드가 늘어나는 것에 비례해 message 복잡도가 늘어남
• DV : 나와 인접한 링크에 대한 정보만 알면 되기 때문에 바깥의 네트워크가 커져도 어느정도의 영향만 있을 뿐 완전 비례하진 않음

 

2. Speed of convergence : 경로를 결정하는 속도

• LS : Link Stat가 broadcast 된 후, 알고리즘을 돌리면 모든 라우터가 똑같은 경로를 그리게 됨
• DV : 서로가 서로의 데이터를 받아오기 때문에 convergence time이 경우에 따라 매우 달라짐.

 

 

 

 

3. Routing의 유형 -  Static Routing, Dynamic Routing

 

3. 1 정적 라우팅 (Static Routing)

• 정적 라우팅은 라우팅 테이블에 경로를 수동으로 추가해야하는 프로세스

​

장점

• 라우터 CPU에 라우팅 오버 헤드가 없으므로 더 저렴한 라우터를 사용하여 라우팅을 수행 할 수 있음
• 관리자 권한을 가진 자만이 특정 네트워크로의 라우팅만을 허용하므로 보안성이 좋음

​

단점

• 대규모 네트워크의 경우 관리자가 각 라우터의 라우팅 테이블에서 네트워크에 대한 각 경로를 수동으로 추가해야 하기 때문에 리소스가 많이 투입됨
• 관리자가 토폴로지에 대해 잘 알고 있어야함 -> 새 관리자가 오면 각 경로를 수동으로 추가해야하므로 토폴로지 경로에 대해 다 배워야함

​

 

3. 2 동적 라우팅 (Dynamic Routing)

• 적응형 라우팅이라고도 하는 동적 라우팅, 라우터가 시스템 내 통신 회로의 현재 조건에 따라 주어진 대상에 대해 다른 경로를 통해 데이터를 전달할 수 있는 프로세스

 

장점

• 구성이 쉽다
• 대상 원격 네트워크에 대한 최상의 경로를 선택하고 원격 네트워크를 검색하는 데 더 효과적

​

단점

• 정적 라우팅보다 안전하지 않음
• traffic에 따라 cost를 책정할 경우 routing loop가 생기거나 꼬이는 문제가 발생할 수 있다.

 

 

 

 

 

 

 

4. Hierarchical routing

4. 1 Hierarchical routing 의 탄생 이유

• 위의 LS, DV 두가지 알고리즘은 network를 flat하게 보고, routing 방식을 결정하는 것
• LS의 경우 네트워크가 커지면 각 노드의 링크 코스트 정보가 너무 커져서 굉장히 비효율적임.
• 사용자 정보를 교환하는것보다 라우팅 정보를 교환하는데 링크가 더 많이 사용될 수 있음
• DV에서도 routing loop등의 문제가 생길 가능성이 크고, routing distance의 길이가 너무 길어짐
• LS와 DV는 네트워크가 커질 수록 라우트 테이블의 크기가 너무너무 커짐
• 네트워크는 각 작은 네트워크들의 모임인데, 각각의 네트워크들은 내 주소 정보를 모두에게 알려주고 싶지 않아함

 

4. 2 Hierarchical routing의 특징

• 네트워크는 지역적으로 제한된, 지역내에 있는 한 기관에 속한 라우터들의 집합인 autonomous system으로 나눔
• autonomous system 단위로 라우팅 테이블을 만듬
• 그 후  autonomous system 내에서 라우팅을 실행하는데, 이것을 intra-AS routing protocol이라고 함.
• 각 autonomous system은 gateway router로 서로 연결될 수 있음

 

 

 

 

5. Forwarding table

• 라우터의 forwarding table에는 두가지 종류의 목적지 서브넷으로 구분된다.

 

 

• Intra-AS subnet : 내 AS에 속한 서브넷 -> intra-AS routing 알고리즘으로 전부 작성 가능
• Inter-AS subnet : 내 AS에 속하지 않은 서브넷 -> 다른 서브넷에 있는 목적지 서브넷은 Inter-AS Routing 알고리즘 필요
• 이 두가지를 함께 협력적으로 사용해서 포워딩 테이블을 작성

 

예제

 

 

• AS1이 내 AS라고 가정
• AS1은 AS3와 AS2의 정보가 필요함
• 3a, 1c, 1b, 2a는 각 AS들의 Gateway router
• Inter - AS Routing protocol을 이용해 각 AS의 Gateway router들은 정보를 주고 받고 각자의 AS 내의 라우터들에게 들어온 정보들에 대한 내용을 공유함
• 내부의 Routing 정보는 Intra - AS Routing protocol을 이용해 작성함