Some samples of our works

Assessment of User QoS in a Deployed GPRS Network

Person in charge :     Frédéric Bodevin In this project, we studied the problem of how to assess the QoS seen by the user in a deployed GPRS network. For this, we studied the major features that could affect the QoS in the GPRS system and created a simulation tool to be able to evaluate the user QoS in different scenarios. We later took real-life measurements in a commercial network and were able to calibrate the tool with the obtained data. We compared the assessed measures with the ones obtained with the calibrated tool. The work allowed a wireless operator to have a better understanding of the QoS phenomena in its deployed network. Publications : Frédéric Bodevin's Master Thesis (École Polytechnique de Montréal) SANSÒ, B., QoS Assessment for GPRS Networks. - Final report SANSÒ, B., BODEVIN, F., Assessing User QoS in a Deployed GPRS Network. Working paper presented at the CORS National Meeting, Vancouver, June 2003. Note: This work won the 2nd prize in CORS Practice Competition.

Performance and routing evaluation of IP networks under GPS and RSVP

Person in charge :     Kajetan Litwin We propose new stochastic routing methods to optimize the performance and the Qualite of Service (QoS) for IP multi-service networks working under GPS discipline and using reservation protocols such RSVP. Our work show that these routing models, based on stochastic measures of maximal delais perform better that conventional algorithms. Publications : Kajetan Litwin's master Thesis (École Polytechnique de Montréal) Paper in preparation.

Design of flat hybrid opto-electronic networks

We propose a network design model for flat networks using hybrid optical/electronic equipments. We describe a set of network components that can be taken into account by this model. We formulate the network design problem and illustrate its difficulties. We then introduce a simpler model for which solutions can be computed easily. Using this simple model, we give numerical results that illustrate the impact of the cost of optics and the cost of electronics on the resource utilization and on the optimal topology of the logical network. One of the main results is that degree constraints on the switches can have a significant impact on the network cost. Another important result is that one cannot rely on intuition to find a good trade-off between optics and electronics. Publications : MEDDEB, A., GIRARD, A., SANSÒ, B., Design Model for Minimum Cost Flat Hybrid Optoelectronic Networks, Submitted to Telecommunication Systems, 2000.

Design of reliable WDM networks

Person in charge :     Antonio Nucci In these work, we take into account failure and dynamic capacity of routing at IP level, to obtain, for the first time, more reliable logical topologies for WDM networks that support unicast and multicast IP connexions. The obtained results show that this approach gives better logical topologies with limited complexity. Publications : Nucci, A., Sansò, B., Crainic, T.G., Leonardi, E., Ajmone~Marsan, M. , Design of Fault-Tolerant Logical Topologies in Wavelength-Routed Optical IP Networks, may 2001, 16 pages.

Bandwidth Management Problems for multi-service networks

Person in charge :     Michaëla Plante Currently, technological possibilities for implementing multi-service networks include both single technology ATM or IP networks and multi-technology networks such as SONET-based or flat networks. However, regardless of the technology employed, the synthesis problem - to optimally route traffic and divide the network's transmission resources between it's virtual links - and to control the bandwidth online and offline for each services remains of prime importance. We propose a classification typology for these problems and new algorithms to solve it. Publications : PLANTE, M., SANSÒ, B., A Typology for Multi-technology, Multi-service Network Synthesis Methods. Accepted in Telecommunication Systems, 2001.

Design of wireless broadband multiservice networks

Sorry, it is a confidential contract and we cannot give details.

Design and topological update of broadband networks with modular switches

Access and backbone have traditionally been designed as two separate networks. This simplifies the resolution approach but can yield to very suboptimal solutions. The difficulty is that realistically sized networks are impossible to tackle directly due to the large combinatorial nature of the problem. A major breakthrough in this area has been to go against the general wisdom and tackle the design jointly, even considering very detailed technical features such as switch modularity, multiplexers, etc. We apply a special decomposition and a clever tabu search to be able to deal with large problems. This approach beats any approach previously proposed: it yields optimality gaps lower than 3% for problem instances of up to 500 users. Expansion problems as well as multitechnology problems have also successfully being tackled. More recently we considered, for the first time in the literature, the joint design of IP WFQ access-core networks with performance guarantees in normal and failed conditions. Publications : CHAMBERLAND, S., SANSÒ, B., On the Design of Multitechnology Networks. Accepted in INFORMS Journal on Computing, 2001. CHAMBERLAND, S., SANSÒ, B., Topological Expansion of Multiple Ring Metropolitan Area Networks, Networks, 36,4, 210-224, 2000. CHAMBERLAND, S., SANSÒ, B., MARCOTTE, O., Topological Design of Two-Level Telecommunication Networks with Modular Switches, Operations Research, 48-4, 745-760, 2000.

