Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of finding a network configuration, such that, after applying a routing protocol, the resulting forwarding plane satisfies the given specifications. The proposed method involves encoding the specifications as well as an incomplete configuration (with missing parameters) as a fact graph (with multiple neighborhood functions) and then using a graph neural network model to predict the missing parameters (to complete the configuration). A synthetic dataset is generated for training the model (by first generating the configurations and then a set of specifications satisfying the resulting forwarding planes). This method has been demonstrated to be significantly faster than SMT-based methods (up to 500x faster) and on average satisfies around 93% of the given requirements.
strengths_and_weaknesses: ### Strengths

+ __Graph encoding enables protocol agnostic application.__ The overall technique can be applied w.r.t. any routing protocol since the fact graph encoding used is very general and furthermore, the data generation process only requires the ability to simulate the protocol.
+ __Simplicity.__ The proposed method appears simple and elegant.
+ __Can obtain approximate solutions even for unsatisfiable specifications.__ This aspect is interesting and I believe that it is of practical significance.

### Weaknesses

- __Lack of clarity in writing.__ Although the overall approach seems simple, the paper was a bit difficult to follow requiring multiple passes to understand.
    + Many network-related concepts are not defined, making the paper less accessible to the broader NeurIPS audience. For example, a forwarding plane is mentioned as the output of a protocol without defining what it actually is, mathematically.
    + The graph encoding seems to be one of the primary components of the technique and it is not described well in the main text. A diagram of the graph with different types of edges for the running example will be helpful.
- __Evaluation on synthetic specifications only.__ The primary evaluation is performed on randomly generated specifications. However, this might not capture the distribution of specifications encountered in realistic scenarios. 
questions: + It appears that generating configuration parameters uniformly at random already achieves around 80% satisfaction rate. Is there an explanation for why this is the case?
limitations: Limitations regarding scalability are discussed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a GNN-based method for synthesising network configurations for a given network topology, such that most, if not all, specifications are satisfied.

The authors argue that existing, SMT-based, methods are of limited use, because they are solving an NP-hard problem exactly, and are thus inherently unable to scale to large instances. Since modern-day applications require fast network configuration generation for large networks, the authors propose to instead use an end-to-end, learning-based method to synthesise "good" network configurations, given a network topology and a set of requirements. Here, they relax the notion that all requirements must be met, and instead just aim to have as many of them met as possible. If I understand correctly, the idea is that this can be given to a human who can then adjust the configuration in order to meet all requirements. The authors argue that this is better than a solver that just doesn't terminate, or takes too long.

Futhermore, they argue that their method is protocol-agnostic, in contrast to hand-coded SMT methods, and realise this by encoding protocols using `Datalog`. In addition, they claim that their method can be used for cross-protocol reasoning. They limit their configuration synthesis to generating link weights for the OSPF protocol, and import policies for the BGP protocol, arguing based on the literature that this is a realistic choice.

To evaluate the quality of their synthesised configurations, the authors define the notion of 'specification consistency', which is simply the fraction of the requirements that are met. Their methods aim to find a protocol (e.g., link weights) that maximises this specification consistency.

The authors describe how they generated a training set of $10\:240$ (input, output) pairs, where the input is a topology and a specification of requirements, and the output is a configuration, such that they could train their models.

They evaluate their method primarily on solution quality, reporting averaged specification consistencies, with respect to three forwarding requirements. They do this for network topologies in three size categories, containing up to 153 nodes. They evaluate different sampling strategies for completing partial configurations into full ones. Finally, they evaluate the time needed to get their configurations, comparing that to the time required by an SMT-based exact method: `NetComplete`.
strengths_and_weaknesses: ### Strengths

- As far as I can tell, the method that the authors propose in this paper is indeed a novel way of synthesising network configurations.
- The authors seems to have a decent grasp of how their work is positioned in the literature.
- The many paragraph titles in the text make it relatively easy to find relevant information in the paper.
- The text does not contain many grammatical errors.
- It seems to me that the problem and the proposed solution would be of interest to the NeurIPS audience.
- The experimental evaluation makes sense to me, although I have a couple of comments (see below).
- The results look promising.
- I like that the author explored the performance of their algorithm on unsatisfiable requirements also, as I can imagine that they might occur quite often in real-life, and their method has the benefit of giving the poor human who has to fix it at least some hints at how to do it.
- The authors to some extent explored different hyperparameter settings for their method (in Table 1).

### Weaknesses

