Internship Position: Network partitioning for scalable routing
Forum 'Stages' - Sujet créé le 2020-12-08 par Youcef Magnouche
Internship Position: Network partitioning for scalable routing
The Network and Traffic Optimization research team of the Paris Research Center is looking for internship candidates. The goal will be the design and the implementation of algorithms to partition networks into areas to improve routing performance. The partitioning and routing methods are based on OR (Operational Research) approaches.
Major Responsibilities
In recent years, the size of networks has increased, and traditional algorithms cannot scale even for a polynomial algorithm like the Dijkstra algorithm. A solution is to divide the network into areas to reduce the size of the network/instance for the algorithms. Traditionally the areas are derived from common engineering practice. In several networks, the routers (nodes) are not assigned a specific role in the topology, and thus portioning is hard to decide.
In this context, the main challenge is to design an efficient partitioning method to obtain a scalable routing in the network. The main objective of this internship will be to design algorithms based on OR techniques (linear programming, graph theory, bi-level) for graph partitioning.
The main objectives of the internship are the following:
- Design and implementation of graph partitioning for large scale networks: exact methods and heuristics using combinatorial optimization.
- Implementation of several algorithms and test overall realistic instances.
- Benchmark existing routing algorithms on the whole network and the partitioned network.
Duration: 6 months
Location: Boulogne-Billancourt, Paris Area
Required Level: Msc in Computer science / Applied mathematics / Operations Research
Technical Skills Requirements:
Candidates must be highly motivated and have the following skills:
- Good operation research and combinatorial optimization skills
- Good mathematical background
- Good programming skills (C/C++/Python)
- Knowledge of networking is a plus but not necessary (IP, routing protocols like OSPF)
Please send your applications to Dr. Sebastien Martin (sebastien.martin@huawei.com) and Dr. Youcef Magnouche (youcef.magnouche@huawei.com). Successful applicants will be contacted within one month.