Modeling and simulation of active networks

Modeling and Simulation of Active Networks

Dhananjai M.Rao and Philip A.Wilsey

Experimental Computing Laboratory

Dept.of ECECS,PO Box210030,Cincinnati,OH45221–0030.

dmadhava@https://www.wendangku.net/doc/c516811093.html,,philip.wilsey@https://www.wendangku.net/doc/c516811093.html,

Abstract

Active networking techniques embed computational ca-

pabilities into conventional networks thereby massively in-

creasing the complexity and customization of the compu-

tations that are performed with a network.In depth stud-

ies of these large and complex networks that are still in

their nascent stages cannot be effectively performed using

analytical methods.Hence,discrete event simulation tech-

niques are the only viable means to study and analyze active

networking architectures.Furthermore,customized and

?exible tools are required to for the analysis of active net-

works using simulation.This paper describes an integrated

environment for the modeling and parallel simulation of ac-

tive networks called Active Networks Simulation Environ-

ment(or ANSE).ANSE utilizes the Time Warp synchro-

nized kernel of WARPED(a general purpose discrete event

simulation kernel)to enable parallel simulation of active

network models.ANSE also includes complete support for

the modeling and simulation of active networks based on

PLAN(Packet Language for Active Networks).This paper

presents the issues involved in the design and development

of ANSE.The Application Programming Interface(API)of

ANSE is presented along with the issues involved in utiliz-

ing it to develop support for PLAN based active networks.

The paper also presents some results obtained from the sev-

eral experiments conducted to evaluate the effectiveness of

ANSE.Our studies indicate that ANSE provides an effec-

tive environment for modeling and simulation of large scale

active networks.

1Introduction

Techniques to effectively utilize the computational and

communication infrastructure of modern networks has lead

investigators to develop active networking architectures.In

an active network,the nodes constituting the network are

Figure1.Overview of ANSE

of WARPED,the simulation kernel utilized by ANSE.In Section3an overview of ANSE and its various compo-nents are presented.The uni?ed modeling front-end and ANSE’s API are also presented in this section.The issues involved in the design and development of support for mod-eling and simulation of active networks based on PLAN is presented in Section3.5.Section4presents results from several experiments conducted using ANSE.Finally,con-cluding remarks and pointers to future work are presented in Section5.

2Background

The parallel simulation capabilities of ANSE have been enabled by developing the framework around a general pur-pose discrete event simulation engine.Object oriented(OO) techniques have been employed to isolate the various mod-ules of ANSE from the underlying simulation kernel.This design not only provides a desired level of“separation of concerns”but also enables the use of different simulation kernels without modi?cation to the application modules. The current implementation of ANSE utilizes the WARPED simulation kernel[4]to enable sequential and parallel sim-ulation of active network models.WARPED is an Applica-tion Program Interface(API)for a general purpose discrete event simulation kernel with different implementations[4]. ANSE utilizes the sequential kernel and the Time Warp based parallel simulation kernel of WARPED.

The parallel simulation implementation in WARPED uses the Time Warp optimistic synchronization strategy[3].A Time Warp synchronized parallel simulation is organized as a set of asynchronously communicating logical processes (LPs).The LPs communicate between each other by ex-changing virtual time-stamped event messages[3].Each LP processes its events maintaining a local virtual time(LVT), changing its state,and generating new events without syn-chronization concerns to other LPs.Although each LP pro-cesses local events in their correct time-stamp order,events are not globally ordered.Causal violations may occur due to the optimistic nature of Time Warp.Causality violations are detected by a LP when it receives an event with time-stamps lower than its LVT(called a straggler event).On receiving a straggler,a rollback mechanism[3]is invoked to recover from the causality error.The rollback process recovers the LP’s state prior to the causal violation,cancel-ing the erroneous output events generated by sending out anti-messages,and re-processing the events in their correct causal order[3].Each LP maintains a list of state transi-tions along with lists of input and output events correspond-ing to each state to enable the recovery process.A periodic garbage collection technique based on Global Virtual Time (GVT)[3]is used to prune the queues by discarding history items that are no longer needed.

