Learning to Configure Computer Networks with Neural Algorithmic Reasoning
Authors: Luca Beurer-Kellner
Martin Vechev
Laurent Vanbever
Petar Veličković
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural algorithmic reasoning
computer networks
configuration synthesis
graph neural networks
systems

Abstract: We present a new method for scaling automatic configuration of computer networks. The key idea is to relax the computationally hard search problem of finding a configuration that satisfies a given specification into an approximate objective amenable to learning-based techniques. Based on this idea, we train a neural algorithmic model which learns to generate configurations likely to (fully or partially) satisfy a given specification under existing routing protocols. By relaxing the rigid satisfaction guarantees, our approach (i) enables greater flexibility: it is protocol-agnostic, enables cross-protocol reasoning, and does not depend on hardcoded rules; and (ii) finds configurations for much larger computer networks than previously possible. Our learned synthesizer is up to 490x faster than state-of-the-art SMT-based methods, while producing configurations which on average satisfy more than 93% of the provided requirements.  

Learning to Configure Computer Networks with Neural Algorithmic Reasoning
Luca Beurer-Kellner Martin Vechev!
Laurent Vanbever'
Petar Veličković"
ETH Zurich, Switzerland
DDepMiind
http:://ggaaabb.comm/ccssssrs/rr network
Abstract
We present a new method for scaling automatic configuration computer networks. The key idea is to relax the computationally hard search problem of finding a configuration that satisfies a given specification into an approximate objective amenable to learning-based techniques. Based on this idea, train a neural algorithmic model which learns to generate configurations likely to (fully partially) satisfy a given specification under existing routing protocols. By relaxing the rigid satisfaction guarantees, our approach (i) enables greater flexibility: is protocol -agnosoi,gg,,ttic, enables cross-protocol reasoning, and does not depend on hardcoded rules; and (ii) finds configurations for much larger computer networks than previously possible. Our learned synthesizer is up to 490x faster than state-of th-thr- SMT-based methods, while producing configurations which on average satisfy more than 92% of the provided requirements.
Introduction
Configuring large-scale networks is challenging and important task as network configuration mistakes regularly lead to massive internet-wide outages affecting millions (resp. billions of Internet users [35] 25 Typically, network operators provide router-level configuration W which, after applying protocols such as shortest-path routing, induces a certain forwarding behaviour FWD illustrated in Figure As this remains challenging task, much recent research has focused automating configuration by leveraging synthesis techniques [I5] 5 31]: A synthesizer is used to automatically generate router-level configuration W that, after applying routing protocols results in forwarding behavior that satisfies a given specification on how traffic should be routed.
SMT-based Synthesis Due to the hardness of the configuration synthesis problem 77. many effective tools in this domain 15 [4 employ search-based procedures to find a solution to a set of first-order logic constraints. This enables comprehensive and exact synthesis by modelling network behavior in first-order logic. However, these tools are typically protocc--specific, hand-coded, and can exhibit discrepancies in behavior when compared to actual router hardware [6] Most importantly, however, they can be very slow or fail to complete for large networks. For example, the state-of-the-art SMT-based tool NetComplete [5] requires more than 6 hours to synthesize configuration for a network with 64 nodes, for which other SMT-bbased tools like SyNET [4] take even longer (> 24 hours) [15]. Con-SMT-baseed tools
resort satisfiability modulo theory (SMT) solvers, which
such as Propane or Zeppelin 39 have achieved better performance, but at the cost generality.
"Correspondence to luca. As of 2021, Facebook reportedly has 2.9 billion monthly active users i|
.ttz.. ch.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Forwarding Plane
Protocol
Configuration W (Graph Algorithm, c.g. OSPF)
FWD
Check Consistency
Specification S
C(FWD,
Prot
not (e.IC_0.011
reachable tsolasionn
Configuration Synthesis (exact, approximate)
Figure 1: Network configuration synthesis. The goal of configuration synthesis is to find configuration W that maximizes consistency C(FwD, 8) for given specification S.
Addressing the scalability barrier The reason for the wide-spread use of SMT in configuration synthesis is the inherent computational complexity of the underlying synthesis problem, parts of This means that any exact synthesis method is bound to run into scalability issues (as do all SMT-based methods). However, to be practically useful, synthesizer must scale to the size of real-world networks and the frequency at which configurations are updated. For example, in a Tier- ISP, network operators modify their configurations up to 20 times per day, on average [36]. We argue that one way to address this scalability barrier, is relaxing the configuration synthesis problem to admit approximate solutions with high utility configurations which may not always satisfy all requirements
which have been shown to be NP-hard 16 44
given specification but may satisfy almost all of them. Such configuration would be a much better starting point for network operator than having no automated support whatsoever. The core technical challenge then is coming up with a strategy likely to find solutions with high utility.
This Work: enabling fast and scalable configuration via neural algorithmic reasoning We address this challenge and present the first learning-based framework for approximate configuration synthesis. Our relaxed formulation allows us. for the first time, to apply end-to-end learning to the problem of network configuration synthesis, thereby enabling fast and scalable configuration synthesis with almost interactive response times (<90s even for large networks). Technically, leverage the observation that routing protocols can often be formulated as Bellman-Ford style graph algorithms, class of problems that has recently been studied in the area of neural algorithmic reasoning (NAR) (43. Connecting the two fields and building on ideas from NAR, we are able train graph-based neural model with strong inductive bias to learn an inverse mapping from specifications back to network configurations: Our model learns how to perform synthesis from dataset of (specification, configuration) pairs obtained by simulating the involved protocols and observing the computed forwarding state. With this method, we can support cross-protocol reasoning and do not have to manually provide any hardcoded synthesis rules. Concretely, we introduce generic embedding scheme for topologies and configurations, making our method protocol- aggosticc During synthesis, given a specification, our model predicts distributions of network configurations from which we can sample possible results.
Main Contributions Our core contributions are:
We formulate relaxation of the exact configuration synthesis problem, which enables fast and scalable network configuration, amenable to learning-basse based techniques (Section 2).
We propose NAR-based neural network architecture for learning synthesizer models that rely on a graph-based encoding of topologies and configurations, and a strong inductive bias towards an iterative synthesis procedure (Section 4
We conduct an extensive evaluation of our learning-based synthesizer with respect to both precision and scalability. We demonstrate that our learned synthesizer is up to 490x faster than a state-of-the-ar SMT-hased tool while producing high utility configurations which on average satisfy 93% of provided constraints (Section 5).

---

2
Configuration Synthesis: Exact and Learned
We first state the general configuration synthesis problem and explain why it is hard to solve. We then present a rather different approach based on learning that addresses the scalability barrier of traditional synthesis.
Forwarding Behavior and Specifications We focus on the level of the forwarding plane of a network. This means we consider how a network forwards traffic, given a packet with a certain destination. The forwarding plane is determined by distributed computation that depends on the different routing protocols use. More formally, we define the forwarding plane FWD as follows:
FWD == Pro
Pro((W; (T) corresponds to the result of applying routing protocols to the network topology T and the configuration W (e.g. link weights). In the following, we omit T as remains fixed synthesis. The resulting forwarding plane FWD can be understood as directed graph superimposed on topology T. It specifies a subset of links that are used to forward packets. To illustrate consider Figure applying the routing protocols yields forwarding plane FWD which corresponds to the subset of links (C,A), (B,A) A), (A, E). (D, F). The other links of the network are not part of the forwarding plane and will thus not be used to forward traffic.
Given FWD, consider forwarding specification S := {Ra y as input to the synthesis problem. Each requirement in S is modelled as a function R,, where R, (FWD) = 1 if FWD satisfies the requirement and 0 otherwise. Practical example requirements include reachability, traffic isolation specifying concrete forwarding paths.
Exact Configuration Synthesis following optimization objective:
We formulate the general configuration synthesis problem as the
W arg max C(Prot(W).S) where C(FWD, S) ER,s R&(FWD) WeP(W)
(1)
|S]
P(W) denotes the set of all possible configurations and C(FWD, S) is the specification consistency of a forwarding plane FWD w.r.t specification objective is solved by limiting the search to globally-optime configurations such that C(FWD, 1.0, i.e. all requirements must satisfied. Such exact methods typically resort to SMT solvers because of the hardness of the underlying problem: configurations comprise a large number of tunable parameters, where the execution several interacting protocols yields the overall forwarding state. Even worse, parts of the configuration synthesis problem have been shown to be NP-hard [7] 16 44); For example, already the subproblem of finding link weights that yield a given set of forwarding paths under shortest-pait -oott routing is NP-hard [7]. This makes scaling exact synthesis to real-world networks extremely challenging.
traditional, exact configuration synthesis, this
Searning-Based Synthesis To enable fast and scalable configuration synthesis, we propose to relax both the optimality well the rigid satisfaction requirements w.r.t the specification S. Concretely, we relax the set of admissible solutions to include configurations that are not optimal, but still satisfy large number of provided requirements. Note that this is not the same merely allowing solutions with C(FWD, S) < 1.0, because maximum satisfiability does not relax the hardness the problem. Instead, we propose to search for near-optimal, good solutions and rely on the value of specification consistency C' as a measure of quality.
An approximate synthesis formulation relaxes the hardness the problem, however, it also leads to the difficult technical challenge of finding solutions with high utility (c.g.. where many requirements are satisfied). To address this challenge, we propose a rather different approach where we learn synthesis from data. Concretely, we learn inverse mapping that attempts to predict approximate solutions W with high utility, as guided by the following objective:
(FWD) s.t. C(FWD, is high W Prot (FoDD
This can be implemented as a synthesizer model Msyn which produces solution given just the topology T and the specification S:
3

---

Physical
BGP Session
External Router
Internal Router
L.:
LP:22
LI::
AIP:
Round 1
Round 2
Final
Forwarding Planc
Figure 2: An illustration of propagating BGP route announcements in a small network, including internal peers (blue), external peers (purple), BGP sessions well as physical links. The last graph illustrates the resulting forwarding plane after applying BGP/OSPF.
W Msym (S;
We propose a learning-based based approach for training such synthesizer models based on neural algorith- mie reasoning (cf. Section D. First, however, we discuss the routing protocols that make up function Prot and how they relate to graph algorithms and by extension to NAR.
3 Routing Protocols as Graph Algorithms
In practice, the routing protocols defining Prot are implemented distributed systems in which multiple peers communicate to determine the network's s forwarding state. However, theoretical work on routing algebras [2 has shown that the underlying computation pesssage-passing graph algorithm. As a consequence, many routing protocols can be formulated as Bellman-Ford (BF) style propagation processes. This class of problems has also recently been subject to work on NAR [43 41] and algorithmic alignment [45). The authors of these works demonstrate that neural networks are capable of closely imitating BF-style algorithms when provided with a suitable inductive bias. Based on this insight, NAR proposes to replace traditional algorithms with neural networks to learn improved algorithmic procedures or extend existing algorithms to be applicable to raw data [41]. Following the idea of NAR, we implement a synthesizer model for network configurations as an iterative Graph Neural Network (GNN) learn Prot-1 by relying on a Bellman- Ford style inductive bias.
be understood as a traditional
Synthesis Setting Our approach is general for the domain of networks, but we focus on two widely-
used routing protocols: (1) Open Shortest Path First (OSPF) 30 - it uses link weights to route traffic along the shortest path towards the destination, and the (2) Border Gateway Protocol (BGP) (32), used to exchange reachability information, mostly on the level of larger backbone networks. When using BGP, a routing destination announces its existence to other networks and routers by sending out BGP announcements. Receivers of announcements then choose to pass them on to other peers, redistribute them internally and/or modify them according to a set of decision rules. BGP and OSPF interact, for instance, BGP will consider the OSPF cost of internal destinations in its routing decisions. This means, that effective BGP/OSPF synthesis tools must implement cross-protood reasoning, configuring BGP and OSPF, such that together they yield the desired forwarding behaviour.
Example To provide basic intuition about BGP/OSPF routing, consider the simple example network in Figure 2 We apply the two protocols to obtain the forwarding plane. Physical OSPF edges are labelled with corresponding link weight determining the OSPF cost of paths through the network. Dotted lines represent designated BGP edges, used to propagate BGP announcements. Our network imports multiple BGP announcements and from and respectively. Both represent route to the same destination. As shown, the announcements have so-called BGP local preference of 2 (we ignore other BGP properties this example). The announcements are propagated through the network and the best route is selected according to designated BGP decision procedure. Figure 2 shows the intermediate states of this propagation process. As both announcements have the same local preference value, the decision cannot climinate based on that. Instead, in round 2, node B

---

4x
F
Distribution Syuthesized
Parameters
IBC
Masked Input
Embedding
Fact Base Graph
Encoder GNN
Latent Synthesizer
Processor GNN
Latent
Fact Base
Synthesizer
Input
Output
Argument
Decoders
Figure 3: Neural synthesizer architecture. A provided input fact base is first embedded graph including the masked to-be- co-be-synthen be-syythesized parameters. Then encoder GNN, processor GNN and decoder networks are applied to obtain distribution over synthesized parameters.
selects over due lower OSPF cost (shorter path) of 2 via node A compared to 3 via node D. Node D selects A over since it learns this route directly from an external peer which is preferred stable state and we can derive
BGP, After Round 3, the BGP propagation process converges the forwarding plane as shown on the left in Figure 2 For completeness, we include the full BGP decision process in Appendix A.33
Configuration Parameters For our purposes, we define the set of synthesized configuration parameters as follows: For OSPF, we synthesize link weights as explored in existing work [6] For BGP, we focus on setting, where we synthesize BGP import policies only. This means we synthesize the modifications required for BGP announcements when entering the network, to satisfy the routing specification. Previous work has confirmed that this is a realistic configuration setting that applies majority of real-world networks 9 38)
Based on the observation that routing protocols such OSPF and BGP can be expressed as message-passingg algorithms, we heavily rely on GNNs/NAR for the design of our synthesizer model as discussed next. In our evaluation, we then train such model for the concrete case of BGP/OSPF and compare synthesis performance with a traditional SMT-based tool.
4 Neural Configuration Synthesis Model
We train a graph neural network (GNN) as the neural synthesis configuration model. The model's input consists of a topology, a specification, and configuration sketch where oo-be-synthesized parameters are omitted. Following the NAR paradigm, we first encode this synthesizer input in latent space. Then, we apply an iterative processor network based on the graph attention mechanism [42] Last, apply a decoder network to predict the values of omitted configuration parameters, thereby synthesizing a configuration.
remain protocol-agnostie our model is generic with respect to the input format, using an intermediate representation based on Datalog- facts. Figure provides an overview our graph-based neural synthesizer architecture.
4.1 Training Dataset of Inverse Pairs
sarming-based synthesizer model is formulated as a supervised learning problem. Thus, we can directly train neural network to learn the inverse mapping, given dataset of corresponding input-output pairs. To obtain such dataset, we sample random network configuration for some topology using uniform generative process. Then, we simulate the involved protocols using Prot, to obtain the corresponding forwarding plane. Next, we extract a specification by randomly selecting properties that hold for the computed forwarding plane. This leaves us with pair of specification and topology as input, and a corresponding configuration as output.
The key to constructing the dataset is the implementation of Prot. Even though Prof is protocol- specific, it turns out the overall implementation effort is comparatively low, especially when compared SMT-based synthesis methods. Protocols are well-defined algorithms that can be easily simulated, whereas the alternative of implementing hardcoded synthesis rules directly often requires expert
5

---

router (A) router (B)
network (N1) bgp_route (E, .,,,2,2.3,,.011
(...)
fwd (A (A, ,N) not fud (B, A,,,,,,, M1) (...)
NN)
conn (A, 22) conn (A, ,) (...)
Figure 4: A fact base encoding a network's topology, parameters such as link weights (conn facts) and specification (fwd facts).
Graph
Node Features
Fact Base
route:(A)
.con
h
emb(router) = rosset
router(B)
h
= (ombte) = V Vintter
netwozk(NNtt))
loter
(embbbewwrk))
Verwork
router
(..11)
emb( -embb 12)
conn(A, Iwd(A, Net:)
V Vonn + W Weanng onehhol
Not:
h/wd/A.B.Net)))
= emb(faude Viwd
Figure 5: An example of embedding a simple fact base using our generic graph embedding scheme. Different neighborhoods are indicated as edge labels 0, 1 2. The full set of structural embedding rules provided in Figure 6 Appendix A.1 We mark nodes and facts relating to topology, specification and configurations in color.
knowledge of SMT solvers. This process may also be adapted rely on actual router hardware to compute the result of Prot, thereby capturing real-world behavior precisely.
4.2 Embedding Topologies, Specifications and Configurations
To remain agnostic with respect to routing protocols, our model architecture implements a generic graph-based encoding of Patalog-like facts, similar to knowledge graphs [33]: first encode topologies, configurations and specifications as a set of Datalog like facts and then employ generic embedding scheme embed these facts into latent space.
of Datalog-like facts, as depicted in Figure serves the input fact base F to our synthesizer model. F is set of facts (ao...... an) where arguments may be constants (e.g. A or B) or integer literals. Each fact has corresponding boolean truth value denoted as [f[a]]. For instance, from the fact base in Figure we can derive [fwd(AA (A, B, N1)]s true and A, false.
Fact Base
Synthesis as Completion Task A network's topology, protocol configuration, parameters, and the specification are all represented in single fact base. To predict the value of unknown, to-be- synthesized parameters, we support the notion of unknown parameters as illustrated at 1 in Figure 4 where the link weight between router nodes and is omitted. Based this input format, synthesis corresponds to using our model to predict the value of unknown parameters provided fact base.
Embedding To transform a fact base into a graph with node features, apply structurally-defiee embedding scheme. An example of this embedding scheme is given in Figure As shown, embed topology. specification and configuration all into single graph. This places network routers, the related specification predicates as well as configuration parameters in close adjacency to each other, simplifying the synthesis procedure for the processor network. In our scheme, both facts and constants are represented as distinct nodes. The relationships between facts and constants are encoded node adjacency defined by neighborhood functions N,. We use multiple neighborhoods, i.c. multiple types of edges, to encode the argument position of a constant occurring in a fact. To handle unknown parameters, Overall, the embedding function EMB relies on a set learned parameters, including Ve IR per fact type in F, Wboc Dx2 for boolean values, W. IR DxN per integer argument of fact type and V hole IDP to represent unknown parameters, D is the dimensionality of the latent space and N
replace the corresponding embedding with learned Vhole embedding.

---

Table 1: Average consistency with 3x 16 BGP/OSPF requirements, sampling configurations randomly from uniform distribution and multi-shot sampling using our synthesizer model.
Random
1 1-Shot
4-shot
8-shot
Small
0.87+0.11
0.94=0.04
0.95
0.95=0.04
Medium
0.81+0.10
0.96=0.04
0.96+0.04
0.96=0.04
Large
0.80+0.05
0.93=0.05
0.93+0.05
0.94=0.05
specifies the number of supported integer values. For the complete embedding scheme, please see Appendix(A.1 A.I
4.3 A NAR-based Synthesizer Model
Our synthesizer model employs an encode--rocess-eecce architecture, inspired by neural algorithmic reasoning [4]]. It employs four main components to produce the output distribution for an unknown parameter in a fact base F: The fact base embedding EMB, the encoder ENCGAT, the processor PROCGAT and the fact-type specific decoder network DEC,.
Overall, the model can be expressed as follows, where Xj and H, refer the intermediate node representations per node in the graph constructed via our fact base embedding.
X, == ENCGAr(EMB(F)); + where z~ 10,(0,1)
H == PROCGAT((X:)).
O
115(ao Is(ao.....a a.........) softmar (DEC) (H)))
ENCGAT is a GNN relying on Graph Attention Layers (GAT) 42 for propagation. We additionally apply noise to the latent node representation Xj via z as a source of non-determinism. anticipating the fact that the synthesis problem often has more than one solution. The processor PROCGAT is modelled as an iterative process. It consists of a 6-layer graph attention module which we apply for total of 4 iterations. According to the NAR paradigm, this computational structure encodes an inductive bias towards an iterative solution to the synthesis problem.
In the encoder and processor GNNs, we rely on a composed variant of the graph attention layer as introduced by 42 We employ multiple graph attention layers in lockstep, one per neighborhood N; defined by our graph embedding (cf. Section 4.2) and combine the intermediate results after each step by summation. For details on the graph attention module, please refer to Appendix A.2
Finally, an argument decoder DEC,, used, to produce the output distribution Of (ag...... .............) for an unknown parameter at position i of fact fy E F, corresponding to node j. For this, the synthesizer model provides one decoder per integer argument, per supported fact type. For example, model for the fact base in Figure 4 would provide a decoder network D R R-V to decode values for the third argument of conn fact. Decoder networks are implemented as simple multi-layer perceptron models.
Supervision Signal During training, we mask all fact arguments that represent to bo-be-synthesized configuration parameters in our synthesis setting as unknown parameters. As a supervision signal we use the masked values as the ground-true -ruth and apply a negative log- likellodd loss to the output distribution of the corresponding argument decoder networks.
Multi-Shot Sampling To sample values from the output distributions of unknown parameters, we apply a multi-shot sampling strategy. We sample values only for subset of unknown parameters, insert them in the input fact base and run the synthesizer again. We repeat until no more unknown parameters remain. This multi-shot strategy allows the model to incorporate concrete values of previously synthesized parameters in its computation. our evaluation, we compare this approach to sampling all parameters at once.
Evaluation
In this section, we assess the performance our model trained BGP/OSPF synthesis. For this, trained synthesizer model on dataset of 10, 240 samples, constructed by randomly sampling
7

---

Table 2: Average specification consistency of our synthesizer model, where standard deviation is reported with respect to the different topologies in a dataset. We apply the model to synthesis tasks with 3 x N requirements, i.e. N requirements per supported specification fact.
Dataset
rod
reachable
trofficlsolation
Overall
Full Matches
90% Matches
3 x
S
0.97
0.94
1.00
0.07
6/8
6/8
0.95
0.94
1.00
0.94=0.08
L
0.92
1.00
1.00
0.94=0.06
4/8
4/8
3 x
0.98
0.98
0.91
0.96=0.05
M 0.97
0.98
1.00
0.98=0.03
4/8
8/8
L 0.96
0.92
0.97
0.95=0.03
1/8
8/8
x 16
S
0,98
0.92
0,95
0,95=0.03
2/8
8/8
M
0,95
0.95
0,98
0.96=0.04
3/8
7/8
0.94
0.91
0.95
0.93=0.05
1/8
6/8
topologies, corresponding specifications and BGP/OSPF configurations as described Section 4.1
For details BGP/OSPF dataset generation and training, please see Appendix |A.3 Lastly, we also evaluate our architectural design decisions in an ablation and parameter study in Appendix
Dataset, Metrics and Experimental Setup We compare using datasets Small (S), Medium (M), and Large (L). Each dataset comprises real-world topologies taken from the Topology Zoo [29]. where the number of nodes lies between 0-18, 18-39, and 39-153, respectively. To obtain random forwarding specifications we use the same generative pipeline as discussed in Section 4.1 Regarding forwarding requirements,
implement support for three specification facts: fwd requirements to set/block forwarding paths, reachable to specify reachability and trafficIsolation to induce traffic isolation among traffic classes (no shared links). In each topology, we do synthesis for different traffic classes (routing destinations) at a time. Overall, this results in datasets 8 topologies per dataset x differently-sizz specifications 72 synthesis tasks. To assess synthesis quality, we determine specification consistency as the relative number of specification facts in fact base that are satisfied by the synthesized configuration. We run all experiments on an Intel(R) 19-9900X @ 3.5GHz machine with 64GB of system memory and an NVIDIA RTX 3080 GPU with 10GB of video memory.
5.1 Synthesis Quality
To assess the quality of synthesized network configurations, we examine specification consistency with increasingly large topologies and specifications. For each synthesis task, we run our synthesizer times using 4-shot sampling and report the network configurations with the highest overall consistency. Table documents the results. On average, our synthesis model achieves 93% specification consistency for all datasets and specifications. With few requirements, the synthesizer model even succeeds in producing fully-consistent configurations (cf. Full Matches in Table 2). We observe a slight decrease in consistency with increasingly large topologies.
Multi-Shot Sampling To determine the effect of muulti-shot-samplingg we report consistency when using 1-shot, 4-shot and 8-shot sampling in Table [ As baseline, we also show consistency when sampling configurations from a uniform distribution (per parameter). This simple method can achieve suprisingly good results, as parts of a specification may be satisfied naturally by the mechanics of shortest-path routing. Still, competing with this baseline our synthesizer model shows clear improvements and multi-shot sampling further increases consistency.
Number of Samples We also consider the number of times we sample from our synthesizer model. We observe that sampling more than one alternative configuration can lead to improved best-of specification consistency across all datasets. Based on this observation, we boost synthesis peformance by sampling multiple times per synthesis task. For each configuration that we obtain this way, we simulate the routing protocols, obtain the forwarding plane and check specification consistency. This fully automated process allows us to determine the best result without consulting the user. We select the best result as the overall output for synthesis, dismissing the other samples. We experiment how the number of times we sample affects the resulting consistency in Appendix B
8

---

Table 3: Comparing consistency and synthesis time of our method (Neural) with the SMT-based
NetComplete. The notation To indicates the number of timed out runs out of (25+ minutes).
# Requirements
NetCompletc (8)
Neural CPU (s)
Speedup
Consisteney
Full Matches
reqs.
S
18.07 14.55
0.72
25.2x
0.97
7/8
33.39
3.18sa4.32 24.25s+28.35
19.1x
0.94
6/8
L
1389,48 us TO TO
57.3x
0.99=0.03
7/8
reqs.
S
247. 247.69s=436.90
1.25s
198.7x
0,96=0.08
6/8
M
>25m s2 TD
4.55
329.8x
0.97=0.04
4/8
L
>25m sz
31.28s428.53
48.0x
0.97=0.05
5/8
16 reqs.
S
231668852235.5:: To
2,88s= 1,66
492.0x
0.92=0.06
1/8
M
>25m ss
6.53s=5.10
229.8x
0.95=0.05
2/8
I.
>25m TO
87.99s 141.97
17.0x
0.95=0.03
2/8
Overall, sampling more than once is beneficial for all datasets, Average best consistency values appear be reached after 4-5 samples for 16 BGP/OSPF requirements. Hence, we rely on 5 samples in all other experiments as trade-off of fast synthesis time and good specification consistency.
Unsatifiable Specifications practice, network operators may sometimes provide unsatisfiable specifications. While exact methods will typically return an error for such inputs, our relaxed setting enables to consider partial solutions, i.e. configurations that still achieve high specification consistency while ignoring unsat requirements. This may be preferable in some scenarios, especially when perfect specification consistency not critical anyway. To simulate this scenario, we evaluate specification consistency for OSly-only synthesis tasks, which were all verified to be unsatisfiable using the SMT-hased synthesizer NetComplete [15]. We still observe a comparatively high average consistency of 0.90 for our learned synthesizer. This suggests that our model is indeed capable of handling unsatisfiable specifications, while still producing good, partial solutions. For more detailed unsat results and methodology, see Appendix B.2
5.2 Comparison to SMT-based Synthesis
We compare the synthesis time of our learned synthesizer with the SMT-based. state-of-art con- figuration synthesis tool NetComplete [15]. We compare BGP/OSPF and OSPF-only synthesis time. For each topology/ppecificttion, using 4-shot sampling, whereas for consistency we report the best out of the 4 runs. If a fully consistent configuration is found, we do not continue to sample and only report time until then. For NetComplete, we time out at 25 minutes and report that as lower bound exceeded. We restrict comparison to specifications that only include forwarding paths (i.e. fwd facts), as the type of supported requirements in NetComplete does not fully align with our model.
report the total time of rumning our synthesizer 4 times
Table 3 shows that our synthesizer model outperforms NetComplete by multiple orders of magnitude. We observe speedup of 20 490x that increases with the size of topology/specifcattion. The loss of precision due to approximation remains moderate, with the average consistency of the synthesized configurations being greater than 92% even for large topologies. In comparison, NetComplete times out on more than half of the synthesis tasks, which means that we only observe a lower bound for speedup. Running our model GPU memory, cf. Appendix B.3). Comparing OSPF-only synthesis time, our synthesizer model achieves speedup of 10x over NetComplete. With 16 requirements on dataset L this can also increase up to 500x. Further, our model produces fully-consistent OSPF configurations even more often than for BGP/OSPF. See Appendix B.4 for the full OSPF-only synthesis comparison.
GPU can result in even greater speedups (up to 900x given enough
5.3 Discussion
We have shown that our learning-based synthesizer reaches a very high degree of consistency, often producing fully-consistent configurations. With respect to synthesis time, we outperform SMT-baaeed methods by large margin, especially for larger topologies. However, this comes at price: our model sometimes fails to produce fully consistent configurations, especially for large topologies

---

with many requirements. In comparison, SMT-based synthesis will always produce fully consistent configurations if and once it completes. We, therefore, observe a trade-off between consistency and synthesis time. We also note that our evaluation considers real topologies (Topology Zoo (29) but not real specifications. This is due to the lack of a large, practical dataset thereof. Still, we experiment with robustness (Appendix D by introducing distribution shift regarding the size of specifications during training and achieve comparable performance.
Scaling to Even Larger Topologies The Topology Zoo 22 as used for our evaluation, provides good range of realistically-sine -ized networks. However, if we consider synthesis at very large scale (e.g. thousands of routers), we note the following scalability limitations: (1) Our models consume a lot of video memory, reaching beyond the amounts available on current consumer GPUs (> 12GB). This limit is reached with networks of 150 or more routers, and we have to do inference on the CPU (as indicated in Table 3). If even faster synthesis is important at this scale, more than one such GPU is needed for inference. Further, (2) the distance that information is propagated in the synthesizer GNN is finite due to the model's fixed number of iterations. This means that in very large networks, our synthesizer model will only be capable of deriving solutions by local reasoning which is very likely to impact synthesis quality. While out of the scope of this paper, longer training with more synthesizer iterations and larger topologies may be necessary to obtain comparable results at very large scale.
Nonetheless, envision a wide range of peeetically-releaam applications for fast, approximate synthesis, including ML-guided synthesis, unsatisfiable specifications, and hybrid synthesizers, leveraging both learning and SMT solvers. We list number of future directions in Appendix C
Related Work
Traditional Configuration Synthesis Next to methods based on compilation such as Propane/Propane-TT [5), there is number of exact configuration synthesis methods based on constraint solving, e.g. ConfigAssure [31], SyNet (14] and NetComplete (15). These tools are typically hand-coded, very protocol-specific, and can be slow due to the solvers they employ. In contrast, our approach is approximate but scales to much larger networks. Further, as a side-product of our learning-based approach, we can easily adapt to new protocols and allow for transparent cross-prosd cross-protocol reasoning, merely by training on different protocol data.
GNNs and Networking DeepBGP 2
relies on GNNs and reinforcement learning to do configura- tion synthesis. However, it is limited to BGP configuration and is slower than SMT-based synthesis. In contrast, our lcarning- based framework is cross- prosso,oooooo, does not rely on reinforcement learning and provides better synthesis times. Apart from configuration synthesis, GNNs have also been applied to other problems in the networking domain. For example, the authors of RouteNet [4]] use GNNs to predict networking performance metrics. Other work focuses on learning improved protocols like Q-Routing 8 and Graph-Query Neural Networks [8].
Neural Algorithmic Reasoning NAR refers to the idea of replacing algorithms with neural networks to learn improved algorithmic procedures. Successful applications include graph algorithms 43), combinatorial optimization problems [10, 26 37] and multi-task settings [23]. Our synthesis framework the first application of NAR to the networking domain and relies on the naRvna incode-process decode architecture. In the hierarchy of NAR approaches in [10), our method is an algorithm-level approach, as we do not supervise on intermediate steps. Although step-level methods promise better generalization, it is not clear what an intermediate result of general synthesis procedure would be. Future work on a step-level approach may further improve our model.
7 Conclusion
We presented a learning-based method to enable approximate but scalable network configuration synthesis. For BGP/OSPF routing, our neural synthesizer is up to 490x faster than SMT-based methods, while producing configurations with very high specification consistency. We believe there are future research that can be explored in the direction of learning- based synthesis and ML-guided network configuration. Ethical Issues This work does not raise any ethical issues.
Acknowledgments This work was partially supported by ETH Research Grant ETH-03 19-2.
10

---

References
[1] 2022.
Number of monthly active Facebook users worldwide as of 3rd quar- number- (Feb 2022). https://www.staiist htt.://aa..coo/tttttiiaaa//a/aaa weg
ter 2021.
Last-Access; 02.02.2022.
[2] Mahmoud Bahnasy, Fenglin Li, Shihan Xiao, and Xiangle Cheng. 2020. DeepBGP: a machine learning approach for BGP configuration synthesis. In Proceedings of the Workshop on Network Meets Al & ML. 48-55.
[3] T. Bates, R. Chandra, and E. Chen. 2000. BGP Route Reflection - An Altemattve to Full Mesh iBGP, RFC2796. (2000). https://datatrracker ietf wttp.//...o/o/oo///////122212210 html
[4] Ryan Beckett, Ratul Mahajan, Todd Millstein, Jitendra Padhye, and David Walker. 2016. Don't mind the gap: Bridging nedwork-wide objectives and device-level configurations. In Proceedings of the 2016 ACM SIGCOMM Conference. 328-341.
[5] Ryan Beckett, Ratul Mahajan, Todd Millstein, Jitendra Padhye, and David Walker. 2017. Network configuration synthesis with abstract topologies. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. 437-451.
[6] Rüdiger Birkner, Tobias Brodmann, Petar Tsankov, Laurent Vanbever, and Martin T Vechev. 2021. Metha: Network Verifiers Need To Be Correct Too!. In NSDI. 99-113.
[7] Andreas Bley. 2007. Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths. Networks: An International Journal 50, (2007), 29-36.
[8] Justin A Boyan and Michael L Littman. 1994. Packet routing in dynamically changing networks: reinforcement learning approach. In Advances neural information processing systems. 67 1-678.
[9] Matthew Caesar and Jennifer Rexford. 2005. BGP routing policies in ISP networks. IEEE network 19, 6 (2005), 5-11.
[10] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. 2021. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint 2rXiv:2102.09544 (2021).
[11] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021. Evaluating large language models trained code. arXiv preprint 2rXiv:2107.03374 (2021).
[12] Luca Cittadini, Stefano Vissicchio, and Giuseppe Di Battista. 2010. Doing don'ts: Modi- fying BGP attributes within autonomous system. In 2010 IEEE Network Operations and Management Symposium-NOMS 2010. IEEE, 293-300.
[13] Iddo Drori and Nakul Verma. 2021. Solving Linear Algebra by Program Synthesis. arXiv preprint arXiv:21 11,0111 (2021).
[14] Ahmed El-Hassany, Petar Tsankov, Laurent Vanbever, and Martin Vechev. 2017. Network-wide configuration synthesis. In International Conference on Computer Aided Verification. Springer, 261-281.
[15] Ahmed El- El-Hassany, Petar Tsankov, Laurent Vanbever, and Martin Vechev. 2018. Netcom- plete: Practical network- wide configuration synthesis with autocompletion. 15th (USENIX) Symposium on Networked Systems Design and Implementation ((NSDI) 18). 579-594.
[16] Bernard Fortz and Mikkel Thorup. 2000. Internet traffic engineering by optimizing OSPF weights. In Proceedings IEEE INFOCOM 2000. conference on computer communications. Nineteenth annual joint conference of the IEFE computer and communications societies (Cat. No. 00CH37064), Vol. 2. IEEE, 519-528.

---

[17] Aaron Gember-Jacobson, Aditya Akella, Ratul Mahajan, and Hongqiang Harry Liu. 2017. Automatically repairing network control planes using an abstract representation. In Proceedings of the 26th Symposium on Operating Systems Principles. 359-373.
[18) Fabien Geyer and Georg Carle. 2018. Learning and generating distributed routing protocols using graph-based deep learning. In Proceedings of the 2018 Workshop on Big Data Analytics and Machine Learning for Data Communication Networks. 40)45.
[19] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural message passing for quantum chemistry. In International conference on machine learning. PMLR, 1263-1272.
[20] GitHub.com. 2021. GitHub Copilot. (2021). https://cooilott.iibtie com
[21] Timothy G Griffin and João Luís Sobrinho. 2005. Metarouting. In Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communi- cations. 1-12.
[22] Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R Salakhut- dinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv: h00.:120..0550 7500 (2012).
[23] Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličkovié. 2022. A Generalist Neural Algorithmic Learner. (2022). https: http:::/doo..r////// 10. 48550/ ARXIV. 2209. 11142
[24] Sergey Ioffe and Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International conference on machine learning. PMLR, 448-456.
[25] Santosh Janardhan. 2021. More details about the October 4 outage. (Oct 2021). https //eggineer ng. fb. httm///22//////0/////tttto/m/aa/ httpe///iaaetaaaaarato/taaaaaa wttat/uutaaggeelllaeeee Last-
ing.
Access: 06. 10.2021.
[26] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bres- son. 2020. Learning TSP requires rethinking generalization. arXiv preprint arXiv:2006.07054 (2020).
[27] Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.698 (2014).
[28] Thomas N Kipf and Max Welling. 2016. Semi Sumi-super classification with graph convolutional networks. arXiv preprint arXiv:1609.0 009000009907..... (2016).
[29] Simon Knight, Hung X Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. 2011. The internet topology zoo. IEEE Journal on Selected Areas in Communications 29, (2011), 1765-1775.
[30] Moy. 1998. OSPF Version 2, RFC2328. (1998). https://aatatraccer: ietf. oro./oorr//o/// html/rfc258
[31] Sanjai Narain, Gary Levin, Sharad Malik, and Vikram Kaul. 2008. Declarative infrastructure configuration synthesis and debugging. Journal of Network and Systems Management 16, 3 (2008), 235-258.
[32] Yakov Rekhter, Tony Li, Susan Hares, et al. 1991. A border gateway protocol 4 (BGP-4), RFC4271. (1991). htttp:://atttrrackest ietf org/ wwgg/doc/htm///f4477
[33] Paolo Rosso, Dingqi Yang, and Philippe Cudré-Mauroux, 2020. Beyond triplets: hyper- relational knowledge graph embedding for link prediction. In Proceedings of The Web Confer- ence 2020. 1885-1896.
12

---

[34] Krzysztof Rusek, José Suárez- Suárez-Varela, Paul Almasan, Pere Barlet-Ros, and Albert Cabellos- Aparicio. 2020. RouteNet: Leveraging Graph Neural Networks for network modeling and optimization in SDN. IEEE Journal on Selected Areas in Communications 38, 10 (2020), 2260-2270.
[35] Adam Satariano. 2021.
What is Fastly, the company behind the worldwide inter- https://wwrt mytimestt............ www/2021/06/03 /ttp:///bbbussss/////// Lcce-s: 02.02.2022.
net outage? (June 2021).
outage. html,
[36] Tibor Schneider, Rüdiger Birkner, and Laurent Vanbever. 2021. Snowcap: synthesizing network- wide configuration updates. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference.
33-49.
[37] Daniel Selsam and Nikolaj Bjørner. 2019, Guiding gegh-performance SAT solvers with unsat- core predictions. In International Conference on Theory and Applications of Satisfiability Testing. Springer, 336-353.
[38] Samuel Steffen, Timon Gehr, Petar Tsankov, Laurent Vanbever, and Martin Vechev. 2020. Probabilistic verification network configurations. In Proceedings of the Annual conference of the ACM Special Interest Group Data Communication the applications, technologies. architectures, and protocols for computer communication. 750-764.
[39] Kausik Subramanian, Loris D' Antoni, and Aditya Akella. 2018. Synthesis of fault-tolerant distributed router configurations. Proceedings of the ACM Measurement and Analysis of Computing Systems 2. (2018), 1-26.
[40] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention all you need. In Advances in neural information processing systems. 5998 6608.
[41] Petar Veličković and Charles Blundell. 2021. Neural Algorithmic Reasoning, arXiv preprint arXiv:2105.0276/ (2021).
[42] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXtv:1710.10003 (2017).
[43] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. 2019. Neural execution of graph algorithms. arXiv preprint arXiv:1910. 10593 (2019).
[44] Stefano Vissicchio, Luca Cittadini, Laurent Vanbever, and Olivier Bonaventure. 2012. iBGP deceptions: More sessions, fewer routes. INFOCOM, 2012 Proceedings IEEE. IEEE, 2122- 2130.
[45] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2019. What can neural networks reason about? arXiv preprint arXiv:1905.132 13211 (2019).
13


Reviews:
[{"review_id": "oRceA4VOLMM", "reviewer": "Reviewer_cd7P", "summary": "This paper is concerned with the problem of finding a computer network configuration given a topology and a set of routing requirements. \nInstead 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.\nAfter training, the model is able to efficiently generate configurations that satisfy the requirements with high probability. ", "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? \n\n2- Can your technique be applied to much larger topologies than those seen during the training?\n\n3- How does your techique perform on topologies with thousands of nodes?  \n\n4- Have you considered different GNN architetures in your experiments?\n\n5- 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. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nI 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.\nMost 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).\n\n---\n\n**Main comments**\n\n---\n\nI don't understand the advantage of mapping different inputs\n(topology, specification and configuration sketch) into a single\nembedding space instead of treating them differently. As the general\ntrend is aiming at finding semantically disentangled latent spaces,\nmixing together in the same latent space facts related to the topology\nand information on the protocol seems suboptimal. Can you elaborate on\nthis algorithmic choice?\n\n---\n\n\"To remain agnostic with respect to routing protocols, our model\narchitecture implements a generic graph-based encoding of Datalog-like\nfacts\"\n\nProbably, adding a figure depicting the resulting graph for a small\nfact-base would significantly help understanding the proposed\napproach.\n\n---\n\nI wish that some archtectural choices were discussed in detail\nand motivated.  For instance, what is the added benefit of having\nGATs? Is adding a Gaussian noise to the input encoding a standard\npractice when multiple solutions to the optimization problem exists?\nHave the authors performed ablation tests for validating these choices?\n\n---\n\nOn the experimental section:\n\n- It is not clear whether the proposed model generalizes to larger\n   topologies. This is is a pivotal aspect, unless the model can be\n   effectively trained on real-world topologies with \"millions of\n   nodes\".\n\n- The benchmarks only include very small topologies. I get that the\n   SMT-based approach doesn't scale to large topologies. Nonetheless\n   Table 2 could show the average consistency of the generated\n   configurations for much larger networks. After all, this is the\n   whole point of approximating the problem with neural networks.\n\n- Besides a comparison of the proposed approach with a SMT-based\n   configurator, no alternative is considered. Why not reporting\n   ablation studies for different architectural choices? These preliminary results are suggesting that GNN-based\n   techinques can be used to approximate this complex optimization\n   problem, not that the proposed approach and architectural choices\n   are particularly well-suited for the task.\n\n- The fact that the approach is protocol-agnostic seems one of its\n   strongest selling points (see abstract), but in the experiments\n   only a couple of protocols are considered. Plus, both protocols\n   were already encoded in SMT. Are there protocols that are out of\n   scope of (or currently not supported by) SMT-based methods? Adding\n   additional experiments with more protocols would strenghten this\n   aspect.\n\n---\n\n**Minor points**\n\n---\n\nIn my opinion, the formal description of the problem in Section 2 could be improved:\n\n- 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.\n\n- It is initially mentioned that the topology T is fixed in the\n  configuration synthesis task and it is thus omitted in the following\n  equations, but it is reintroduced after line 98. In the same\n  equation, Prot is not mentioned anymore. I get that the proposed\n  approach to synthesis is protocol-agnostic, but that doesn't seem to\n  be the case in general (e.g. with SMT-based approaches). It feels\n  like the description of the task is mixed with specifics of the\n  proposed approach.\n\n\n---\n\n- While I tend to like papers with many examples, I don't see the\npurpose of 'Example intuition' at line 126. What is exactly the\nintuition it should convey? Is it really functional to understanding\nthe contribution? On a side note, it also feels unnecessary for people\nwho know BGP and OSPF already, while being too vague to really help\nunderstanding how these routing algorithms work.\n\n---\n\n\"$D_2^{connected}∶ \\mathbb{R}^D → \\mathbb{R}^\\mathbb{N}$\"\n\n- What is the subscript 2 indicating? I guess the superscript\n$\\mathbb{N}$ (typically referring to the set on natural numbers) is a\ntypo? Also, how is this output a distribution over configuration values?\n\n---\n\n\"A learning-based synthesizer model is formulated as a simple\ninput-output mapping.\"\n\n- I don't understand the sentence. I guess is that you cast the network\nconfiguration given the topology as a supervised learning problem.\n\n---\n\n\"Based on the observation that routing protocols such as OSPF and BGP\ncan be expressed as graph algorithms\"\n\n- I would write 'message-passing algorithms'.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lPmqJM_JF8r", "reviewer": "Reviewer_5wwX", "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.\n\nThe 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.\n\nFuthermore, 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.\n\nTo 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.\n\nThe 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.\n\nThey 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`.", "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?\n\nQ2: 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?\n\nQ3: 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?\n\nQ4: 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?\n\nQ5: 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?\n\nQ6: 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?\n\nQ7: 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.\n\nQ8: Can the authors explain why it is so important that their method does not rely on reinforcement learning?\n\nQ9: 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?\n\nSome smaller remarks:\n\n- line 15: 'resp.' Why 'resp.'? It doesn't make sense to me in the sentence structure.\n- line 18: \"Figure 1 - here\" -> \"Figure 1. Here\"\n- line 31: \"inherent computational complexity\" I find this statement rather unconvincing without specifying what that computational complexity is.\n- line 36: \"relaxing\" -> \"to relax\"\n- 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?\n- line 71: is the second $i$ subscript a typo?\n- line 130: \"the same destination\" which is ...?\n- line 134: \"the decision cannot eliminate\" I'm confused at the concept of a decision making decisions.\n- 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.\n\nAs for other limitations: the authors describe how they modified the original problem and proposed a method for solving that modified ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- As far as I can tell, the method that the authors propose in this paper is indeed a novel way of synthesising network configurations.\n- The authors seems to have a decent grasp of how their work is positioned in the literature.\n- The many paragraph titles in the text make it relatively easy to find relevant information in the paper.\n- The text does not contain many grammatical errors.\n- It seems to me that the problem and the proposed solution would be of interest to the NeurIPS audience.\n- The experimental evaluation makes sense to me, although I have a couple of comments (see below).\n- The results look promising.\n- 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.\n- The authors to some extent explored different hyperparameter settings for their method (in Table 1).\n\n### Weaknesses\n\n- 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:\n  - 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.\n  - 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\".\n  - 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.\n  - 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.\n- 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.\n- 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.\n\nI address the other weaknesses in my questions below.\n\n### Summary\n\nMy 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zbnd-rQfPU1", "reviewer": "Reviewer_CE15", "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.\n\nThe 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).", "questions": "Can you please make Section 1 a bit more reader-friendly? Thanks!\n\nThroughout the paper there is a lot of undefined technical jargon (OSPF, BGP, etc) :) Could you please amend this?\n\nCould 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.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nThis 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).\n\nQuality:\nThe quality of the paper is high, in my opinion: It is well written and the results seem strong.\n\nClarity:\nPresentation 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?)\n\nSignificance:\nThis work is significant in my opinion; see Originality above.\nAnother reason I find this paper important is the scalability of the proposed neural network solution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BX49B9RsL0", "reviewer": "Reviewer_yuPQ", "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.", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n+ __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.\n+ __Simplicity.__ The proposed method appears simple and elegant.\n+ __Can obtain approximate solutions even for unsatisfiable specifications.__ This aspect is interesting and I believe that it is of practical significance.\n\n### Weaknesses\n\n- __Lack of clarity in writing.__ Although the overall approach seems simple, the paper was a bit difficult to follow requiring multiple passes to understand.\n    + 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.\n    + 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.\n- __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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept