Library/Computer Network
Unicast Routing Protocol
Celdee
2008. 6. 11. 05:17
인터넷은 한가지 라우팅 프로토콜로 정의되기에는 너무 크게 확장되었으며, 이런 이유 때문에 인터넷은 AS(Automonous System ; AS)로 나눠진다. AS는 하나의 단일 관리 기관 하에 있는 라우터와 네트워크의 이름이다. AS에서의 라우팅을 도메인 내(intradomain)에서의 라우팅이라 한다. AS 간의 라우팅을 도메인 간(interdomain) 라우팅이라 한다. 각 AS는 AS 내의 라우팅을 처리하기 위해 하나 이상의 도메인 내 라우팅 프로토콜을 사용한다. 그러나, AS 간의 라우팅을 처리하기 위해서는 하나의 도메인 간 라우팅 프로토콜을 사용한다.
몇가지 도메인 내, 및 도메인 간 라우팅 프로토콜이 사용되고 있다. RIP(Routing Information Protocol)는 거리 벡터 프로토콜의 구현이고, OSPF(Open Shortest Path First)는 링크 상태 프로토콜의 구현이다. BGP(Border Gateway Protocol)는 경로 벡터 프로토콜의 구현이다.
거리 벡터 라우팅에서, 각 노드는 자신과 직접 연결된 이웃과, 라우팅 테이블을 주기적으로, 또는 변화가 있을 때마다 통보하는 방식을 통해 공유한다. 먼저, 이웃에게 라우팅 정보를 받았다면, 자기 자신과 송신 노드 사이의 값을 더하고, 이런 방식으로 수정된 라우팅 테이블과 예전의 라우팅 테이블을 비교해서 작은 값을 선택하여 갱신한다.
거리 벡터 라우팅과 다른 방식으로, 링크 상태 라우팅이 있다. 이 방법 역시 도메인 내 라우팅에서 사용되는 방법인데, 이것은 각자의 노드가 자신의 링크 상태 정보를 가지는 링크 상태 패킷(LSP)를 발송하여, 모여진 링크 상태 정보를 사용하여 최단 경로를 알아낸다.
거리 벡터 라우팅의 문제점은 불안정하다는 것이다. 즉, A와 B가 있을 때, X가 A를 거쳐서 갈 수 있는 경로라 하자. 여기서, A에서 X까지 연결에 문제가 생겼다고 하자. 이때 노드 A는 자신의 라우팅 테이블 정보를 변경하며, 변경된 정보는 B에게 전달된다. B가 A에게 라우팅 정보를 받기 전에 자신의 라우팅 정보를 갱신하면 문제가 복잡해진다. B의 라우팅 저보가 A에게 전달되기 때문에, A는 B가 X에게 가는 경로를 찾았다고 생각하고 즉각 자신의 정보를 수정하게 된다. 트리거 갱신 정책에 따라 즉각 이 사실은 B에게 통보되며, B는 A에 변화가 있다고 생각하고 자신의 라우팅 정보를 수정하게 된다. 이 과정은 계속 반복되어 X까지 도달하는 비용이 무한대로 증가한 시점이 되어서야 X에 도달하는 것이 불가능하다는 것을 알게 된다. 이 시점까지, 시스템은 불안정하게 된다.
이 문제를 해결하기 위해서 몇 가지 해결책이 제시될 수 있는데, 도달 할 수 없는 경로를 의미하는 무한대의 값을 낮게 잡거나, 두 노드 사이에서는 split horizon, poison revers 따위의 방법을 통해 해결 할 수 있지만, 노드가 셋 이상이 되면 마찬가지 문제가 발생 할 수 있다.
첫번째 해결책인 무한대를 작게 설정하는 방법은, 사실 거리 벡터 라우팅의 대부분의 구현에서 각 노드 간의 거리를 1로, 16을 무한대로 정의한다. 즉, 이것은 거리 벡터 라우팅이 큰 시스템에서는 사용될 수 없음을 의미한다. 각 방향으로의 망의 크기가 15홉을 넘을 수 없다.
다른 해결 방법으로, 수평 분할(split horizon)이 있다. 이 정책에서는, 각 인터페이스를 통해 테이블을 플러딩(flooding)하는 대신에 각 인터페이스를 통해 자신의 테이블의 일부 만을 전송한다. 만약 테이블에 기반을 두고 노드 B가 생각하기를, X에 도달하는 최적읜 경로가 A를 거치는 것이라면 이 정보를 A에게로 전달할 필요할 필요는 없다. 이 정보는 A로부터 온 것이므로 이미 A는 알고 있기 때문이다. A로부터 정보를 받아 이를 수정한 후 다시 A에게로 보내는 것이 혼란을 발생시킬 수 있다. 우리 시나리오에서 노드 B는 A에게로 보내기 전에 라우팅 테이블에서 마지막 라인을 제거하게 된다. 이 경우 노드 A는 X까지의 거리를 무한대로 유지하게 된다. 나중에 노드 A가 자신의 라우팅 테이블을 B에게 전송하면 노드 B도 자신의 라우팅 테이블을 수정하게 된다. 따라서 처음 갱신 이후 시스템은 안정적으로 되고 노드 A와 B 모두 X로의 경로가 도달 가능하지 않음을 알게 된다.
하지만, 이 방법은 하나의 단점을 가진다. 보통 거리 벡터 프로토콜은 타이머를 사용하고 만약 경로 상에 새로운 소식이 없으면 테이블에서 이 경로를 제거한다. 이전 시나리오에서 노드 B가 A로 보내는 광고에 X로의 경로를 제거해 버리면, 노드 A는 이것이 수평 분할 정책 때문에 그런 것인지, 아니면 B가 최근에 X에 관한 정보를 받지 못해서 인지 예측할 수 없다. 수평 분할 정책은 poision reverser 정책과 조합되어 질 수 있다. 노드 B는 여전히 X에 대한 값을 전달하지만, 만약 정보의 송신자가 A인 경우 거리 값을 무한대로 설정해서 이 값은 A로 부터 받았기 때문에 A가 이 값을 사용하지 않도록 경고 할 수 있다.
몇가지 도메인 내, 및 도메인 간 라우팅 프로토콜이 사용되고 있다. RIP(Routing Information Protocol)는 거리 벡터 프로토콜의 구현이고, OSPF(Open Shortest Path First)는 링크 상태 프로토콜의 구현이다. BGP(Border Gateway Protocol)는 경로 벡터 프로토콜의 구현이다.
거리 벡터 라우팅에서, 각 노드는 자신과 직접 연결된 이웃과, 라우팅 테이블을 주기적으로, 또는 변화가 있을 때마다 통보하는 방식을 통해 공유한다. 먼저, 이웃에게 라우팅 정보를 받았다면, 자기 자신과 송신 노드 사이의 값을 더하고, 이런 방식으로 수정된 라우팅 테이블과 예전의 라우팅 테이블을 비교해서 작은 값을 선택하여 갱신한다.
거리 벡터 라우팅과 다른 방식으로, 링크 상태 라우팅이 있다. 이 방법 역시 도메인 내 라우팅에서 사용되는 방법인데, 이것은 각자의 노드가 자신의 링크 상태 정보를 가지는 링크 상태 패킷(LSP)를 발송하여, 모여진 링크 상태 정보를 사용하여 최단 경로를 알아낸다.
거리 벡터 라우팅의 문제점은 불안정하다는 것이다. 즉, A와 B가 있을 때, X가 A를 거쳐서 갈 수 있는 경로라 하자. 여기서, A에서 X까지 연결에 문제가 생겼다고 하자. 이때 노드 A는 자신의 라우팅 테이블 정보를 변경하며, 변경된 정보는 B에게 전달된다. B가 A에게 라우팅 정보를 받기 전에 자신의 라우팅 정보를 갱신하면 문제가 복잡해진다. B의 라우팅 저보가 A에게 전달되기 때문에, A는 B가 X에게 가는 경로를 찾았다고 생각하고 즉각 자신의 정보를 수정하게 된다. 트리거 갱신 정책에 따라 즉각 이 사실은 B에게 통보되며, B는 A에 변화가 있다고 생각하고 자신의 라우팅 정보를 수정하게 된다. 이 과정은 계속 반복되어 X까지 도달하는 비용이 무한대로 증가한 시점이 되어서야 X에 도달하는 것이 불가능하다는 것을 알게 된다. 이 시점까지, 시스템은 불안정하게 된다.
이 문제를 해결하기 위해서 몇 가지 해결책이 제시될 수 있는데, 도달 할 수 없는 경로를 의미하는 무한대의 값을 낮게 잡거나, 두 노드 사이에서는 split horizon, poison revers 따위의 방법을 통해 해결 할 수 있지만, 노드가 셋 이상이 되면 마찬가지 문제가 발생 할 수 있다.
첫번째 해결책인 무한대를 작게 설정하는 방법은, 사실 거리 벡터 라우팅의 대부분의 구현에서 각 노드 간의 거리를 1로, 16을 무한대로 정의한다. 즉, 이것은 거리 벡터 라우팅이 큰 시스템에서는 사용될 수 없음을 의미한다. 각 방향으로의 망의 크기가 15홉을 넘을 수 없다.
다른 해결 방법으로, 수평 분할(split horizon)이 있다. 이 정책에서는, 각 인터페이스를 통해 테이블을 플러딩(flooding)하는 대신에 각 인터페이스를 통해 자신의 테이블의 일부 만을 전송한다. 만약 테이블에 기반을 두고 노드 B가 생각하기를, X에 도달하는 최적읜 경로가 A를 거치는 것이라면 이 정보를 A에게로 전달할 필요할 필요는 없다. 이 정보는 A로부터 온 것이므로 이미 A는 알고 있기 때문이다. A로부터 정보를 받아 이를 수정한 후 다시 A에게로 보내는 것이 혼란을 발생시킬 수 있다. 우리 시나리오에서 노드 B는 A에게로 보내기 전에 라우팅 테이블에서 마지막 라인을 제거하게 된다. 이 경우 노드 A는 X까지의 거리를 무한대로 유지하게 된다. 나중에 노드 A가 자신의 라우팅 테이블을 B에게 전송하면 노드 B도 자신의 라우팅 테이블을 수정하게 된다. 따라서 처음 갱신 이후 시스템은 안정적으로 되고 노드 A와 B 모두 X로의 경로가 도달 가능하지 않음을 알게 된다.
하지만, 이 방법은 하나의 단점을 가진다. 보통 거리 벡터 프로토콜은 타이머를 사용하고 만약 경로 상에 새로운 소식이 없으면 테이블에서 이 경로를 제거한다. 이전 시나리오에서 노드 B가 A로 보내는 광고에 X로의 경로를 제거해 버리면, 노드 A는 이것이 수평 분할 정책 때문에 그런 것인지, 아니면 B가 최근에 X에 관한 정보를 받지 못해서 인지 예측할 수 없다. 수평 분할 정책은 poision reverser 정책과 조합되어 질 수 있다. 노드 B는 여전히 X에 대한 값을 전달하지만, 만약 정보의 송신자가 A인 경우 거리 값을 무한대로 설정해서 이 값은 A로 부터 받았기 때문에 A가 이 값을 사용하지 않도록 경고 할 수 있다.