The WARPED kernel presents an interface to build logi-cal processes based on Jefferson’s original de?nition[3]of Time Warp[4].The kernel provides an API to build dif-ferent LPs with unique de?nitions of state[4].The basic functionality for sending and receiving events between LPs using a message passing system is supported by the kernel. In WARPED,LPs are placed into groups called“clusters”. LPs on the same cluster communicate with each other with-out the intervention of the message passing system,which is faster than communication through the message system[4]. Although LPs are grouped together into clusters they are not coerced into synchronizing with each other.Control is ex-changed between the application and the simulation kernel through cooperative use of function calls.

3The Active Networks Simulation Environ-ment(ANSE)

ANSE was developed to ease modeling and simulation of active networks.An overview of ANSE is presented in

Figure1.As shown in Figure1,the primary input is the topology of the network model to be simulated.The syntax

and semantics of the input topology is de?ned by the Topol-ogy Speci?cation Language(TSL).TSL provides simple, yet robust,hierarchical modeling techniques for represent-

ing a network as a set of interconnected components/nodes. The components used in the TSL description are developed

using ANSE’s API.As illustrated in Figure1,the input net-work model is parsed into an object-oriented in-memory in-termediate format(TSL-IF).An elaboration module is used

to elaborate or“?atten”a hierarchical network model.Elab-oration is performed to ease further processing of the net-work model.TSL-IF is used to represent the elaborated

network model.As shown in Figure1,a back-end code-generator utilizes the elaborated network model to gener-

ate ANSE API compliant(C++)code.The generated code is compiled and linked with necessary libraries such as the WARPED library,ANSE library,PLAN library,and other user-de?ned libraries(as the case maybe)to obtain the?nal executable.The?nal executable performs the actual simu-lation when it is run.A detailed description of the various

modules constituting ANSE is presented in the following subsections.

3.1Topology Speci?cation Language(TSL)

The primary input to ANSE(as shown in Figure1)is the topology of the network to be simulated is provided to the environment in Topology Speci?cation Language(TSL)[5] syntax.The Backus Normal Form(BNF)of TSL gram-mar is shown in Figure2.As speci?ed by the grammar,a TSL speci?cation consists of a set of interconnected topol-ogy speci?cations.Each topology speci?cation consists of three main sections,namely;(i)the object de?nition section that contains the details of the modules that need to be used to simulate the topology;(ii)the object instantiation section that speci?es the various nodes constituting the topology; and(iii)the netlist section that de?nes the interconnectivity between the various instantiated nodes.Figure3.1presents a network model along with the corresponding TSL descrip-tion.An optional label may be associated with each topol-ogy.The label may be used as an object de?nition in sub-sequent topology speci?cations to nest a topology within another.In other words,the labels,when used to instantiate an object,result in the complete topology associated with the label to be embedded within the instantiating topology. Figure3.1presents the TSL source code to model a larger network using hierarchical constructs.As illustrated by the ?gure,the model of the network is speci?ed by intercon-necting three instances of the network model shown in https://www.wendangku.net/doc/c516811093.html,ing this technique,a simple sub-network consist-ing of merely ten nodes can be recursively used to construct a network with six levels of hierarchy to specify a network design list tsl topology

design

list::=include include list include name”;

?le identi?er.identi?er

tsl topology topology

topology tsl label tsl network tsl de?nition

instantiation list

de?nition de?nition

de?nition object section

object name:url optional

name::=identi?er

url::=host number.factory

optional;

parameter::=“string”

identi?er.factory

port

instantiation instantiation

instantiation object section

object

instance:object parameter

instance:object parameter

instance:label

object

list list list net section

net instance:instance

list:=object object list identi?er::=start char

start

