PROGRAM 1


/*  filename:  program1.c     author:  anthony f. ortiz  */
/*  link state routing program  */

/*  header files  */
#include 

/*  max node constant  */
#define maxnodes 8
/*  max events constant  */
#define maxevents 1000
/*  initialization constants for routing tables  */
#define infinity 10000
#define tentative 0
#define permanent 1

/*  topologies structure will be a int [][][]  */
/*  not shown here  */

/*  link state packet structure  */
struct linkstatepacket
{
    int address;
    int links [maxnodes];
};

/*  single routing buffer  */
struct buffer
{
    int address;
    int sendflags [maxnodes];
    int ackflags [maxnodes];
};

/*  full routing buffer  */
struct routerbuffer
{
    struct buffer buffers [maxnodes - 1];
};

/*  single node of the routing table  */
struct state
{
    int pred;
    int length;
    int label;
};

/*  full routing table  */
struct routingtable
{
    struct state states [maxnodes];
};

/*  single event  */
struct event
{
    int orgin;
    int source;
    int destination;
};

/*  initialize all router topologies to 0.  */
void initialize_topologies_zero (int topologies [maxnodes][maxnodes][maxnodes])
{
    int i = 0;
    int j = 0;
    int k = 0;
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes; j++)
        {
            for (k = 0; k < maxnodes; k++)
            {
                topologies [i][j][k] = 0;
            }
        }
    }
}

/*  initialize all state link packets to 0.  */
void initialize_linkstatepackets_zero (struct linkstatepacket packets [maxnodes])
{
    int i = 0;
    int j = 0;
    for (i = 0; i < maxnodes; i++)
    {
        packets [i].address = i;
        for (j = 0; j < maxnodes; j++)
        {
            packets [i].links [j] = 0;
        }
    }
}

/*  initialize all router buffers to 0.  */
void initialize_routerbuffers_zero (struct routerbuffer rbuffers [maxnodes])
{
    int i = 0;
    int j = 0;
    int k = 0;
    int address;
    for (i = 0; i < maxnodes; i++)
    {
        address = 0;
        for (j = 0; j < maxnodes - 1; j++)
        {
            if (i == j)
            {
                address = address + 1;
            }
            rbuffers [i].buffers [j].address = address;
            address = address + 1;
            for (k = 0; k < maxnodes; k++)
            {
                rbuffers [i].buffers [j].sendflags [k] = 0;
                rbuffers [i].buffers [j].ackflags [k] = 0;
            }
        }
    }
}

/*  initialize all routing tables to 0.  */
void initialize_routingtables_zero (struct routingtable tables [maxnodes])
{
    int i = 0;
    int j = 0;
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes; j++)
        {
            tables [i].states [j].pred = -1;
            tables [i].states [j].length = infinity;
            tables [i].states [j].label = tentative;
        }
    }
}

/*  initialize event queue to zero.  */
void initialize_eventqueue_zero (struct event events [maxevents])
{
    int i = 0;
    for (i = 0; i < maxevents; i++)
    {
        events [i].orgin = 0;
        events [i].destination = 0;
        events [i].source = 0;
    }
}

/*  initialize all router topologies.  */
void initialize_topolologies (int topologies [maxnodes][maxnodes][maxnodes])
{
    FILE * infile;
    int startnode = 0;
    int endnode = 0;
    int weight = 0;
    infile = fopen ("nodes.dat", "r");
    while (! feof (infile))
    {
        fscanf (infile, "%i %i %i", &startnode, &endnode, &weight);
        topologies [startnode - 1][startnode - 1][endnode - 1] = weight;
    }
    fclose (infile);
}

/*  initialize all link state packets.  */
void initialize_linkstatepackets (int topologies [maxnodes][maxnodes][maxnodes], struct linkstatepacket packets [maxnodes])
{
    int i = 0;
    int j = 0;
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes; j++)
        {
            if (i == packets [i].address && topologies [i][i][j] != 0)
            {
                packets [i].links [j] = topologies [i][i][j];
            }
        }
    }
}

/*  initialize all router buffers.  */
void initialize_routerbuffers (struct routerbuffer rbuffers [maxnodes], struct linkstatepacket packets [maxnodes])
{
    int i = 0;
    int j = 0;
    int k = 0;
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes - 1; j++)
        {
            for (k = 0; k < maxnodes; k++)
            {
                if (i == k)
                {
                    rbuffers [i].buffers [j].ackflags [k] = 1;
                }
                if (rbuffers [i].buffers [j].address != packets [i].address && packets [i].links [k] != 0)
                {
                    rbuffers [i].buffers [j].sendflags [k] = 1;
                }
            }
        }
    }
}

