이 글은 컴퓨터 네트워크 수업내용을 정리한 글임을 알림니다.

라우팅을 할때 사용되는 두가지 알고리즘에 대해 서술 하려 한다.

1. Link-state 라우팅(다익스트라)

• 다익스트라 알고리즘을 이용 (쇼티스트 패스 first)
• 노드를 기준으로 동작

모든 정보를 제어하는 Remote 라우터가있을때 사용하는 알고리즘 이다.

표기법

표기법

• D(v) : 목적지 v까지 거리
• p(v) : v 이전 노드
• N' : 최단 경로노드가 추가되는 temp 노드 집합

중요한 것은

노드가 1개…2개…3개 될때마다 릴랙스!!

이다.

위 그림에서 서술해 보자면

1. 출발지에서 주변 노드의 경로를 계산 (나머지는 무한) (u에서 인접과 나머지는 무한으로 표기한 모습)
2. 출발지에서 다음으로 가장 적은 경로를 선택해 접근 한뒤 N`에 넣기 (그림에서 가중치가 3인 w를 선택한 모습)
3. 접근한 노드의 인접 가중치를 모두 고려해 출발지에서 접근한 노드의 인접 노드 의 경로를 모두 업데이트 ( w로 갔을때 주변 노드중 v를 봤을 때 3+3=6으로 원래 7보다 작아서 업데이트 됨, 또한 y 역시 무한에서 3+8로 업데이트 된다.)
4. 그다음 u에서 갈수있는 곳중에 가장 작은 노드로 접근후 N`에 추가 (현재 5,6,7,11중 5이므로 x를 선택)
5. 접근한 노드의 인접 가중치를 모두 고려해 출발지에서 접근한 노드의 인접 노드 의 경로를 모두 업데이트 (x로 갔을때 주변 노드중 w, y, z 중 업데이트 되는 것은 무한→14로 z업데이트 밖에 없다.)
6. 그다음 u에서 갈수있는 곳중에 가장 작은 노드로 접근후 N`에 추가 (현재 6,7,11,14중 6이므로 v를 선택)
7. …
8. 모든 노드가 N`에 들어오면 마무리 된다.

2. Distance Vector (벨만 포드)

• 인접한 라우터의 정보를 받아 라우팅 테이블을 만들어 나감
• 벨만포드 이큐에이션를 이용해 테이블을 완성

중요한 것은

간선이 1개…2개…3개 될때마다 릴랙스!!
u 노드에서 z 노드까지의 최적 경로를 구하고 싶은데 정보가 부족하니 주어진 정보를 활용해서 du(z) 를 구하자는 방식!!

1. 출발지에서 주변 노드의 경로를 계산 (나머지는 무한) (u에서 인접과 나머지는 무한으로 표기한다.)
2. 출발지에서 간선 하나로 가는 곳 모두 릴랙스 (그림에서 v,w,x 를 2,5,1로 릴랙스 가능하다.)
3. 간선 2두개 가는곳 모두 릴랙스 (z는 9으로, y는 2 등등… )
4. …
5. 노드의 갯수 - 1개의 간선을 조사하면 마무리 된다.