Bin Packing Problem of Distributed Traffic Engineering

Bin Packing Problem ? What is Bin Packing ? I will explain in this post Bin Packing Problem in MPLS Traffic Engineering. Very complex post normally but I will make it simple for you. And trust me, it is important to understand.

Before I start explaining Bin Packing problem, let’s just remember the purpose of MPLS Traffic Engineering. Very easy, MPLS Traffic Engineering is deployed to use all available capacity on the network, or maximize the capacity usage of the entire network, so at the end ‘ Money ‘ ! If there will be any idle link, due to SPF shortest path selection maybe, MPLS Traffic Engineering gives us to ability to utilize those under utilized or no utilized links as well.

I explain couple other main reasons of MPLS Traffic Engineering in this post, but just remember that, Maximizing the capacity usage of our networks is primary technical goal. Bin Packing problem is just the opposite.

Although the purpose of MPLS Traffic Engineering is to maximize the usage by sending the traffic to the all possible paths optimally, as you will see from the below example, this is not always the case unfortunately.

   

Figure -1 LSP Blocking Due to Bin Packing


In the above topology, PE1 wants to signal RSVP LSP to the PE3. PE1 wants to signal with 300Mbps capacity. 300 Mbps from PE1 to PE3, can be signal through two paths. First one is PE1 – P1 – P2 – PE3 and the second one is PE1 – P1 – P3 – P2 – PE3 Obviously the second one is longer path (IGP cost is higher over the bottom path), thus PE1 to PE3 LSP is setup over the red LSP (PE1 – P1 – P2 – PE3) When this LSP signaled, over the top path, only 700 Mbps link capacity remains.

Bottom path haven’t been used yet, thus bottom path has 500 Mbps capacity. So far, so good, no problem ! But, PE2 will not stay there without any traffic forever. And here it is. PE2 wants to setup 800 Mbps RSVP signaled LSP to PE3. From PE2 to PE3, physically two paths are available.

These are; PE2 – P1 – P3 – P2 – PE3 and PE2 – P1 – P2 – PE3. Although there are two available paths from PE2 to PE3, none of them can be used. Because, top path capacity is only 700 Mbps, because 300 Mbps is used by the RED LSP (PE1 LSP). Bottom path cannot be used, because maximum available capacity is 500Mbps.

This is Bin Packing Problem. If PE2 LSP request would come first, it could use only top path and when the PE1 request comes, PE1 LSP could be setup over the bottom path. But there is no coordination between the PE 1 and PE2. They don’t talk each other and say, hey here is my traffic demand, you should use the top path and I will use the bottom path, so on and so forth.

PE1 request came first, it’s demand is satisfied over the IGP shortest path and Red LSP is signaled. If order would be different, at least in this topology, we wouldn’t have an issue.

This request (Bandwidth in this case) ordering problem is called ‘ race condition ‘ problem. Whoever comes first, He gets the bandwidth baby ! How Bin Packing Problem can be avoided ? Do we have a solution for this ? Fortunately yes. First solution is LSP Priority. By giving a higher priority to the PE2 LSP, when the request comes, PE1 LSP is moved to the bottom path.

Second one is changing the computation mechanism. Note: Below part will be a bit more technical, promised to keep it as simple, but might be harder, let’s try. Distributed path computation with MPLS is done with CSPF (Constrained Based Shortest Path First Algorithm). Each router knows the traffic demand of itself and it attacks to the available bandwidth.

They don’t know the traffic demand of the other routers. But don’t confuse traffic demand with network topology. They of course know the each other topology, because every router in an Area or Level (OSPF and IS-IS respectively) has the same LSDB (Link State Database) and TED (Traffic Engineering Database, TED is only when Traffic Engineering is enabled) Since they don’t know each other traffic demands, if there would be a centralized node which talk with these routers and learn the traffic demands and the network topology, it could calculate the path on behalf of all the routers and tell to the routers which path they should use for their LSPs.