/*  this procedure simulates flooding using routing buffers and an  */
/*  event queue.                                                    */
int do_flooding (int topologies [maxnodes][maxnodes][maxnodes], struct linkstatepacket packets [maxnodes], struct routerbuffer rbuffers [maxnodes], struct event events [maxevents])
{
    int i = 0;
    int j = 0;
    int k = 0;
    int size = 0;
    int orgin = 0;
    int source = 0;
    int destination = 0;
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes - 1; j++)
        {
            for (k = 0; k < maxnodes; k++)
            {
                if (rbuffers [i].buffers [j].sendflags [k] == 1)
                {
                    events [size].orgin = rbuffers [i].buffers [j].address;
                    events [size].source = i;
                    events [size].destination = k;
                    size++;
                }
            }
        }
    }
    printf ("flooding process\n\n");
    for (i = 0; i < size; i++)
    {
        orgin = events [i].orgin;
        source = events [i].source;
        destination = events [i].destination;
        printf ("node %i sending node %i's link state packet to node %i.\n", source + 1, orgin + 1, destination + 1);
        for (j = 0; j < maxnodes; j++)
        {
            topologies [orgin][source][j] = packets [source].links [j];
        }
        printf ("node %i received node %i's link state packet from node %i.\n", destination + 1, orgin + 1, source + 1);
        printf ("node %i sending ack for node %i's link state packet to node %i.\n", destination + 1, orgin + 1, source + 1);
        printf ("node %i received ack for node %i's link state packet from node %i.\n\n", source + 1, orgin + 1, destination + 1);
    }
    printf ("the # of messages is %i\n\n", size);
    return size;
}

/*  calculate routing tables with dijkstra's algorithm.  */
void calculate_routingtables (int topologies [maxnodes][maxnodes][maxnodes], struct routingtable tables [maxnodes], int source, int terminal)
{
    int initial = 0;
    int i = 0;
    int min = 0;
    tables [terminal].states [terminal].pred = -1;
    tables [terminal].states [terminal].length = 0;
    tables [terminal].states [terminal].label = permanent;
    initial = terminal;
    source = -1;  /*  not sure about this variable  */
    do
    {
        for (i = 0; i < maxnodes; i++)
        {
            if (topologies [terminal][initial][i] != 0 && tables [terminal].states [i].label == tentative)
            {
                if (tables [terminal].states [initial].length + topologies [terminal][initial][i] < tables [terminal].states [i].length)
                {
                    tables [terminal].states [i].pred = initial;
                    tables [terminal].states [i].length = tables [terminal].states [initial].length + topologies [terminal][initial][i];
                }
            }
        }
        initial = -1;
        min = infinity;
        for (i = 0; i < maxnodes; i++)
        {
            if (tables [terminal].states [i].label == tentative && tables [terminal].states [i].length < min)
            {
                min = tables [terminal].states [i].length;
                initial = i;
            }
        }
        tables [terminal].states [initial].label = permanent;
    }
    while (initial != source);
}

/*  find optimal path given a start and destination.  */
void find_path (struct routingtable tables [maxnodes])
{
    int start = 0;
    int destination = 0;
    int hop = 0;
    int hop2 = 0;
    int length = 0;
    int pathlength = 0;
    do
    {
        pathlength = 0;
        printf ("enter a source (1-8): ");
        scanf ("%i", &start);
        start = start - 1;
        printf ("\nenter a destination (1-8): ");
        scanf ("%i", &destination);
        destination = destination - 1;
        printf ("\nthe path is ");
        if (start == destination)
        {
            printf ("%i with weight = 0.\n", start + 1);
        }
        else
        {
            hop = start;
            do
            {
                printf ("%i -> ", hop + 1);
                hop = tables [destination].states [hop].pred;
            }
            while (destination != hop);
            printf ("%i with weights ", hop + 1);
            hop = start;
            do
            {
                hop2 = tables [destination].states [hop].pred;
                length = tables [destination].states [hop].length - tables [destination].states [hop2].length;
                printf ("%i + ", length);
                pathlength = pathlength + length;
                hop = tables [destination].states [hop].pred;
            }
            while (destination != hop);
            printf ("0 = %i\n", pathlength);
        }
        printf ("\n");
    }
    while (start != destination);
}

/*  print all the routers topologies.  */
void print_topologies (int topologies [maxnodes][maxnodes][maxnodes])
{
    int i = 0;
    int j = 0;
    int k = 0;
    printf ("router topologies\n\n");
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes; j++)
        {
            for (k = 0; k < maxnodes; k++)
            {
                printf ("%i ", topologies [i][j][k]);
            }
            printf ("\n");
        }
        printf ("\n");
    }
}

/*  print all the link state packets.  */
void print_linkstatepackets (struct linkstatepacket packets [maxnodes])
{
    int i = 0;
    int j = 0;
    printf ("link state packets\n\n");
    for (i = 0; i < maxnodes; i++)
    {
        printf ("%i ", packets [i].address + 1);
        for (j = 0; j < maxnodes; j++)
        {
            printf ("%i ", packets [i].links [j]);
        }
        printf ("\n\n");
    }
}

/*  print all the router buffers.  */
void print_routerbuffers (struct routerbuffer rbuffers [maxnodes])
{
    int i = 0;
    int j = 0;
    int k = 0;
    printf ("router buffers\n\n");
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes - 1; j++)
        {
            printf ("%i ", rbuffers [i].buffers [j].address + 1);
            for (k = 0; k < maxnodes; k++)
            {
                printf ("%i ", rbuffers [i].buffers [j].sendflags [k]);
            }
            for (k = 0; k < maxnodes; k++)
            {
                printf ("%i ", rbuffers [i].buffers [j].ackflags [k]);
            }
            printf ("\n");
        }
        printf ("\n\n");
    }
}

