/* $Id: node.c,v 10.1 92/10/06 23:06:54 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. */ #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 "route.h" #include "link.h" #define EnoughSpace ( (pval(nd, nd_buffer_space)->u.i== -1) ||\ ((pval(nd, nd_curr_buffer_space)->u.i+pkt->pk_length) <=\ pval(nd, nd_buffer_space)->u.i) ) static caddr_t instant_rate(); /* function to compute instantaneous drop rate */ /*extern Log pkt_log;*/ #ifdef DEBUG extern Log debug_log; #endif static caddr_t nd_reset(), nd_create(), nd_delete(), nd_neighbor(), nd_uneighbor(),nd_start(), nd_send(), nd_receive(), nd_produce(), nd_failure(), nd_repair(); void pk_free() ,occupy_space(); static void discard_pk(); static int routing_table_look_up(), index_in_local_top_table(), exist_data_space_to_replace(); static unsigned int transmission_time_ticks(); static void give_route_pkt_priority(); /* The main action routine of a node */ /*ARGSUSED*/ caddr_t node_action(src, nd, type, pkt, arg) Component *src; register Nodee *nd; int type; Packet *pkt; caddr_t arg; { register caddr_t result = NULL; dbg_set_level(DBG_ERR); /* Just a big switch on type of event */ switch (type) { case EV_RESET: result = nd_reset(nd); break; case EV_CREATE: /* Minor sanity check first-- nd should be NULL when initializing. */ #ifdef DEBUG if (nd) dbg_write(debug_log, DBG_ERR, (Component *)NULL, "Node initialization called with non-null pointer."); #endif result = nd_create((char *)arg); break; case EV_DEL: result = nd_delete(nd); break; case EV_NEIGHBOR: result = nd_neighbor(nd, (Component *)arg); break; case EV_UNEIGHBOR: result = nd_uneighbor(nd, (Component *)arg); break; case EV_START: #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)nd, "started "); #endif result = nd_start(nd); break; case EV_NODE_RECEIVE: result = nd_receive(nd, src, pkt); break; case EV_NODE_SEND: result = nd_send(nd, (Neighbor *)arg); break; case EV_NODE_PRODUCE: result = nd_produce(nd, (Component *)arg, pkt); break; case EV_NODE_FAILURE: result = nd_failure(nd, src); break; case EV_NODE_REPAIR: result = nd_repair(nd, src); break; case EV_INSTANT_RATE: result = instant_rate(nd); break; case EV_STOP: result = (caddr_t) nd; break; default: #ifdef DEBUG dbg_write(debug_log, DBG_ERR, (Component *)nd, "received unrecognized event of type %d", type); #endif break; } /* end switch */ return(result); } /****************************************/ static caddr_t nd_reset(nd) register Nodee *nd; { register Neighbor *temp, *n; register unsigned int ticks; register int k; /* Clear out all of the outgoing packet queues. */ for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next){ if (n->n_c->co_class == LINK_CLASS) { while (q_deq(n->n_pq)) ; log_param((Component *)nd, n->n_p); } } /* Fill in local topology table for that node */ /* For each outgoing link, determine the node at the other end, the propagation delay and bandwidth of that link */ k = 0; for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next) if (n->n_c->co_class == LINK_CLASS) { nd->loc_topology_table[k].n_link = n->n_c; nd->loc_topology_table[k].l_status = "Up"; /* ((Link *)(n->n_c))->link_status->u.p; */ nd->loc_topology_table[k].l_delay = ((Link *)(n->n_c))->link_propagation_delay->u.i; nd->loc_topology_table[k].l_bandwidth = ((Link *)(n->n_c))->link_bandwidth->u.i; nd->loc_topology_table[k].l_q = n->n_pq; /* Current queue length */ /* for that outgoing link can be easily */ /* computed as l_q->q_len */ temp = (Neighbor *)((Link *)(n->n_c))->link_neighbors->l_head; while ((temp->n_c->co_class != NODE_CLASS) || ((Nodee *)(temp->n_c) == nd)) temp = temp->n_next; /* Node in the other end of that link found */ nd->loc_topology_table[k].n_nd = (temp->n_c); k++; } nd->loc_topology_table[k].n_nd = (Component *)NULL; /* End of table */ nd->loc_topology_table[k].n_link = (Component *)NULL; /* End of table */ for (k = 0; k < MAX_LINKS; k++) { nd->loc_topology_table[k].queue_size = 0; nd->loc_topology_table[k].tot_queue_size = 0.0; nd->loc_topology_table[k].avg_queue_size = 0; nd->loc_topology_table[k].last_op_time = 0; nd->loc_topology_table[k].last_utilization = 0.0; nd->loc_topology_table[k].total_delay = 0.0; nd->loc_topology_table[k].total_trans_queuing_delay = 0.0; nd->loc_topology_table[k].total_tr_delay = 0.0; nd->loc_topology_table[k].no_of_packets = 0; nd->loc_topology_table[k].ave_delay = nd->loc_topology_table[k].l_delay + nd->nd_delay->u.i; nd->loc_topology_table[k].total_util = 0; nd->loc_topology_table[k].ave_util = 0.0; nd->loc_topology_table[k].l_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].delay_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].util_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].hndly_cost = lcostfcn_adr->minimum->u.i; } /* Clear input routing packet queue */ while (q_deq((queue *)pval(nd, nd_pq)->u.p)) ; log_param((Component *)nd, pval(nd, nd_pq)); /* Node up */ pval(nd, nd_status)->u.p = "Up"; log_param((Component *)nd, pval(nd, nd_status)); pval(nd, nd_dropped)->u.i = 0; log_param((Component *)nd, pval(nd, nd_dropped)); pval(nd, nd_curr_buffer_space)->u.i = 0; log_param((Component *)nd, pval(nd, nd_curr_buffer_space)); nd->memory_utl->u.d = 0.0; log_param((Component *)nd, nd->memory_utl); pval(nd, max_occupied_space)->u.i = 0; log_param((Component *)nd, nd->max_occupied_space); nd->last_packets_dropped = 0; #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)nd, "reset"); #endif return((caddr_t)nd); } /****************************************/ static caddr_t nd_start(nd) register Nodee *nd; { register unsigned int ticks; /* Schedule first failure */ if (nd->nd_time_btw_fails->u.i > 0) { ticks = (unsigned)((double)(time_to_fail(nd)) * 1000000.0 / USECS_PER_TICK); ev_enqueue(EV_NODE_FAILURE, (Component *)nd, (Component *)nd, ev_now()+ticks, nd->nd_action, (Packet *)NULL, (caddr_t)NULL); } /* Schedule first computation of instantaneous drop rate */ ev_enqueue(EV_INSTANT_RATE, (Component *)nd, (Component *)nd, ev_now(), nd->nd_action, (Packet *)NULL, (caddr_t)NULL); #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)nd, "started :local topology table initialized .."); #endif return((caddr_t)nd); } /****************************************/ /* Compute instantaneous drop rate in packets/msec for this node */ static caddr_t instant_rate(nd) register Nodee *nd; { nd->drop_rate->u.d = (((double)nd->nd_dropped->u.i - (double)nd->last_packets_dropped)*(double)1000.0) /(double)perf_update_dt_usecs; log_param((Component *)nd, nd->drop_rate); nd->last_packets_dropped = nd->nd_dropped->u.i; /* Schedule next computation */ ev_enqueue(EV_INSTANT_RATE, (Component *)nd, (Component *)nd, (tick_t)(ev_now() + perf_update_dt_usecs/USECS_PER_TICK), nd->nd_action, (Packet *)NULL, (caddr_t)NULL); return((caddr_t)nd); } /****************************************/ static caddr_t nd_create(name) register char *name; { register Nodee *newnd; /* Memory for the component structure. */ newnd = (Nodee *)sim_malloc(sizeof(Nodee)); /* have to create a neighbor list */ newnd->nd_neighbors = l_create(); strncpy(newnd->nd_name, name, 40); newnd->nd_params = q_create(); newnd->nd_type = NODE; newnd->nd_class = NODE_CLASS; newnd->nd_action = node_action; newnd->nd_menu_up = FALSE; /* Initialize the parameters */ newnd->nd_pktlog = param_init((Component *)newnd, "Name", (PFD)NULL, make_name_text, make_short_name_text, param_input_name, 0, DisplayMask | InputMask | CanHaveLogMask, 0.0); newnd->nd_delay = param_init((Component *)newnd, "Delay to process a packet (uSec)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); newnd->nd_delay->u.i = 1000; /* currently not used */ newnd->nd_speed = param_init((Component *)newnd, "Speed of node (uSec/kbyte)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, 0, 0.0); newnd->nd_speed->u.i = 0; newnd->nd_buffer_space = param_init((Component *)newnd, "Buffer space in bytes (-1=inf)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, nd_buffer_space)->u.i = -1; newnd->nd_time_btw_fails = param_init((Component *)newnd, "Mean time btw failures (sec)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, nd_time_btw_fails)->u.i = -1; newnd->dist_chosen_fail = param_init((Component *)newnd, "Interfailure dist (0=>EXP, 1=>UNIF)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, dist_chosen_fail)->u.i = 0; newnd->sd_fail = param_init((Component *)newnd, "Enter standard deviation if UNIF", (PFD)NULL, make_double_text, make_short_double_text, param_input_double, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, sd_fail)->u.d = 0; newnd->nd_time_for_repair = param_init((Component *)newnd, "Mean time to repair (sec)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, nd_time_for_repair)->u.i = 1200; newnd->dist_chosen_repair = param_init((Component *)newnd, "Repair time dist (0=>EXP, 1=>UNIF)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, dist_chosen_repair)->u.i = 0; newnd->sd_repair = param_init((Component *)newnd, "Enter standard deviation if UNIF", (PFD)NULL, make_double_text, make_short_double_text, param_input_double, 0, DisplayMask | ModifyMask, 0.0); pval(newnd, sd_repair)->u.d = 0; newnd->nd_status = param_init((Component *)newnd, "Node status", (PFD)NULL, make_str_text, make_short_str_text, (PFI)NULL, 0, DisplayMask | CanHaveLogMask, 0.0); pval(newnd, nd_status)->u.p = "Up"; newnd->nd_curr_buffer_space = param_init((Component *)newnd, "Buffer space used", int_calc, make_int_text, make_short_int_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); pval(newnd, nd_curr_buffer_space)->u.i = 0; newnd->max_occupied_space = param_init((Component *)newnd, "Max buffer space used", int_calc, make_int_text, make_short_int_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); pval(newnd, max_occupied_space)->u.i = 0; newnd->nd_dropped = param_init((Component *)newnd, "Number of packets dropped", int_calc, make_int_text, make_short_int_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); pval(newnd, nd_dropped)->u.i = 0; newnd->last_packets_dropped = 0; newnd->drop_rate = param_init((Component *)newnd, "Instantaneous drop rate", double_calc, make_double_text, make_short_double_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); pval(newnd, drop_rate)->u.d = 0; newnd->memory_utl = param_init((Component *)newnd, "Memory utilization", double_calc, make_double_text, make_short_double_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); pval(newnd, memory_utl)->u.d = 0; newnd->nd_pq = param_init((Component *)newnd, "Input routing queue", pktq_calc, pktq_text, pktq_short_text, (PFI)NULL, TIME_HISTORY, DisplayMask | CanHaveMeterMask | CanHaveLogMask, 0.0); /* Make queue to store packets in */ pval(newnd, nd_pq)->u.p = (caddr_t)q_create(); /* Mark end of local topology table */ newnd->loc_topology_table[0].n_nd = (Component *)NULL; newnd->loc_topology_table[0].n_link = (Component *)NULL; #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)newnd, "Node initialized"); #endif return((caddr_t)newnd); } /****************************************/ static caddr_t nd_delete(nd) register Nodee *nd; { register Neighbor *n; /* Delete all outgoing queues */ for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next) if (n->n_c->co_class == LINK_CLASS) lq_delete((list *)n->n_pq); lq_delete((list *)pval(nd, nd_pq)->u.p); /* Wipe routing packet queue */ comp_delete((Component *)nd); return((caddr_t)nd); } /****************************************/ static caddr_t nd_neighbor(nd, c) register Nodee *nd; register Component *c; { register Neighbor *n; Param *p; if (!(n = add_neighbor((Component *)nd, c, 0, 3, ROUTE_CLASS, LINK_CLASS, APTR_CLASS))) return((caddr_t)NULL); /* Failed */ if (c->co_class == ROUTE_CLASS) { /* Get pointers to routing table, to func that estimates route processing time, and to the routing module */ nd->nd_ptr_route_tab = (RoutingTable *)(((Routet *)c)->routing_table->u.p); nd->nd_route_process_time = (PFI)(((Routet *)c)->processing_time); nd->nd_ptr_routing_mod = (Routet *)c; return((caddr_t)n); } /* Allocate a queue for outgoing packets */ if (c->co_class == LINK_CLASS) { n->n_pq = q_create(); p = param_init((Component *)nd, c->co_name, pktq_calc, pktq_text, pktq_short_text, (PFI)NULL, TIME_HISTORY, 0, 0.0); strcat(p->p_name, " output queue"); p->p_flags = CanHaveMeterMask | DisplayMask | CanHaveLogMask; p->u.p = (caddr_t)n->n_pq; /* pointer to the outgoing queue */ n->n_p = p; return((caddr_t)n); /* Just need to return something non-zero */ } return((caddr_t)n); /* Just need to return something non-zero */ } /****************************************/ static caddr_t nd_uneighbor(nd, c) register Nodee *nd; register Component *c; { Neighbor *n; if (c->co_class == ROUTE_CLASS) { nd->nd_ptr_route_tab = (RoutingTable *) NULL; nd->nd_route_process_time = (PFI) NULL; nd->nd_ptr_routing_mod = (Routet *) NULL; } if (c->co_class == LINK_CLASS) { n = find_neighbor(nd->nd_neighbors, c); lq_delete((list *)n->n_pq); } return((caddr_t)remove_neighbor((Component *)nd, c)); } /****************************************/ static caddr_t nd_receive(nd, src, pkt) register Nodee *nd; register Component *src; register Packet *pkt; { register unsigned int ticks, rt_process_time; register Neighbor *n; register int k; Component *l; char dummy[10]; pkt->pk_arrival_time = ev_now(); /* if the node is down drop the packet */ if (*(char *)(nd->nd_status->u.p) == 'D') { discard_pk(nd, pkt); return((caddr_t)nd); } /* if the node is up and it is a route packet */ if (pkt->pk_type == ROUTE_PACKET) { if (!(EnoughSpace)) { if (!(exist_data_space_to_replace(nd, pkt->pk_length))) { discard_pk(nd, pkt); return((caddr_t)nd); } } /* Evaluate time to process the routing packet (in ticks) */ rt_process_time = (*((PFI)(nd->nd_route_process_time))) ((Component *)nd->nd_ptr_routing_mod, pkt); rt_process_time = rt_process_time / USECS_PER_TICK; /* This assumes that the routing packet joins the routing packet */ /* without delay and only ONE routing processor */ if (((queue *)pval(nd, nd_pq)->u.p)->q_len > 0) pkt->pk_time = ((Packet *)(((queue *)nd->nd_pq->u.p)->q_tail->qe_data))->pk_time + rt_process_time; else { pkt->pk_time = ev_now() + rt_process_time; ev_enqueue(EV_ROUTE_PROCESSING, (Component *)nd, (Component *)(nd->nd_ptr_routing_mod), pkt->pk_time, ((Component *) (nd->nd_ptr_routing_mod))->co_action, pkt, (caddr_t)NULL); } q_addt((queue *)pval(nd, nd_pq)->u.p, (caddr_t)pkt); log_param((Component *)nd, pval(nd, nd_pq)); occupy_space(nd, pkt); return((caddr_t)nd); } /* if the node is up and it is a transport packet for me */ /* This assumes that the transport packet is IMMEDIATELY passed */ /* without delay to the APTR */ if ((Nodee *)(pkt->pk_dest_socket.so_host) == nd) { ev_call(EV_APTR_RECEIVE, (Component *)nd, (Component *)pkt->pk_dest_socket.so_port, ((Component *)pkt->pk_dest_socket.so_port)->co_action, pkt, (caddr_t)NULL); return ((caddr_t)nd); } /* if the node is up and it is a transport packet destined for others */ if (EnoughSpace) { /* look for next hop in the routing table */ k = routing_table_look_up(nd, pkt); if (k < 0) { discard_pk(nd, pkt); return((caddr_t)nd); } l = (*(nd->nd_ptr_route_tab))[k].hop; n = find_neighbor(nd->nd_neighbors, l); if (!n) { /* next hop in routing table is not a neighbor */ /* Error in implementing the routing algorithm */ printf("Next hop [%s] in routing table is not a neighbor!!!\n", l ? l->co_name : "(nil)"); return((caddr_t)NULL); } k = index_in_local_top_table(nd, l); ticks = transmission_time_ticks(nd, pkt->pk_length, nd->loc_topology_table[k].l_bandwidth); /* This assumes infinite servers for the nodal delay (which includes */ /* the routing table consult time) and one server for transmission */ /* for each outgoing queue */ if (n->n_pq->q_len > 0 ) pkt->pk_time = max(pkt->pk_arrival_time + (nd->nd_delay->u.i/USECS_PER_TICK), ((Packet *)(n->n_pq->q_tail->qe_data))->pk_time) + ticks; else { pkt->pk_time = pkt->pk_arrival_time + nd->nd_delay->u.i/USECS_PER_TICK + ticks; ev_enqueue(EV_NODE_SEND, (Component *)nd, (Component *)nd, pkt->pk_time , nd->nd_action, (Packet *)NULL, (caddr_t)n); } q_addt(n->n_pq, (caddr_t)pkt); log_param((Component *)nd, n->n_p); update_ltt(nd, k, pkt->pk_length, 0, 0, 0); occupy_space(nd, pkt); } else /* there are not enough space */ discard_pk(nd, pkt); return((caddr_t)nd); } /*********************************************************/ /* Function discard_pk() drops a packet, retransmits it if it's a transport packet */ static void discard_pk(nd, pkt) Nodee *nd; Packet *pkt; { pval(nd, nd_dropped)->u.i++; log_param((Component *)nd, pval(nd, nd_dropped)); if (pkt->pk_type == TR_PACKET) ev_call(EV_APTR_RETRANSMIT, (Component *)nd, (Component *)pkt->pk_source_socket.so_port, ((Component *)pkt->pk_source_socket.so_port)->co_action, pkt, (caddr_t)NULL); else pk_free(pkt); } /****************************************/ static caddr_t nd_produce(nd, l, pkt) register Nodee *nd; register Component *l; register Packet *pkt; { register unsigned int ticks, process_delay; register Neighbor *n; register int k; char dummy[10]; pkt->pk_arrival_time = ev_now(); /* if the node is down drop the packet */ if (*(char *)(nd->nd_status->u.p) == 'D') { discard_pk(nd, pkt); return((caddr_t)nd); } /* The node is up */ if (!(EnoughSpace) && pkt->pk_type != ROUTE_PACKET) { discard_pk(nd, pkt); return((caddr_t)nd); } if (!(EnoughSpace) && pkt->pk_type == ROUTE_PACKET) { if (!(exist_data_space_to_replace(nd, pkt->pk_length))) { discard_pk(nd, pkt); return((caddr_t)nd); } } /* The node is up and there is enough space */ if (!l) { /* find correct link l from routing table */ process_delay = nd->nd_delay->u.i/USECS_PER_TICK; k = routing_table_look_up(nd, pkt); if (k < 0) { discard_pk(nd, pkt); return((caddr_t)nd); } l = (*(nd->nd_ptr_route_tab))[k].hop; } else process_delay = 0; n = find_neighbor(nd->nd_neighbors, l); if (!n) { /* Error */ printf("Next hop [%s] in routing table is not a neighbor!!!\n", l ? l->co_name : "(nil)"); return((caddr_t)NULL); } k = index_in_local_top_table(nd, l); ticks = transmission_time_ticks(nd, pkt->pk_length, nd->loc_topology_table[k].l_bandwidth); /* routing packet joins the outgoing queue without delay, only */ /* account for transmission since there is no routing table */ /* consultation time */ if ( (n->n_pq->q_len > 0) && (pkt->pk_type != ROUTE_PACKET) ) { pkt->pk_time = max(pkt->pk_arrival_time + nd->nd_delay->u.i/USECS_PER_TICK, ((Packet *)(n->n_pq->q_tail->qe_data))->pk_time) + ticks; q_addt(n->n_pq, (caddr_t)pkt); log_param((Component *)nd, n->n_p); } /* The following code is included to give priority to */ /* routing packets to be transmitted quickly */ if ( (n->n_pq->q_len > 0) && (pkt->pk_type == ROUTE_PACKET) ) give_route_pkt_priority(nd, n, pkt, ticks); if (n->n_pq->q_len == 0) { pkt->pk_time = ev_now() + process_delay + ticks; ev_enqueue(EV_NODE_SEND, (Component *)nd, (Component *)nd, pkt->pk_time , nd->nd_action, (Packet *)NULL, (caddr_t)n); q_addt(n->n_pq, (caddr_t)pkt); log_param((Component *)nd, n->n_p); } update_ltt(nd, k, pkt->pk_length, 0, 0, 0); occupy_space(nd, pkt); return((caddr_t)nd); } /****************************************/ static caddr_t nd_send(nd, n) register Nodee *nd; register Neighbor *n; { register Packet *pkt; register unsigned int time_value, processing_delay; register int k; pkt = (Packet *)q_deq(n->n_pq); log_param((Component *)nd, n->n_p); if (pkt->pk_type == ROUTE_PACKET) processing_delay = 0; else processing_delay = nd->nd_delay->u.i; k = index_in_local_top_table(nd, n->n_c); update_ltt(nd, k,-1 * pkt->pk_length, (unsigned)(ev_now() - pkt->pk_arrival_time), transmission_time_ticks(nd, pkt->pk_length, nd->loc_topology_table[k].l_bandwidth), processing_delay); fr_space(nd, pkt); ev_call(EV_LINK_SEND, (Component *)nd, (Component *)n->n_c, ((Component *)n->n_c)->co_action, pkt, (caddr_t)NULL); /* Schedule next send if the outgoing queue is non empty */ if (n->n_pq->q_len > 0) { time_value = ((Packet *)(n->n_pq->q_head->qe_data))->pk_time; ev_enqueue(EV_NODE_SEND, (Component *)nd, (Component *)nd, time_value, nd->nd_action, (Packet *)NULL, (caddr_t)n); } return((caddr_t)nd); } /****************************************/ static caddr_t nd_failure(nd, src) register Nodee *nd; register Component *src; { register Neighbor *n; register Packet *pkt; register unsigned int ticks; register int k; Packet *pkt1; if (play_flag && (Nodee *) src == nd) return (caddr_t) nd; pval(nd, nd_status)->u.p = "Down"; log_param((Component *)nd, pval(nd, nd_status)); /* Schedule repair if node itself caused it */ if (src == (Component *)nd) { ticks = ev_now() + (unsigned)((double)(time_to_repair(nd)) * 1000000.0 / USECS_PER_TICK); ev_enqueue(EV_NODE_REPAIR, (Component *)nd, (Component *)nd, ticks, nd->nd_action, (Packet *)NULL, (caddr_t)NULL); } /***** Assume when I'm down all outgoing links are down *****/ for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next) { if (n->n_c->co_class == LINK_CLASS) { ev_call(EV_LINK_FAILURE, (Component *)nd, (Component *)n->n_c, ((Component *)n->n_c)->co_action, (Packet *)NULL, (caddr_t)NULL); } } pval(nd, nd_curr_buffer_space)->u.i = 0; /* Assume a packet being transmitted is not lost when the node fails */ /* It will be dropped by the link anyway! */ for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next) { if (n->n_c->co_class == LINK_CLASS) { /* Empty outgoing queues */ pkt1 = (Packet *)q_deq(n->n_pq); while (pkt = (Packet *)q_deq(n->n_pq)) discard_pk(nd, pkt); k = index_in_local_top_table(nd, n->n_c); nd->loc_topology_table[k].avg_queue_size = 0; nd->loc_topology_table[k].last_utilization = 0.0; nd->loc_topology_table[k].queue_size = 0; nd->loc_topology_table[k].tot_queue_size = 0; nd->loc_topology_table[k].last_op_time = ev_now(); nd->loc_topology_table[k].total_delay = 0.0; nd->loc_topology_table[k].total_trans_queuing_delay = 0.0; nd->loc_topology_table[k].total_tr_delay = 0.0; nd->loc_topology_table[k].ave_delay =nd->loc_topology_table[k].l_delay + nd->nd_delay->u.i; nd->loc_topology_table[k].no_of_packets = 0; nd->loc_topology_table[k].total_util = 0; nd->loc_topology_table[k].ave_util = 0.0; nd->loc_topology_table[k].l_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].delay_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].util_cost = lcostfcn_adr->minimum->u.i; nd->loc_topology_table[k].hndly_cost = lcostfcn_adr->minimum->u.i; if (pkt1) { q_addh(n->n_pq, (caddr_t)pkt1); (pval(nd, nd_curr_buffer_space)->u.i) += pkt1->pk_length; k = index_in_local_top_table(nd, n->n_c); nd->loc_topology_table[k].queue_size = pkt1->pk_length; } log_param((Component *)nd, n->n_p); } } /* Assume the routing packet currently being processed is not lost when the node fails */ pkt1 = (Packet *)q_deq((queue *)pval(nd, nd_pq)->u.p); /* Empty the routing packet queue */ while (pkt = (Packet *)(q_deq((queue *)pval(nd, nd_pq)->u.p))) discard_pk(nd, pkt); if (pkt1) { q_addh((queue *)pval(nd, nd_pq)->u.p, (caddr_t)pkt1); (pval(nd, nd_curr_buffer_space)->u.i) += pkt1->pk_length; } pkt = pk_alloc(); (pkt->rt_pk).rt_type = ROUTE_PACKET; pkt->pk_type = RT_NODE_SHUTDOWN; /* shutdown packet */ pkt->pk_length = 20; /*** ???? ***/ q_addt((queue *)pval(nd, nd_pq)->u.p, (caddr_t)pkt); log_param((Component *)nd, pval(nd, nd_pq)); occupy_space(nd, pkt); if (pkt1) pkt->pk_time = pkt1->pk_time; else { pkt->pk_time = ev_now(); ev_call(EV_ROUTE_PROCESSING, (Component *)nd, (Component *)(nd->nd_ptr_routing_mod), ((Component *)(nd->nd_ptr_routing_mod))->co_action, pkt, (caddr_t)NULL); } return((caddr_t)nd); } /***********************************/ static caddr_t nd_repair(nd, src) register Nodee *nd; register Component *src; { register Packet *pkt; register unsigned int ticks; register Neighbor *n; if (play_flag && (Nodee *) src == nd) return (caddr_t) nd; pval(nd, nd_status)->u.p = "Up"; log_param((Component *)nd, pval(nd, nd_status)); /* Schedule next failure if node itself caused it */ if (src == (Component *)nd) { ticks = (unsigned)((double)(time_to_fail(nd)) * 1000000.0 / USECS_PER_TICK); ev_enqueue(EV_NODE_FAILURE, (Component *)nd, (Component *)nd, ticks+ev_now(), nd->nd_action, (Packet *)NULL, (caddr_t)NULL); } pkt = pk_alloc(); (pkt->rt_pk).rt_type = ROUTE_PACKET; pkt->pk_type = RT_NODE_WAKEUP ; /* startup packet */ pkt->pk_length = 20; /***** ???? *****/ pkt->pk_time = ev_now(); q_addt((queue *)pval(nd, nd_pq)->u.p, (caddr_t)pkt); log_param((Component *)nd, pval(nd, nd_pq)); occupy_space(nd, pkt); ev_call(EV_ROUTE_PROCESSING, (Component *)nd, (Component *)(nd->nd_ptr_routing_mod), ((Component *)(nd->nd_ptr_routing_mod))->co_action, pkt, (caddr_t)NULL); /*** I'm up, inform all outgoing links ***/ for (n = (Neighbor *)nd->nd_neighbors->l_head; n; n = n->n_next) { if (n->n_c->co_class == LINK_CLASS) { ev_call(EV_LINK_REPAIR, (Component *)nd, (Component *)n->n_c, ((Component *)n->n_c)->co_action, (Packet *)NULL, (caddr_t)NULL); } } return((caddr_t)nd); } /****************************************************/ /* This function returns a value of -1 if the destination is not found in the routing table or if the destination is found in the routing table but it is unreachable. Or, the function returns the index in the routing table (i.e. a value >= 0) if preferred neighbor exists in the routing table */ static int routing_table_look_up(nd, pkt) register Nodee *nd; register Packet *pkt; { register RoutingTable *ptr_route_tab; register int i; ptr_route_tab = (RoutingTable *)(nd->nd_ptr_route_tab); for (i = 0; i < ((Routet *)(nd->nd_ptr_routing_mod))->no_of_nodes && ((*ptr_route_tab)[i].dest != pkt->pk_dest_socket.so_host); i++) ; if (i == ((Routet *)(nd->nd_ptr_routing_mod))->no_of_nodes) { /* destination not found in the table */ return -1; } if (! (*ptr_route_tab)[i].hop) { /* destination unreachable */ return -1; } return i; } /*************************************************/ /* The function returns transmission time in ticks */ static unsigned int transmission_time_ticks(nd, PktLength, LinkBandwidth) Nodee *nd; int PktLength; int LinkBandwidth; { unsigned int ticks; /* Assume that the link bandwidth is in bytes/sec, and packet length in bytes */ ticks = (unsigned) (((double)(PktLength) * 1000000.0 / LinkBandwidth) / USECS_PER_TICK); return ticks; } /*************************************************/ static int index_in_local_top_table(nd, link) register Nodee *nd; register Component *link; { register int i; i = 0; while (nd->loc_topology_table[i].n_link != link) i++; return i; } /***********************************/ /* The following code inserts the routing packet in the head of the outgoing queue (after the packet being processed). Also, it updates pk_time (the time the packet will be send) to reflect the transmission time of the routing packet which is now ahead, for packets already in the outgoing queue */ static void give_route_pkt_priority(nd, n, pkt, ticks) register Nodee *nd; register Neighbor *n; /* points to the outgoing queue */ register Packet *pkt; /* points to the routing packet */ register unsigned int ticks; /* time to transmit routing pkt */ { q_elt *ptr1, *ptr2; unsigned int time; Packet *pkt1; ptr1 = ((queue *)(n->n_pq))->q_head; ptr2 = (((queue *)(n->n_pq))->q_head)->qe_next; while (ptr2 && ((Packet *)(ptr2->qe_data))->pk_type == ROUTE_PACKET) { ptr1 = ptr2; ptr2 = ptr2->qe_next; } pkt->pk_time = ((Packet *)(ptr1->qe_data))->pk_time + ticks; ptr1 = q_adda((queue *)n->n_pq, (Packet *)(ptr1->qe_data), (Packet *)pkt); log_param((Component *)nd, n->n_p); while (ptr2) { pkt1 = (Packet *)(ptr2->qe_data); pkt1->pk_time = max(pkt1->pk_arrival_time + nd->nd_delay->u.i/USECS_PER_TICK, ((Packet *)(ptr1->qe_data))->pk_time) + transmission_time_ticks(nd, pkt1->pk_length, ((Link *)n->n_c)->link_bandwidth->u.i); ptr1 = ptr2; ptr2 = ptr2->qe_next; } } /****************************************** The following function tries to make room to a routing packet when the node is full, by dropping data packet(s). Up to MAX_DATA_PKTS_REPLACED data packets could be dropped. */ static int exist_data_space_to_replace(nd, length) register Nodee *nd; register int length; /* length of the routing packet */ { int j, i, k; Neighbor *n; int space_needed; q_elt *ptr, *prev_ptr, *ptr1, *ptr2; Packet *pkt1; j = 0; space_needed = length; for (n = (Neighbor *)nd->nd_neighbors->l_head; n && (space_needed > 0); n = n->n_next) { if (n->n_c->co_class == LINK_CLASS && n->n_pq->q_len > 1) { /* Neighbor is a link and queue (excluding the one being transmitted) is not empty */ prev_ptr = (((queue *)(n->n_pq))->q_head); ptr = (((queue *)(n->n_pq))->q_head)->qe_next; do { while (ptr && ((Packet *)(ptr->qe_data))->pk_type == ROUTE_PACKET) { prev_ptr = ptr; ptr = ptr->qe_next; } if (ptr) { /* A data packet found */ if (j >= MAX_DATA_PKTS_REPLACED) return 0; /* unsuccessful */ space_needed -= (((Packet *)(ptr->qe_data))->pk_length); nd->data_elt[j] = ptr; nd->prev_data_elt[j] = prev_ptr; nd->which_queue[j]= n; j++; prev_ptr = ptr; ptr = ptr->qe_next; } } while (ptr && (space_needed > 0)); } } if (space_needed > 0) return 0; /* unsuccessful */ for (i = j - 1; i >= 0; i--) { (pval(nd, nd_curr_buffer_space)->u.i) -= (((Packet *)(nd->data_elt[i]->qe_data))->pk_length); qe_del(nd->which_queue[i]->n_pq, nd->data_elt[i]); k = index_in_local_top_table(nd, (Component *)(nd->which_queue[i]->n_c)); update_ltt(nd, k, -1 * ((Packet *)(nd->data_elt[i]->qe_data))->pk_length, 0, 0, 0); /* Should update departure time of following packets */ ptr1 = nd->prev_data_elt[i]; ptr2 = ptr1->qe_next; while (ptr2) { pkt1 = (Packet *)(ptr2->qe_data); pkt1->pk_time = max(pkt1->pk_arrival_time + nd->nd_delay->u.i/USECS_PER_TICK, ((Packet *)(ptr1->qe_data))->pk_time) + (unsigned) (((double)(pkt1->pk_length) * 1000000.0/ (((Link *)nd->which_queue[i]->n_c)->link_bandwidth->u.i)) / USECS_PER_TICK); ptr1 = ptr2; ptr2 = ptr2->qe_next; } discard_pk(nd, ((Packet *)(nd->data_elt[i]->qe_data))); } log_param((Component *)nd, pval(nd, nd_curr_buffer_space)); return 1; /* Successful */ } /*******************************************/ /* Function to be used by the routing module when it deques from the input routing packet in order to decrement the occupied node buffer space appropriately */ void fr_space(nd, pkt) Nodee *nd; Packet *pkt; { (pval(nd, nd_curr_buffer_space)->u.i) -= (pkt->pk_length); log_param((Component *)nd, pval(nd, nd_curr_buffer_space)); nd->memory_utl->u.d = fabs((double)(nd->nd_curr_buffer_space->u.i) / (double)(nd->nd_buffer_space->u.i)); log_param((Component *)nd, nd->memory_utl); log_param((Component *)nd, pval(nd, nd_pq)); } /**********************************************/ void occupy_space(nd, pkt) Nodee *nd; Packet *pkt; { (pval(nd, nd_curr_buffer_space)->u.i) += (pkt->pk_length); log_param((Component *)nd, pval(nd, nd_curr_buffer_space)); if (nd->nd_curr_buffer_space->u.i > nd->max_occupied_space->u.i) { nd->max_occupied_space->u.i = nd->nd_curr_buffer_space->u.i; log_param((Component *)nd, nd->max_occupied_space); } nd->memory_utl->u.d = fabs((double)(nd->nd_curr_buffer_space->u.i) / (double)(nd->nd_buffer_space->u.i)); log_param((Component *)nd, nd->memory_utl); } /********************************************/ update_ltt(nd, k, difference, delay, transmission_delay, processing_delay) Nodee *nd; int k; int difference; unsigned int delay; unsigned int transmission_delay, processing_delay; { if (nd->loc_topology_table[k].queue_size) nd->loc_topology_table[k].total_util += (ev_now() - nd->loc_topology_table[k].last_op_time); nd->loc_topology_table[k].tot_queue_size += nd->loc_topology_table[k].queue_size * (ev_now() - nd->loc_topology_table[k].last_op_time); nd->loc_topology_table[k].queue_size += difference; if (delay) { nd->loc_topology_table[k].total_delay += TICKS_TO_USECS(delay); nd->loc_topology_table[k].total_trans_queuing_delay += (TICKS_TO_USECS(delay) - processing_delay); nd->loc_topology_table[k].total_tr_delay += TICKS_TO_USECS(transmission_delay); nd->loc_topology_table[k].no_of_packets++; } nd->loc_topology_table[k].last_op_time = ev_now(); }