tsrt.c

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

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

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

#include <assert.h>

#include <tsrt.h>
#include "gb_basic.h"

#define MAX_NODE_NAME_SIZE	255

#define other_graph u.I
#define other_node v.I 
#define gateway_graph w.I 
#define gateway_node x.I 
#define gateway_cost y.I 

int get_num_domains ( Graph *g );
int is_transit_node (Graph *g, int v);

void get_domain_graph_list (Graph * g, Graph ** g_list);  
char * get_domain_name (Vertex v); 
int get_next_hop(int i, int j); 
int get_cost(int i, int j); 
/*
extern Graph * restore_graph (char * path);
extern Graph * induced(Graph *, char *, long, long, long); 
*/
/* extern "C" Graph * induced(); */
extern "C" Graph * induced(Graph *, char *, long, long, long);

extern long create_routing_table (Graph *g);

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

long *** route_lpaths; 
long *** route_ldists; 
  
Graph * g, ** g_list; 

void create_domain_routes () {

  Arc *ap;
  int i,j,num_doms,transit_graph; 

  num_doms = get_num_domains(g); 
  g_list = (Graph **) malloc(sizeof(Graph *) * num_doms);
  get_domain_graph_list (g,g_list); 
  
  route_lpaths = (long ***) malloc(sizeof(long **) * num_doms); 
  route_ldists = (long ***) malloc(sizeof(long **) * num_doms); 
  for (i = 0; i < num_doms; i++) {
    create_routing_table(g_list[i]);
    route_lpaths[i] = route_lpath; 
    route_ldists[i] = route_ldist; 
  }

  for (i = 0; i < g->n; i++) {
    if (is_transit_node(g,i)) {
      transit_graph = g->vertices[i].other_graph;
      g_list[transit_graph]->vertices[g->vertices[i].other_node].gateway_graph = transit_graph; 
      g_list[transit_graph]->vertices[g->vertices[i].other_node].gateway_node = g->vertices[i].other_node; 
      for (ap = g->vertices[i].arcs; ap; ap=ap->next) {
        if (! is_transit_node(g,ap->tip - g->vertices)) {
	  g_list[ap->tip->other_graph]->vertices[ap->tip->other_node].gateway_graph = transit_graph; 
	  g_list[ap->tip->other_graph]->vertices[ap->tip->other_node].gateway_node = g->vertices[i].other_node; 
	  g_list[ap->tip->other_graph]->vertices[ap->tip->other_node].gateway_cost = ap->len;
          for (j = 0; j < g_list[ap->tip->other_graph]->n; j++) {
            if (j != (int)ap->tip->other_node) {
 	      g_list[ap->tip->other_graph]->vertices[j].gateway_graph = ap->tip->other_graph;
	      g_list[ap->tip->other_graph]->vertices[j].gateway_node = ap->tip->other_node; 
 	      g_list[ap->tip->other_graph]->vertices[j].gateway_cost = route_ldists[ap->tip->other_graph][j][ap->tip->other_node]; 
	    }
	  }
	}
      }
    }
  }
    
  // These were for checking only ... creates the entire routing table
  // create_routing_table(g);
  //
  // for (i = 0; i < g->n; i++) {
  //   for (j = 0; j < g->n; j++) {
  //     assert(get_cost(i,j) == route_ldist[i][j]);
  //   }
  // }
  
  /*
  long a,b,c,d,e,f; 

  for (i = 0; i < g->n; i++) {
    for (j = 0; j < g->n; j++) {
      if (get_next_hop(i,j) != next_hop(i,j)) {
        printf("alternate routes for %d,%d\n",i,j);
        a = i; 
        printf("my    route: %d--",a);
        while (a != j) {
          a = get_next_hop(a,j); 
          printf("%d--",a);
        }
        a = i; 
        b = 0; 
        printf("\nmy    route: %ld--",b);
        while (a != j) {
          b = get_cost(a,get_next_hop(a,j));
          a = get_next_hop(a,j); 
          printf("%ld--",b);
        }
        b = get_cost(i,j); 
        printf(": our cost: %ld \n",b); 
        a = i; 
        printf("their route: %d--",a);
        while (a != j) {
          a = route_lpath[a][j]; 
          printf("%d--",a);
        }
        a = i; 
        b = 0; 
        printf("\ntheir route: %ld--",b);
        while (a != j) {
          b = route_ldist[a][route_lpath[a][j]];
          a = route_lpath[a][j];
          printf("%ld--",b);
        }
        b = route_ldist[i][j]; 
        printf(": their cost: %ld \n",b); 
      } 
    }
  }
  */

  return;     
}