/*  print all the routing tables.  */
void print_routingtables (struct routingtable tables [maxnodes])
{
    int i = 0;
    int j = 0;
    printf ("routing tables\n\n");
    for (i = 0; i < maxnodes; i++)
    {
        for (j = 0; j < maxnodes; j++)

        {
            printf ("%i %i %i\n", j + 1, tables [i].states [j].pred + 1, tables [i].states [j].length);
        }
        printf ("\n");
    }
}

/*  print event queue.  */
void print_eventqueue (struct event events [maxevents], int size)
{
    int i = 0;
    printf ("event queue\n\n");
    for (i = 0; i < size; i++)
    {
        printf ("%i %i %i\n", events [i].orgin + 1, events [i].destination + 1, events [i].source + 1);
    }
}

/*  this is the main function.  it simulates the link state routing     */
/*  algorithm,                                                          */
/*       1)  discover its neighbors and learn their network addresses.  */
/*       2)  measure the delay or cost to each of its neigbors.         */
/*       3)  construct a packet telling all it has just learned.        */
/*       4)  send this packet to all other routers.                     */
/*       5)  compute the shortest path to every other router.           */
void main ()
{
    /*  router's topologies  */
    int topologies [maxnodes][maxnodes][maxnodes];
    /*  router's link state packets  */
    struct linkstatepacket packets [maxnodes];
    /*  router's buffers  */
    struct routerbuffer rbuffers [maxnodes];
    /*  router's routing tables  */
    struct routingtable tables [maxnodes];
    /*  event queue  */
    struct event events [maxevents];
    /*  source used for dijkstra's algorithm  */
    int source = 0;
    /*  destination used for dijkstra's algorithm  */
    int destination = 0;
    /*  events in queue  */
    int size = 0;


    /*  first 3 steps  */
    initialize_topologies_zero (topologies);
    initialize_linkstatepackets_zero (packets);
    initialize_routerbuffers_zero (rbuffers);
    initialize_topolologies (topologies);
    initialize_linkstatepackets (topologies, packets);
    initialize_routerbuffers (rbuffers, packets);
    //print_topologies (topologies);
    //print_linkstatepackets (packets);
    //print_routerbuffers (rbuffers);


    /*  4th step  */
    initialize_eventqueue_zero (events);
    size = do_flooding (topologies, packets, rbuffers, events);
    //print_topologies (topologies);
    //print_eventqueue (events, size);


    /*  5th step  */
    initialize_routingtables_zero (tables);
    for (destination = 0; destination < maxnodes; destination++)
        calculate_routingtables (topologies, tables, source, destination);
    print_routingtables (tables);


    /*  done with link state routing algorithm  */
    /*  test  */
    find_path (tables);
}

/*  filename:  prog1.out  */

flooding process

node 1 sending node 2's link state packet to node 2.
node 2 received node 2's link state packet from node 1.
node 2 sending ack for node 2's link state packet to node 1.
node 1 received ack for node 2's link state packet from node 2.

node 1 sending node 3's link state packet to node 2.
node 2 received node 3's link state packet from node 1.
node 2 sending ack for node 3's link state packet to node 1.
node 1 received ack for node 3's link state packet from node 2.

node 1 sending node 4's link state packet to node 2.
node 2 received node 4's link state packet from node 1.
node 2 sending ack for node 4's link state packet to node 1.
node 1 received ack for node 4's link state packet from node 2.

node 1 sending node 5's link state packet to node 2.
node 2 received node 5's link state packet from node 1.
node 2 sending ack for node 5's link state packet to node 1.
node 1 received ack for node 5's link state packet from node 2.

node 1 sending node 6's link state packet to node 2.
node 2 received node 6's link state packet from node 1.
node 2 sending ack for node 6's link state packet to node 1.
node 1 received ack for node 6's link state packet from node 2.

node 1 sending node 7's link state packet to node 2.
node 2 received node 7's link state packet from node 1.
node 2 sending ack for node 7's link state packet to node 1.
node 1 received ack for node 7's link state packet from node 2.

node 1 sending node 8's link state packet to node 2.
node 2 received node 8's link state packet from node 1.
node 2 sending ack for node 8's link state packet to node 1.
node 1 received ack for node 8's link state packet from node 2.

node 2 sending node 1's link state packet to node 1.
node 1 received node 1's link state packet from node 2.
node 1 sending ack for node 1's link state packet to node 2.
node 2 received ack for node 1's link state packet from node 1.

node 2 sending node 1's link state packet to node 3.
node 3 received node 1's link state packet from node 2.
node 3 sending ack for node 1's link state packet to node 2.
node 2 received ack for node 1's link state packet from node 3.

node 2 sending node 1's link state packet to node 5.
node 5 received node 1's link state packet from node 2.
node 5 sending ack for node 1's link state packet to node 2.
node 2 received ack for node 1's link state packet from node 5.

