Search

We address the problem of configuring a power distribution network with reliability and resilience objectives by satisfying the demands of the consumers and saturating each production source as little as possible. We consider power distribution networks containing source nodes producing electricity, nodes representing electricity consumers and switches between them. Configuring this network consists in deciding the orientation of the links between the nodes of the network. The electric flow is a direct consequence of the chosen configuration and can be computed in polynomial time. It is valid if it satisfies the demand of each consumer and capacity constraints on the network. In such a case, we study the problem of determining a feasible solution that balances the loads of the sources, that is their production rates. We use three metrics to measure the quality of a solution: minimizing the maximum load, maximizing the minimum load and minimizing the difference of the maximum and the minimum loads. This defines optimization problems called respectively min -M, max -m and min -R. In the case where the graph of the network is a tree, it is known that the problem of building a valid configuration is polynomial. We show the three optimization variants have distinct properties regarding the theoretical complexity and the approximability. Particularly, we show that min -M is polynomial, that max -m is NP-Hard but belongs to the class FPTAS and that min -R is NP-Hard, cannot be approximated to within any exponential relative ratio but, for any ε > 0 , there exists an algorithm for which the value of the returned solution equals the value of an optimal solution shifted by at most ε . [ABSTRACT FROM AUTHOR]

In content delivery networks (CDNs), caches are resources that must be allocated. For that purpose, videos' popularity knowledge helps to make efficient decisions about which videos should be cached. Thus, we must be able to anticipate future needs in terms of requested videos. To do this, we rely on the requests history. This paper focuses on predicting the videos' popularity: the daily number of requests. For that purpose, we propose a two-level prediction approach. At the first level, the experts compute the videos' popularity, each expert using its own prediction method with its own parameters. At the second level, the forecasters select the best experts and build a prediction based on the predictions provided by these experts. The prediction accuracy is evaluated by a loss function as the discrepancy between the prediction value and the real number of requests. We use real traces extracted from YouTube to compare different prediction methods and determine the best parameter tuning for experts and forecasters. The goal is to find the best trade-off between complexity and accuracy of the prediction methods used. Finally, we apply these prediction methods to caching. Prediction methods are compared in terms of cache hit ratio and update ratio. The gain brought by this two-level prediction approach is compared with that obtained by a single prediction level. The results show that the choice of a two-level prediction approach is justified. [ABSTRACT FROM AUTHOR]

Given a directed arc-weighted graph G with n nodes, a root r and k terminals, the directed steiner tree problem (DST) consists in finding a minimum-weight tree rooted at r and spanning all the terminals. If this problem has several applications in multicast routing in packet switching networks, the modeling is not adapted anymore in networks based upon the circuit switching principle in which some nodes, called non diffusing nodes, are unable to duplicate packets. We define a more general problem, namely the directed steiner tree with a limited number of diffusing nodes (DSTLD), that enables us to model multicast in a network containing at most d diffusing nodes. We show that DSTLD is XP with respect to d, and use this result to build a $$\left\lceil \frac{k-1}{d} \right\rceil $$ -approximation algorithm for DST that is XP in d. We deduce from that result a strong inapproximability property. In particular, we prove that, under the assumption that NP $$\not \subseteq $$ ZTIME $$[n^{\log ^{O(1)}n}]$$ , there is no polynomial-time approximation algorithm for DSTLD with ratio $$\varOmega \left( \frac{k}{d}\right) $$ . We finally give an evaluation of performances of an exact algorithm dedicated to the case $$d \le 3$$ . [ABSTRACT FROM AUTHOR]

Some interdomain traffic needs specific guarantees in terms of QoS. Hence, an end-to-end QoS provisioning should be maintained by transit Autonomous Systems and final destinations proposing the services. We propose a distributed stock model following a reverse cascade negotiation in order to enable QoS provisioning at the interdomain level. We analyze different stock strategies on a simple network topology using game theory framework and validate our results by simulation. [ABSTRACT FROM AUTHOR]

To efficiently support the high rate and the high dynamicity of the traffic in metro networks, an optical packet-switched WDM ring, named ECOFRAME, is proposed. The key features of the proposed ring are optical transparency and statistical multiplexing of optical packets on parallel WDM channels. Such features can be exploited by properly allocating wavelengths and receivers. This paper aims to optimally dimension the unidirectional ECOFRAME rings. The dimensioning at minimum cost (i.e., for wavelengths and receivers) is modeled with an mixed-integer linear programming formulation. An heuristic algorithm is also proposed, and its performance is compared against the optimal solutions and bounds. When considering the receiver and wavelength cost, results indicate that trading the wavelengths for receivers allows cost saving of up to 75% with respect to WDM optical packet rings with a single dedicated wavelength per node (i.e., single receiver at each node). [ABSTRACT FROM AUTHOR]

Indexing moving objects (MO) is a hot topic in the field of moving objects databases since many years. An impressive number of access methods have been proposed to optimize the processing of MO-related queries. Several methods have focused on spatio-temporal range queries, which represent the foundation of MO trajectory queries. Surprisingly, only a few of them consider that the objects movements are constrained. This is an important aspect for several reasons ranging from better capturing the relationship between the trajectory and the network space to more accurate trajectory representation with lower storage requirements. In this paper, we propose T-PARINET, an access method to efficiently retrieve the trajectories of objects moving in networks. T-PARINET is designed for continuous indexing of trajectory data flows. The cornerstone of T-PARINET is PARINET, an efficient index for historical trajectory data. The structure of PARINET is based on a combination of graph partitioning and a set of composite B-tree local indexes. Because the network can be modeled using graphs, the partitioning of the trajectory data makes use of graph partitioning theory and can be tuned for a given query load and a given data distribution in the network space. The tuning process is built on a good quality cost model that is supplied with PARINET. The advantage of having a cost model is twofold; it allows a better integration of the index into the query optimizer of any DBMS, and it permits tuning the index structure for better performance. The tuning process can be performed before the index creation in the case of historical data or online in the case of indexing data flows. In fact, massive online updates can degrade the index quality, which can be measured by the cost model. We propose a specific maintenance process that results into T-PARINET. We study different types of queries and provide an optimized configuration for several scenarios. T-PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that our method is robust. It also significantly outperforms the reference R-tree-based access methods for in-network trajectory databases. [ABSTRACT FROM AUTHOR]

In this paper we deal with global communication schemes such as broadcasting or multicasting, in a packet (sub)network in which each node participates in the same distributed application. We want the communication scheme to be performed periodically as often as possible and with some bandwidth guarantee. Such periodicity properties are needed, for example, by multimedia and grid computation applications. We consider commuted switches in the network, i.e., each outgoing link of the switch is assigned to at most one incoming link. Each switch avoids intermediate buffering. Given a network G and a global communication scheme S, an algorithm performing S in G consists in commuting each switch and in specifying to each emitting node the infinite sequence of steps at which it will send a message. The period of this algorithm is the greatest number of steps between two messages emitted by a node. The window of the algorithm is the maximal number of steps needed by a message to reach its destination(s). We first give a general definition of the model of network we consider and of the global communication schemes we study, i.e., the many-to-all scheme where many nodes have one message to send to all the other ones. One well-known case of the many-to-all scheme we especially focus on is gossiping. We present a general way of periodically performing these communication schemes, by covering the graph by substructures called octopuses. Then we show that optimizing the period and the window are two different problems. We end by giving some examples of applications in the torus network. [ABSTRACT FROM AUTHOR]