Optimal Broadband access planning problems

We present a fast tabu search method for the design of access tree networks. We connect a population of users to a set of switches using a variety of SONET channels on fiber optics links and ADM equipment at the nodes. We specifically take into account the economies of scale provided by the transmission systems and the transmission hierarchy of SONET systems. We describe in detail the parameters used for defining neighborhoods, penalty parameters, data structure and indicate how this can lead to substantial improvements of the overall computational time while providing costs lower than those of a more direct method. Publications : GIRARD, A., SANSÒ, B., DADJO, L., A Tabu Search Algorithm for Access Network Design. Accepted in Annals of Operations Research, special issue on Topological Network Design in Telecommunication Systems, Peter Kubat and James Mc.Gregor editors, Baltzer Scientific Publishers, 2001

Routing models taking into account the Non-Poisson nature of the traffic

Routing models for packet-switched networks have traditionally been based on the assumption that the offered traffic is Poisson. This is unrealistic since for many applications, real life data streams tend to be extremely "bursty", contradicting the Poisson assumption. We have introduced a centralized bifurcated routing optimization model for networks with significantly non-Poisson offered traffic. The central purpose of the work was to assess the impact of non-Poisson traffic on routing algorithm developed for Poisson flows. Publications : GENDREAU, M., SANSÒ, B., STANFORD, D., Optimizing Routing in Packet-switched Networks with NonPoisson Offered Traffic, Telecommunication Systems Modeling, Analysis, Design and Management, 5, 323-340, 1996.

Routing, QoS and GoS in IP and ATM multiservice networks

We developed routing algorithms which take in account of QS and GS's various measures for IP and ATM networks. The publications are confidential.

Synthesis and management of multiservice-multitechnology (IP, ATM, SONET, flat) networks

Currently, technological possibilities for implementing multi-service networks include both single technology ATM or IP networks and multi-technology networks such as SONET-based or flat networks. However, regardless of the technology employed, the synthesis problem - to optimally route traffic and divide the network's transmission resources between it's virtual links - and to control the bandwidth online and offline for each services remains of prime importance. We propose a classification typology for these problems and new algorithms to solve it. Publications : PLANTE, M., SANSÒ, B., A Typology for Multi-technology, Multi-service Network Synthesis Methods. Accepted in Telecommunication Systems, 2001.

Reliability and routing of telecommunication networks

The classic measures of reliability are related with the notion of connectivity. However, the telecommunication networks being of flow networks, these measures do not put in evidence what really happen in the network when there is a breakdown. In these works, we have proposed new measures and show the importance of the routing during the evaluation of the reliability. Publications : SANSÒ, B., SOUMIS, F., GENDREAU, M., Centralized and Decentralized Stochastic Routing Models in Telecommunication Networks, Telecommunication Systems Modelling, Analysis, Design and Management C, 1, 133-148, 1993. SANSÒ, B., GENDREAU, M., SOUMIS, F., An Algorithm for Network Dimensioning Under Reliability Considerations, Annals of Operations Research, 36, 263-274, 1992. SANSÒ, B., SOUMIS, F., Communications and Transportation Networks Reliability Using Routing Models, IEEE Transactions on Reliability, 29-38, April 1991. SANSÒ, B., SOUMIS, F., GENDREAU, M., On the Evaluation of Telecommunication Networks Reliability Using Routing Models, IEEE Transactions on Communications, 39(10), 1494-1501, 1991.

IP and ATM network reliability and synthesis

