[Network] 라우팅 알고리즘

KOCW 컴퓨터네트워크-이석복 강의를 수강하며, 해당 내용을 바탕으로 배운 점들을 정리하였다.

라우팅 알고리즘은 크게 2가지 접근방식이 있다.

• Link state
• distance vector

Link-State Routing Algorithm

• Dijkstra 알고리즘을 기반으로 한다.

• 각 라우터가 네트워크에 대한 상태를 모두 알고 있다고 가정한 상황이다.(네트워크에 존재하는 라우터와 각 라우터간 연결 상태 및 비용)

• 특정 라우터로부터 다른 라우터로 이동하는 최단 경로를 모두 계산하고, 이를 바탕으로 fowarding table을 구성한다.

이런식으로 네트워크상의 모든 라우터로 가는데 드는 최소 비용과 그렇게 하기 위해 거쳐야하는 이전 노드(라우터)를 저장한다.

이후 백트레킹을 통해 현재 노드와 연결된 라우터들 중 어떤 라우터로 이동해야 특정 지점까지 최단거리로 이동할 수 있는지를 확인하고 fowarding table에 저장한다.

Distance Vector Algorithm

• Bellman-Ford 알고리즘을 기반으로 한다.
• x에서 y에 도달하는 최단 거리 = min(x에와 인접한 노드들까지의 거리 + x와 인접한 노드에서 y까지 도달하는 최단 거리)
• 각 노드는 최단거리 테이블의 값이 갱신되면 인접 노드에게 해당 정보를 전달한다.
• 전달받은 정보를 통해 테이블 값의 업데이트가 필요하다면 업데이트하고 변경된 정보를 다시 전달하는 과정을 반복한다.
  

생각해봐야 할 점

테이블이 유지되고 있는 상태에서 특정 간선의 cost가 변경되면, 해당 간선에 연결된 노드들은 테이블의 업데이트가 필요한지 확인하기 위해 최단거리 값을 다시 계산한다.

그림과 같이 cost값이 4였던 경로가 1로 변경되면 노드 x, y는 테이블값을 갱신한다.
y->x/ x->y 는 cost값이 4에서 1로
z->x 는 cost값이 5에서 2로 변경된다.

이렇게 cost가 감소하는 긍정적인 방향으로의 변화는 잘 반환한다.

만약 cost가 증가하는 방향으로의 변화가 일어나면 정상적으로 작동하는가.
바뀌기 전 y노드의 테이블을 생각해보면
y->x = 4
y->z = 1 이고
바뀌기 전 z노드의 테이블은
z->x = 5의 값을 가지고 있다.

여기서 y->x간선이 60으로 변경됐을 때, 기존 방식대로 테이블 값을 계산하면 y->x값은 y->x = min(y인접노드까지 거리 + y인접노드에서 x까지 비용)이므로 1 + 5 = 6으로 업데이트 된다.

이 변화에 따라 다시 연결 노드들의 테이블 업데이트가 발생하고 결국 y->x값이 실제 최소비용인 51에 도달할 때까지 순차적으로 계산이 진행된다.

poisoned reverse

해결방법은 다음과 같다.
z에서 x까지 가는 최단루트가 만약 y를 거쳐간다면
y에게는 z에서 x까지 가는 최단 비용값을 무한대로 전달한다.

z->x가 y를 거친다면, y입장에서는 z->x값은 무의미하다.(항상 거치지 않는 것이 더 유리하기 때문에)

또 이렇게 했을 경우 간선 값이 cost를 증가시키는 방향으로 변화하더라도 빠르게 안정화된다.

두 라우팅 알고리즘의 사용여부는 Network 관리자가 선택한다.

Hierarchical routing (계층적 라우팅)

Hierarchical routing 의 탄생 이유

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

hierachical routing의 특징

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

출처: https://be-developer.tistory.com/57

AS간의 통신

• Internet service를 제공하기 위해서는 비용이 발생한다.

• AS내부에서는 최단거리를 계산해서 데이터 전송 경로를 계산했지만, AS외부 네트워크에서 경로를 결정하는 것은 얘기가 달라진다.

• 서비스를 제공하는데 비용이 들기 때문에 이득을 취할 수 있는 방향으로 경로를 설정한다.

그림에서 검정색 점선으로 된 경로는 존재하지 않는다.
가운데 있는 ISP가 어떠한 이득도 취할 수 없기 때문이다.

이러한 AS간의 통신에 사용되는 프로토콜이 BGP이다.

BGP

Border Gateway Protocol

다음과 같이 AS Number를 확인하고 경로에 저장한다.
이 AS Path를 보고 어떤 경로로 데이터를 전송할 것인지 결정하는 것이다.