[컴퓨터 네트워크] 라우팅 알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)

컴퓨터 네트워크를 수강하던 중에 "라우팅 알고리즘"에 대해서 배우게되었습니다.

라우팅 알고리즘은 네트워크계층의 기능을 제어평면과 데이터평면으로 나누어서 설명할때, 제어평면의 기능입니다.

 

한마디로 종단시스템간의 전체적인 데이터 패킷 전송과정에서 라우터->라우터로 이어지는 경로를 어떻게 가장 효율적으로 구성할까에 대한 알고리즘적 논의입니다.

여기서 효율적이라 함은 cost 즉 비용이 적고, fastest 가장 빠르며 , least congested 혼잡이없는 경로를 말합니다.

또한 라우터의 측면에서는 전송에 필요한 bandwidth나 지연되는 정도를 cost 값이라고 부르기도 합니다.

 

이러한 주제에 있어서 핵심질문은

당연히 두 host간의 패킷 전송 경로에서 가장 least cost path를 발견해내는 것입니다.

이번 포스트에서는 이러한 라우팅 알고리즘 중에 링크스테이트 알고리즘인 다익스트라 알고리즘에 대해서 다뤄보겠습니다. 

 

이 포스트는 설명이나, 정보공유의 의미보다는 저 스스로 학습하고 다시 저만의 언어로 바꾸어 설명하면서 개념을 익히는데에 있기때문에, 정보의 정확성이 떨어질수도 있습니다. 댓글로 남겨주세요 !

 

학습을 위해 다익스트라 알고리즘에 대한 두가지 포스트를 참조했습니다. 

https://www.crocus.co.kr/532?category=209527

다익스트라 알고리즘(Dijkstra Algorithm) 개념

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

본격적으로 다익스트라 알고리즘은 링크스테이트 알고리즘으로 모든 라우터가 해당하는 네트워크 topology 정보

즉 다 시말해서 각각의 라우터에 링크들의 cost 비용에 대해서 알고있어야합니다. (다음 포스트에서 다루게 될

거리벡터 알고리즘과 자주 비교됩니다. )

 

다익스트라 알고리즘은 uwvxyz에 대한 table들을 다 알고있다는 전제하에 최단경로를 갱신해가면서 최종적으로

모든 정점에 방문했을경우 최단경로를 알수있습니다.

 

위의 다익스트라 알고리즘 예시에 대해서 다루자면

 

u를 기준으로 했을때 vwxyz 정점에 대한 가중치 값은 7,3,5,inf,inf 입니다

여기서 최솟값을 가지는 것이 w이므로 w를 방문합니다. ( = 다음 방문 정점은 least cost를 목표로한 알고리즘이기때문에 그 테이블에서 가장 작은 값을 가지는 정점이면서, 방문하지않은 정점으로 방문합니다)

 

u->w를 방문했을때 다시 나머지 vxyz에 대해서, w를 통해서 갔을때 이전의 가중치값보다 효율적인지 비교합니다.

그리고 만약 더 효율적이라면, 그 값으로 테이블을 지정합니다.

 

다시 말해서, uw 테이블에서 v를 예시로 들면  u->w->v = 3+3 =6 이고, u->v =7 입니다

따라서 u에서 v로 가는 최단경로를 기존값 7에서 6으로 업데이트해주는것입니다. 

이같은 과정을 반복하여 모든 정점에 도달했을때

u에서 출발하여 각 정점으로 가는 최단경로를 다 알수있는것입니다.

 

 

위의 예시를 바탕으로 C언어를 이용해 코드를 작성해보았습니다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <stdio.h> #include <stdbool.h> int number = 6; int INF = 10000000;// 무한대를 나타내기 위함   //전체 그래프를 초기화합니다   int a[6][6] = {       {0,7,3,5,10000000,10000000}, // 1을 기준으로 가중치 값     {7,0,3,10000000,4,10000000},     {3,3,0,4,8,10000000},     {5,10000000,4,0,7,9},     {10000000,4,8,7,0,2},     {10000000,10000000,10000000,9,2,0}, };   bool v[6]; int d[6];//거리이면서 최소비용 배열   int getlowIndex() {     int min = INF;     int index = 0;     for (int i = 0; i < number; i++) {         if (d[i] < min && !v[i]) {             min = d[i];             index = i;         }// 최소거리를 가지는 정점을 반환합니다.     }     return index; }   void Dijkstra(int start) {     for (int i = 0; i < number; i++) {         d[i] = a[start][i];     }// d배열에 0부터 시작해서 각 정점으로 도착하는 값들을 넣는다      //알고리즘이 진행되는 과정에서 각 정점으로 도착하는 값들이 재설정되고, 무한대인 값들도 값이 설정될것이다.     v[start] = true;       //이까지 다익스트라 함수에서 알고리즘을 위한 초기설정       for (int i = 0; i < number - 2; i++) {         int current = getlowIndex();         v[current] = true;// 방문했기때문에           for (int j = 0; j < 6; j++) {             if (v[j] != 1) {//방문하지않은 정점에 대해서                 if (d[current] + a[current][j] < d[j]) {                     d[j] = d[current] + a[current][j];                 }             }         }       } }   int main() {     Dijkstra(0);     for (int i = 0; i < number; i++) {         printf("%d ", d[i]);     } } Colored by Color Scripter

cs