Advanced Reservation Simulator (ARS)

Author: Niloofar Fazlollahi Advisor: Professor David Starobinski

Introduction

The Advanced Reservation Simulator (ARS) generates random network topologies with manageable network parameters. Then, it emulates online random generation of transmission requests over the network. The underlying network is assumed to support in advance reservation of dedicated channels for transmissions. Thus after generation of each request, ARS reserves a route accordingly. Reservation of dedicated channels in advance is demonstrated as one of the requirements of ultra-high-speed networking applications. Please click here for information on advanced reservation in ultra-high-speed networking. Some existing high-speed network test-beds are UltraScience Net, DRAGON and LambdaRail.

ARS is based on our proposed algorithmic framework called Graded Channel Reservation (GCR) (check here). GCR grades available paths between the source/destination pair of the transmission based on predetermined criteria and assigns the highest graded path to the connection. GCR framework consists of the basic GCR algorithm itself and several extensions to it:

• GCR

• GCR_switch

• GCR_minimum

• GCR_limitx

In GCR a single fixed path is reserved which is best according to specified criteria. This criterion may be anything such as connection delay, path length, or path width. GCR_switch is a lot similar to GCR but path needs not be fixed during a connection and it can switch at any time. This can lead to significant performance improvement. GCR_minimum keeps number of path switches per connection at minimum. GCR_limitx bounds total number of path switches per connection by x.

ARS

ARS reads network topology from user input. Then, it generates random connection requests between random pairs where each request consists of {source, destination, connection bandwidth, connection duration}. User can select one of several probability distributions provided for each parameter (See explanation on input parameter file below). ARS returns to the user the earliest connection time that meets user demands. Various ARS executables are provided based on various GCR algorithms described above and are accessible below. All ARS algorithms are implemented based on the following technique: time is divided into slots that are formed spontaneously when any connection starts or ends in the network and are delineated by such connection start or end times (Note no granularity is introduced to time). The basic ARS, based on basic GCR, does the following upon arrival of each request:

• ARS reads in the network state (how the nodes are connected and how much bandwidth is left on each link)

• Edges with insufficient bandwidth are crossed out

• Available bandwidth on each edge at consecutive times slots, are intersected for as long as the requested time interval. Thus, a graph is obtained whose edge bandwidths are intersection of available bandwidths during the requested interval.

• A Breadth First Search (BFS) is carried out on the resulting intersection graph to find the shortest path from source to destination of the connection:

• If BFS fails, a new intersection and path search is carried out starting at the next time slot

• Else, ARS returns this path as the earliest shortest path for connection.

Other extensions to ARS, such as ARS_switch, ARS_minimum, and ARS_limitx use a similar framework but with some differences regarding number of paths allowed per connection. For example in ARS_switch we no longer search for a fixed path that lasts for the whole connection duration; we can reserve an independent path per each slot. Thus, we do not do the intersection of resources step as we did in ARS.

User instructions

You can download the ARS executables below. You can run any of the executable files either directly from terminal or by running the executer Perl script provided below. When running directly, user can set all simulation parameters (except the topology settings) through the screen. Meaningless input values are discarded and set to the default value after a warning appears on the screen. If you run the executables through Perl script an input parameter file should be created and inputs are no longer set through the screen. The required arrangement for this file is explained in the following.

In order to run the executable (either directly or using the Perl script 'executer.pl'), you need to create a file called 'input-topology.txt' in the same location as the executable and write the adjacency matrix of the topology into the file. An example is provided below:

Fig. 1: (a) Sample input network (b) network adjacency matrix

Each non-zero element in row i and column j of the matrix specifies a directed link from node i to node j. Network size (number of nodes in the network) can be any number no larger than 20 . Network size is implicitly calculated by the simulator given the network adjacency matrix.

For example, writing the above matrix to file 'input-topology.txt' results network size of 4.

Note that in this model, link capacities are all the same and its value is determined by a parameter through an input file called 'input-parameters.txt'. The structure of this file is explained below. Output statistics are written to file 'average-delay.txt' as explained below.

User can request multiple simulations, each with different set of parameters while keeping the same topology. Note that each simulation may consist of several runs of the code with the same parameters. Our performance measure is average delay in hours which is defined as the average time elapsed since a request is placed until transmission start time. For each simulation, starting at an initial load the average delay calculation is repeated number of runs times at each load (Network load or load is a parameter defined as the total number of requests generated between all pairs per unit time). Then it increments the value of the load by the specified step-size received by user though 'input-parameters.txt' and repeats the same process at the new load. This process continues until the average delay calculated at all of the runs exceeds the maximum average delay specified by user.

Parameters input file:

'input-parameters.txt' is an input file in which user writes the value of all control parameters in a certain format. Each line of 'input-parameters.txt' should contain a full set of parameters for one simulation. The parameters in each line of 'input-parameters.txt' should be written in the following order from left to right:

1. Simulation number (integer starting from 1)
2. Link capacities in Gigabit/second (float > 0 )
3. Initial network load value in requests/hour (float >= 0 )
4. Constant increment in the load value in requests/hour (float > 0 )
5. Maximum desirable average delay in hours (float > 0 )
6. Number of requests per each run (number of requests that make up one average statistics) (integer > 0 )
7. Total number of runs at each load value ( integer > 0 )
8. Mean connection duration requested in hours (float > 0 )
9. Choice of probabilistic distribution for request inter-arrival time (value 1: uniform, value 2: exponential). Note that mean inter-arrival request time is 1/'load value' and it is measured in hours. 10. Choice of probabilistic distribution for destination selection (value 1: uniform, value 2: 50% hotspot) 11. Choice of probabilistic distribution for requested connection bandwidth (value 1: uniform ranging from 1 to half the 'link Capacities' (in Gigabits/seconds), value 2: 80% chance 1 Gigabits/seconds and 20% chance half 'link capacities') 12. Choice of probabilistic distribution for requested connection duration (value 1: exponential, value 2: Pareto). Note that mean value of connection duration in hours is determined by parameter 7. 13. Upper bound on maximum allowable path switches per connection (integer ≥ 0 )

The last parameter is only required when running ARSlimit executable. Otherwise it should be removed from the input parameters file.

If one wants multiple simulations with different parameters using the same topology, it is easily doable by appending lines with desired input parameters to 'input-parameters.txt'.

Note that if the value of one parameter is out of its meaningful range, the program will automatically set it to default and print a warning on the screen. A sample 'input-parameters.txt' file is illustrated below:

Sample Input parameter file

The first line corresponds to the first simulation which starts at an initial average load of 1 request/hour and the maximum accepted value of average delay is 4 hours. 3 runs are carried out per load. The second simulation has a different load increment step and maximum delay is 5 hours. There will be only 2 runs per load.

Output file:

Whether run directly or through the Perl script, a single output text file is generated whose name will be 'average-delay-' followed by the name of the executable. Each line of the file relates to one load value. The first value in each line is the average load value and statistics for different runs at that load value are written in subsequent columns of the same line. Different simulations are delineated from each other by a line and simulation number. Below is a sample output resulting from the above input:

Sample output file corresponding to the above inputs

Downloads

The executable files below are Linux compatible. If execution permission is denied for any of the downloaded files please set the owner permissions to --x primarily (e.g. using command 'chmod o=x filename'). Windows users can run the executables using Cygwin which can be downloaded from the cygwin-website.

Executables:

• ARS

• ARS_switch

• ARS_minimum

• ARS_limitx

• Perl script

Extra

• Exponential distribution:

• Pareto distribution:

Acknowledgment

This research is supported in part by the US Department of Energy under ECPI grant DE-FG02-04ER25605.