Based on the ETAG algorithm by Edy Tan and Andres Guedez

Advisor: Prof. David Starobinski

Introduction

The ETAG GUI is a Java Swing front end to the ETAG algorithm. ETAG is a file transfer scheduling algorithm based on the All-Slots algorithm developed by the Department of Energy for their Ultrascience Net.

This UltraScience Net is a very high speed network created by the DOE with the purpose of having dedicated lines for their scientists to transfer very large files accross. Faced with the troublesome task of sometimes having to transfer data sets in the Petabyte range, the DOE realized that their network could be much improved if they provided links across which guaranteed speed and bandwidth could be achieved.

Please refer to the DOE UltraScience Net webpage for more information.

ETAG

ETAG is based on the Floyd-Warshall All-Pairs Shortest Path algorithm. The main purpose of the algorithm is to find the "best path" from any two nodes across the network while taking into consideration the amount of bandwidth required and the time that the transfer must be scheduled for.

In order to do this, ETAG carries out the following steps:

• Read in the network state (how the nodes are connected, how much bandwidth is left in each link, what transfers are currently happening, etc)
• Discard all the timeslots in which the request couldn't possibly be fulfilled (not enough bandwidth is left for the required amount of time).
• Run a modified version of the Floyd-Warshall algorithm in which timeslots are created and stored for all the possible paths through which the request could be fulfilled.
• Once we have all these paths, we can decided which one is "best". This is done by using shortest, widest or earliest path algorithms or a combination of them. The shortest path is defined as that through which the least number of nodes are traveled. The earliest path is that in which the request is serviced at the earliest possible time from when the request was made. The widest path is that which leaves the most available bandwidth after the request has been serviced.

A lot of optimization can be done in this last step since the different algorithms used to select the final path can provide drastically better or worse perfomance depending on the load of the network.

GUI

The purpose of the GUI is to provide a tool that makes it easier to see and understand the inner workings of the algorithm. Once the GUI is completely finished it will be able to create timetables and plots that allow the user to analyze the results after running a simulation. The ability to graphically analyze the data will make it much easier for the researcher to separate those changes that work best from those that don't when trying to optimize the algorithm.

Requirements

The GUI requires the following external libraries in order to compile:

• Grappa. Used for the creation and display of the graph that displays the network. It offers very nice features like being able to create the graph by clickin on the screen and automatic layout of all the components by communicating with a server that has the dot layout engine.
• JFreeChart. Used for creating and manipulating the plots that will be created after running a simulation.

Screenshots

At startup:



Running:



User Manual

For instructions on how to use the program please read the user manual.

Download

Click here to download the code.

How to Compile

• Make sure that you have both external libraries need. They are listed under Requirements.
• Make sure that your CLASSPATH variable is set to include the working directory and the directory where the jar files for the libraries are stored.
• Compile the program with javac EtagGui.java.
• Run it with: java EtagGui samplefile.dot

Acknowledgment

This research is supported by the US Department of Energy under ECPI grant "A Theory of Stability in Communication Networks" (DE-FG02-04ER25605). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the US Department of Energy.

Laboratory of Networking and Information Systems

Room 413 Photonics  Building

8 St Mary's Street, Boston MA 02215

Web site created by Sachin Agarwal

Maintained by Weiyao Xiao (weiyao@bu.edu)