An Adaptive Time Window Algorithm for Large Scale Network Emulation

Simple item page
dc.contributor.authorKodukula, Surya Ravikiranen
dc.contributor.committeechairVaradarajan, Srinidhien
dc.contributor.committeememberNance, Richard E.en
dc.contributor.committeememberArthur, James D.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T20:31:34Zen
dc.date.adate2002-02-07en
dc.date.available2014-03-14T20:31:34Zen
dc.date.issued2002-01-25en
dc.date.rdate2003-02-07en
dc.date.sdate2002-02-07en
dc.description.abstractWith the continuing growth of the Internet and network protocols, there is a need for Protocol Development Environments. Simulation environments like ns and OPNET require protocol code to be rewritten in a discrete event model. Direct Code Execution Environments (DCEE) solve the Verification and Validation problems by supporting the execution of unmodified protocol code in a controlled environment. Open Network Emulator (ONE) is a system supporting Direct Code Execution in a parallel environment - allowing unmodified protocol code to run on top of a parallel simulation layer, capable of simulating complex network topologies. Traditional approaches to the problem of Parallel Discrete Event Simulation (PDES) broadly fall into two categories. Conservative approaches allow processing of events only after it has been asserted that the event handling would not result in a causality error. Optimistic approaches allow for causality errors and support means of restoring state — i.e., rollback. All standard approaches to the problem of PDES are either flawed by their assumption of existing event patterns in the system or cannot be applied to ONE due to their restricted analysis on simplified models like queues and Petri-nets. The Adaptive Time Window algorithm is a bounded optimistic parallel simulation algorithm with the capability to change the degree of optimism with changes in the degree of causality in the network. The optimism at any instant is bounded by the amount of virtual time called the time window. The algorithm assumes efficient rollback capabilities supported by the â Weaves' framework. The algorithm is reactive and responds to changes in the degree of causality in the system by adjusting the length of its time window. With sufficient history gathered the algorithm adjusts to the increasing causality in the system with a small time window (conservative approach) and increases to a higher value (optimistic approach) during idle periods. The problem of splitting the entire simulation run into time windows of arbitrary length, whereby the total number of rollbacks in the system is minimal, is NP-complete. The Adaptive Time Window algorithm is compared against offline greedy approaches to the NP-complete problem called Oracle Computations. The total number of rollbacks in the system and the total execution time for the Adaptive Time Window algorithm were comparable to the ones for Oracle Computations.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-02072002-141811en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-02072002-141811/en
dc.identifier.urihttp://hdl.handle.net/10919/31160en
dc.publisherVirginia Techen
dc.relation.haspartsurya_etd.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectParallel Simulationen
dc.subjectTime Windowen
dc.subjectEmulationen
dc.subjectOptimistic Algorithmen
dc.titleAn Adaptive Time Window Algorithm for Large Scale Network Emulationen
dc.typeThesisen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
surya_etd.pdf
Size:
617.39 KB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses