/* $Id: link.c,v 10.1 92/10/06 23:06:49 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. */ /* link.c */ #include #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 "link.h" #include "perf.h" #ifdef DEBUG extern Log debug_log; #endif static caddr_t link_util_update(); static caddr_t link_create(), link_delete(), link_start(), link_reset(), link_neighbor(), link_uneighbor(), link_send(), link_receive(), link_failure(), link_repair(); void pk_free(); caddr_t link_action(src, g, type, pkt, arg) Component *src; register Link *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 = link_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, "Link initialization called with non-null pointer."); #endif result = link_create((char *)arg); break; case EV_DEL: result = link_delete(g); break; case EV_NEIGHBOR: result = link_neighbor(g, (Component *)arg); break; case EV_UNEIGHBOR: result = link_uneighbor(g, (Component *)arg); break; case EV_START: result = link_start(g); break; case EV_STOP: result = (caddr_t)g; break; case EV_LINK_RECEIVE: result = link_receive(g, src, (queue *) arg); break; case EV_LINK_SEND: result = link_send(g, src, pkt); break; case EV_LINK_FAILURE: result = link_failure(g, src); break; case EV_LINK_REPAIR: result = link_repair(g, src); break; default: /* default includes EV_MK_PEER */ #ifdef DEBUG dbg_write(debug_log, DBG_ERR, (Component *)g, "got unexpected event of type %x", type); #endif break; } return(result); } /****************************************/ static caddr_t link_create(name) register char *name; { Link *newl; /* Memory for the component structure. */ newl = (Link *)sim_malloc(sizeof(Link)); /* First things first-- copy name into the new structure. */ strncpy(newl->link_name, name, 40); newl->link_neighbors = l_create(); newl->link_queue_1 = q_create(); newl->link_queue_2 = q_create(); newl->link_params = q_create(); newl->link_class = LINK_CLASS; newl->link_type = LINK; newl->link_action = link_action; newl->link_menu_up = FALSE; /* Initialize the parameters */ (void)param_init((Component *)newl, "Name", (PFD)NULL, make_name_text, make_short_name_text, param_input_name, 0, DisplayMask | InputMask, 0.0); newl->link_propagation_delay = param_init((Component *)newl, "Link propagation delay (USECS)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newl, link_propagation_delay)->u.i = 100; newl->link_bandwidth = param_init((Component *)newl, "Link bandwidth (bytes/sec)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newl, link_bandwidth)->u.i = 187500; newl->link_failure_time = param_init((Component *)newl, "Mean time btw failures (msecs)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newl, link_failure_time)->u.i = -1; newl->dist_failure = param_init((Component *)newl, "Interfailure dist (0=>EXP, 1=>UNIF)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newl, dist_failure)->u.i = 0; newl->sd_failure = param_init((Component *)newl, "Enter standard deviation if UNIF", (PFD)NULL, make_double_text, make_short_double_text, param_input_double, 0, DisplayMask | ModifyMask, 0.0); pval(newl, sd_failure)->u.d = 0; newl->link_repair_time = param_init((Component *)newl, "Mean time to repair (msecs)", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | ModifyMask, 0.0); pval(newl, link_repair_time)->u.i = 10; newl->dist_repair = param_init((Component *)newl, "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(newl, dist_repair)->u.i = 0; newl->sd_repair = param_init((Component *)newl, "Enter standard deviation if UNIF", (PFD)NULL, make_double_text, make_short_double_text, param_input_double, 0, DisplayMask | ModifyMask, 0.0); pval(newl, sd_repair)->u.d = 0; newl->link_status = param_init((Component *)newl, "Link status", (PFD)NULL, make_str_text, make_short_str_text, param_input_int, 0, DisplayMask | CanHaveLogMask, 0.0); pval(newl, link_status)->u.p = "Up"; newl->failure_status = param_init((Component *)newl, "Failure status", (PFD)NULL, make_int_text, make_short_int_text, param_input_int, 0, DisplayMask | CanHaveLogMask, 0.0); pval(newl, failure_status)->u.i = 0; newl->idata_util_1 = param_init((Component *)newl, "Inst. Data Util. ", double_calc, make_double_text, make_short_double_text, (PFI)NULL, BAR_GRAPH, CanHaveMeterMask | DisplayMask | CanHaveLogMask, 0.1); pval(newl, idata_util_1)->u.d = 0.0; newl->irout_util_1 = param_init((Component *)newl, "Inst. Rout. Util.", double_calc, make_double_text, make_short_double_text, (PFI)NULL, BAR_GRAPH, CanHaveMeterMask | DisplayMask | CanHaveLogMask, 0.1); pval(newl, irout_util_1)->u.d = 0.0; newl->idata_util_2 = param_init((Component *)newl, "Inst. Data Util. ", double_calc, make_double_text, make_short_double_text, (PFI)NULL, BAR_GRAPH, CanHaveMeterMask | DisplayMask | CanHaveLogMask, 0.1); pval(newl, idata_util_2)->u.d = 0.0; newl->irout_util_2 = param_init((Component *)newl, "Inst. Rout. Util.", double_calc, make_double_text, make_short_double_text, (PFI)NULL, BAR_GRAPH, CanHaveMeterMask | DisplayMask | CanHaveLogMask, 0.1); pval(newl, irout_util_2)->u.d = 0.0; #ifdef DEBUG dbg_write(debug_log, DBG_INFO, (Component *)newl, "link initialized"); #endif return((caddr_t)newl); } /****************************************/ static caddr_t link_delete(l) register Link *l; { lq_delete((list *)l->link_queue_1); lq_delete((list *)l->link_queue_2); comp_delete((Component *)l); return((caddr_t)l); } /****************************************/ static caddr_t link_reset(l) register Link *l; { pval(l, link_status)->u.p = "Up"; pval(l, failure_status)->u.i = 0; pval(l, idata_util_1)->u.d = 0.0; pval(l, irout_util_1)->u.d = 0.0; pval(l, idata_util_2)->u.d = 0.0; pval(l, irout_util_2)->u.d = 0.0; l->data_bytes_1 = 0; l->data_bytes_2 = 0; l->rout_bytes_1 = 0; l->rout_bytes_2 = 0; while (q_deq(l->link_queue_1)) ; while (q_deq(l->link_queue_2)) ; l->next_rcv_ev_1 = (Event *) NULL; l->next_rcv_ev_2 = (Event *) NULL; log_param((Component *) l, l->link_status); log_param((Component *) l, l->failure_status); log_param((Component *) l, l->idata_util_1); log_param((Component *) l, l->irout_util_1); log_param((Component *) l, l->idata_util_2); log_param((Component *) l, l->irout_util_2); return((caddr_t) l); } /****************************************/ static caddr_t link_neighbor(l, c) register Link *l; register Component *c; { caddr_t result; Param *p; char *name1, *name2; Neighbor *n; static char b[160]; result = (caddr_t)add_neighbor((Component *)l, c, 2, 1, NODE_CLASS); if (l->link_neighbors->l_len == 2){ /* The following four codeparts add the names of source and destination to every link */ /* Re-Initialization of the idata_util_1 parameters */ n = (Neighbor *)(l->link_neighbors->l_head); name1 = n->n_c->co_name; n = n->n_next; name2 = n->n_c->co_name; sprintf(b, "%s, %s->%s", l->idata_util_1->p_name, name1, name2); strncpy(l->idata_util_1->p_name, b, 40); l->idata_util_1->p_name[39] = 0; log_param((Component *)l, l->idata_util_1); /* Re-Initialization of the irout_util_1 parameters */ sprintf(b, "%s, %s->%s", l->irout_util_1->p_name, name1, name2); strncpy(l->irout_util_1->p_name, b, 40); l->irout_util_1->p_name[39] = 0; log_param((Component *)l, l->irout_util_1); /* Re-Initialization of the idata_util_2 parameters */ sprintf(b, "%s, %s->%s", l->idata_util_2->p_name, name2, name1); strncpy(l->idata_util_2->p_name, b, 40); l->idata_util_2->p_name[39] = 0; log_param((Component *)l, l->idata_util_2); /* Re-Initialization of the irout_util_2 parameters */ sprintf(b, "%s, %s->%s", l->irout_util_2->p_name, name2, name1); strncpy(l->irout_util_2->p_name, b, 40); l->irout_util_2->p_name[39] = 0; log_param((Component *)l, l->irout_util_2); } return result; } /****************************************/ static caddr_t link_uneighbor(l, c) register Link *l; register Component *c; { return((caddr_t)remove_neighbor((Component *)l, c)); } /****************************************/ /* returns time in msecs */ #define time_to_fail(l) (random_no(l->dist_failure->u.i, \ (l->link_failure_time->u.i < 200) ? 0.0 : \ (double) l->link_failure_time->u.i - 200, \ l->sd_failure->u.d, \ (unsigned) 1, \ (unsigned) 100000000) + 200) /****************************************/ #define time_to_repair(l) (random_no(l->dist_repair->u.i, \ (l->link_repair_time->u.i < 200) ? 0.0 : \ (double) l->link_repair_time->u.i - 200, \ l->sd_repair->u.d, \ (unsigned) 1, \ (unsigned) 100000000) + 200) /****************************************/ static caddr_t link_start(l) register Link *l; { register unsigned int ticks, time; /* Check if the link is properly connected */ if (l->link_neighbors->l_len != 2){ #ifdef DEBUG dbg_write ( debug_log, DBG_ERR, (Component *)l, "Link is not properly connected"); #endif return((caddr_t)NULL); } /* Calculate the max number of bytes in one time interval dt */ l->bytes_in_dt = (int) (( (double)(l->link_bandwidth->u.i) * (double) perf_update_dt_usecs ) / 1000000.0 ); /* Add the link to the list of components in the perf_module */ pm((Component *)l, LINK, NEW_COMPONENT, 0, 0, 0, 0); /* Schedule first link failure */ if (l->link_failure_time->u.i > 0) { ticks = MSECS_TO_TICKS(time_to_fail(l)); time = ev_now() + ticks; ev_enqueue (EV_LINK_FAILURE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)NULL ); } /* Something non-Null to return */ return ((caddr_t)l); } /*******************************************/ static caddr_t link_util_update(l, trigger) register Link *l; register int trigger; { int bytes; int type; q_elt *temp; Packet *pkt; /* link_util_update is used to update the number of received bytes in an event driven manner; version 2; Dec, 4 1990 */ if (trigger == 1) /* trigger determines which lq wants an update lq1 = 1; lq2 = 2 */ { /* Determine the size of the newly arrived packet */ temp = l->link_queue_1->q_tail; pkt = (Packet *)(temp->qe_data); bytes = pkt->pk_length; type = pkt->pk_type; /* Depending of the type of packet and the link which received it, increase the appropriate byte counter */ if (type == ROUTE_PACKET) /* Packet is routing packet */ l->rout_bytes_1 = l->rout_bytes_1 + bytes; else /* Packet must be data or ack packet */ l->data_bytes_1 = l->data_bytes_1 + bytes; } else { if (trigger == 2) { /* Determine the size of the newly arrived packet */ temp = l->link_queue_2->q_tail; pkt = (Packet *)(temp->qe_data); bytes = pkt->pk_length; type = pkt->pk_type; if (type == ROUTE_PACKET) /* Packet is routing packet */ l->rout_bytes_2 = l->rout_bytes_2 + bytes; else /* Packet must be data or ack packet */ l->data_bytes_2 = l->data_bytes_2 + bytes; } #ifdef DEBUG else dbg_write(debug_log, DBG_ERR, (Component *)l, "Link to be updated is non existent"); #endif } } /*******************************************/ static caddr_t link_send(l, src, pkt) register Link *l; register Component *src; register Packet *pkt; { register Component *c; register unsigned int time; /** normal sending procedure, link is up **/ if (*(char *)l->link_status->u.p == 'U'){ /* Arrival time at the next node is calculated */ time = ev_now() + (l->link_propagation_delay->u.i / USECS_PER_TICK) ; pkt->pk_time = time; /* Decision in which link queue to put the packet */ /* In order to make the above mentioned decision, I am using the following convention: The first neighbor in the link_neighbor list is the source for link_queue_1. Packets coming from the first neighbor therefore are appended to link_queue_2. The second neighbor is the source for link_queue_2. Packets coming from the second neighbor are put in link_queue_1. */ if (src != ((Component *)((Neighbor *)l->link_neighbors->l_head)->n_c)){ q_addt(l->link_queue_2, (caddr_t)pkt); link_util_update(l, 2); /* If there is only one packet in link_queue_2, we have to schedule the link_receive */ if (l->link_queue_2->q_len == 1) l->next_rcv_ev_2 = ev_enqueue(EV_LINK_RECEIVE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)l->link_queue_2); } else { q_addt(l->link_queue_1, (caddr_t)pkt); link_util_update(l, 1); /* If there is only one packet in link_queue_1, we have to schedule the link_receive */ if (l->link_queue_1->q_len == 1) l->next_rcv_ev_1 = ev_enqueue(EV_LINK_RECEIVE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)l->link_queue_1); } } else /** link is down; routing packets are discarded, APTR packets are retransmitted **/ if (pkt->pk_type == TR_PACKET) { c = (Component *)(pkt->pk_source_socket.so_port); ev_call(EV_APTR_RETRANSMIT, (Component *)l, c, c->co_action, pkt, (caddr_t)NULL); } else pk_free(pkt); return((caddr_t) l); } /************************************************************/ static caddr_t link_receive(l, src, arg) register Link *l; register Component *src; register queue *arg; { register Neighbor *n; register Component *c; register Packet *pkt; register unsigned int time; if (arg == l->link_queue_1){ /* packets in link_queue_1 are to be sent to the second neighbor */ pkt = (Packet *)q_deq(l->link_queue_1); n = (Neighbor *)(l->link_neighbors->l_head); c = n->n_next->n_c; ev_call(EV_NODE_RECEIVE, (Component *)l, c, c->co_action, pkt, (caddr_t)NULL); /* if link_queue_1 is not empty, the next link_receive has to be scheduled */ if (l->link_queue_1->q_len != 0){ time = ((Packet *)(l->link_queue_1->q_head->qe_data))->pk_time; l->next_rcv_ev_1 = ev_enqueue(EV_LINK_RECEIVE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)l->link_queue_1); } else l->next_rcv_ev_1 = (Event *) NULL; } if (arg == l->link_queue_2){ /* packets in link_queue_2 are to be sent to the first neighbor */ pkt = (Packet *)q_deq(l->link_queue_2); c = ((Neighbor *)(l->link_neighbors->l_head))->n_c; ev_call(EV_NODE_RECEIVE, (Component *)l, c, c->co_action, pkt, (caddr_t)NULL); /* if link_queue_2 is not empty, the next link_receive has to be scheduled */ if (l->link_queue_2->q_len != 0){ time = ((Packet *)(l->link_queue_2->q_head->qe_data))->pk_time; l->next_rcv_ev_2 = ev_enqueue(EV_LINK_RECEIVE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)l->link_queue_2); } else l->next_rcv_ev_2 = (Event *) NULL; } return((caddr_t) l); } /*************************************************************/ static caddr_t link_repair(l, src) register Link *l; register Component *src; { register Packet *pkt_1, *pkt_2; register unsigned int time, ticks; register int queue_flag; if (play_flag && l == (Link *)src) return (caddr_t) l; if (l == (Link *)src){ /* link repair caused by the link */ l->failure_status->u.i = l->failure_status->u.i - 1; ticks = MSECS_TO_TICKS(time_to_fail(l)); time = ticks + ev_now(); /* Schedule next link failure */ ev_enqueue (EV_LINK_FAILURE, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)NULL); } else /* link repair caused by an adjacent node */ l->failure_status->u.i = l->failure_status->u.i - 2; log_param((Component *)l, l->failure_status); /** If the link is totally up, schedule wakeup-packets **/ if (l->failure_status->u.i == 0){ pm((Component *)l, LINK, LINK_WAKEUP, 0, 0, 0, 0); /* wakeup-packet for the first neighbor node*/ pkt_1 = pk_alloc(); pkt_1->pk_type = ROUTE_PACKET; pkt_1->rt_pk.rt_type = RT_LINK_WAKEUP; pkt_1->pk_length = 50; pkt_1->pk_source_socket.so_host = (Component *) l; q_addt(l->link_queue_1, (caddr_t)pkt_1); ev_call (EV_LINK_RECEIVE, (Component *)l, (Component *)l, l->link_action, (Packet *)NULL, l->link_queue_1); /* wakeup-packet for the second neighbor node*/ pkt_2 = pk_alloc(); pkt_2->pk_type = ROUTE_PACKET; pkt_2->rt_pk.rt_type = RT_LINK_WAKEUP; pkt_2->pk_length = 50; pkt_2->pk_source_socket.so_host = (Component *) l; q_addt(l->link_queue_2, (caddr_t)pkt_2); ev_call (EV_LINK_RECEIVE, (Component *)l, (Component *)l, l->link_action, (Packet *)NULL, l->link_queue_2); l->link_status->u.p = "Up"; log_param((Component *)l, l->link_status); } return((caddr_t) l); } /**********************************************************/ static caddr_t link_failure(l, src) register Component *src; register Link *l; { register Packet *pkt_1, *pkt_2, *pkt; register Component *c; register unsigned int ticks, time; register int queue_flag; if (play_flag && l == (Link *) src) return (caddr_t) l; /* link is up and failed now */ if (*(char *)l->link_status->u.p == 'U'){ l->link_status->u.p = "Down"; pm((Component *)l, LINK, LINK_FAILURE, 0, 0, 0, 0); log_param((Component *)l, l->link_status); queue_flag = l->link_queue_1->q_len; /* Empty out link_queue_1 and retransmit APTR packets */ while ((pkt = (Packet *)q_deq(l->link_queue_1)) != NULL ){ if (pkt->pk_type == TR_PACKET){ c = (Component *)(pkt->pk_source_socket.so_port); ev_call(EV_APTR_RETRANSMIT, (Component *)l, c, c->co_action, pkt, (caddr_t)NULL); } else pk_free(pkt); } if (queue_flag) { ev_dequeue(l->next_rcv_ev_1); l->next_rcv_ev_1 = (Event *) NULL; } /* Produce shutdown packet and call link_receive */ pkt_1 = pk_alloc(); pkt_1->pk_type = ROUTE_PACKET; pkt_1->rt_pk.rt_type = RT_LINK_SHUTDOWN; pkt_1->pk_length = 50; pkt_1->pk_source_socket.so_host = (Component *) l; q_addh(l->link_queue_1, (caddr_t)pkt_1); ev_call(EV_LINK_RECEIVE, (Component *)l, (Component *)l, l->link_action, (Packet *)NULL, l->link_queue_1); queue_flag = l->link_queue_2->q_len; /* Empty out link_queue_2 and retransmit APTR packets */ while ((pkt = (Packet *)q_deq(l->link_queue_2)) != NULL ){ if (pkt->pk_type == TR_PACKET){ c = (Component *)(pkt->pk_source_socket.so_port); ev_call(EV_APTR_RETRANSMIT, (Component *)l, c, c->co_action, pkt, (caddr_t)NULL); } else pk_free(pkt); } if (queue_flag) { ev_dequeue(l->next_rcv_ev_2); l->next_rcv_ev_2 = (Event *) NULL; } /* Produce shutdown packet and call link_receive */ pkt_2 = pk_alloc(); pkt_2->pk_type = ROUTE_PACKET; pkt_2->rt_pk.rt_type = RT_LINK_SHUTDOWN; pkt_2->pk_length = 50; pkt_2->pk_source_socket.so_host = (Component *) l; q_addh(l->link_queue_2, (caddr_t)pkt_2); ev_call(EV_LINK_RECEIVE, (Component *)l, (Component *)l, l->link_action, (Packet *)NULL, l->link_queue_2); /** link fails because of link failure, schedule repair **/ if (l == (Link *)src){ l->failure_status->u.i = l->failure_status->u.i +1; ticks = MSECS_TO_TICKS(time_to_repair(l)); time = ev_now() + ticks; ev_enqueue(EV_LINK_REPAIR, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)NULL); } /** link fails because of node failure, no repair scheduled **/ else l->failure_status->u.i = l->failure_status->u.i + 2; return((caddr_t)l); } /** Link fails the second or third time **/ if (l == (Link *)src){ l->failure_status->u.i = l->failure_status->u.i +1; ticks = MSECS_TO_TICKS(time_to_repair(l)); time = ev_now() + ticks; ev_enqueue(EV_LINK_REPAIR, (Component *)l, (Component *)l, time, l->link_action, (Packet *)NULL, (caddr_t)NULL); } else l->failure_status->u.i = l->failure_status->u.i + 2; /** log the new failure status **/ log_param((Component *)l, l->failure_status); return((caddr_t) l); }