void get_domain_graph_list (Graph *g, Graph ** g_list) {

  int i,j,k,nodes_so_far = 0,graph_num=0;
  char * name = (char *) malloc(MAX_NODE_NAME_SIZE), *c, hash[] = "#";
  Arc * ta, * na, * pa, * ca, * ga; 
  
  bzero(name,MAX_NODE_NAME_SIZE);

  for (i = 0; i < g->n; i++) {
    sprintf(name,"%s#%d",g->vertices[i].name,i);
    g->vertices[i].name = (char *)malloc(MAX_NODE_NAME_SIZE);
    sprintf(g->vertices[i].name,"%s",name);
    g->vertices[i].u.I = 0;
  }
 
  bzero(name,MAX_NODE_NAME_SIZE);
  while (nodes_so_far < g->n) {
    i = 0; 
    while (g->vertices[i].u.I == 1) {
      g->vertices[i].z.I = 0;
      i++;
    }
    assert (i < g->n);
    strncpy(name, get_domain_name(g->vertices[i]), MAX_NODE_NAME_SIZE);
    for (j = i; j < g->n; j++) {
      if (strncmp(name, get_domain_name(g->vertices[j]), MAX_NODE_NAME_SIZE) == 0) {
        g->vertices[j].z.I = 1; 
        nodes_so_far ++;
        g->vertices[j].u.I = 1;
      }
      else 
        g->vertices[j].z.I = 0; 
    }
    g_list[graph_num] = induced(g,NULL,0,0,1);
    graph_num ++; 
  }

  for (i = 0; i < graph_num; i++) {
    for (j = 0; j < g_list[i]->n; j++) {
      c = strstr(g_list[i]->vertices[j].name, hash);
      strcpy(name, c+1); 
      g->vertices[atoi(name)].other_graph = i; 
      g->vertices[atoi(name)].other_node = j; 
      g_list[i]->vertices[j].other_node = atol(name);
    }
  }
 
  /*
  for (i = 0; i < graph_num; i++) {
    for (j = 0; j < g_list[i]->n; j++) {
      printf("edges for %d, %d: ",i,j);
      for (ta = g_list[i]->vertices[j].arcs; ta; ta = ta->next) {
        printf("%d ",ta->tip->other_node);
      }
      printf("\n");
    }
    printf("\n\n");
  }
  

  for (i = 0; i < graph_num; i++) {
    for (j = 0; j < g_list[i]->n; j++) {
      printf("edges for %d,%d : ",i,j);
      k = g_list[i]->vertices[j].other_node; 
      strncpy(name, get_domain_name(g->vertices[k]), MAX_NODE_NAME_SIZE);
      for (ga = g->vertices[k].arcs; ga; ga = ga->next) {
        if (strncmp(name, get_domain_name(* ga->tip), MAX_NODE_NAME_SIZE) == 0)
          printf("%d ",ga->tip - g->vertices);
      }
      printf("\n");
    }
    printf("\n\n");
  }

  */

  //reordering the arcs in subgraphs as per the original graph 
  for (i = 0; i < graph_num; i++) {
    for (j = 0; j < g_list[i]->n; j++) {
      k = g_list[i]->vertices[j].other_node;
      ca = g_list[i]->vertices[j].arcs; 
      pa = NULL;
      ga = g->vertices[k].arcs;
      bzero(name,MAX_NODE_NAME_SIZE);
      strncpy(name, get_domain_name(g->vertices[k]), MAX_NODE_NAME_SIZE);

      //Invariant: the list is correct from arcs to ca. 
      while (ga) {
        if (strncmp(name, get_domain_name(* ga->tip), MAX_NODE_NAME_SIZE) != 0) {
	  ga = ga->next; 
          continue; 
	}
        assert(ca);
        if (ca->tip->other_node == ga->tip - g->vertices) {
          pa = ca;
	  ca = ca->next; 
          ga = ga->next; 
	  continue; 
        }
	else {
          ta = ca; 
          for (na = ca->next; na; na = na->next) {
            if (na->tip->other_node == ga->tip - g->vertices) {
	      break; 
	    }
            else {
              ta = na; 
            }
	  }
          ta->next = na->next; 
          na->next = ca; 
          if (pa != NULL) {
            pa->next = na; 
            pa = na; 
          }
          else {
            g_list[i]->vertices[j].arcs = na;
            pa = na; 
	  }
          ga = ga->next;
        }
      }
    }
  }

  /*
  for (i = 0; i < graph_num; i++) {
    for (j = 0; j < g_list[i]->n; j++) {
      printf("edges for %d, %d: ",i,j);
      for (ta = g_list[i]->vertices[j].arcs; ta; ta = ta->next) {
        printf("%d ",ta->tip->other_node);
      }
      printf("\n");
    }
    printf("\n\n");
  }    
  */

  free(name);
  return; 
}  

int get_new_to_old (int a, int b) { 

  return g_list[a]->vertices[b].other_node; 
}


