As far as user data is concerned, much is made of the big social media conglomerates like Google and Meta. However, cloud service providers such as Amazon Web Services and Microsoft Azure are the backbone of countless applications, holding the keys to vast amounts of data stored on their servers.
Within those companies, it is the role of cloud operators to be in charge of the systems to make sure they run smoothly. Their responsibilities include managing complex tasks like optimizing data storage and handling virtual machine requests, which often come with varying demands for CPU, GPU, and memory resources.
To support their efforts, cloud operators often employ approximate algorithms called “heuristics” to tackle computationally demanding problems in network management. While efficient, heuristics can underperform under certain network conditions, potentially leading to suboptimal resource allocation, traffic drops, or delays. Existing heuristic analyzers can identify one or a few single instances where heuristics falter but lack the capacity to explain why, limiting their practicality for operators.
To try to solve this challenge, a team led by an MIT CSAIL PhD student has developed XPlain, a tool to augment existing heuristic analyzers and provide operators with a comprehensive understanding of heuristic underperformance.
The potential consequences of heuristics underperforming can directly impact consumers. For instance, one heuristic used in Microsoft's wide area traffic engineering solution had a potential underperformance of 30 percent, meaning the company would need to overprovision networks, drop traffic, or experience delays to compensate.
XPlain focuses on three critical questions:
- Where does a heuristic fall short compared to the optimal solution, and what are the characteristics of the input in those cases?
- Why does the heuristic underperform?
- What can be done to mitigate this underperformance?
To address the first question, XPlain offers:
- Adversarial Input Sets: It identifies all input conditions, for a given problem instance, that lead to suboptimal heuristic performance.
- Generalized Patterns: By extrapolating from specific instances, XPlain uncovers the broader input characteristics and problem traits that consistently cause heuristics to fail.
For the second question, XPlain provides clear comparisons between the heuristic and the optimal solution, highlighting the differences in decision-making.
Finally, XPlain's insights allow operators to take action. By identifying adversarial input sets, they can preemptively mitigate risks—such as caching optimal solutions or switching to alternative heuristics for those challenging instances in production.
PhD student Pantea Karimi describes XPlain as “our vision for a ‘generalizer’ that can augment existing heuristic analyzers and help operators either improve their heuristics (by helping them find why the heuristics underperform) or use them more safely (by finding all regions where they underperform).”
Karimi outlines four key components of XPlain:
- Domain-Specific Language (DSL): A novel DSL based on network flow abstractions enables users to describe heuristics and benchmark algorithms. This DSL facilitates automated analysis, comparison, and explanation of heuristic behavior.
- Adversarial Subspace Generator: This component leverages existing analyzers to identify an initial adversarial input and iteratively expands the search space to discover statistically significant adversarial subspaces.
- Explainer: By comparing the actions of the heuristic and benchmark within each adversarial subspace, the explainer highlights the specific decisions made by the heuristic that contribute to its suboptimal performance.
- Generalizer: This component analyzes instance-based explanations across a diverse set of problem instances to identify general patterns and trends that lead to heuristic underperformance.
The researchers showed the feasibility of XPlain in generating comprehensive explanations for heuristic behavior, including for concrete examples of problems such as traffic engineering and vector bin-packing (VBP). They also showed that the DSL was effective in modeling a wide range of heuristics and that the adversarial subspace generator could successfully identify statistically significant regions of underperformance. The explainer could effectively visualize the discrepancies between heuristic and benchmark actions, revealing the root causes of suboptimal performance.
“The larger goal is to create explainability for heuristics and make it easier for operators to figure out what wrong’s with their heuristic,” says Karimi.
The team says that future research efforts will focus on expanding XPlain's capabilities to support a broader range of more complex heuristics and problem domains. This includes developing efficient mechanisms to summarize complex explanations and make them actionable for operators, and refining the generalizer's capabilities to extract more meaningful and comprehensive insights from instance-based explanations.
“XPlain represents a significant step towards making heuristics safer and more transparent for network operators,” says Karimi. “By providing in-depth explanations for heuristic underperformance, XPlain empowers operators to make more informed decisions regarding heuristic deployment, optimization, and mitigation strategies.”
Karimi co-authored the paper with PhD graduate Solal Pirelli of the École Polytechnique Fédérale de Lausanne (EPFL), assistant professor Santiago Segarra of Rice University, and PhD student Pooria Namyar at the University of Southern California, alongside several individuals at Microsoft Research: senior researchers Siva Kesava and Reddy Kakarla, researcher Ryan Beckett, senior research engineer Beibin Li, and principal researcher Behnaz Arzani. They presented the paper this fall at the Twenty-Third ACM Workshop on Hot Topics in Networks (HotNets 2024).