- In general, I find that the authors are overselling their work. They use the phrase "radically new method/approach", without really showing what is so "radical" about their approach, but I'm willing to see this as a choice of words used for advertising that I personally find inappropriate, and hence a matter of personal taste. However, there are some more serious cases of possible overselling:
  - The authors state in the abstract that their approach "enables cross-protocol reasoning". This sounds very interesting, so I was excited to read the experimental section to get a sense of how well this works. Unfortunately, I could not find any theoretical or empirical evidence to back up this claim. Maybe they showed it, but it just wasn't clear to me what exactly they mean by "cross-protocol reasoning" (I am not very familiar with computer network configuration)? In that case, the paper would be improved (at least for me) by making this more clear.
  - I find the phrasing "breaking the scalability barrier" also problematic. The authors talk about the "inherent computational complexity" of the synthesis problem, without specifying what that complexity is, except for mentioning that parts of the problem are NP-hard. In addition, they modify the original configuration synthesis problem from a satisfiability problem to an approximation/optimisation problem. Nothing inherently wrong with that, provided that this is well-motivated, but I find that "breaking the scalability barrier" conveys a larger promise than "proposing a method to solve a different problem than the original one".
  - The authors claim in the abstract that the configurations that they synthesise "on average satisfy more than 93% of the provided requirements". However, the way I understand the sentence in lines 244-245, the authors obtain this number by always reporting the best out of five runs of each synthesis task. Maybe I misunderstand their experimental setup, but as I understand it now, it seems somewhat misleading to me. As far as I can tell, the authors do not report in the paper about the quality of the 4 discarded solutions per synthesis task. In a different experiment (Table 3) they seem to pick the best out of 4 runs instead of 5, which seems arbitrary and smells of possible cherry picking to me.
  - The observed speedup of upt to 560x reported in line 280 is somewhat undercut by the fact that the proposed method only has a full match in 2/8 instances for that case. I don't think that 25 minutes is a truely prohibiting time for an SMT-solver to come up with an exact solution, so while this speedup is impressive, I would argue that the goal of speedup is not autotelic, but only makes sense if you are also achieving similar quality results, and/or the original time was prohibitively long.
- The authors argue that the fact that routing protocols can be expressed as graph algorithms motivates their choice to "heavily rely on GNNs/NAR". However, they don't explain very well what GNNs are, and only explain NAR in the last paragraph of the Related Work section, right before the conclusion. It would've been easier for me to understand the points made in this paper if this concept was explained much earlier.
- I honestly have trouble verifying the validity of the experiments, because the experimental protocol is rather opaque to me. I have tried to add some clarifying questions below.

I address the other weaknesses in my questions below.

### Summary

My general impression of the paper is that it is a good attempt at solving a somewhat artificial problem. While fairly well-written, I found it hard to follow, but that is probably due to my lack of knownledge in the are. The experiments seem sensible, but the experimental setup is somewhat opaque to me. My largest issue is with the way in which the findings are presented, which I find somewhat misleading in some cases. Perhaps I am misunderstanding the claims or the methods in this paper, but in that case, it would probably benefit from some editing.
questions: Q1: I am confused by the paragraph in lines 85-91. The way that the configuration synthesis problem is described in lines 21-22 gives me the impression that it's a satisfiability problem: we need a configuration that meets the requirements. Then, in the paragraph in lines 75-84, the authors formulate an optimisation version of that satisfiability problem, which makes sense to me in the context of this work. However, in lines 85-86, they "propose to relax both the optimality as well as the rigid satisfaction requirements", which implies that the original configuration synthesis problem is an optimisation problem. Since understanding the exact problem that you are trying to solve is quite crucial, it would be great if the authors could clear this up for me and explain what they mean by the sentence in lines 85-86?

Q2: What exactly do the authors mean by "cross-protocol reasoning", and do they have any theoretical or empirical evidence that their method does indeed enable cross-protocol reasoning? If yes, (how) did they present it in the paper? If they did not present it in the paper, why not? If they do not have the evidence, can they please clarify what justifies this claim?

Q3: The authors mention computational complexity as a limiting factor for any method that aims to synthesise network configurations. Can they specify what that complexity is?

Q4: If I understand correctly, the authors have 3x8 = 24 instances, and they do synthesis for 4 different traffic classes each, and then with 2, 8 and 16 requirements per specification fact? So they have a total of 3x8x4x3 = 288 synthesis tasks. Is that correct? As I understand it, the authors then run the synthesiser 5 times, and report the configuration with the highest overall consistency, which I guess means averages over the `fwd`, `reachable` and `trafficIsolation` forwarding requirements? Am I correct in my understanding that for each of these 96 synthesis tasks, the authors did 5 runs and reported on the quality of the best run? If no, could the authors clarify this matter for me? If yes, could the authors report on the qualities of the other runs?

