Volume 31 - 2019 - CARI 2018

Special issue for CARI 2018

1. ε-TPN: definition of a Time Petri Net formalism simulating the behaviour of the timed grafcets

Sogbohossou, Médésu ; Sogbohossou, Medesu ; Vianou, Antoine ; Gmati, Nabil ; Badouel, Eric ; Watson, Bruce.
To allow a formal verification of timed GRAFCET models, many authors proposed to translate them into formal and well-reputed languages such as timed automata or Time Petri nets (TPN). Thus, the work presented in [Sogbohossou, Vianou, Formal modeling of grafcets with Time Petri nets, IEEE Transactions on Control Systems Technology, 23(5)(2015)] concerns the TPN formalism: the resulting TPN of the translation, called here ε-TPN, integrates some infinitesimal delays (ε) to simulate the synchronous semantics of the grafcet. The first goal of this paper is to specify a formal operational semantics for an ε-TPN to amend the previous one: especially, priority is introduced here between two defined categories of the ε-TPN transitions, in order to respect strictly the synchronous hypothesis. The second goal is to provide how to build the finite state space abstraction resulting from the new definitions.

2. Dynamic resource allocations in virtual networks through a knapsack problem's dynamic programming solution

Kengne Tchendji, Vianney ; YANKAM, Yannick Florian.
The high-value Internet services that have been significantly enhanced with the integration of network virtualization and Software Defined Networking (SDN) technology are increasingly attracting the attention of end-users and major computer network companies (Google, Amazon, Yahoo, Cisco, ...). In order to cope with this high demand, network resource providers (bandwidth, storage space, throughput, etc.) must implement the right models to understand and hold the users' needs while maximizing profits reaped or the number of satisfied requests into the virtual networks. This need is even more urgent that users' requests can be linked, thereby imposing to the InP some constraints concerning the mutual satisfaction of requests, which further complicates the problem. From this perspective, we show that the problem of resource allocation to users based on their requests is a knapsack problem and can therefore be solved efficiently by using the best dynamic programming solutions for the knapsack problem. Our contribution takes the dynamic resources allocation as a multiple knapsack's problem instances on variable value requests.