char::=[a-z,A-Z,0-9,

char char string

string

is also implemented in C++.The IF consists of a set of cross-referenced classes,each class representing a particu-lar grammar entity.The IF is composed by?lling in the ref-erences in the various C++classes generated by the parser with appropriate values.Since composition is achieved via base class references,each node can refer to another node or even a sub-network.This provides an ef?cient data structure for representing and analyzing hierarchical net-works[7,6].

3.2.1Static Elaborator

Hierarchical constructs provide convenient techniques to speci?c large networks by reusing the speci?cation for smaller sub-networks[7,6].However,the hierarchical con-structs have to be elaborated or“?attened”prior to simula-tion[7,6].Elaboration is the process in which each hierar-chical level is broken down to its constituting components. The basic steps involved in elaborating a hierarchical spec-i?cation are shown in Figure4.As illustrated in the?gure, the elaborator starts with an user-speci?ed topology and re-cursively traverses the various sub-topologies in the model and creates new instances of the sub-topologies and the ob-jects.Elaboration of sub-topologies is done before they are imploded into the enclosing topology.Imploding hierar-chies involves inclusion of all necessary object de?nitions, object instantiations,and corresponding data structures. Elaboration may be done statically or at runtime.Static elaboration occurs prior to code-generation while runtime elaboration occurs just before simulation commences,when

(2)Hierarchal network

Figure3.Example Network models and TSL step1:Initialize elaborator

1.Initialize new symbol table and IF

2.Search input IF and locate node corresponding to user

speci?ed top level topology

3.Call elaboration(step2)with new topology

step2:Elaboration subroutine(parameter topology) 1.Process the list of netlists speci?ed in the topology.

If the node is an object instantiation perform step3.If the node is a topology label perform step4.

step3:Elaborate object instantiation

1.Create new instance of the object instantiation with

mangled labels.

2.Create new object de?nition for the new instance with

mangled labels and add to new symbol table,if neces-sary.

3.Add new object instantiation to the new topology and

update netlist entry.

step4:Elaborate sub-topology

1.Instantiate temporary symbol table and IF

2.Recursively call elaboration with the sub-topology

3.Implode new IF to the new topology

Figure4.Phases in elaborating a TSL design

the generated code is executed.In ANSE,static elaboration is performed with the TSL-IF generated by the parser and the elaborated topology is also represented in TSL-IF(as shown in Figure1).

3.3Code Generator

As shown in Figure1,the back-end code-generator uti-lizes the elaborated TSL-IF to generate a simulatable model from the given TSL description.The generated code in in C++in concordance with all the other components of ANSE.The OO nature of TSL-IF has been exploited in the development of the code-generator.The generated code is compliant with the API of ANSE.A model developer can directly develop the network model(compliant with ANSE’s API)and bypass these stages.However,the com-plexity involved in model development would be consider-ably higher.The back-end code-generator can be replaced with a different code-generator in order to re-target the gen-erated code for different frameworks.

3.4ANSE API and Library

ANSE presents an interface to the application developer for modeling a network as set of communicating logical processes(LPs).The LPs are modeled as entities which send and receive events to and from each other,and act

on these events by applying them to their internal state. Figure5shows the Universal Markup Language(UML) diagram for the core classes that constitute the API.As illustrated in the?gure,the NetworkNode class forms the parent class for all the networking components in the system.The ActiveNode and PLANNode are derived from this class.The NetworkNode class is used to model conventional networking components while the ActiveN-ode is used to model active components.The Networ-kNode also provides methods for accessing routing tables and supports primitive domain name services(DNS).The state(NetworkNodeState and ActiveNodeState) and packet(Packet and ActivePacket)classes corre-sponding to the LP hierarchy are also shown in Figure5. The state classes are used to encapsulate the state informa-tion associated with each node/component.The state in-formation is used by WARPED(the underlying simulation kernel)to enable rollbacks[3]and recover from causal vio-lations that could occur in Time Warp based simulations[4]. The Packet(and derived)class is used for all communica-tions between the nodes constituting a network model.The packets in turn represent the discrete events in the simula-tion.The API has been developed in C++and the object oriented features of the language have been exploited to en-sure it is simple and yet robust.The API plays a critical role in insulating the model from the underlying simulation kernel.The interface has been carefully designed to provide suf?cient?exibility to the application developer and enable optimal system performance.Further details on the API are available in the literature[7].

3.5PLAN library

As illustrated in Figure5,ANSE’s API has been used to develop a library for modeling and simulating active net-works based on PLAN,a Packet Language for Active Net-works[2].PLAN is a simple,functional programming lan-guage based on a subset of ML with some added primitives to express remote evaluation[2].In a PLAN based active network,the active packets can contain a PLAN program

Figure5.Core classes of ANSE API that can be used to customize the active network to provide

different networking services.The PLAN library provides a PLANNode that is capable of parsing and interpreting

PLAN packets.A PLAN parser,constructed using PCCTS,

is used to parse incoming PLAN packets into an OO inter-mediate format(IF).The IF is fed to a PLAN interpreter

that executes the program contained in the packet.The in-terpreter supports all PLAN constructs including recursive

function calls,exceptions,and forwarding of any PLAN

packets generated during interpretation.The PLAN library also contains a PacketInjector component that can be

used to inject PLAN packets into the simulated network.

The PacketInjector can be used to inject a PLAN pro-gram from a given?le or obtain the PLAN program interac-

tively from the user.The PacketInjector can be driven using a variety of traf?c generators based on random num-

ber generators available as a part of the ANSE library.The

random number generators generate traf?c based on mathe-matical distributions(such as normal or constant delay dis-

tributions,Poisson distribution,and Pareto distributions).

The library also contained components for modeling differ-ent types of communication links with different parameters

(such as transmission delay and packet loss ratio).

The runtime structure of a typical PLAN based ac-tive network is shown in Figure6.As illustrated in the

?gure,a single instance of the PLAN parser and inter-

preter are shared by the different PLANNodes.The de-sign helps to minimize the overall resource requirements

(memory in particular)of the simulations;thereby enabling

simulation of larger networks using available hardware re-sources.However,in parallel simulations,a single instance

of the PLAN parser and interpreter are used in each clus-ter.This approach is a tradeoff between the overall mem-

ory requirements of the simulation versus simulation over-

heads(such as communication and concurrency).It must be noted that concurrent demands/usage of the parser and in-

terpreter never arises because execution of events on a clus-

ter proceeds in a serial order.In other words,although the WARPED clusters and the LPs operate asynchronously with each other,the events on a given cluster are executed seri-ally.Hence,in a given cluster,only one event can be active

at a time and the PLAN parser and interpreter are assigned

(or reserved)for use by that event.Since parsing of PLAN packets their interpretation are two distinct and indepen-dent stages,they can be cascaded or pipelined(i.e.,when a previous packet is being interpreted the next packet can be parsed)to improve performance.Such a design would be of considerable bene?t in shared memory multiprocessor (SMP)platforms.Any dependencies or inconsistencies that could arise due to asynchronous pipelining can be resolved by directly utilizing the optimistic simulation infrastructure. In other words,if inconsistencies arise then the simulation would get rolledback and the events would get reprocessed

Figure6.Runtime structure

Model

PLAN Others

Injectors

1959 Model219127

226245 Model455375

3100991 Table1.Characteristics of the models

in the correct causal order.However,such a design was not adopted in the current implementation because other simu-lation techniques(such as sequential simulation and conser-vative simulations)may not be capable of supporting such a design.

As shown in Figure6,the routing tables and DNS tables (built and maintained by NetworkNode s)are also shared between the various nodes constituting the simulation.This design also helps to reduce the overall memory require-ments of the simulations.As explained earlier,concurrent access to these data structures does not arise.Hence,com-plex locking mechanisms/semaphores are not necessary to ensure their consistency/coherence.The routing and DNS tables are replicated at each cluster(in a parallel simulation) to minimize simulation overheads.The runtime modules of ANSE(present in the ANSE library)assist in construct-ing the tables by providing necessary information about the network model being simulated.Although,the LPs are par-titioned onto different clusters,the necessary information (such as name of the nodes along with the interconnectiv-ity data)related to all the nodes are extracted and?lled into the tables.In the current implementation of ANSE, the LPs are equally divided amongst the clusters used in a simulation i.e.,each cluster has(almost)an equal num-ber of LPs.ANSE’s API also includes interfaces for im-plementing other partitioning algorithms.It must be noted that,partitioning,assignment of nodes to clusters,and par-allel simulation is completely transparent to the application modules.The applications(and generated code)does not change based on the number of clusters or the underlying synchronization technique used in the simulations.

4Experiments

The experiments conducted to evaluate the performance of ANSE and the results obtained from the experiments are presented in this section.Table1tabulates the char-acteristics of the models used to conduct the experiments. The network models were described in TSL and utilized the various components available in the PLAN and ANSE li-braries.The network models consisted of a set of intercon-nected PLAN nodes.The larger models such as Model3, Model4,Model5were constructed using the hierarchi-cal modeling constructs supported by TSL.The number of PLAN nodes in each model is shown in Table1.The other components of the model such as traf?c generators, packet injectors,and links are grouped together and tabu-lated in Table1(under the“Others”column).A route trac-ing PLAN program[2]was run on the simulated network model.The route tracing PLAN packets hop from one node to another(as they get interpreted by each PLAN node in the

simulated network)and at each node they generate two new PLAN packets.One packet carries the information about the current hop back to the source node (i.e.,the node at which the route tracing for that particular packet began).The other packet proceeds forward to trace the route un-til the destination node is reached.The destination node on each packet was randomly chosen from the set of nodes par-ticipating in the simulation.The PacketInjector (de-scribed earlier)was used to inject the PLAN packets into the simulated network.Each PacketInjector was pro-grammed to generate 500requests (i.e.,trace route to 500randomly chosen PLAN nodes).The links interconnecting the nodes were con?gured (through suitable parameters in the TSL description)to have zero losses i.e.,no packets get lost (in other words,a basic TCP/IP type of connectivity was assumed).

The graphs in Figure 7present the time taken for per-forming the different phases of model generation such as parsing,elaboration,code-generation,and compiling the generated code.The experiments were conducted on a Linux workstation consisting of dual Pentium II (300Mhz)processors with 128MB of main memory.The timings were obtained using the standard Unix time command.The times plotted in the graphs are the average values com-puted from 10simulation runs.As illustrated by the graphs shown in Figure 7the time overall time for generating a net-work model scales almost linearly with respect to the total number of objects (or LPs)constituting a network model.This data suggests illustrates the scalability of the modeling and simulation infrastructure supported by ANSE.It also indicates that ANSE will be capable of generating large network models in reasonable time frames.

The parallel simulation experiments were conducted us-ing a network of workstations.Each workstation consisting of two Pentium II (300MHz)processors in shared mem-ory con?guration.Each workstation had 128MB of main

0.001

0.01

0.1

1

10

T i m e (s e c )

Number Of Objects

Figure 7.Time for model generation

memory (RAM)and were running Linux.The workstations were interconnected by fast Ethernet.The parallel simula-tions were conducted using 1to 16WARPED clusters.The results obtained from the various experiments are presented by the graphs in Figure 8.The timing information for the various simulations were obtained using the standard Unix time command.The simulation times plotted in the graphs are the average values computed from 10simulation runs.The timings obtained from the simulations conducted using the sequential kernel available with WARPED are also plot-ted in the graphs.The sequential simulator was con?gured for its most optimal con?guration (including using a splay tree data structure for maintaining event lists).

As illustrated by the graphs in Figure 8,parallel simu-lation provides considerable improvements in performance for even medium sized network models.For example,par-allel simulation using 16processors provides an order of magnitude improvement in performance when compared to a sequential simulation.The primary factor for the pro-nounced improvement in performance is the high event granularity of the active packets which need to be parsed and interpreted.As the number of processors used in the simulation are increased,the computational load gets dis-tributed across the parallel processors which in turn reduces the overall simulation time.However,as illustrated by Fig-ure 8(a),for small models,the performance deteriorates as the number of processors are increased.This is because the smaller models do not have suf?cient concurrency and load to utilize all the parallel processors.Hence,the overheads of parallel simulations out weigh the gains accrued by increas-ing the number of processors.The results also demonstrate the scalability of the parallel simulation framework.The ex-periments highlight that considerable improvements in per-formance of the simulations can be achieved by employing parallel simulation techniques.The experiments also illus-trate the overall effectiveness of ANSE for modeling and simulation of active networks.

5Conclusions

The issues involved in the design and implementation of an Active Networks Simulation Environment (ANSE)were presented in this paper.The experiences gained during the development of ANSE also highlight a number of issues on different aspects of active network modeling and simula-tion.Our experiences indicate that it is better to have to have a simple,yet ?exible,language such as TSL,for modeling network topologies.It is useful to have a clear delineation between the languages for developing the software mod-ules for networking components and network modeling lan-guages.For example,TSL and ANSE can also be used to enable simulation of conventional networks.The ?exibility and general purpose design of ANSE can be utilized to en-

T i m e (s e c )

Number Of Processors

(a)Small Models 0

500100015002000250030003500400045000246

810

121416

T i m e (s e c )

Number Of Processors

Model4:Sequential Model4:Parallel Model5:Sequential Model5:Parallel

(b)Large Models

Figure https://www.wendangku.net/doc/c516811093.html,parison between sequential and parallel simulation times

able inter-operability between different type of models and even different simulators.An experimental evaluation of ANSE was presented in the paper.The experiments demon-strate that considerable improvements in performance of the active network simulations can be achieved by employing parallel simulation techniques.The experiments in con-junction with the diverse set of issues addressed by ANSE highlight the effectiveness of the active networks simulation environment provided by ANSE.

References

[1]D AVID L.T ENNENHOUSE ,J.M.S.,S INCOSKIE ,

W.D.,W ETHERALL ,D.J.,AND M INDEN ,G.J.A survey of active network research.IEEE Communica-tions Magazine 35,1(Jan.1997),80–86.

[2]H ICKS ,M.,K AKKAR ,P.,M OORE ,J.T.,G UNTHER ,

C.A.,AND N ETTLES ,S.PLAN:A Packet Lan-guage for Active Networks.In In Proceedings of the Third ACM International Conference on Functional Programming Languages (SIGPLAN’98)(May 1998),pp.86–93.

[3]J EFFERSON , D.Virtual time.ACM Transactions

on Programming Languages and Systems 7,3(July 1985),405–425.

[4]R ADHAKRISHNAN ,R.,M ARTIN ,D.E.,C HETLUR ,

M.,R AO ,D.M.,AND W ILSEY ,P.A.An Object-Oriented Time Warp Simulation Kernel.In Proceed-ings of the International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE’98),D.Caromel,R.R.Oldehoeft,and M.Tholburn,Eds.,vol.LNCS 1505.Springer-Verlag,Dec.1998,pp.13–23.

