User login

Stephen Eichler's blog

25

Mar

2014

Research has been carried out into the possibility that some load balancers partition packets to their successor nodes based on packet fields other than those that are considered usual. Thirteen fields where chosen for the test and scamper, the program we use for traceroute MDA, was modified to carry them out. Traceroute MDA is an analysis that scans the Internet for load balancers and other network topology information.

Small numbers of load balancers have been found that do this, and many of the same load balancers are found by different field tests. The next question was to find out if these load balancers behaved as load balancers all the time. The case of also being a per packet load balancer was excluded from the counts i.e one that partitions randomly. Three cases emerged that of a small number of hits and misses, a large number of misses and a small number of hits and no hits. A miss means that no load balancer was found though the same node that was a load balancer in another trace exists in the topology, but with only one successor if any. There may be some more special cases to exclude from the data such as the node being last in the trace etc. It appears that some of these load balancers show fairly consistent load balancing across a couple of field types, others show the load balancing behaviour only rarely.

The Internet simulator simulates doubletree and traceroute in its unmodified state. Traceroute determines Internet topology between a source and destination, but not including load balancers. Doubletree is a modified version of traceroute that is designed to avoid repeatedly analysing the same parts of the Internet, by sharing information between vantage points.

We are currently trying to simulate unmodified doubletree using very large datasets. This caused the simulator to run a long time. Analysis with valgrind callgrind indicates that the gang analysis case which is being used is the major problem here. So, the question is now being asked: can we do without gang analysis for this work?

A fast mapping like protocol has been set up for detecting black holes in load balancers. It involves one round of traceroute MDA analysis followed by eight rounds of Paris traceroute, followed by one further round of MDA. Paris traceroute causes the same path through a load balancer to be consistently followed. Comparing the initial and final MDA traces determines if a change in topology has occurred in the Internet. If this is the case finding a short Paris trace may not be due to a blackhole. After excluding all of the special cases that I can think of there remain some cases which appear to be blackholes in load balancers in our data.

In order to run this type of analysis on PlanetLab we prefer to use ICMP packets. Modifications were made to scamper on Yoyo our University computer outside the firewall, to randomly choose a flow ID for each trace and a run was initiated.

It has been decided that regression equations may not be sufficiently fundamental to understand the mathematical models predictions. In the first instance I am extracting 'proportional to' type relationships from these equations to see if more fundamental inferences may be made about the structure of the model.

It will also be desirable to try and derive these proportional to relationships from theoretical arguments. For example, is the number of packets sent from a vantage point proportional to the number of destinations probed in system where there are no savings measures taken. If a match or resolution is found between these two approaches then that would be good progress.

It may also be necessary to focus on the data sets with a large packet limit and determine if incomplete load balancer information should be counted if it seems sensible to do so. This is important because a small number of very high cost load balancers may exist, and these are the most important ones to avoid repeated analysis of.

18

Mar

2014

A longer run to find black holes in load balancers using our version of fast mapping has been carried out. Instead of 1000 addresses, two lots of 5000 were used. In each case there was an initial traceroute MDA run followed by eight Paris traceroute runs and in turn a final MDA run. The resulting warts files were scanned using the upgraded analysis program which when it finds a short Paris trace, compares the initial and final MDA runs for route changes and checks the Paris end point to see if it is within a load balancer. Some special cases which are flagged are when the destination is inside a load balancer itself and when the Paris stop point is at the convergence point of a load balancer. These special cases explained the possible black holes found in the 1000 destination data, however some true appearance black holes in LBs were found in the 5000 destination data. It may be possible to continue this on planetlab however it is probably necessary to use ICMP probes, and this would reduce the number of per flow load balancers seen, requiring more probing to see the same number of load balancers.

Initial runs were carried out using valgrind callgrind. It took me a while to realise that I could not use my Internet Simulator bash script as callgrind appeared to analyse the bash shell in this case. When I ran the program directly I still couldn't start with no instrumentation and then manually activate it. When I did this there were no events collected. This seems to be a callgrind bug. Another possibility is to try the programmatic activation of callgrind instrumentation by recompiling the simulator with an activation macro included. It turns out that making memory map nodes in the build method starts almost immediately, and I don't know how long it takes before it gets to making links. Running valgrind without a delayed start can help answer this. The objective is still to delay for a day and then run instrumentation for two days.

11

Mar

2014

