On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.