네트워크 계층: 제어 평면

5.2 라우팅 알고리즘

 

라우터-링크의 그래프화

라우팅 알고리즘의 목표는 송신자부터 수신자까지 좋은 경로(=최소 비용)를 결정하는 것이다.

라우팅 문제를 나타내는데에는 그래프가 매우 적합하다.

G=(N, E)로 나타낼 수 있고 N은 라우터 E는 물리 링크에 대입된다.

 

최단 경로를 구하는 두 가지 접근 방식이 있다.

◾ 정적 라우팅 알고리즘. 모든 경로를 미리 알고있어서 경로가 고정된다. (=link state)

◾ 동적 라우팅 알고리즘. 인접한 경로만 알고 상황에 따라 경로를 바꾼다. (=distance vector)

 

 

1) 링크 상태(link state) 라우팅 알고리즘

모든 경로를 미리 알 수 있는 이유는 노드들이 브로드캐스팅을 통해 서로 동기화가 되기 때문이다.

링크 상태 라우팅 알고리즘은 다익스트라 알고리즘 그 자체이다.

모든 경로를 미리 알고있다는것은 엣지의 가중치를 모두 알고있다는 얘기이기 때문에 다익스트라 알고리즘을 수행하면 최적의 경로가 산출된다.

 

목적지까지의 최소 비용을 백트래킹 하면 경로를 구할 수 있다.

 

하지만 현실적으로 전 세계에 존재하는 모든 라우터가 동기화 되는것은 불가능에 가깝기 때문에 브로드캐스팅의 범위는 관리주체가 동일한 하나의 네트워크 까지만이다.

 

 

2) 거리 벡터(distance vector) 라우팅 알고리즘

동적 계획법에 의해 구해지지만 모든 경로를 미리 알고있는 상태가 아니므로 인접 노드들과 메시지를 주고 받으며 자신의 거리 벡터를 갱신하여 라우팅 테이블을 작성해나간다.

 

인접 노드로부터 거리 벡터 메시지를 받으면 자신의 거리 벡터를 갱신하고 갱신이 이루어졌을 경우 인접 노드들에게 거리 벡터 메시지를 보낸다.

 

더이상 자신의 거리 벡터가 갱신되지 않으면 안정화가 되어서 거리 벡터 메시지를 보내지 않는다.

 

 

◾ 거리 벡터 알고리즘: 링크 비용 변경과 링크 고장

만약 링크의 비용이 변경되는 경우 링크와 연결된 노드들은 자신의 거리 벡터를 다시 계산하고 갱신되면 인접 노드들에게 거리 벡터 메시지를 보낸다.

링크의 비용이 기존보다 더 작아진 경우에는 금방 안정화가 이루어지지만 기존보다 더 커진경우에는 갱신 횟수가 굉장히 많아질 수 있다. (무한 계수 문제, count to infinity problem)

 

 

◾ 거리 벡터 알고리즘: 포이즌 리버스 추가

자신의 거리 벡터를 갱신할 때, 인접 노드로부터 받은 거리 벡터에 의해 갱신이 이루어지면 경유하는 경로에 해당하는 노드에게는 자신의 경로를 무한대라고 알려준다.

위의 그림에서 z-x의 경로는 초기에 7이었으나 거리 벡터 알고리즘에 의해 최종적으로 y를 경유하는 3으로 갱신된다.

이 때, y를 경유해서 갱신되었기 때문에 next hop인 y에게는 z-x의 비용을 무한대라고 알려준다.

 

 

◾ LS와 DV 알고리즘의 차이

링크 상태 라우팅 알고리즘	거리 벡터 라우팅 알고리즘
중앙 집중형	분산형
네트워크 전체 인식	인접 라우터의 정보만 인식
다익스트라 (그리디)	벨만-포드 (동적계획법)
동기적	비동기적
이벤트 기반의 갱신 신호 교환	주기적으로 거리 벡터를 교환

 

 

5.3 인터넷에서의 AS 내부 라우팅: OSPF

 

하지만 LS, DV 알고리즘 둘 다 대규모 네트워크에 직접 적용하기에는 문제가 있다.

LS는 브로드캐스팅을 주고받느라 포워딩 테이블이 영원히 완성되지 않을것이고, DV는 라우팅 테이블의 안정화가 영원히 이뤄지지 않을 것이다.

 

이 문제는 라우터들을 자율 시스템(autonomous system, AS)으로 조직화 해서 해결할 수 있다.

AS는 동일한 관리 제어하에 있는 라우터의 그룹으로 구성되고 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용한다. (예: 대학교, 지역ISP)

AS들은 ICANN의 지역 등록 기관에 의해 AS번호가 부여되어 관리된다.

 

ISP간에 계층이 존재해서 서로 제공자-고객 관계가 되어 비용을 지불하는 것처럼 AS간에도 계층이 존재해서 제공자-고객 관계가 성립한다. (예: 지역ISP-대학교)

제공자-고객 관계는 암묵적으로 연결이 필요한쪽이 고객이 된다.

AS가 서로를 필요로 하는 경우는 제공자-고객 관계가 성립되기 어렵기 때문에 피어링이라는 동등한 관계로 맺어진다.

 

OSPF 프로토콜은 모든 라우터가 아닌 AS 내부의 라우터들만 링크 상태 알고리즘을 수행한다.

 

 

5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅: BGP

 

동일한 AS 내부에 있는 출발지와 목적지 사이에서 패킷을 라우팅 할 때의 경로는 AS 내부 라우팅 프로토콜에 의해 결정된다. 하지만 패킷이 여러 AS를 통과하게 되는 경우 AS간의 라우팅 프로토콜이 필요하게 된다.

통신하는 AS간의 프로토콜은 동일해야 하고 일반적으로 경계 게이트웨이 프로토콜(BGP, Border Gateway Protocol)을 사용한다.

AS간의 패킷 이동

 

AS 가장자리에 있는 게이트웨이 라우터들 끼리 BGP가 이루어진다.

 

경로 정보를 인접한 AS에게 자신의 AS 번호를 담아서 브로드캐스팅 하면 AS 경로가 누적되어 계속 브로드캐스팅 된다.

이렇게 받은 경로 정보들 중 원하는 경로를 선택하는 것은 각 AS의 정책에 의해 이루어진다.

가장 짧은 경로를 선택하는것이 이상적이지만 보통은 고객 AS에게 보내는걸 우선적으로 한다. (고객 > 피어 > 제공자 순)

 

 

5.6 인터넷 제어 메시지 프로토콜(ICMP)

 

호스트와 라우터간에 네트워크 계층 정보를 주고받기 위해 사용되는 프로토콜이다.

주로 오류보고에 사용된다.

 

ICMP 메시지 타입

ICMP는 라우터가 생성하며 IP 패킷의 데이터 영역에 담겨서 전송된다.

traceroute가 ICMP로 구현되어있다. TTL을 1부터 점차 늘려나가서 경로를 추적한다.