Q5: It seems that the authors assign the same weight to all the requirements. Since they propose essentially an optimisation method, for which we can measure the quality of the solution, I am wondering if the authors considered how realistic this is? They seem to expect a human to finalise the configuration to something that satisfies all requirements. I can imagine that some requirements are easier for a human to meet than other, so maybe some requirements could/should have less weight than others? I missed any reflection on this. Maybe the authors can clarify?

Q6: The choice to run the algorithms for 25 minutes seems strange to me. I could understand 15 minutes, I could understand 30 minutes, but 25 minutes smells a bit like cherry picking to me. Can the authors motivate this choice?

Q7: This may be just a gap in my knowledge, but what is a "strong inductive bias"? The authors mention it a few times and it seems important, but it is not clear to me what it is.

Q8: Can the authors explain why it is so important that their method does not rely on reinforcement learning?

Q9: Line 272-273: "We compare both BGP/OSPF and OSPF-only synthesis time. My first question is: why? My secon question: I don't see that reflected in the table, how should I read the table to understand it?

Some smaller remarks:

- line 15: 'resp.' Why 'resp.'? It doesn't make sense to me in the sentence structure.
- line 18: "Figure 1 - here" -> "Figure 1. Here"
- line 31: "inherent computational complexity" I find this statement rather unconvincing without specifying what that computational complexity is.
- line 36: "relaxing" -> "to relax"
- line 36-37: "to admit approximate solution with high utility -- configuration which may not always satisfy all requirements" I cannot parse this sentence, could you please rephrase?
- line 71: is the second $i$ subscript a typo?
- line 130: "the same destination" which is ...?
- line 134: "the decision cannot eliminate" I'm confused at the concept of a decision making decisions.
- line 138: "the left" do you mean "the right"?
limitations: The authors did not discuss any potential negative societal impact. I don't think that their work would have any, so I wouldn't hold this choice against them.

As for other limitations: the authors describe how they modified the original problem and proposed a method for solving that modified
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors put forward a novel method to automatically reconfigure computer networks. Their main contribution is to relax the notion of an acceptable configuration to account for the cases where only an approximation is possible. The latter case is chosen so that various learning techniques can be applied.

The main contributions of this work are: A relaxation of the configuration synthesis problem, that admits a scalable approximate solution, and the introduction and training of a neural network that generates configurations likely to satisfy the approximate guarantees mentioned above, in a *scalable* fashion (this latter point is what makes this work interesting).
strengths_and_weaknesses: Originality:
This paper seems original. Although there exists some prior work on automating network configuration by using a variety of synthesis techniques, this work seems to be the first to present a trade-off between the accuracy of the chosen configuration and the speed of configuration. Moreover, this work seems to be the first in using learning-based techniques in the context of automating network configuration (in contrast to previous work, where SMT techniques are predominantly used).

Quality:
The quality of the paper is high, in my opinion: It is well written and the results seem strong.

Clarity:
Presentation of the paper and writing are clear, in general. I believe that Section 1 could have been written in a more reader-friendly way, especially to account for the case where the reader is not an expert and may not be familiar with SMT solvers, etc. (Could you please make this part a bit gentler?)

Significance:
This work is significant in my opinion; see Originality above.
Another reason I find this paper important is the scalability of the proposed neural network solution.
questions: Can you please make Section 1 a bit more reader-friendly? Thanks!

Throughout the paper there is a lot of undefined technical jargon (OSPF, BGP, etc) :) Could you please amend this?

Could you please explain Figure 1 a bit further?
limitations: In my opinion, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper is concerned with the problem of finding a computer network configuration given a topology and a set of routing requirements. 
Instead of relying on traditional Satisfiability Modulo Theory (SMT) approaches, the proposed approach builds upon recent advances in approximating computationally hard decision problems with Graph Neural Networks (GNNs). An advantage of the proposed technique lies in its protocol-agnostic nature: in principle, it can be used to configure any protocol that can be reduced to a message-passing computation over the network.
After training, the model is able to efficiently generate configurations that satisfy the requirements with high probability. 
strengths_and_weaknesses: The paper is generally well-written and the proposed approach makes sense to me. While many papers aim at solving with GNNs more general decision or optimization problems, such as SAT or (weighted) model counting, I think it makes sense to introduce in the learner an inductive bias for solving specific real-world problems. I found interesting the realization that routing protocols can be cast as message-passing algorithms, thus their (approximate) configuration is amenable to GNN-based approaches.

