네트워크 계층 : 제어평면(control plane), 라우팅 알고리즘 분류

라우터별 제어 : 포워딩과 라우팅 기능이 모두 개별 라우터에 포함

                   각 라우터는 다른 라우터의 라우팅 구성요소와 통신하여 자신의 포워딩 테이블의 값을 계산하는 라우팅 구소요소를 가짐

                   라우터별 제어 방식 기반 프로토콜 : OSPF, BGP 프로토콜

라우터별 제어 : 개별 라우팅 알고리즘들이 제어 평면에서 상호 작용

 

논리적으로 중앙 집중된 제어 : 논리적으로 집중된 컨트롤러가 포워딩 테이블을 작성하고 모든 개별 라우터가 사용하도록 배포

컨트롤러는 잘 정의된 프로토콜을 통해 각 라우터의 제어 에이전트(CA)와 상호작용하여 라우터의 플로우 테이블을 구성 및 관리

CA(control agent) : 컨트롤러와 통신하고 일반적으로 컨트롤러의 명령을 수행하는 최소한의 기능만 가짐

                               라우터별 제어 방식과 달리 CA는 서로 직접 상호작용하지 않으며 포워딩 테이블을 계산하는 데 적극적으로 참여 안함

논리적으로 중앙 집중된 제어 : 일반적으로 원격에 위치한 컨트롤러가 지역의 제어 에이전트(CA)와 상호작용

논리적으로 중앙 집중된(logically centralized)의 의미 :

실제로는 고장 또는 참여 호스트 수의 증가에 따른 성능저하 문제에 대응하기 위해 여러 개의 서버에 라우팅 서비스가 구현된다 하더라도 마치 하나의 중앙 서비스 지점에 있는 것처럼 서비스에 접근한다는 뜻

ex) SDN(Software-Defined Networking)은 논리적으로 중앙 집중된 컨트롤러라는 개념을 채택

      Google은 데이터 센터를 상호 연결하는 내부 B4 글로벌 광역 네트워크의 라우터를 제어하기 위해 SDN을 사용

 

 

 

 

라우팅 알고리즘의 목표 : 송신자부터 수신자까지 라우터의 네트워크를 통과하는 "좋은 경로"(route)를 결정

좋은 경로 => 최소 비용 경로 + 정책(ex : Y기관에 속해 있는 라우터 x는 Z기관이 소유한 네트워크가 보낸 패킷을 전달해서는 안됨) 고려

 

라우팅 문제를 나타내는 데에는 그래프가 사용됨.

그래프 G = (N, E)로 표현  (N : 노드 집합, E : 에지 집합)

하나의 에지는 집합 N에 속하는 한 쌍의 노드로 표시

네트워크 계층 라우팅 상황에서, 그래프 상의 노드는 패킷 포워딩 결정이 이루어지는 지점인 라우터를 나타내며,

이 노드들을 연결하는 에지는 라우터들 간 물리 링크를 나타냄.

컴퓨터 네트워크에 대한 추상화된 그래프 모델

그림에서 에지는 비용을 나타내고, 비용은 일반적으로 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영

ex) 노드 u에서 노드 w사이의 최소 비용 경로 => 경로비용 3 (u, x, y, w)

만약 그래프의 모든 에지가 같은 비용을 갖는다면 최소 비용 경로가 곧 최단 경로(shortest path) 임.(출발지~목적지 사이 최소 링크 포함)

 

라우팅 알고리즘 분류

1) 중앙 집중형 라우팅 알고리즘 vs 분산 라우팅 알고리즘

중앙 집중형 라우팅 알고리즘

네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산

(모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 함) 

링크 상태(link-state, LS) 알고리즘 : 전체 상태 정보를 가지는 알고리즘, 네트워크 내 각 링크의 비용을 알고 있어야 함.

 

분산 라우팅 알고리즘

라우터들에 의해 반복적이고 분산된 방식으로 최소 비용 경로 계산 수행

어떠한 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지 않음.

각 노드는 자신에 직접 연결된 링크에 대한 비용 정보만 가지고 시작하여 반복된 계산과 이웃 노드와의 정보 교환을 통해 점차적으로 목적지까지의 최소 비용 경로를 계산함.

거리 벡터(distance-vector, DV) 알고리즘 : 각 노드가 네트워크 내 모든 다른 노드까지 비용(거리)의 추정값을 벡터 형태로 유지

이웃한 라우터끼리 반복적으로 메시지를 교환하는 분산형 알고리즘은 라우터들이 직접 상호 작용하는 제어 평면에 적합.

 

2) 정적 라우팅 알고리즘 vs 동적 라우팅 알고리즘

정적 라우팅 알고리즘 : 경로가 아주 느리게 변함, 사람이 개입(사람이 직접 링크 비용을 수정 등)하기 때문

동적 라우팅 알고리즘 : 네트워크 트래픽 부하(load)나 토폴로지(망구성방식) 변화에 따라 라우팅 경로를 바꿈

                                  주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행

                              장점 : 네트워크 변화에 더 빠르게 대응 가능, 단점 : 경로의 루프(loop)나 경로 진동(oscillation)과 같은 문제에 취약

 

3) 라우팅 알고리즘이 부하에 민감한 정도

부하에 민감한 알고리즘(load-sensitive algorithms) : 링크 비용이 현재 혼잡 수준을 나타내기 위해 동적으로 변화

                                              ex) 현재 혼잡한 링크에 높은 비용을 부과하면, 라우팅 알고리즘은 혼잡한 링크를 우회하는 경로를 택할 것임

부하에 민감하지 않은 알고리즘(load-insensitive) : 링크 비용이 현재(또는 최근)의 혼잡을 반영하지 않아 부하에 민감하지 않음

                                                                                ex) 오늘날 사용되는 인터넷 라우팅 알고리즘 : RIP, OSPF, BGP

 

 

 

 

참고 도서 :

컴퓨터 네트워킹 : 하향식 접근(7판) - James F. Kurose , Keith W.Ross 지음