본 내용은 한양대학교 이석복 교수님의 강의를 참고하여 정리하였습니다. 교재는 Pearson/Addison Wesley에서 출판한 Computer networking : a top-down approach입니다.
Routing algorithms
- 노드 A에서 노드 B로 가는 최소비용 경로를 찾는 방법
알고리즘의 종류
- 경로 고정 여부
* Static routing : 관리자가 수동으로 경로를 입력
* Dynamic routing : 라우터가 상황에 따라 경로를 동적으로 결정
- Gateway 내/외부
* Interior gateway protocol : AS(Autonomous System) 내에서의 라우팅을 담당
* Exterior gateway protocol : 서로 다른 AS 사이에서의 라우팅을 담당
- Routing table 관리
* Distance vetor algorithm : routing table에 목적지까지 가는데 필요한 거리와 방향만 기록 (인접 router)
* Link state algorithm : 한 router에서 모든 routers로 가는 최단 경로를 찾아서 routing table에 기록 (모든 routers)
- 주요 routing algorithms
Link-state algorithm
- 링크 상태 정보를 모든 라우터에 전달하여 최단 경로 트리를 구성하는 라우팅 프로토콜 알고리즘
- ICMP를 이용해서 브로드캐스트를 통해 네트워크의 노드와 비용을 라우터에게 전달한 뒤 알고리즘 실행
- 다익스트라
Distance vector algorithm
- Distance를 vector로 저장하는 알고리즘
- Router는 목적지까지의 모든 경로를 테이블에 저장하지 않고, 최단 비용 경로로 가는 인접 라우터만 저장
- 인접 라우터가 가진 table을 서로 교환하며 table을 갱신
- 방법
- 동작
* 각 노드는 다음 단계를 반복한다.
1. 인접 노드들로부터 링크 비용에 변화가 있는 메시지가 올 때까지 대기
2. 메시지를 받으면, 자신의 노드의 distance vector를 갱신
3. 자신의 노드의 distance vector에 변화가 생기면, 인접 노드들에게 알림
- 예시
* 첫 번째 수행에서는 자기 자신과 연결된 노드들 간의 비용만 알고 나머지는 모르기 때문에 무한대 비용
* 두 번째 수행에서는 자신의 distance vector를 인접 노드들에게 전달, 그리고 자신에서 다른 노드들로 가는 비용 갱신
* 세 번째 수행에서는 자신의 distance vector가 갱신되었다면, 인접 노드에게 정보 전달, 그리고 변화가 없으므로 종료
- 문제
* 링크의 비용이 감소할 경우, 업데이트가 빠름
+ 예시
~ 수행 1 : 노드 y와 x는 링크의 변화를 인식하고 자신의 distance vector를 수정
~ 수행 2 : 인접 노드들에게 변경된 정보 전달하고 인접 노드들도 distance vector 수정
~ 수행 3 : 인접 노드들에게 변경된 정보 전달하고 인접 노드들도 distance vector 수정 그리고 종료
~ 세 번만에 수행 종료
* 링크의 비용이 증가할 경우, 업데이트가 느림
+ 예시
~ 안정화된 상태에서 링크 비용 변화
~ 붉은 색으로 된 숫자를 보면 값이 부정확함을 알 수 있다.
~ 결과 값이 붉은 색 6인 경우, 이 과정을 44회 반복하면 안정화 된다.
~ 결과 값이 붉은 색 5인 경우, 이 과정을 55회 반복하면 안정화 된다.
~ Routing looping인 count to infinity 문제 발생 : 계속 증가하게 된다는 의미
- 문제 해결
* 원인 : 한 라우터가 이웃 라우터들의 정보를 다 가지고 있지 못했기 때문이다. (업데이트가 느리기 때문)
* Maximum hop count : 거처가는 라우터의 횟수를 제한한다. 16이상이면 infinite로 간주하여 routing table에서 삭제한다.
* Split horizon : 라우터 B가 라우터 A로부터 정보를 수신 받았을 때, B는 A에게 반대로 동일한 정보를 송신하지 않는다.
* poision reverse : 갱신된 값을 이웃 라우터에게 전달할 때, 갱신된 값의 경로가 이웃 라우터를 거쳐가는 경우에는 갱신 값을 infinite로 보낸다. 위 붉은 색 6이 발생한 경우는, y->z->y->x의 경로이다. 중복된 경로를 가기 때문에 발생한 것이다. 다음 경로는 y->y->z->y->x이다. 따라서, 애초에 라우터 z에서 받은 경로 z->y->x = 6를 infinite로 바꾸면 반복 횟수가 줄어든다. 즉, z에서 받는 경로 중에 y를 거쳐가는 경우가 있으면 그 값을 infinite로 받으면 해결된다.
Link-state와 Distance algorithm 비교
Hierarchical routing (계측적 라우팅)
- 실제 network는 규모가 상당하기 때문에 Distance network와 Link-state 알고리즘을 바로 적용하기 힘들다.
- Distance vector는 링크가 하나 바뀌면 안정화되는 데 대단히 많은 시간이 필요
- Link state는 노드가 너무 많아서 forwarding table를 만드는 데 대단히 많은 시간 필요
- 계층적으로 관리 필요
- AS (Autonomous system)
* 계층적으로 관리하기 위한 각각의 독립적인 네트워크 영역
* Global unique number
* forwarding table은 intra-AS algorithm과 inter-AS algorithm에 의해 설정
* 예시 : SKT, KT, LG U+, etc
* Intra-AS : 같은 AS 내의 라우터는 같은 라우팅 알고리즘 사용
+ 예시 : RIP, OSPF, IGRP
* Gateway router : AS의 가장자리에 있으면서 다른 AS와 링크로 연결되어 있는 라우터
* AS 간의 관계
+ 사용하기 위해 비용을 지출하는 소비자와 네트워크를 제공하는 제공자
BGP (Border Gateway Protocol)
- Inter AS routing
- AS 간에 연결하는 알고리즘
- 선택할 수 있는 경로는 많다.
* 대학교에서 AS5 또는 AS4 또는 AS3로 갈 수 있다.
* AS3보다 AS4 또는 AS5로 가는 경로가 더 짧은 수 있겠지만, AS3를 선택하기도 한다. 예를 들어서, customer link를 거칠 때에는 한양대학교에서 비용을 지불하지 않아도 되기 때문이다.
참고
- 블로그 1
'Software Courses > Network' 카테고리의 다른 글
| Link layer : MAC protocol (0) | 2021.01.10 |
|---|---|
| Link layer : overview (0) | 2021.01.10 |
| Network : IP (0) | 2021.01.06 |
| Network : router (0) | 2021.01.06 |
| Network : overview (0) | 2021.01.06 |