Soutenance de These Haitao Wu Approximation algorithm design and analysis in next generation communication networks'

PhD defense (Haitao Wu) entitled ''Approximation algorithm design and analysis in next generation communication networks''


  The phd defense will take place at 14h, Monday November 5th, in the salle de these of the Saint Marte Campus.


Title : Approximation algorithm design and analysis in next generation communication networks

Time: Monday, November, 5th,  14h

Place:  Salle de these, Sainte Marte (City center)


Jury :

  •         M.  Walid Ben-Ameur, Professor, Telecom SudParis : Reviewer ; 
  •         M.  Ken Chen, Professor, Univ. Paris 13 : Reviewer;
  •         M.  Eitan Altman, Senior Researcher, INRIA,  : Examiner ;
  •         M.  Abderrahim Benslimane, Professor,  Univ. Avignon : Examiner ;
  •         Ms. Annie Gravey, Professor,  IMT Atlantique : Examiner ;
  •         M.  Juan-manuel Torres,  Asso. Professor HDR, Univ. Avignon,  Supervisor
  •         M.  Fen Zhou, Asso. Professor HDR,  ISEP/Univ. Avignon, co-Supervisor
  •         M. Yaojun Chen, Professor,  Nanjing Univ, co-Supervisor



With the coming of intellectual era and Internet of Everything (IoE), the needs of worldwide communication and diverse applications have been explosively growing. This information revolution requires the future communication networks to be more efficient, intellectual, agile and scalable. Many technologies have emerged to meet the requirements of next generation communication networks such as Elastic Optical Networks (EONs) and networking virtualization. However, there are many challenges coming along with them, such as Routing and Spectrum Assignment (RSA) in EONs and Virtual Network Embedding (VNE) in network virtualization. This dissertation addresses the algorithm design and analysis for these challenging problems: the impacts of traffic distribution and network topology on lightpath routing, the distance spectrum assignment and the VNE problem for paths and cycles.

      For lightpath routing, the first subproblem of the RSA, there is always a pending issue that how the changes of the traffic distribution and EON topology affect it. As the lightpath routing plays a critical role in the overall performance of the RSA, this dissertation provides a thoroughly theoretical analysis on the impacts of the aforementioned two key factors. To this end, we propose two theoretical chains, and derive the optimal routing scheme taking into account two key factors.

     We then treat the second subproblem of RSA, namely spectrum assignment. Any two lightpaths sharing common fiber links might have to be isolated in the spectrum domain with a proper guard-band to prevent crosstalk and/or reduce physical-layer security threats. We consider the scenario with diverse guard-band sizes, and investigate how to assign the spectrum resources efficiently in such a situation. We provide the upper and lower bounds for the optimal solution of the DSA, and further devise an efficient algorithm which can guarantee approximation ratios in some graph classes.

     The topology heterogeneity of Virtual Network Requests (VNRs) is one important factor hampering the performance of the VNE. However, in many specialized applications, the VNRs are of some common structural features $\textit{e.g.}$, paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications by accounting for topology characteristics. We prove the NP-Harness of path and cycle embeddings. To solve them, we propose some efficient algorithms and analyze their approximation ratios.


Key-words: Elastic Optical Networks (EONs), Routing and Spectrum Assignment (RSA), Distance Spectrum Assignment (DSA), Virtual Network Embedding (VNE), Approximation Algorithms.

Lundi, 5 Novembre, 2018 - 14:00 to 16:00

Laboratoire Informatique d'Avignon

Université d'Avignon et des Pays de Vaucluse
339 chemin des Meinajaries, Agroparc BP 91228, 84911 Avignon cedex 9
+33 (0)4 90 84 35 00