node 2 sending node 3's link state packet to node 1.
node 1 received node 3's link state packet from node 2.
node 1 sending ack for node 3's link state packet to node 2.
node 2 received ack for node 3's link state packet from node 1.

node 2 sending node 3's link state packet to node 3.
node 3 received node 3's link state packet from node 2.
node 3 sending ack for node 3's link state packet to node 2.
node 2 received ack for node 3's link state packet from node 3.

node 2 sending node 3's link state packet to node 5.
node 5 received node 3's link state packet from node 2.
node 5 sending ack for node 3's link state packet to node 2.
node 2 received ack for node 3's link state packet from node 5.

node 2 sending node 4's link state packet to node 1.
node 1 received node 4's link state packet from node 2.
node 1 sending ack for node 4's link state packet to node 2.
node 2 received ack for node 4's link state packet from node 1.

node 2 sending node 4's link state packet to node 3.
node 3 received node 4's link state packet from node 2.
node 3 sending ack for node 4's link state packet to node 2.
node 2 received ack for node 4's link state packet from node 3.

node 2 sending node 4's link state packet to node 5.
node 5 received node 4's link state packet from node 2.
node 5 sending ack for node 4's link state packet to node 2.
node 2 received ack for node 4's link state packet from node 5.

node 2 sending node 5's link state packet to node 1.
node 1 received node 5's link state packet from node 2.
node 1 sending ack for node 5's link state packet to node 2.
node 2 received ack for node 5's link state packet from node 1.

node 2 sending node 5's link state packet to node 3.
node 3 received node 5's link state packet from node 2.
node 3 sending ack for node 5's link state packet to node 2.
node 2 received ack for node 5's link state packet from node 3.

node 2 sending node 5's link state packet to node 5.
node 5 received node 5's link state packet from node 2.
node 5 sending ack for node 5's link state packet to node 2.
node 2 received ack for node 5's link state packet from node 5.

node 2 sending node 6's link state packet to node 1.
node 1 received node 6's link state packet from node 2.
node 1 sending ack for node 6's link state packet to node 2.
node 2 received ack for node 6's link state packet from node 1.

node 2 sending node 6's link state packet to node 3.
node 3 received node 6's link state packet from node 2.
node 3 sending ack for node 6's link state packet to node 2.
node 2 received ack for node 6's link state packet from node 3.

node 2 sending node 6's link state packet to node 5.
node 5 received node 6's link state packet from node 2.
node 5 sending ack for node 6's link state packet to node 2.
node 2 received ack for node 6's link state packet from node 5.

node 2 sending node 7's link state packet to node 1.
node 1 received node 7's link state packet from node 2.
node 1 sending ack for node 7's link state packet to node 2.
node 2 received ack for node 7's link state packet from node 1.

node 2 sending node 7's link state packet to node 3.
node 3 received node 7's link state packet from node 2.
node 3 sending ack for node 7's link state packet to node 2.
node 2 received ack for node 7's link state packet from node 3.

node 2 sending node 7's link state packet to node 5.
node 5 received node 7's link state packet from node 2.
node 5 sending ack for node 7's link state packet to node 2.
node 2 received ack for node 7's link state packet from node 5.

node 2 sending node 8's link state packet to node 1.
node 1 received node 8's link state packet from node 2.
node 1 sending ack for node 8's link state packet to node 2.
node 2 received ack for node 8's link state packet from node 1.

node 2 sending node 8's link state packet to node 3.
node 3 received node 8's link state packet from node 2.
node 3 sending ack for node 8's link state packet to node 2.
node 2 received ack for node 8's link state packet from node 3.

node 2 sending node 8's link state packet to node 5.
node 5 received node 8's link state packet from node 2.
node 5 sending ack for node 8's link state packet to node 2.
node 2 received ack for node 8's link state packet from node 5.

node 3 sending node 1's link state packet to node 2.
node 2 received node 1's link state packet from node 3.
node 2 sending ack for node 1's link state packet to node 3.
node 3 received ack for node 1's link state packet from node 2.

node 3 sending node 1's link state packet to node 4.
node 4 received node 1's link state packet from node 3.
node 4 sending ack for node 1's link state packet to node 3.
node 3 received ack for node 1's link state packet from node 4.

node 3 sending node 2's link state packet to node 2.
node 2 received node 2's link state packet from node 3.
node 2 sending ack for node 2's link state packet to node 3.
node 3 received ack for node 2's link state packet from node 2.

node 3 sending node 2's link state packet to node 4.
node 4 received node 2's link state packet from node 3.
node 4 sending ack for node 2's link state packet to node 3.
node 3 received ack for node 2's link state packet from node 4.

node 3 sending node 4's link state packet to node 2.
node 2 received node 4's link state packet from node 3.
node 2 sending ack for node 4's link state packet to node 3.
node 3 received ack for node 4's link state packet from node 2.

node 3 sending node 4's link state packet to node 4.
node 4 received node 4's link state packet from node 3.
node 4 sending ack for node 4's link state packet to node 3.
node 3 received ack for node 4's link state packet from node 4.

node 3 sending node 5's link state packet to node 2.
node 2 received node 5's link state packet from node 3.
node 2 sending ack for node 5's link state packet to node 3.
node 3 received ack for node 5's link state packet from node 2.

