Project Report:

Submitted by:

Anshul Kundaje

abk2001@columbia.edu

M.S. Electrical Engineering

Columbia University

Advisors:

Dr. Rolf Stadler

Koon Seng Lim

Introduction:

The project extended over the Fall semester of 2001 and involved extending the capabilities of SIMPSON. The following goals were accomplished:

1. Study of Navigation Patterns [1] for Scalable Internet Management
2. Study of the Universal Topology generator BRITE [2] and related graph models.
3. Extending SIMPSON to read BRITE’s output format
4. Added support for scrollable topology display window

Navigation Patterns for Scalable Internet Management:

Due to the lack of up-to-date centralized network data, global operations are difficult in large and diverse networks such as the Internet. State information needs to be collected directly from all the nodes. The aim is to develop an algorithm that optimizes time and traffic complexity. Navigation patterns is one solution. It is based on the methodical use of distributed control schemes. The navigation pattern defines the degree of parallelism and internal synchronization of a distributed management operation. This concept is described below, in brief.

The execution of a management operation involves the mapping of a global operation onto local operations and the aggregation of the results. A navigation pattern defines the process by which these local operations are distributed and their results aggregated. This allows the separation of the semantics of a management operation from the control flow. The concept of navigation patterns can be realized in various ways. It involves the exchange of messages between the network nodes based on a certain pattern. The control message may contain a mobile agent, program code/state, or simply execution state related to the management operation.

The echo pattern is a navigation pattern with the very useful property of being scalable and adaptive to network topology. It is based on the class of parallel graph traversal algorithms known as echo/wave-propagation algorithms.

The echo pattern functions on a 2 phase operation:

• In the expansion phase, the flow of control emanates from the node connected to the management station outwards via messages called explorers. These carry the control messages to perform management operations and result aggregation. Upon receiving a message for the first time, a node sends explorers along all direct links excluding the link from which the explorer arrives. If an explorer arrives at an already visited node, the node sends an echo back on the same link. If the explorer arrives at a leaf node, the requested operation is performed and the result is sent as an echo.
• In the contraction phase, a node waits until it has received an echo for every explorer it has sent out. It then aggregates the result from its own operation and those contained in the echo and this result is propagated back on its original explorer link.
• The whole operation ends when the node connected to the management station has received and aggregated all the echoes from its immediate neighbors.

In the case of the echo pattern, a change of the execution graph can affect the time complexity but the traffic complexity remains the same.

SIMPSON is used to simulate these navigation patterns and analyze data obtained from the simulations for various topologies. Topology generators like BRITE generate topologies based on different models. The navigation patterns are tested on these topologies.

SIMPSON- A SIMple Pattern Simulator fOr Networks:

SIMPSON is a tool for

1. Exploring performance and behavior of pattern-based management systems via simulation

1. Developing and testing pattern-based management programs.

The components and features of the tool include:

1. A software framework for developing (dynamic-link) libraries of patterns, aggregators and operators;
2. A debugging environment that allows the interactive control of the execution of a management program during run-time, including pausing it, resuming it, and tracing it;
3. A graphical user interface that allows real-time visualization of the distributed state of the management program as it executes;
4. Performance counters and utilities for logging and exporting run-time performance data for further processing by external programs.
5. Scenario authoring capabilities to simulate random node and link failures as well as to run canned demos with documentary;
6. Batch execution capability to run simulation non-interactively.

Typical operations to conduct a simulation are as follows:

1. Load topology, pattern and aggregator program files
2. Run simulation
3. Export simulation statistics
4. Plot statistics

The SIMPSON v1.1 input file format was as follows:

Universal Topology Generator BRITE:

BRITE is a universal topology generator developed by researchers at Boston University [2].

An ideal topology generator should enable the use and development of generation models that produce accurate representations of Internet topologies. Thus, it should include features that appeal to the researcher who is in need of accurate synthetic topologies for studying the correctness and performance of protocols and algorithms, as well as to the researcher who is in search for better and more powerful generation models. The following is a list of desirable characteristics for a topology generator.

1. Representativeness.
2. Inclusiveness.
3. Flexibility.
4. Efficiency.
5. Extensibility.
6. User-friendliness.
7. Interoperability.
8. Robustness.

BRITE was designed to be a flexible topology generator, not restricted to any particular way of generating topologies. As such, it supports multiple generation models. The figure depicts a schematic view of the structure of BRITE as it is being used at Boston University. The different components are labeled (1)-(4).