A second run of the Internet Simulator has been started with delayed Valgrind. Valgrind call-graph will be started after a day of running. This is to find out what the simulator is spending most of its time doing as it seems to be taking to long to run. These runs are using less than ten percent of virtual memory each, which is more economical than I thought. Tony McGregor is going to have a look at these results to help determine the problem.

More work has been carried out on our version of fast mapping which uses one round of traceroute MDA before and after 6-8 rounds of Paris traceroute. The analysis program has been upgraded to be more concise and descriptive. Also Paris traceroute has been upgraded to vary the flow ID used from trace to trace within the same scamper process. The process ID was used to generate the source port value. Furthermore a series of data sets has been generated of size 5000 destinations and a run of two cycles using two different data sets has been initiated to test the changes.

It appears that some of the promising results from fast mapping so far weren't actually black holes in load balancers. However new data is required as the problems above before they were fixed made the results less useful.

04

Mar

2014

Further work has been carried out on the development of the Megatree mathematical model. Megatree is like doubletree but stores and shares information about load balancers instead, and is applied to Traceroute MDA analysis. It has been difficult to fit regression models that provide useful predictions when extrapolated. This is because the data that I have to use is for 20 vantage points and 70000 destinations. Furthermore the number of vantage points which collected traces with a maximum to 65000 probes vs. 15000 is two out of 20. This first round of testing uses an average across vantage points, so it will be necessary to come back and focus on the two full test vantage points. In one case it was necessary to add a varying asymptotic model to the regression to get a useful realistic fit. Based on this, the first round of results look sensible and interesting. The model included my first attempts at estimating the cost of control packets, which share load balancer information between vantage points.

I have also been preparing for a discussion of my supervisors on how to round out my research program. This has involved generating a set of slides.

26

Feb

2014

I am revisiting a strategy to find black holes in load balancers. The original set up used traceroute MDA which maps load balancers, followed by six cycles of Paris traceroute. The idea was to look for shortened Paris traces and further process these to see if the stop point was in a load balancer. A further final round of MDA has been added after Paris to check for route changes. The coding related to this change is underway. Currently more route changes are being found than should be so I am testing the algorithm that detects these on a trace case by case basis.

A mathematical model is also being developed for Megatree. This is an analogue to Doubletree that records details of load balancer diamonds and avoids repeatedly mapping them, especially the big complex ones that occur in smaller numbers. I have carried out regression analysis on the UDP CAIDA data to predict savings and packets numbers. I carried out transformations to make the residuals normally distributed and the relationships linear. These formulae were then included in a computer program which was inputted with factor levels used to produce customised results. I have generated results for the local and global scenarios i.e. within a vantage point and sharing LB data between vantage points. Next it will be necessary to generate relationships to make simulation of inter vantage point traffic costs possible.

18

Feb

2014

The warts analysis was modified to provide data to the megatree mathematical model. Megatree involves local and distributed approaches to avoiding the mapping of the same load balancer more than once, and is based on Doubletree. In particular subsets of the 70000 destinations sets were created to create model data for varying numbers of destinations. Regression analysis was carried out to provide model structure.

The fast mapping analysis has been updated to include a full MDA trace at the beginning and end of the data collection cycle. This is to check for route and load balancer changes. Our fast mapping protocol uses six runs of paris traceroute between the MDA runs. There is still some more debugging and design to carry out.

11

Feb

2014

A start has been made on mathematically modelling a program along the lines of doubletree to probe load balancers once. Initial attempts to model the distributions of the local and global sets are underway and some initial results have been collected.

A run of my version of fastmapping has been started. I am rechecking the validity of this approach to attempting to observe black holes in load balancers.

04

Feb

2014

The process of starting the Internet simulator on a full size run was completed.

Corrections throughout the whole paper have been made. It may now be time for Tony to have a look at it, or maybe some other possible critics.

I wrote a short review on the progress and possible forward strategy of my research. Some planning is required at this stage to work out how to develop a rounded story to tell.

29

Jan

2014

Warts data was analysed to find the sets of internal diamond nodes that had changed. This was then made into a graph for the paper.

A graph of unique load balancer intersection sets was also constructed for per flow and per destination data.

Further updates were made to the paper including changes to the discussion and conclusions.

The shortened Internet simulator test run was found to have completed successfully. The full length run was initiated.

21

Jan

2014

The scamper run on Planetlab has finished and the results are being downloaded.

Further updates have been carried out on the paper. This has included updates to the turnover section and the introduction.

My six monthly report was finalised and submitted.