I wish that some aspects were more formally defined and I struggled with understanding the rationale for embedding the different inputs into a single latent space.
Most importantly, I think that the experimental section should be improved in order to show the usefulness of the approach in real-world settings (see detailed comments below).

---

**Main comments**

---

I don't understand the advantage of mapping different inputs
(topology, specification and configuration sketch) into a single
embedding space instead of treating them differently. As the general
trend is aiming at finding semantically disentangled latent spaces,
mixing together in the same latent space facts related to the topology
and information on the protocol seems suboptimal. Can you elaborate on
this algorithmic choice?

---

"To remain agnostic with respect to routing protocols, our model
architecture implements a generic graph-based encoding of Datalog-like
facts"

Probably, adding a figure depicting the resulting graph for a small
fact-base would significantly help understanding the proposed
approach.

---

I wish that some archtectural choices were discussed in detail
and motivated.  For instance, what is the added benefit of having
GATs? Is adding a Gaussian noise to the input encoding a standard
practice when multiple solutions to the optimization problem exists?
Have the authors performed ablation tests for validating these choices?

---

On the experimental section:

- It is not clear whether the proposed model generalizes to larger
   topologies. This is is a pivotal aspect, unless the model can be
   effectively trained on real-world topologies with "millions of
   nodes".

- The benchmarks only include very small topologies. I get that the
   SMT-based approach doesn't scale to large topologies. Nonetheless
   Table 2 could show the average consistency of the generated
   configurations for much larger networks. After all, this is the
   whole point of approximating the problem with neural networks.

- Besides a comparison of the proposed approach with a SMT-based
   configurator, no alternative is considered. Why not reporting
   ablation studies for different architectural choices? These preliminary results are suggesting that GNN-based
   techinques can be used to approximate this complex optimization
   problem, not that the proposed approach and architectural choices
   are particularly well-suited for the task.

- The fact that the approach is protocol-agnostic seems one of its
   strongest selling points (see abstract), but in the experiments
   only a couple of protocols are considered. Plus, both protocols
   were already encoded in SMT. Are there protocols that are out of
   scope of (or currently not supported by) SMT-based methods? Adding
   additional experiments with more protocols would strenghten this
   aspect.

---

**Minor points**

---

In my opinion, the formal description of the problem in Section 2 could be improved:

- It is not initially clear what FWD is from a mathematical viewpoint. Figures 1 and 2 clarify that it can be represented as a graph, but I would mention it in the text anyway.

- It is initially mentioned that the topology T is fixed in the
  configuration synthesis task and it is thus omitted in the following
  equations, but it is reintroduced after line 98. In the same
  equation, Prot is not mentioned anymore. I get that the proposed
  approach to synthesis is protocol-agnostic, but that doesn't seem to
  be the case in general (e.g. with SMT-based approaches). It feels
  like the description of the task is mixed with specifics of the
  proposed approach.


---

- While I tend to like papers with many examples, I don't see the
purpose of 'Example intuition' at line 126. What is exactly the
intuition it should convey? Is it really functional to understanding
the contribution? On a side note, it also feels unnecessary for people
who know BGP and OSPF already, while being too vague to really help
understanding how these routing algorithms work.

---

"$D_2^{connected}∶ \mathbb{R}^D → \mathbb{R}^\mathbb{N}$"

- What is the subscript 2 indicating? I guess the superscript
$\mathbb{N}$ (typically referring to the set on natural numbers) is a
typo? Also, how is this output a distribution over configuration values?

---

"A learning-based synthesizer model is formulated as a simple
input-output mapping."

- I don't understand the sentence. I guess is that you cast the network
configuration given the topology as a supervised learning problem.

---

"Based on the observation that routing protocols such as OSPF and BGP
can be expressed as graph algorithms"

- I would write 'message-passing algorithms'.
questions: 1- What is the rationale for encoding everything (topology, configuration parameters and requirements) in one fact graph and embedding it into a single latent space? 

2- Can your technique be applied to much larger topologies than those seen during the training?

3- How does your techique perform on topologies with thousands of nodes?  

4- Have you considered different GNN architetures in your experiments?

5- Have you tried configuring protocols that are out of reach of the SMT-based configurators?
limitations: As mentioned above, I wish that the paper clarified how the proposed approach generalize after training to larger problems, since this is is crucial for applying the proposed technique to large, real-world networks.
review_title: null

Meta-review: metareview: The reviewers found the approach proposed in the work to be novel and reviewers find the work to have promise. The reviewers also felt that it would be best for authors to present a detailed analysis on the scalability limitations and we are confident that authors would do so in the final version. 
confidence: Certain
Decision: Accept