node 3 sending node 5's link state packet to node 4.
node 4 received node 5's link state packet from node 3.
node 4 sending ack for node 5's link state packet to node 3.
node 3 received ack for node 5's link state packet from node 4.

node 3 sending node 6's link state packet to node 2.
node 2 received node 6's link state packet from node 3.
node 2 sending ack for node 6's link state packet to node 3.
node 3 received ack for node 6's link state packet from node 2.

node 3 sending node 6's link state packet to node 4.
node 4 received node 6's link state packet from node 3.
node 4 sending ack for node 6's link state packet to node 3.
node 3 received ack for node 6's link state packet from node 4.

node 3 sending node 7's link state packet to node 2.
node 2 received node 7's link state packet from node 3.
node 2 sending ack for node 7's link state packet to node 3.
node 3 received ack for node 7's link state packet from node 2.

node 3 sending node 7's link state packet to node 4.
node 4 received node 7's link state packet from node 3.
node 4 sending ack for node 7's link state packet to node 3.
node 3 received ack for node 7's link state packet from node 4.

node 3 sending node 8's link state packet to node 2.
node 2 received node 8's link state packet from node 3.
node 2 sending ack for node 8's link state packet to node 3.
node 3 received ack for node 8's link state packet from node 2.

node 3 sending node 8's link state packet to node 4.
node 4 received node 8's link state packet from node 3.
node 4 sending ack for node 8's link state packet to node 3.
node 3 received ack for node 8's link state packet from node 4.

node 4 sending node 1's link state packet to node 3.
node 3 received node 1's link state packet from node 4.
node 3 sending ack for node 1's link state packet to node 4.
node 4 received ack for node 1's link state packet from node 3.

node 4 sending node 1's link state packet to node 5.
node 5 received node 1's link state packet from node 4.
node 5 sending ack for node 1's link state packet to node 4.
node 4 received ack for node 1's link state packet from node 5.

node 4 sending node 2's link state packet to node 3.
node 3 received node 2's link state packet from node 4.
node 3 sending ack for node 2's link state packet to node 4.
node 4 received ack for node 2's link state packet from node 3.

node 4 sending node 2's link state packet to node 5.
node 5 received node 2's link state packet from node 4.
node 5 sending ack for node 2's link state packet to node 4.
node 4 received ack for node 2's link state packet from node 5.

node 4 sending node 3's link state packet to node 3.
node 3 received node 3's link state packet from node 4.
node 3 sending ack for node 3's link state packet to node 4.
node 4 received ack for node 3's link state packet from node 3.

node 4 sending node 3's link state packet to node 5.
node 5 received node 3's link state packet from node 4.
node 5 sending ack for node 3's link state packet to node 4.
node 4 received ack for node 3's link state packet from node 5.

node 4 sending node 5's link state packet to node 3.
node 3 received node 5's link state packet from node 4.
node 3 sending ack for node 5's link state packet to node 4.
node 4 received ack for node 5's link state packet from node 3.

node 4 sending node 5's link state packet to node 5.
node 5 received node 5's link state packet from node 4.
node 5 sending ack for node 5's link state packet to node 4.
node 4 received ack for node 5's link state packet from node 5.

node 4 sending node 6's link state packet to node 3.
node 3 received node 6's link state packet from node 4.
node 3 sending ack for node 6's link state packet to node 4.
node 4 received ack for node 6's link state packet from node 3.

node 4 sending node 6's link state packet to node 5.
node 5 received node 6's link state packet from node 4.
node 5 sending ack for node 6's link state packet to node 4.
node 4 received ack for node 6's link state packet from node 5.

node 4 sending node 7's link state packet to node 3.
node 3 received node 7's link state packet from node 4.
node 3 sending ack for node 7's link state packet to node 4.
node 4 received ack for node 7's link state packet from node 3.

node 4 sending node 7's link state packet to node 5.
node 5 received node 7's link state packet from node 4.
node 5 sending ack for node 7's link state packet to node 4.
node 4 received ack for node 7's link state packet from node 5.

node 4 sending node 8's link state packet to node 3.
node 3 received node 8's link state packet from node 4.
node 3 sending ack for node 8's link state packet to node 4.
node 4 received ack for node 8's link state packet from node 3.

node 4 sending node 8's link state packet to node 5.
node 5 received node 8's link state packet from node 4.
node 5 sending ack for node 8's link state packet to node 4.
node 4 received ack for node 8's link state packet from node 5.

node 5 sending node 1's link state packet to node 2.
node 2 received node 1's link state packet from node 5.
node 2 sending ack for node 1's link state packet to node 5.
node 5 received ack for node 1's link state packet from node 2.

node 5 sending node 1's link state packet to node 4.
node 4 received node 1's link state packet from node 5.
node 4 sending ack for node 1's link state packet to node 5.
node 5 received ack for node 1's link state packet from node 4.

node 5 sending node 1's link state packet to node 6.
node 6 received node 1's link state packet from node 5.
node 6 sending ack for node 1's link state packet to node 5.
node 5 received ack for node 1's link state packet from node 6.

