12-2:Network Layer: control plane

Network layer control plane

어떤 역할을하는지

실제 인터넷에서 사용되는 실제구현 체제에대해

 

- introduction

- routing protocols

  - link state

  - distance vector

- intra-ISP routing: OSPF

- routing among ISPs: BGP

 

distance vector알고리즘은 Bellman-Ford(BF) 식에서 나온 것이며

다이나믹 프로그래밍과 비슷하게 생각하면 된다. 결과적으로 보면

Dx(y)라는 것이 있으면 x에서부터 y까지의 최소비용 경로에 대한 코스트를 의미하는 것이고,

이 최소비용을 계산하려면

x와 연결되어 있는 여러가지 이웃들이 있을 것이다.

어떤식으로든 그것들과 연결이 되어, y와 연결되어 있다고 가정해보자

그러면 이를 계산하기 위해서

x에서 y에 이르는 최소비용 경로에 대한 비용을 계산하려면 일단 x의 이웃들, 직접연결된 이웃들을 Cx,v 라고 표시한다.

x->a=1, x->b=2, x->c=3이라고 가정하면 모든 것에 대해서 계산을 해서 그다음에 a에서 y까지 가는 최소 비용 경로, b->y, c->y 까지 가는 경로 코스트를 다 가지고 있다고가정하면, x와 직접 연결된 노드와 다음것까지의 경로는 Dv(y)에 대입해주면 a를 통해서 y를 가는 비용, b를통해서 y로 가는비용, c를 통해서 y가는 비용을 비교해서 가장 작은 값을 더해주면된다.

 

현재 알고있는 정보를 기준으로 가장 비용을 최소로 하는 비용을 선택할 수 있을 것이다.

Cx,v같은 경우는 링크 스테이트 알고리즘에서 봤다 싶이, 내게서 다이렉트 코스트, 직접 연결되어 있는 애들의 코스트를 의미한다.

 

그래서 식에 대입을 하면, 새로운 최소비용을 계산해 낼 수 있다.

 

u에서 시작해서, z까지 도착하는데 걸리는 최소비용을 찾으려고 가정해보자.

우선 u와 직접적으로 연결되어 있는노드들에서부터 z까지 도달하는데 걸리는 최소 코스트를 계산해보면

v에서 시작해서 z까지 도달하는데  최소경로가 5라는 것을 알고 있는 상태, 그리고 

Dx(z), x에서시작해서 z까지 도달하는 걸리는 최소 경로는 3, 

Dw(z) w에서 시작해서 z까지 도달하는데 걸리는 최소 경로는 3,

 

 

이상태에서 u에서 z까지 걸리는 최소 비용을 계산해 내려고 한다고 하자

식에 대입을 하면

 

일단 u에서 v를 거쳐서 z로 가는것을 보면

v에서 z까지 가는 경로(Dv(z))가 5라는 것을알고 있다.

그럼 여기서 u에서 v로 가는 경로 코스트(Cu,v)만 더해주면 된다.

그렇다면 2+5 = 7 이 나온다.

 

마찬가지로 u에서 x를 통해서 z로 가는 건,

Cu,x + Dx(z) = 1 + 3 = 4,

 

Cu,w + Dw(z) = 5 + 3 = 8

 

그러므로 여기서 가장 작은 값을 고르는것이니, 4가되겠다.

u에서 z까지 갈 수있는 최소비용은 4라는 것을 알 수 있다.

그리고 이것을 알 수 있다면, 이 4는 z라우터에 도착하기 위해서는 x로 보내는 것이 최선임을 알 수 있다.

 

포워딩 테이블을 업데이트할 때는 실제 어떤 패킷을 어떤 목적지로 보내기 위해서 어떤 링크로 보내는지만 세팅을 하기 때문에 딱 최소한의 필요한 정보만을 얻어낼 수 있게 된다.

전체 경로를 다 가질 필요 없이 어떤 링크로 패킷을 전달해야하는지를 빠르게 계산해 낼 수 있게 된다.

 

이 디스턴트 백터 알고리즘을 생각해보면, 각 노드가 자신의 현재 디스턴스 벡터 값을 자신의 이웃들한테 보냄.

링크 스테이트 알고리즘은 전체 글로벌한 정보를 가지고 각자 계산을 하는 거였는데, 

각각의 노드는 맨 처음에는 자신만 갖고 있는 일부정보만을 가지고 계산을 한다.

