MetaOpt
Towards efficient heuristic design where we achieve quantifiable and confident performance
We use heuristics all the time across many systems including those that are critical to production services. Production systems use heuristics because they are faster or scale better than their optimal counterparts. But practitioners often don’t know the performance gap between the heuristic and the optimal, or another heuristic in realistic scenarios. We present MetaOpt, a system that helps analyze heuristics.
Do you have examples where you used MetaOpt?
Here are some example use-cases and results:
Comparing Heuristics in Traffic Engineering. We used MetaOpt to find the performance gaps for demand pinning and POP where we compare them to the optimal multi-commodity flow algorithm. We compute the performance gap — the difference between the heuristic and the optimal which we normalize by the total network capacity. The performance gap is a lower bound on the optimality gap, the worst-case gap between the two.
We find the demand pinning (DP) heuristic Microsoft uses for WAN traffic engineering and POP incur 33.9% and 20% relative performance gaps on a large topology. This means there exists (and we can find) adversarial traffic demands that cause the demand pinning heuristic we use in Microsoft to use 33.9% more capacity compared to optimal. Network operators that use DP may need to over-provision the network by that much to satisfy this demand. MetaOpt by default, searches for adversarial demands among all possible demands.
We can constrain MetaOpt to search over realistic demands. These exhibit temporal locality where few node pairs communicate. The gap for PoP and DP reduces by less than 1% when we run MetaOpt with this constraint.
Comparing heuristics in Packet scheduling. We compared the packet scheduling algorithm SP-PIFO to PIFO. We compute and compare the priority-weighted average packet delay between the two algorithms which penalizes them if they increase the delay of high-priority packets.
MetaOpt shows there exists an input packet sequence where SP-PIFO is 3X worse than PIFO. We used MetaOpt to compare SP-PIFO and AIFO (two heuristics). AIFO emulates PIFO through a single FIFO queue. MetaOpt finds inputs for which AIFO incurs 6X more priority inversions than SP-PIFO. Such analyses can help designers weigh performance trade-offs against switch resource usage.
Proving properties of and improving heuristics. We used MetaOpt to find adversarial inputs for various heuristics and analyzed these inputs to prove performance bounds for these heuristics or to improve them.
We proved a new bound for vector bin-packing. Vector bin packing (VBP) heuristics try to minimize the number of bins they use. Theoreticians prove bounds on their approximation ratio: the worst-case ratio, over any input, of the number of bins the heuristic uses compared to the optimal.
A heuristic’s approximation ratio is the worst-case ratio, over any input, of the number of bins needed for the heuristic to that needed for the optimal. Recent work showed 2-dimensional FFDSum (which is a greedy heuristic that scores and sorts balls based on the sum across all of their dimensions and adds them to the first bin they can fit in) asymptotically approaches an approximation ratio of 2 (where the optimal uses nearly infinite bins). We proved the approximation ratio is always at least 2—even when the optimal requires a finite number of bins!
Proving a new bound for packet scheduling and improving the heuristic. We analyzed adversarial inputs MetaOpt found for SP-PIFO and proved a lower bound on its priority-weighted average delay relative to PIFO. The bound is a function of the priority range and the number of packets.
Adversarial inputs to SP-PIFO trigger priority inversions, which queue high priority packets behind low priority ones. We tested a Modified-SP-PIFO, which splits queues into groups; we assign each group a priority range, and run SP-PIFO on each group independently. Modified-SP-PIFO reduces the performance gap of SP-PIFO by 2.5X.
We have also used MetaOpt in many other contexts such as WAN capacity planning, analyzing machine learning models, analyzing caching algorithms, and many other use cases. We will publish soon.
Who do I contact with questions?
Behnaz Arzani (bearzani@microsoft.com) and Pooria Namyar (Namyar@usc.edu) are the main contacts for the MetaOpt project.