I think some of you are saying that it is SDN approach and that’s correct. In case of MPLS networks, PCE (Path Computation Element) with some extensions, exactly does that. By having centralized traffic demand view, we would avoid Bin Packing Problem, thus would be able to signal required LSP, timely and over an optimal paths. End result would be as below for the above topology.


Figure – 2 Optimal Bin Packing – No Problem for the LSP Demands

PE1 is signaled through the bottom path (Red LSP) and PE2 is signaled through the top path (Blue LSP) 200Mbps (1000- 800Mbps demand of Blue LSP) remains at the top path , 200 Mbps (500 – 300 Mbps demand of Red LSP) remains at the bottom path. No need to have complex priority schema in this case.

Created by
Orhan Ergun

Orhan Ergun, CCIE/CCDE Trainer, Author of Many Networking Books, Network Design Advisor, and Cisco Champion 2019/2020/2021

He created OrhanErgun.Net 10 years ago and has been serving the IT industry with his renowned and awarded training.

Wrote many books, mostly on Network Design, joined many IETF RFCs, gave Public talks at many Forums, and mentored thousands of his students.  

Today, with his carefully selected instructors, OrhanErgun.Net is providing IT courses to tens of thousands of IT engineers. 

View profile

Daniel Lardeux
Daniel Lardeux Senior Network Consultant at Post Telecom

I passed the CCDE Practical exam and Orhan’s CCDE course was very important contributor to my success. I attended the CCDE course of Orhan Ergun in July and it was exactly what I needed, Orhan is taking the pain to break down the different technologies.

Roy Lexmond
Roy Lexmond Senior Network Designer at Routz CCDE #20150017 & CCIE R&S; #26557

After I attended Orhan Ergun’s CCDE course I passed the CCDE practical exam.I really enjoyed the course a lot ...

Nicholas Russo
Nicholas Russo Network Consulting Engineer (CCDE/CCIEx2), Cisc

I signed up for Orhan’s CCDE training. This training is very technically detailed and the use-cases, quizzes, scenarios, and mind maps are all great resources in the overall training program. Orhan teaches his students to think like a network designer ...

Slide Heading
Slide Heading Network Systems Engineer at Conscia A/S CCIE #42544 (SP) & CCDE #20160015

Orhan is forcing you to take off the implementation hat that most of us have been wearing for many years, instead he is providing a new fancy design hat, which makes you see and deal with the issues presented ...