점점 디스턴스 벡터를 자신의 이웃들과 교환을 하기 시작하며 조금씩 업데이트해 나아간다.

이웃으로부터 이스턴스 벡터를 새로 받으면 자신의 디스턴스 벡터를 업데이트해 나아간다.

 

이것을 반복을 하다보면, 처음에는 완전하지 않은 정보였지만, 점점 확산이된다. 

이웃들과 계속 정보교환 하다보면, 결국 네트워크 전체에 걸쳐서 디스턴스 벡터가 조금씩 완전한 형태로 업데이트가 되어간다.

결국에는 시간이 충분히 지나고 중간에 링크 코스트가 변하지 않는 가정하에서는 실제 최소 코스트 값에 수렴을하게된다.

 

1️⃣각 노드가 하는 것은 일단 기다리고, 코스트가 변한다거나, 내 이웃으로부터 디스턴스 벡터 값을 받을 때 까지 기다리고

 

2️⃣새로운 디스턴스 벡터를 받았거나, 자신의 로컬 링크가 바뀌었으면 내 디스턴스 벡터도 변경이 일어났을 것이다.

내 디스턴스 벡터를 받은 정보나 변한 정보를바탕으로 다시계산을 할 것이다.

 

3️⃣그리고변경이 일어났다면 자신의 이웃한테 알려준다

 

이 과정을 계속 반복하게 된다.

이렇게 반복하는 그런 특성을 가지고 있고, 그리고 이것은 비동기적으로 일어난다고 생각하면된다

모든 라우터가 어느시점에 같이 업데이트가 되는 게아니라 각자 따로 돌게 된다. 

서로서로 업데이트 되며 확산되어 가는 개념이라고 생각하면 된다.

 

업데이트가 따로 없으면 알고리즘은 자동으로 멈춘다.

변화가 있을때만 동적으로 변화가 일어난다.

기본적으로 각각의 라우터가 독립적으로 동작하지만 이게 분산적으로 처리가된다.

중양 집중형으로 동작하는게아닌 각 라우터가 부분적인 정보만 가지고 조금씩 서로 교환해 나아가며 점점 완벽한 정보에 가까운 정보를 만들어 나간다고 생각하면 된다.

 

디스턴스 벡터는 자신에게서 부터 나가는 링크에 대한 정보 밖에 없다. 그래서 지금 라우터 a라고 가정하면 디스턴스 벡터는 위 그림과 같이 표시할 수 있다. 그래서 b,d 밖에 정보가 없다.

최초에는 가장 가까운 이웃에 대한 정보밖에 가지고 있지 않다.

 

각각의 노드가 결국에는 자기가 갖고 있는 디스턴스 벡터를 자신의 이웃한테 그 정보를 보내게 된다.

t는 1이 된다. 

내 이웃으로 부터 디스턴스 벡터를 받은 상태가 된다.

 

이것을 바탕으로 각각의 노드들이 새롭게 내 로컬 디스턴스 벡터를 업데이트하는 것이다.

업데이트 된 결과를 다시 내 이웃한테 보낸다.

 

이를 계속 반복한다.

 

이런식으로 계속 반복적으로 동작을 한다.

 

그러면 실제로 계산은 어떻게 이루어 지는지 보자

b를 예시로 들어서 보면,

b이웃은 현재 a,c,e가 있다.

그러면 b는 디스턴스 벡터를 이 이웃들로부터 받을 것이다.

그래서 b의 최초의 디스턴스 벡터 값은 a, c, e로만 갈 수 있으니까 

이 3개의 노드에 대한 링크 코스트만 업데이트해준다.

 

그리고 디스턴스 벡터 정보를 a,c,e로부터 각각 다 받을 것이다.

그래서 이 정보를 가지고 새로운 디스턴스 벡터를 만들어 간다.

 

그러면 b는 이웃들과만 신경쓰면 되기 때문에,

계산을 해보면,

우선 b에서 a까지가는 최소경로를 구하려 한다.

그러면 이를 계산하려면

일단 a로 간다고 가정했을 때

b에서 a로 갔면 a에서 다시 a로 가는 것은 0이므로

코스트는 8+0 = 0이된다.

 

b에서 c를 거쳐서 a로 간다고 하면,

b에서 c로 가는 것은 1이고,

c에서 a로 가는 것은 직접적으로 갈 수 있는 방법이 없기 때문에 무한대가 된다.

 

