[네트워크] 라우팅 알고리즘 (Link State, Distance Vector)

네트워크 관련 글 순서(참조 영상 기준)

애플리케이션 계층
- 네트워크 애플리케이션의 원리
- DNS
- TCP를 이용한 Socket 프로그래밍

전송계층
- 전송 계층 서비스의 원리
- rdt 원리
- 연결 지향 전송: TCP
- TCP 흐름 제어(3-way handshake, 4-way handshake)
- TCP 혼잡 제어

네트워크 계층
- 네트워크 계층 서비스
- Network Address Translation(NAT), DHCP
- 라우팅 알고리즘(Link State, Distance Vector)
- 계층적 경로 변경(AS)

링크 계층
- 다중 엑세스 프로토콜
- LANs(근거리 통신망)

무선 및 모바일 네트워크
- 무선 네트워크

웹 요청 시 일어나는일

네트워크 보안
- 대칭키 & 공개키,RSA 암호화
- Secure e-mail, SSL, MAC
- IPSec(ESP), Firewall(방화벽)

 

라우팅 알고리즘

송신자로부터 수신자까지 데이터를 전송할때 어떤 라우터들을 통과해서 가야할지 경로를 선택하는 알고리즘.

이 라우팅 알고리즘에 의해 fowarding table이 구성된다.

 

Static

• Forwarding Table을 직접 만드는 방법

Dynamic

• Forwarding Table을 네트워크 상태에 따라 업데이트하는 방법
  • Link State(LS), Distance Vector(DV), Hierarchical 방법이 있다.

 

여기선 다이나믹 알고리즘에대해서 다룬다.

 

링크 상태 알고리즘(Link State)

• 대표적으로 Dijsktra's Algorithm
• 네트워크 토폴로지^[각주:1]와 모든 링크 비용의 정보를 토대로, 노드로부터 다른 노드들의 최소 비용을 계산.
  • 해당 정보는 ICMP패킷^[각주:2]을 broadcast를 하여 네트워크 토폴로지와 링크 비용을 파악할 수 있음.
• N개의 노드가 있을때, N번을 반복하면서 각노드로까지의 최소 비용을 계산하는 알고리즘.
•  추후 알고리즘편으로 올릴 예정.

 

거리 벡터 알고리즘(Distance Vector)

• 전체 네트워크 토폴로지는 알지 못하고, 본인이 가진 정보와 이웃 라우터의 갱신정보^[각주:3]를 가지고 최소비용을 계산하는 알고리즘.
• 경로의 비용에 변화가 있을 경우, 이웃에게 새로운 거리 비용이 담긴 벡터를 보냄으로서 정보를 고쳐나감.
• 비동기적이고 반복적으로 변화가 없을때까지 수행.
• 대표적으로 벨만포드 알고리즘 사용.
• 추후 알고리즘편으로 올릴 예정.

 

---

타 블로그 참조 내용(아래 참조 확인)

링크 상태 vs 거리 벡터

구분	항목	거리벡터(Distance Vector)	링크상태(Link State)
경로 설정	기준	거리와 방향 기준	전체 토폴리지 고려
	주요 메트릭	Hop count	Symbolic length
	계산 방식	라우터간의 거리 합산	다른 라우터까지의 최단 경로 계산
	알고리즘	벨만-포드	다익스트라
갱신	대상	인접 라우터	모든 라우터
	시점	일정 주기	링크 변화 발생시(이벤트)
	교환 정보	라우팅 테이블	링크 상태 정보
라우팅테이블	라우팅 테이블 정보	이웃 라우팅 정보	네트워크 전체
	필요 메모리	적음, 적은 라우팅 테이블	많음. 큰 라우팅 테이블
	전송	테이블 전체 전송	변경된 정보만 전송
규모		작은 규모 네트워크 적합	큰 규모 네트워크 적합

 

 

항목	거리 벡터	링크 상태
장점	라우팅 테이블 작음 -> 메모리 절약	컨버전스 타임[footnote]라우터간에 서로 변경된 정보를 주고 받는 데 걸리는 시간[/footnote[빠름
	동작수행속도 빠름	라우팅 테이블 교환 오버헤드 감소
		필요정보만 교환 -> 네트워크 트래픽 감소
		최적경로 찾아냄
단점	컨버전스 타임이 느림	라우팅 테이블 메모리 대량 소모
	주기적 정보교환 ->네트워크 트래픽 과다	SPF 등 경로계산을 위한 CPU 부하 발생
	네트워크 변화 감지 소요시간 김
	변경 최적경로가 아닐 수 있음

 

 

---

참조

 

KOCW 네트워크 강의 - 한양대 2018 1학기 이석복 교수님

컴퓨터네트워크

링크 상태 vs 거리 벡터 차이 참조

010. 거리벡터 라우팅(Ditance Vector Routing)과 링크 스테이트 라우팅(Link State Routing)

 

1. 컴퓨터 네트워크의 요소(링크, 노드 등)들을 연결해놓은 것. 또는 그 방식 [본문으로]
2. 통신 오류 보고와 오류 수정 기능을 가진 패킷. IP프로토콜을 기반으로 동작. [본문으로]
3. 이웃 노드까지가는데 최소비용이 담긴 정보 [본문으로]