home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / mrdebug.tar.Z / mrdebug.tar / dist_vect.c < prev    next >
C/C++ Source or Header  |  1993-10-25  |  29KB  |  892 lines
  1. /*****************************************************************
  2.  
  3.   PROGRAM: Network Distance Vector Routing Computer
  4.  
  5.   DESCRIPTION:
  6.          This program assumes knowledge of the entire
  7.      network before starting.  It uses Dijkstra's
  8.      algorithm to determine the shortest path tree
  9.      from the given source and fills in the appropriate
  10.      distance vector entries for that source in the
  11.      sites' distance vector tables.
  12.  
  13.  METHOD:
  14.          Dijkstra's algorithm.  The reverse direction edge weights
  15.      are used to determine the weight between any two sites.
  16.      The algorithm uses the relaxation method it starts with
  17.      all nodes being infinite distance except the source which
  18.      is zero distance.  The  graph is assumed to be stored as
  19.      an adjacency list.  The program gradually investigates out
  20.      from the source always expanding the lowest cost node next.
  21.      Once a node has been investigated, it need not be looked at
  22.      again.
  23.  
  24.   PROGRAMMER:        Deb Agarwal        6/1993
  25.  
  26. *********************************************************************/
  27. #include    <stdio.h>
  28. #include    <string.h>
  29.  
  30. #include       "types.h"
  31. #include       "mrhash.h"
  32. #include       "data_struct_proto.h"
  33. #include       "dist_vect_proto.h"
  34.  
  35. /********* EXTERNAL REFERENCES ***********/
  36. extern    int   verbose;
  37. extern    int   reverse_path;
  38.  
  39. /******************************************************************
  40.  
  41.   FUNCTION: init_source( net, source )
  42.  
  43.   DESCRIPTION:
  44.         This function initializes the data structures for Dijkstra's
  45.     algorithm which is used to create distance vector routing
  46.     tables.
  47.  
  48. **********************************************************************/
  49.  
  50. void   init_source( Network *net, long source )
  51. {
  52.    long  v;
  53.    Interface *cur_ifc;
  54.    
  55.    for( v=0; v< net->no_nodes; v++ )
  56.       {/*
  57.        **     Start with all nodes at infinite distance and with
  58.        **     no parent node.
  59.        */
  60.       net->adj_list[v].dist_vects.distance = INFINITE_DIST;
  61.       net->adj_list[v].dist_vects.next_hop_subnet = NULL;
  62.       net->adj_list[v].dist_vects.next_hop_node = INVALID_NODE;
  63.       net->adj_list[v].dist_vects.in_tree = FALSE;
  64.       for( cur_ifc =  net->adj_list[v].interfaces.first;
  65.        cur_ifc != NULL; cur_ifc = cur_ifc->next )
  66.      {
  67.      cur_ifc->type &= ~ROUTE_MASK;   /* zero child and leaf */
  68.      cur_ifc->in_tree = FALSE;       /* used by print_tree */
  69.          }
  70.       }
  71.    /*
  72.    **      The distance of the source site is 0
  73.    */
  74.    net->adj_list[source].dist_vects.distance = 0;
  75.    return;
  76. }
  77.  
  78. /**********************************************************************
  79.  
  80.   FUNCTION: relax_node( frm_node, to_node, weight )
  81.  
  82.   DESCRIPTION:
  83.        This function relaxes the to_node of an edge by reassigning
  84.        the distance function if this path is shorter than the best
  85.        currently known path.
  86.  
  87. **********************************************************************/
  88.  
  89. void relax_node(Network *net, Interface *frm_ifc, long frm_node, long to_node, long weight )
  90. {
  91.    DVTable *dvt1, *dvt2;
  92.  
  93.    dvt1 = &net->adj_list[frm_node].dist_vects;
  94.    dvt2 = &net->adj_list[to_node].dist_vects;
  95.      /*
  96.      **    Check if this new path is shorter distance or the same distance
  97.      **    and through a lower address node.
  98.      */
  99.      if( dvt2->distance >= (dvt1->distance + weight) )
  100.     {
  101.     /*
  102.     **      If the node this path just came from is the same
  103.     **      length as my previous path and the address of the
  104.     **      previous node is higher than the one I have as prev,
  105.     **      then do not relax this node.
  106.     */
  107.     if( dvt2->next_hop_subnet != NULL )
  108.        if(dvt2->distance == (dvt1->distance + weight) &&
  109.           frm_ifc->to_addr >  dvt2->next_hop_subnet->to_addr )
  110.           return;
  111.  
  112.     /*
  113.     **    If we got this far, then this path is shorter distance than the
  114.     **    previous known one or through a lower address so remember it as
  115.     **    the shortest distance path.
  116.     */
  117.      dvt2->distance = dvt1->distance + weight;
  118.          dvt2->next_hop_subnet = frm_ifc;
  119.      dvt2->next_hop_node = frm_node;
  120.         }/* endif */
  121.    return;
  122. }
  123.  
  124. /***********************************************************************
  125.  
  126.   FUNCTION: dijkstra_tree( net, source )
  127.  
  128.   DESCRIPTION:
  129.        This function performs the outer loop of Dijkstra's algorithm.
  130.        It initializes the node distance vector table entries, and then
  131.        investigates nodes one at a time starting always with the one
  132.        of shortest distance.
  133.  
  134. **********************************************************************/
  135.  
  136. void dijkstra_tree( Network *net, long source )
  137. {
  138.    long       cur_node;
  139.    Interface *cur_ifc, *back_ifc;
  140.    
  141.    init_source( net, source );
  142.  
  143.    while( (cur_node = extract_min_dist_node( net )) != INVALID_NODE )
  144.       {/*
  145.        **   cur_node is the node that is the minimum distance from the source
  146.        **   of all the remaining nodes.  It's place in the tree has now stabilized
  147.        **   because no shorter distance path will be found in the future so record
  148.        **   it and relax the nodes on its outgoing edges that are not down.
  149.        */
  150.        net->adj_list[cur_node].dist_vects.in_tree = TRUE;
  151.        for( cur_ifc = net->adj_list[cur_node].interfaces.first;
  152.         cur_ifc != NULL; cur_ifc = cur_ifc->next )
  153.       {
  154.       if( !(cur_ifc->type & (DOWN | DISABLED)))
  155.         {
  156.         /*
  157.         **   The current mrouted uses the outgoing metric to determine
  158.         **   the cost between this node and its parent in the source tree.
  159.         **   We need to determine the reverse direction edge weight for
  160.         **   use in the distance calculation since we are coming from the
  161.         **   parent
  162.         */
  163.         back_ifc = find_ifc( net, NULL, cur_ifc->to_name, cur_ifc->name );
  164.         if( back_ifc == NULL || back_ifc->type & (DOWN | DISABLED))
  165.            {/*
  166.             **    For some reason this tunnel was not reported in both directions
  167.             **    so, we will assume that the tunnel is actually down
  168.             */
  169.            if( verbose )
  170.               printf( "reverse edge  %s to %s not found  or down, assuming this edge is down\n",
  171.                  cur_ifc->to_name, cur_ifc->name );
  172.            cur_ifc->type |= DOWN;
  173.             }
  174.         else
  175.            {
  176.            if( reverse_path )
  177.                 relax_node( net, back_ifc, cur_node, cur_ifc->to_node, cur_ifc->metric );
  178.            else
  179.                 relax_node( net, back_ifc, cur_node, cur_ifc->to_node, back_ifc->metric );
  180.            }
  181.             }
  182.           }/* endfor */
  183.       }/* endwhile */
  184.    /*
  185.    **    Now that the distance vector routing calculations are complete,
  186.    **    calculate the child and leaf bits for the reverse path forwarding
  187.    **    algorithm.
  188.    */
  189.    find_child_leaf( net, source ); 
  190.    return;
  191. }
  192.  
  193. /******************************************************************************
  194.  
  195.   FUNCTION: extract_min_dist_node( net )
  196.  
  197.   DESCRIPTION:
  198.         This function returns the node that has the minimum distance in
  199.     its distance vector table.  It only searches through nodes that
  200.     are not yet marked as in tree.  If all nodes are done, then it returns
  201.     INVALID_NODE.  A simple linear search is performed each time the
  202.     function is called.
  203.  
  204. ******************************************************************************/
  205.  
  206. long    extract_min_dist_node( Network *net )
  207. {
  208.    long i;
  209.    long cur_min;
  210.    long min_node;
  211.  
  212.    min_node = INVALID_NODE;
  213.    cur_min = INFINITE_DIST;
  214.    
  215.    for( i = 0; i < net->no_nodes; i++)
  216.       {
  217.       if( !net->adj_list[i].dist_vects.in_tree )
  218.      if( net->adj_list[i].dist_vects.distance < cur_min )
  219.         {
  220.         min_node = i;
  221.         cur_min =  net->adj_list[i].dist_vects.distance;
  222.         }
  223.       }
  224.    return min_node;
  225. }
  226.  
  227. /***********************************************************************
  228.  
  229.   FUNCTION: find_child_leaf( net, source )
  230.  
  231.   DESCRIPTION:
  232.         Fill in the child and leaf structures for each distance
  233.     vector routing table in the graph.  It only fills in the
  234.     entries for routes to the current source.  The child and
  235.     leaf bits are maintained at each interface.  The calculation
  236.     is carried out as specified for reverse path forwarding.
  237.  
  238. ***********************************************************************/
  239.  
  240. void      find_child_leaf( Network *net, long source )
  241. {
  242.    int        v;
  243.    Interface *cur_ifc;
  244.    DVTable   *to_dvtable;
  245.    Node      *frm_node;
  246.  
  247.    for( v = 0; v < net->no_nodes; v++ )
  248.       {
  249.       frm_node = &net->adj_list[v];
  250.       if( v != source && frm_node->dist_vects.next_hop_subnet == NULL )
  251.      /*
  252.      **     This node is not in the spanning tree so we don't need
  253.      **     to worry about its child interfaces.
  254.      */
  255.      continue;
  256.       for( cur_ifc = frm_node->interfaces.first;
  257.        cur_ifc != NULL; cur_ifc = cur_ifc->next )
  258.     {
  259.     if( !(cur_ifc->type & (DOWN | DISABLED)))
  260.         {/*
  261.          **   If this is the next_hop_subnet, then it is the
  262.          **   parent so mark it as such.
  263.          */
  264.         if( cur_ifc == frm_node->dist_vects.next_hop_subnet )
  265.            {
  266.            cur_ifc->type |= PARENT;
  267.            continue;
  268.            }
  269.         /*
  270.         **       This is not the parent interface so start out
  271.         **       assuming that it is a child and leaf and then
  272.         **       determine if it is not.
  273.         */
  274.         cur_ifc->type |= ( CHILD | LEAF );
  275.         /*
  276.         **    For the neighbor (always only one) on this interface.  Check if
  277.         **    it has a shorter distance or same distance and
  278.         **    lower address.  If so, then this interface is not a
  279.         **    child.
  280.         */
  281.         to_dvtable = &net->adj_list[cur_ifc->to_node].dist_vects;
  282.         if( !(net->adj_list[cur_ifc->to_node].type & SUBNET ))
  283.            {
  284.            if( to_dvtable->distance <= frm_node->dist_vects.distance &&
  285.           !(cur_ifc->type & SUBNET))
  286.               {
  287.           if( to_dvtable->distance == frm_node->dist_vects.distance )
  288.              {
  289.              if( cur_ifc->to_addr < cur_ifc->address)
  290.             cur_ifc->type &= ~CHILD;
  291.              }
  292.           else
  293.              /*
  294.              **     If this is a SUBNET node, then make everybody except
  295.              **     the parent children because messages are broadcast on
  296.              **     the subnet.
  297.              */
  298.              cur_ifc->type &= ~CHILD;
  299.               }
  300.            }
  301.         else
  302.            {/*
  303.         **    This is a connection to a subnet.  The subnet is not a child if
  304.         **    the subnet does not consider this node a parent.
  305.         */
  306.            if( strcmp( to_dvtable->next_hop_subnet->to_name, cur_ifc->name ))
  307.           cur_ifc->type &= ~CHILD;
  308.            }
  309.         if( to_dvtable->next_hop_node == INVALID_NODE ||
  310.             to_dvtable->next_hop_node == v )
  311.            /*
  312.            **   This interface is not a leaf if there is a neighbor
  313.            **   that considers this node its parent (next_hop_subnet)
  314.            **   or if it leads to the source.
  315.            */
  316.            cur_ifc->type &= ~LEAF;
  317.         
  318.         if( (cur_ifc->type & CHILD) && (cur_ifc->type & LEAF) &&
  319.             (cur_ifc->type & TUNNEL ))
  320.            /*
  321.            **      This interface is a tunnel and the router at the
  322.            **      other end does not consider this router to be its
  323.            **      parent so do not mark it as a child or leaf.
  324.            */
  325.            cur_ifc->type &= ~(CHILD|LEAF);
  326.         }
  327.         }
  328.       }
  329. }
  330.  
  331. /************************************************************************
  332.  
  333.   FUNCTION: print_entry( )
  334.  
  335.   DESCRIPTION:
  336.       Print a particular entry of a path or a tree.
  337.  
  338. ************************************************************************/
  339. void print_entry( FILE *out, NAME name, long indent, long posn, long distance,
  340.           long threshold, long suspect, int print_out, u_long type )
  341. {
  342.    long i;
  343.  
  344.    if( !print_out )
  345.       return;
  346.    for( i=1; i <= (posn*indent); i++)
  347.       fprintf(out, " " );
  348.    fprintf(out, "%s, %ld/%ld/%ld", name, posn, distance, threshold );
  349.    if (type & SRCRT)
  350.       fprintf(out, "/srcrt");
  351.    if (type & DOWN)
  352.       fprintf(out, "/down");
  353.    if (type & DISABLED)
  354.       fprintf(out, "/disabled");
  355.    if( suspect )
  356.       fprintf(out, "/SUSPECT");
  357.    fprintf(out, "\n");
  358. }
  359.  
  360. /************************************************************************
  361.  
  362.   FUNCTION: print_tree( )
  363.  
  364.   DESCRIPTION:
  365.       This function prints out the shortest path tree determined by
  366.       the distance vector routing protocol.  It is called recursively.
  367.       Each time it finds another node in the tree, it calls the function
  368.       again with this node as the source.  The branches of the tree will
  369.       follow those determined by the distance vector routing protocol
  370.       and the find child and leaf routine.  Subnet nodes are not printed
  371.       unless they are the source or the destination.
  372.  
  373. *************************************************************************/
  374.  
  375. void   print_tree( FILE *out, int indent, Network *net, long source, Interface *frm_ifc, long posn,
  376.            long hops, long threshold, long suspect, long max_thresh, int print_out )
  377. {
  378.    int        add_indent = 0;
  379.    long       nxt_thresh;
  380.    Interface *cur_ifc, *back_ifc;
  381.    NAME       last_name;
  382.  
  383.    if( frm_ifc !=  net->adj_list[source].dist_vects.next_hop_subnet && threshold > 0 )
  384.       {/*
  385.        **     The previous node is forwarding packets to me but I
  386.        **     will not forward them because he is not my parent node.
  387.        **     Just print my interfaces indicating receipt and return.
  388.        */
  389.       if( !(net->adj_list[source].type & SUBNET ))
  390.      {
  391.      print_entry(out, frm_ifc->name, indent, posn, -1, threshold, suspect,
  392.              print_out, frm_ifc->type );
  393.      frm_ifc->in_tree = TRUE;
  394.      strcpy( last_name, "\0" );
  395.      for( cur_ifc = net->adj_list[source].interfaces.first;
  396.          cur_ifc != NULL; cur_ifc = cur_ifc->next )
  397.         if( !(cur_ifc->type & (DOWN|DISABLED)))
  398.            {
  399.            if( strcmp( cur_ifc->name, last_name ) &&
  400.            strcmp( cur_ifc->name, frm_ifc->name))
  401.           {/*
  402.            **    This interface has not been printed out yet so lets do
  403.            **    it now.  The above if assumes all interfaces of the same
  404.            **    name are together at a node and not separated by other
  405.            **    interfaces.
  406.            */
  407.           print_entry(out, cur_ifc->name, indent, posn+1, -1,
  408.                   threshold, suspect, print_out, cur_ifc->type );
  409.           cur_ifc->in_tree = TRUE;
  410.           strcpy( last_name, cur_ifc->name );
  411.               }
  412.            }
  413.          }
  414.       return;
  415.       }
  416.    /*
  417.    **     If I reached here, this packet came in on my parent interface
  418.    **     so print all of my interfaces and forward it to all of my
  419.    **     children.
  420.    */
  421.    strcpy( last_name, "\0" );
  422.    if( net->adj_list[source].type & SUBNET )
  423.       posn--;
  424.    /*
  425.    **      The following loop etc are to make sure before we print this
  426.    **      interface out that there is at least one up interface with this
  427.    **      name before we print it out.
  428.    */
  429.    if( !(net->adj_list[source].type & SUBNET ))
  430.       {
  431.       print_entry(out, frm_ifc->name, indent, posn,
  432.           net->adj_list[source].dist_vects.distance,
  433.           threshold, suspect, print_out, frm_ifc->type );
  434.       hops++;
  435.       }
  436.    frm_ifc->in_tree = TRUE;
  437.  
  438.    add_indent = 0;
  439.    for( cur_ifc = net->adj_list[source].interfaces.first;
  440.         cur_ifc != NULL; cur_ifc = cur_ifc->next )
  441.      if( !(cur_ifc->type & (DOWN|DISABLED)))
  442.       {
  443.       if( strcmp( cur_ifc->name, frm_ifc->name))
  444.      {
  445.      if( strcmp( cur_ifc->name, last_name ))
  446.         {/*
  447.          **    This interface has not been printed out yet so lets do
  448.          **    it now.  The above if assumes all interfaces of the same
  449.          **    name are together at a node and not separated by other
  450.          **    interfaces.
  451.          */
  452.         add_indent = 1;
  453.         if( !(net->adj_list[source].type & SUBNET ))
  454.            print_entry(out, cur_ifc->name, indent, posn+1,
  455.                net->adj_list[source].dist_vects.distance,
  456.                threshold, suspect, print_out, cur_ifc->type );
  457.         else
  458.            add_indent = 0;
  459.         cur_ifc->in_tree = TRUE;
  460.         }
  461.      strcpy( last_name, cur_ifc->name );
  462.          }
  463.       else
  464.      add_indent = 0;
  465.       
  466.       if( cur_ifc->type & CHILD )
  467.      {
  468.         /*
  469.         **    Forward the packet to all of the children.  Also send
  470.         **    a pointer to the interface the site is receiving this
  471.         **    on so I can decide whether it received it from its parent.
  472.         **    When determining the current ttl(threshold) needed,a packet must have
  473.         **    a ttl of at least 2 to be forwarded.
  474.         */
  475.         if( cur_ifc->threshold == 1 )
  476.            nxt_thresh = hops + 2;
  477.         else
  478.            nxt_thresh = hops + cur_ifc->threshold;
  479.         if( nxt_thresh < threshold )
  480.            nxt_thresh = threshold;
  481.         back_ifc = find_ifc( net, NULL, cur_ifc->to_name, cur_ifc->name );
  482.         /*
  483.         **    If the reverse direction of this edge is down, do not
  484.         **    continue out this edge.
  485.         */
  486.         if( back_ifc->type & (DOWN | DISABLED))
  487.            continue;
  488.         /*
  489.         **    The following if allows a ttl to be specified and only the
  490.         **    portions of the tree that are within reach of that ttl will
  491.         **    be printed.  The max_thresh is specified when requesting a
  492.         **    tree printout.
  493.         */
  494.         if( max_thresh < 0 || nxt_thresh <= max_thresh )
  495.            {
  496. /*           printf( "calling print tree %s with posn %ld add_indent %d\n",
  497.               cur_ifc->to_name, posn+1, add_indent );*/
  498.            print_tree( out, indent, net, cur_ifc->to_node, back_ifc, (posn + 1 + add_indent),
  499.                hops, nxt_thresh, (cur_ifc->type & SUSPECT), max_thresh, print_out );
  500.            }
  501.          }
  502.       }
  503.    return;
  504. }
  505.  
  506. /**************************************************************************
  507.  
  508.   FUNCTION: print_unreach( net )
  509.  
  510.   DESCRIPTION:
  511.        This function prints a list of the nodes that were found to be
  512.        unreachable when investigating the source's minimum spanning
  513.        tree.  It will also print the nodes that were not reached due
  514.        to specification of a max_thresh (ttl) for the tree printout.
  515.        Subnets that are unreachable are not printed out, just the
  516.        unreachable interfaces on it.
  517.  
  518. **************************************************************************/
  519.  
  520. void      print_unreach(FILE *out, Network *net, int print_out )
  521. {
  522.    long       v, j=0, found, found2, last_v = INVALID_NODE,
  523.               tot_unreach = 0;
  524.    Interface *cur_ifc;
  525.    NAME       last_name;
  526.  
  527.    strcpy( last_name, "\0" );
  528.  
  529.    found = TRUE;
  530.    found2 = TRUE;
  531.    if( !print_out )
  532.       fprintf( out, "\nNumber of unreachable interfaces:  " );
  533.    else
  534.       fprintf( out, "\nUnreachable interfaces:\n" );
  535.    for( v = 0; v < net->no_nodes; v++ )
  536.      {
  537.      if( !(net->adj_list[v].type & SUBNET ))
  538.       {
  539.       if( !net->adj_list[v].dist_vects.in_tree )
  540.      {/*
  541.       **      If this node is not in the tree, it must have been
  542.       **      unreachable when djkstra's algorithm was computed.
  543.       */
  544.      for( cur_ifc = net->adj_list[v].interfaces.first; cur_ifc != NULL;
  545.           cur_ifc = cur_ifc->next )
  546.         {/*
  547.          **  Print all of the interfaces at this node
  548.          */
  549.         if( strcmp( last_name, cur_ifc->name ))
  550.            {
  551.            strcpy( last_name, cur_ifc->name );
  552.            if( print_out )
  553.           {
  554.           j++;
  555.           if( cur_ifc->type & (DOWN|DISABLED))
  556.              fprintf( out, "%s down, ", cur_ifc->name );
  557.           else
  558.              fprintf( out, "%s, ", cur_ifc->name );
  559.           if( j >= 4 )
  560.              {/* break the printout into separate lines */
  561.              fprintf(out, "\n" );
  562.              j = 0;
  563.                  }
  564.               }
  565.            else
  566.           tot_unreach++;  
  567.            }
  568.         }/*endfor*/
  569.          }/* endif */
  570.       else
  571.      {/*
  572.       **      This node was found to be in the spanning tree
  573.       **      but it may not have been printed because
  574.       **      it was down or a max ttl was specified.  If all of
  575.       **      the interfaces of a specific name are down then print
  576.       **      this interface as unreachable even though the node is
  577.       **      reachable.  Also print this interface name if none of
  578.       **      the interfaces with this name were printed when the
  579.       **      tree was printed out.
  580.       */
  581.      for( cur_ifc = net->adj_list[v].interfaces.first; cur_ifc != NULL;
  582.           cur_ifc = cur_ifc->next )
  583.         {
  584.         if( strcmp( last_name, cur_ifc->name ))
  585.            {
  586.            if( !found  || !found2 )
  587.           {
  588.           if( print_out )
  589.              {
  590.              j++;
  591.              if( !found )
  592.             fprintf( out, "%s down, ", last_name );
  593.              else
  594.             fprintf( out, "%s, ", last_name );
  595.              if( j >= 4 )
  596.             {
  597.             fprintf(out, "\n" );
  598.             j = 0;
  599.                     }
  600.              }
  601.           else
  602.              tot_unreach++;
  603.               }
  604.            found = FALSE;
  605.            found2 = FALSE;
  606.            }/* end if */
  607.         strcpy( last_name, cur_ifc->name );
  608.         last_v = v;
  609.         if( !(cur_ifc->type & (DOWN|DISABLED)))
  610.            /*
  611.            **   There is at least one interface with this name that is not
  612.            **   down so don't print it.
  613.            */
  614.            found = TRUE;
  615.         if( cur_ifc->in_tree )
  616.            /*
  617.            **   There is at least one interface with this name that was
  618.            **   printed with the latest source tree so don't print it
  619.            **   here.
  620.            */
  621.            found2 = TRUE;
  622.         }/* end for */
  623.          }/* end else */
  624.       }/* end if( SUBNET ) */
  625.      for( cur_ifc = net->adj_list[v].interfaces.first; cur_ifc != NULL;
  626.       cur_ifc = cur_ifc->next )
  627.     cur_ifc->in_tree = FALSE; /* reset for next round */
  628.      }/* end for each node */
  629.    if( !print_out )
  630.       fprintf( out, "%ld", tot_unreach );
  631.    fprintf(out,  "\n" );
  632.  
  633.    strcpy( last_name, "\0" );
  634.    return;
  635. }
  636.  
  637.  
  638.  
  639. /*******************************************************************
  640.  
  641.   FUNCTION: push_path_elem( Path_stack *stack, NAME name )
  642.  
  643.   DESCRIPTION:
  644.        This function pushes a path element onto a stack for later
  645.        retrieval.  It returns a pointer to the path element.
  646.  
  647. **********************************************************************/
  648.  
  649. Path_item *push_path_elem( Path_stack *stack, NAME name, long distance,
  650.                long threshold, int suspect, int same_node,
  651.                int print, u_long type )
  652. {
  653.    Path_item *cur_elem;
  654.  
  655.    cur_elem = (Path_item *)calloc(1, sizeof(Path_item));
  656.    strcpy( cur_elem->name, name );
  657.    cur_elem->distance = distance;
  658.    cur_elem->threshold = threshold;
  659.    cur_elem->same_node = same_node;
  660.    cur_elem->suspect = suspect;
  661.    cur_elem->print = print;
  662.    cur_elem->type = type;
  663.    if( stack->number == 0 )
  664.       {
  665.       stack->first = cur_elem;
  666.       cur_elem->next = NULL;
  667.       }
  668.    else
  669.       {
  670.       cur_elem->next = stack->first;
  671.       stack->first = cur_elem;
  672.       }
  673.    stack->number++;
  674.    return cur_elem;
  675. }
  676.  
  677. /**************************************************************************
  678.  
  679.   FUNCTION: pop_path_elem( Path_stack *stack )
  680.  
  681.   DESCRIPTION:
  682.         This function deletes the top item in the path stack
  683.     and fixes the stack variables accordingly.
  684.  
  685. ***************************************************************************/
  686.  
  687. void     pop_path_elem( Path_stack *stack )
  688. {
  689.    Path_item *cur_item;
  690.  
  691.    if( stack->number > 0 )
  692.       {
  693.       cur_item = stack->first;
  694.       stack->first = cur_item->next;
  695.       free( cur_item );
  696.       stack->number--;
  697.       }
  698. }
  699.  
  700. /*****************************************************************************
  701.  
  702.   FUNCTION: print_path_stack( Path_stack *stack, FILE *out )
  703.  
  704.   DESCRIPTION:
  705.        This function prints out the path saved in the stack.  It is called
  706.        each time the source is reached to print the path taken to reach the
  707.        source.
  708.  
  709. ***************************************************************************/
  710.  
  711. void    print_path_stack( Path_stack *stack, long indent, FILE *out )
  712. {
  713.    Path_item *cur_elem;
  714.    long i, cur_threshold = 0, hops=1;
  715.    long nxt_thresh;
  716.  
  717.    /*
  718.    **    For each element in the stack
  719.    */
  720.    for( i = 1, cur_elem = stack->first; cur_elem != NULL; cur_elem = cur_elem->next )
  721.       {/*
  722.        **   Calculate the ttl needed to reach this node from the source.  A ttl of
  723.        **   at least 2 is required to be forwarded out a link.
  724.        */
  725.       nxt_thresh = (hops - 1) + cur_elem->threshold;
  726.       if( cur_elem->threshold == 1 )
  727.      nxt_thresh++;
  728.       if( nxt_thresh > cur_threshold )
  729.      cur_threshold = nxt_thresh;
  730.       /*
  731.       **    This path element is in the stack but should not be printed out so
  732.       **    go on to the next one.  This is most likely a subnet node, it was
  733.       **    placed in the stack to allow correct calculation of the thresholds.
  734.       */
  735.       if( !cur_elem->print )
  736.      continue;
  737.       /*
  738.       **    Indent the proper amount of spaces and print the node
  739.       */
  740.       print_entry( out, cur_elem->name, indent, i,
  741.            cur_elem->distance, cur_threshold, cur_elem->suspect, TRUE,
  742.            cur_elem->type);
  743.       /*
  744.       **     The same_node boolean is used to indicate when the next element in the
  745.       **     stack will be an interface at the same site so don't increment
  746.       **     the hop count.
  747.       */
  748.       if( !cur_elem->same_node )
  749.      hops++;
  750.       i++;
  751.       }
  752.    return;
  753. }
  754.  
  755. /************************************************************************
  756.  
  757.   FUNCTION: print_path()
  758.  
  759.   DESCRIPTION:
  760.       This function is called recursively to print a path from a
  761.       source to a destination.  All paths of equal distance are
  762.       printed unless the branch is at a subnet connection.  The
  763.       alternate paths are printed because the current version of
  764.       mrouted will not change paths if a new path appears that is
  765.       equal length so it is not always the low address path that wins.
  766.       The equal paths that branch at subnets will always use the
  767.       low address path because mrouted will always choose this way.
  768.       
  769. *************************************************************************/
  770.  
  771. void     print_path( FILE *out, Network *net, int indent, NAME source, NAME cur,
  772.              long cur_node, Path_stack *stack )
  773. {
  774.    long suspect, cur_metric;
  775.    Interface *cur_ifc, *back_ifc;
  776.  
  777.    /*
  778.    **     First, find out the parent interface of this node.  If there
  779.    **     is no parent interface, this must be the source so print out
  780.    **     the path.
  781.    */
  782.    cur_ifc = net->adj_list[cur_node].dist_vects.next_hop_subnet;
  783.    if( cur_ifc == NULL )
  784.       {
  785.       /*
  786.       **   Although the source is at this node, I may not have entered the
  787.       **   node on the source interface so I also need to print the interface
  788.       **   I entered on.
  789.       */
  790.       if(strcmp( source, cur ))
  791.      push_path_elem( stack, cur, 0, 0, FALSE, TRUE, TRUE, 0 );
  792.       if( verbose )
  793.      fprintf( out, "\nPath from specified source to destination:\n");
  794.       fprintf( out, "%s, 0/0/0\n", source );
  795.       print_path_stack( stack, indent, out );
  796.       if(strcmp( source, cur ))
  797.      pop_path_elem( stack );
  798.       return;
  799.       }
  800.  
  801.    /*
  802.    **     If this node is a subnet, I don't need to worry about equal
  803.    **     distance path branching so simply push this node onto the
  804.    **     path stack and investigate its parent node.
  805.    */
  806.    if(net->adj_list[cur_node].type & SUBNET)
  807.       {
  808.       back_ifc = find_ifc( net, NULL, cur_ifc->to_name, cur_ifc->name );
  809.       suspect = FALSE;
  810.       if( back_ifc->type & SUSPECT )
  811.      suspect = TRUE;
  812.       push_path_elem( stack, cur, net->adj_list[cur_node].dist_vects.distance,
  813.               back_ifc->threshold, suspect, FALSE, FALSE,
  814.               back_ifc->type );
  815.       print_path( out, net, indent, source, cur_ifc->to_name,
  816.           cur_ifc->to_node, stack );
  817.       /*
  818.       **   After returning, clean up the stack
  819.       */
  820.       pop_path_elem( stack );
  821.       return;
  822.       }
  823.    /*
  824.    **    If I have made it to here, then this is not a subnet node
  825.    **    so I must investigate all paths of equal length that branch at
  826.    **    this point.
  827.    */
  828.    for( cur_ifc = net->adj_list[cur_node].interfaces.first; cur_ifc != NULL;
  829.         cur_ifc = cur_ifc->next )
  830.      if( !(cur_ifc->type & (DOWN | DISABLED)))
  831.       {
  832.       back_ifc = find_ifc( net, NULL, cur_ifc->to_name, cur_ifc->name );
  833.       if( back_ifc == NULL || (back_ifc->type & (DOWN | DISABLED)))
  834.      {/*
  835.       **    For some reason this tunnel was not reported in both directions
  836.       **    so, we will assume that the tunnel is actually down
  837.       */
  838.      if( verbose )
  839.         printf( "reverse edge  %s to %s not found or down, assuming edge is down\n",
  840.            cur_ifc->to_name, cur_ifc->name );
  841.      cur_ifc->type |= DOWN;
  842.      continue;
  843.          }
  844.  
  845.       /*
  846.       **   Determine the path length that would result if this edge were
  847.       **   on the path and if it is greater than the distance
  848.       **   to the source then this is not an alternate branch so go on to the
  849.       **   next interface.
  850.       */
  851.       if( reverse_path )
  852.          cur_metric = back_ifc->metric + net->adj_list[cur_ifc->to_node].dist_vects.distance;
  853.       else
  854.          cur_metric = cur_ifc->metric + net->adj_list[cur_ifc->to_node].dist_vects.distance;
  855.       if( cur_metric > net->adj_list[cur_node].dist_vects.distance )
  856.      continue;
  857.  
  858.       suspect = FALSE;
  859.       if( back_ifc->type & SUSPECT )
  860.      suspect = TRUE;
  861.       /*
  862.       **   If we have gotten this far, then this interface is on the current
  863.       **   path so push it onto the path stack.
  864.       */
  865.       push_path_elem( stack, cur, net->adj_list[cur_node].dist_vects.distance,
  866.               back_ifc->threshold, suspect, FALSE, TRUE,
  867.               back_ifc->type);
  868.       /*
  869.       **   The interface that we are going out is different than the one we
  870.       **   arrived on so also push the interface we are leaving on onto the stack.
  871.       */
  872.       if(strcmp( cur_ifc->name, cur ))
  873.      push_path_elem( stack, cur_ifc->name, net->adj_list[cur_node].dist_vects.distance,
  874.              back_ifc->threshold, suspect, TRUE, TRUE,
  875.              back_ifc->type);
  876.       /*
  877.       **    Now to find the rest of the path to the source starting from here.
  878.       */
  879.       print_path( out, net, indent, source, cur_ifc->to_name,
  880.           cur_ifc->to_node, stack );
  881.       /*
  882.       **    Clean up the path stack and remove my entries
  883.       */
  884.       pop_path_elem( stack );
  885.       if(strcmp( cur_ifc->name, cur ))
  886.      pop_path_elem( stack );
  887.       }
  888.    return;
  889. }
  890.  
  891.  
  892.