e를 거쳐서 간다고 하면 1 이고,

e->a는 무한대이다.

 

그렇기 때문에 계산을 하면 두개가 무한대이기 때문에 최솟값은 8이된다.

 

이 값은 완벽한 최소경로라고 할 수 없고, 현재 알고 있는 값들로 계산했을 때 추정되는 값이다.

 

b에서 c로 가는 것을 보면

Cb,a: b에서 a로 가는 것은 8이고

Da(c): a->c = ∞

 

Cb,c = 1

Dc(c)=  0

 

Cb,e = 1

De(c) = ∞

 

= min(∞, 1, ∞) = 1

 

Cb,a = 8

Da(d) = 1

 

Cb,c = 1

Dc(d) = ∞

 

Cb,e = 1

De(d) = 1

 

= min(9, ∞, 2) = 2

 

이런식으로 홉이 1인 애들을 다 검사한다. -> a,c,d,e

결국에 현재 상태에서 도달할 수 없는 애들이 나오고, 업데이트를 해주어야 한다.

지금 이상태에서 알게된 정보를 하나의 홉만큼 떨어져 있는 애들의 정보를 받아

얘네랑 연결되어 있는 애들 정보까지 얻어 올 수 있게된다 -> f,g,h,i

 

디스턴스 벡터를 a,c,e 로 받아서 계산하게 되어 새로운 디스턴스 벡터를 받게 된다.

 원래 것에서 변경이 일어났다.

⬇️

 

 

이번에는 c가 b로부터디스턴스 벡터를 받았다고 가정하자

c는 b한테 갈수밖에 없다.

t=0 , 자기 자신 디스턴스 벡터 업데이트

t(time)가 1 이 되면 1 홉만큼 떨어져 있는 애한테 까지 확산이 될 것이다.

t가 2가 되면 2 c에서 보낸 디스턴스 벡터 값을 가지고 b는업데이트를 했을 것이다.

c에서 보낸 디스턴스 벡터가 a와 e한테 까지 영향을 미치게 될 것이고,

t = 3이 되면 하나더 나아가서 a와 e가 d,f,h한테까지 확산을 할 것이다.

c에서 원래 가지고 있던 디스턴스 벡터가 홉 3개만큼 떨어진 애들한테까지 전파가 된다.

이런식으로 시간이 지날수록 나한테서 멀리 떨어져있는 라우터한테까지 나의 정보가 확산이 된다.

 

 

링크코스트가 변할 수 있다고 했는데 변할때도 디스턴스 벡터알고리즘이 동작을 한다.

코스트가 더 작아졌을 때를 가정해보자, 어쩔 땐 노드가 내 로컬링크의 코스트가 바뀐 것은 금방 알아차릴수 있을 것이다. 그러면 계산을 해서 업데이트를 한다. 디스턴스벡터가 변경이 되면 내 이웃들한테 정보를 알려줄 것이다.

코스트가 줄어든 것은 좋은 뉴스이기 때문에, 빠르게 확산이 된다.

처음에는 링크 코스트가 바뀐 것을 알고 디스턴스 벡터 업데이트하고 이웃에게 전파할 것이고,

t=1인 경우 홉1인 업데이트된 정보를 받을 것이다.

이것을 바탕으로 자신의 테이블을 업데이트할 것이고, 새로운 x에 도달하기위한 비용을 계산할 것이다. 

그리고 다시 전파할 것.

 

업데이트를 다시해서 변경이 일어났다면 이 부분을 다시 주변 이웃에게 알리고, 아니라면 더이상 메시지를 보내지 않고, 디스턴스 벡터값이 안정된 상태로 남아 있을 것이다. 이런 식으로 동작을 한다고 생각하면 된다.

 

나쁜 뉴스는, 코스트가 올라갔다면, 4->60으로

그러면 y가 이 부분을 감지를 할 것이고, 이 부분을 업데이트할 것이다.

가지고 있는 정보를 보면 원래는 y->x로 가기위한 코스트가 4였는데, z를 기준으로 보면 z에서 x로 가는데의 최소비용은 Y를 거쳐서 x로 가는 5였다. 그렇기 때문에 원래 y의 기준에서는 z->x가는 것이 5라고 알려줬기 때문에 5로 업데이트를 할 것이다. 이 5가 의미하는 것은 y->x가 4라는 가정이 있었을 때이다. 이 때 y는 z로 보내는 것이 최소경로라고 판단하고 x로 보내는 패킷을 z한테 포워딩을할 것이고, z같은 경우 x로 보내는 최소 경로가 y를 통해서 보내는 것이라고 알고 있는 상황이다.

