Please note that these Trac pages are no longer being updated. Wiki contents/documentation have moved to GitHub.
Exploring the Delay Space with Seattle
Table of Contents
This work was performed by Philipp Eittenberger, Marcel Großmann and Udo Krieger from the Computer Networks Group (KTR) of OttoFriedrich University Bamberg, Germany.
Further information can be found in:
Philipp M. Eittenberger, Marcel Großmann, Udo R. Krieger:
Doubtless in Seattle: Exploring the Internet Delay Space.
8th EuroNF Conference on Next Generation Internet 2012 (NGI 2012), Karlskrona, Sweden, 2527 June 2012.
Modified DivideandConquer Algorithm
The allpairsping algorithm we use is based on a modified divideandconquer algorithm. It uses a central coordination instance to avoid interferences between each measurement trial. To obtain the latency matrices, we implemented the two following programs: the "controller" program, which is monitoring and controlling the steps of the divideandconquer algorithm, and the "node" program, which is responsible for performing the measurements on each tested Seattle VM.
Controller
This program controller.repy is repsonsible for the execution of the divideandconquer algorithm and for the coordination of the measurement rounds. It may only be installed on one Seattle VM to coordinate all VMs on which the "node" program is running. For this purpose, it obtains a list S with the IPs of all Seattle nodes to measure.
In the divide step the list S is split into two sublists S_{1} and S_{2}. If the length of S is odd, S_{1} receives the last remaining node.
In the conquer phase, the controller sends a message to each node of the sublist S_{1} to indicate, which node of S_{2} should be measured. Furthermore, by permuting the measured list, the controller will ensure that all possible pairs are measured. By switching the sublists thereafter and restarting the conquer step, it will perform all measurements bidirectionally.
When the measurements have been performed bidirectionally and the length of one of the remaining sublists is greater than one, the divideandconquer algorithm starts with this sublist recursively again.
The program is started in seash.py by executing:
controller.repy [port] [ipfile] [measures] [waittime]
 [port]: Your specific port for Seattle
 [ipfile]: A file you uploaded to the controller VM with all IPs that should be measured (You might use show ip to ipfile.txt in Seash to save the ipfile)
 [measures]: The number of measurements that should be performed
 [waittime]: A specific waiting time between each measurement
Node
The program node.repy is responsible for the execution of the measurements. It is executed on all Seattle VMs which should be measured. Being governed by the controller each node will produce a list of n measurements with a specific waiting time t between each try.
The program is started in seash.py by executing:
node.repy [port]
 [port]: Your specific port for Seattle
