DRMSim - Sophia Antipolis
Contents
1. where priority is on performance for the sake of simulation on large networks this efficient but less flexible approach was opted for As explained before the main goal of DRMSIM is to quantitatively evaluate some of the main performance metrics of the routing models and especially those related to scalability and stability The following performance metrics have been in DRMSIM other can easily complement this set e Stretch the stretch of a routing scheme is defined as the ratio over all source destination pairs between the routing scheme path length and the minimum path length actual distance for the same source destination 10 pair Intuitively the stretch is a quality measure of the paths length in crease as produced by a routing scheme compared to shortest path lengths Shortest path routing either AS path length based path vector routing or cost metric based link state routing are stretch 1 This metric is inter esting to measure since compact routing schemes usually since producing reduced routing tables are not always able to choose the minimum path for a given destination but on the other hand the routing scheme should favour selection computation of routes whose stretch remains closer to 1 e Routing table size it is calculated using the size of a single entry and the number of entries in the routing tables RT RT size is directly related to routing system scalability because the less memory a router needs to s2. 4 6 GT ITM Aone of the most popular generators available is 1 The following text is taken from 8 The main characteristic of GT ITM is that it provides the Transit Stub TS model which focuses on reproducing the hierarchical struc ture of the topology of the Internet In the TS model a connected random graph is first generated e g using the Waxman method or a variant of it Each node in that graph represents an entire Transit domain Each transit domain node is expanded to form another connected random graph representing the backbone topology of that transit domain Next for each node in each transit domain a number of random graphs are generated representing Stub domains that are attached to that node Finally some extra connectivity is added in the form of back door links between pairs of nodes where a pair of nodes consists of a node from a transit domain and another from a stub domain or one node from each of two different stub domains GT ITM also includes about five flavors of flat random graphs We sent a mail to the authors to get a version that works on Linux The source code was designed for SunOS and cannot get compiled on Linux Ubuntu 22 6 4 7 CAIDA Ar he Cooperative Association for Internet Data Analysis CAIDA provides data about the structure of Internet The router level topology map is par ticularly relevant to us It can be downloaded at the following URL http wiw caida org tools measurement ski
3. area network for RMI Mascsim cooperative hosts 4 Software architecture In this section we describe the software architecture of DRMSIM and explain the choices that were made so as to be able to simulate large scale networks and maintain modularity of the code 4 1 Module dependencies Routing simulator DRMSim MET GEN Discrete event Simulator Mascsim Graph model Dipergrafs N Java Unix bridge java4unix Graphical view Graphstream ict Pd Java Runtime Environment v1 5 or later Figure 1 The dependencies of modules Figure 4 1 represents the DRMSIM modules and their dependencies DRM SIM relies through the Javadunix framework on UNIX facilities DRMSIM relies also on DIPERGRAFS for the network and topology models and on MASOSIM for the discrete event simulation engine The Graphstream mod ule can be used to obtain a view of the routing scheme In practice each of these modules comes as a JAR file that must be included in the JVM classpath The installation procedure of DRMSIM automates the process of downloading the modules and installing them in the UNIX user account More details concerning these modules are given in the following 4 1 1 Mascsim MASCSIM operates at the level of the simulation it models and implements a distrbuted discrete event simulation infrastructure It defines the following entities the simulation the system t
4. overhead The computational complexity is defined as the number of cycles needed to recompute a RT entry for a given destina tion and insert it as part of the RT or replace remove an existing entry in the RT To validate and test DRMSIM we have implemented many different routing schemes from simple ones such as source routing to more complex ones such as BGP We describe these algorithms in the next Section 11 4 4 Graphical monitoring of the routing process DRMSIM comes with a set of command line tools which allow the execution of simulation campaigns and the extraction of results Also for the purpose of monitoring which is of paramount importance when prototyping distributed applications an aircraft view of the network is also provided 5 Introduction to routing The Internet is organized in a number of AS Autonomous System An Au tonomous System AS is an administative entity which consists in a collection of connected IP routing prefixes under the contro of one or more network op erators that presents a common clearly defined routing policy to the Internet AS inner and outter routing obey to different rules Two classes of protocols are then defined IGP Interior Gateway Protocol and AGP Exterior Gateway Protocol 5 1 Routing in the current Internet Routing over the current Internet is achieved by the the coupling of hierarchical addressing and a set of routing protocols Most commonly found include BGP Bor
5. BGP Morever the simulation model is too rich the mem ory and CPU consumption required makes it hardly usable on large topologies Unlike the former simulator C BGP 10 was designed to work on topologies of several thousands of ASes This simulator built as an efficient decision process simulator allow experimentations on BGP protocol and attributes However it lacks temporal dimension as the simulator does not implement BGP timers nor messages delays link crossing delay router CPU waiting Another large scale BGP simulator was proposed in 5 Its aim was to run BGP simulations on several thousands nodes topologies by keeping the temporal delays introduced by the BGP timers But like all the previous simulators this one uses Log ical AS topologies ignoring IBGP interactions and the effects of AS internal event on the convergence Same goes for the RouteSim BGP simulator 9 Althought the model was abstracted enought to allow large topologies simula tion it lacked realistic temporal delay model not allowing the observation of user traffic variation consequences on BGP signalisation Another way in BGP simulator conception was explored by the creators of BGP By integrating a real BGP implentation into a simulator the simulations gained a realness never obtained before but the low level of abstraction made memory and CPU consumption too large to allow large topologies simulation 6 2 3 RIP The Routing Information Protocol or RI
6. DRMSIM a network simulator for the investigation of routing schemes User manual Luc Hogie Issam Tahiri Dimiti Papadimitriou Fr d ric Majorczyk Mascotte project INRIA Sophia Antipolis FR LaBRi University of Bordeaux FR 3 Alcatel Lucent Bell Antwerpen BE February 1 2010 Contents 1 Package overview 4 2 Installation 4 2 1 Prerequisite mia e do eh ee a ee ye idee 4 2D Procedure ie Wu tau aa A SEG ES atin 5 2 9 Pileseirist lled poa e 4 49 66 fe a e tai RUP bes 5 3 DRMSim s commands 6 4 Software architecture 8 4 1 Module dependencies 00000000 8 ATL MASESIM n e ci le a OR Baad uu 8 4 1 2 Dipergr tsc 2 epo A ee m 9 45143 JAVA AU uk aac Ge ee i AI Adi a AE ES RU EUR S 9 4 L4 Graphstream ee lt 6 4 2062 004444 RR PS 9 4 2 Object oriented model llle 9 4 3 Measurement model 00000000 9 4 4 Graphical monitoring of the routing process 12 5 Introduction to routing 12 5 1 Routing in the current Internet o o 12 5 2 Classification of routing protocols 0 13 5 2 1 Distance vector and link state protocols 13 5 2 2 AS level or router level routing les 13 6 Simulation models 13 6 1 Network model aa ae eee et 24 4 4 44 EX 33443434494 14 6 1 1 On memory consumption and computational performance 14 6 2 Routing protocols oe usd a a Renee Pages ond 14 6 2 1 Standard set aam 6464 645084 04 aaas ee eas 14 0 2 2 BG
7. In this scenario a source and a destination are defined at random Then routing are scheduled in a sequence until one succeeds Then the simulation stops 7 8 2 All to all 7 8 3 DoNothing Instantiate the system and immediatly stop 7 9 monitor a simulation process In order to enable the monitoring of the simulation all along the simulation DRMSIM provides a bridge with the GraphStream graph rendering framework In order to enable the graphical rendering the line system listeners inria alu views BasicRoutingView must be uncommented 25 8 Implementation notes DRMSIM is developed and tested under the Java Development Kit version 1 6 0_12 b04 on a 64 bits Linux box It is not guaranteed that it will work on different platforms Also Graphstream have shown to fail on v1 7 virtual machines which makes views based on it unusable with this virtual machine 8 1 Code reuse A development strategy followed in the DRMSIM project is to maximize the use of existing code software hereby to minimize the number of lines of code written from scratch 8 1 1 Madhoc Madhoc 6 is Mobile ad hoc NETwork MANET simulator developed at the Universities of Luxembourg CSC lab and Le Havre LITIS lab Its pri mary objective is to enable researchers to investigate broadcasting protocols over MANETs The code of Madhoc is modular and allowed us to extract a number of reusable components In particular we will use its time slicing simulation e
8. P as it is more commonly called is one of the most enduring of all routing protocols RIP is also one of the more easily confused protocols because a variety of RIP like routing protocols proliferated some of which even used he same name RIP and the myriad RIP like protocols were based on the same set of algorithms that use distance vectors to math ematically compare routes to identify the best path to any given destination address These algorithms emerged from academic research that dates back to 1957 6 3 Metrics Definition implementation the metrics for the evaluation of routing protocols e the stretch of a routing path is the ratio between the length of this routing path and the length of the shortest path It takes its values in 1 inf The closer to 1 the better e size in bit of the routing tables The lower the better e size in bit of the message headers The lower the better e the amount of traffic that is generated for inter changing topology infor mations e number of entries in the routing tables The lower the better 19 e observed duration to go back to a steady state after a sudden change of the topology The lower the better Ano the algorithmic complexity of the routing function is an important met ric When the number of entries in the forwarding table is large the routing routine may fail to provide routing information efficiently Also the algorithmic comprehensiveness is to be looked at In or
9. P wara Bogle Arata MEME Nhe a aus 15 0 2 9 REBA 6 2 E Rbk See AA he lo ee vo Ae d 19 09 Met ris aid ut PORN atur ce ese Mee dno Soy A Ata eat eae 19 6 4 Topology generators 0 000052 eee 20 6 4 1 Standardiset si EE GE MASS 21 6 4 2 Randomized set es 21 6 43 Tier 1 Tier 2 Tier T3 o 21 0AA net uode a AE bee am ba 22 6 42 59 Brite ii A huoc 8 A eo le es a 22 0 16 9GTAIT Me Aiit Be A wu 22 64 7 GAIDAS cor ft Be o ee ud Meo ve aed 23 6 5 Dynamics 25s a a a ee eee A AA Cete ge ad at dd 23 6 6 Traffic model ex ica Ree ee Ek et 23 6 7 Time model ya ee a a A a 23 63 Granularity a aa x xov RU UE RA ee aa 23 7 Frequently Asked Questions FAQs 23 7 1 What is the input of the simulator 0 23 7 2 Is it possible to define my own topology 24 7 3 deal with the output e 24 7 4 How can I add a new metric ss 24 7 5 How can I generate a GLP graph o o 24 7 6 How to implement a new routing protocol 25 7 7 Is there a way to import a new topology CAIDA Inet 25 7 8 How to run DRMSIM 0048 25 T8 D One tOONeE 4 rada e A 25 TE AMO A A as AA a 25 8 3 DoNothing sc ed A DE LE Le eee ee as 25 7 9 monitor a simulation process 04 25 8 Implementation notes 26 8 1 Codede se oi tin Ae ek de ce BE A a th tina a a 26 81 Madhoc a eee o Shh Oh hd eye
10. a et d 26 841 2 Dipergrals i dew es AREA AE a a ci Rie tng 26 8 1 3 GraphStream 02002 00004 26 84 GCOBIDA 5 esas di m ture pU nena a a 26 8 1 5 Ploticus av E EE Oa i a ta A 27 8 2 dnvoc tioti s 2 ios Ru rRNA ee de deg 27 8 2 1 Drawing a network alu network printer 27 8 2 2 Running a simulation mascsim_compute_simulation 27 8 2 3 Running a simulation alu scan available topology generators 27 8 3 Results 8 4 Simulation campains 000000004 This working paper describes DRMS mm a software simulator that aims at the evaluation of routing protocols at a large scale Indeed most simulator do not allow the simulations of more than a few hundred nodes DRMSIM is an attempt to simulate up to ten thousand nodes on typical workstations Its development happens in the context of a study focusing on dynamic compact routing A key target is to provide a software that is able to handle simulated networks consisting of a mininum of ten thousands nodes This requirement imposes a careful analysis of the data structures that will be used in the network model as well as on the granularity and time management of the simulation model This joint research project is conducted by Alcatel Lucent Bell Universit de Bordeaux LaBri and INRIA labs at Sophia Antipolis Mascotte project It is funded by Alcatel Lucent Bell The design development philosophy of DRMSIM is make to compromise on the quality of the cod
11. ant time complexity Taking measure often requires additional possibly time consuming computations Another approach consists thus in taking only the metrics that might have be affected after an event executes This approach reduces the computational overload presented herein before but does not solve it the event defines a set of metrics which are potentially affected by its execu tion but there may still exist metrics which were actually not affected but for which new measures would still be computed For this purpose DRMSIM uses a different approach which consists in taking a measure as soon as the corresponding metric has actually been affected This approach effectively reduces additional computations to the minimum The simulation code becomes targeted to a specific simulation objective what has to be observed is hard coded in the events themselves In practice when an event performs an action of interest that affects the state of the system it can subsequently compute a new value for the corresponding metric and store this value in the measure history A drawback of this approach is that it introduces a dependency between the simulation and the measurement code if one decides to carry on the same simulation but look at different metrics the original code will have to be duplicated and modified Also specifying a new metric and its associate measure imposes a modification of the simulation code Nevertheless in the context of DRMSIM
12. brite 2010 01 04 16 38 41 jar lib mascsim 2010 01 20 11 58 52 jar lib up 2010 01 04 16 38 41 jar lib inria drmsim 2010 01 20 11 58 52 jar HOME bin contains the executable programs coming with DRMSIM bin mascsim cache clear bin mascsim result plotter bin drmsim bench protocol bin mascsim campaign bin mascsim develop config bin mascsim cache publish bin drmsim scan available topology generators bin mascsim result config extractor bin drmsim cleaner bin mascsim result info bin mascsim compute simulation bin mascsim cache info bin mascsim rmi lan scanner bin mascsim determine input filename bin mascsim result values extractor bin mascsim cache query bin mascsim result merger Those files are simple bash scripts that invoke tha java virtual machine 3 DRMSim s commands Just like any UNIX application DRMSIM appears to the user as a set of com mands The following commands are available drmsim bench protocol bench drmsim cleaner ALU file cleaner drmsim_network_printer ALU compact routing simulator performs simula tion of routing protocols on internet like dynamic networks drmsim scan available metrics scans for available class inria mascsim metrics Metric drmsim scan available topology generators scans for available class in ria dipergrafs topology Topology Generator mascsim cache clear Clears the result cache This operation is applied to the local cache stored on the local disk mascsim cac
13. communication session is set up between bordering autonomous systems using TCP listening port number 179 This communication session is required to stay connected which is used by both sides to periodically exchange and update information When this TCP connection breaks for some reason each side is required to stop using information it has learned from the other side 15 In other words the TCP session serves as a virtual link between two neighbor ing autonomous systems and the lack of communication means that this virtual link is down Now imagine that each autonomous system is a virtual supern ode then the entire Internet can be thought of as a graph connecting virtual supernodes by virtual links The first model The closest to reality implemented in the simulator corre sponds to the latter since every node is considered as an AS This means that it can simulate the external BGP communication EBGP in a an optimal way but not the internal one IBGP In a router where BGP is running many types of Routing Information Bases are stored First there is the Loc RIB which contains all the paths known by the router and that are actually used in the forwarding process in addition to this a BGP router has an Adj RIB IN and an ADJ RIB OUT for every adjacent node which is linked to by a virtual TCP connection The aim of these RIBs is to provide a neighbor based filtering for both incoming and outgoing advertised routes Since the security p
14. der Gateway Protocol is a EGP OSPF Open Shortest Past First is complex and resource demanding OSPF is a IGP IS IS Interior System to Interior System is the only OSI IGP IGRP Interior Gateway Routing Protocol is proprietary of Cisco Systems The large deployment of Cisco routers make it a largely used protocol IGRP is IGP RIP Routing Information Protocol RIP is a IGP RIP2 add VLSM and authentification functionalities to RIP EIGRP Enhanced IGRP is a Cisco proprietary routing protocol loosely based on their original IGRP EIGRP is an advanced distance vector routing pro tocol with optimizations to minimize both the routing instability incurred after topology changes as well as the use of bandwidth and processing power in the router Routers that support EIGRP will automatically re distribute route information to IGRP neighbors by converting the 32 bit EIGRP metric to the 24 bit IGRP metric Most of the routing optimiza tions are based on the Diffusing Update Algorithm DUAL work from SRI which guarantees loop free operation and provides a mechanism for fast convergence 12 5 2 Classification of routing protocols 5 2 1 Distance vector and link state protocols There are two major types of routing protocols some with variants link state routing protocols and path vector protocols distance vector routing protocols A distance vector routing protocol requires that a router informs its neigh bors of topology cha
15. der to have more details about the behavior of a protocol we are investi gating other metrics that we would like to add without decreasing the simulator performance and those are mainly e the Number of stable and transient updates generated during convergence In fact during convergence some candidate routes may become transient Upon occurence of an event E that necessitates reconvergence from the current state at each router we say that a candidate route r to a prefix p is transient if E causes the AS Path of r to be no longer valid A route with AS Path P AgA1A3 A for a destination d at node A444 with Ag being the origin AS is said to be transient if there exists some A 0 lt lt n 1 such that the AS Path of the route at A is not the same as AgA1A2 A Therefore during convergence candidate routes may be either stable or transient Note that in standard BGP procedures for instance it is not possible for a node to figure out if any of its candidate paths is transient e data plane convergence time A node or a set of nodes has reached data plane convergence when the node or set of nodes has a stable forwarding path to the destination implied by the unvarying next hop at the node and at each of the downstream nodes Data plane convergence is equivalent to forwarding convergence Note that an AS path at a node can change without causing a change of next hop at a node but next hop will not change unless there is a rou
16. des As a consequence Inet output cannot be visualized The dipergrafs project provides a front end to Inet through the class inria dipergrafs topology InetTopologyGenerator In order for the topology generation to work the Inet application must be in stalled on the computer and the inet command should be accessible through the PATH environment variable The path to the inet command can also be specified in the configuration file by filling the path to inet entry 6 4 5 Brite BRITE 8 is the precursor to the universal generation tool It implements a single generation model that has several degrees of freedom with respect to how the nodes are placed in the plane and the properties of the interconnection method to be used Under certain configuration of the parameters BRITE 1 0 generation model is equivalent to Waxman Under other configuration of parameters BRITE 1 0 implements the Barabsi Albert model proposed in 2 in which a network grows incrementally and the nodes interconnect with preference towards higher degree nodes The dipergrafs project provides a bridge to Inet through the class inria dipergrafs topology BriteTopologyGenerator To achieve this result Dipergrafs exploits a modified copy of the source code of Brite Indeed Brite was designed in such a way that it exploit the text based I O streams Modification of the source code consists in bypassing this interface in order to directly interact with the Brite s framework 6
17. e 1997 M Doar A better model for generating test networks In Proceedings of Globecom 796 Nov 1996 Antoine Dutot Fr d ric Guinand Damien Olivier and Yoann Pign Graphstream A tool for bridging the gap between complex systems and dynamic graphs In EPNACS Emergent Properties in Natural and Artifi cial Complex Systems 2007 Giorgio Gallo Giustino Longo Stefano Pallottino and Sang Nguyen Di rected hypergraphs and applications Discrete Appl Math 42 2 3 177 201 1993 Fang Hao and Pramod Koppol An internet scale simulation setup for bgp SIGCOMM Comput Commun Rev 33 3 43 57 2003 Luc Hogie The Madhoc Simulator Technical report Le Havre University http agamemnon uni 1lu lhogie madhoc 2005 Cheng Jin Qian Chen and Sugih Jamin Inet Internet topology generator Technical Report CSE TR 433 00 University of Michigan at Ann Arbor 2000 Alberto Medina Ibrahim Matta and John Byers On the origin of power laws in internet topologies Technical report Computer Science Depart ment at Boston University Boston MA USA 2000 J Nykvist and L Carr Motykova Simulating convergence properties of bgp pages 124 129 Oct 2002 Bruno Quoitin C BGP Users Guide 2005 Bernard M Waxman Routing of multipoint connections pages 347 352 1991 28
18. e written so that extensibility and reusability are maximized 1 Package overview The official webpage for the DRMSIM project is http www sop inria fr mascotte projets DCR The software is the union of several projects including MASCSIM a discrete event simulation platform http www sop inria fr members Luc Hogie mascsim A graph library http www sop inria fr members Luc Hogie dipergrafs A bridge between Java and UNIX http www sop inria fr members Luc Hogie java4unix And a graph render library http graphstream sourceforge net 2 Installation 2 1 Prerequisite In order to use DRMSIM you must have an UNIX operating system Of course Linux is fine The choice for the Java Virtual Machine is more tricky More UNIX computers around actually are Linux boxes Linux comes with a Java Virtual Machine GCJ According to its official website GCJ is a portable optimizing ahead of time compiler for the Java Programming Language It can compile Java source code to Java bytecode class files or directly to native machine code and Java bytecode to native machine code According to most users it does not work DRMSIM proved unoperational when running atop GCJ If DRMSIM or its installation program does not work on your machine checking the JVM is the first thing to do DRMSIM turns out to work fine with both Sun s official JVM and OpenJDK 2 DRMSIM was successfully tested on the following platforms u
19. he events the metrics the measures etc At this level the network is not considered MASCSIM also provides a set of tools for dealing with user simulations with simulation campaigns result processing and graph plotting 4 1 2 Dipergrafs DIPERGRAFS defines the concept and efficient implementations of network that is used in DRMSIM It also provide a set of algorithms and input output mechanisms for dealing with the corresponding data structure a directed hy pergraph 4 1 3 Java4unix Java4unix provides the glue between the Java implementation of DRMSIM and the UNIX operating system Specific issues related to the execution of Java applications are solved by Java4unix by bridging specific executable classes by bash scripts copied in the SHOME bin directory of the local user Java4unix also provides the capabilities required for the installation and updates of DRMSIM 4 1 4 Graphstream Graphstream is a graph rendering toolkit developed by Dutot and al at the Le Havre University Graphstream is used in DRMSIM as a routing monitor It allows the user to observe the behaviour of the simulated routing scheme at each step of its execution 4 2 Object oriented model DRMSIM is an object oriented application designed as a set of independent soft ware components In particular it uses the DRMSIM discrete event simulation engine itself derived from Madhoc a mobile wireless network simulator and the DIPERGRAFS l
20. he info Prints info on the local cache e g number of results stored mascsim cache publish Publish the given result file to a cache This can be applied either to the local cache or to the web cache mascsim_cache_query Query a cache and indicate whether the given result number identifies a result that is stored in the cache This can be applied to both local and web cache mascsim campaign Performs a simulation campaign In practise it generates a set of independant simulation jobs and execute them according to a given execution strategy mascsim_compute_simulation Compute the simulation job described in the given file mascsim determine input filename Determines the file name that the given input should have This name should match the name of the file mascsim develop config Develops the input configuration This configura tion must defined a set of parameters than will be deployed mascsim result config extractor Restore the mascsim file s taht were used to compute the given result file s mascsim result info Prints information on the content of given result files mascsim result merger Compute the average of a set of given result files The result is stored in a special result file mascsim result plotter Plots the content of result files The output is a PDF file mascsim result values extractor Restore the mascsim file s that were used to compute the given result file s mascsim rmi lan scanner Scans the local
21. ibrary Many components take part in the workflow of the MASCSIM simulation engine a simulation campaign is a set of execution for individual simulation computations Once all individual simulation have been completed the simulation campaign computes statistically confident results out of all results collected The way individual simulation are executed is called an execution strategy We have developed three different strategies First the sequential execution takes the set of individual simulation jobs in a sequence and process them all in a row Second the multi thread strategy instantiates a predefined number of threads and uses them to execute the jobs in parallel This technique allows to take advantage of multi core workstations Last the distributed strategy which is still under tests use the RMI technology to dis tribute the individual simulation jobs across a set of cooperating workstations 4 3 Measurement model Taking measures along a discrete event simulation see Figure 4 3 can be per formed in a number of ways The most simple way consists in considering that t1 t2 tN vl v2 vN Figure 2 Measurement Approach all events will change the state of the system so as it is worthwhile to take new measures for all the defined metrics Nevertheless this approach fails to consider that a measure on the state of a system is not always obtainable in const
22. le will be provided These files contain the description of the starting simulation 8 2 1 Drawing a network alu network printer The command alu network printer reads the configuration files build the model but do not start the simulation Instead it produces a files containing the graphical rendering of the network before the simulation starts The network is rendered by the GraphViz graph drawing application 8 2 2 Running a simulation mascsim_compute_simulation The command alu simulator runs the simulation whose the model is described in the configuration files The simulation runs until its termination condition is satisfied 8 2 3 Running a simulation alu scan available topology generators The command alu scan available topology generators performs a full scan of the available classes according to the entries listed in the classpath a prints a list of the classes that can be used as topology generators 8 3 Results Once the simulation finished DRMSIM writes a number of alu metric files in the current directory Each of these files correspond to a given metric whose the value changed along the simulation A alu metric file contains a sequence of datevalue entries which describe the timestamped evolution of the related metric 8 4 Simulation campains cA 27 References 1 ES 10 11 K Calvert M Doar A Nexion and E Zegura Modeling internet topology IEEE Communications Magazin
23. nges periodically and in some cases when a change is detected in the topology of a network Compared to link state protocols which require a router to inform all the nodes in a network of topology changes distance vector routing protocols have less computational complexity and mes sage overhead The link state protocol is performed by every switching node in the network i e nodes that are prepared to forward packets in the Internet these are called routers The basic concept of link state routing is that every node constructs a map of the connectivity of the network in the form of a graph showing which nodes are connected to which other nodes Each node then independently cal culates the best next hop from it to every possible destination in the network The collection of best next hops forms the node s routing table 5 2 2 AS level or router level routing In the specific context of the Internet routing protocols can be classified ac cording to their usage domain wether they are use to route packets within AS Autonomous System or between AS 6 Simulation models Before making a large scale simulation model there are many issues that should be addressed and the most important are e How to generate a realistic Internet topology e How to simulate policy configuration e What kind of metrics to gather to facilitate reasoning about both control plane and data plane behavior e How to simulate protocol procedures for a ve
24. ngine as well as its measurement system 8 1 2 Dipergrafs The simulation network implementation relies on the Dipergrafs 4 framework Dipergrafs is a graph manipulation toolkit which support directed hypergraphs and a large set of algorithms dedicated to the navigations query etc Although it can be presented as a general purpose graph library Dipergrafs was developed with the objective to be adequate to network simulation 8 1 3 GraphStream GraphStream 3 is a java library developped at the University of Le Havre that handles and display dynamic directed graphs in a very simple way We use it to see what happens in the simulated routing protocol all along the simulation Because of computational cost inherent to graph drawing Graphstream can be used only when the number of vertices is small two hundred nodes constitute a practical limit 8 1 4 CoLibA CoLibA is a framework for the integration of Java based applications into the UNIX command line environment In particular it provides command line pars ing input output facilities deployment enhanced access to functionalities of the operating system etc 26 8 1 5 Ploticus cA 8 2 Invocation DRMSIM is meant to be invoked from the command line using the command alu simulator The simulator expects to find in the current directory a set of files whose the name extension is alu Each configuration file contains a set of key valuel value2 valueN entries Examp
25. ogy generator takes care of generating GLP topologies inria dipergrafs topology GLPTopol The name of this class must be given to the topology generator parameter key for the simulator In addition the following configuration must be provided as it is used for initializing the topology generator glp numberOflInitialNodes glp numberOfEdgesPerStep glp beta glp stepProbability 24 7 6 How to implement a new routing protocol The definition of a new routing protocol can be achieved by deriving the class inria alu routing AbstractRoutingAlgorithm Basically doing this con sists in defining e the set of outgoing links that will be used to forward an incoming message e the type of header messages need to embed e the reactive behavior of the protocol when a network link breaks The new routing protocol class finally need to be specified for simulation using the configuration key routing protocol 7 7 Is there a way to import a new topology CAIDA Inet DRMSIM defines a number of special topology generator whose the aim is to enable the import of topologies generated using external tools like Inet or available as description files such as the CAIDA maps In the specific cas 7 8 How to run DRMSim The most obvious way to run DRMSIM is to use the mascsim compute simulation command It takes as the only parameter it accepts the name of the configura tion file which describes the simulation 7 8 1 One to one
26. olicies are not part of the simulation targets only the loc RIB was implemented It is an aggregation of many routes taking into consideration the most important attributes the path and its destination network while leaving the flexibility for adding new ones according to simulation needs However the implemented BGP routing model contains all the steps needed to establish maintain retrieve or to close a BGP session Thus the majority of the events that may occur in the latter are handled Then we tried to simplify this model by reducing the number of events and assuming that a BGP session has only two possible states It is either IDLE or ESTABLISHED this only has an impact on the establishment of the sessions But after there is exactly no difference between the two models In term of performance the initial phase in every simulation will end faster if we consider similar scenarios Eventhough this simplification seemed to be a better solution it was still not enough to perform a simulation on a Internet like graph The idea then was to find another way to simplify more the model without creating a lack in the information provided by the simulation Noticing that there was a redondacy between the information stored in the RIB and the one stored in the forwarding table we decided to forward the packets using the RIB and then remove the forwarding table this made our model simpler and decreased the time and the amount of memory needed by a sim
27. r starts yes yes yes BGP connection Local administrator stops yes yes yes BGP connection Indication that Connec yes no no tRetryTimer has just ex pired Indication that HoldTimer yes yes yes has just expired Indication that KeepAlive yes yes yes Timer has just expired Indication that the connec yes no no tion is successfully set up Confirmation of the initia yes no no tion of a connection Receiving a connection fail yes no no ure indication Receiving a valid OPEN yes no no messsage Receiving a BGP message yes no no with invalide header Detecting an error in the re yes no no ceived OPEN message Receiving an invalide NOTI yes no no FICATION message Indication that a yes no no KEEPALIVE message is received Indication that a valide UP yes yes yes DATE message is received Indication that a invalide yes yes yes UPDATE message is re ceived Other BGP simulators and their limits BGP simulators are not rare Several projects have developed some abstract model of the protocol to check its properties For instance SSF OS BGP4 implementation of the BGP proto col on SSFNet simulator was developped to study BGP stability behavior in different network topologies when confronted to various events The simula tor contains a lot of features from the protocol specification and even includes implementation specific aspects However the model did not incorporate user 18 traffics effects on
28. ry large routing topology while making efficient use of ressources such as memory e How to identify meaningful and realistic failure update scenarios that re flects reality 13 6 1 Network model The network model of DRMSIM relies on the concept of directed hypergrah 4 which adequately matches the structure of actual interconnection networks More precisely directed hyper graphs are able to represent the whole set of peculiarities of practical networks including bus topologies asymetric links redundant connections In simple terms a directed hypergraph can be seen as a digraph on P E it is a directed graph that connect sets of nodes Since they define no constraints on the content of the set of nodes all connection configurations are possible 6 1 1 On memory consumption and computational performance DRMSIM graph model makes use coupled incidence lists Every graph object resp node and edge is assigned an integer ID which is used to access the set of incident objects resp edges and nodes Four incidence lists allow to get for a given node the sets of incoming and outgoing edges and for a given edge the sets of source and destination nodes This technic allows fast graph navigation since jumping from node to node consists in two array indexing Also it is efficient in memory consumption if the sets of IDs are dense 6 2 Routing protocols DRMSIM routing model allows unicast and multicast routing It defines a ro
29. s routing forwards messages to nodes whose the ID is the clos est to messages destination ID This routing strategy requires a structured addressing of nodes It is used in Distributed HashTables DHTs random routing upon receiving a message that is not target to itself the router forwards the message using a randomly selected outgoing link or to a randomly selected relay It is a localized protocol round robin routing links are used in a sequential order Although this form routing cannot be used for multi hop routing it can be used for load balancing purposes These protocols can be used to simulate denial of service no routing do not forward any message Previous hop router is not informed of the denial of service back to previous hop router routing messages are not altered and sent back to router at the previous hop which will have to select another next hop relay to achieve relay This is the same as no routing except that the previous hop router gets informed of the denial of service by receiving the message it just forwarded 6 2 2 BGP Ar he BGP protocol is used to communicate information about networks defined by IP address blocks between entities known as autonomous systems AS so that one part of the Internet knows how to reach another part The exchange of network information is done by setting up a communication session between bordering autonomous systems For reliable delivery of information a TCP based
30. sing Sun s JDK version 1 6 or OpenJDK e Ubuntu 9 04 e Fedora 10 e CentOS 5 4 We still have not tested it under Mac OS X 2 2 Procedure In order to install DRMSIM on your computer you need to run the following command wget http www sop inria fr mascotte projets DCR releases install drmsim sh bash install drmsim sh This will query the official website for the last version of the code and down load it Next it will copy the corresponding files into you home directory as follows 2 3 Files installed The installer creates 3 directories in your HOME if they do not yet exist HOME drmsim contains the jar files of the last version drmsim drmsim jars drmsim jars java4unix 2010 01 20 11 58 52 jar drmsim jars dipergrafs 2010 01 20 11 58 52 jar drmsim jars toools 2010 01 04 16 38 41 jar drmsim jars graphstream jar lhttp gcc gnu org java 2OpenJDK is the effort by Sun Microsystems to release a fully buildable Java Development Kit based completely on free and open source code drmsim jars alusim brite 2010 01 04 16 38 41 jar drmsim jars mascsim 2010 01 20 11 58 52 jar drmsim jars up 2010 01 04 16 38 41 jar drmsim jars inria drmsim 2010 01 20 11 58 52 jar drmsim current version txt HOME lib contains a set of symbolic links to the jar in HOME drmsim lib java4unix 2010 01 20 11 58 52 jar lib dipergrafs 2010 01 20 11 58 52 jar lib toools 2010 01 04 16 38 41 jar lib graphstream jar lib alusim
31. t generate any new link asymmetric create a new link in the opposite direction asymetric link This doubles the number of links in the network 6 4 2 Randomized set DRMSIM implements the following randomized topology generators tree creates a random tree 6 4 3 Tier 1 Tier 2 Tier T3 Adon the Internet nodes can be classified according to their structural role in the network Three categories have been identified e Tl nodes which belong to the international operators of the internet like AT amp T Sprint etc These nodes form Wide Area networks e T2 nodes which usually belong to national organizations like university networks or public access provider PCCW Global France Tlcom Tiscali etc These nodes form the Metropolitan Area networks e T3 nodes corresponds to nodes in Local Area networks end users The topology of the network depends on the type of nodes it connect The network of Tl1s is the heart of the internet It is very dense T nodes are connected to T1 ones throught very fast links Generally a T2 is connected to two T1 nodes for redundancy purposes In the vast majority of the cases a T3 node is connected to one single T2 one Another generator that implements models trying to imitate the structure of the Internet is Tiers 2 21 6 4 4 Inet Inet 7 currently at version 3 0 is an Autonomous System AS level Internet topology generator Inet cannot generate network consisting of less than 3037 no
32. te AS path change This leads to the following observation Protocol convergence implies data plane convergence but the converse is not true Hence for a prefix m 0 lt DP lt PCm where DP and PC are data plane and protocol where convergence times for the prefix m respectively e average downtime is also proposed as ametric to capture the notion of potential disruption of reachability to a destination 6 4 Topology generators Most generators produce random networks 11 The problem of creating a topology can be expressed as creating or deleting a number of edges so as the resulting graphs will have the required properties This is how DRMSIM model topology generators they are a function f g C where g is a graph that may already feature some edges and C is a set of contrainsts DRMSIM implements the topologies described in the following 20 assuming that all of these generators are composeable in the sense that they can be invoked in a sequence on the same graph 6 4 1 Standard set DRMSIM implements a number of basic topology generator which allow to create networks whose the nodes are connected by directed chain iterate on the set of nodes and connect every node towards its predecessor directed grid create a sequence of directed chains and connect every node in a given directed chain with the node at the same index in the predecessor directed chain symmetric makes all links to be symetric This does no
33. tore its entries the more scalable the routing system would be Shortest path routing schemes are incompressible i e for all nodes in for all graphs their lower bound equal their upper bound i e O n log n bits are required to store their RT entries Note when designing a routing scheme there is a fundamental trade off between the stretch of a routing scheme and the size of the RT it produces e Communication cost the dynamic nature of the routing protocol such as those currently deployed over the Internet allows each router to be kept up to date wrt to non local topological changes resulting from topological failures addition withdraw of routes and ASs The latter information is exchanged between routers by means of routing information updates each router timely distributes to its own peers following specific selection cri teria the routing information received from other peers Communication cost is defined as the number of routing updated messages that needs to be exchanged between routers to converge after a topology change Re cently showed that the communication cost lower bound for scale free graphs is at best linear up to logarithmic factors The number of routing updates may change according to the advertisement technique time or event driven e Computational complexity routing updates processing results in recalcu lation of the RT entries and can lead to convergence delay and instabilities but also processing
34. try this one has two values The name of this file is given to the command mascsim compute simulation 7 2 Is it possible to define my own topology 7 3 deal with the output The output of a simulation job is a binary file whose the extension if result The content of such file can be displayed using the command mascsim result info Since a result file contains a number of metric each of them defining a list of measure that have been taken along the simulation it is possible to get plots out of it The command mascsim result plotter takes a result file as input and generate a plot in the form of a PostScript file for every metric found 7 4 How can I add a new metric The addition of a new metric can be done by deriving the class inria mascsim metrics Metric Basically doing this implies to define the domain of the metric define if a given value is an acceptable value for the metric and to implement the way a new value for the metric can be obtained on the simulated system In most of the cases the user will want to define a metric that is numeric In this case there is the need for defing the unit for this metric A list of of pre defined units are available as static fields of the inria mascsim metrics Unit class If none of these units suit then new metric then the user must sub class inria mascsim metrics Unit and implement a new unit that meets its particular needs 7 5 How can I generate a GLP graph A specific topol
35. tter router_topology 6 5 Dynamics Dynamics consider maintenance operations on the network infrastructure as well as router failures End user mobility is not looked at A 6 6 Traffic model A 6 7 Time model ADRMSm is built atop a general purpose discrete event simulation engine In discrete event simulation the operation of a system is represented as a chronological sequence of events Each event occurs at an instant in time and marks a change of state in the system Stewart Robinson 2004 Simulation The practice of model development and use Wiley The simulation must keep track of the current simulation time Time hops because events are instantaneous the clock skips to the next event start time as the simulation proceeds An event is described by the time at which it occurs and the code that will be used to simulate that event This code may schedule new event that will occur in the future or cancel existing events 6 8 Granularity DRMSIM performs packet level simulations The basic event that are modelled within DRMSIM are e emission of a packet from one node to another node e reception of a packet from one node Routing protocols may individually define other events for their own needs 7 Frequently Asked Questions FAQs 7 1 What is the input of the simulator The input of DRMSIM is an ASCII configuration file The syntax of this This file is the following 23 an entry one value another en
36. ulation 16 Connect fails start connectretry timer connection Active close connection intiate a connection at Connection succeeds Y connectretry 1 TCP connexion error receive Notification timer expires stop connectretry timer start connectretry timer send open message Opensent Y E TCP connection closed wait receive open check remote AS fail send notification process capabilities succeed Y send keepalive close connection Openconfirm wait TCP connexion closed TCP connexion error receive Notification TCP connection closed receive Keepalive keepalive timer expires start hold timer send keepalive reset keepalive timer Established examine table version no updates required BGP table changes wait receive Keepalive reset hold timer receive Update Sa succeed hold timer expires send Update process Update fail send Notification keepalive timer expires send Keepalive reset keepalive timer 17 The BGP events implemented in every package BGP Events bgp full bgp simple bgp simpler Local administrato
37. uting protocol as a function L R route r l m where m is the incoming message r is the router the message m came from l is the link the router r used to forward the message m L is a set of outgoing links where the message will be sent R isa set of relay nodes to which the message will be sent In practise all nodes that are destination nodes of links in L will receive the message but only those in R are allowed to relay it 6 2 1 Standard set AADRMSM features a set of routing protocol that were developed in the context of the modeling testing of the simulation engine source routing the source locally computes the path the message will follow and embeds this path into the message header Every fowarding node will hence know where to route the message This is a centralized protocol 14 QoS based routing is a polymorph routing protocol that choose the actual routing strategy according to QoS information stored in the header of the message blind broadcasting routing upon receiving a message that is not target to itself the router forwards the message on all outgoing links It is a local ized protocol shortest path routing upon receiving a message that is not target to itself the router forwards the message on the links that belong to the shortest paths to the destinations This routing protocol should be used as a reference for the evaluation of other protocols It relies on global network information closest addres
Download Pdf Manuals
Related Search