routing.c

模拟器提供了一个简单易用的平台

/*
 * $Revision: 1.2 $
 * $Id: routing.C,v 1.2 1998/06/02 16:04:44 bobby Exp bobby $
 */

/*
 * File: routing.c
 * Author: Suman Banerjee <[e-mail]>
 * Date: July 31, 2001
 * Terms: GPL
 *
 * myns simulator
 */



#include <stdio.h>
#include <stdlib.h>

#include "gb_graph.h"

#define MAX_NODE_NAME_SIZE	255

#define BIGNUM 0x0fffffffl
#define vtoi(g,v)	((v) - (g)->vertices)

long **route_dist, **route_ldist, **route_t;
long **route_path, **route_lpath;

int iter_print_route (int a, int b)
{
  do {
    a = route_lpath[a][b];
     printf ("%d,", a);
  } while (a!=b);
  return 1;
}


int rt_num_hops (int a, int b)
{
  int c = 0;
  while(a!=b) {
    a = route_lpath[a][b];
    c++;
  }
  return c;
}

int print_route (int a, int b)
{
//   if (a == b)
//     return a;
//   if (route_lpath[a][b] == -1) {
//     c_printf (STAT, "%d,", a);
//     return b;
//   }
//   print_route(a, route_lpath[a][b]);
//   print_route(route_lpath[a][b],b);
  iter_print_route (a, b);
  return 1; 
}

int rec_next_hop (int a, int b)
{
  /* using temporary matrix now! */
  if (a==b)
    return a;
  if (route_t[a][b] == -1)
    return b;
  return rec_next_hop(a, route_t[a][b]);
}

int next_hop (int a, int b)
{
  return route_lpath[a][b];
}

/*
void print_connectivity_matrix(int n, long **dist)
{
  int i, j;

  c_printf (DEBUG, "    ");
  for (i=0; i < n; i++)
    c_printf(DEBUG, "  %2d", i);
  printf ("\n");
	
  for (i=0; i < n; i++){
    c_printf (DEBUG, "%2d |", i);
    for (j=0; j < n; j++){
      if (dist[i][j] == BIGNUM)
	c_printf (DEBUG, "   .");
      else
	c_printf (DEBUG, "  %2d", dist[i][j]);
    }
    c_printf (DEBUG, "|  %2d", i);
    c_printf (DEBUG, "\n");
  }
  c_printf (DEBUG, "---\n");
	
}
*/

int allocate_route_table(Graph *g)
{
  int i;


  i = g->n*g->n*sizeof(long*);
  route_lpath = (long**) malloc(i);
  for (i=0; i < g->n; i++) {
    route_lpath[i] = (long *) malloc (g->n*sizeof(long));
  }
  return 1;
}


