Chap 4,5. Network Layer

forwarding: router의 input으로부터 적절한 router의 output으로 packet을 옮기는 것

routing: 출발지로부터 목적지까지 packet의 경로를 결정하는 것.

 

 

Longest prefix matching

: 주어진 목적지 주소로 forwarding table을 찾아볼 때, 

가장 긴 주소와 매칭되는 인터페이스를 매칭하는 방법.

 

forwarding table이 다음과 같이 있을 때, 

목적지 주소가 다음과 같다면 

-> 0번 인터페이스와 매칭된다.

-> 1번 인터페이스와 매칭된다.

 

 

Scheduling mechanism

scheduling: link를 따라 보낼 다음 packet을 선택하는 것

FIFO(First In Fisrt Out) scheduling: queue에 도착한 순서대로 packet을 보내는 것

 

discard policy: 만약 꽉 찬 queue에 packet이 도착했다면 누구를 버려야 하나? 에 관한 정책

• tail drop: 방금 도착한 packet을 버린다
• priority: 우선순위에 따라 버린다
• random: 랜덤으로 버린다

 

 

Routing protocol

: router의 네트워크를 통해 sending host로부터 receiving host까지의 

"good" 경로를 결정하는 일.

1. path finding
2. path determination
3. path select
-> 경로 찾고 결정해서 선택

• "good"이란? 
  -> 비용이 적게 든다, 빠르다, 혼잡이 적다

 

Routing algorithm의 분류

 

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

 

global:

• 모든 router가 모든 topology와 모든 링크 비용의 정보를 가진다.
  * topology: 네트워크가 연결되는 방식과 서로 다른 장치 간에 데이터가 흐르는 방식을 정의한다.
  물리적 토폴로지는 네트워크 장치의 물리적 배열과 이를 연결하는 데 사용되는 케이블을 나타내고,
  논리적 토폴로지는 물리적 위치에 관계없이 네트워크 장치의 논리적 연결을 나타낸다.
• 대표적으로 link state algorithm이 있다.

local(decentralized):

• router는 바로 물리적으로 연결된  topology와 링크 비용의 정보를 가진다
  -> 부분적으로 topology 정보를 가진다
• 대표적으로 distance vector algorithm이 있다.

 

 

Link-State Routing Algorithm

• Dijkstra's algorithm을 사용한다
  -> 한 노드에서 다른 노드로 가는 최소한의 비용이 드는 경로를 계산
• N개의 노드가 있을 때, N번을 반복하면서 각 노드까지의 최소비용을 계산하는 알고리즘.
• c(i, j): node i부터 j까지의 비용. 
• D(v): 목적지 v까지의 비용
• P(v): 목적지 v로 가는데 거치는 직전 노드
• N: 노드의 집합

수도코드

 

 

 

Distance Vector Routing Algorithm

 

 

• Bellman-Ford algorithm 사용한다.
• 각 노드는 직접적으로 연결된 이웃하고만 communicate 한다
  -> via는 출발지와 바로 연결된 노드만 가능.
• 전체 네트워크 topology는 알지 못하고, 본인이 가진 정보와 이웃 라우터의 정보를 가지고
  최소비용을 계산하는 알고리즘.
• 변화가 없을 때까지 반복한다

수도코드

 

 

 

link state VS distance vector

	link state	distance vector
장점	라우터간에 서로 변경된 정보를 주고 받는 데 걸리는 시간(convergence time)이 빠름	라우팅 테이블 작음 -> 메모리 절약
	라우팅 테이블 교환 오버헤드 감소	계산속도 빠름
	필요정보만 교환하여 네트워크 트래픽 감소
	최적경로 찾아냄
단점	라우팅 테이블 메모리 대량 소모	주기적 정보교환으로 네트워크 트래픽 과다
	경로계산을 위한 CPU 부하 발생	변경 시 최적경로가 아닐 수 있음
		convergence time이 느림