이번 회차에서는 네트워크계층의 핵심기능인 '라우팅'과 '라우팅알고리즘'에 대해 공부할 것이다! 라우팅에 대해서 배우고, 경로를 설정하는 다양한 방식에 따라 다른 9개의 라우팅 알고리즘을 배워보자!
라우팅(Routing) (=경로설정) <-네트워크계층의 핵심기능
1. 라우팅이란 노드(라우터)가 동적인 or 정적인 라우팅정보를 이용해서 패킷을 어디로 보낼 건지 결정하는 기능!
2. 라우팅을 할때는 정확성, 단순성, 견고성, 공평성, 효율성을 고려해야 함!
3. 라우팅 방식에는
미리 결정된 경로로만 라우팅하는 Nonadaptive 라우팅알고리즘 ->네트워크 변화를 고려하지않지롱
네트워크 변화를 라우팅할때 반영하는 Adaptive 라우팅알고리즘!
((Nonadaptive는 초기 라우팅알고리즘이었고, Adaptive는 환경변화에 잘 적응하는 더 좋은 알고리즘!))
**여기서 네트워크 변화로는
Topology(네트워크 상황의 변화(공유기가 1개->2개로 바뀌는 경우)) , traffic load(네트워크 노드들의 혼잡도) , failure (장애, 오류)
'테이블 관리 방법에 따른 분류' 라고도 할 수 있음! 즉, 정적 라우팅(Nonadaptive)은 네트워크 관리자가 직접 목적지 별로 네트워크 경로를 지정하는 방식! (관리자가 변경하지 않을 경우 테이블 내용 변하지X) . 반면 동적 라우팅(Adaptive)은 네트워크의 변동된 정보를 라우터 간에 자동으로 교환하여 업데이트하는 방식!
4. 노드(라우터) 구조 : 라우팅 알고리즘 탑재 + 라우팅 테이블 (라우팅정보를 저장하는 테이블, 라우터가 생성&관리함)
->Nonadaptive: 모든 패킷에 대해서 항상 동일한 결과 + 정적 라우팅정보가 저장된 라우팅테이블
->Adaptive: 패킷마다 결과가 각각 다를 수 있음 + 동적 라우팅정보가 저장된 라우팅테이블
5. 라우팅의 성능지표 (경로를 설정하는 기준!!)
-Number of hops (홉의 최솟값!)
-Average packet delay (패킷 지연 시간)
-Cost (코스트값)
-Throughput
6. 라우팅의 결정시점
-Packet단위 (datagram 방식) : 패킷을 어디로 보낼지 결정할때 라우팅발생
-Session단위 (virtual circuit 방식) : 패킷의 경로를 어디로 설정할지 결정할때 ~
7. 라우팅의 결정지점
-각 노드(distributed) : 각 노드에서 경로를 결정하는 경우
-중앙 노드(centralized) : 중앙노드가 경로를 결정하는 경우
-소스 노드(source) : 출발할 때 소스노드가 경로를 결정하는 경우
8. 라우팅테이블 업데이트 시점
-Continuous (지속적으로 업데이트)
-Periodic (주기적으로 업데이트)
-Major load change (네트워크 부하가 심하게 걸릴때!)
-Topology change (위상이 바뀔때!)
라우팅 알고리즘
**라우팅알고리즘을 쉽게 말하자면, 네트워크 계층을 통해 정보(포켓) 이동 시, 최적의 경로를 결정하기 위한 방식 이다. 즉, 정보(포켓)를 목적지까지 전송하기 위해서 인접한 라우터들의 네트워크 정보와 매트릭 값을 받아 최적의 경로를 설정하는 과정 이란 소리!
1. 분류 -Nonadaptive Routing algorithm - Shortest Path Routing Algorithm
- Flooding //
-Adaptive Routing algorithm - Distance Vector 라우팅알고리즘
- Link State 라우팅알고리즘
- Random //
- Hierarchical //
- Broadcasting //
- Multicasting //
- Anycasting //
라우터의 구조를 간단히 말해보자면,
데이터링크계층에서 Packet을 수신받아서 수신Queue에 Store하고 들어온것부터 한개씩 라우터로 가서 라우팅알고리즘을 통해 (라우팅테이블에 저장된 정보를 이용해서) 경로설정(Routing)을 해서 Forwarding을 함!
Nonadaptive Routing Algorithm
Shortest Path Routing Algorithm <-가장 짧은 길이(cost)를 찾는 알고리즘이라 생각하면 쉬움!
- 다익스트라(Dijkstra)가 제안한 그래프 이론에서의 Shortest path 알고리즘을 도입
- 네트워크(그래프) 상에서 각 노드간의 최단 경로를 찾는 알고리즘을 이용한 방식
- 링크에 cost 부여하고, 출발지와 목적지 간의 cost합 중 최저값을 갖는 경로를 선택!
<그림 속> 오른쪽 네트워크 토폴로지에서 N1->N6을 예시로 하면,
홉의 수 기준 : N1->N3->N6, 최단거리 기준 : N1->N4->N5->N6
정리를 하자면,
1. 각각의 노드는 다 (라우팅정보가 저장된) 라우팅테이블을 갖고 있음!
2. 정적인 라우팅정보(홉의 수, cost거리)를 이용해서 패킷의 전송경로를 지정!
=>각 노드 간의 최단거리 기준으로 라우팅 수행!