BRITE reads the generation parameters from a configuration file (1) that can be either hand written by the user or automatically generated by BRITE's GUI. BRITE provides the capability of importing topologies (2) generated by other topology generators (GT-ITM [3], Inet [4], Tiers [5], BRITE 1.0 [6]) or topological data gathered directly from the Internet (NLANR [7], Skitter [8]). It is possible to generate topologies using BRITE and then reuse them to generate other topologies by combining them with BRITE models or other imported formats.

The distribution of BRITE used contained eight different generation models namely:

1. Flat Router models: a. Waxman b. Barabasi-Albert models
2. Flat Autonomous system models: a. Waxman b. Barabasi-Albert models
3. 4 Imported formats: GT-ITM, NLANR, INet, Imported BRITE

Waxman Model: basically refers to a generation model for a random topology using Waxman’s probability model for interconnecting the nodes of the topology, which is given by:

0 < a,

b <= 1,

d is the Euclidean distance from node u to node v,

L is the maximum distance between any two nodes.

Barabasi-Albert Model: This model suggests two possible causes for the emergence of a power law in the frequency of outdegrees in network topologies: incremental growth (refers to growing networks that are formed by the continual addition of new nodes, and thus the gradual increase in the size of the network) and preferential connectivity (the tendency of a new node to connect to existing nodes that are highly connected or popular)

Nodes are connected according to the incremental growth approach. When a node i joins the network, the probability that it connects to a node j already belonging to the network is given by:

Also, we can incorporate these models in hierarchical models. There a 2 types of hierarchical models:

1. Top-Down approach
2. Bottom-Up approach

Top-Down Approach: Top-down means that BRITE generates first an AS-level topology according to one of the available flat AS-level models (e.g. Waxman, Imported File, etc.). Next, for each node in the AS-level topology BRITE will generate a router-level topology using a different generation model from the available flat models that can be used at the router-level. BRITE uses an edge connection mechanism to interconnect router-level topologies as dictated by the connectivity of the AS-level topology. The basic edge connection methods provided with BRITE operate as follows. If (i; j) is a link in the AS-level topology, then pick a node u from the router-level topology associated with AS node i, RT(i), and a node v from the router-level topology associated with the AS node j, RT(j), such that:

1. Random: u is picked randomly from RT(i) and v randomly from RT(j)
2. Smallest degree: u and v are nodes with the smallest degrees in RT(i) and RT(j), respectively.
3. Smallest degree non-leaf: u and v are nodes of smallest degree in RT(i) and RT(j) respectively but are not leaves.
4. Smallest k-degree: u and v are nodes of degree greater that or equal to k in RT(i) and RT(j) respectively.

The final topology is obtained by flattening the hierarchical topology into a router-level topology composed of the individual topologies associated with each node at the AS-level.

Bottom-Up Approach: In this model, BRITE first generates a router-level topology using any of the available models. Once this topology has been constructed, BRITE assigns to each AS node (level-2 node) a number of routers according to an assignment type specified by the user. With this number of assigned routers to an AS node, BRITE groups that many nodes from the router topology following a grouping method specified also by the user as a parameter to BRITE. This model is just an experimental model.

The process of topology generation is divided into a four-step process:

1. Placing the nodes in the plane

2. Interconnecting the nodes
3. Assigning attributes to topological components (delay and bandwidth for links, AS id for nodes, etc.)
4. Outputting the topology to a specific format.

Placement of Nodes: Nodes can be placed based on a random or a heavy-tailed distribution.

Assignment of Bandwidths: BRITE assigns bandwidths to links according to one of four possible distributions. The user specifies in the configuration file passed to BRITE, which distribution is going to be used (BWdist), along with a minimum (BWmin) and maximum (BWmax) values for possible bandwidths that can be assigned.

BRITE assigns a bandwdith to each link that is either:

1. Constant: the value specified by BWmin (equal for all links in the topology).
2. Uniform: a value uniformly distributed between BWmin and BWmax.
3. Exponential: a value exponentially distributed with mean BWmin.
4. Heavy-tailed: a value heavy-tailed distributed (Pareto with shape 1.2) with minimum value BWmin and maximum value equal to BWmax.

The parameters used by BRITE are shown below:

~:Flat topology parameters:~

~:Top-Down Approach Parameters:~

~: Bottom-Up Parameters:~

BRITE Output format:

A BRITE-formatted output file contains three sections:

1. Model information: information about the topology contained in the file. Includes number of nodes and edges, and information specific to the model used to generate the topology.

2. Nodes: for each node in the graph, a line is written into the output file with the following format : NodeId xpos ypos indegree outgdegree ASid type.

