Synthese de reseaux pour des communications multipoint (French text).

摘要

This work deals with the design of networks supporting multipoint communications. The network design problem includes two subproblems, routing and dimensioning. The routing is to choose the routes that carry the calls in order to maximize the revenue generated by the multicast connections. The dimensioning is to optimize the capacities of the network links in order to minimize the cost of the network. The design problem is to maximize the net value of the network.; Network design with point-to-point connections has shown that the direct link is often optimal to connect the calls either in the call routing context or in the dimensioning context. Multipoint connections are connected using trees instead of paths.; Our first objective is to understand the tree selection problem and to evaluate its impact on the network performance. Second, we want to give a mathematical formulation for the tree selection problem. Third, we want to investigate how traffic variation affects the network performance. We also want to investigate the importance of knowing a priori the traffic demands and the members participating in the communications. Finally, we want to generalize our work to the multi-class case.; We can summarize our contributions as follows. First, we have highlighted and prioritized the important points of the network design problem with multipoint communications.; We have established two simple criteria for the tree selection, one for routing and one for dimensioning. We have shown that these two criteria are contradicting each other.; We then have proposed two algorithms to select the trees in the call routing context, one based on the gradient projection method and one based on a heuristic.; We have also proposed two algorithms to select the trees in the network design context, one based on the gradient projection method with column generation and one based on a simple heuristic.; We have also studied the network design problem with point-to-point and point-to-multipoint communications and have shown that the results depend on the mix of traffic.; We have also studied the sensitivity of the network performance in the presence of traffic variation. We have shown that the variation of the traffic intensity has a negligible impact on the network performance.; We then have proposed an algorithm to economically increase the network connectivity and we have shown that introducing more connectivity in the network is done at a much higher price than the improvement of the revenue obtained by re-optimizing the call routing.; Finally, we have generalized our study to the multi-class case and we have shown that our conclusions are valid in that context. (Abstract shortened by UMI.)