tutorial-wsc05

Informations

• Publié par: Apre
• Nombre de lectures: 11
• Langue: English

Extrait

Proceedings of the 2005 Winter Simulation Conference
M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, eds.
ADVANCED CONCEPTS IN LARGE-SCALE NETWORK SIMULATION
David M. Nicol Jason Liu
Michael Liljenstam Dept. of Math and Computer Sciences
Coordinated Science Laboratory Colorado School of Mines
University of Illinois, Urbana-Champaign Golden, CO 80401
Urbana, IL 61801
ABSTRACT tion to relieve in part the burden of abstracting and
modeling system behavior within a simulator. Emula-
This tutorial paper reviews existing concepts and fu- tion gives analysts a means of generating tra c by real
turedirectionsinselectedareasrelatedtosimulationof applications, have that tra c be managed (in part) by
large-scalenetworks. Itcoversspeci callytopicsintraf- actual networking hardware, but intersperse simulated
c modeling, simulation of routing, network emulation, elements in such a way that the actual elements are
and real-time simulation. unaware of interacting with a simulation. We review
current work and problems in that area.
1 INTRODUCTION Wehopethatthisexpositionofchallengingproblems
inlarge-scalenetworkservesasaresourceforthosewho
Use of communication networks is pervasive, and is in- by choice or by context need to learn about it.
creasing. The larger and more complex these networks
become, the harder it is to predict their behavior be-
2 TRAFFICMODELINGINLARGE-SCALEfore deployment. Analytic models often are useful for
IP NETWORKSa coarse level of analysis, but are limited in the prob-
lems they can tractably solve. Detailed discrete-event
simulations remain a valuable tool for understanding Models of network tra c drive virtually every conceiv-
and optimizing network designs. Commercial network able network simulation experiment. We want to use
simulation tools have wide-spread use, particularly in models that faithfully represent behavior of real traf-
government. Simulation of large-scale networks poses c, but may encounter problems when simulating large
some severe problems related to scale. In this paper we networks that carry IP tra c. The most straightfor-
consider work in three areas that address some of these ward approach is to represent IP packets individually.
problems. Within the simulation an event occurs when a packet
We rst consider the area of modeling tra c. The arrives at a new device, after having crossed a link.
problems of scale here are simply that there is so much It is straightforward to see the rami cations this has
tra c that it is computationally infeasible to simu- on the simulation workload. Suppose the average link
late it all at a ne degree of resolution. The work bandwidth in a model is b bits per second, that the av-
we describe addresses this through abstraction, which erage link utilization is p, that an IP packet uses 8000
(as we will see) brings its own new set of problems to bits, and that there are N links in the model. Then
be solved. Next we consider the simulation of rout- Nbu/8000isalowerboundonthenumberofevents
ing protocols, particularly the Border Gateway Proto- the simulation executes per simulation second. A large
col(BGP).Problemshereariseagainbecauseofscale— capacity network may have OC-48 links, which carry
simulating all routers at a high degree of resolution im- 2400Gbps. Assuming link utilization of 10%, the lower
poses a memory cost that grows in the square of the bound scales in N as 30N million events per second. A
size of the network. Here again one may use abstrac- highly tuned network simulator that runs on a work-
tionandapproximationtoalleviatesomeoftheseprob- station might be able to execute 1M events per second;
lems,butagainthesolutionscreateadditionalproblems we see then that a large-scale simulator that models
to be considered. Finally we discuss use of simulation IP packets directly may advance simulation time at a
in network emulation and real-time simulation. The rate that is considerably slower than real-time. This
context here is integration of virtual representation of limits the type of simulation experiment that might be
systems with physically actual systems. One motiva- performed.Nicol, Liljenstam, and Liu
One can address the issue by abstracting the traf- linear in time. The basic idea has been used for some
c, and consider it as a “ ow”, not unlike uid passing time, particularly using piece-wise constant ow rate
through a pipe. Flow formulations change the way we functions, e.g., see Kesidis et al. (1996), Nicol et al.
update the model, and may o er computational advan- (1999), Nicol and Yan (2004), Nicol et al. (2003). The
tageswhentherateofupdatesperunitsimulationtime DEFF allows one to cast ow state computations into
issigni cantlysmaller(Liuetal. 1999,Liuetal. 2001). the discrete domain, using familiar techniques. For ex-
Itiscommonlythecasethatwewouldliketouseanab- ample, if a tra c source injects ow into the network
stracted tra c model to describe so-called background at a linearly increasing rate until the rate exceeds the
tra c, and a detailed packet level model to describe network ingress point’s ability to absorb it, at time s
“foreground” tra c of particular interest. The back- one can compute the time t of saturation and schedule
ground tra c model paints a lower resolution picture a conditional event at t to deal with the model state
of what is happening in the network. Ideally it does so change induced by the saturation. Typically the e ect
inawaythatcanbeinterpretedbythesimulatortoad- of processing such an event is to alter the rate parame-
equately represent the impact that background tra c tersofsomeows. Ofcourse,ifthemodelstatechanges
has on the foreground tra c behavior. in such a way to invalidate the conditional event at t,
then the event can be canceled.Some ow models describe how the ow changes in
time with di erential equations, e.g., see Padhye et al. ThecomputationaladvantageoftheDEFFapproach
can be assessed by considering how many fewer events(1998), Bu and Towsley (2001), Liu et al. (2004), Yan
are needed to maintain the model state. If a discrete-and Gong (1998). The speci cs of the equations cap-
event uid formulation de nes events at time s andturehowprotocolslikeTCPa ecttheo eredload,and
t with no intervening events, and if over that epochhow things like RED (Random Early Detection queue
the average ow rate is packets per second, thenmanagement)andnetworkbandwidthlimitationsa ect
the DEFF formulation represents with one event statethe o ered load. These types of models express the be-
what the IP packet formulation takes (t s) events.havior in terms of coupled variables whose values are
Clearly the computational savings can be signi cant.determined by numerical integration of the equations.
Some formulations allow one to conceptually aggregate However, there can be complications which have no
all TCP tra c streams that have the same source and parallel in the IP packet formulation. The usual model
destination as a single mathematical entity, and de- ofowscompetingforagivenlink’sbandwidthassumes
scribe the interactions of those abstracted ows. Mod- that if there is congestion (e.g. more demand for band-
elslikethesehaveproventheirutilitymostimpressively width than capacity), then each ow is allocated band-
for stationary models of TCP, where the variables are widthinproportiontotherateofitsarrivaltothelink.
long-termaverages. SinceTCPcontrolactionsoccurat Thus if ow i arrives at rate , the available band-iPnthe time-scale of a packet’s round-trip time across the width is , and = (assuming n ows), thenii=1
thnetwork, “long-term” means considerably longer than when < the rate of the i ow through the link
that. For this reason (and others) these types of mod- is ( / ) . However, consider the rami cations. Sup-i
elsarenotwell-suitedforsimulationswherethemetrics pose that ow i is dened by a tra c source, and at
ofinterestintheforegroundtra caresensitivetovari- some time t an event is executed that changes . Sup-i
ability in the background tra c. Time-dependent dif- pose further that at time t the link into which ow i is
ferential equations can address this issue, but the main fed is congested. The change in causes a change ini
limitationwithexistingapproachesistheirfocusonde- , which causes a change in the value of every ow into
scribing how all tra c is shaped by a speci c protocol. thelink. Theseowratechangeshavetobepropagated
The state of the art does not yet support application in downstream; therefore the processing of one event may
a context where tra c is created and shaped by di er- induce many events.
ent sources and protocols. One can intermix tra c that is represented by IP
Models based on di erential equations inherently packets and tra c represented by ows, in the same
take a continuous view of the model state, and describe model(Nicol, Liljenstam, andLiu2003). Theissuesin-
how that state changes continuously. An alternative clude determining how each type of representation af-
ow formulation is inherently discrete event. In this fectstheother. Forexample,whenapacketisscheduled
Discrete Event Fluid Flow(DEFF)formulationa ow’s to cross a link, and there are ow representations also
rate at a point in the network is assumed to have a competing for that link, the simulation model must de-
mathematical form such that given the ow rate at terminewhatlatencytoascribetothepacket(latencyis
time s, in the absence of discrete events it is simple composed of queuing time, transit time of the r