네트워크계층 - 라우팅 알고리즘

※kocw에서 제공하는 이석복 교수님의 컴퓨터네트워크 수업을 듣고 필기한 내용입니다.

출처를 따로 밝히지 않는 한 전부 해당 수업에서 제공한 자료들이며 제가 작성한 부분에 있어 틀린 부분이 있을 수도 있다는 점 양해바랍니다.

---

 

 

라우팅 알고리즘

---

 

- 포워딩 테이블을 체우는 알고리즘

- 라우팅 알고리즘의 2종류

1. link state algorithm: 모든 라우터 정보를 알고 알고리즘을짬

2. distance vector algorithm: 이웃된 라우터 정보만 알고 알고리즘을 짬

 

 

 

Link state algorithm

---

- 각 링크가 브로트케스트로 자기 정보를 보내서 모든 링크의 정보를 알고있게 만듬

- 모든 정보를 알고있으나 데이크스트라 알고리즘 사용

데이크스트라 알고리즘: ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

example

 

 

u -> z 최단 경로 구하기

"u"	N`	D(v)	D(w)	D(x)	D(y)	D(z)
round 0	{u}	7,u	3,u	5,u	∞	∞
round 1	{w,u}	6,w		5,u	11,w
round 2	{x,w,u}	6,w			11,w	14,x
round 3	{v,x,w,u}				10,v	14,x
round 4	{y,v,x,w,u}					12,y

N`: 현재까지 최단거리를 확실하게 알고있는 노드의 집합

D(): distance 값

 

"u" 에서 각 노드의 최단 거리(u의 포워딩 테이블)

destination	routing
v	w
x	x
y	w
w	w
z	w

- routing필드는 목적지가 destination일때 보낼 다음 이웃 노드

- 이런식으로 각각의 라우터는 각각의 포워딩 테이블을 가지고있음

- 포워딩 테이블에 따라 데이터를 전달할 노드를 선택하면 됨

 

 

distance vector algorithm

---

 

- 출발지 u에서 목적지 z까지의 거리를 재귀적으로 구하는 알고리즘

- link state algorithm과 달리 모든 라우터 정보를 알고 있는게 아니라 이웃된 라우터 정보만 알고 있음(vector에 저장)

- 자기가 알고 있는 라우터 정보를 이웃 라우터에게 전달해야됨, 이때 vector(array)로 보낸다고 해서 distance vector algorithm

- 정보를 받을 때마다 거리를 계산해서 update 시 다시 주변에 정보를 전달, 혹은 라우터 정보가 바뀔때마다 주변에 정보를 전달

- 1턴 1턴씩 동작

- 1턴때마다 받은 정보들로 라우터와의 거리를 계산함

- update 될 거리가 있으면 이웃 라우터에게 새로 전송

- update가 더이상 되지 않을때까지 반복, 더이상 update 안되면 그걸로 포워딩 테이블 짬

- 들어온 패킷의 목적지까지 가장 짧은 라우터로 보냄

 

- 옆 이웃들에게 정보를 받을 때 자기 자신을 거쳐가는 경로가 있으면 나중에 거리가 바뀔때 count-to-infinity가 발생할 수 있음

-  자기 자신을 거쳐가는 경로는 ∞로 주는 poisoned reverse 방법을 사용해야됨

 

 

autonomous systems(AS)

---

- 자치권, 각각의 네트워크에서는 각자가 어떤 라우팅 알고리즘을 사용할 건지 정함

- link state algorithm, distance vector algorithm은 Intra-AS 라고함

- 각각의 Intra-AS는 고유의 숫자를 가지고 있음(ASN)

- 둘다 특정 범위 내에 네트워크에서만 적용 가능

- 전체 네트워크에 적용하기에는 무리가 있음

- link state algorithm로 구현한 프로토콜이 OSPF 프로토콜

- distance vector algorithm로 구현한 프로토콜은 RIP 프로토콜

- 더 큰 범위의 네트워크 끼리의 라우팅 알고리즘은 Inter-AS라고함

 

Inter-AS

- hierarchical routing으로 구현한 프로콜인 BGP 프로토콜을 사용함

 

- 세상에는 60000+개의 AS가 존재함, 그 AS사이에도 급(?)이 있음

- 네트워크를 제공해주는(skt같은) AS를 provider라고 하고 네트워크를 제공받는(한양대 등) AS를 customer라고 함

- 같은 급끼리는 peering 관계라고 함

- peering 관계끼리는 자유롭게 트레픽을 제공받고 provider/customer 관계에서는 계약으로 트레픽을 제공받음

- 이러한 관계가 모여 파란색 처럼 트레픽 전송이 가능하게 됨

- 검은색 점선의 트래픽은 허용이 안됨, 중간에 있는 AS는 저 트래픽을 제공하는데 어떠한 이득도 얻을 수 없기 때문

 

- AS5나 AS4를 거쳐가는게 효율이 더 좋지만 customer를 더 거쳐갈수록 이익이 더 크기 때문에 AS3, AS2를 거쳐감

- intra AS는 최고 효율을 내는 프로토콜을 사용하지만 inter AS는 그저 더 많은 이익을 얻는 경로를 찾아가는 프로토콜(BGP)를 사용함