Luận án: Mô hình và Thuật toán Tối ưu Mạng với Segment Routing - François Aubry

Models and Algorithms for Network Optimization with Segment Routing François Aubry February 2020 Université catholique de Louvain (UCLouvain) Institute of Information and Communication Technologies Electronics and Applied Mathematics (ICTEAM) Louvain School of Engineering Louvain la Neuve, Belgium Thesis Commitee: Yves Deville, UCLouvain, Belgium (supervisor) Olivier Bonaventure, UCLouvain, Belgium (supervisor) Charles Pecheur, UCLouvain, Belgium (chairperson) Pierre Schaus, UCLouvain, Belgium Bernard Fortz, ULB, Belgium Stefan Schmid, University of Vienna, Austria J’ai l’impression que ce qui compte dans la vie, c’est jeter de la poussière d’électron libre comme un papillon qui tourne, qui tourne même au prix de se brûler sur la lanterne, ce qui compte, c’est le rêve. Comme Einstein qui rêve qu’il chevauche un rayon de lumière, comme Vieux Temps qui enferme le tragique de la beauté dans quelques minutes de violon, comme celui qui sourit à sa voisine de palier, comme toi et moi au jeu des bouches de fer: tout ça, c’est la même chose, c’est la tentative insensée de la vie qui cherche à exploser au moins pour quelques instants. Et regarde toutes ces femmes dans le monde qui, sans désemparer, maintiennent la cohérence et permettent aux enfants de rêver. Mais même en mourant, on peut écouter de la musique, on peut encore rêver.

Géry Aubry Abstract Optimizing the way traffic is routed over networks has been of interest since we first started using computer networks to communicate and exchange infor- mation. Network technologies are constantly evolving and so do the underlying problems that need to be solved. This thesis focus on studying the recently proposed segment routing tech- nology. In a traditional IP network, packets are routed using shorted paths according to weights that are configured on the network links.

Segment rout- ing offers a new way of routing traffic by allowing packets to do some detours on their way. Between these detours, traditional shortest path routing is used, making this technology have almost no usage overhead. We aim at providing a mathematical formalization of segment routing and showcase several of its use cases. We believe that such a formalization is going to help advance the research of the algorithmic aspects of segment routing by providing a solid mathematical foundation and notations which can serve as a starting point for others to research this topic.

We leverage segment routing to solve traffic engineering problems, perform network monitoring and provide traffic duplication services that are robust to link failures. 3 4 Acknowledgements So many things to say. Doing this thesis lead to some of the best moments and memories of my life so far. This is not surprising when we consider that it accounts for about 19% of it.

I have had the chance to share my office with amazing people. Over these years we shared a lot of things and I strongly believe that those will be the most important takeaways from having done a PhD. Michael, even though you hated me on the first few weeks (months?) because I allegedly refused a beer from you when we were students, I am glad that we moved passed that to become such good friends. I own you a lot.

Not only did I learn to like beer (which is very useful when you live in Belgium), but you definitely made all these years memorable. From the travels to the simple things such as just sitting on the balcony saying random things, all those moments come together as the best years of my life. I hope Roxanne does not beat me after reading this! You are the best. Trung, you were already the office boss when we arrived.

I remember our first trip to Paris for the Column Generation school. I think this is when the three of us actually became close. We had printed this 9x9 GO board that we would bring everywhere to play. I think we probably annoyed a lot of restaurant and bar owners along the way.

I regret only being too scared of flying to attend your wedding, it was stupid. Fortunately now I am over it and we could already meet twice in Vietnam! Can’t wait to see you in May! Thanh, you completed our office in the best possible way! I was so happy to have you come back to do your PhD with us. Living with you, Nhung, Brinnie and Ratheil was very nice for me. I will always remember our Smash Bros tournaments.

I hope that one day we can meet in Vietnam rather than Belgium! Ratheil (a.a Bowser), we first started talking at the ICTEAM day. I will always remember the subject of that conversation (M). I think that since that day we became good friends. We shared an apartment for a few years and, believe me when I tell you that the 6 months that you were away every year really were the worst months of the year.

You were there for a lot of the important and hard things that life threw at me (or that I threw at myself?). I am very grateful to you. You are strongly missed in Belgium, you should come back more often! Also, I can’t wait to see you in Benin! John. things have never been the same since you arrived.

You brought so much life and joy to the group. The time when you and Ratheil were in the office next door were really the funniest times to work at INGI. You taught me a lot of good ways to see life and face problems. I really appreciate you and hope that we can remain as close friends as we are regardless of distances.

Thanks 5 6 for that trip in the US, it was awesome! I am still waiting to see you in Taı̈wan! Nathan, don’t let Delphine read this or it might make her cancel your wed- ding! Our love is boundless! I wish I could be as wise as you and bury my young self. However I don’t know yet how to do that. I promise that I will continue trying if you promise that you will consider buying new pants. It will be good for both of us.