[5]R AO ,D.M.,R ADHAKRISHNAN ,R.,AND W ILSEY ,

P.A.FWNS:A Framework for Web-based Net-

work Simulation.In 1999International Conference On Web-Based Modelling &Simulation (WebSim’99)(Jan.1999),A.G.Bruzzone,A.Uhrmacher,and E.H.Page,Eds.,vol.31,Society for Computer Simulation,pp.9–14.

[6]

R AO ,D.M.,AND W ILSEY ,P.A.An object-oriented framework for parallel simulation of ultra-large com-munication networks.In Proceedings of the the Third International Symposium on Computi ng in Object-Oriented Parallel Environments (Nov.1999).

[7]

R AO ,D.M.,AND W ILSEY ,P.A.Simulation of ultra-large communication networks.In Proceedings of the Seventh International Symposium on Modeling,Anal-ysis and Simulation of Computer and Telecommunica-tion Systems (Oct.1999),pp.112–119.

[8]

R ILEY ,G.F.,F UJIMOTO ,R.M.,AND A MMAR ,M.H.A generic framework for parallelization of net-work simulations.In Proceedings of the Seventh Inter-national Symposium on Modeling,Analysis and Sim-ulation of Computer and Telecommunication Systems (Oct.1999),pp.128–135.

[9]

R OBINSON ,S.Simulation model ver?ciation and val-idation:Increasing the users’con?dence.In Proceed-ings of the 1997Winter Simulation Conference (Dec.1997).

[10]

S WAMINATHAN ,K.,R ADHAKRISHNAN ,R.,W ILSEY ,P. A.,AND A LEXANDER ,https://www.wendangku.net/doc/c516811093.html,rge scale active networks simulation.In International Workshop on Applied Parallel Computing (PARA98),B.Kagstrom,J.Dongarra,E.Elmroth,and J.Was-niewski,Eds.,vol.LNCS 1541.Springer-Verlag,June 1998,pp.537–542.

[11]

Z EGURA ,E.,C ALVERT ,K.,AND B HATTACHARJEE ,S.How to model an internetwork.In Proceedings of IEEE INFOCOM (Apr.1996),pp.594–602.