node 5 sending node 1's link state packet to node 8.
node 8 received node 1's link state packet from node 5.
node 8 sending ack for node 1's link state packet to node 5.
node 5 received ack for node 1's link state packet from node 8.

node 5 sending node 2's link state packet to node 2.
node 2 received node 2's link state packet from node 5.
node 2 sending ack for node 2's link state packet to node 5.
node 5 received ack for node 2's link state packet from node 2.

node 5 sending node 2's link state packet to node 4.
node 4 received node 2's link state packet from node 5.
node 4 sending ack for node 2's link state packet to node 5.
node 5 received ack for node 2's link state packet from node 4.

node 5 sending node 2's link state packet to node 6.
node 6 received node 2's link state packet from node 5.
node 6 sending ack for node 2's link state packet to node 5.
node 5 received ack for node 2's link state packet from node 6.

node 5 sending node 2's link state packet to node 8.
node 8 received node 2's link state packet from node 5.
node 8 sending ack for node 2's link state packet to node 5.
node 5 received ack for node 2's link state packet from node 8.

node 5 sending node 3's link state packet to node 2.
node 2 received node 3's link state packet from node 5.
node 2 sending ack for node 3's link state packet to node 5.
node 5 received ack for node 3's link state packet from node 2.

node 5 sending node 3's link state packet to node 4.
node 4 received node 3's link state packet from node 5.
node 4 sending ack for node 3's link state packet to node 5.
node 5 received ack for node 3's link state packet from node 4.

node 5 sending node 3's link state packet to node 6.
node 6 received node 3's link state packet from node 5.
node 6 sending ack for node 3's link state packet to node 5.
node 5 received ack for node 3's link state packet from node 6.

node 5 sending node 3's link state packet to node 8.
node 8 received node 3's link state packet from node 5.
node 8 sending ack for node 3's link state packet to node 5.
node 5 received ack for node 3's link state packet from node 8.

node 5 sending node 4's link state packet to node 2.
node 2 received node 4's link state packet from node 5.
node 2 sending ack for node 4's link state packet to node 5.
node 5 received ack for node 4's link state packet from node 2.

node 5 sending node 4's link state packet to node 4.
node 4 received node 4's link state packet from node 5.
node 4 sending ack for node 4's link state packet to node 5.
node 5 received ack for node 4's link state packet from node 4.

node 5 sending node 4's link state packet to node 6.
node 6 received node 4's link state packet from node 5.
node 6 sending ack for node 4's link state packet to node 5.
node 5 received ack for node 4's link state packet from node 6.

node 5 sending node 4's link state packet to node 8.
node 8 received node 4's link state packet from node 5.
node 8 sending ack for node 4's link state packet to node 5.
node 5 received ack for node 4's link state packet from node 8.

node 5 sending node 6's link state packet to node 2.
node 2 received node 6's link state packet from node 5.
node 2 sending ack for node 6's link state packet to node 5.
node 5 received ack for node 6's link state packet from node 2.

node 5 sending node 6's link state packet to node 4.
node 4 received node 6's link state packet from node 5.
node 4 sending ack for node 6's link state packet to node 5.
node 5 received ack for node 6's link state packet from node 4.

node 5 sending node 6's link state packet to node 6.
node 6 received node 6's link state packet from node 5.
node 6 sending ack for node 6's link state packet to node 5.
node 5 received ack for node 6's link state packet from node 6.

node 5 sending node 6's link state packet to node 8.
node 8 received node 6's link state packet from node 5.
node 8 sending ack for node 6's link state packet to node 5.
node 5 received ack for node 6's link state packet from node 8.

node 5 sending node 7's link state packet to node 2.
node 2 received node 7's link state packet from node 5.
node 2 sending ack for node 7's link state packet to node 5.
node 5 received ack for node 7's link state packet from node 2.

node 5 sending node 7's link state packet to node 4.
node 4 received node 7's link state packet from node 5.
node 4 sending ack for node 7's link state packet to node 5.
node 5 received ack for node 7's link state packet from node 4.

node 5 sending node 7's link state packet to node 6.
node 6 received node 7's link state packet from node 5.
node 6 sending ack for node 7's link state packet to node 5.
node 5 received ack for node 7's link state packet from node 6.

node 5 sending node 7's link state packet to node 8.
node 8 received node 7's link state packet from node 5.
node 8 sending ack for node 7's link state packet to node 5.
node 5 received ack for node 7's link state packet from node 8.

node 5 sending node 8's link state packet to node 2.
node 2 received node 8's link state packet from node 5.
node 2 sending ack for node 8's link state packet to node 5.
node 5 received ack for node 8's link state packet from node 2.

node 5 sending node 8's link state packet to node 4.
node 4 received node 8's link state packet from node 5.
node 4 sending ack for node 8's link state packet to node 5.
node 5 received ack for node 8's link state packet from node 4.

node 5 sending node 8's link state packet to node 6.
node 6 received node 8's link state packet from node 5.
node 6 sending ack for node 8's link state packet to node 5.
node 5 received ack for node 8's link state packet from node 6.

node 5 sending node 8's link state packet to node 8.
node 8 received node 8's link state packet from node 5.
node 8 sending ack for node 8's link state packet to node 5.
node 5 received ack for node 8's link state packet from node 8.