그래서 이 패킷을 다시 y에게 보낼 것이다.

즉, y라우터가 판단하기에 현재 y->x 로 바로 가는 것이 60이기 때문에,

z로 갔다가 z->y->x로 가는 것이 더 빠르다는 판단을 할 것이라는 것.

그렇게 되면 y라우터에서 Dy(x) 즉, y에서 x로 가는 코스트를

다시 돌려보내기 위한 y->z= 1

그리고 z->y->x = 5

둘을 더하여 Dy(x)는 6이된다.

 그러면 x로 가야하는 패킷이 y랑 z 라우터 둘 중하나에 패킷이 도착하면 이 패킷이 링크 사이에서 계속 왔다갔다 할 것이다. 영원히 왔다갔다 할 것이다. 이런 것을 왔다갔다 하기위해 TTL이 있다. 그래서 몇번의 홉까지 이 패킷이 살아 있을 것인지 이런 것을 이제 ip프로토콜에서 가지고 있었을 것이다. 그래서 이게 그럴 때 문제를 해결하기 위해 만들어 진것이라고 생각하면 된다. 그리고 이러한 문제를 count-to-infinity problem이라고 한다.

근데 결국에는 서로 라우터끼리 디스턴스 벡터를 주고 받고하다보면 조금씩 개선이 될 것이다. 

 

Dz(x) = Cz,y + Dy(x) 

= 1 + 6 = 7

이런식으로 계속 왔다갔다하게 되면 1씩늘어나게 될 것이다. 

이렇게 되다보면 y를 통해서 x로 가는 것보다 z에서 바로 x로 가는 50이 오히려 더 작은 순간이 올 것이다.

그렇게 되면 그 순간 z가 경로를 바꾸어 y로 보내지 않고 x로 보내야하는 것을 알 때 까지 이 카운트 인피니티가 일어날 것이다.

이렇게 이 나쁜 뉴스는 굉장히 천천히 전달이 되는 것을 알 수 있다.

 

Link State 와 Distance Vector 알고리즘 비교

메시지 복잡성 측면에서는 LS는 n개 라우터가 있을 때 O(n^2) 메시지를 보내야한다.

서로서로 모든 라우터한테 정보를 보내야한다.

 

DV는 전체한테 보낼 필요 없이 내 이웃에게만 전달하면 되긴하지만 시간이 조금 걸린다.

시간이 얼마나 걸릴지는 모른다. 이웃이 얼마나 많은지, 몇 홉에 걸쳐 네트워크가 구성되어 있는지에 따라 차이가 있기 때문에 상황에 따라 많이 달라진다.

 

수렴 속도 또한 LS는 O(n^2)이고, 라우팅이 왔다갔다하는 경우도 발생을 해서 수렴을 하지 못할 수도 있다.

DV같은 경우 경우에 따라 수렴을 할 수 있는 것이 매우 달라질 수 있다. 카운트 투 인피니티 문제 처럼 코스트가 어떻게 설정되냐에 따라 나쁜 뉴스인 경우 시간이 좀 많이 걸릴 수도 있다.

= 라우팅 루프

 

라우터중하나가 이상하게 동작해도 정상적으로 동작하는 것을 보장하는지에 대한 경고성 측명에서 보면 LS같은 경우 하나의 라우터가 코스트를 잘못된정보를 다른라우터들한테 알려줄 수도 있다. 어땟든 각각의 라우터가 자신의 포워딩 테이블만을 업데이트하기 때문에 전체로 확산이 되지는 않는다. 디스턴스 벡터 같은 경우는 한 라우터가 자신의 디스턴스 벡터를 알려줄 때 모든 라우터들한테 낮은 비용으로 도달을 할 수있다는 듯 잘못알려준다면 고장난 라우터한테 모든 요청이 가게될 수 있다. 이렇게 되면 그 라우터는 블랙홀처럼 변해버릴 수 있다. 

결국에는 다른 라우터의 정보를 가지고 나의 것을 점점 업데이트하는 방식이기 때문에 잘못된 정보가 껴있으면 그정보때문에 네트워크전체에 영향을 줄 수도 있다.