컴퓨터 네트워크 시간에 Router가 Routing table을 만드는 여러 Protocol 중

Dijkstra Algorithm을 사용하는 OSPF에 대해 배웠습니다.

레포트로 어느 네트워크 상태에서

각 node들의 routing table을 Dijkstra Algorithm을 이용해서 만드는 것이 나왔습니다.

다행히 예전에 해당 알고리즘을 대충 본터라

그것을 보았던 책을 꺼내들고 찬찬히 진행하였습니다.

정확하게는 그 전에 개략적인 방향을 잡은 후 책과 함께 다듬어나간 후

마지막으로 제 힘으로 최종 마무리를 하였습니다.

밑에 해당 C 코드와 보고서를 붙입니다.

001.pdf

/*
* School ID : Secret
* Name : NoSyu
* History
*         2008-10-12
*             I read the paper.
*         2008-10-13
*             I make a pseudocode on the paper,
*             and prepare the program.
*             At this time, I use the Fedora Eclipse.
*             Because I don't know how to compile and debug on VIM.
*             But Eclipse is useful and usable to debug the code.
*         2008-10-18
*             I restart the homework because I prepare the mid-term exam.
*             I make the functions cost vector roughly.
*             I don't have time to write comments and good names.
*         2008-10-19
*             I write the comments.
*             I add the code to find the next hop
*             and the code to print the result.
*         2008-10-20
*             I make the result struct because of optimization.
*             It makes to reduce the variable in Find_ShortestPath_Dijkstra
*             Before to change the code, there are 7 variables in function,
*             but now there are 6 variables include the arguments.
*         2008-10-26
*             I write the comment more.
*             And I rename the function.
*         2008-10-27
*             I make the code about all path
*             I think it's not project,
*             but my friends said he would add the function.
*             So I add the that code.
*         2008-10-28
*             I remove the all path code.
*             But I want to remain this code.
*             So I change the code to comment.
* */

// include the header file
#include <stdio.h>                        // Standard Input Output header file
#include <stdlib.h>                    // Standard library header file
#include <string.h>                    // String function header file

// define the value
#define MAX_NODE 7                        // There are 7 nodes
#define INF_MET 100                        // metrics is infinity.

// declation output Struct
typedef struct
{
    int cost_vector[MAX_NODE];            // the cost vector
    int next_hop_vector[MAX_NODE];        // the next hop address vector
//    char all_path[MAX_NODE][MAX_NODE];    // All path from SRC to DEST, String
} output_struct;

// declation functions
void Find_ShortestPath_Dijkstra(int[][MAX_NODE], output_struct*, int);
int Find_Minimal_Cost_Position(int[], int[]);

/*
* main function
* argument : void
* return : int
*
* It's main function.
* */
int main(void)
{
    // Information about Intra Network
    // Metric information
    // Each row and column means node
    int metric_matrix[MAX_NODE][MAX_NODE] = {
            {0, 7, 2, INF_MET, INF_MET, INF_MET, 10},         // node 1
            {7, 0, INF_MET, 5, 11, INF_MET, INF_MET},         // node 2
            {2, INF_MET, 0, 7, INF_MET, INF_MET, 3},         // node 3
            {INF_MET, 5, 7, 0, INF_MET, 6, 8},                // node 4
            {INF_MET, 11, INF_MET, INF_MET, 0, 4, INF_MET},    // node 5
            {INF_MET, INF_MET, INF_MET, 6, 4, 0, 9},        // node 6
            {7, INF_MET, 3, 8, INF_MET, 9, 0}                // node 7
            };
    // Output next hop vector. Initial the node itself.
    int chosen_node_number = 0;         // start node number
    int for_index;                         // variable using in for loop
    output_struct cost_nexthop_vec; // output struct
    // Print the ID and name
    printf("Computer Network - Implementation of Dijkstra Algorithm.\n"
            "School ID : 2004314081\n"
            "Name : Bak Jin Yeong\n\n");    // print my school ID and name.
    while(1) // infinite loop. user don't want to continue, then stop.
    {
        // Print the message on console and get node number
        printf("Write the node number that you want to know : ");
        scanf("%d", &chosen_node_number);        // get the node number
        // if number is not in from 1 to 7, iterate the get process
        while(chosen_node_number < 1 || 7 < chosen_node_number)
        {
            // Print what is incorrect
            printf("Wrong! You enter the number from 1 to 7\n");
            // Print the message on console and get node number
            printf("Write the node number that you want to know : ");
            // refresh the stdin buffer
            // This code is introduced at http://couple.haruschool.com/tc/22
            while(getchar() != '\n')
                ;
            scanf("%d", &chosen_node_number);    // get the node number
        }
        // refresh the stdin buffer
        // This code is introduced at http://couple.haruschool.com/tc/22
        while(getchar() != '\n')
            ;
        // chosen_node_number is from 1 to 7,
        // but array index is started from 0.
        // So decrese the this variable to approach the array easily.
        chosen_node_number--;                // decrese 1 chosen_node_number
        // Initialize the cost_vector from metric matrix and next hop vector
        for(for_index = 0 ; for_index < MAX_NODE ; for_index++)
        {
            // Copy the intial information to chosen node
            cost_nexthop_vec.cost_vector[for_index]
                        = metric_matrix[chosen_node_number][for_index];
            // Initial next hop is node itself
            cost_nexthop_vec.next_hop_vector[for_index] = for_index + 1;
            // Initial all_path is NULL(0)
            // Because all_path is handled like a string
            // It is easy to know the end of the path.
//            memset(cost_nexthop_vec.all_path[for_index], 0, MAX_NODE);
        }
        // Find the shortestpath using Dijkstra algorithm
        Find_ShortestPath_Dijkstra(metric_matrix,
                &cost_nexthop_vec, chosen_node_number);
        // Print the optimized path
        // Before start chosen_node_number is decreased 1 for indexing.
        // But now it will be printed.
        // So it must be returned(increasing 1).
//        chosen_node_number++;
        // Print the column infomation
        printf("node\tcost\tnexthop\tPath\n");
        // Print the all node information
        for(for_index = 0 ; for_index < MAX_NODE; for_index++)
        {
            // Print the node information
            // If path is null, then only printed SRC and DEST
            // I don't care about SRC and DEST is same.
//            printf("%d\t%d\t%d\t%d%s%d\n",
            printf("%d\t%d\t%d\n",
                for_index+1,                                // node number
                cost_nexthop_vec.cost_vector[for_index],    // the cost
                cost_nexthop_vec.next_hop_vector[for_index]);// the next hop
//                chosen_node_number,                            // SRC
//                cost_nexthop_vec.all_path[for_index],        // Path
//                for_index+1);                                // DEST
        }
        // Continue the process?
        printf("Do you want to see other node result?(y/n) ");
        // if user want to finish the program
        if('n' == getchar())
        {
            break; // go out from while loop
        }
        printf("\n"); // print new line to distinguish new process
    } // end main while loop
    return 0; // End of the program.
} // end main function