int get_next_hop (int a, int b) {

  long ua = g->vertices[a].other_graph; 
  long va = g->vertices[a].other_node;
  long wa = g_list[ua]->vertices[va].gateway_graph; 
  long xa = g_list[ua]->vertices[va].gateway_node; 
  long ub = g->vertices[b].other_graph; 
  long vb = g->vertices[b].other_node;
  long wb = g_list[ub]->vertices[vb].gateway_graph; 
  long xb = g_list[ub]->vertices[vb].gateway_node; 

//same domain 
  if (ua == ub) {
    return get_new_to_old(ua,route_lpaths[ua][va][vb]);
  }
    
//source is deep inside some stub
  if ((ua == wa) && (va != xa)) {
    return get_new_to_old(ua,route_lpaths[ua][va][xa]);
  }

//source is stub's gateway
  if (ua != wa) {
    return get_new_to_old(wa,xa);
  }

//dest is stub gateway many hops away from transit source
  if ((ub != wb) && (wb == wa) && (xb != xa)) {
    return get_new_to_old(wa,route_lpaths[wa][xa][xb]);
  }
    
//dest is stub gateway one hop away from transit source
  if ((ub != wb) && (wb == wa) && (xb == xa)) {
    return get_new_to_old(ub,vb);
  }

//source is a transit node & dest is deep inside a stub
  if ((ub == wb) && (vb != xb)) {
    return get_next_hop(a,g_list[ub]->vertices[xb].other_node); 
  }

  return -1; 
}

int get_cost (int a, int b) {

  long ua = g->vertices[a].other_graph; 
  long va = g->vertices[a].other_node;
  long wa = g_list[ua]->vertices[va].gateway_graph; 
  long xa = g_list[ua]->vertices[va].gateway_node; 
  long ub = g->vertices[b].other_graph; 
  long vb = g->vertices[b].other_node;
  // long wb = g_list[ub]->vertices[vb].gateway_graph; 
  // long xb = g_list[ub]->vertices[vb].gateway_node; 

//same domain 
  if (ua == ub) {
    return route_ldists[ua][va][vb];
  }
    
//source is deep inside some stub
  if ((ua == wa) && (va != xa)) {
    return route_ldists[ua][va][xa] + get_cost(g_list[ua]->vertices[xa].other_node, b);
  }

//source is stub's gateway
  if (ua != wa) {
    return g_list[ua]->vertices[va].gateway_cost + get_cost(g_list[wa]->vertices[xa].other_node,b);
  }

  return get_cost(b,a);

  return -1; 
}

int get_domain_degree(Vertex v) {

  char * domain_v; 
  Arc *a; 
  int degree = 0; 

  domain_v = (char *)malloc(MAX_NODE_NAME_SIZE); 
  strncpy(domain_v, get_domain_name(v), MAX_NODE_NAME_SIZE); 
  for (a = v.arcs; a != NULL; a=a->next) {
    if (strncmp(domain_v, get_domain_name(* a->tip), MAX_NODE_NAME_SIZE) == 0) 
      degree ++; 
  }
  free(domain_v);
  return degree; 

}  
    

int get_num_transit_nodes (Graph *g) {

  int i, k = 0; 

  for (i = 0; i < g->n; i++) {
    if (is_transit_node(g, i))
      k++; 
  }
  return k; 
}


int is_transit_node (Graph *g, int v) {
  return (g->vertices[v].name[0] == 'T');
}


static char pp[MAX_NODE_NAME_SIZE];

char * get_domain_name (Vertex v) { // not MT safe
  
  char * prefix = pp; 

  bzero(prefix,MAX_NODE_NAME_SIZE);

  if (v.name[0] == 'T') {
    strncpy (prefix, v.name, 1);  
  }
  
  else if (v.name[0] == 'S')
    {
      char *c;
      char dot[] = "."; 

      c = strstr (v.name, dot); // scans till the first dot
      assert (c);
      c = strstr (c+1, dot); // scans till the second dot
      assert (c);
      strncpy (prefix, v.name, (c-v.name));  // bug XXX      
      
    }  

  return prefix; 
}


int get_num_domains ( Graph *g ) {
 
  int i,doms = 0; 
  char prefix[MAX_NODE_NAME_SIZE];
  int got_transit = 0; 

  // assumes vertices are ordered by domain 
  // transit nodes can occur in any order. 
  
  
  bzero(prefix, MAX_NODE_NAME_SIZE);

  for (i = 0; i < g->n; i++) {
    if (strncmp(prefix, get_domain_name(g->vertices[i]), MAX_NODE_NAME_SIZE) != 0) {
      strncpy (prefix, get_domain_name(g->vertices[i]), MAX_NODE_NAME_SIZE);
      if (prefix[0] == 'S' || ! got_transit) 
        doms++; 
      if (prefix[0] == 'T') 
        got_transit = 1; 
    }
  }
  return doms; 
}