/* $Id: exBF_ack.c,v 10.1 92/10/06 23:06:42 ca Exp $ */ /* * MaRS Maryland Routing Simulator * Copyright (c) 1991 University of Maryland * All Rights Reserved. * * Permission to use, copy, modify, distribute, and sell this software and its * documentation for any purpose is hereby granted without fee, provided that * the above copyright notice appear in all copies and that both that * copyright notice and this permission notice appear in supporting * documentation, and that the name of U.M. not be used in advertising or * publicity pertaining to distribution of the software without specific, * written prior permission. U.M. makes no representations about the * suitability of this software for any purpose. It is provided "as is" * without express or implied warranty. * * U.M. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL U.M. * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * * Authors: Cengiz Alaettinoglu, Klaudia Dussa-Zieger, Ibrahim Matta * Systems Design and Analysis Group * Department of Computer Science * University of Maryland at College Park. */ /* * Routing Module - Extended BF Algorithm * * For a full description of this algorithm, refer to : * "Chunhsiang Cheng, Ralph Riley, Srikanta P.R. Kumar, and * J.J. Garcia-Luna-Aceves, "A LOOP-FREE EXTENTED BELLMAN-FORD * ROUTING PROTOCOL WITHOUT BOUNCING EFFECT", ACM, 1989" */ #include #include #include #include "sim.h" #include "q.h" #include "list.h" #include "component.h" #include "log.h" #include "comptypes.h" #include "packet.h" #include "eventdefs.h" #include "event.h" #include "node.h" #include "exBF_ack.h" #include "link.h" #include "perf.h" #ifdef DEBUG extern Log debug_log; #endif #define RT(g) (*((RoutingTable *)(g->routing_table->u.p))) #define LTT(g) (*((LocalTopologyTable *)(g->local_top->u.p))) #define DT(g) (*((DistanceTable *)(g->distance_table->u.p))) static caddr_t exBFa_create(), exBFa_delete(), exBFa_neighbor(), exBFa_uneighbor(), exBFa_start(), exBFa_reset(), exBFa_start_computation(), exBFa_processing(); static int routing_processing_time(); void fr_space(); static index_at_DT(), add_new_node(), in_path(), min_in_row(), cost_change(); static void rt_update(), initialize_tables(), send_changes(), mark_j_undetermined(), shutdown_event(), wake_up_event(); static Packet *copy_rt_to_vector(), *create_vector(); caddr_t exBF_ack_action(src, g, type, pkt, arg) Component *src; register ExBFat *g; int type; Packet *pkt; caddr_t arg; { caddr_t result = NULL; dbg_set_level(DBG_ERR); /* Just a big switch on type of event */ switch (type) { case EV_RESET: #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)g, "reset"); #endif result = exBFa_reset(g); break; case EV_CREATE: /* Minor sanity check first-- g should be NULL when initializing. */ #ifdef DEBUG if (g) dbg_write(debug_log, DBG_INFO, (Component *)NULL, "ExBF_ack Generator initialization called with non-null pointer."); #endif result = exBFa_create((char *)arg); break; case EV_DEL: result = exBFa_delete(g); break; case EV_NEIGHBOR: result = exBFa_neighbor(g, (Component *)arg); break; case EV_UNEIGHBOR: result = exBFa_uneighbor(g, (Component *)arg); break; case EV_MK_PEER: result = (caddr_t) g; break; case EV_START: result = exBFa_start(g); break; /* The preceding were the commands. Now the actual events */ case EV_ROUTE_PROCESSING: result = exBFa_processing(g, pkt); break; case EV_START_COMPUTATION: result = exBFa_start_computation(g); break; case EV_STOP: result = (caddr_t) g; break; default: #ifdef DEBUG dbg_write(debug_log, DBG_ERR, (Component *)g, "got unexpected event of type %x", type); #endif break; } return(result); } /****************************************************/ static caddr_t exBFa_create(name) register char *name; { ExBFat *newg; /* Memory for the component structure. */ newg = (ExBFat *)sim_malloc(sizeof(ExBFat)); /* First things first-- copy name into the new structure. */ strncpy(newg->exBFa_name, name, 40); /* have to create a neighbor list */ newg->exBFa_neighbors = l_create(); newg->exBFa_params = q_create(); newg->exBFa_class = ROUTE_CLASS; newg->exBFa_type = EXBF_ACK; newg->exBFa_action = exBF_ack_action; newg->exBFa_menu_up = FALSE; /* Initialize the parameters */ (void)param_init((Component *)newg, "Name", (PFD)NULL, make_name_text, make_short_name_text, param_input_name, 0, DisplayMask | InputMask, 0.0); newg->brdcast_period = param_init((Component *)newg, "Time btw new cycle starts (msec)", int_calc, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newg, brdcast_period)->u.i = 10000; newg->sd = param_init((Component *)newg, "Standard deviation", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newg, sd)->u.i = 1000; newg->distance_table = param_init((Component *)newg, "Distance table", (PFD)NULL, make_text, make_text, (PFI)NULL, 0, 0, 0.0); pval(newg, distance_table)->u.p = sim_malloc(sizeof(DistanceTable)); newg->local_top = param_init((Component *)newg, "Local topology table", (PFD)NULL, make_text, make_ltt_text, (PFI)NULL, TEXT_METER, DisplayMask | CanHaveLogMask | CanHaveMeterMask, 0.0); pval(newg, local_top)->u.p = (caddr_t) NULL; newg->routing_table = param_init((Component *)newg, "Routing table", (PFD)NULL, make_text, make_rt_text, (PFI)NULL, TEXT_METER, DisplayMask | CanHaveLogMask | CanHaveMeterMask, 0.0); pval(newg, routing_table)->u.p = sim_malloc(sizeof(RoutingTable)); newg->processing_time = routing_processing_time; newg->no_of_nodes = 0; newg->node = (Component *) NULL; #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)newg, "ExBF_ack generator initialized"); #endif return((caddr_t)newg); } /*************************************************/ static caddr_t exBFa_delete(g) register ExBFat *g; { free(g->routing_table->u.p); free(g->distance_table->u.p); comp_delete((Component *) g); return (caddr_t) g; } static caddr_t exBFa_reset(g) ExBFat *g; { g->no_of_nodes = 0; g->link_cost_time = 0; return (caddr_t) g; } /*************************************************/ static caddr_t exBFa_neighbor(g, c) register ExBFat *g; register Component *c; { caddr_t result; /* Put the passed neighbor into my neighbor list, but only if it is a legal neighbor (a node). Also can only have one neighbor. */ result = (caddr_t)add_neighbor((Component *)g, c, 1, 1, NODE_CLASS); if (result != (caddr_t)NULL) { g->local_top->u.p = (caddr_t)((Nodee *)c)->loc_topology_table; g->node = c; } return result; } /*************************************************/ /* Initialize distance- and routing- tables */ static void initialize_tables(g) register ExBFat *g; { register int i, j, ind; int lc; for (j = 0; j < MAX_NO_OF_NODES; j++) { for (i = 0; i < MAX_LINKS; i++) { DT(g) [j].cost_via [i] = MARS_INFINITY; DT(g) [j].head_via [i] = (Component *)NULL; } DT(g) [j].dest = (Component *)NULL; DT(g) [j].cost = MARS_INFINITY; RT(g) [j].dest = (Component *)NULL; RT(g) [j].cost = MARS_INFINITY; RT(g) [j].hop = (Component *)NULL; g->head[j] = (Component *)NULL; } RT(g) [0].dest = g->node; RT(g) [0].hop = (Component *) NULL; RT(g) [0].cost = 0; g->no_of_nodes++; for (i = 0; LTT(g) [i].n_nd != (Component *)NULL; i++) { ind = g->no_of_nodes; lc = link_cost((Routet *)g, i); g->no_of_nodes++; DT(g) [ind].dest = LTT(g) [i].n_nd; DT(g) [ind].cost = lc; DT(g) [ind].cost_via [i] = lc; DT(g) [ind].head_via [i] = g->node; RT(g) [ind].dest = LTT(g) [i].n_nd; RT(g) [ind].cost = lc; RT(g) [ind].hop = LTT(g) [i].n_link; g->head[ind] = g->node; g->old_cost_via [i] = lc; g->num_ack [i] = 0; } log_param((Component *)g, g->routing_table); } /********************************************************/ static caddr_t exBFa_uneighbor(g, c) register ExBFat *g; register Component *c; { caddr_t result; result = (caddr_t)remove_neighbor((Component *)g, c); if (result != (caddr_t)NULL) { g->local_top->u.p = (caddr_t) NULL; g->node = (Component *) NULL; g->no_of_nodes = 0; } return result; } /**********************************************************/ static caddr_t exBFa_start(g) register ExBFat *g; { if (g->exBFa_neighbors->l_len != 1) { #ifdef DEBUG dbg_write(debug_log, DBG_ERR, (Component *)g, "ExBF_ack Module not connected to a node"); #endif return((caddr_t)NULL); } if (!lcostfcn_adr) { printf("LINK_COST_FUNC typed component not found...\n"); return((caddr_t)NULL); } initialize_tables(g); send_changes(g, 0, (Component *) NULL, (Component *) NULL); /* Check changes in link costs */ ev_enqueue(EV_START_COMPUTATION, (Component *)g, (Component *)g, ev_now() + time_btw_broadcast(g) / USECS_PER_TICK, g->exBFa_action, (Packet *)NULL, (caddr_t)NULL); /* Something non-NULL to return */ return((caddr_t)g); } /**********************************************************/ static int routing_processing_time(g, pkt) register ExBFat *g; register Packet *pkt; { switch (pkt->rt_pk.rt_type) { case RT_LINK_SHUTDOWN : return 2000; case RT_LINK_WAKEUP : return 2000; case RT_NODE_SHUTDOWN : return 10; case RT_NODE_WAKEUP : return 10; case RT_VECTOR : return 4500; case RT_VECTOR_ACK : return 2000; default : ; } return 10; } /*********************************************************/ static int add_new_node(g, c) register ExBFat *g; Component *c; { int ind; int i; ind = g->no_of_nodes; g->no_of_nodes++; RT(g)[ind].dest = c; RT(g)[ind].cost = MARS_INFINITY; RT(g)[ind].hop = (Component *) NULL; g->head[ind] = (Component *) NULL; DT(g)[ind].dest = c; DT(g)[ind].cost = MARS_INFINITY; for (i = 0; LTT(g)[i].n_nd != (Component *)NULL; i++) { DT(g)[ind].cost_via [i] = MARS_INFINITY; DT(g)[ind].head_via [i] = (Component *) NULL; } log_param((Component *)g, g->routing_table); return ind; } /******************************************************/ static caddr_t exBFa_start_computation(g) register ExBFat *g; { unsigned int time_now, ticks; if (*(char *)((Nodee *)g->node)->nd_status->u.p == 'D') { #ifdef DEBUG printf("%s : node is down cant start a new cycle at %d ticks\n", g->exBFa_name, ev_now()); #endif return((caddr_t)g); } /* node is UP */ /* Check if link weights have changed */ compute_link_cost_metrics((Routet *)g); if (!cost_change(g)) { #ifdef DEBUG printf("%s : no cost change cant start a new cycle at %d ticks\n", g->exBFa_name, ev_now()); #endif ; } /* schedule next computation */ time_now = ev_now(); ticks = time_btw_broadcast(g) / USECS_PER_TICK; ev_enqueue(EV_START_COMPUTATION, (Component *)g, (Component *)g, time_now + ticks, g->exBFa_action, (Packet *)NULL, (caddr_t)NULL); return((caddr_t)g); } /******************************************************/ static int index_at_DT(g, sink) register ExBFat *g; register Component *sink; { register int i; for (i = 1; DT(g)[i].dest != sink && i < g->no_of_nodes; i++) ; if ( i == g->no_of_nodes) return -1; /* This is the first time we hear about that node */ else return i; } /*******************************************************/ /* The following function "in_path" returns 1 if Neighbor is in the path from my node to Dest. Otherwise, the function returns 0 */ static int in_path(g, Neighbour, Dest) register ExBFat *g; register Component *Neighbour; register Component *Dest; { Component *h; h = g->head[index_at_DT(g, Dest)]; /* find head from my node to Dest */ if (h == (Component *) NULL) return 0; if (h == g->node) /* Neighbor is not in the path from my node to Dest */ return 0; else { if (h == Neighbour) /* Neighbor is in the path from my node to Dest */ return 1; else return in_path(g, Neighbour, h); /* cannot determine yet, try again */ } } /*******************************************************/ /* The following procedure "rt_update" updates the routing * table. Any destination j will be assigned a distance copied * from column b iff cost to j thru b is minimum among row j * of distance table and each node v extracted from cost to j * thru b must be that cost to v thru b is also the minimum * among row v. * * Switch to the neighbor that offers the shortest distance * representing a path which does not contain the failed link. */ static void rt_update(g, node1, node2) register ExBFat *g; register Component *node1, *node2; { register int j, b, not_min; int path_contains_failed_link; Component *v, *vprev; for (j = 1; j < g->no_of_nodes; j++) { do { path_contains_failed_link = 0; b = min_in_row(g, j); if (b != -1) { not_min = 0; vprev = DT(g) [j].dest; v = DT(g) [j].head_via[b]; while (v != g->node && !not_min && !((vprev == node1 && v == node2) || (vprev == node2 && v == node1))) { if (b != min_in_row(g, index_at_DT(g, v))) not_min = 1; else { vprev = v; v = DT(g) [index_at_DT(g, v)].head_via [b]; } } if ((vprev == node1 && v == node2) || (vprev == node2 && v == node1)) { DT(g) [j].cost_via [b] = MARS_INFINITY; path_contains_failed_link = 1; } } } while (path_contains_failed_link && (b != -1)); if (v == g->node && !not_min && b != -1) { RT(g) [j].cost = DT(g) [j].cost_via [b]; g->temp_hop [j] = LTT(g) [b].n_link; RT(g) [j].hop = (Component *) NULL; g->head[j] = DT(g) [j].head_via [b]; DT(g) [j].cost = RT(g) [j].cost; } else mark_j_undetermined(g, j); } log_param((Component *)g, g->routing_table); } /**********************************************************/ /* Copy routing table into routing vector */ static Packet *copy_rt_to_vector(g) register ExBFat *g; { register int j; register Packet *pkt; rt_vector_triplet *triplet; pkt = create_vector(g); for (triplet = (rt_vector_triplet *) pkt->tail, j = 1; j < g->no_of_nodes; j++, triplet++) { triplet->destination = RT(g) [j].dest; triplet->best_cost = RT(g) [j].cost; triplet->head = g->head[j]; } return pkt; } /*********************************************************/ static Packet *create_vector(g) register ExBFat *g; { register Packet *pp; pp = pk_alloc(); pp->pk_length = VECTOR_PKT_HEADER_SIZE + (g->no_of_nodes - 1) * sizeof(rt_vector_triplet); pp->pk_type = ROUTE_PACKET; pp->rt_pk.rt_type = RT_VECTOR; pp->rt_pk.rt.vector.sender = g->node; pp->rt_pk.rt.vector.no_of_triplets = g->no_of_nodes - 1; pp->tail = sim_malloc((g->no_of_nodes - 1) * sizeof(rt_vector_triplet)); return pp; } /**********************************************************/ static int min_in_row(g, j) register ExBFat *g; register int j; { register int i; int min_column, min_cost; min_column = -1; min_cost = MARS_INFINITY; for (i = 0; LTT(g) [i].n_nd != (Component *)NULL; i++) { if (DT(g) [j].cost_via [i] < min_cost) { min_cost = DT(g) [j].cost_via [i]; min_column = i; } } return min_column; } /*******************************************************/ static void mark_j_undetermined(g, j) register ExBFat *g; register int j; { RT(g) [j].cost = MARS_INFINITY; RT(g) [j].hop = (Component *) NULL; g->temp_hop [j] = (Component *) NULL; g->head[j] = (Component *) NULL; DT(g) [j].cost = MARS_INFINITY; log_param((Component *)g, g->routing_table); } /********************************************************/ static int cost_change(g) register ExBFat *g; { register int i, j, update; int lcst[MAX_LINKS]; for (i = 0; LTT(g) [i].n_nd != (Component *) NULL; i++) lcst [i] = link_cost((Routet *)g, i); update = 0; for (j = 1; j < g->no_of_nodes; j++) { for (i = 0; LTT(g) [i].n_nd != (Component *) NULL; i++) { if (lcst [i] == MARS_INFINITY) DT(g) [j].cost_via [i] = MARS_INFINITY; if (DT(g) [j].cost_via [i] != MARS_INFINITY) DT(g) [j].cost_via [i] += (lcst [i] - g->old_cost_via [i]); if ((DT(g) [j].cost_via [i] < RT(g) [j].cost) || ((i == index_at_LTT_by_link((Routet *)g, g->temp_hop [j])) && (DT(g) [j].cost_via [i] > RT(g) [j].cost))) update = 1; } } for (i = 0; LTT(g) [i].n_nd != (Component *) NULL; i++) g->old_cost_via [i] = lcst [i]; if (update) send_changes(g, 0, (Component *) NULL, (Component *) NULL); return update; } /********************************************************/ static void send_changes(g, failure_flag, node1, node2) register ExBFat *g; Component *node1, *node2; int failure_flag; { register int i, j, rt_pkts_count; Packet *p, *sent_pkt; rt_vector_triplet *triplet, *sent_triplet; rt_update(g, node1, node2); /* Update routing table */ p = copy_rt_to_vector(g); rt_pkts_count = 0; /*send updates to select neighbors and infinity to others */ for (i = 0; LTT(g) [i].n_nd != (Component *) NULL; i++) { /* Send changes on outgoing UP links */ if (*(char *)(((Link *)(LTT(g) [i].n_link))->link_status)->u.p == 'D') continue; sent_pkt = create_vector(g); sent_triplet = (rt_vector_triplet *) sent_pkt->tail; /* Test if the change is triggered by a link failure */ if (failure_flag) { /* stamp routing vector sent with identity of the failed link */ sent_pkt->rt_pk.rt.vector.failure_flag = 1; sent_pkt->rt_pk.rt.vector.node1 = node1; sent_pkt->rt_pk.rt.vector.node2 = node2; } else { sent_pkt->rt_pk.rt.vector.failure_flag = 0; sent_pkt->rt_pk.rt.vector.node1 = (Component *) NULL; sent_pkt->rt_pk.rt.vector.node2 = (Component *) NULL; } for (triplet = (rt_vector_triplet *) p->tail, j = 1; j < g->no_of_nodes; triplet++, j++,sent_triplet++) { if (in_path(g, LTT(g) [i].n_nd, triplet->destination)) { sent_triplet->destination = triplet->destination; sent_triplet->best_cost = MARS_INFINITY; sent_triplet->head = (Component *) NULL; } else { sent_triplet->destination = triplet->destination; sent_triplet->best_cost = triplet->best_cost; sent_triplet->head = triplet->head; } } rt_pkts_count ++; ev_call(EV_NODE_PRODUCE, (Component *)g, g->node, g->node->co_action, sent_pkt, LTT(g) [i].n_link); g->num_ack [i]++; /* Wait for ack */ } pk_free(p); pm((Component *)g, EXBF_ACK, ROUTING_PKT, rt_pkts_count, 0, 0, 0); } /******************************************************/ static caddr_t exBFa_processing(g, pkt) register ExBFat *g; register Packet *pkt; { register int i; int j, k, update, m, flag, lc; rt_vector_triplet *triplet; unsigned int ticks; Packet *ack_pkt; free_routing_queue((Routet *)g, pkt); /* standard */ k = index_at_LTT_by_node((Routet *)g, pkt->rt_pk.rt.vector.sender); switch (pkt->rt_pk.rt_type) { case RT_VECTOR : update = 0; triplet = (rt_vector_triplet *) pkt->tail; for (i = 1; i <= pkt->rt_pk.rt.vector.no_of_triplets; i++, triplet++) { if (triplet->destination == g->node) continue; j = index_at_DT(g, triplet->destination); if (j == -1) j = add_new_node(g, triplet->destination); lc = link_cost((Routet *)g, k); if ( (triplet->best_cost == MARS_INFINITY) || (lc == MARS_INFINITY) ) DT(g) [j].cost_via [k] = MARS_INFINITY; else DT(g) [j].cost_via [k] = triplet->best_cost + lc; DT(g) [j].head_via [k] = triplet->head; if (DT(g) [j].cost_via [k] < RT(g) [j].cost) update = 1; m = index_at_LTT_by_link((Routet *)g, g->temp_hop [j]); if (m == k && (DT(g) [j].cost_via [k] > RT(g) [j].cost)) update = 1; } /* Send back a routing vector's ack to the sender */ ack_pkt = pk_alloc(); ack_pkt->pk_length = ACK_PKT_SIZE; ack_pkt->pk_type = ROUTE_PACKET; ack_pkt->rt_pk.rt_type = RT_VECTOR_ACK; ack_pkt->rt_pk.rt.vector.sender = g->node; ev_call(EV_NODE_PRODUCE, (Component *)g, g->node, g->node->co_action, ack_pkt, LTT(g) [k].n_link); pm((Component *)g, EXBF_ACK, ROUTING_PKT, 1, 0, 0, 0); if (update) send_changes(g, pkt->rt_pk.rt.vector.failure_flag, pkt->rt_pk.rt.vector.node1, pkt->rt_pk.rt.vector.node2); pk_free(pkt); break; case RT_VECTOR_ACK : /* Interneighbor coordination required to prevent routing-table loops */ g->num_ack [k]--; flag = 0; for (i = 0; (LTT(g) [i].n_nd != (Component *) NULL) && !flag; i++) if (g->num_ack [i] > 0) flag = 1; if (!flag) { /* Got routing vector acks from all neighbors */ for (j = 1; j < g->no_of_nodes; j++) RT(g) [j].hop = g->temp_hop [j]; /*switch to preferred neighbors*/ } pk_free(pkt); break; case RT_LINK_WAKEUP : wake_up_event(g, pkt); break; case RT_LINK_SHUTDOWN : shutdown_event(g, pkt); break; default : ; } log_param((Component *)g, g->routing_table); schedule_next_EV_ROUTE_PROCESSING((Routet *)g); /* standard */ return ((caddr_t) g); } /******************************************************/ static void shutdown_event(g, pkt) register ExBFat *g; register Packet *pkt; { int k, j, update; update = 0; k = index_at_LTT_by_link((Routet *)g, pkt->pk_source_socket.so_host); for (j = 1; j < MAX_NO_OF_NODES; j++) { DT(g) [j].cost_via [k] = MARS_INFINITY; DT(g) [j].head_via [k] = (Component *) NULL; g->old_cost_via [k] = MARS_INFINITY; if ((j < g->no_of_nodes) && (k == index_at_LTT_by_link((Routet *)g, g->temp_hop [j]))) update = 1; } link_failure_init_LTT((Routet *)g, k); g->num_ack [k] = 0; pk_free(pkt); if (update) /* update due to link failure */ send_changes(g, 1, g->node, LTT(g) [k].n_nd); } /******************************************************/ static void wake_up_event(g, pkt) register ExBFat *g; register Packet *pkt; { int k, update, lc; update = 0; k = index_at_LTT_by_link((Routet *)g, pkt->pk_source_socket.so_host); link_repair_init_LTT((Routet *)g, k); lc = link_cost((Routet *)g, k); DT(g) [k+1].cost_via [k] = lc; DT(g) [k+1].head_via [k] = g->node; g->old_cost_via [k] = lc; pk_free(pkt); if (DT(g) [k+1].cost_via[k] < RT(g) [k+1].cost) update = 1; if (update) send_changes(g, 0, (Component *) NULL, (Component *) NULL); }