/*
* Find_ShortestPath_Dijkstra function
*
* argument
*         metric_matrix : information about Inter network metrics
*         const_nexthop_vec : pointer to output_struct sturct.
*                             In the struct, there are two array,
*                             cost_vector and next_hop_vector
*                             from chosen_node_number
*         chosen_node_number : User choose the node number
* return : void
*
* It find the Shortest Path using Dijkstra algorithm.
* */
void Find_ShortestPath_Dijkstra(int metric_matrix[][MAX_NODE],
        output_struct* cost_nexthop_vec, int chosen_node_number)
{
    // Permanent list.
    // index : node number
    // value 0 : empty, value non-zero : added list, I use 1
    int permanent_list[MAX_NODE] = {0};
    int for_index;                     // variable using in for loop
    int add2perm_i = 0;             // Minimal cost index in tentative list
    // Dijkstra algorithim
    // move chosen node to permanent list
    permanent_list[chosen_node_number] = 1;
    // Find_Minimal_Cost is return the Minimal cost index in tentative list
    // And tentative list is empty, it will return the -1
    // That time process is finish
    while(-1 != (add2perm_i
            = Find_Minimal_Cost_Position
            (cost_nexthop_vec->cost_vector, permanent_list)))
    {
        // Move the one with the shortest path to permanent list
        permanent_list[add2perm_i] = 1;
        // Add each unprocessed neighbor of last moved node
        // If neighbor is in the tentative list with larger cumulative cost,
        // replace it with new one
        for(for_index = 0 ; for_index < MAX_NODE ; for_index++)
        {
            // If permanent_list is zero, that node is in tentative list
            if(!permanent_list[for_index])
            {
                // If adding cost is less than existing cost, change it.
                // next hop is how to go to add2perm_i node.
                // Because new information is from add2perm_i node,
                // there is the next hop about shortest path to that node.
                if(cost_nexthop_vec->cost_vector[add2perm_i]
                    + metric_matrix[add2perm_i][for_index]
                      < cost_nexthop_vec->cost_vector[for_index])
                {
                    // change the cost value
                    cost_nexthop_vec->cost_vector[for_index]
                     = cost_nexthop_vec->cost_vector[add2perm_i]
                       + metric_matrix[add2perm_i][for_index];
                    // change the next hop
                    cost_nexthop_vec->next_hop_vector[for_index]
                     = cost_nexthop_vec->next_hop_vector[add2perm_i];
                    // add the Path
                    // get the path from src to add2perm
//                    strcpy(cost_nexthop_vec->all_path[for_index],
//                            cost_nexthop_vec->all_path[add2perm_i]);
                    // add the add2perm node
                    // all_path likes a string.
                    // So end of the string is calculated strlen
                    // Therefore it is long code.
//                    cost_nexthop_vec->all_path
//                    [for_index]
//                     [strlen(cost_nexthop_vec->all_path[for_index])]
//                      = add2perm_i + '1';
                } // end change the value, if condition
            } // end check the node is in tentative list, if condition
        } // end check the all node, for loop
    } //end move from tentative list to permanent list, while loop
} // end Find_ShortestPath_Dijkstra function

/*
* Find_Minimal_Cost_Postion function
*
* argument
*         cost_vector : this function find the minimal value in it
*         permanent_list : To find the minimal value,
*                         if permanent_list value is 1, pass it.
*                         Because that value is not in tentative list.
* return : the index that is minimal value in cost_vector and tentative list
*
* This function find the minimal value position in cost_vector.
* And check if the value is in tentative list.
* */
int Find_Minimal_Cost_Position(int cost_vector[], int permanent_list[])
{
    int for_index;                     // variable using in for loop
    int minimal_value = INF_MET;     // minimal value
    int minimal_index = -1;         // minimal value position
    // Check all node to find the minimal value position in tentative list
    for(for_index = 0 ; for_index < MAX_NODE; for_index++)
    {
        // if cost is lower than minimal_value
        // and node is in tentative list
        // change the minimal value information
        if(cost_vector[for_index] < minimal_value
                && !permanent_list[for_index])
        {
            // change the minimal value
            minimal_value = cost_vector[for_index];
            // change the minimal value position
            minimal_index = for_index;
        }
    }
    return minimal_index;            // return the minimal value position
} // end Find_Minimal_Cost_Postion

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.