3 * The source code for the ntp discrete event simulator.
5 * Written By: Sachin Kamboj
6 * University of Delaware
9 * (Some code shamelessly based on the original NTP discrete event simulator)
15 #include "ntp_config.h"
17 /* forward prototypes */
18 int determine_event_ordering(const Event *e1, const Event *e2);
19 int determine_recv_buf_ordering(const struct recvbuf *b1,
20 const struct recvbuf *b2);
21 void create_server_associations(void);
22 void init_sim_io(void);
24 /* Global Variable Definitions */
25 sim_info simulation; /* Simulation Control Variables */
26 local_clock_info simclock; /* Local Clock Variables */
27 queue *event_queue; /* Event Queue */
28 queue *recv_queue; /* Receive Queue */
29 static double sys_residual = 0; /* adjustment residue (s) */
31 void (*event_ptr[]) (Event *) = {
32 sim_event_beep, sim_update_clocks, sim_event_timer, sim_event_recv_packet
33 }; /* Function pointer to the events */
37 * Define a function to compare two events to determine which one occurs
41 determine_event_ordering(
46 return (e1->time - e2->time);
51 * Define a function to compare two received packets to determine which
52 * one is received first.
55 determine_recv_buf_ordering(
56 const struct recvbuf *b1,
57 const struct recvbuf *b2
63 /* Simply convert the time received to double and subtract */
64 LFPTOD(&b1->recv_time, recv_time1);
65 LFPTOD(&b2->recv_time, recv_time2);
67 return (int)(recv_time1 - recv_time2);
71 /* Define a function to create the server associations */
72 void create_server_associations(void)
76 for (i = 0; i < simulation.num_of_servers; ++i) {
77 printf("%s\n", stoa(simulation.servers[i].addr));
78 if (peer_config(simulation.servers[i].addr,
89 NULL /* group ident */) == 0) {
91 "ERROR!! Could not create association for: %s\n",
92 stoa(simulation.servers[i].addr));
98 /* Main Simulator Code */
109 /* Initialize the local Clock */
110 simclock.local_time = 0;
112 simclock.slew = 500e-6;
114 /* Initialize the simulation */
115 simulation.num_of_servers = 0;
116 simulation.beep_delay = BEEP_DLY;
117 simulation.sim_time = 0;
118 simulation.end_time = SIM_TIME;
120 /* Initialize ntp modules */
137 /* Call getconfig to parse the configuration file */
138 getconfig(argc, argv);
139 loop_config(LOOP_DRIFTINIT, 0);
140 initializing = FALSE;
143 * Watch out here, we want the real time, not the silly stuff.
145 gettimeofday(&seed, NULL);
146 ntp_srandom(seed.tv_usec);
148 /* Initialize the event queue */
149 event_queue = create_priority_queue((q_order_func)
150 determine_event_ordering);
152 /* Initialize the receive queue */
153 recv_queue = create_priority_queue((q_order_func)
154 determine_recv_buf_ordering);
156 /* Push a beep and a timer on the event queue */
157 enqueue(event_queue, event(0, BEEP));
158 enqueue(event_queue, event(simulation.sim_time + 1.0, TIMER));
161 * Pop the queue until nothing is left or time is exceeded
163 /* maxtime = simulation.sim_time + simulation.end_time;*/
164 while (simulation.sim_time <= simulation.end_time &&
165 (!empty(event_queue))) {
166 curr_event = dequeue(event_queue);
167 /* Update all the clocks to the time on the event */
168 sim_update_clocks(curr_event);
170 /* Execute the function associated with the event */
171 (*event_ptr[curr_event->function])(curr_event);
172 free_node(curr_event);
174 printf("sys_received: %lu\n", sys_received);
175 printf("sys_badlength: %lu\n", sys_badlength);
176 printf("sys_declined: %lu\n", sys_declined);
177 printf("sys_restricted: %lu\n", sys_restricted);
178 printf("sys_newversion: %lu\n", sys_newversion);
179 printf("sys_oldversion: %lu\n", sys_oldversion);
180 printf("sys_limitrejected: %lu\n", sys_limitrejected);
181 printf("sys_badauth: %lu\n", sys_badauth);
190 loopback_interface = emalloc_zero(sizeof(*loopback_interface));
191 ep_list = loopback_interface;
192 strlcpy(loopback_interface->name, "IPv4loop",
193 sizeof(loopback_interface->name));
194 loopback_interface->flags = INT_UP | INT_LOOPBACK;
195 loopback_interface->fd = -1;
196 loopback_interface->bfd = -1;
197 loopback_interface->ifnum = 1;
198 loopback_interface->family = AF_INET;
199 AF(&loopback_interface->sin) = AF_INET;
200 SET_ADDR4(&loopback_interface->sin, LOOPBACKADR);
201 SET_PORT(&loopback_interface->sin, NTP_PORT);
202 AF(&loopback_interface->mask) = AF_INET;
203 SET_ADDR4(&loopback_interface->mask, LOOPNETMASK);
207 /* Define a function to create an return an Event */
209 Event *event(double t, funcTkn f)
213 if ((e = get_node(sizeof(*e))) == NULL)
214 abortsim("get_node failed in event");
220 /* NTP SIMULATION FUNCTIONS */
222 /* Define a function for processing a timer interrupt.
223 * On every timer interrupt, call the NTP timer to send packets and process
224 * the clock and then call the receive function to receive packets.
226 void sim_event_timer(Event *e)
228 struct recvbuf *rbuf;
230 /* Call the NTP timer.
231 * This will be responsible for actually "sending the packets."
232 * Since this is a simulation, the packets sent over the network
233 * will be processed by the simulate_server routine below.
237 /* Process received buffers */
238 while (!empty(recv_queue)) {
239 rbuf = (struct recvbuf *)dequeue(recv_queue);
240 (*rbuf->receiver)(rbuf);
244 /* Arm the next timer interrupt. */
246 event(simulation.sim_time + (1 << EVENT_TIMEOUT), TIMER));
251 /* Define a function to simulate a server.
252 * This function processes the sent packet according to the server script,
253 * creates a reply packet and pushes the reply packet onto the event queue
256 sockaddr_u *serv_addr, /* Address of the server */
257 endpt * inter, /* Interface on which the reply should
259 struct pkt *rpkt /* Packet sent to the server that
260 needs to be processed. */
263 struct pkt xpkt; /* Packet to be transmitted back
265 struct recvbuf rbuf; /* Buffer for the received packet */
266 Event *e; /* Packet receive event */
267 server_info *server; /* Pointer to the server being simulated */
268 script_info *curr_script; /* Current script being processed */
270 double d1, d2, d3; /* Delays while the packet is enroute */
271 double t1, t2, t3, t4; /* The four timestamps in the packet */
272 l_fp lfp_host; /* host-order l_fp */
277 /* Search for the server with the desired address */
279 for (i = 0; i < simulation.num_of_servers; ++i) {
280 if (memcmp(simulation.servers[i].addr, serv_addr,
281 sizeof(*serv_addr)) == 0) {
282 server = &simulation.servers[i];
287 fprintf(stderr, "Received packet from %s on %s\n",
288 stoa(serv_addr), latoa(inter));
290 abortsim("Server with specified address not found!!!");
292 /* Get the current script for the server */
293 curr_script = server->curr_script;
295 /* Create a server reply packet.
296 * Masquerade the reply as a stratum-1 server with a GPS clock
298 xpkt.li_vn_mode = PKT_LI_VN_MODE(LEAP_NOWARNING, NTP_VERSION,
300 xpkt.stratum = STRATUM_TO_PKT(((u_char)1));
301 memcpy(&xpkt.refid, "GPS", 4);
302 xpkt.ppoll = rpkt->ppoll;
303 xpkt.precision = rpkt->precision;
307 /* TIMESTAMP CALCULATIONS
312 t2 ----------------- t3
315 /* Compute the delays */
316 d1 = poisson(curr_script->prop_delay, curr_script->jitter);
317 d2 = poisson(curr_script->proc_delay, 0);
318 d3 = poisson(curr_script->prop_delay, curr_script->jitter);
320 /* Note: In the transmitted packet:
321 * 1. t1 and t4 are times in the client according to the local clock.
322 * 2. t2 and t3 are server times according to the simulated server.
323 * Compute t1, t2, t3 and t4
324 * Note: This function is called at time t1.
327 NTOHL_FP(&rpkt->xmt, &lfp_host);
328 LFPTOD(&lfp_host, t1);
329 t2 = server->server_time + d1;
330 t3 = server->server_time + d1 + d2;
331 t4 = t1 + d1 + d2 + d3;
333 /* Save the timestamps */
334 xpkt.org = rpkt->xmt;
335 DTOLFP(t2, &lfp_host);
336 HTONL_FP(&lfp_host, &xpkt.rec);
337 DTOLFP(t3, &lfp_host);
338 HTONL_FP(&lfp_host, &xpkt.xmt);
339 xpkt.reftime = xpkt.xmt;
342 * Ok, we are done with the packet. Now initialize the receive
343 * buffer for the packet.
346 rbuf.receiver = &receive; /* callback to process the packet */
347 rbuf.recv_length = LEN_PKT_NOMAC;
348 rbuf.recv_pkt = xpkt;
351 memcpy(&rbuf.srcadr, serv_addr, sizeof(rbuf.srcadr));
352 memcpy(&rbuf.recv_srcadr, serv_addr, sizeof(rbuf.recv_srcadr));
355 * Create a packet event and insert it onto the event_queue at the
356 * arrival time (t4) of the packet at the client
358 e = event(t4, PACKET);
360 enqueue(event_queue, e);
363 * Check if the time of the script has expired. If yes, delete it.
365 if (curr_script->duration > simulation.sim_time &&
366 NULL == HEAD_PFIFO(server->script)) {
369 * For some reason freeing up the curr_script memory kills the
370 * simulation. Further debugging is needed to determine why.
373 UNLINK_FIFO(curr_script, *server->script, link);
380 /* Define a function to update all the clocks
381 * Most of the code is modified from the systime.c file by Prof. Mills
384 void sim_update_clocks(Event *e)
390 /* Compute the time between the last update event and this update */
391 time_gap = e->time - simulation.sim_time;
394 printf("WARNING: e->time %.6g comes before sim_time %.6g (gap %+.6g)\n",
395 e->time, simulation.sim_time, time_gap);
397 /* Advance the client clock */
398 if (e->time + time_gap < simclock.local_time)
399 printf("WARNING: e->time + gap %.6g comes before local_time %.6g\n",
400 e->time + time_gap, simclock.local_time);
401 simclock.local_time = e->time + time_gap;
403 /* Advance the simulation time */
404 simulation.sim_time = e->time;
406 /* Advance the server clocks adjusted for systematic and random frequency
407 * errors. The random error is a random walk computed as the
408 * integral of samples from a Gaussian distribution.
410 for (i = 0; i < simulation.num_of_servers; ++i) {
411 simulation.servers[i].curr_script->freq_offset +=
412 gauss(0, time_gap * simulation.servers[i].curr_script->wander);
414 simulation.servers[i].server_time += time_gap *
415 (1 + simulation.servers[i].curr_script->freq_offset);
418 /* Perform the adjtime() function. If the adjustment completed
419 * in the previous interval, amortize the entire amount; if not,
420 * carry the leftover to the next interval.
423 adj = time_gap * simclock.slew;
424 if (adj < fabs(simclock.adj)) {
425 if (simclock.adj < 0) {
427 simclock.local_time -= adj;
430 simclock.local_time += adj;
433 simclock.local_time += simclock.adj;
439 /* Define a function that processes a receive packet event.
440 * This function simply inserts the packet received onto the receive queue
443 void sim_event_recv_packet(Event *e)
445 struct recvbuf *rbuf;
447 /* Allocate a receive buffer and copy the packet to it */
448 if ((rbuf = get_node(sizeof(*rbuf))) == NULL)
449 abortsim("get_node failed in sim_event_recv_packet");
450 memcpy(rbuf, &e->rcv_buf, sizeof(*rbuf));
452 /* Store the local time in the received packet */
453 DTOLFP(simclock.local_time, &rbuf->recv_time);
455 /* Insert the packet received onto the receive queue */
456 enqueue(recv_queue, rbuf);
461 /* Define a function to output simulation statistics on a beep event
464 /*** TODO: Need to decide on how to output for multiple servers ***/
465 void sim_event_beep(Event *e)
468 static int first_time = 1;
469 char *dash = "-----------------";
472 fprintf(stderr, "BEEP!!!\n");
473 enqueue(event_queue, event(e->time + simulation.beep_delay, BEEP));
475 if(simulation.beep_delay > 0) {
477 printf("\t%4c T %4c\t%4c T+ERR %3c\t%5cT+ERR+NTP\n",
478 ' ', ' ', ' ', ' ',' ');
479 printf("\t%s\t%s\t%s\n", dash, dash, dash);
482 printf("\t%16.6f\t%16.6f\t%16.6f\n",
483 n->time, n->clk_time, n->ntp_time);
486 printf("\t%16.6f\t%16.6f\t%16.6f\n",
488 n->time, n->clk_time, n->ntp_time);
494 /* Define a function to abort the simulation on an error and spit out an
498 void abortsim(char *errmsg)
506 /* CODE ORIGINALLY IN libntp/systime.c
507 * -----------------------------------
508 * This code was a part of the original NTP simulator and originally
509 * had its home in the libntp/systime.c file.
511 * It has been shamelessly moved to here and has been modified for the
512 * purposes of the current simulator.
517 * get_systime - return the system time in NTP timestamp format
521 l_fp *now /* current system time in l_fp */ )
524 * To fool the code that determines the local clock precision,
525 * we advance the clock a minimum of 200 nanoseconds on every
526 * clock read. This is appropriate for a typical modern machine
527 * with nanosecond clocks. Note we make no attempt here to
528 * simulate reading error, since the error is so small. This may
529 * change when the need comes to implement picosecond clocks.
531 if (simclock.local_time == simclock.last_read_time)
532 simclock.local_time += 200e-9;
534 simclock.last_read_time = simclock.local_time;
535 DTOLFP(simclock.local_time, now);
537 if (ntp_node.ntp_time == ntp_node.last_time)
538 ntp_node.ntp_time += 200e-9;
539 ntp_node.last_time = ntp_node.ntp_time;
540 DTOLFP(ntp_node.ntp_time, now);
546 * adj_systime - advance or retard the system clock exactly like the
549 int /* always succeeds */
551 double now /* time adjustment (s) */
554 struct timeval adjtv; /* new adjustment */
560 * Most Unix adjtime() implementations adjust the system clock
561 * in microsecond quanta, but some adjust in 10-ms quanta. We
562 * carefully round the adjustment to the nearest quantum, then
563 * adjust in quanta and keep the residue for later.
565 dtemp = now + sys_residual;
570 adjtv.tv_sec = (long)dtemp;
571 dtemp -= adjtv.tv_sec;
572 ticks = (long)(dtemp / sys_tick + .5);
573 adjtv.tv_usec = (long)(ticks * sys_tick * 1e6);
574 dtemp -= adjtv.tv_usec / 1e6;
575 sys_residual = dtemp;
578 * Convert to signed seconds and microseconds for the Unix
579 * adjtime() system call. Note we purposely lose the adjtime()
583 adjtv.tv_sec = -adjtv.tv_sec;
584 adjtv.tv_usec = -adjtv.tv_usec;
585 sys_residual = -sys_residual;
588 /* ntp_node.adj = now; */
594 * step_systime - step the system clock. We are religious here.
596 int /* always succeeds */
598 double now /* step adjustment (s) */
603 printf("step_systime: time %.6f adj %.6f\n",
604 simclock.local_time, now);
606 simclock.local_time += now;
611 * gauss() - returns samples from a gaussion distribution
613 double /* Gaussian sample */
615 double m, /* sample mean */
616 double s /* sample standard deviation (sigma) */
622 * Roll a sample from a Gaussian distribution with mean m and
623 * standard deviation s. For m = 0, s = 1, mean(y) = 0,
628 while ((q1 = drand48()) == 0)
629 /* empty statement */;
631 return (m + s * sqrt(-2. * log(q1)) * cos(2. * PI * q2));
636 * poisson() - returns samples from a network delay distribution
638 double /* delay sample (s) */
640 double m, /* fixed propagation delay (s) */
641 double s /* exponential parameter (mu) */
647 * Roll a sample from a composite distribution with propagation
648 * delay m and exponential distribution time with parameter s.
649 * For m = 0, s = 1, mean(y) = std(y) = 1.
653 while ((q1 = drand48()) == 0)
654 /* empty statement */;
655 return (m - s * log(q1 * s));