|
|||||||||||||||||||||||||||||||||
 |
Abstract:
"Distributed simulation of computer networks optimization tasks on compute cluster"
Author: Alexey Astakhov |
||
Urgency of workNetwork is a complex mix of applications, communication protocols, links, traffic flows and routing algorithms. Designing of a network is enough a challenging task, requiring developers to compare performance expectations in a network with design time costs and memory sizes. [1] Efficiency of network construction and corporate information systems became extremely actual problem, especial in conditions of insufficient financing information technologies at the enterprises. Therefore, it is expedient to create not a real physical network, but its model, for reasons given it will be already possible to judge performance inside a network and to make a decision on, whether it is necessary to develop the given model or not. Opportunities of physical modeling are enough limited. It allows to solve separate problems in assignment of a few combinations of researched system parameters. Really, at natural modeling of computer network it is practically impossible to check up its work for variants with use of various types of communication devices - routers, switchboards, etc. Check in practice about ten different types of routers is related not only to the great efforts and time expenses, but also to considerable material costs. But even when not types of devices and not operational systems are changes in network optimization, but only their parameters, carrying out of experiments in real-time for huge amount of every possible combinations of these parameters is practically impossible for foreseeable time. Even simple change of the maximal size of a package in any report demands reconfiguration operational system in hundreds computers of a network that demands from network administrator of carrying out of very big work. Therefore, in many cases there is preferable to use math modeling in network optimization. The math model represents set of ratios (formulas, equations, inequalities, logic conditions), determining changing process of system condition depending on its parameters, entrance signals, entry conditions and time. Special class of math models are imitating models. Such models represent the computer program which step by step reproduces the events occuring in real system. With reference to computer networks their imitating models reproduce processes of message generation by applications, splitting of messages into packages and frames of the certain protocols, the delays are related to processing of messages, packages and frames inside operational system, process of access reception by a computer to the shared network environment, handling process of acting packages by a router, etc. At imitating simulation of network it’s not required to get the expensive equipment – its work is simulated by the programs precisely reproducing all basic features and parameters of such equipment. Advantage of imitating models is the opportunity of substitution of event changing process in researched real-time system on the accelerated event changing process in rate of program work. In result it’s possible in few minutes to reproduce work of several days that enables to estimate work of a network in a wide range of varied parameters. Result of imitating model work is statistical data of the most important network characteristics, which are collected during supervision over proceeding events: response times, operating ratios of channels and nodes, probability of packet losses, etc. [2] On the other hand, simulation of large-scale networks with a plenty of nodes demands a lot of time. Process of simulation it’s possible to parallelize using compute cluster. In this case, on each cluster node will be carried out a construction of some model part of computer network, and time of performance of simulation will considerably be reduced. Therefore the distributed simulation on clusters recently has got a big popularity and is rather actual problem in modern information researches.  Figure 1 – Typical topology of cluster network Overview of existing researchesThere are special focused on network simulation program systems in which process of model creation is simplified. Such program systems generate model of a network on the basis of the initial data on its topology and used protocols about stream rates of inquiries between computers of a network, extent of communication lines, about types of the used equipment and applications. Program systems of modeling can be highly specialized and universal, allowing to simulate networks of the most various types. Quality of modeling results substantially depends on accuracy of the initial data on a network, transferred to system of imitating simulation. In the work these systems use the information about spatial arrangement of a network, number of nodes, configurations of connections, rates of the data transmission, used protocols and type of the equipment, and also about applications are carried out in a network. Usually imitating model is construction not from beginning. There are exist imitating models of basic network elements: most widespread types of routers, communication channels, methods of access, protocols, etc. These models of separate network elements are created on the basis of the various data: results of test experiments of real devices, the analysis of principles of their work, analytical ratios. In result the library of typical network elements is created, which can be adjusted with the help of parameters beforehand stipulated in models. Systems of imitating modeling usually include a set of tools for preparation of the initial data on a researched network - preliminary data processing about topology of a network and the measured traffic. These tools can be useful, if the modelled network represents a variant of an existing network and there is an opportunity to carry out measurement of traffic and other parameters necessary for simulation. In addition system is supplied with tools for statistical processing the received results of modeling. Software of modeling can be classified on educational, commercial and specialized. [1] Among educational analytical tools of modeling it is possible to mark out: DEsign tool LITE (Delite) is a wide area network design tool, supporting various types of design algorithms; Cappuccino is a simulator of a noncommercial web-project for the limited number of the applications, allowing to calculate various parameters of a network. Commercial tools of modeling: XNetMod is a tool for modeling the local networksthat allows to analyse the performance of configuration before implementing it; TND-Tool (Topologycal Network Design Tool) is used to find out effective solution to the network topology design problem; NetRule is the simulator combining the best features of the mathematical analysis and simulation tool, supports a plenty of nodes in a network; XNP (Extensible Network Planner) is a network design tool for both extensible and conventional networks, supports a plenty of various algorithms. One of popular network simulators is ns2. The simulator is completely written in language C++ and distributed with an open code. OTcl is used as the managing interface language. It’s possible to define and operate model both through interface OTcl and with use language C++. Network WorkBench is a discrete event network simulator developed for academic investigation of Internet protocol. Netsim is a simulator used for research of local networks. MaRS (Maryland Routing simulator) is a discrete event simulator providing a flexible platform for the evaluation and comparison of network routing algorithms. PDNS (Parallel/Distributed ns) is the expanded version of ns simulator for the distributed simulation. OPNET (Optimised Network Engineering tool), COMNET III, REAL (Realistic And Large), Ted (Telecommunication Description Language), USSF (Ultra-Large Simulation Framework) are commercial network modeling tools. The specialized tools are ATN-TN (ATM Traffic and Network simulator) which can characterize behaviour of a network, and GloMoSim (Global Mobile System simulator) is a scalable simulation environment for wireless network systems. In the master’s work I use PRIME (Parallel Real-time Immersive Modeling Environment). PRIME is a research project, its main goal is research of the fundamental technologies, which allow large-scale network real-time simulation and development of the network real-time simulation environment. [3] The basic program tool for researches is simulator PRIME mainly written in C++, and runs in Unix environment. It needs for its work Linux, Mac OS or cygwin. The simulator consist of two component: PRIME SSF and PRIME SSFNet. PRIME SSF is a mechanism of simulation which is designed for run large-scale models on parallel machines (including sequential simulation). SSF is a scaled environment of modeling, it’s API standard for model development. PRIME SSF implements SSF specification. [4] PRIME SSFNet is the simulator developed on top of PRIME SSF that deals with simulations of the infrastructure network such as Internet. PRIME SSFNet implements necessary network components: routers, links, protocols, etc. PRIME SSF is developed based on our previous DaSSF and iSSF implementations which provide a highly efficient simulation of large-scale systems. Deciding tasksOne of the main tasks in mine master’s work is network simulation on compute cluster. For this purpose it is necessary: 1) to analyze advanced concepts and approaches in large-scale simulation; 2) to find a network simulator which allows to model computer networks of the big dimension, and also supports parallel simulation on the distributed memory; 3) to organize run of simulation system on Microsoft Windows Compute Cluster Server 2003. PRIME has been chosen as a simulation system, which allows to create models using DML descriptions (Domain Modeling Language) or using C++. With the program superstructure PRIME SSFNet models of computer networks are created, using standard classes of SSF API. So it performs simulation on cluster where communication between nodes is organized with message passing by protocol MPI (Message Passing Interface). [2]  Figure 2 - Creation of network model using the DML description (Animation: number of frames - 16, repeat count - 10, duration - [20, 80] ms) It is necessary to construct model for network optimization so that the network worked as the most effective. For this purpose it is necessary to solve below-mentioned problems. 1) To state criteria of the network performance. Often such criteria are performance and reliability for which in turn it is required to choose concrete parameters of an estimation, for example, response time and availability. 2) To define set of varied network parameters, it is expressly or by implication influences on criteria of efficiency. These parameters really should be varied, i.e. it’s necessary to be convinced that they can be changed in some limits. So, if the size of a package of any protocol in concrete operational system is established automatically and cannot be changed by adjustment this parameter in this case is not varied though in other operational system it can be changed at the request of the administrator, so it’s varied. Other example is a throughput of the internal router trunk - it can be considered as a parameter of optimization only if the opportunity of router replacement in a network is supposed. 3) To determine a threshold of sensitivity values of efficiency criterion. So, network performance can be estimated by logic values "Works"/"Does not work", and then optimization is reduced to diagnostics of malfunctions and reduction of a network in any efficient condition. Other extreme case is fine adjustment} of a network at which parameters of a working network (for example, the frame size or size of a window of the unconfirmed packages) can vary for increasing performance (for example, average response time) even for some percent. Generally network optimization is a some intermediate variant at which it’s required to choose such values of network parameters that parameters of its efficiency have essentially improved, for example, users received answers to the inquiries to a database server not for 10 seconds, and for 3 seconds, and transfer of a file on the remote computer was carried out not for 2 minutes, and for 30 seconds. [2] Thus there is a task of the analysis (definition of system value criterion for the given combination of network parameters) and synthesis (a choice of varied parameters values which the parameter of efficiency has the best value). Theoretical analysisImitating simulation is the method allowing to build the models, which describe processes passing in reality. This model can be played in time for one test and some set of tests. Thus results will be defined by casual character of processes. On these data it is possible to receive enough steady statistics. Imitating simulation is a method of the research that supposed that the investigated system is replaced with the simulator and then experiments are carried out whit it to extract information on this system. One of such simulators is system PRIME SSF. PRIME SSF is capable of running on a variety of architectures. It can be configured to run either as a stand-alone program, in which case parallelization is supported using shared memory on multiprocessor platforms (including sequential simulation if the machine only has a single processor), or as a distributed program, where communication and synchronization are supported via message passing. Note that the distributed simulation in SSF can be regarded as a collection of SSF simulators each running on multiprocessor machine in a cluster of machines that communicate using message passing. The SSF API contains only five main base classes that can be used for building a complex simulation model. Their functions are briefly described below. Entity is the base class that represents a simulation entity. A simulation entity is a container for simulation state variables. For example, in a network simulation, hosts and routers are typically modeledas entities. Each entity contains variables that describe the state of a router or a host, such as the size of the output queue at the network interface or the remaining time before a packet retransmission. It is expected that user creates a class derived from the Entity base class containing user-defined state variables, including processes and channels. Process is considered as a part of an entity that specifies the evolution of the entity’s state. Each simulation process in SSF is represented by an instance of a Process class or a class derived from the Process base class. These processes as traditional Unix processes: they are independent threads of control. inChannel represents the receiving end of a directed communication link between entities. In SSF, communication between entities is achieved by message passing. An inChannel object belongs to an entity and the ownership is immutable. That is, one cannot change the owner entity of an input channel once it has been created. outChannel is the starting point of a communication link between entities. Similar to the inChannel object, an outChannel object must belong to an entity. An output channel of an entity can be mapped to multiple input channels that belong to this or other entities. A message sent to the output channel will delivered by the simulation runtime system to all corresponding input channels that are mapped to the output channel. Event is the base class that represents messages sent between entities through the communication channels. The user is expected to define his or her own event classes that are derived from this Event base class. In this case, the user is able to include specific information that needs to be passed between entities. SSF API is truly generic for systems that can be modeled as a collection of objects that communicate via message passing. This type of simulation model can be automatically mapped to multiple processors for parallel processing. Personal developmentsDuring performing this work system PRIME has been started on operational system Linux (Ubuntu 5.10) under virtual machine VMware Workstation. In PRIME SSF environment there was simulated the simply computer network where different input parameters are varied and analysis of network was taken for different time of modeling. In PRIME SSFNet environment there was simulated a computer network with 3 hosts which behaviour has been approached to behaviour of a real physical network. Further it is planned to develop own network model in PRIME SSFNet environment, using tools of SSF API on which it would be possible to set varied parameters of a computer network, and by results of modeling to judge performance of model. Run of model on very large-scale network is supposed to be carried out on Microsoft Windows Compute Cluster Server 2003. Experimental researchesThe researches of a computer network were carried out on models: muxtree and 3hosts. The muxtree model represents a simplistic network of multiplexer switches. The network topology is a tree, where the leaves of the tree are traffic sources. Packets are generated from these traffic sources. They travel through the switches and flow to the root of the tree. At each multiplexer, the packets are buffered in a FIFO queue before entering service. Each packet in service waits for some constant service time before it is sent to the multiplexer at the next level until it reaches the root. Packets may be dropped if a buffer overflow occurs. An example topology of the model is shown in figure 3. There are two parameters that control the topology of the tree: the number of input links to each multiplexer switch (fan-in) and the height of the multiplexer tree (levels). In the example shown in the figure, the network consists of 4 levels of multiplexers, each having a fan-in of 2.  Figure 3 - Topology of the muxtree model In 3hosts model there're three types of machines to be employed in emulation. One of more machines will function as the simulation gateway; one of more machines will run the simulator; and one or more machines will function as the client machines, where we run real distributed applications.  Figure 4 – Model 3hosts In further planning to carry out experiments on more common model for which it will be possible to set more input parameters and to make the analysis on the basis of the received results. Overview of results and summaryDuring experiments the following parameters of model are changed: a simulation time, a number of levels of multiplexor’s tree, a count of inputs on each multiplexor, a buffer size, a transfer time, an inter-arrival time, a service time. In each case it was determined number of the sent packages (Num), number of losses (Lost) and number of packages which have achieved a root of a tree (Sent). Modeling was carried out in time to equal 100 seconds. Number of levels in model - 5, inputs - 4, buffer size - 5, transfer time - 5, inter-arrival time - 5, service time - 5. At change of simulation time numerical parameters grew practically linearly.  Figure 5 – Dependence of package’s number on simulation time The increase number of levels in a tree effect exponential growth on number of packages. Thus the percentage ratio of the sent packages to the general number of packages remained almost former (23 %). Change of inputs on each multiplexor with the constant buffer size, results in the heavy losses of packages.  Figure 6 – Dependence of package’s number on levels of tree  Figure 7 – Dependence of package’s number on inputs Changes of the buffer size on each multiplexor does not influence on number of generated packages with length of queue unequal to 0. With increase buffer size number of losses is reduced and becomes significant less, than number of the packages which have achieved a root of a tree, at value 50.  Figure 8 – Dependence of package’s number on buffer size Changes of transfer time take an uniform exposure on results. The variation of n inter-arrival time interval allows to see, that with increase this time the general number of the packages generated for established time, is reduced, and the number of the packages which have achieved a root of a tree, practically remains constant. The increase service time also reduces the general number of packages, and losses remain constants.  Figure 9 – Dependence of package’s number on transfer time  Figure 10 – Dependence of package’s number on inter-arrival time  Figure 11 – Dependence of package’s number on service time Perspectives of further researchesSearch of effectiveness increase of a computer network represents the complex problem demanding all parameters of system. Further development of model in PRIME SSFNet environment is planned with a glance of more network parameters. By results of experiments on this model it will be possible to judge performance of a network, and also to say about a choice of the optimal set of parameters. Run on an uniprocessor machine does not allow to model a large-scale network, therefore modeling will be transferred on compute cluster where it is possible to achieve significant reduction of simulation time. Links
The master's work is developing at the moment.
|
| :: Biography :: Abstract :: Library :: Links :: Search results :: Individual task :: | ||