/* I am unsure how to account reuse of a PVC; i.e. between 2 core routers, it would cost little to increase the data volume, but the cost of creating PVC would incurr some static overhead costs. Heuristic: Allocate the 'hardest' contracts first, to put the main bearers in place first, then add the littler ones as needed. */ /* IP VPN network design costing calculator backbone_cost.c (aka bb.c) $RCSfile: backbone_cost.c,v $ $Source: /home1/horton/IBCM/IPConnect/src/backbone_cost/RCS/backbone_cost.c,v $ $Author: horton $ $Header: /home1/horton/IBCM/IPConnect/src/backbone_cost/RCS/backbone_cost.c,v 1.6 1999/10/02 23:45:14 horton Exp $ */ #include #include #include #include typedef unsigned char boole; #define infinity 1.0e10 #define start_multiplier 0.01 typedef struct _Cost { double cost; double cost_latency; double cost_jitter; double cost_pkt_loss; double cost_reliability; int cost_hops; } Cost; typedef struct _router { char * name; double use_cost; boole voice_capable; double latency; double jitter; int hops; /* additional to 1 hop */ double prob_packet_loss; double reliability; double max_pkts_per_sec; double per_route_cost; int max_routes; double oversubscription; /* use 1+over as capacity */ double x, y; /* geographic location */ double curr_pkts_per_sec; int number_routes; /* Dijkstra algorithm temporaries */ boole determined; /* whether cost determined yet*/ int upstream; /* index of closest router to source*/ double cost; Cost gst; } Router; typedef struct _phys_link { // Router * from_r; // Router * to_r; int from_r; int to_r; double use_cost; boole voice_capable; double latency; double capacity_forw; double capacity_rev; double capacity_voice_forw; double capacity_voice_rev; double oversubscription; /* use 1+over as capacity */ int hops; /* if implementation of links has hops e.g. IP4->IP6 interworking tunnel ? */ double used_forw; double used_rev; double used_voice_forw; double used_voice_rev; double jitter; double prob_packet_loss; double reliability; } Phys_Link; typedef struct _Topology { Router *nodes; Phys_Link *links; double total_cost; Cost total_gst; } Topology; typedef struct _Q2 { // Router * from_r; // Router * to_r; int from_r; int to_r; double want_forw; double want_rev; double want_voice_forw; double want_voice_rev; boole voice_wanted; double want_packets_per_sec; int routes_consumed; double max_latency; double max_jitter; int max_hops; double max_packet_loss; double min_reliability; int file_pos; } Q2; typedef struct _Costing { double per_router; double per_link; double per_link_bw; double per_link_voice_bw; double per_router_pkts_per_sec; /* forwarded */ double per_link_distance; double per_link_distance_bw; double per_link_distance_voice_bw; double per_distance_latency; double per_link_capacity_fullness; double per_link_capacity_voice_fullness; } Costing; Router def_router; Phys_Link def_Phys_Link; Q2 def_contract; Router *routers = 0; int num_routers = 0; Phys_Link *fixed_links = 0; int num_fixed = 0; Q2 *contracts = 0; int num_contracts = 0; Costing costing; Topology best_topology; double latency_cost_multiplier = start_multiplier; double jitter_cost_multiplier = start_multiplier; double pkt_loss_cost_multiplier = start_multiplier; double hop_cost_multiplier = start_multiplier; int verbose = 0; int model = 0; /* 0 = all models, 1 = loop all topologies, 2 = mesh*/ /*#define TYPEOF(x) typeof(x)*/ #define TYPEOF(x) #define REALLOC(ptr,size) (ptr) ? realloc((ptr),(size)) : malloc((size)) #define FREE(x) if(!(x)) {;} else { free(x); x = 0; } FILE *tbl = 0; boole sort_dispersion = 0; char *model_names[] = { "all-models", "all", "mesh", "prune" }; void usage(char *f) { fprintf(stderr, "Usage: %s [-verbose] [-model all|mesh|prune ] [-forward result] [-qsort] specification_file[s...]\n", f); /* specification file */ fprintf(stderr,"# comment\n"); fprintf(stderr,"default router\n"); fprintf(stderr," use_cost _float_\t\t-- aka occupancy\n"); fprintf(stderr," voice_capable Y | T | N | F\n"); fprintf(stderr," latency _float_\t\t --uS\n"); fprintf(stderr," jitter _float_\t\t-- mean uS\n"); fprintf(stderr," loss _float_\t\t-- P(loss)\n"); fprintf(stderr," hops _int_\t\t-- extra hops\n"); fprintf(stderr," reliability _float_\t\t-- \n"); fprintf(stderr," oversubscription _float_\t\t-- difference from 1\n"); fprintf(stderr," max_pkts_per_sec _float_\n"); fprintf(stderr," per_route_cost _float_\n"); fprintf(stderr," max_routes _int_\n"); fprintf(stderr,"end\n"); fprintf(stderr,"\n"); fprintf(stderr,"default link\n"); fprintf(stderr," use_cost _float_\t\t-- aka occupancy\n"); fprintf(stderr," voice_capable Y | T | N | F\n"); fprintf(stderr," latency _float_\t\t-- uS\n"); fprintf(stderr," jitter _float_\t\t-- mean uS\n"); fprintf(stderr," loss _float_\t\t-- P(loss)\n"); fprintf(stderr," hops _int_\t\t-- extra hops\n"); fprintf(stderr," reliability _float_\t\t-- \n"); fprintf(stderr," oversubscription _float_\t\t-- difference from 1\n"); fprintf(stderr," capacity _float_\t\t-- kBPS forward = reverse\n"); fprintf(stderr," voice_capacity _float_\t\t-- kBPS forward = reverse\n"); fprintf(stderr,"end\n"); fprintf(stderr," \n"); fprintf(stderr,"router\n"); fprintf(stderr," name _name_\n"); fprintf(stderr," use_cost _float_\t\t-- aka occupancy\n"); fprintf(stderr," voice_capable Y | T | N | F\n"); fprintf(stderr," latency _float_\n"); fprintf(stderr," jitter _float_\t\t-- mean uS\n"); fprintf(stderr," loss _float_\t\t-- P(loss)\n"); fprintf(stderr," hops _int_\t\t-- extra hops\n"); fprintf(stderr," reliability _float_\t\t-- \n"); fprintf(stderr," oversubscription _float_\t\t-- difference from 1\n"); fprintf(stderr," max_pkts_per_sec _float_\n"); fprintf(stderr," per_route_cost _float_\n"); fprintf(stderr," max_routes _int_\n"); fprintf(stderr," location x_pos y_pos\n"); fprintf(stderr,"end\n"); fprintf(stderr,"\n"); fprintf(stderr,"link\n"); fprintf(stderr," from _router_name_ to _router_name_\n"); fprintf(stderr," use_cost _float_\t\t-- aka occupancy\n"); fprintf(stderr," voice_capable Y | T | N | F\n"); fprintf(stderr," latency _float_\t\t-- uS\n"); fprintf(stderr," jitter _float_\t\t-- mean uS\n"); fprintf(stderr," loss _float_\t\t-- P(loss)\n"); fprintf(stderr," hops _int_\t\t-- extra hops\n"); fprintf(stderr," reliability _float_\t\t-- \n"); fprintf(stderr," oversubscription _float_\t\t-- difference from 1\n"); fprintf(stderr," capacity forward_float reverse_float\n"); fprintf(stderr," voice_capacity forward_float reverse_float\n"); fprintf(stderr,"end\n"); fprintf(stderr,"\n"); fprintf(stderr,"contract\n"); fprintf(stderr," from _router_name_ to _router_name_\n"); fprintf(stderr," voice Y | T | N | F -- default is data (i.e. not voice)\n"); fprintf(stderr," packets_per_second _float_\n"); fprintf(stderr," max_latency _float_\n"); fprintf(stderr," max_jitter _float_\t\t-- mean uS\n"); fprintf(stderr," max_loss _float_\t\t-- P(loss)\n"); fprintf(stderr," max_hops _int_\t\t-- extra hops\n"); fprintf(stderr," min_reliability _float_\t\t-- \n"); fprintf(stderr," capacity forward_float reverse_float\n"); fprintf(stderr," routes _int_\t\t-- #attached customer subnets default 2\n"); fprintf(stderr,"end\n"); fprintf(stderr,"\n"); fprintf(stderr,"cost\n"); fprintf(stderr," router\t\t_float_\n"); fprintf(stderr," link\t\t_float_\n"); fprintf(stderr," link_bw\t\t_float_\n"); fprintf(stderr," link_voice_bw\t\t_float_\n"); fprintf(stderr," router_pkts_per_sec\t\t_float_\n"); fprintf(stderr," link_distance\t\t_float_\n"); fprintf(stderr," link_distance_bw\t\t_float_\n"); fprintf(stderr," link_distance_voice_bw\t\t_float_\n"); fprintf(stderr," distance_latency\t\t_float_\n"); fprintf(stderr," link_capacity_fullness\t\t_float_\n"); fprintf(stderr," link_capacity_voice_fullness\t\t_float_\n"); fprintf(stderr,"end\n"); } int curr_line; char *curr_file = 0; double qcost1(Q2 *q) { return ((q->want_forw + q->want_rev + q->want_voice_forw +q->want_voice_rev) * (costing.per_link_bw + 0.000001)) + ((q->want_voice_forw + q->want_voice_rev) * (costing.per_link_voice_bw + 0.000001)) + (q->routes_consumed * (costing.per_router + 0.000001)) + (costing.per_distance_latency/q->max_latency); } int qcost(const void *v1, const void *v2) { Q2 *q1 = (Q2 *) v1; Q2 *q2 = (Q2 *) v2; double c1 = infinity, c2 = infinity; if (q1) c1 = qcost1(q1); if (q2) c2 = qcost1(q2); if (c1 < c2) return (-1); if (c1 > c2) return (1); return (0); } void Cost_add(Cost *to, Cost *plus) { if (!to || !plus) return; to->cost += plus->cost; to->cost_latency += plus->cost_latency; to->cost_jitter = sqrt(to->cost_jitter*to->cost_jitter + plus->cost_jitter*plus->cost_jitter); to->cost_pkt_loss = 1 - ( 1-to->cost_pkt_loss) * ( 1 - plus->cost_pkt_loss); to->cost_hops += plus->cost_hops; } int parse_costing(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; int keys; int errors = 0; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "router"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_router, rest); } else if ( 0 == (strcasecmp(keyword, "link"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link, rest); } else if ( 0 == (strcasecmp(keyword, "link_bw"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_bw, rest); } else if ( 0 == (strcasecmp(keyword, "link_voice_bw"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_voice_bw, rest); } else if ( 0 == (strcasecmp(keyword, "router_pkts_per_sec"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_router_pkts_per_sec, rest); } else if ( 0 == (strcasecmp(keyword, "link_distance"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_distance, rest); } else if ( 0 == (strcasecmp(keyword, "link_distance_bw"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_distance_bw, rest); } else if ( 0 == (strcasecmp(keyword, "link_distance_voice_bw"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_distance_voice_bw, rest); } else if ( 0 == (strcasecmp(keyword, "distance_latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_distance_latency, rest); } else if ( 0 == (strcasecmp(keyword, "link_capacity_fullness"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_capacity_fullness, rest); } else if ( 0 == (strcasecmp(keyword, "link_capacity_voice_fullness"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &costing.per_link_capacity_voice_fullness, rest); } else { fprintf(stderr,"%s:%d: unrecognised costing keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } return errors; } int parse_def_router(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; int keys; int errors = 0; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "voice_capable"))) { if ( 0 == (strcasecmp(arg, "y"))) { def_router.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "T"))) { def_router.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "N"))) { def_router.voice_capable = 0; } else if ( 0 == (strcasecmp(arg, "F"))) { def_router.voice_capable = 0; } else { fprintf(stderr,"%s:%d: unrecognised voice_capable '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.latency, rest); } else if ( 0 == (strcasecmp(keyword, "jitter"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.jitter, rest); } else if ( 0 == (strcasecmp(keyword, "loss"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.prob_packet_loss, rest); } else if ( 0 == (strcasecmp(keyword, "hops"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &def_router.hops, rest); } else if ( 0 == (strcasecmp(keyword, "reliability"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.reliability, rest); } else if ( 0 == (strcasecmp(keyword, "oversubscription"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.oversubscription, rest); } else if ( 0 == (strcasecmp(keyword, "max_pkts_per_sec"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.max_pkts_per_sec, rest); } else if ( 0 == (strcasecmp(keyword, "per_route_cost"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.per_route_cost, rest); } else if ( 0 == (strcasecmp(keyword, "max_routes"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &def_router.max_routes, rest); } else if ( 0 == (strcasecmp(keyword, "use_cost"))) { if (0 == strcasecmp(arg, "infinity")) { def_router.use_cost = infinity; } else { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_router.use_cost, rest); } } else { fprintf(stderr,"%s:%d: unrecognised default router keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } return errors; } int parse_def_link(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; int keys; int errors = 0; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "voice_capable"))) { if ( 0 == (strcasecmp(arg, "y"))) { def_Phys_Link.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "T"))) { def_Phys_Link.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "N"))) { def_Phys_Link.voice_capable = 0; } else if ( 0 == (strcasecmp(arg, "F"))) { def_Phys_Link.voice_capable = 0; } else { fprintf(stderr,"%s:%d: unrecognised voice_capable '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.latency, rest); } else if ( 0 == (strcasecmp(keyword, "jitter"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.jitter, rest); } else if ( 0 == (strcasecmp(keyword, "loss"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.prob_packet_loss, rest); } else if ( 0 == (strcasecmp(keyword, "reliability"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.reliability, rest); } else if ( 0 == (strcasecmp(keyword, "oversubscription"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.oversubscription, rest); } else if ( 0 == (strcasecmp(keyword, "capacity"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.capacity_forw, rest); def_Phys_Link.capacity_rev = def_Phys_Link.capacity_forw; } else if ( 0 == (strcasecmp(keyword, "voice_capacity"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.capacity_voice_forw, rest); def_Phys_Link.capacity_voice_rev = def_Phys_Link.capacity_voice_forw; } else if ( 0 == (strcasecmp(keyword, "use_cost"))) { if (0 == strcasecmp(arg, "infinity")) { def_Phys_Link.use_cost = infinity; } else { keys = sscanf(buf, "%s%lf%s\n", keyword, &def_Phys_Link.use_cost, rest); } } else { fprintf(stderr,"%s:%d: unrecognised default link keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } return errors; } int parse_router(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; int keys; int errors = 0; Router router = def_router; if (fixed_links) { fprintf(stderr,"%s:%d: Cannot add routers after specifying physical links -- '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } /* bug - can't do subsequent changes to router spec */ while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "name"))) { router.name = strdup(arg); } else if ( 0 == (strcasecmp(keyword, "voice_capable"))) { if ( 0 == (strcasecmp(arg, "y"))) { router.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "T"))) { router.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "N"))) { router.voice_capable = 0; } else if ( 0 == (strcasecmp(arg, "F"))) { router.voice_capable = 0; } else { fprintf(stderr,"%s:%d: unrecognised voice_capable '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.latency, rest); } else if ( 0 == (strcasecmp(keyword, "jitter"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.jitter, rest); } else if ( 0 == (strcasecmp(keyword, "loss"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.prob_packet_loss, rest); } else if ( 0 == (strcasecmp(keyword, "hops"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &router.hops, rest); } else if ( 0 == (strcasecmp(keyword, "reliability"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.reliability, rest); } else if ( 0 == (strcasecmp(keyword, "oversubscription"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.oversubscription, rest); } else if ( 0 == (strcasecmp(keyword, "max_pkts_per_sec"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.max_pkts_per_sec, rest); } else if ( 0 == (strcasecmp(keyword, "per_route_cost"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.per_route_cost, rest); } else if ( 0 == (strcasecmp(keyword, "max_routes"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &router.max_routes, rest); } else if ( 0 == (strcasecmp(keyword, "use_cost"))) { if (0 == strcasecmp(arg, "infinity")) { router.use_cost = infinity; } else { keys = sscanf(buf, "%s%lf%s\n", keyword, &router.use_cost, rest); } } else if ( 0 == (strcasecmp(keyword, "location"))) { keys = sscanf(buf, "%s%lf%lf%s\n", keyword, &router.x, &router.y, rest); } else { fprintf(stderr,"%s:%d: unrecognised router keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } if (!errors) { routers = (Router *) (REALLOC( (void *)routers, (num_routers+1) * sizeof(Router))); routers[num_routers++] = router; } return errors; } int parse_link(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; char fr_k[100], to_k[100], from_r[100], to_r[100]; int keys; int errors = 0; Phys_Link link, link_2; link.from_r = link.to_r = -1; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "from"))) { keys = sscanf(buf, "%s%s%s%s\n", fr_k, from_r, to_k, to_r); for (link.from_r = num_routers-1; link.from_r > 0; link.from_r --) { if (0 == strcasecmp(from_r, routers[link.from_r].name)) break; } for (link.to_r = num_routers-1; link.to_r > 0; link.to_r --) { if (0 == strcasecmp(to_r, routers[link.to_r].name)) break; } if ((link.from_r == -1) || (link.to_r == -1)) { fprintf(stderr,"%s:%d: couldn't find routers from (%d)'%s' to (%d)'%s", curr_file, curr_line, link.from_r, from_r, link.to_r, to_r); errors += 1; continue; } link_2 = link; if ((fixed_links) && (fixed_links[link.from_r*num_routers+link.to_r].from_r != -1)) { link = fixed_links[link.from_r*num_routers+link.to_r]; } else { link = def_Phys_Link; } link.from_r = link_2.from_r; link.to_r = link_2.to_r; } else if ( 0 == (strcasecmp(keyword, "voice_capable"))) { if ( 0 == (strcasecmp(arg, "y"))) { link.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "T"))) { link.voice_capable = 'Y'; } else if ( 0 == (strcasecmp(arg, "N"))) { link.voice_capable = 0; } else if ( 0 == (strcasecmp(arg, "F"))) { link.voice_capable = 0; } else { fprintf(stderr,"%s:%d: unrecognised voice_capable '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.latency, rest); } else if ( 0 == (strcasecmp(keyword, "jitter"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.jitter, rest); } else if ( 0 == (strcasecmp(keyword, "loss"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.prob_packet_loss, rest); } else if ( 0 == (strcasecmp(keyword, "hops"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &link.hops, rest); } else if ( 0 == (strcasecmp(keyword, "reliability"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.reliability, rest); } else if ( 0 == (strcasecmp(keyword, "oversubscription"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.oversubscription, rest); } else if ( 0 == (strcasecmp(keyword, "use_cost"))) { if (0 == strcasecmp(arg, "infinity")) { link.use_cost = infinity; } else { keys = sscanf(buf, "%s%lf%s\n", keyword, &link.use_cost, rest); } } else if ( 0 == (strcasecmp(keyword, "capacity"))) { keys = sscanf(buf, "%s%lf%lf%s\n", keyword, &link.capacity_forw, &link.capacity_rev, rest); } else if ( 0 == (strcasecmp(keyword, "voice_capacity"))) { keys = sscanf(buf, "%s%lf%lf%s\n", keyword, &link.capacity_voice_forw, &link.capacity_voice_rev, rest); } else { fprintf(stderr, "%s:%d: unrecognised link keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } if (!errors) { if (! fixed_links) { int i, j; fixed_links = (Phys_Link *) (REALLOC( (void *)fixed_links, (num_routers*num_routers) * sizeof(Phys_Link))); for (i = 0; i < num_routers; i++) { for (j = 0; j < num_routers; j++) { fixed_links[i*num_routers+j].from_r = -1; fixed_links[i*num_routers+j].to_r = -1; } } } } if ((link.from_r == -1) || (link.to_r == -1)) { fprintf(stderr,"%s:%d: no FROM clause in link\n", curr_file, curr_line); errors += 1; return errors; } fixed_links[link.from_r*num_routers+link.to_r] = link; link_2 = link; link_2.from_r = link.to_r; link_2.to_r = link.from_r; link_2.capacity_forw = link.capacity_rev; link_2.capacity_rev = link.capacity_forw; link_2.capacity_voice_forw = link.capacity_voice_rev; link_2.capacity_voice_rev = link.capacity_voice_forw; fixed_links[link_2.from_r*num_routers+link_2.to_r] = link_2; return errors; } int parse_contract(FILE *f) { char buf[1000]; char keyword[100], arg[100], fill[100], arg2[100], rest[100]; int keys; int errors = 0; int r; Q2 contract = def_contract; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; fill[0] = 0; arg2[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s%s%s\n", keyword, arg, fill, arg2, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "end"))) { break; } else if ( 0 == (strcasecmp(keyword, "from"))) { if (strlen(arg) == 0) { fprintf(stderr,"%s:%d: missing from node '%s", curr_file, curr_line, buf); errors += 1; continue; } for (r = 0; r < num_routers; r++) { if (0 == strcasecmp(routers[r].name, arg)) { contract.from_r = r; break; } } if (r >= num_routers) { fprintf(stderr,"%s:%d: undefined from node '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; continue; } if (strlen(arg2) == 0) { fprintf(stderr,"%s:%d: missing to node '%s", curr_file, curr_line, buf); errors += 1; continue; } for (r = 0; r < num_routers; r++) { if (0 == strcasecmp(routers[r].name, arg2)) { contract.to_r = r; break; } } if (r >= num_routers) { fprintf(stderr,"%s:%d: undefined to node '%s' in '%s", curr_file, curr_line, arg2, buf); errors += 1; continue; } } else if ( 0 == (strcasecmp(keyword, "voice"))) { if ( 0 == (strcasecmp(arg, "y"))) { contract.voice_wanted = 'Y'; } else if ( 0 == (strcasecmp(arg, "T"))) { contract.voice_wanted = 'Y'; } else if ( 0 == (strcasecmp(arg, "N"))) { contract.voice_wanted = 0; } else if ( 0 == (strcasecmp(arg, "F"))) { contract.voice_wanted = 0; } else { fprintf(stderr,"%s:%d: unrecognised voice '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "max_latency"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &contract.max_latency, rest); } else if ( 0 == (strcasecmp(keyword, "max_jitter"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &contract.max_jitter, rest); } else if ( 0 == (strcasecmp(keyword, "max_loss"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &contract.max_packet_loss, rest); } else if ( 0 == (strcasecmp(keyword, "max_hops"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &contract.max_hops, rest); } else if ( 0 == (strcasecmp(keyword, "min_reliability"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &contract.min_reliability, rest); } else if ( 0 == (strcasecmp(keyword, "capacity"))) { if(contract.voice_wanted) { keys = sscanf(buf, "%s%lf%lf%s\n", keyword, &contract.want_voice_forw, &contract.want_voice_rev, rest); } else { keys = sscanf(buf, "%s%lf%lf%s\n", keyword, &contract.want_forw, &contract.want_rev, rest); } } else if ( 0 == (strcasecmp(keyword, "routes"))) { keys = sscanf(buf, "%s%d%s\n", keyword, &contract.routes_consumed, rest); } else if ( 0 == (strcasecmp(keyword, "packets_per_second"))) { keys = sscanf(buf, "%s%lf%s\n", keyword, &contract.want_packets_per_sec, rest); } else { fprintf(stderr,"%s:%d: unrecognised contract keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } if ((contract.from_r == -1) || (contract.to_r == -1)) { fprintf(stderr,"%s:%d: missing contract endpoints in '%s", curr_file, curr_line, buf); errors += 1; } if (!errors) { contracts = (Q2 *) (REALLOC( (void *)contracts, (num_contracts+1) * sizeof(Q2))); contract.file_pos = num_contracts+1; contracts[num_contracts++] = contract; } return errors; } int parse_file(FILE *f) { char buf[1000]; char keyword[100], arg[100], rest[100]; int keys; int errors = 0; while(fgets(buf, sizeof(buf), f)) { curr_line += 1; keys = strlen(buf); if (keys <= 1) continue; keyword[0] = 0; arg[0] = 0; rest[0] = 0; keys = sscanf(buf, "%s%s%s\n", keyword, arg, rest); if ( 0 == (strcasecmp(keyword, "#"))) { /* comment */ continue; } else if ( 0 == (strcasecmp(keyword, "default"))) { if ( 0 == (strcasecmp(arg, "router"))) { errors += parse_def_router(f); } else if ( 0 == (strcasecmp(arg, "link"))) { errors += parse_def_link(f); } else { fprintf(stderr,"%s:%d: unrecognised default '%s' in '%s", curr_file, curr_line, arg, buf); errors += 1; } } else if ( 0 == (strcasecmp(keyword, "router"))) { errors += parse_router(f); } else if ( 0 == (strcasecmp(keyword, "cost"))) { errors += parse_costing(f); } else if ( 0 == (strcasecmp(keyword, "link"))) { errors += parse_link(f); } else if ( 0 == (strcasecmp(keyword, "contract"))) { errors += parse_contract(f); } else { fprintf(stderr,"%s:%d: unrecognised keyword '%s' in '%s", curr_file, curr_line, keyword, buf); errors += 1; } } return errors; } int parse_spec(char *fname) { FILE *f = 0; curr_line = 0; f = fopen(fname, "r"); if (f) { curr_file = fname; parse_file(f); fclose(f); } else { perror(fname); } return 0; } /* missing latency, link/router loading accumulation */ double charge( int from_r, int to_r, Q2 *q2, Router *rs, Phys_Link *ls, int dir, Cost *gst) { double d = 0; double dist; Cost gst_d; if (verbose > 2) printf("Q(%d '%s'->%d '%s' ++ hop %d'%s'->%d'%s'\n", q2->from_r, rs[q2->from_r].name, q2->to_r, rs[q2->to_r].name, from_r, rs[from_r].name, to_r, rs[to_r].name); if (!gst) gst = &gst_d; /* ensure there is a placeholder */ memset(gst, 0, sizeof(Cost)); /* check if this exceeds capacities */ if (rs[(dir==0) ? from_r : to_r].max_pkts_per_sec* (1+rs[(dir==0) ? from_r : to_r].oversubscription) < rs[(dir==0) ? from_r : to_r].curr_pkts_per_sec + q2->want_packets_per_sec) { if (verbose) printf("Router[%d](%s) would exceed forwarding rate %f/%f\n", (dir==0) ? from_r : to_r, rs[(dir==0) ? from_r : to_r].name, rs[(dir==0) ? from_r : to_r].curr_pkts_per_sec , q2->want_packets_per_sec); return infinity; } if ((ls[from_r*num_routers+to_r].used_forw + q2->want_forw) > (ls[from_r*num_routers+to_r].capacity_forw* (1+ls[from_r*num_routers+to_r].oversubscription))) { if (verbose) printf("link[%d->%d] would exceed forward capacity %f/%f\n", from_r, to_r, ls[from_r*num_routers+to_r].capacity_forw, q2->want_forw); return infinity; } if ((ls[from_r*num_routers+to_r].used_rev + q2->want_rev) > (ls[from_r*num_routers+to_r].capacity_rev* (1+ls[from_r*num_routers+to_r].oversubscription))) { if (verbose) printf("link[%d->%d] would exceed reverse capacity %f/%f\n", from_r, to_r, ls[from_r*num_routers+to_r].capacity_rev, q2->want_rev); return infinity; } /* Check that features (well voice is only feature) supported */ if (q2->voice_wanted) { if( ! rs[from_r].voice_capable) { if (verbose > 1) printf("Router[%d]%s not voice capable\n", from_r, rs[from_r].name); return infinity; } if( ! rs[to_r].voice_capable) { if (verbose > 1) printf("Router[%d]%s not voice capable\n", to_r, rs[to_r].name); return infinity; } if( ! ls[from_r*num_routers+to_r].voice_capable) { if (verbose > 1) printf("link %d->%d not voice capable\n", from_r, to_r); return infinity; } } /* per router charged on leaving the 'from' router */ d += costing.per_router * rs[(dir==0) ? from_r : to_r].use_cost; gst->cost_latency += rs[(dir==0) ? from_r : to_r].latency; gst->cost_jitter = sqrt( (gst->cost_jitter*gst->cost_jitter) + (rs[(dir==0) ? from_r : to_r].jitter* rs[(dir==0) ? from_r : to_r].jitter)); gst->cost_pkt_loss = 1 - ((1 - gst->cost_pkt_loss) * (1 - rs[(dir==0) ? from_r : to_r].prob_packet_loss)); gst->cost_hops += 1 + rs[(dir==0) ? from_r : to_r].hops; d += costing.per_router_pkts_per_sec * q2->want_packets_per_sec; /* per link charge */ /* charged if this requires a new VC setup */ if ((ls[from_r*num_routers+to_r].used_forw == 0) && (ls[from_r*num_routers+to_r].used_rev == 0) ) { d += costing.per_link * ls[from_r*num_routers+to_r].use_cost; } /* per link bandwidth charge ??? I don't have the charging scale right here*/ d += costing.per_link_bw * q2->want_forw; /* * link rate */ /* distance charge */ dist = sqrt( (rs[from_r].x - rs[to_r].x) * (rs[from_r].x - rs[to_r].x) + (rs[from_r].y - rs[to_r].y) * (rs[from_r].y - rs[to_r].y) ); d += costing.per_link_distance * dist; /* * per link charge */ d += costing.per_link_distance_bw * dist * ((dir==0) ? q2->want_forw : q2->want_rev); /* * per link charge */ gst->cost_latency += ls[from_r*num_routers+to_r].latency; gst->cost_jitter = sqrt( (gst->cost_jitter*gst->cost_jitter) + (ls[from_r*num_routers+to_r].jitter* ls[from_r*num_routers+to_r].jitter)); gst->cost_pkt_loss = 1 - ((1 - gst->cost_pkt_loss) * (1 - ls[from_r*num_routers+to_r].prob_packet_loss)); d += gst->cost_latency * latency_cost_multiplier; d += gst->cost_jitter * jitter_cost_multiplier; d += gst->cost_pkt_loss * pkt_loss_cost_multiplier; d += gst->cost_hops * hop_cost_multiplier; gst->cost = d; return d; } void evaluate(char *matrix) { int from_r, to_r; Router *test_routers = 0; Phys_Link *test_topology = 0; Topology this_topology; int c, r, s, t, u, d; double cost; Cost gst; Cost contract_sla; test_routers = (Router *) malloc(num_routers * sizeof(Router)); memcpy(test_routers, routers,num_routers * sizeof(Router)); test_topology = (Phys_Link *) malloc(num_routers * num_routers * sizeof(Phys_Link)); for (from_r = 0; from_r < num_routers; from_r++) { for (to_r = 0; to_r < num_routers; to_r++) { test_topology[from_r*num_routers+to_r].from_r = -1; test_topology[from_r*num_routers+to_r].to_r = -1; } } for (from_r = 0; from_r < num_routers; from_r++) { for (to_r = 0; to_r < num_routers; to_r++) { if (matrix[from_r*num_routers+to_r]) { if(verbose) printf(" %d->%d", from_r, to_r); /* see if there is a specific link definition else */ if ( fixed_links && (fixed_links[from_r*num_routers+to_r].from_r != -1) && (fixed_links[from_r*num_routers+to_r].to_r != -1)) { test_topology[from_r*num_routers+to_r] = fixed_links[from_r*num_routers+to_r]; if(verbose>1) printf("+"); } else { test_topology[from_r*num_routers+to_r] = def_Phys_Link; test_topology[to_r*num_routers+from_r] = def_Phys_Link; test_topology[from_r*num_routers+to_r].from_r = from_r; test_topology[from_r*num_routers+to_r].to_r = to_r; test_topology[to_r*num_routers+from_r].from_r = to_r; test_topology[to_r*num_routers+from_r].to_r = from_r; } } } } if(verbose) printf("\n"); this_topology.nodes = test_routers; this_topology.links = test_topology; this_topology.total_cost = 0; memset(&this_topology.total_gst, 0, sizeof(this_topology.total_gst)); /* for each contract calculate best route through add in cost to total cost if cost is infinite, break if this isn't the best network so far { FREE(test_routers); FREE(test_topology); } */ for (c = 0; c < num_contracts; c++) { for (d = 0; d <= 1; d++) { /* forward /reverse direction */ latency_cost_multiplier = start_multiplier; jitter_cost_multiplier = start_multiplier; pkt_loss_cost_multiplier = start_multiplier; hop_cost_multiplier = start_multiplier; do { /* until additional constraints jitter/latency/... satisfied */ memset(&contract_sla, 0, sizeof(contract_sla)); /* initialise single source */ for (r=0; r < num_routers; r++) { test_routers[r].determined = 0; /* in 'V' set */ test_routers[r].upstream = -1; /* no path to source */ test_routers[r].cost = infinity; memset(&test_routers[r].gst, 0, sizeof(Cost)); } if (d == 0) { test_routers[contracts[c].from_r].cost = 0; test_routers[contracts[c].from_r].upstream = contracts[c].from_r; } else { test_routers[contracts[c].to_r].cost = 0; test_routers[contracts[c].to_r].upstream = contracts[c].to_r; } do { /* pick a node - the cheapest (why I don't know) */ for (r = 0, u = -1, cost = infinity+1; r < num_routers; r++) { if ( !test_routers[r].determined && test_routers[r].cost <= cost) { u = r; cost = test_routers[r].cost; } } if (-1 == u) break; /* no remaining vertices to try */ test_routers[u].determined = 'Y'; for (t = 0; t < num_routers; t++) { /* check that topology allows this node to connect via a PVC */ if ((test_topology[u*num_routers+t].from_r != -1) && (test_topology[u*num_routers+t].to_r != -1) ) { cost = charge(u, t, &contracts[c], test_routers, test_topology, d, &gst); /* 'relax' */ if (test_routers[t].cost > (test_routers[u].cost + cost)) { test_routers[t].cost = test_routers[u].cost + cost; test_routers[t].upstream = u; test_routers[t].gst = gst; } } } } while (1); /* now extract the cost to our required destination (contracts[c].to_r) * add the cost of the hops to the routers and links providing the path * add the cost to the total for contract */ if (d == 0) { /* forward */ this_topology.total_cost += test_routers[contracts[c].to_r].cost; if(verbose) printf("Q2[%d]%d->%d: ", c, contracts[c].from_r, contracts[c].to_r); if (tbl) fprintf(stderr, "missing code to backtrack the routers in this path back to the ip routes\n"); if (test_routers[contracts[c].to_r].cost < infinity) { for(t = contracts[c].to_r; (test_routers[t].upstream!= -1)&&(test_routers[t].upstream!= t); t = test_routers[t].upstream) { if(verbose) printf(" %d <=", t); Cost_add(&contract_sla, &test_routers[t].gst); } } /* router utilization */ Cost_add(&contract_sla, &test_routers[t].gst); if(verbose) printf("@%d $ %f\n", t, test_routers[contracts[c].to_r].cost); } else { /* reverse */ this_topology.total_cost += test_routers[contracts[c].from_r].cost; if(verbose) printf("Q2[%d]%d<-%d: ", c, contracts[c].from_r, contracts[c].to_r); if (test_routers[contracts[c].from_r].cost < infinity) { for(t = contracts[c].from_r; (test_routers[t].upstream!= -1)&&(test_routers[t].upstream!= t); t = test_routers[t].upstream) { if(verbose) printf(" %d <=\n", t); Cost_add(&contract_sla, &test_routers[t].gst); } } /* router utilization */ Cost_add(&contract_sla, &test_routers[t].gst); } if(verbose) { printf("@%d $ %f ", t, test_routers[contracts[c].from_r].cost); printf("L=%f J=%f H=%d PL=%f\n", contract_sla.cost_latency, contract_sla.cost_jitter, contract_sla.cost_hops, contract_sla.cost_pkt_loss); } /* check additional constraints */ if (contract_sla.cost_latency > contracts[c].max_latency) { if(verbose)printf("Latency %f > c[%d]%f @mult=%f\n", contract_sla.cost_latency, c, contracts[c].max_latency, latency_cost_multiplier); latency_cost_multiplier *= 2; if(latency_cost_multiplier < infinity/start_multiplier) continue; } if (contract_sla.cost_jitter > contracts[c].max_jitter) { if(verbose)printf("Jitter %f > c[%d]%f @mult=%f\n", contract_sla.cost_jitter, c, contracts[c].max_jitter, jitter_cost_multiplier); jitter_cost_multiplier *= 2; if(jitter_cost_multiplier < infinity/start_multiplier) continue; } if (contract_sla.cost_pkt_loss > contracts[c].max_packet_loss) { if(verbose)printf("Loss %f > c[%d]%f @mult=%f\n", contract_sla.cost_pkt_loss, c, contracts[c].max_packet_loss, pkt_loss_cost_multiplier); pkt_loss_cost_multiplier *= 2; if(pkt_loss_cost_multiplier < infinity/start_multiplier) continue; } if (contract_sla.cost_hops > contracts[c].max_hops) { if(verbose)printf("Hops %d > c[%d]%d @mult=%f\n", contract_sla.cost_hops, c, contracts[c].max_hops, latency_cost_multiplier); hop_cost_multiplier *= 2; if(hop_cost_multiplier < infinity/start_multiplier) continue; } /* OK , we have succeeded or failed to satisfy additional constraints, and the cost indicates whether success/fail */ if (d == 0) { /* forward */ this_topology.total_cost += test_routers[contracts[c].to_r].cost; if(verbose) printf("Q2[%d]%d->%d: ", c, contracts[c].from_r, contracts[c].to_r); if (test_routers[contracts[c].to_r].cost < infinity) { for(t = contracts[c].to_r; (test_routers[t].upstream!= -1)&&(test_routers[t].upstream!= t); t = test_routers[t].upstream) { if(verbose) printf(" %d <=", t); /* router utilization */ test_routers[t].curr_pkts_per_sec += contracts[c].want_packets_per_sec; test_routers[t].number_routes += contracts[c].routes_consumed; /* link use */ test_topology[ /*from*/test_routers[t].upstream*num_routers + t]. used_forw += contracts[c].want_forw; } } /* router utilization */ test_routers[t].curr_pkts_per_sec += contracts[c].want_packets_per_sec; test_routers[t].number_routes += contracts[c].routes_consumed; if(verbose) printf("@%d $ %f\n", t, test_routers[contracts[c].to_r].cost); } else { /* reverse */ this_topology.total_cost += test_routers[contracts[c].from_r].cost; if(verbose) printf("Q2[%d]%d<-%d: ", c, contracts[c].from_r, contracts[c].to_r); if (test_routers[contracts[c].from_r].cost < infinity) { for(t = contracts[c].from_r; (test_routers[t].upstream!= -1)&&(test_routers[t].upstream!= t); t = test_routers[t].upstream) { if(verbose) printf(" %d <=", t); /* router utilization */ test_routers[t].curr_pkts_per_sec += contracts[c].want_packets_per_sec; test_routers[t].number_routes += contracts[c].routes_consumed; /* link use */ test_topology[ /*from*/test_routers[t].upstream*num_routers + t]. used_forw += contracts[c].want_rev; } } /* router utilization */ test_routers[t].curr_pkts_per_sec += contracts[c].want_packets_per_sec; test_routers[t].number_routes += contracts[c].routes_consumed; } break; } while (1); } } if(verbose) printf("Total: $ %f\n", this_topology.total_cost ); if (this_topology.total_cost < best_topology.total_cost) { FREE(best_topology.nodes); FREE(best_topology.links); best_topology.total_cost = this_topology.total_cost; best_topology.nodes = test_routers; best_topology.links = test_topology; } else { FREE(test_routers); FREE(test_topology); } if(verbose) printf("\n"); } /* recursively look at all topologies */ void corner( int from_r, int to_r, char *matrix) { int from_c, to_c; /* child to try */ char *matrix_c = 0; char sent = 0; //printf(" corner(from %d, to %d) ", from_r, to_r); //evaluate(matrix); //printf("\n"); if ((from_r == 0) && (to_r == 0) ) { /* Can't go deeper */ //printf("EVAL: "); evaluate(matrix); return; } // matrix[from_r*num_routers+to_r] = 'Y'; // evaluate(matrix); matrix_c = (char *) (malloc(num_routers*num_routers)); memcpy(matrix_c, matrix, num_routers*num_routers); for( from_c = from_r, to_c = to_r, sent = 0; !sent; ) { //printf("(%d>%d)", from_c, to_c); if ((from_c == 0) && (to_c == 0) ) { /* Can't go deeper */ corner(from_c, to_c, matrix_c); sent = 'Y'; continue; } /* find next possible router connection combination */ if(to_c == 0) { to_c = num_routers-1; from_c -= 1; } else { to_c -= 1; } if (to_c >= from_c) continue; /* only map 1/2 matrix */ /* test cases where this link is absent and present */ corner(from_c, to_c, matrix_c); //printf("[%d->%d]", from_c, to_c); matrix_c[from_c*num_routers+to_c] = 'Y'; corner(from_c, to_c, matrix_c); sent = 'Y'; } FREE(matrix_c); } void set_defs(void) { def_router.name = "unnamed"; def_router.voice_capable = 0; def_router.latency = 0; def_router.max_pkts_per_sec = infinity; def_router.per_route_cost = 0; def_router.max_routes = 0x3fffffff; def_router.x = def_router.y = 0; def_Phys_Link.from_r = def_Phys_Link.to_r = 0; def_Phys_Link.use_cost = 0; def_Phys_Link.voice_capable = 0; def_Phys_Link.latency = 0; def_Phys_Link.capacity_forw = def_Phys_Link.capacity_rev = infinity; def_Phys_Link.capacity_voice_forw = def_Phys_Link.capacity_voice_rev = infinity; memset ((void *)&costing, 0, sizeof(costing)); memset( (void*)&def_contract, 0, sizeof(def_contract)); def_contract.from_r = def_contract.to_r = -1; def_contract.max_latency = infinity; def_contract.max_jitter = infinity; def_contract.max_hops = 65535; def_contract.max_packet_loss = infinity; def_contract.min_reliability = 0; def_contract.routes_consumed = 2; } int main (int argc, char * argv[]) { int a; int from_r, to_r; char *matrix = 0; if (argc < 2) { usage(argv[0]); exit(1); } set_defs(); for (a = 1; a < argc; a++) { /* Switches */ if (0 == strcasecmp("-help", argv[a])) { usage(argv[0]); continue; } if (0 == strcasecmp("--help", argv[a])) { usage(argv[0]); continue; } if (0 == strcasecmp("-verbose", argv[a])) { verbose += 1; continue; } if (0 == strcasecmp("-v", argv[a])) { verbose += 1; continue; } if (0 == strcasecmp("-qsort", argv[a])) { sort_dispersion += 1; continue; } if(0 == strcasecmp("-model", argv[a])) { int m; a++; for (m = 0; m < sizeof(model_names)/sizeof(model_names[0]); m++) { if(0 == strcasecmp(model_names[m], argv[a])) { model = m; break; } } continue; } if(0 == strcasecmp("-forward", argv[a])) { a++; tbl = fopen(argv[a], "w"); if (!tbl) perror(argv[a]); continue; } parse_spec(argv[a]); } if (sort_dispersion) { qsort(contracts, num_contracts, sizeof(Q2), qcost); // need to go through and change all the error reports on per contract // to use file_pos } for (a = 1; a <= 2; a++ ) { best_topology.total_cost = infinity; best_topology.nodes = 0; best_topology.links = 0; /* Build all possible topologies model */ if ( (1 == a) && (( 0 == model) || (1 == model))) { for (from_r = 0; from_r < num_routers; from_r++) { for (to_r = 0; to_r < num_routers; to_r++) { if (to_r >= from_r) continue; /* only map 1/2 matrix */ matrix = (char *) (REALLOC(matrix, num_routers*num_routers)); memset(matrix, 0, num_routers*num_routers); matrix[from_r*num_routers+to_r] = 'Y'; //printf("main->corner(from %d, to %d)\n", from_r, to_r); corner(from_r, to_r, matrix); } } } if ( (2 == a) && (( 0 == model) || (2 == model))) { matrix = (char *) (REALLOC(matrix, num_routers*num_routers)); memset(matrix, 0, num_routers*num_routers); for (from_r = 0; from_r < num_routers; from_r++) { for (to_r = 0; to_r < num_routers; to_r++) { //if (to_r >= from_r) continue; /* only map 1/2 matrix */ if (to_r == from_r) continue; /* only map 1/2 matrix */ matrix[from_r*num_routers+to_r] = 'Y'; } } evaluate(matrix); } printf(" Best topology [model=%s (%d)] $ %f : \n", model_names[a], a, best_topology.total_cost); if (best_topology.nodes) { for (from_r = 0; from_r < num_routers; from_r++) { printf("[%d]'%s' %f pkts/sec, %d routes\n", from_r, best_topology.nodes[from_r].name, best_topology.nodes[from_r].curr_pkts_per_sec, best_topology.nodes[from_r].number_routes ); } } if (best_topology.links) { for (from_r = 0; from_r < num_routers; from_r++) { for (to_r = 0; to_r < num_routers; to_r++) { if (best_topology.links[from_r*num_routers+to_r].from_r != -1) { if ((0 == best_topology.links[from_r*num_routers+to_r].used_forw) && (0== best_topology.links[from_r*num_routers+to_r].used_rev)) continue; printf("%d->%d ", from_r, to_r); printf(" >> %f, << %f \n", best_topology.links[from_r*num_routers+to_r].used_forw, best_topology.links[from_r*num_routers+to_r].used_rev); } } } printf("\n"); } } exit(0); return (0); } /* * $Log: backbone_cost.c,v $ * Revision 1.6 1999/10/02 23:45:14 horton * add sort * * Revision 1.10 1999/08/19 02:01:43 horton * Add link charging code. * Add voice capability checking * Add capacity and capability checking * Make verbosity an int rather than boole * * Revision 1.9 1999/08/13 03:01:54 horton * Implement additional constraint routing (latency/jitter) * * Revision 1.8 1999/08/09 02:55:54 horton * Ignore unused PVCs in mesh model. * * Revision 1.5 1999/08/06 08:16:59 horton * Ignore unused PVC links * * Revision 1.3 * Add charging and alternate model to just start with a mesh. * * Revision 1.7 1999/08/06 05:05:25 horton * First charged, and routed solution * add model * * Revision 1.3 1999/08/06 02:45:47 horton * First charged, and routed solution. * * Revision 1.5 1999/07/30 06:31:43 horton * More file parsing. Start building cost calculator * * Revision 1.4 1999/07/29 07:24:31 horton * *** empty log message *** * * Revision 1.3 1999/07/29 07:18:32 horton * Start parsing config files. * * Revision 1.2 1999/07/28 06:29:49 horton * Add RCS * */