long
create_routing_table(Graph *g)
{
  register int i,j,k;
	
  int changed;
  long diam, ldiam, newdist = 0, otherend;
  Vertex *v;
  Arc *a;

  i = g->n*g->n*sizeof(long*);
  route_dist = (long **)malloc(i);
  route_ldist = (long**)malloc(i);

  route_t = (long **)malloc(i);
  route_path = (long**) malloc(i);
  route_lpath = (long**) malloc(i);

  for (i=0; i < g->n; i++) {
    route_dist[i] = (long *)malloc(g->n*sizeof(long));
    route_ldist[i] = (long *)malloc(g->n*sizeof(long));
		
    route_t[i] = (long *) malloc (g->n*sizeof(long));
    route_path[i] = (long *) malloc (g->n*sizeof(long));
    route_lpath[i] = (long *) malloc (g->n*sizeof(long));
		
    for (j=0; j < g->n; j++){
      route_dist[i][j] = route_ldist[i][j] =  BIGNUM;
      route_path[i][j] = route_lpath[i][j] = -1;
    }
    route_dist[i][i] = route_ldist[i][i] = 0;
  }
	
  for (i=0,v=g->vertices; i < g->n; i++,v++){
    for (a=v->arcs; a; a=a->next) {
      otherend = vtoi(g,a->tip);
       	    route_ldist[i][otherend] = 1; // previously a->len;     
    /*  route_ldist[i][otherend] = a->policywt;
      if (! a->policywt){
	route_ldist[i][otherend] = 1; 
      } */
      
      /* edge weight */
      route_dist[i][otherend] = 1;
    }
  }
  /*   	print_connectivity_matrix (g->n, route_dist);   */
	
  /* iterate until nothing changes */
  changed = 1;
  while (changed) {
    /* INVARIANT: route_dist[i][k] ==
       BIGNUM  === route_ldist[i][k] == BIGNUM */
    changed = 0;
    for (i=0; i<g->n; i++)
      for (j=0; j<g->n; j++) {
	for (k=0; k<g->n; k++) { /* i < k < j */
				/*if (i==j || j==k || i==k)
				  continue;*/
				/* i != j && j != k && i != k */
	  if ( (route_dist[i][k] == BIGNUM ) || (route_dist[k][j] == BIGNUM) )
	    continue;	/* nothing to gain */
	  newdist = route_dist[i][k] + route_dist[k][j];
	  if (newdist < route_dist[i][j]) {
	    route_dist[i][j] = newdist;
	    changed++;
	    route_path[i][j] = k;
	  } /* if shorter */
	  newdist = route_ldist[i][k] + route_ldist[k][j];
	  if (newdist < route_ldist[i][j]) {
	    route_ldist[i][j] = newdist;
	    route_lpath[i][j] = k;
	    changed++;
	  } /* if shorter */
	} /* for k */
      } /* for j */
  } /* while (changed) */

  diam = ldiam = 0;

  /* copy into t -- and create the routing table */
  for (i=0; i<g->n; i++) {
    for (j=0; j<g->n; j++) {
      route_t[i][j] = route_lpath[i][j];
    }
  }

  for (i=0; i<g->n; i++) {
    for (j=0; j<g->n; j++) {
      route_lpath[i][j] = rec_next_hop(i,j);
    }
  }

  /* should be able to free everything but
   * route_lpath
   */
	
  {
		
    for (i=0; i<g->n; i++) {
      free(route_t[i]);
      free(route_dist[i]);
//      free(route_ldist[i]);
      free(route_path[i]);
    }
    free(route_dist);
//    free(route_ldist);
    free(route_t);
    free(route_path);
  }
	

//   print_connectivity_matrix (g->n, route_lpath); 
	
	
  /* now find max shortest path */
  /* 	for (i=0; i<g->n; i++) */
  /* 		for (j=0; j<g->n; j++) { */
  /* 			if (route_dist[i][j] > diam){ */
  /* 				diam = route_dist[i][j]; */
  /* 			} */
  /* 			if (route_ldist[i][j] > diam) */
  /* 				ldiam = route_ldist[i][j]; */
  /* 		} */
	
  /* 	for (i=0; i<g->n; i++) */
  /* 		for (j=0; j<g->n; j++) { */
  /* 			if (route_path[i][j] != -1) */
  /* 				route_path[i][j] = next_hop(i,j); */
  /* 		} */
	
	
	
  /* 	print_connectivity_matrix (g->n, route_dist); */
  /* 	print_connectivity_matrix (g->n, route_path); */
	
	
  /* 	{ */
  /* 		int s = 6, d=16; */
	
  /* 		c_printf (DEBUG, "route from %d to %d:\n", s, d); */
  /* 		print_route (s,d); */
  /* 		c_printf (DEBUG, "%d\n", d); */
  /* 		c_printf (DEBUG, "next hop from %d to %d: %d\n", 1, 16, */
  /* 						next_hop(1, 16)); */
	
  /* 	} */
	
	
  /* 	c_printf (DEBUG, "\n"); */
  return diam;
	
} /* create_routing_table */


/*
boolean save_route_table (char *f, Graph *g, long **t)
{
  int fd;
  int i, j;
  char graph_name[MAX_NODE_NAME_SIZE];
	
		
  if ((fd=open (f, O_CREAT|O_TRUNC|O_WRONLY, 0666))==-1){
    panic ("save_route_table: open");
  }

  strcpy (graph_name, g->id);
  if (write (fd, graph_name, MAX_NODE_NAME_SIZE)!=MAX_NODE_NAME_SIZE)
  {
    panic ("Could not write graph name\n");
  }
  for (i=0; i < g->n; i++){
    for (j=0; j < g->n; j++){
      if (write (fd, &t[i][j], sizeof(long))!=sizeof(long)){
	c_printf (ALWAYS, "error writing path[%d][%d]\n", i, j);
	panic  ("save_route_table: write");
      }
    }
  }
  close(fd);
}

boolean get_route_table(Graph *Topology, char *RT_FILE_NAME, char *GR_FILE_NAME)
{
  int i, j;
  int fd;
  char graph_name[MAX_NODE_NAME_SIZE];
	
  strcpy (RT_FILE_NAME, GR_FILE_NAME);
  strcat (RT_FILE_NAME, RT_SUFFIX);

  if ((fd=open(RT_FILE_NAME, O_RDONLY))==-1){
    c_printf (ALWAYS, "Could not open file %s\n", RT_FILE_NAME);
    return FALSE;
  }

  allocate_route_table (Topology);
  if (read (fd, graph_name, MAX_NODE_NAME_SIZE)!=MAX_NODE_NAME_SIZE)
  {
    c_printf (ALWAYS, "Could not read graph name\n");
    return FALSE;
  }
  if (strcmp(graph_name, Topology->id)){
    c_printf (ALWAYS, "Graph Id mismatch,\n f <%s>\n t <%s> \n",
	      graph_name, Topology->id);
    return FALSE;
  }
  for (i=0; i < Topology->n; i++){
    for (j=0; j < Topology->n; j++){
      if (read (fd, &route_lpath[i][j], sizeof(long))!= sizeof(long)) {
	c_printf (ALWAYS, "Could not read path[%d][%d]\n", i, j);
	return FALSE;
      }
    }
  }
  close(fd);
  return TRUE;
}
*/