/* * Implementation exercise 3: CSMA/CD: Transmission medium * * An Engineering Approach to Computer Networking * * S. Keshav * */ /* * ARGS USED: diameter * * Simuates a shared medium like Ethernet. The diameter is the maximum end to * end propagation delay. * * This node exactly simulates a broadcast medium with a 'master' node that has a * point to point link to every other station. At start up, the master * comes up with a random set of distances between it and each node. * The delay in sending a packet from node_1 to node_2 is * | delay_to_node_1 - delay_to_node_2 |. * Messages placed on the "medium" are delivered to the * stations (called slave) after the corresponding delay. * Actually, only the edge from the master to a slave node has a delay * associated with it, the slave to master direction has zero delay, so * that the master knows about a packet instantaneously. To do this * cleanly, the packet size is carried in the pkt->proto_flag field, * instead of in the size field. */ #include "../kernel/real.h" extern int CSMA_DEBUG; extern struct graph *Graph; /* simulation input */ extern float diameter; /* from input file */ extern float weight[MAX_NODES +1][MAX_NODES +1]; #define JAM_TIME 0.05 /* 50 ms */ #define TIMER1 16 #define TIMER2 17 #define TIMER3 18 #define TIMER4 19 #define moddiff(x,y) (((x)>(y))?((x)-(y)):((y)-(x))) /* stores all the state associated with the medium */ struct medium_state { int medium_busy; struct { long weight; /* distance from master to this node */ } nbr[MAX_NODES + 1]; } ; ecn_master() { PKT_PTR pkt, cpkt; int i, node; ident destn, sender, sink; long key, delay; timev now; gredgeptr edge; struct medium_state m; int pkt_size; /* pkt_size of packet being transmitted */ int pkt_source; /* source of the packet transmitted */ int pkt_dest; /* destination of packet transmitted */ int nacks_sent = 0; /* have nacks already been sent? */ timev data_pkt_time; int count = 0; node = get_node_id(); printf("Node %d: CSMA medium master\n", node); source_node_type[node] = ROUTER; sink = assigned_sink[node]; m.medium_busy = 0; /* initialize weight array to 0 */ for(i = 1; i <= MAX_NODES; i++) m.nbr[i].weight = -1; /* * Discover all the stations on the segment, and assign them a random * distance from the master. The distance between two nodes is the difference * of their distances from the master. */ edge = Graph->edges; while (edge isnt 0) { int n1, n2; long weight; /* n1 and n2 are the ids of the nodes at each end */ n1 = edge->node1->nodedata->nodeid; n2 = edge->node2->nodedata->nodeid; /* we only add latency to the edge from the master to slave */ /* so master instantaneously knows of packet placed on wire */ if((n1 is node) or (n2 is node)) { switch (count) { case 0: weight = 0; count++; break; case 1: weight = (long)(diameter * MILLION); count ++; break; default: weight = (long) (RANDOM * diameter * MILLION); } diameter = diameter; printf("Master selected delay %d microseconds on edge %d --> %d\n", weight, n1, n2); if (n1 is node) m.nbr[n2].weight = weight; else m.nbr[n1].weight = weight; } edge = edge->next; } /* sit in an infinite loop, waiting for packets */ for (ever) { sender = recvm(&destn, &key, &pkt); if(CSMA_DEBUG) pkt_print(pkt); now = runtime(); switch (pkt->type) { case DATA: nacks_sent = 0; if ((not m.medium_busy) or (m.medium_busy and pkt_source is pkt->source)) { /* medium was idle or previous packet from this source.*/ m.medium_busy = 1; /* save packet size and source, then destroy original pkt */ pkt_size = pkt->proto_flag; /* source saved it here */ pkt_source = pkt->source; pkt_dest = pkt->dest; data_pkt_time = now; free(pkt); /* send a BUSY message to all neighbors */ tell_all(m, BUSY, pkt_source); /* set a timer to send idle after packet transmission time */ make_pkt(pkt); pkt->type = TIMER1; set_timer((float)(pkt_size * 8 / line_speeds[node][pkt_source]), pkt); } else { /* collision: jam the network by sending * NACKs to all nodes */ timev diff; float delay; diff = time_minus(now, data_pkt_time); delay = 1e-6 * (float)(moddiff(m.nbr[pkt_source].weight, m.nbr[pkt->source].weight)); delay = delay - make_float(diff); pkt_source = pkt->source; pkt->type = TIMER3; /* horrible hack */ if(delay < 0) delay = 0; set_timer(delay, pkt); } make_plot("busy", 0); make_plot("busy", 10); break; case TIMER1: /* send an IDLE packet to all nodes, but dont make medium idle yet */ if(not nacks_sent) { tell_all(m, IDLE, pkt_source); make_pkt(pkt); pkt->type = TIMER2; set_timer(diameter, pkt); } break; case TIMER2: make_plot("busy", 10); make_plot("busy", 0); free(pkt); m.medium_busy = 0; break; case TIMER3: /* send a NACK packet to all nodes */ /* this is a little conservative: actually, the nodes could have * heard sooner */ tell_all(m, NACK, pkt_source); /* set a timer to send idle after jam time */ pkt->type = TIMER4; set_timer(diameter, pkt); break; case TIMER4: /* send an IDLE packet to all nodes and make medium idle */ tell_all(m, IDLE, pkt_source); make_plot("busy", 10); make_plot("busy", 0); free(pkt); m.medium_busy = 0; nacks_sent = 1; break; case INT: free(pkt); break; default: printf("pkt->type %d, pkt->so %d, pkt->dest %d\n", pkt->type, pkt->source, pkt->dest); pr_error("source received a pkt of unknown type", node); } } } /* this function sends a packet to all nodes after the correct delay */ static int tell_all(m, type, source) struct medium_state m; int type, source; { int i, node = get_node_id(); PKT_PTR pkt; timev now; float edge_weight; now = runtime(); /* tweak the link delay for each edge as the mod difference in delays */ for (i = 1; i <= MAX_NODES; i++) { if(m.nbr[i].weight isnt -1) { edge_weight = moddiff(m.nbr[i].weight, m.nbr[source].weight); weight[node][i] = edge_weight; make_pkt(pkt); pkt->type = type; pkt->size = 0; pkt->dest = i; if(CSMA_DEBUG) printf("(%f) Node %d sending %s pkt to node %d\n", make_float(now), node, pkt_types[pkt->type], i); send_pkt(pkt); } } }