The table below explains the meaning of each:

A sample output file is shown below:

Values of -1 indicate that the parameter is not applicable for the model used.

Extending SIMPSON to read BRITE’s output format:

This was accomplished in two steps:

1. Initially a stand alone program was written which parsed files in BRITE format and converted them to native SIMPSON v1.1 format. The program was written in C++. It was tested on GNU C++ compilers. The program is attached in the appendix section of this report. SIMPSON was tested on the files created by the program.
2. The next stage of the project involved extending SIMPSON itself to read BRITE output files directly. The main code for this is present in the files topology.cpp : in the libcore source files
   topology.h : in the libcore header files
   The new version of SIMPSON v1.4 reads BRITE files directly.

Support for scrollable topology display window:

SIMPSON v1.1 was unable to accommodate large topologies. The simplest way to extend this was to enable scrolling in the topology display window. The CNetView class was added. It was derived from CScrollView which has a large part of the scrolling functionality built within it. This part of the project involved a study of Visual C++ 6.0 especially the View Classes. The functions related to scrolling in the implementation files are

SetScrollSizes(MM_TEXT, CSize(1000,1000));

void CNetView::OnDraw(CDC* pDC)

void CNetView::on_event(NodeEvent event, void *event_info)

Version 1.4 thus has scrolling capabilities and allows visualization of networks as large as 10,000 nodes.

Another enhancement to the visualization of the topology is the addition of a background image. This was implemented by Koon Seng Lim.

Appendix:

Makefile:

default:

g++ -Wall -o project project.cpp

clean:

rm -f project project.cpp~ makefile~ output.top

Project.cpp

#include<string.h>

#include<stdlib.h>

#include<iostream.h>

#include<fstream.h>

/***********************************************

The node class

***********************************************/

class node

{

private:

long int nodeid; //node id

float xpos,ypos; //xpositon and y position on the plane

long int indegree,outdegree; //indegree & outdegree of node

long int asid; //autonomous system id

char type[20]; //type of node

long int * nid; //array of nodeids to which the node is connected

long int nconn; //number of neighbor nodes currently connected

public:

node(); //constructor

~node(); //destructor

void setnodeid(long int x){ nodeid=++x; } //sets nodeid

void setxpos(float x){ xpos=x; } //sets xposition

void setypos(float y){ ypos=y; } //sets yposition

void setindegree(long int x){ indegree=x; } //sets indegree of node

void setoutdegree(long int x){ outdegree=x; } //sets oudegree of node

void setasid(long int x){ asid=x; } //sets asid

void settype(char *x){ strcpy(type,x); } //sets type

void addnid(long int x); //add a neighbor node id to the array nid

void output1(char*filename); //output format 1

void output2(char*filename); //output format 2

};

node::node()

{

nodeid=-1;

xpos=-1;

ypos=-1;

indegree=0;

outdegree=0;

asid=-1;

strcpy(type,"none");

nid=NULL;

nconn=0;

}

node::~node()

{

if(nid) delete []nid;

}

void node::addnid(long int x)

{

if (nid==NULL) nid=new long int[indegree];

nid[nconn]=++x;

nconn++;

}

void node::output1(char* filename)

{

ofstream ofile(filename,ios::app);

if (!ofile.good())

{

cerr << "Error creating output file" << endl;

exit(0);

}

ofile << nodeid << " | " << xpos << " " << ypos << endl;

ofile.close();

}

void node::output2(char* filename)

{

ofstream ofile(filename,ios::app);

if (!ofile.good())

{

cerr << "Error creating output file" << endl;

exit(0);

}

ofile << nodeid << " ";

for( long int i=0; i<indegree; i++ )

ofile << nid[i] << " ";

ofile << endl;

ofile.close();

}

/*****************************************************

main function

*****************************************************/

int main(int argc, char *argv[]) //argv[1] is the inputfile path and name

