#!/usr/bin/awk -f
# “FIXCLOCK” COPYRIGHT NOTICE, LICENSE AND DISCLAIMER. # # Copyright 2002 by Raphael S. Ryger, Dept. of Computer Science, Yale University # # Permission to use, copy, modify, and distribute this software and its # documentation for any purpose and without fee is hereby granted, provided # that the above copyright notice appear in all copies and that both the # copyright notice and this permission notice and warranty disclaimer appear # in supporting documentation, and that the name of the author not be used # in advertising or publicity pertaining to distribution of the software # without specific, written prior permission. # # The author disclaims all warranties with regard to this software, including # all implied warranties of merchantability and fitness. In no event shall he # 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.
# Usage: fixclock <datafile> # # The behavior of this script is modulated by parameters derived from the # command line, else from the environment, else from the defaults following. # (In sh and ksh, environment variable settings may be prepended in the command # line to the invocation of the script, to apply only to that invocation.) # parameter default # ——— ——- # parsing group: # datalinepattern null (effectively, all lines) # pastdatapattern null (effectively, no such line) # fieldseparator null (effectively, whitespace) # hostfieldnum null (effectively, all data lines) # sentfieldnum must be specified # receivedfieldnum must be specified # bouncedfieldnum must be specified # target extracted from (the string) <datafile> # # tuning group: # segmentsecs 12 # intrastretchmaxerr 2 # interstretchmaxerr 10 # sourceskew 0 # # verbosity group (binary values: null or 0 is false; else true): # showall null # showtarget null # showreadings null # showminima null # showintrastretchtests null # showonewaystretches null # showstdroundtrips null # showquality null # showcompositestretches null # showregions null # showcoverage null # # data file side effects: # writefixeddir null # writeorigfixedplotdir null # # Notes on parameters: # datalinepattern AWK pattern picking out the data lines. The data lines # need not be successive. # pastdatapattern AWK pattern recognizing a line which is past the relevent # data, upon which the script may wind up and exit. (This # pattern will only be consulted if a line does not match # datalinepattern.) # target Any IP address for which there are readings in the file # may have its timing data analyzed and revised, not only the # nominal “target” of the data. # segmentsecs Segments should be long enough to make it likely (not # necessarily definite) that segment minima for one-way (not # necessarily round-trip) transit times are the ideal, # congestion-less, times; # but, on the other hand, short enough to allow four consecutive # jump-less segments, in absence of congestion, even for target # clocks that are reset by jumps on a very frequent schedule. # The default, 12 seconds, allows for jump resets as frequent # as once per minute. # intrastretchmaxerr The maximum absolute millisecond difference between an # actual segment minimum one-way transit time and a linearly # interpolated transit time for that timepoint, in a stretch of # segments to be considered adjustment-less. # interstretchmaxerr The maximum absolute millisecond difference between an # actual segment minimum one-way transit time and a linearly # interpolated transit time for that timepoint, in considering # a pair of “adjustment-less” stretches for coalescing. # sourceskew A guess at the skew of the source machine’s clock with respect # to standard time. If the guess is good, considerations of # the sign of apparent target skew can become meaningful after # compensation for the guessed source skew. But we avoid them # anyway! We do innocuously do the compensation. # showall Turns on all the following “show” parameters, displaying all # available information – unless explicitly overridden for # individual “show” parameters by setting them to 0. # showtarget Shows the target IP address at the top of the output. # showreadings Displays preliminarily-normalized data data for the target: # “there” time, “back” time, round-trip time. # showminima Displays the segment minima of the transit times, as well as # the global minima of these times. # showintrastretchtests Displays the skews and errors involved in the # collinearity tests for adding segments to stretches. # showonewaystretches Displays the jump-less stretches, with their skews, # for each direction, as determined without regard to the other # direction. # showstdroundtrips Displays the data and conclusions for the individual # local inferences of “standard round-trip time”. (The average # is what we finally use.) # showquality Displays the ratio of the inferred “standard” round-trip # time to the measured global minimum round-trip time. This # is around 1.0 with “good” data, and drops with persistent # congestion and, especially, clock craziness. # showcompositestretches Displays the final stretch information, after the # one-way stretch information from the two directions has been # synthesized into a single coherent picture. # showregions Displays the final map that will drive the correction pass. # The segment artifice is gone. Regions are defined by source # “sent” timestamps. # showcoverage Displays the total time coverage of the identified regions, # hence of the fixed data (if requested), relative to the # duration of the probing run. # writefixeddir The value is taken as the name of the directory to which to # write the fixed file as <datafile>.fix, and the rejected # (unfixable) record file as <datafile>.rej . # (A command-line setting of “//” may be used to override an # environment setting and will be interpreted as null.) # writeorigfixedplotdir The value is taken as the name of the directory # to which to write three space-delimited data files – one # isolating the (relevant target) triples of the original # data file, another containing the fixed triples, and a # third containing the rejected triples, those that could not # be fixed – named, respectively, <datafile>.plot, # <datafile>.fix.plot, and <datafile>.rej.plot . The shifting # and scaling of the data in these .plot files is chosen for # effectiveness of resulting graphs, and for compatibility # with the analytical text output. # (A command-line setting of “//” may be used to override an # environment setting and will be interpreted as null.)
# Assumptions in the analysis: # - There is no change in the routing to the target, or in the networking # infrastructure along the path, during the course of the data. # - Regular clock jumps do not happen more frequently than once per # 5 * segmentsecs. # - Congestion-free one-way transits occur often, so that maximal runs of # at least 4 consecutive segments with congestion-free transit times in # the same direction bracket most of each adjustment-free portion of the # data. # - There is at least one overlap of stretches of collinear-min-OTT # segments for the two directions; # else, there is at least one (reasonably) congestion-free round trip # in the data. # Adjustments by high-absolute-value temporary skew require low congestion as # they occur for proper analysis by the present method.
function setparameters( default) {
# default["datalinepattern"] = null # default["pastdatapattern"] = null # default["fieldseparator"] = null # default["hostfieldnum"] = null # default["sentfieldnum"] = *must* be specified # default["receivedfieldnum"] = *must* be specified # default["bouncedfieldnum"] = *must* be specified # default["target"] = targetfromfilename() default["segmentsecs"] = 12 default["intrastretchmaxerr"] = 2 default["interstretchmaxerr"] = 10 default["sourceskew"] = 0 # default["showall"] = null # default["showtarget"] = null # default["showreadings"] = null # default["showminima"] = null # default["showintrastretchtests"] = null # default["showonewaystretches"] = null # default["showstdroundtrips"] = null # default["showstdquality"] = null # default["showcompositestretches"] = null # default["showregions"] = null # default["showcoverage"] = null # default["writefixeddir"] = null # default["writeorigfixedplotdir"] = null (datalinepattern != "") \ || datalinepattern = ENVIRON["datalinepattern"] (pastdatapattern != "") \ || pastdatapattern = ENVIRON["pastdatapattern"] (fieldseparator != "") \ || fieldseparator = ENVIRON["fieldseparator"] (hostfieldnum != "") \ || hostfieldnum = ENVIRON["hostfieldnum"] (sentfieldnum != "") \ || sentfieldnum = ENVIRON["sentfieldnum"] (receivedfieldnum != "") \ || receivedfieldnum = ENVIRON["receivedfieldnum"] (bouncedfieldnum != "") \ || bouncedfieldnum = ENVIRON["bouncedfieldnum"] (target != "") \ || target = ENVIRON["target"] (segmentsecs != "") \ || ((segmentsecs = ENVIRON["segmentsecs"]) != "") \ || segmentsecs = default["segmentsecs"] (intrastretchmaxerr != "") \ || ((intrastretchmaxerr = ENVIRON["intrastretchmaxerr"]) != "") \ || intrastretchmaxerr = default["intrastretchmaxerr"] (interstretchmaxerr != "") \ || ((interstretchmaxerr = ENVIRON["interstretchmaxerr"]) != "") \ || interstretchmaxerr = default["interstretchmaxerr"] (sourceskew != "") \ || ((sourceskew = ENVIRON["sourceskew"]) != "") \ || sourceskew = default["sourceskew"] (showall != "") \ || showall = ENVIRON["showall"] (showtarget != "") \ || ((showtarget = ENVIRON["showtarget"]) != "") \ || showtarget = showall (showreadings != "") \ || ((showreadings = ENVIRON["showreadings"]) != "") \ || showreadings = showall (showminima != "") \ || ((showminima = ENVIRON["showminima"]) != "") \ || showminima = showall (showintrastretchtests != "") \ || ((showintrastretchtests = ENVIRON["showintrastretchtests"]) \ != "") \ || showintrastretchtests = showall (showonewaystretches != "") \ || ((showonewaystretches = ENVIRON["showonewaystretches"]) \ != "") \ || showonewaystretches = showall (showstdroundtrips != "") \ || ((showstdroundtrips = ENVIRON["showstdroundtrips"]) \ != "") \ || showstdroundtrips = showall (showquality != "") \ || ((showquality = ENVIRON["showquality"]) \ != "") \ || ((showstdroundtrips || showcompositestretches) && showquality = 1) \ || showquality = showall (showcompositestretches != "") \ || ((showcompositestretches = ENVIRON["showcompositestretches"]) \ != "") \ || showcompositestretches = showall (showregions != "") \ || ((showregions = ENVIRON["showregions"]) != "") \ || showregions = showall (showcoverage != "") \ || ((showcoverage = ENVIRON["showcoverage"]) != "") \ || showcoverage = showall (writefixeddir != "" && writefixeddir != "//") \ || writefixeddir = ENVIRON["writefixeddir"] (writeorigfixedplotdir != "" && writeorigfixedplotdir != "//") \ || writeorigfixedplotdir = ENVIRON["writeorigfixedplotdir"]
}
function targetfromfilename( fromfilename) {
fromfilename = FILENAME sub(/^.*\//, "", fromfilename) sub(/^[^0-9.]*/, "", fromfilename) sub(/[^0-9.].*/, "", fromfilename) sub(/^\./, "", fromfilename) sub(/\.$/, "", fromfilename) return fromfilename
}
function abs(number) {
return (number < 0) ? -number : number
}
function fixbyteorder (integer, revinteger, byte, ii) {
if (!needs_bytes_reversed) return integer revinteger = 0 for (ii = 0; ii < 4; ++ii) { byte = integer % 256 revinteger = revinteger*256 + byte integer = (integer - byte) / 256 } return revinteger
}
# Note: the variable tb holds the “there or back” direction code: # 0 is “there” (outbound), 1 is “back” (inbound).
function segmentboundary() {
if (showminima) print "Segment", segments \ ": minthere", min[0,segments] \ "; minback", min[1,segments] \ "; minroundtrip, fictive", (min[0,segments] + min[1,segments]) \ ", actual", min[2,segments] if (min[0,segments] < globalminthere) globalminthere = min[0,segments] if (min[1,segments] < globalminback) globalminback = min[1,segments] if (min[2,segments] < globalminroundtrip) globalminroundtrip = min[2,segments] # For each of the "there" and "back" directions, examine the # collinearity of the following four points: # the respective minimum of the respective candidate/extended # stretch's startseg; # the respective minimum of the mid-stretch segment; # the respective minimum of the immediate predecessor of the # present (old) segment; and # the respective minimum of the present (old) segment. # Note that in testing the first foursome for a (potential) stretch, # it could be that the first two and last two minima immediately # straddle segment boundaries, in which case this instance of the # test establishes almost nothing; but if so, the minima collinearity # test for the next segment minimum will be all the more stringent. for (tb = 0; tb < 2; ++tb) { if (segments - this_stretch_startseg[tb] < 3) continue seg1 = this_stretch_startseg[tb] seg2 = int((seg1 + segments) / 2) seg3 = segments - 1 # for "there", we use the "sent" timestamps; # for "back", we use the "bounced" timestamps; if (tb == 0) { if (min[tb,segments] > min[tb,seg1]) { use_sent1 = min_sent_late[tb,seg1] use_sent2 = min_sent_late[tb,seg2] use_sent3 = min_sent_late[tb,seg3] use_sent = min_sent_late[tb,segments] } else { use_sent1 = min_sent[tb,seg1] use_sent2 = min_sent[tb,seg2] use_sent3 = min_sent[tb,seg3] use_sent = min_sent[tb,segments] } min2shouldbe = ((use_sent - use_sent2) * min[tb,seg1] + \ (use_sent2 - use_sent1) * min[tb,segments]) / \ (use_sent - use_sent1) min3shouldbe = ((use_sent - use_sent3) * min[tb,seg1] + \ (use_sent3 - use_sent1) * min[tb,segments]) / \ (use_sent - use_sent1) this_skew = (min[tb,segments] - min[tb,seg1]) / \ (use_sent - use_sent1) } else { if (min[tb,segments] > min[tb,seg1]) { use_bounced1 = min_bounced_late[tb,seg1] use_bounced2 = min_bounced_late[tb,seg2] use_bounced3 = min_bounced_late[tb,seg3] use_bounced = min_bounced_late[tb,segments] } else { use_bounced1 = min_bounced[tb,seg1] use_bounced2 = min_bounced[tb,seg2] use_bounced3 = min_bounced[tb,seg3] use_bounced = min_bounced[tb,segments] } min2shouldbe = \ ((use_bounced - use_bounced2) * min[tb,seg1] + \ (use_bounced2 - use_bounced1) * min[tb,segments]) / \ (use_bounced - use_bounced1) min3shouldbe = \ ((use_bounced - use_bounced3) * min[tb,seg1] + \ (use_bounced3 - use_bounced1) * min[tb,segments]) / \ (use_bounced - use_bounced1) this_skew = (min[tb,segments] - min[tb,seg1]) / \ (use_bounced - use_bounced1) } min2error = min[tb,seg2] - min2shouldbe min3error = min[tb,seg3] - min3shouldbe if (showintrastretchtests) { print " segment", seg2, "min" thereback[tb], "off by", min2error ",", "segment", seg3, "min" thereback[tb], "off by", min3error print " " thereback[tb], "skew from segment", seg1 ": ", this_skew } # act on the collinearity test results if (abs(min2error) <= intrastretchmaxerr && abs(min3error) <= intrastretchmaxerr) { # collinearity test good if (in_stretch[tb]) { # extend existing (confirmed) stretch with present # (old) segment stretch_index[tb,segments] = stretches[tb] stretch_endseg[tb,stretches[tb]] = segments } else { # confirm candidate stretch in_stretch[tb] = 1 ++stretches[tb] stretch_index[tb,segments-3] = \ stretch_index[tb,segments-2] = \ stretch_index[tb,segments-1] = \ stretch_index[tb,segments] = stretches[tb] stretch_startseg[tb,stretches[tb]] = segments - 3 stretch_endseg[tb,stretches[tb]] = segments } stretch_skew[tb,stretches[tb]] = this_skew if (in_data == 2) # no more readings: adjust choices of minimum times ... if (min[tb,segments] > min[tb,seg1]) if (tb == 0) for (ii = seg1; ii <= segments; ++ii) min_sent[tb,ii] = min_sent_late[tb,ii] else for (ii = seg1; ii <= segments; ++ii) min_bounced[tb,ii] = min_bounced_late[tb,ii] } else { # collinearity test bad if (in_stretch[tb]) { # existing (confirmed) stretch cannot be extended: # adjust choices of minimum times ... if (min[tb,segments] > min[tb,seg1]) if (tb == 0) for (ii = seg1; ii <= segments - 1; ++ii) min_sent[tb,ii] = min_sent_late[tb,ii] else for (ii = seg1; ii <= segments - 1; ++ii) min_bounced[tb,ii] = min_bounced_late[tb,ii] # ... and start a new candidate stretch in_stretch[tb] = 0 this_stretch_startseg[tb] = segments } else # shift candidate stretch start segment ++this_stretch_startseg[tb] } }
}
function compatiblecounterskews(there_skew, back_skew) {
# Test: is average of the two skews off from 0 no more than # intrastretchmaxerr / (2 * segmentsec * 1000) # In the collinearity tests we are essentially allowing for an error # no greater than this in the individual skews, hence in their average. return (abs(there_skew + back_skew) <= \ intrastretchmaxerr / (segmentsecs * 1000))
}
function continuation(first_tb, first_seg, second_tb, second_seg,
ii, x, y, zz) { if (showcompositestretches) print "continuation:", thereback[first_tb], "seg", first_seg ",", thereback[second_tb], "seg", second_seg first_stretch_startseg = \ stretch_startseg[first_tb,stretch_index[first_tb,first_seg]] first_stretch_endseg = \ stretch_endseg[first_tb,stretch_index[first_tb,first_seg]] second_stretch_startseg = \ stretch_startseg[second_tb,stretch_index[second_tb,second_seg]] second_stretch_endseg = \ stretch_endseg[second_tb,stretch_index[second_tb,second_seg]] if (first_tb == 0) { x[1] = min_sent[0,first_stretch_startseg] y[1] = min[0,first_stretch_startseg] x[2] = min_sent[0,first_stretch_endseg] y[2] = min[0,first_stretch_endseg] } else { x[1] = min_bounced[1,first_stretch_startseg] - stdroundtrip y[1] = stdroundtrip - min[1,first_stretch_startseg] x[2] = min_bounced[1,first_stretch_endseg] - stdroundtrip y[2] = stdroundtrip - min[1,first_stretch_endseg] } if (second_tb == 0) { x[3] = min_sent[0,second_stretch_startseg] y[3] = min[0,second_stretch_startseg] x[4] = min_sent[0,second_stretch_endseg] y[4] = min[0,second_stretch_endseg] } else { x[3] = min_bounced[1,second_stretch_startseg] - stdroundtrip y[3] = stdroundtrip - min[1,second_stretch_startseg] x[4] = min_bounced[1,second_stretch_endseg] - stdroundtrip y[4] = stdroundtrip - min[1,second_stretch_endseg] } if (showcompositestretches) { print " y[1]", y[1], "y[2]", y[2], "y[3]", y[3], "y[4]", y[4] print " x[1]", x[1], "x[2]", x[2], "x[3]", x[3], "x[4]", x[4] } # take the "x" extrema as endpoints reordered = 0 for (ii = 1; ii <= 4; ++ii) { if (x[ii] < x[1]) { zz = x[1]; x[1] = x[ii]; x[ii] = zz zz = y[1]; y[1] = y[ii]; y[ii] = zz reordered = 1 } if (x[ii] > x[4]) { zz = x[4]; x[4] = x[ii]; x[ii] = zz zz = y[4]; y[4] = y[ii]; y[ii] = zz reordered = 1 } } if (showcompositestretches) if (reordered) { print " reordered ..." print " y[1]", y[1], "y[2]", y[2], "y[3]", y[3], "y[4]", y[4] print " x[1]", x[1], "x[2]", x[2], "x[3]", x[3], "x[4]", x[4] } min2shouldbe = ((x[4] - x[2]) * y[1] + (x[2] - x[1]) * y[4]) \ / (x[4] - x[1]) min3shouldbe = ((x[4] - x[3]) * y[1] + (x[3] - x[1]) * y[4]) \ / (x[4] - x[1]) min2error = y[2] - min2shouldbe min3error = y[3] - min3shouldbe if (showcompositestretches) print " min2error", min2error, "min3error", min3error return (abs(min2error) <= interstretchmaxerr && \ abs(min3error) <= interstretchmaxerr)
}
function inferstdroundtrip(seg) {
# We assume that segment seg is in both "there" and "back" stretches. # We work with the "there" minima for the two end-segments of seg's # "there" stretch, as well as with the "back" minimum for seg iteself... # # there_1(sent_3 - (bounced_2 - RT)) + # there_3((bounced_2 - RT) - sent_1) # RT - back_2 = ------------------------------------- # sent_3 - sent_1 # seg_1 = stretch_startseg[0,stretch_index[0,seg]] # use its "there" min seg_2 = seg # use its "back" min seg_3 = stretch_endseg[0,stretch_index[0,seg]] # use its "there" min tmpstdroundtrip_a = \ (min[0,seg_1] * (min_sent[0,seg_3] - min_bounced[1,seg_2]) + \ min[1,seg_2] * (min_sent[0,seg_3] - min_sent[0,seg_1]) + \ min[0,seg_3] * (min_bounced[1,seg_2] - min_sent[0,seg_1])) \ / ((min_sent[0,seg_3] + min[0,seg_3]) - \ (min_sent[0,seg_1] + min[0,seg_1])) if (showstdroundtrips) print "segments", seg_1, "there,", seg_2, "back,", seg_3, "there:", "ROUNDTRIP", tmpstdroundtrip_a # ... and vice versa, # using "back" stretch end-segment "back" data, and seg "there" data seg_1 = stretch_startseg[1,stretch_index[1,seg]] # use its "back" min seg_2 = seg # use its "there" min seg_3 = stretch_endseg[1,stretch_index[1,seg]] # use its "back" min tmpstdroundtrip_b = \ (min[1,seg_1] * (min_bounced[1,seg_3] - min_sent[0,seg_2]) +\ min[0,seg_2] * (min_bounced[1,seg_3] - min_bounced[1,seg_1])+\ min[1,seg_3] * (min_sent[0,seg_2] - min_bounced[1,seg_1])) \ / ((min_bounced[1,seg_3] - min[1,seg_3]) - \ (min_bounced[1,seg_1] - min[1,seg_1])) if (showstdroundtrips) print "segments", seg_1, "back,", seg_2, "there,", seg_3, "back:", "ROUNDTRIP", tmpstdroundtrip_b return (tmpstdroundtrip_a + tmpstdroundtrip_b) / 2
}
function stretch_length(tb, str) {
return stretch_endseg[tb, str] - stretch_startseg[tb, str] + 1
}
function set_region_start(tb, seg, reg) {
region_first_seg[reg] = seg $0 = data[min_index[tb,seg]] region_first_tb[reg] = tb region_first_orig_sent[reg] = $sentfieldnum region_first_sent[reg] = min_sent[tb,seg] region_first_orig_received[reg] = fixbyteorder($receivedfieldnum) region_first_received[reg] = min_received[tb,seg] region_first_orig_bounced[reg] = $bouncedfieldnum region_first_bounced[reg] = min_bounced[tb,seg] region_first_received_shouldbe[reg] = \ (tb == 0) ? region_first_orig_sent[reg] + stdroundtrip / 2 \ : region_first_orig_bounced[reg] - stdroundtrip / 2
}
function set_region_end(tb, seg, reg) {
region_last_seg[reg] = seg $0 = data[min_index[tb,seg]] region_last_tb[reg] = tb region_last_orig_sent[reg] = $sentfieldnum region_last_sent[reg] = min_sent[tb,seg] region_last_orig_received[reg] = fixbyteorder($receivedfieldnum) region_last_received[reg] = min_received[tb,seg] region_last_orig_bounced[reg] = $bouncedfieldnum region_last_bounced[reg] = min_bounced[tb,seg] region_last_received_shouldbe[reg] = \ (tb == 0) ? region_last_orig_sent[reg] + stdroundtrip / 2 \ : region_last_orig_bounced[reg] - stdroundtrip / 2
}
BEGIN {
setparameters() if (fieldseparator != "") FS = fieldseparator # must be set here init = 1 }
init {
init = 0 error = 0 # Note: FILENAME for targetfromfilename() was not available in BEGIN if (target == "") target = targetfromfilename() if (hostfieldnum != "" && (!(hostfieldnum > 0) || target == "")) { printf "Initialization:", "hostfieldnum and/or target not properly set.\n" \ > "/dev/stderr" error = 1 exit } if ( ! (sentfieldnum > 0 && receivedfieldnum > 0 && bouncedfieldnum > 0 && sentfieldnum != receivedfieldnum && receivedfieldnum != bouncedfieldnum && bouncedfieldnum != sentfieldnum) ) { printf "Initialization: data field numbers not properly set.\n" \ > "/dev/stderr" error = 2 exit } sourcescale = 1 / (1 + sourceskew) if (writefixeddir == "//") writefixeddir = "" if (writeorigfixedplotdir == "//") writeorigfixedplotdir = "" if (showtarget) print "Target:", target if (writefixeddir) { no_dir_filename = FILENAME sub(/^.*\//, "", no_dir_filename) fixedfilename = writefixeddir "/" no_dir_filename ".fix" printf "" > fixedfilename rejectedfilename = writefixeddir "/" no_dir_filename ".rej" printf "" > rejectedfilename } if (writeorigfixedplotdir) { no_dir_filename = FILENAME sub(/^.*\//, "", no_dir_filename) plotfilename = writeorigfixedplotdir "/" no_dir_filename ".plot" printf "" > plotfilename fixedplotfilename = \ writeorigfixedplotdir "/" no_dir_filename ".fix.plot" printf "" > fixedplotfilename rejectedplotfilename = \ writeorigfixedplotdir "/" no_dir_filename ".rej.plot" printf "" > rejectedplotfilename } intpattern = "^[ \t]*-*[0-9][0-9]*[ \t]*$" datalines = 0 in_data = 0 # before "data" (portion possibly containing readings) readings = 0 segments = 0 thereback[0] = "there" # word for "there" direction code 0 thereback[1] = "back" # word for "back" direction code 1 # variable "tb" ranges over "there" and "back" direction codes for (tb = 0; tb < 2; ++tb) { stretches[tb] = 0 in_stretch[tb] = 0 } needs_bytes_reversed = 0 }
in_data == 2 {
# will have exited if not intending to write fixed file print >> fixedfilename next }
$0 ~ datalinepattern {
in_data = 1 ++datalines data[datalines] = $0 if (hostfieldnum && $hostfieldnum != target) next if ($sentfieldnum !~ intpattern || $receivedfieldnum !~ intpattern || $bouncedfieldnum !~ intpattern) next if (readings == 0) { first_NR = NR first_index = datalines first_sent = $sentfieldnum first_received = $receivedfieldnum first_bounced = $bouncedfieldnum # before setting the cosmetic shifts, we wait till the next reading, # which, in comparison with this reading, will indicate whether # we need to reverse the byte order of the target timestamps. readings = 1 next } else if (readings == 1) { if (abs($receivedfieldnum - first_received) > 256 * 256) needs_bytes_reversed = 1 sourceshift = -first_sent targetshift = int((first_sent + first_bounced)/2 + sourceshift \ - fixbyteorder(first_received)) sent = 0 received = fixbyteorder(first_received) + targetshift bounced = int((first_bounced + sourceshift) * sourcescale) there = received - sent back = bounced - received roundtrip = bounced - sent segments = 1 min_index[0,1] = min_index[1,1] = \ min_index[0,1] = min_index[1,1] = \ first_index min_sent[0,1] = min_sent[1,1] = \ min_sent_late[0,1] = min_sent_late[1,1] = \ sent # 0 min_received[0,1] = min_received[1,1] = \ min_received_late[0,1] = min_received_late[1,1] = \ received min_bounced[0,1] = min_bounced[1,1] = \ min_bounced_late[0,1] = min_bounced_late[1,1] = \ bounced globalminthere = min[0,1] = there globalminback = min[1,1] = back globalminroundtrip = min[2,1] = roundtrip this_stretch_startseg[0] = 1 # "there", candidate only! this_stretch_startseg[1] = 1 # "back", candidate only! if (showreadings) { print "Segment 1:" print "1 (line", first_NR ") at", sent \ ": there", there ", back", back ", roundtrip", roundtrip } } ++readings sent = int(($sentfieldnum + sourceshift) * sourcescale) received = fixbyteorder($receivedfieldnum) + targetshift bounced = int(($bouncedfieldnum + sourceshift) * sourcescale) there = received - sent back = bounced - received roundtrip = bounced - sent if (sent >= segments * segmentsecs * 1000) { # the present reading begins a new segment; report on the old ... segmentboundary() # ... and initialize the new ++segments if (showreadings) print "\nSegment", segments ":" min_index[0,segments] = min_index[1,segments] = \ min_index_late[0,segments] = min_index_late[1,segments] = \ datalines min_sent[0,segments] = min_sent[1,segments] = \ min_sent_late[0,segments] = min_sent_late[1,segments] = \ sent min_received[0,segments] = min_received[1,segments] = \ min_received_late[0,segments] = min_received_late[1,segments] =\ received min_bounced[0,segments] = min_bounced[1,segments] = \ min_bounced_late[0,segments] = min_bounced_late[1,segments] = \ bounced min[0,segments] = there min[1,segments] = back min[2,segments] = roundtrip } else { if (there < min[0,segments]) { min_index[0,segments] = min_index_late[0,segments] = datalines min_sent[0,segments] = min_sent_late[0,segments] = sent min_received[0,segments] = min_received_late[0,segments] = \ received min_bounced[0,segments] = min_bounced_late[0,segments] = bounced min[0,segments] = there } else if (there == min[0,segments]) { min_index_late[0,segments] = datalines min_sent_late[0,segments] = sent min_received_late[0,segments] = received min_bounced_late[0,segments] = bounced } if (back < min[1,segments]) { min_index[1,segments] = min_index_late[1,segments] = datalines min_sent[1,segments] = min_sent_late[1,segments] = sent min_received[1,segments] = min_received_late[1,segments] = \ received min_bounced[1,segments] = min_bounced_late[1,segments] = bounced min[1,segments] = back } else if (back == min[1,segments]) { min_index_late[1,segments] = datalines min_sent_late[1,segments] = sent min_received_late[1,segments] = received min_bounced_late[1,segments] = bounced } if (roundtrip < min[2,segments]) min[2,segments] = roundtrip } if (showreadings) print readings, "(line", NR ") at", sent \ ": there", there ", back", back ", roundtrip", roundtrip next }
in_data == 0 {
if (writefixeddir) print >> fixedfilename next }
in_data == 1 {
if (pastdatapattern == "" || $0 !~ pastdatapattern) { ++datalines data[datalines] = $0 next } savepostdataline = $0 in_data = 2 pastdata() if (writefixeddir) { # write first post-data line to fixed file print savepostdataline >> fixedfilename next } exit }
function pastdata() {
if (!readings) { error = 3 printf "No readings found for target %s.\n", target \ > "/dev/stderr" exit } duration=sent segmentboundary() if (showminima) print "\nglobalminthere", globalminthere \ "; globalminback", globalminback \ ";\n\t\t\tglobalminroundtrip, fictive", (globalminthere + globalminback) \ ", actual", globalminroundtrip if (showonewaystretches) { print "\nJumpless one-way stretches and their skews:" for (ii = 1; ii <= segments; ++ii) print "Segment", ii \ ":\tthere stretch", stretch_index[0,ii] \ ", skew", stretch_skew[0,stretch_index[0,ii]] \ ";\n\t\t back stretch", stretch_index[1,ii] \ ", skew", stretch_skew[1,stretch_index[1,ii]] } # The ideal, congestion-free, round-trip time -- needed for the # reconciliation and coalescing of one-way stretches for opposite # directions -- may not be available in globalminroundtrip: there # may not have been a single reading without congestion in at least # one of the directions. However, any pair of (non-spurious) # stretches for opposite directions which overlap on at least two # segments should, in their segment minima for their respective # directions, represent collinear target clock deviation points. # Expressing this collinearity by intertranslating the one-way # transit-time minima for the opposite directions in terms of the # unknown ideal round-trip time allows us to derive the ideal # round-trip time -- provided the one-way transit-time minima are # perfectly congestion-free and error-free. Practically, however, # what we can expect to derive by this method is a useful "standard # round-trip time" that, as said, may well be smaller than # globalminroundtrip, perhaps considerably. It might also be just # a bit bigger than globalminroundtrip, perhaps by a millisecond or # two (depending on intrastretchmaxerr), as if the effective baseline # round-trip time, given our limited sampling and our error tolerance # for "collinearity", is a bit higher than the super-good time that # may be observed as a fluke. # Choosing the very lowest of the values for "standard round-trip # time" that we can obtain by calculations of the sort suggested # would give us the value closest to the true "ideal round-trip time". # But this value may not be consistent with our generally imperfect # one-way transit time minima, and so would not be the best choice of # standard value to mediate the inter-direction translation we need # to reconcile and coalesce counter-directional stretches. We must # bear in mind that our objective is not to emerge from the analysis # with as accurate an estimate as we can for the congestion-free # transit times; but rather to emerge with a reliable assessment of # whether no clock adjustments occurred between non-overlapping # adjustment-free stretches. # Therefore, we instead take as the effective stdroundtrip the # average of all the values we can calculate as described above. # We use globalminroundtrip as a guess at stdroundtrip if there # are no approriate pairs of overlapping segments at all to admit # our calculation -- and then with low expectations, after issuing # a warning. if (showstdroundtrips) print "\nInferring \"ideal round-trip time\":" idealcues = 0 total = 0 for (ii = 1; ii <= segments; ++ii) { if ( (stretch_index_0 = stretch_index[0,ii]) == "" || (stretch_index_1 = stretch_index[1,ii]) == "" || min_sent[0,stretch_endseg[0,stretch_index_0]] < \ min_sent[1,stretch_startseg[1,stretch_index_1]] || min_sent[1,stretch_endseg[1,stretch_index_1]] < \ min_sent[0,stretch_startseg[0,stretch_index_0]] ) continue if (!compatiblecounterskews(stretch_skew[0,stretch_index[0,ii]], stretch_skew[1,stretch_index[1,ii]])) { for (tb = 0; tb < 2; ++tb) { this_stretch_index = stretch_index[tb,ii] if (stretch_length(tb, this_stretch_index) == 4 && stretch_length(1-tb, this_stretch_index) >= 6) { for (jj = stretch_startseg[tb, this_stretch_index]; jj <= stretch_endseg[tb, this_stretch_index]; ++jj) stretch_index[tb,ii] = "" if (showrejectstretches) print "REJECTING length 4", "\"" thereback[tb] "\"", "stretch at Segment", ii ": incompatible skews" break } } continue } ++stdcuesegs total += inferstdroundtrip(ii) } if (stdcuesegs) stdroundtrip_for_quality = stdroundtrip = total / stdcuesegs else { print "WARNING: no usable overlapping counter-stretches." \ > "/dev/null"
# local change – ratul > “/dev/stderr”
stdroundtrip_for_quality = 0 stdroundtrip = globalminroundtrip } if (showquality) { print "\nThe following provides a measure of the quality of", "the timing data:"
local change to avoid divide by zero errors
if (globalminroundtrip != 0) { printf "inferred stdroundtrip / globalminroundtrip: " \ "%s / %s = %s\n", stdroundtrip_for_quality, globalminroundtrip, stdroundtrip_for_quality / globalminroundtrip } else { printf "inferred stdroundtrip / globalminroundtrip: " \ "%s / %s = %s\n", stdroundtrip_for_quality, globalminroundtrip, "nan" } } if (showstdroundtrips || showcompositestretches) print "\nUsing stdroundtrip", stdroundtrip # synthesize composite stretches if (showcompositestretches) { print "\nComposite stretch processing:" } last_stretch_segment = 0 last_stretch_tb = "" # (will prefer "there" data when both available) for (ii = 1; ii <= segments; ++ii) { there_skew = stretch_skew[0,stretch_index[0,ii]] back_skew = stretch_skew[1,stretch_index[1,ii]] if (there_skew == "" && back_skew == "") { if (showcompositestretches) print "Segment " ii ": not in a stretch." segment_composite[ii] = "unknown" # may be overwritten continue } # skews have been registered from "there" and/or from "back" data if ((there_skew != "" && back_skew == "") || (there_skew == "" && back_skew != "")) { # skews have been registered from "there" XOR from "back" data this_tb = (there_skew != "") ? 0 : 1 if (stretch_index[this_tb,ii-1] == stretch_index[this_tb,ii]) { # past start of stretch if (showcompositestretches) print "Segment " ii ":", "past start of only stretch. CONTINUE." segment_composite[ii] = "CONTINUE" } else if (last_stretch_segment && continuation(last_stretch_tb, last_stretch_segment, this_tb, ii)) { # new stretch resumes last stretch; # assume intervening congestion, and fill the gap, if any if (showcompositestretches) print "Segment " ii ":", "new stretch resumes last stretch. Back fill CONTINUE." for (jj = last_stretch_segment + 1; jj <= ii; ++jj) segment_composite[jj] = "CONTINUE" } else { # start of the very first stretch, or following jump or turn # ... which we may someday take the trouble to locate ... if (showcompositestretches) print "Segment " ii ":", "START of the very first stretch, or following jump/turn." segment_composite[ii] = "START" } last_stretch_segment = ii last_stretch_tb = this_tb continue } # skews have been registered both from "there" and from "back" data if (stretch_index[0,ii-1] == stretch_index[0,ii] && stretch_index[1,ii-1] == stretch_index[1,ii]) { # past start of both of the stretches # (we save repeated continuation checks) if (showcompositestretches) print "Segment " ii ":", "in two stretches; past start of both. CONTINUE." segment_composite[ii] = "CONTINUE" last_stretch_segment = ii last_stretch_tb = 0 continue } # at least one of the two stretches is just starting if (continuation(0, ii, 1, ii)) { # (The "continuation" test should work for arbitrarily # positioned stretches.) if (stretch_index[0,ii-1] == stretch_index[0,ii] || stretch_index[1,ii-1] == stretch_index[1,ii]) { # one stretch continuing, another starting, compatibly if (showcompositestretches) print "Segment " ii ":", "CONTINUE test succeeded for start new mid-existing." segment_composite[ii] = "CONTINUE" } else if (last_stretch_segment && continuation(last_stretch_tb, last_stretch_segment, 0, ii)) { # both stretches are just starting, but resume last stretch; # assume intervening congestion, and fill the gap, if any if (showcompositestretches) print "Segment " ii ":", "new stretches resume last stretch. Back fill CONTINUE." for (jj = last_stretch_segment + 1; jj <= ii; ++jj) segment_composite[jj] = "CONTINUE" } else { # both stretches are just starting if (showcompositestretches) print "Segment " ii ":", "double START, very first or after jump/turn." segment_composite[ii] = "START" } last_stretch_segment = ii last_stretch_tb = 0 continue } else { # "continuation" test failed: the two stretches can't be merged. # The stretches should be hinged on this single segment, # NOT overlapping on two or more segments. One must be ending. if (stretch_index[0,ii] == stretch_index[0,ii+1] && stretch_index[1,ii] == stretch_index[1,ii+1]) { # BAD: neither is ending. if (showcompositestretches) print "Segment " ii ":", "continuation test failed; BAD non-hinge case." printf "ERROR: Stretches overlappiing at segment %d " \ "are incompatible.\n", ii > "/dev/stderr" error = 4 exit } if ((stretch_index[0,ii] != stretch_index[0,ii+1] && min_sent[0,ii] > min_bounced[1,ii] - stdroundtrip) \ || (stretch_index[1,ii] != stretch_index[1,ii+1] && min_bounced[1,ii] - stdroundtrip > min_sent[0,ii])) { # BAD: overlapping at a fine granularity, within segment. if (showcompositestretches) print "Segment " ii ":", "continuation test failed;", "BAD micro-overlap in hinge case." printf "ERROR: Stretches overlappiing inside segment %d " \ "are incompatible.\n", ii > "/dev/stderr" error = 5 exit } if (compatiblecounterskews(there_skew, back_skew)) { if (showcompositestretches) print "Segment " ii ": continuation test failed; JUMP." segment_composite[ii] = "JUMP" } else { if (showcompositestretches) print "Segment " ii ": continuation test failed; TURN." segment_composite[ii] = "TURN" } last_stretch_segment = ii last_stretch_tb = 0 continue } } if (showcompositestretches) { print "\nComposite stretch end result:" for (ii = 1; ii <= segments; ++ii) print "Segment", ii \ ":\t" segment_composite[ii] } # map final regions # Note: we assume no out-of-sequence packet delivery, at least at the # data's spacing of packets ... but perhaps necessarily, if moving # through a fixed path, with fixed hardware interfaces. regions = 0 for (ii = 1; ii <= segments; ++ii) { if (segment_composite[ii] == "unknown") continue there_stretch = stretch_index[0,ii] back_stretch = stretch_index[1,ii] if (segment_composite[ii] == "START") { # region start point ++regions if (there_stretch && (!back_stretch || min_sent[0,ii] <= min_sent[1,ii])) set_region_start(0, ii, regions) else set_region_start(1, ii, regions) } if (segment_composite[ii] == "CONTINUE") { if (segment_composite[ii+1] == "CONTINUE" || segment_composite[ii+1] == "JUMP" || segment_composite[ii+1] == "TURN") continue # region end point if (there_stretch && (!back_stretch || min_sent[0,ii] >= min_sent[1,ii])) set_region_end(0, ii, regions) else set_region_end(1, ii, regions) } else if (segment_composite[ii] == "JUMP" || segment_composite[ii] == "TURN") { # region start and end points if (min_sent[0,ii] < min_sent[1,ii]) { set_region_end(0, ii, regions) set_region_start(1, ii, regions+1) } else { set_region_end(1, ii, regions) set_region_start(0, ii, regions+1) } ++regions } } if (showregions) { print "\nFinal map of regions:" for (ii = 1; ii <= regions; ++ii) printf "Region %d (segments %d - %d):\n" \ " %s %d->%d->%d to %s %d->%d->%d\n", ii, region_first_seg[ii], region_last_seg[ii], (region_first_tb[ii] == 0) ? "(\"there\")" \ : "(\"back\")", region_first_orig_sent[ii], region_first_orig_received[ii], region_first_orig_bounced[ii], (region_last_tb[ii] == 0) ? "(\"there\")" \ : "(\"back\")", region_last_orig_sent[ii], region_last_orig_received[ii], region_last_orig_bounced[ii] } if (showcoverage) { coverage = 0 for (ii = 1; ii <= regions; ++ii) coverage += region_last_sent[ii] - region_first_sent[ii] printf "\nRelative coverage: %s / %s = %s\n", coverage, duration, coverage / duration } if (!writefixeddir && !writeorigfixedplotdir) return # write corrected data lines to fixed file saveOFS = OFS OFS = FS search_from_region = 1 if (writeorigfixedplotdir) # display globalminthere as half the standard round trip. plottargetshift = targetshift + int(stdroundtrip/2) - globalminthere for (ii = 1; ii <= datalines; ++ii) { $0 = data[ii] if ($0 !~ datalinepattern || (hostfieldnum && $hostfieldnum != target) || $sentfieldnum !~ intpattern || $receivedfieldnum !~ intpattern || $bouncedfieldnum !~ intpattern) { if (writefixeddir) print >> fixedfilename continue } # locate region, if any, covering this reading; else reject. for (jj = search_from_region; jj <= regions; ++jj) { if ($sentfieldnum <= region_last_orig_sent[jj]) break } search_from_region = jj # fix the target byte order, even for the rejected data points $receivedfieldnum = fixbyteorder($receivedfieldnum) if (writeorigfixedplotdir) { # shift and scale to match analytical output sent = int(($sentfieldnum + sourceshift) * sourcescale) received = $receivedfieldnum + plottargetshift bounced = int(($bouncedfieldnum + sourceshift) * sourcescale) printf "%d %d %d\n", sent, received, bounced \ >> plotfilename } if (jj > regions || $sentfieldnum < region_first_orig_sent[jj]) { # didn't find one if (writefixeddir) print >> rejectedfilename if (writeorigfixedplotdir) { printf "%d %d %d\n", sent, received, bounced \ >> rejectedplotfilename } continue } # found the region first_orig_received = region_first_orig_received[jj] last_orig_received = region_last_orig_received[jj] first_received_shouldbe = region_first_received_shouldbe[jj] last_received_shouldbe = region_last_received_shouldbe[jj] received = $receivedfieldnum $receivedfieldnum = int( \ ((last_orig_received - received) * first_received_shouldbe + \ (received - first_orig_received) * last_received_shouldbe) / \ (last_orig_received - first_orig_received) ) if (writefixeddir) print >> fixedfilename if (writeorigfixedplotdir) { # shift and scale fixed received to match sent shift and scale received = int(($receivedfieldnum + sourceshift) * sourcescale) printf "%d %d %d\n", sent, received, bounced \ >> fixedplotfilename } } OFS = saveOFS }
END {
if (error) exit error if (in_data != 2) pastdata() }
# The objective is to compose a map of the target’s clock skews and jumps over # the duration of the probing run. This allows compensation, removing target # clock artifacts from the probe’s timing data. # # Note: I refer to the outgoing direction as “there” and the incoming direction # as “back”. # # We analyze the “there” data and the “back” data independently, at first, for # maximal stretches of length at least 4 of segments whose segment minima for # one-way packet transit times, in the respective directions, are collinear. # The idea in the independent analysis of the two directions is two-fold: # foremost, a lack of persuasive data for one direction, due to obscuring of # clock behavior by network congestion in that direciton, can be covered for # by persuasive data for the other direction; and secondly, if data for both # directions are independently persuasive, the redundancy provides a measure # of error-checking and allows us to infer an uncongested round-trip time that # should be more reliable than the global minimum round-trip time.