The synthesis of the switched layer is generally carried out taking into account the user's required quality of service (QoS) for the normal state. QoS degradation in failure situations is usually studied afterwords, by simulating major disruptions. In previous work, we proposed a totally different approach to assure network robustness: incorporate the failures and the QoS in failed situations directly into the design procedure. This simple idea, that has been implemented in packet, circuit, ATM and WDM networks gives rise to networks that cost less and perform better. Note that this type of approach is just now gaining in popularity in the telecommunication community under the name of "design protection". Publications : GIRARD, A., SANSÒ, B., Multicommodity Flow Models, Failure Propagation and Reliable Network Design, IEEE/ACM Transactions on Networking, 6(1), 82-93, 1998. CHAMBERLAND, s., SANSÒ, B., Sequential Parallel and Approaches to Incorporate Reliability in the Synthesis of Computer Networks, Journal of Networks and System Management, 131-157, 1997. SANSÒ, B., GIRARD, A., MOBIOT, F., An Integrated Model for Reliability and Synthesis of ATM Networks with SVCs Connections, Submitted to IEEE/ACM Transactions on Networking, 2000. NUCCI, A., SANSÒ, B., CRAINIC, T.G., LEONARDI, E., AJMONE-MARSAN, M., Design of Fault-Tolerant Logical Topologies in Wavelength-Routed Optical IP Networks. Accepted in Globecom, 2001.

Multicasting

The Steiner Tree Problem in graphs (STP) is well known NP-Hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as multicast IP and ATM, since it appears as the inherent mathematical structure behind multicast communications. We propose a tabu search algorithm for the STP in graphs. The main features of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and powerful diversification mechanisms. Computational results on the benchmark problems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics. Publications : GENDREAU, M., LAROCHELLE, J.-F., SANSÒ, B., A Tabu Search Heuristic for the Steiner Tree Problem, extended abstract (invited), Proceedings of the Third ORSA Telecommunications Conference, Boca Raton, USA, March 1995.

Dimensioning of a Largely Distributed Computer Networks in an Air-Ground Application

Since computers are distributed on many continents worldwide, the service demand per site (as measured by messages to be treated) can vary greatly with time of day. We propose a model for optimizing costs while taking advantage of the demand variations over time and the possible load sharing among the sites. The model consists of a mixed integer programming formulation with non-linear constraints. The model aims at finding the best number of computer elements while taking into account international load sharing between sites and guaranteeing a good response time from the system. The problem was solved to optimality by careful modelling and exploitation of the system constraints. We found, for a real system, that this type of optimization yields substantial gains when compared with redundant solutions. The problem presented can very well be adapted to ASP's internaitonally distributed systems. Publications : KREIDI, A., SANSÒ, B., Optimization of an Internationally Distributed Air-Ground Airline Telecommunication System, accepted in Telecommunication Systems, February 2001. KREIDI, A., SANSÒ, B., Optimization of a Geographically Distributed AirGround Airline Telecommunications System, Telecommunication Systems, Nashville, USA, March 1995, 186-187.

Managing redundant information in largely distributed computer systems

Managing redundant information is becoming an important issue in today's increasingly large distributed computer networks. As total redundancy is extremely costly to achieve, it has been proposed to keep perfectly updated information only at the servers, while keeping old copies of that information on local computers. For such copies to be useful, a maximum lifetime length is assigned to them. Before the lifetime has elapsed, the local devices must be stashed with a new updated copy. The problem of optimizing the updates so that the maximum lifetime length constraints are respected has been previously formulated as a binary problem and proved to be NP-hard through a reduction to the Steiner tree problem in graphs. We explore the properties of another formulation, based on a state transition graph approach. We prove that only a subset of states and transitions will be in the optimal solution and that, thanks to those properties, it is possible to greatly reduce the size of the graph. This problem is closely related to the multicast problems proposed for IP, as well as to several caching schemes that are being proposed for IP and entertainment satellite networks. Publications : WALKER, B., SANSÒ, B., Managing Redundancy in a Distributed Computer Network: A State Transition Approach for the Stashing Problem, Operations Research, 46(3), 305-315, 1998. SANSÒ, B., SOUMIS, F., The Dynamic Predicate Stashing Copy Problem, Networks, 23(8), 681-690, 1993.