The lectures will present problems arising in the design of telecommunication networks considered by operators like France Telecom or manufacturers like Alcatel. There will be two kinds of networks studied including optical WDM networks with MPLS management and wireless radio networks. In both cases environmental aspects like minimization of energy will be considered. Examples of such problems are tunnels in MPLS, multicasting, WIFI access, gathering in radio networks, placement of access points, fault tolerant on board satellite networks. For each problem we will show how to give simple models to tackle them. Then we will introduce algorithmic tools to solve them. All these problems being difficult, we will emphasize approximation algorithms, dynamic programming and heuristics. We will also present some powerful theoretical tools in graph theory and combinatorial optimization.
Teachers
- Prof. Jean-Claude Bermond
- Prof. David Coudert
- Prof. Havet
- Prof. Giroire
- Prof. Syska
- Prof. Perennes
- Prof. Galtiere
Teams involved
- Mascotte (INRIA, I3S)
New resources (2011)
Old resources
- Lectures notes (2010)
- Fault-Tolerant Network for Satellites (2010)
- Flow (on class 15/10/2010)
- Chapter 2 from "Routing, Flow, and Capacity Design of Communication and Computer Networks"
- Kleinberg, Tardos; Algorithm design; Pearson Addison-Wensley; 2005.
Chapters 3, 4 & 7 - Satellites problem:
- Greedy algorithms:
- Linear programming:
- Linear programming (chapters 1,2, 17); Vazak Chvatal.
- Graphs & algorithms; Michel Gondram, Michel Minau. (appendix: LP, chapter branch and bounds technics).
- Linear programming; Georges Dantzig. Nice historical presentation.
- Flow:
- Wikipedia article
- Menger's theorem: proof
- Articles on load/RWA:
- A. Schrijver, P. Seymour, P. Winkler, The ring loading problem, SIAM Review 41 (1999) 777-791. [pdf]
In this article, you will find the NP-completeness proof of the ring loading problem and approximation algorithms. - J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-Covering of K_n by Cycles.
Journal of Combinatorial Designs, 11(2):100-112, 2003. [pdf]
Completely solve the load problem for all-to-all set of requests on undirected and directed cycles. - B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes and U. Vaccaro.
Graph problems arising from Wavelength-Routing in All-Optical Networks.
In Proc. Conference WOCS97, Geneva, April 1997, 1997. [pdf] [other version].
Survey results on the relation between the load and the chromatic number. - B. Beauquier, P. Hell, and S. Pérennes. Optimal Wavelength-routed Multicasting.
DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 84(1-3), May 1998. [pdf] [Report]
Proof that the load equals the chromatic number for one-to-all and one-to-many sets of requests in any WDM network - B. Beauquier. All-To-All Communication in some Wavelength-Routed All-Optical Networks.
Networks, 33(3):179—187, May 1999. [pdf]
Consider all-to-all set of requests in some particular classes of WDM networks.
- A. Schrijver, P. Seymour, P. Winkler, The ring loading problem, SIAM Review 41 (1999) 777-791. [pdf]
- Slides on reliability
- Slides "GMPLS Label Space Minimization through Hypergraph Layouts" (15/1)
- Data gathering (22/1)
- Gathering Algorithms on Paths under Interference Constraints
- Data Gathering in Wireless Networks. Vincenzo Bonifaci, Ralf Klasing, Peter Korteweg, Leen Stougie, and Alberto Marchetti-Spaccamela.
- Hardness and approximation of gathering in static radio networks. Bermond, J.-C. Galtier, J. Morales, N. Klasing, R. Perennes, S.
Old Exams Info (2010)
There is no final exam, but an oral presentation (20 minutes + 10 minutes for questions) on one of the articles listed here: http://www-sop.inria.fr/members/Frederic.Havet/Cours/ubinet.html
The presentations will be done on February, 12th during the whole day. You must be here for all the talks. Some tips given: show motivation, results, related work. Reserve some time to talk about possible future work on the topic.
Papers for the presentation
- Call Scheduling in Wireless Networks by J.-C. Bermond et al. Cyprien
- Characterization of graphs and digraphs with small process number by D. Coudert and J.-S. Sereni Madrover
- Coloring powers of planar graphs by G. Agnarsson and M. Halldorsson
- On the complexity of bandwidth allocation in radio networks by R. Klasing, N. Morales and S. Perennes Eric
- On the complexity of the regenerator placement problem in optical networks by M. Flammini et al. Joe
- Directed virtual path layout in ATM networks by J.-C. Bermond et al..
- Distributed computing of efficient routing schemes in generalized chordal graphs by N. Nisse et al. Tuan
- Distributed link scheduling with constant overhead by L.X. Bui et al. Thao
- Diverse routing in optical mesh networks by J. Q. Hu YanWen
- Fractional path coloring in bounded degree trees with applications by I. Caragiannis et al.
- Graph imperfection by S. Gerke and C. McDiarmid
- On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks by P. Saengudombert, E. Modiano and R. G. Gallager.
- Physical topology design for survivable routing of logical rings in WDM-based networks by A. Narula-Tam, E. Modiano and A. Brzezinski Mariem
- Reconfiguration of the Routing in WDM Networks with Two Classes of Services by D. Coudert et al. Amine
- Ring Routing and Wavelength Assignment by G. Wilfong, P. Winkler Bamba
- Shared risk resource group: complexity and approximability issues by D. Coudert et al. Remik
- Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks by N. Cohen et al. Martín
- Traffic grooming in path, star, and tree networks: complexity, bounds and algorithms by S. Huang, R. Dutta and G. N. Rouskas
- A unified approach to distance-two colouring of graphs on surfaces by O. Amini et al.
- Virtula-topology adaptation for WDM mesh networks under dynamic traffic by A. Gencata and B. Mukherjee Claudio
- Wavelength-routed optical networks: linear formulation, resource budgeting tradeoofs, and a reconfiguration study by D. Banerjee and B. Mukherjee
- WDM and directed star arboricity by O. Amini et al.
- GMPLS Label Space Minimization through Hypergraph Layouts by J-C. Bermond et al. Ali
- Discrete Cost Multicommodity Network Optimization Problems and Exact Solution Methods by M. Minoux