{ //argv[2] is the output file path and name

long int numnodes; //number of nodes in the graph

long int numedges; //number of edges in the graph

long int planel; //length of plane relative to which the x and y position of a node are defined

long int planeb; //breadth of plane realtive to which the x and y position of a node are defined

/***************************

error checking for arguments

****************************/

if(argc!=3)

{

cerr << "Illegal Input format:Requires 3 arguments:project <inputfile> <outputfile>" << endl;

exit(0);

}

/*************

opening files

**************/

ifstream ifile(argv[1],ios::in|ios::nocreate);

if (!ifile.good())

{

cerr << "Error opening input file: It must exist to be read" << endl;

exit(0);

}

ofstream ofile(argv[2],ios::out);

if (!ofile.good())

{

cerr << "Error creating output file" << endl;

exit(0);

}

/******************************

parameters for the output file

*******************************/

float lspeed,latency,p_overhead,size_mssg;

cout << "Enter link speed in bps" << endl;

cin >> lspeed;

cout << "Enter latency per hop in secs" << endl;

cin >> latency;

cout << "Enter the protocol overhead per message in seconds" << endl;

cin >> p_overhead;

cout << "Enter the size of messages in bytes" << endl;

cin >> size_mssg;

/*******************

the parsing begins

*******************/

ifile.seekg(0,ios::beg);

char *buff; //temporary buffer "buff"

buff=new char[600];

ifile.getline(buff,600); //skip first line

for(int i=0; i<4; i++) ifile >> buff; //skip next 4 strings

delete []buff;

ifile >> numnodes >> planel >> planeb; //save next 3 long ints namely numnodes, planel, planeb

/*************************

create the array of nodes

*************************/

node *list;

list = new node[numnodes];

/********************

parsing continues

********************/

buff=new char[600];

for(int i=0;i<3;i++) ifile.getline(buff,600); //skip 3 lines

/************************************************

parse the node section of the BRITE output format

************************************************/

for(long int i=0; i<numnodes; i++)

{

long int j,m;

float k;

char *l;

l=new char[20];

ifile >> j; //read nodeid

list[j].setnodeid(j);

ifile >> k; //read xpos

list[j].setxpos(k);

ifile >> k; //read ypos

list[j].setypos(k);

ifile >> m; //read indegree

list[j].setindegree(m);

ifile >> m; //read outdegree

list[j].setoutdegree(m);

ifile >> m; //read asid

list[j].setasid(j);

ifile >> l; //read type

list[j].settype(&l[0]);

delete []l;

ifile.getline(buff,600); //skip the rest of the line

}

/**************************************************

parse the edge section of the BRITE output format

**************************************************/

ifile.getline(buff,600); //skip next line

ifile >> buff;

char temp;

ifile.get(temp); //skip next 2 characters

ifile.get(temp);

ifile >> numedges; //read number of edges

ifile.getline(buff,600); //skip the rest of the line

/*********************************

set the neighbors of all the nodes

*********************************/

for( long int i=0; i<numedges; i++)

{

long int j;

long int from;

long int to;

ifile >> j >> from >> to; // read the edgeid, fromnode and tonode:NOTE: the graph is undirected

list[from].addnid(to); // add the tonode to the nid array of the fromnode

list[to].addnid(from); // vice versa

ifile.getline(buff,600); //skip the rest of the line

}

/****************

output into file

****************/

ofile << "SIMPSON TOPOLOGY FILE V1.1" << endl;

ofile << lspeed << endl;

ofile << latency << endl;

ofile << p_overhead << endl;

ofile << size_mssg << endl;

ofile << numnodes << endl;

ofile << "No" << endl << endl;

ofile.close();

for( long int i=0; i<numnodes; i++)

{

list[i].output1(argv[2]);

}

ofile.open(argv[2],ios::app);

if (!ofile.good())

{

cerr << "Error creating output file" << endl;

exit(0);

}

ofile << endl;

ofile.close();

for( long int i=0; i<numnodes; i++)

{

list[i].output2(argv[2]);

}

delete []buff;

delete []list;

ifile.close();

return 0;

}

References:

[1] K.S. Lim and R. Stadler, "A Navigation Pattern for Scalable Internet Management," March 10, 2001, CTR Technical Report 503-00-01

[2] Alberto Medina et al. “BRITE: Universal Topology Generation from a User’s Perspective” http://cs-www.bu.edu/brite/publications/usermanual.pdf

[3] K. Calvert, M. Doar, and E. Zegura. Modeling Internet Topology. IEEE Transactions on Communications, pages 160–163, December 1997.

[4] C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report Research Report CSE-TR-433-00, University of Michigan at Ann Arbor, 2000.

[5] M. Doar. A Better Model for Generating Test Networks. In Proceeding of IEEE GLOBECOM, November 1996.

[6] A. Medina, I. Matta, and J. Byers. On the Origin of Power-laws in Internet Topologies. ACM Computer Communication Review, pages 160–163, April 2000.

[7] National Laboratory for Applied Network Research (NLANR). http://moat.nlanr.net/rawdata/.

[8] K.C. Claffy and D. McRobb. Measurement and Visualization of Internet Connectivity and Performance. http://www.caida.org/Tools/Skitter.