Raziel, my dear friend. It is crazy to think that we spent so much time in the department before talking for the first time. I love how you are always ready to party and have fun. Thank you for all those beers that we shared.

I hope that one day you will bring me to Mexico! Gaël, I think we share a lot of interests, if you know what I mean (T)! It was good to have someone to talk about these things. It is funny that out of all the traveling and cool things that I did in these years, the things I remember the most are simply the times when some of us stayed late at the office and just talk about everything. Olivier, I would write Goletti but then you will be mad at me. After knowing you I think that the 3rd floor is the right place for you.

Welcome! I would have liked to have started knowing you better earlier though. Hopefully I can still have access to the office for the next few months! Bruno, you are the one friend I could keep from Portugal when I moved to Belgium. You made studying mathematics feel like a stand-up comedy show. I would give everything to spend one more week in that life.

It was fun while it lasted. Fortunately, now our paths crossed again and it is work that feels like a stand-up comedy show. Thank you for all the laughter. I would like to thank my mother, father and brother for putting up with me for so long.

I know it was not always easy. Dad, I miss you too much. Loosing you was by far the hardest challenge during this thesis. You still live in me, even if only as brain waves whenever I remember you.

Mom, you are probably the one who did the most of all for me. You are the one who made everything else possible. All the good times happened because you were there facilitating it. There are no words that I could say that would accurately represent how thankful I am.

Antoine, you are eight years older than me but that did not prevent you from always being there with me while growing up. I don’t think a lot of kinds have had the luck I had to have an older brother like you. You’ve made me treasure my childhood to the point were I am often nostalgic about it even nowadays. I would like to thank my supervisors Yves Deville and Olivier Bonaventure without whom this work would simply not exist.

When I started this thesis I was working on a subject that did not speak to me. Olivier saved me by finding the subject that I would eventually fall in love with. I will be forever grateful for that. Both of them put in countless hours to help me do the best that I could.

I want to also thank my thesis committee for their insightful questions and comments on my thesis. You really made me happy for having written it. 7 To all the students with whom I had the chance to interact with: Thank you. Specially all of you that I had the privilege to coach.

I probably learned more from you all than you did from me. It was a blast and I am sad that it is over. I hope that you all had as much fun as I did. I won’t cite all names because there are so many names that I will probably forget some.

Lastly but not least, I want to thank my girlfriend, Yeyeh. You are the one that puts up with me every day. As I said, it is not easy but yet, here you are. I hope it will remain as such.

You’re simply the best. Everyday you make my dreams a possibility.1 Why segment routing .2 SR applications and contributions .4 Structure and style. 18 2 Network and routing model 19 2. 22 3 Topology dataset analysis 27 3.2 ECMP and non shortest path links .3 Degrees and density .1 Segment routing formalization .2 Acyclic sr-paths.

52 5 Optimal sr-paths 61 5.1 Minimum weight sr-path .2 Achieving minimum latency with SR .2 Maximum weight sr-paths .3 Maximum capacity sr-paths. 76 6 Traffic engineering with SR 77 6.1 Traffic engineering formalization .2 A brief introduction to LP and MIP .3 Traffic engineering with segment routing .1 Existing MIP models and algorithms for SRTE .4 The idea behind Column Generation .5 CG for the path model .6 Minimizing the worst link utilization λ .7 CG experimental results .1 Near-optimum evaluation .2 Any-time behavior .3 Adjacency segment benefits. 104 7 Network monitoring with segment routing 107 7.1 Minimum segment cost covers .2 Column generation cycle cover algorithm .3 Pinpointing single-link failures .4 Dual topology monitoring .1 Computing ECMP-free and complete IGP weights .2 Prime-based complete IGP .3 Randomized complete IGP .4 Cycle covers with ECMP-free and complete IGP. 135 8 Disjoint paths with SR 139 8.1 Disjoint paths and network flows .2 Disjoint sr-paths .1 Maximum set of disjoint sr-paths .2 Minimizing the total latency .3 Min-max edge-disjoint sr-paths .4 Robustly disjoint sr-paths .1 Adapting SR-2EDP to RDPs .2 Adapting the dedicated algorithm to RDPs .3 The case of single-link failures .4 Evaluation of RDPs.

160 9 Conclusion 169 Chapter 1 Introduction Optimizing the way traffic is routed over networks has been of interest since we first started using computer networks to communicate and exchange information [48, 53]. Network technologies are constantly evolving and so do the underlying problems that need to be solved. This thesis focus on studying the recently proposed segment routing technology. In a traditional IP network packets are routed using shorted paths according to weights that are configured on the network links.