Executing the Programs
To get the programs running, first acquire your VMs and exclude one node from the whole group; then, run "node.repy" on all members of the group, export their IPs to a file and finally, upload the IP file to the node that was removed from the group and run "controller.repy" on it.
Calculations
For the statistical analysis of the collected data, the following metrics are provided: the quantiles, the mean value and an estimation of the variance and the deviation.
Mean Value
def calcmean(floatlist): result = 0.0 for f in floatlist: result += f if len(floatlist) > 0: result /= len(floatlist) return result
Estimation of the Variance and Deviation
def calcestimate(floatlist): result = 0.0 mean = calcmean(floatlist) for f in floatlist: result += (f  mean) ** 2 if len(floatlist) > 1: result /= (len(floatlist)  1) else: result = 0 return result
def calcdeviation(floatlist): result = calcestimate(floatlist) result = result ** .5 return result
Quantiles
def calcquantil(sortedfloatlist, quantil=0.25): result = 0 n = len(sortedfloatlist) datapoint = n * quantil if int(datapoint) is not 0: if datapoint % int(datapoint) > 0: datapoint = int(datapoint) result = sortedfloatlist[int(datapoint)] else: result = (sortedfloatlist[int(datapoint  1)] + sortedfloatlist[int(datapoint)]) / 2 return result
Displaying the Results
The controller can display the results in several ways:
On a Website
The website is generated after one measurement round is done. You can access it with a Browser using the IP of the dedicated Controller node in conjunction with your Seattle port (e.g. http://1.2.3.4:1234).
def show_status(srcip, srcport, connobj, ch, mainch): webpage = "<html><head><title>RoundTripTime</title></head><body><h1>RoundTripTimes measured by " + getmyip() + '</h1>' if mycontext['int_measured'] < len(mycontext['list_availableips']): print "Html in progress" webpage += "<b>Still in Progress...</b>" else: for i in range(9): webpage += "<h2>" webpage += getmeasurelabel(i) webpage += "</h2>" webpage += generatetable(i) webpage += '</html>' connobj.send('HTTP/1.1 200 OK\nContentType: text/html\nContentLength: ' + str(len(webpage)) + '\nServer: Seattle Testbed\n\n' + webpage) connobj.close()
In a CSV File
The Controller generates a CSV file that can be downloaded. It contains all measurement values.
def generate_csv(sorted=False, file="results"): filestring = file + ".csv" myfileobject = open(filestring, "w") writestring = "From; To;" for i in range(mycontext['int_tries']): writestring += str(i + 1) + "; " writestring += "\n" for fromip in mycontext['list_availableips']: for toip in mycontext['list_availableips']: if fromip is not toip: writestring += fromip + "; " writestring += toip + "; " if sorted: currentlist = getsortedlist(fromip, toip) else: currentlist = getlist(fromip, toip) for value in currentlist: writestring += str(value) + "; " if len(currentlist) < mycontext['int_tries']: writestring += addsemicolon(mycontext['int_tries']  len(currentlist)) writestring += "\n" writestring += "\n" myfileobject.write(writestring) myfileobject.close()
In a LaTeX Table
Another possible representation of the results is as a LaTeX file. It contains the allpairsmatrices as tables of all conducted calculations and can be obtained from the controller too.
def generate_tex(size=0, file="results"): filestring = file + ".tex" myfileobject = open(filestring, "w") writestring = "\\begin{landscape}\n" writestring += "\\section{Results of the measurements of controller " + getmyip().replace(".", ".\"\"") + "}\n" if size is 0: writestring += "\\normalsize\n" elif size is 1: writestring += "\\small\n" elif size is 2: writestring += "\\footnotesize\n" elif size is 3: writestring += "\\tiny\n" else: writestring += "" writestring += generate_longtable(0) writestring += generate_longtable(1) writestring += generate_longtable(2) writestring += generate_longtable(3) writestring += generate_longtable(4) writestring += generate_longtable(5) writestring += generate_longtable(6) writestring += generate_longtable(7) writestring += generate_longtable(8) writestring += "\\end{landscape}\n\\normalsize" myfileobject.write(writestring) myfileobject.close()
Visualization as TikZ Graphic
A graphical visualization of the divideandconquer algorithm is given as TikZ graphic. It is also generated by the controller and shows all single steps the algorithm is recursively traversing.
def generate_tikz(file="tikzgraphics"): filestring = file + ".tex" myfileobject = open(filestring, "w") writestring = "\\textbf{Caption:}\n" writestring += "\\begin{tabbing}\n" writestring += "IP1000 \= " + getmyip() + "\\kill\n" writestring += "IPC" + "\\> " + getmyip() + "\\\\\n" for ip in mycontext['map_ipforgraphics']: writestring += mycontext['map_ipforgraphics'][ip] + "\\> " + ip + "\\\\\n" writestring += "\\end{tabbing}\n" writestring += "\\tikzstyle{ipnode}=[circle, fill=gray!20 ,draw,thick]\n" for i in range(len(mycontext['string_graphics'])): writestring += "\\begin{figure}[H]\n\\centering\n" writestring += mycontext['string_graphics'][i] writestring += "\\caption{ConquerMeasure " + str(i + 1) + "}\n\\label{img:conq" + str(i + 1) + "}\n" writestring += "\\end{figure}\n\n" myfileobject.write(writestring) myfileobject.close()
Results
The results of a first test run with 50 nodes is provided in latencymap.csv. This map contains the mean values of the median reduced measurement lists between two nodes
In measuremap.csv all results are presented row wise with the additional information of the distances between the nodes and their location.
First Measurement
The first measurement was conducted with 103 nodes. The results are given in first_latencymap.csv and the row wise presentation of the 10,506 measurement pairs with the additional information of their distances can be found in first_measuremap.csv
Second Measurement
The second measurement included 109 nodes. The results are given in second_latencymap.csv.
Third Measurement
The second measurement included 107 nodes. The results are given in third_latencymap.csv.
Attachments

controller.repy
(22.6 KB)  added by pheitt
8 years ago.
Controller program

node.repy
(3.7 KB)  added by pheitt
8 years ago.
Node program

conquer.png
(17.0 KB)  added by pheitt
8 years ago.
conquer phase

allpairsping.png
(35.6 KB)  added by pheitt
8 years ago.
allpairsping

measurements.png
(26.1 KB)  added by pheitt
8 years ago.
Measuring

measuremap.csv
(184.1 KB)  added by pheitt
8 years ago.
Results of test set with distances

latencymap.csv
(32.8 KB)  added by pheitt
8 years ago.
Results of test set

first_measuremap.csv
(1.0 MB)  added by pheitt
8 years ago.
Results of first measurement with distances

first_latencymap.csv
(144.1 KB)  added by pheitt
8 years ago.
Results of first measurement

second_latencymap.csv
(158.7 KB)  added by pheitt
8 years ago.
Results of second measurement

third_latencymap.csv
(151.2 KB)  added by pheitt
8 years ago.
Results of third measurement