Contribuições à modelagem e à simulação de sistemas distribuídos usando redes de Petri coloridas - alocação de webcaches e particionamento de modelos em processos independentes

Abstract

The investigation of specific aspects of a system through simulations makes it possible to identify in advance faults, blocks and instabilities , among other aspects. Thus, the costs and risks associated with the implementation of systems are reduced, making it possible to analyze the projects of these systems in different scenarios. To this end, coloured Petri nets (CPN) are often used. However, simulating systems at multiple levels of abstraction, including specific analyzes and performance evaluations, may require highly specialized technical knowledge, increasing the cost of the simulation. In addition, simulators developed for large systems that allow complex configurations may require a large amount of computational resources, compromising simulations based on CPN. Aiming to provide mechanisms to reduce the cost of extensibility and increase the robustness of simulations performed in CPN, two contributions are presented in this thesis. In the first one, we present the Multi-Language Programming Interface (IPML), which allows to extend simulators without in the CPN. In order to validate IPML, two extensible simulators were developed: CacheSim, a tool that provides a platform for modeling, configuration and use of Internet caching policies, and TransportSim, a configurable tool that allows the representation and analysis of simulation scenarios for metro / rail transportation. It is demonstrated, in the form of use cases, how to extend these simulators without modifying the CPN. As a second contribution, we propose distributed colored Petri nets (DCPNs), which allow the design of individual models that are not necessarily hierarchical, and which can be executed in independent processes on different computers. The distribution of a CPN model is performed with the addition of the Distributed Fusion Place concept. Simulations are possible with the execution of algorithms that allow the communication and coordination of the multiple processes that contain the individual models and execute simultaneously. In order to dispense with the use of priorities as a solution to distributed conflicts and thus not to compromise the analytical power of the CPN, a protocol has been created for simultaneous access to multiple critical regions, ensuring fairness in the selection of events that may occur and allowing parallel execution of non-conflicting transitions. The DCPN allows the conception and distributed simulation of CPN without adding new semantic resources to CPN. This allows the transformation of centralized simulators into a single process in simulators that can be distributed in multiple execution nodes, with effective low development cost. The formal definition of DCPN is presented and the analysis of a distributed model is discussed. The results demonstrate that the addition of new processes increases the performance of a simulation up to a saturation limit, in which the cost of communication between the multiple nodes does not compensate the segmentation of the model.