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
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.