node 6 sending node 1's link state packet to node 5.
node 5 received node 1's link state packet from node 6.
node 5 sending ack for node 1's link state packet to node 6.
node 6 received ack for node 1's link state packet from node 5.

node 6 sending node 1's link state packet to node 7.
node 7 received node 1's link state packet from node 6.
node 7 sending ack for node 1's link state packet to node 6.
node 6 received ack for node 1's link state packet from node 7.

node 6 sending node 2's link state packet to node 5.
node 5 received node 2's link state packet from node 6.
node 5 sending ack for node 2's link state packet to node 6.
node 6 received ack for node 2's link state packet from node 5.

node 6 sending node 2's link state packet to node 7.
node 7 received node 2's link state packet from node 6.
node 7 sending ack for node 2's link state packet to node 6.
node 6 received ack for node 2's link state packet from node 7.

node 6 sending node 3's link state packet to node 5.
node 5 received node 3's link state packet from node 6.
node 5 sending ack for node 3's link state packet to node 6.
node 6 received ack for node 3's link state packet from node 5.

node 6 sending node 3's link state packet to node 7.
node 7 received node 3's link state packet from node 6.
node 7 sending ack for node 3's link state packet to node 6.
node 6 received ack for node 3's link state packet from node 7.

node 6 sending node 4's link state packet to node 5.
node 5 received node 4's link state packet from node 6.
node 5 sending ack for node 4's link state packet to node 6.
node 6 received ack for node 4's link state packet from node 5.

node 6 sending node 4's link state packet to node 7.
node 7 received node 4's link state packet from node 6.
node 7 sending ack for node 4's link state packet to node 6.
node 6 received ack for node 4's link state packet from node 7.

node 6 sending node 5's link state packet to node 5.
node 5 received node 5's link state packet from node 6.
node 5 sending ack for node 5's link state packet to node 6.
node 6 received ack for node 5's link state packet from node 5.

node 6 sending node 5's link state packet to node 7.
node 7 received node 5's link state packet from node 6.
node 7 sending ack for node 5's link state packet to node 6.
node 6 received ack for node 5's link state packet from node 7.

node 6 sending node 7's link state packet to node 5.
node 5 received node 7's link state packet from node 6.
node 5 sending ack for node 7's link state packet to node 6.
node 6 received ack for node 7's link state packet from node 5.

node 6 sending node 7's link state packet to node 7.
node 7 received node 7's link state packet from node 6.
node 7 sending ack for node 7's link state packet to node 6.
node 6 received ack for node 7's link state packet from node 7.

node 6 sending node 8's link state packet to node 5.
node 5 received node 8's link state packet from node 6.
node 5 sending ack for node 8's link state packet to node 6.
node 6 received ack for node 8's link state packet from node 5.

node 6 sending node 8's link state packet to node 7.
node 7 received node 8's link state packet from node 6.
node 7 sending ack for node 8's link state packet to node 6.
node 6 received ack for node 8's link state packet from node 7.

node 7 sending node 1's link state packet to node 6.
node 6 received node 1's link state packet from node 7.
node 6 sending ack for node 1's link state packet to node 7.
node 7 received ack for node 1's link state packet from node 6.

node 7 sending node 1's link state packet to node 8.
node 8 received node 1's link state packet from node 7.
node 8 sending ack for node 1's link state packet to node 7.
node 7 received ack for node 1's link state packet from node 8.

node 7 sending node 2's link state packet to node 6.
node 6 received node 2's link state packet from node 7.
node 6 sending ack for node 2's link state packet to node 7.
node 7 received ack for node 2's link state packet from node 6.

node 7 sending node 2's link state packet to node 8.
node 8 received node 2's link state packet from node 7.
node 8 sending ack for node 2's link state packet to node 7.
node 7 received ack for node 2's link state packet from node 8.

node 7 sending node 3's link state packet to node 6.
node 6 received node 3's link state packet from node 7.
node 6 sending ack for node 3's link state packet to node 7.
node 7 received ack for node 3's link state packet from node 6.

node 7 sending node 3's link state packet to node 8.
node 8 received node 3's link state packet from node 7.
node 8 sending ack for node 3's link state packet to node 7.
node 7 received ack for node 3's link state packet from node 8.

node 7 sending node 4's link state packet to node 6.
node 6 received node 4's link state packet from node 7.
node 6 sending ack for node 4's link state packet to node 7.
node 7 received ack for node 4's link state packet from node 6.

node 7 sending node 4's link state packet to node 8.
node 8 received node 4's link state packet from node 7.
node 8 sending ack for node 4's link state packet to node 7.
node 7 received ack for node 4's link state packet from node 8.

node 7 sending node 5's link state packet to node 6.
node 6 received node 5's link state packet from node 7.
node 6 sending ack for node 5's link state packet to node 7.
node 7 received ack for node 5's link state packet from node 6.

node 7 sending node 5's link state packet to node 8.
node 8 received node 5's link state packet from node 7.
node 8 sending ack for node 5's link state packet to node 7.
node 7 received ack for node 5's link state packet from node 8.

