Posts+Tagged+%26%238216%3B3d%26%238217%3B

Bachelor’s thesis complete

Thursday, June 16th, 2011

Yesterday I finally handed in my bachelor’s thesis at the Technische Universität München. Although the chosen subject “Interactive visualization of global routing dynamics” was quite interesting to work with it does feel good when everything is over. However, since my advisers seemed to be quite pleased with the results, it is very likely that I will continue my work on this project as at research assistant at the Chair for Network Architectures and Services.

Abstract

To manage the rapid growth of the Internet, numerous tools were designed that allow to visually interpret routing graphs from a specific vantage point or on a local scale, thus helping network administrators make decisions on routing policies. Many of the applied techniques however exhibit poor scaling when they are used to draw larger parts of the global routing graph. In this thesis, AS-Viewer is introduced as a new and flexible tool that allows the use of different graph drawing techniques to display a wide variety of annotations for the AS-Graph. To limit the complexity of the resulting images, clustering can be used alongside with hierarchy based graph layouts. In addition, the graph drawing is done in hardware accelerated 3D, allowing the user to interactively inspect the AS-Graph using perspective to highlight specific subregions of the Internet. Further interactivity is provided through an interpreter that allows close inspection and man­ipulation of the graph. It will be concluded that AS-Viewer can greatly help interpreting large and complex datasets on global routing by allowing to quickly identify peculiarities and potential errors, thus making it an ideal tool in further analysis of global Internet structure.

If the images or the abstract made you curious: here is the .pdf

En route to CAIDA topology map

Wednesday, March 30th, 2011

In my current endeavor to make the BGP-Graph comprehensible a few huge leaps have been made. If you are familiar with other work in this field you may know the following image. (source)

Internet topology map from CAIDA.org

Internet topology map from CAIDA.org

Although this rendering does convey a few insights that are not plainly visible looking at the graph data, it still has some serious drawbacks. My main criticism is that it is  fixed image that does not allow easy reuse of the underlying data or any interactivity such as querying and highlighting certain parts of the graph. Also it is not possible to watch changes in this graph in relation to events like 2008′s severing of a FLAG submarine cable leaving much of the middle east with poor Internet speeds. (BBC article)

As you could see in previous articles, it is not trivial to turn such a huge graph into something meaningful. A main problem has been that the force-based graph layout that I employed takes very long to converge if I impose too many restrictions that limit the complexity of the resulting layout. My new approach is to help the force-based algorithm by providing it with a meaningful initialization of the graph layout. Using the CAIDA as-rank dataset I determined a circle radius on which each Autonomous System is placed. The initial angle at which the AS is placed was then calculated using the country code in the WHOIS information obtained from APNIC and the other RIRs.

After this initial placement the movement of the graph nodes was restricted to the angle. The force-based layout algorithm then spread the ASes and also moved a fair few of them away from the United States, where many of them are registered although their main business is done elsewhere. The resulting positions can then be rendered and update in realtime using any decent graphics card.

Longitude based layout of graph

Longitude based layout of graph

There is still a lot of work left but this seems to me like a rather significant breakthrough. Next I will try to integrate my clustering algorithms into the rendering, stay tuned for more…

progress@thesis

Wednesday, February 16th, 2011

Due to some exams at uni my thesis has been on low priority recently. Since last Thursday however these exams belong to the past and my thesis is humming along once more.

Right now I’m focusing on several aspects such as the rendering (note how the lines between nodes have been replaced by textured quads), user interface (descriptions are displayed for selected AS). Once I have improved the still rudimentary 3D navigation I will try to get the whole graph to render at once using an improved layout and a clustering algorithm.

Other interesting sub-projects are accessing the UPDATE messages from bgp-mon in realtime and integrating further information such as the as_rel dataset from CAIDA.

Stay tuned for more screenshots soon!