Tuesday, August 18, 2015

Session 1, Paper 2: A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks

Authors: Renaud Hartert (UCLouvain), Stefano Vissicchio (UCLouvain), Pierre Schaus (UCLouvain), Olivier Bonaventure (UCLouvain), Clarence Filsfils (Cisco Systems Inc), Thomas Telkamp (Cisco Systems Inc), Pierre Francois (IMDEA Networks Institute)

Presenter: Stefano Vissicchio


This paper introduces a two-layer architecture in control plane to achieve scalable traffic engineering in carrier-grade networks. The solution supports declarativity and expressiveness by doing two things:
  • A centralized optimizer, DEFO, which translates high-level goals into optimized paths
  • A routing model called Middlepoint Routing (MR), which is less constrained than shortest-path routing and natively supports multi-path routing (contrary to end-to-end tunneling).

The two-layer architecture are optimization layer on top of connectivity layer. At optimization layer, it provides a domain specific language which enables network operators to declaratively define traffic engineering targets and constraints, and translates them into optimized paths. At connectivity layer, the configurations are initially done by the operators and later overwritten by optimized ones if generated by upper layer. DEFO computes paths based on Middlepoint Routing model, and midpoint selection is proved to be NP-hard. The authors propose a heuristic approach to compute solutions.

The evaluation is done on multiple topologies (including real-world ISP topologies, topologies from Rocketfuel project and synthetic ones) and multiple demand matrices. The result shows that DEFO is more efficient than incremental IGP-WO, and DEFO has low er optimization overhead compared to RSVP-TE.

To sum up, this paper is interesting in two aspects: 
  • declarativity and expressiveness achieved by a high-level domain specific language
  • leveraging segment routing model enabling scalable traffic engineering in carrier-grade networks
Q&A:
Q: Do you allow subgraph to be shaped across different paths?
A: Yes. We have abstraction of demands, for each demand we have different graphs.
- Follow-up Q: What if there are nodes overlapped between top and bottom?
- Follow-up A: We can do that. It is not a strong constraint.

Q: About choice of optimization, traffic engineering (TE) is normally considered a linear programing (LP) problem, so why use constraint programming (CP)?
A: If you want to support different TE objectives, you need more structured approach. With CP we can support flexibility of our language in an easier way. We are not claiming that CP is better than LP. Another advantage with CP is that we can budget time.
- Follow-up Q: How do you cut off at 2 minutes?
- Follow-up A: It is generally fast with CP to compute a solution.

Q: 2 middlepoints are used in the paper, what about the performance and complexity when using more than 2?
A: 3 middlepoints do not bring much gain. More complexity for sure, but not sure if it will cause problems to the system.