node 7 sending node 6's link state packet to node 6.
node 6 received node 6's link state packet from node 7.
node 6 sending ack for node 6's link state packet to node 7.
node 7 received ack for node 6's link state packet from node 6.

node 7 sending node 6's link state packet to node 8.
node 8 received node 6's link state packet from node 7.
node 8 sending ack for node 6's link state packet to node 7.
node 7 received ack for node 6's link state packet from node 8.

node 7 sending node 8's link state packet to node 6.
node 6 received node 8's link state packet from node 7.
node 6 sending ack for node 8's link state packet to node 7.
node 7 received ack for node 8's link state packet from node 6.

node 7 sending node 8's link state packet to node 8.
node 8 received node 8's link state packet from node 7.
node 8 sending ack for node 8's link state packet to node 7.
node 7 received ack for node 8's link state packet from node 8.

node 8 sending node 1's link state packet to node 5.
node 5 received node 1's link state packet from node 8.
node 5 sending ack for node 1's link state packet to node 8.
node 8 received ack for node 1's link state packet from node 5.

node 8 sending node 1's link state packet to node 7.
node 7 received node 1's link state packet from node 8.
node 7 sending ack for node 1's link state packet to node 8.
node 8 received ack for node 1's link state packet from node 7.

node 8 sending node 2's link state packet to node 5.
node 5 received node 2's link state packet from node 8.
node 5 sending ack for node 2's link state packet to node 8.
node 8 received ack for node 2's link state packet from node 5.

node 8 sending node 2's link state packet to node 7.
node 7 received node 2's link state packet from node 8.
node 7 sending ack for node 2's link state packet to node 8.
node 8 received ack for node 2's link state packet from node 7.

node 8 sending node 3's link state packet to node 5.
node 5 received node 3's link state packet from node 8.
node 5 sending ack for node 3's link state packet to node 8.
node 8 received ack for node 3's link state packet from node 5.

node 8 sending node 3's link state packet to node 7.
node 7 received node 3's link state packet from node 8.
node 7 sending ack for node 3's link state packet to node 8.
node 8 received ack for node 3's link state packet from node 7.

node 8 sending node 4's link state packet to node 5.
node 5 received node 4's link state packet from node 8.
node 5 sending ack for node 4's link state packet to node 8.
node 8 received ack for node 4's link state packet from node 5.

node 8 sending node 4's link state packet to node 7.
node 7 received node 4's link state packet from node 8.
node 7 sending ack for node 4's link state packet to node 8.
node 8 received ack for node 4's link state packet from node 7.

node 8 sending node 5's link state packet to node 5.
node 5 received node 5's link state packet from node 8.
node 5 sending ack for node 5's link state packet to node 8.
node 8 received ack for node 5's link state packet from node 5.

node 8 sending node 5's link state packet to node 7.
node 7 received node 5's link state packet from node 8.
node 7 sending ack for node 5's link state packet to node 8.
node 8 received ack for node 5's link state packet from node 7.

node 8 sending node 6's link state packet to node 5.
node 5 received node 6's link state packet from node 8.
node 5 sending ack for node 6's link state packet to node 8.
node 8 received ack for node 6's link state packet from node 5.

node 8 sending node 6's link state packet to node 7.
node 7 received node 6's link state packet from node 8.
node 7 sending ack for node 6's link state packet to node 8.
node 8 received ack for node 6's link state packet from node 7.

node 8 sending node 7's link state packet to node 5.
node 5 received node 7's link state packet from node 8.
node 5 sending ack for node 7's link state packet to node 8.
node 8 received ack for node 7's link state packet from node 5.

node 8 sending node 7's link state packet to node 7.
node 7 received node 7's link state packet from node 8.
node 7 sending ack for node 7's link state packet to node 8.
node 8 received ack for node 7's link state packet from node 7.

the # of messages is 126

routing tables

1 0 0
2 1 2
3 2 6
4 3 8
5 2 8
6 5 11
7 8 13
8 5 12


1 2 2
2 0 0
3 2 4
4 3 6
5 2 6
6 5 9
7 8 11
8 5 10


1 2 6
2 3 4
3 0 0
4 3 2
5 4 3
6 5 6
7 8 8
8 5 7


1 2 8
2 3 6
3 4 2
4 0 0
5 4 1
6 5 4
7 8 6
8 5 5


1 2 8
2 5 6
3 4 3
4 5 1
5 0 0
6 5 3
7 8 5
8 5 4


1 2 11
2 5 9
3 4 6
4 5 4
5 6 3
6 0 0
7 6 3
8 7 4


1 2 13
2 5 11
3 4 8
4 5 6
5 8 5
6 7 3
7 0 0
8 7 1


1 2 12
2 5 10
3 4 7
4 5 5
5 8 4
6 7 4
7 8 1
8 0 0

enter a source (1-8): 7
enter a destination (1-8): 3
the path is 7 -> 8 -> 5 -> 4 -> 3 with weights 1 + 4 + 1 + 2 + 0 = 8

enter a source (1-8): 1
enter a destination (1-8): 1
the path is 1 with weight = 0.




BACK TO CS4590 PAGE.