이석복 네트워크 (13)Distance vector

===

http://ocw.hanyang.ac.kr/?course=8457

 

===

link state든

distance vector든 라우터들이 연결된 네트워크 상황에서 모든 잠재적인 목적지를 향한 최단거리를 구한 것

그리고 둘 다 하나의 네트워크에 국한돼서 그 내부에 라우팅이 이뤄질 때 사용되는 알고리즘이다. 인터넷 전체로 브로드캐스팅은 말이 안되니까

내 소유 라우터들의 알고리즘을 정하는데 그게 저 둘중 하나로 선택하는 것

 

그럼 자치권 밖에선 어떻게 해? 그게 더 중요할 것 같은데 그거 다음시간에

 

===

c(x,v)는 알고

dv(y)는 recursive하게 구한다 

 

===

방금한거랑 똑같은 슬라이드

내가 u, z까지 최소경로?

셋중에 하나다 v, w, x(이웃) 중에 하나다.

 

===

u에게 v가 자기자신이 알고있는 distance의 array를 넘겨준다

array를 vector라고도 한다

넘겨주는 정보가 distance의 array이므로 distance vector 알고리즘이라 불린다. link state는 link정보를 넘겨줬었으니까

 

===

각 노드는 자기가 알고 있는 distance vector를 직접연결된 이웃한테 넘겨주고 

노드는 받으면 계산할 수 있다

 

모든 노드가(나는 X라고 치면)

각각 노드로 가는 distance를 내부적으로 알고 있겠지. 처음에 모르는 상태면 무한대일거고

이게 계속 업데이트 되는 과정인 것

이웃으로부터 이웃의 distance vector를 받으면

이게 계산이 되고 기존에서 업데이트 되면 내 distance vector가 바뀌었으므로 이 정보를 다시 이웃들한테 전달

이웃이 또 계산. 업데이트 되면 또 전달. 반복

 

또는 자기랑 직접적으로 연결된 링크의 cost가 변경된 경우 값들 계산해보고 변경되면 전달

 

계속 반복하다보면 어느순간 업데이트 되지않고 stablize. 이게 라우팅이 다 계산된 상황

 

===

는

 

라우터 X안에 들어 있는 테이블

src&dest distance

남의건 모르니까 ?다

 

X입장에서 0 4 50 이 X가 가진 distance vector다. array잖아

dx(Y) = 4인 것

 

===

마찬가지로

이렇게 되는데, 저 빨간색이 각자의 distance vector고 이걸 이웃한테 넘긴다

 

===

위에것이 시간 0 이었고

넘기고 시간 1

다른데서 온걸로 채우니까 완성됐다

그럼 이제 x는 이웃한테 받았으니까 내 distance vector를 재계산 해봐야돼 

저 둘 중 하나다

리포트 받은걸로 계산해보면

그대로 4다

이거는

5로 업데이트

이걸 다시 이웃한테 전달!

 

===

Y, Z도 리포트받은걸로 재계산(X 재계산전에 보낸 것)

Y는 바뀌는거 없고

Z는

5로 업데이트

 

이 라운드가 끝나면 자기 distance vector를 이웃한테 보낸다 Y는 안 변했으니 안 보낸다

 

===

보내면

셋다 새로운걸 받았으니 재계산 해야한다

 

재계산할 때

이렇게 한다 Y에서 X로 가는데, Y의 이웃은 X와 Z니까 

▽저거 5가

여기서 Y에서 X로 가는걸 따지는데 이웃은 X, Z니까 거기까지 간다음에 최단거리를 따지는 것이고

Z이웃으로 가는건 Y -> Z -> Y -> X 이렇게 가네, 1+5 = 6인거네

4 vs 6으로 4가 이겼다

 

===

이러면 distance vector가 안변해서 안정화된 상태가 됐다

 

===

좌냐 우냐 중에 선택하는 것이다

 

===

안정화된 상태에서 link cost가 바뀌면? 링크와 이웃한 애들은 자기자신의 distance vector를 재계산해봐야해

-> 변화가 있으면? -> 넘겨줘야해

이러면 Z는 link cost바뀐걸 모르니까 일단 할게 없고 Y의 C(y, x)가 1로 바뀌는데, 이거 이웃에게 넘겨줘야

 

link cost가 좋게 바뀌었을 땐 안정화가 금방 끝나는데

이렇게 되면

C(y, x) = 50

이렇게 바뀐다! 바뀌니까 전송(forwarding)

6으로 바뀐다

 

큰 그림으로 보려면 50으로 바뀌어야하는데, 아직 6이야 왜?

Y의 안에 Z가 준 벡터엔 아직 업데이트가 반영이 안됐어, Z가 자기가 Z에서 X로 가는 5인 길 알고 있대서 그거 아직 믿고 있어. 그래서 6

이 6을 받은 Z는 7을 주고

그거 받은 Y는 8, Z는 9 ... 50될때까지

 

기분 좋은 소식은(link cost가 저렴해지는)건 바로 수렴이 됐는데

cost가 늘어나는 소식은 좀 오래걸린다

 

distance vector에서만 특수하게 생기는 count-to-infinity문제라고 부른다. 현상임. 큰그림을 가지지 못한채 이웃에서 넘어오는 부분적인 걸 갖고 계산을 하다보니 이래됨. 상대방이 보내는 distance값 자체가 자기자신을 의존하는 값인 경우도 blind한 채로 그냥 계산을 하니까. 나는 상대방을 믿고 상대방은 나를 믿고.. count는 계속 올라가고

Y->Z->Y->Z 라는 길을 5라고 Z가 Y한테 말하면 Y는 자기를 다시 통해서 가는 길인지도 모르고 뭐 다른 길이 있는 줄로 이해한다. 그래서 사실 Z는 Y한테 Y통해서 가는 길은 무한대라고 알려줘야해. Y는 이 정보가 필요하지 않아. 넘겨주면 안돼 그 정보로 착각해 그래야 count-to-infinity문제가 발생하지 않는다.

y한테만 이렇게

그럼 바로 50이 되고 수렴 끝

 

60이되면

왼 60 오 무한대, 60이 이긴다 (Z가 Y한텐 무한대로 줬으니까)

60으로 바뀌고 이게 넘어가

Z에서 Z에서 X로 가는게 61 vs 50이 돼서 Y의존하지 않는게 더 짧아져서 50을 넘김

그럼 Y에서 60vs51이 되는거지 그래서 51이 된다

 

라운드가 한번만 더 생겨

 

===

설명 안한 그림