Kim Pedersen
Kim Pedersen CCIE in RS and SP (#29189) CCDE#20170021

I’ve used Orhan’s self-paced CCDE training material. If you are interested in knowing how all the technologies go together in a coherent design i can highly recommend it.I also enjoyed the Quizzes which helped pick out my weak spots in selecting ...

Laurent Metzger
Laurent Metzger 3xCCIE/CCDE Senior Network Architect

Hi Orhan. I passed the CCDE exam on February 22. I read everything that you put on your Self Paced CCDE Training course and it was very helpful in my success. Thank you very much.

Martin J. Duggan
Martin J. Duggan Network Architect at AT&T;, Ciscopress Author CCDE #20160006 & CCIE#7942

I attended Orhan’s April 201610 days CCDE Bootcamp. I am CCDE now !

You can tell Orhan has a great deal of experience, it really comes through when he presents his design case studies and the CCDE Practical scenarios.

Muhammad Abubakar
Muhammad Abubakar Lead Network Architect – CCDE #20160016 2xCCIE #26693 2xJNCIE VCIX

Your excellent CCDE materials and amazing Bootcamp helped me tremendously through my learning journey.Also thank you very much for being available whenever I have a design question or a complex design topics. I can’t compare your design skills ...

Jennifer Pai
Jennifer Pai Network/Security Engineer at KNET Technology

Thanks Orhan very much for this course. It helped strengthen my “Network design mind”.

Ruslan Silyayev
Ruslan Silyayev Solution Architect at R.I.S.K Company

Training by Orhan is not a CCDE preperation training only. It will be useful for engineers which are dealing with design. You want to pass CCDE exam or learn network design, then don’t look at anywhere else!

Sameer Meher
Sameer Meher Solutions Architect at 23 Wards/Japan

Orhan Ergun’s CCDE course was really very good. CCDE Level Intelligence was delivered very well and with very useful case studies and the scenarios, I am thankful to Orhan for all his help!

Ken Young
Ken Young Senior Technical Architect Province of Nova Scotia, 2xCCIE #41597 | CCDE #20170047

If anyone wants to understand network design and architecture, also pass CCDE exam , I recommend you to attend Orhan’s online courses! I am a CCDE now but learning is a journey, we will be together in your other courses too Orhan!

Matt Cross
Matt Cross Technical Architect at Heartland – CCDE #2019::7

Orhan did an excellent job of filling in the gaps of knowledge that I had that took me to the finish line of the practical exam CCDE. The community of people that Orhan facilitates are both engaging and supportive of the journey to CCDE. Orhan ...

Shiling Ding
Shiling Ding Sentinel Technologies – CCDE #2019::12

Just passed the CCDE Practical exam! I attended Orhan Ergun’s CCDE training program , used Orhan’s Instructor Led and Self-Paced CCDE training and Online CCDE Practical Scenarios during my CCDE journey. Orhan’s CCDE In Depth book is an excellent summary ...

Abelardo Basurto
Abelardo Basurto Solutions Architect at Cisco Systems – CCDE 2018::6

Hi everyone, I’ve just passed the CCDE Exam. My Number is CCDE 2018::6 I attended to Online CCDE Bootcamp of Orhan. I want to thank Orhan not only for the great book and bootcamp, but also for his commitment, availability and willingness to assist the ...

Hady Mohamed Abdellah
Hady Mohamed Abdellah Network Architect Hamad International Airport Qatar – CCDE 2018::1

Hi guys, I’m so happy that I passed the exam. I’ve already got my number CCDE 2018::1. Thanks to Orhan for being the best CCDE instructor in the world. I highly recomend Orhan’s CCDE Training and In-Depth-CCDE ...

Bryan Bartik
Bryan Bartik Sr. Systems Engineer at CompuNet – CCDE 20170059

Hi Orhan I passed CCDE Practical exam on November 2017 ! I really enjoyed your materials and quizzes and use cases. They were definitely helpful in my preparation. Thanks a lot !

Giedrius Trapkauskas
Giedrius Trapkauskas Network Solutions Architect at Liberty Global – CCDE 20180004

I attended Orhan’s CCDE Training in Istanbul and it was very helpful in my preparation. I passed the exam recently and I want to say Thank you Orhan! For those who want to pass the CCDE exam, definitely start with ...

Alaa Issa
Alaa Issa Sr.Solutions Architect – CCDE#20180033 3xCCIE ( Collab|DC|Security )#27146

I registered to Orhan’s training in Feb 2017. From that time, I attended Orhan’s training several times. The depth of knowledge which Orhan has is amazing, and how to present such consistent knowledge to the ...

Mazin Ahsan Design Lead Engineer | Solutions Engineer | CCDE License # 20160030 | CCIE Licence # 23892

I passed the CCDE Practical Lab exam on November 17,2016 from supplications of elders and dedication from my Sensei Mr. Orhan Ergun I took different CCDE bootcamps in the past. Orhan has the most depth and expertise ...

Jeff Patterson CCDE# 2018::11

Hi Orhan I wanted to pass along my appreciation for the outstanding training material. I used the online CCDE training provided by Orhan as well as the In-Depth-CCDE book and passed the exam in February 2018. Thank you Orhan!

Mehdi Sfar
Mehdi Sfar Network and Security Architect / CCDE #20210003 | CCIE R&S; #51583

I signed up for Orhan’s CCDE Self paced Course. This course, along with the CCDE In Depth book, helped me for my CCDE Practical as well as Written exams. It pushed me to ask the "WHY" questions and allowed ...

Related courses

Cisco CCDE v3 Training

71:39:34 Hours
225 Lectures
Expert

$1246

MPLS Zero to Hero Training

30:07:04 Hours
51 Lectures
Intermediate

$250

Cisco CCIE Service Provider Training

108:43:00 Hours
258 Lectures
Expert

$1246