INDIANA—In-Network Distributed Infrastructure for Advanced Network Applications

Programmable Hardware Abstraction

Figure 1 presents the high-level design of our INDIANA framework. Here, we discuss the abstraction of how the programmable network hardware provides compute nodes in the ICC and how INDIANA provides virtualization.

Hardware level abstraction

Below we describe the virtualized hardware component and how we virtualize it to provide microservices. In Figure 1, each programmable node holds several InPEs, each consisting of RISC-V soft cores. We deploy InOps on low-level hardware threads associated with a core. We assume a one-to-one mapping between an InPE and a hardware thread in our initial implementation. Once we deploy an InOp on a core using INDIANA, we register the (InOp, service identifier) pair in the Service Registry. We use the relationship at Equation (1) to uniquely identify services deployed for each application by application id (appid). Given application and InOp identifiers (oid), F1 produces a unique numerical value to use as a service identifier for corresponding data sources. F1 is a function external to the underlying system, and the relationship between both sides of the Equation does not change as the externally exposed service identifier (sid) is consistent, even though the internal physical InOp placement changes.

s i d = F 1 ( a p p i d , o i d )

(1)

Internally, we have two types of core identifiers. The physical core identifier (pcid) uniquely identifies each hardware thread (tid), as shown by Equation (2), and is constant for a given cluster deployment. The virtual core identifier (vcid) identifies where INDIANA deploys a specific InOp, as shown by Equation (3). Here, we distinguish between the two different core identifiers, as we can expose more executable units than what is realistically available by context-switching between idle and active threads. However, for this initial implementation, we assume that physical and virtual core identifiers are the same.

p c i d = F 2 ( n o d e i d , c o r e i d , t i d )

(2)

v c i d = F 3 ( a p p i d , o i d )

(3)

Flange uses the virtual core identifier to build rules for the SDN-capable switch. For an incoming packet, the mapping created by Flange, such as service identifier → switch port X, identifies the correct programmable node to route the packet. During the Adaptation stage, once Flange determines that the virtual core for a specific core should change, it updates the service identifier mapping above and wraps the previously decoded data packet with an Ethernet frame with the updated MAC address, and redirects to the correct physical core.

Serverless Architecture

Section 2.1 discusses the relationship between programmable network hardware, virtualization, and task graphs. In this section, we discuss how the complete INDIANA design offers a serverless architecture on top of the programmable network hardware.

Generalized Flow Placement

Having established a mechanism for injecting InOps onto an INDIANA compute node, we now have the groundwork laid for a more generalized interface for operating on network flows. For the purpose of this examination, a network flow is any set F of packets with consistent identifying features that distinguish it from packets not in F.

This is a much broader definition of a network flow than you will see in much of the network orchestration literature. In brief, by broadening the definition of a flow, we allow our analysis of network behavior to be sufficiently flexible to support unconventional network topologies. We will address the larger ramifications and justifications for this definition in more detail in Section 3.

Our goal with INDIANA is to provide a general purpose solution for operation placement within an arbitrary network topology. Generalized operation placement requires three discrete components: programmable hardware, a best-effort algorithm to solve for resource allocations, and a mechanism for defining and controlling the placement algorithm to suite the demands of a given problem domain. The first we have already discussed in Section 2; a method for installing arbitrary InOps onto a variety of network hardware. Each of these compute nodes is capable of further specialization into InPE slices so as to improve flow level parallelism. Expanding the scope outward, even a perfectly optimal placement within a single computation node is still non-optimal if there exist nodes with higher spacial affinity to the packets in the network flows being serviced.

We take a network wide approach to placement by treating all compute nodes as a single pool of resources which are labeled by their affinity to each flow. This allows us to solve the intra-node and inter-node placement of functions in the same pass.

Consider a virtual compute node representing the totality of the available compute resource on the network sliced into N InPEs with a capacity

C ( n ) → { small , med , large }

(4)

We further specify the set of flows F as

F = { f | packet p ∈ f ∧ p r e d ( p ) }

(5)

There is a cost function ψ ( f ) for the unit cost of placing an operation onto an InPE. We would like to identify a mapping

M ( f ) → { n i | n i ∈ N ∧ P ( f , n , i ) }

(6)

F n = { f ∈ F | n ∈ M ( f ) } m i n i m i z e ( ∑ F n f ψ ( f ) ) S u b j e c t t o C ( n ) ≥ ∑ F n f ψ ( f )

(7)

This formulation shares similarities to both the bin packing and number partitioning problems (Martello and Toth, 1990). However, it differs in a few key ways. Our goal is to maximize the available parallelism in the system; conventional bin packing approaches will minimize the number of bins while maximizing the allocation per bin.

Multiway number partitioning shares more in common with the above, but differs again in one key way: our use of elastic bin sizes allows us to upgrade a bin to a larger size for greater capacity at the expense of parallel execution.

We developed an algorithm that instead maximizes the number of bins within a constrained space, collapsing bins into larger bins on an as needed basis.

The constraints in Equation (7) are also insufficient to describe a real world multi-commodity function placement problem. For this, we need to further specify the function color of a flow. Since flows may have multiple functions applied in sequence, we define color as a mapping

A ( f , n ) → a ∈ A

(8)

∀ n ∈ N : ∀ f 1 , f 2 ∈ F n : A ( f 1 , n ) = A ( f 2 , n )

(9)

Considered as a whole, Equations 7 and 9 define the algorithm we use to perform function placement in INDIANA.

Each flow is labeled by a set of desired operations and each node is labeled based on its candidacy for acting as a solution for each flow. A solution is generated all at once for all flows by aggregating all compute nodes into a single virtual node and solving for the minimal load per InPE.

Defining discrete applications

Having defined our placement constraints, we need a mechanism for specifying the parameters of a discrete instance onto which our algorithm should be applied. For this purpose, we have implemented the Flange NOS.

The Flange NOS is broadly composed of three components: A frontend compiler that consumes human-writable high level, flow-oriented declarations and produces Flange Assertion Graphs, a backend resolver that takes serialized Flange Assertion Graphs and apply them to a specific network topology, and a runtime service for re-validating existing programs as needed as the network topology changes. The relationship between these three components and the underlying network topology is shown in Figure 6.OPEN IN VIEWER

INDIANA processsing element

We envision the use of programmable network devices in order to realize a fully integrated network architecture for deploying low-latency microservices. Different programmable networking devices are built using a variety of types of hardware including Application Specific Integrated Circuits (ASIC)s, Network Processors, and Field Programmable Gate Arrays (FPGA)s. ASICs provide fast packet processing but have fixed functionality and can be hard to program. Network Processors are more flexible and may be easier to program, however, the high throughputs required for network-heavy applications require heavily optimized application designs. FPGAs provide a middle ground, outperforming Network Processors without sacrificing too much programmability. In this work, we realize our design using RISC-V soft cores (dynamically instantiated, general-purpose RISC-V processors) on FPGA-based Smart NICs in order to achieve flexibility, performance, and determinism when executing applications.

This work builds on top of prior work discussed below, specifically for the INDIANA in-network processing elements, or InPEs. The initial version of an InPE was found in InLocus (Brasilino et al., 2018), where we presented an in-situ stream-oriented architecture designed around Vivado’s High Level Synthesis capabilities (HLS) in which C-like code is compiled directly to low-level, FPGA register-transfer logic (Xilinx, 2021). HLS hardware modules provide orders of magnitude gains in performance over NodeJS or linux-based C reference solutions, while at the same time benefiting programmability as application developers implement high level code to interact with hardware components written in Verilog. However, HLS limits our ability to implement a dynamic and adaptive function deployment architecture because the FPGA must be dynamically reconfigured, which requires extensive hardware knowledge and is time-consuming.

The second generation InPE was developed as part of NetFaaS, where we investigated how we can achieve performance similar to Verilog hardware modules but with more flexibility and programmability (Ossen et al., 2022). NetFaaS introduced RISC-V soft-core based stream processing services relating to our work, used an Ethernet MAC Address-based service identification scheme, and introduced a new dual-ported memory implemented in hardware. The memory used full and empty signals (identified based on data availability) to control the handshake between the core and memory, reducing memory access latency. HLS module hardware resource consumption increases with increased functional complexity, while RISC-V soft cores have fixed hardware complexity and are a suitable alternative that provides general-purpose computation with better utilization.

In this work, we extend the notion of an InPE to encapsulate any compute architecture that can be deployed into our network, with a focus on heterogeneity and dynamic adaptive customization. This third generation InPE model forms the basic unit of in-network computation and is the target on which InOps are bound (Section 3.2). While we use the term InPE to characterize a class of objects, our evaluation of the full-stack INDIANA framework requires concrete cores and performance metrics. Our evaluation in Section 4.1 will characterize the performance of the unmodified BOOM (Asanovic et al., 2015) RISC-V implementation deployed within the FireSim tiled network framework (Karandikar et al., 2018), which can be viewed as simulating a potential real-world heterogeneous network target.

INDIANA operator placement

Given a set of statically provisioned InPEs as described above, we need a mechanism for mapping INDIANA operators (InOp)s to InPEs. This mapping should be as close to the theoretical optimal mapping for flow allocation as possible to minimize packet loss due to congestion or node over-subscription.

We implement a greedy approach to this InOp placement problem, which shares much in common with the bin packing problem. Our solution roughly follows a Worst Fit approach to bin packing. While Worst Fit matches the approximate optimality guarantee of the more efficient Next Fit, our use case includes the additional constraint of minimizing the work per node. While this results in a larger overall time complexity by a factor of O ( log | N | ) , the unit cost of placing a single flow onto an InPE is dominated by the available compute on a node. This means that by using Worst Fit we reduce the probability of flow migration due to new sources being added to the system at run time.

A similar result can be achieved through Best Fit, however, the conditions of the underlying network are in flux-spikes of flow congestion must be accounted for. Best Fit provides similar time complexity and resilience to flow migration, compared to Worst Fit while maintaining a stronger approximate optimality guarantee but is brittle to intra-flow fluctuation.

Our algorithm begins by modeling each node as a set of unlabeled tiles categorized into cost tiers read from the Service Registry (Figure 1). Tiles ultimately map to discrete InPEs, but we will use an abstraction here to distinguish the internally mutable tiles from the discrete deployed InPEs. Each tile is annotated with a capacity, cap, and cost, ψ. The cap of a tile is considered to be the maximum capacity of a tile of size C minus the resident set of flows R on the tile while ψ is the cost function for the tile to exist on the node and Ψ is the upgrade cost to a higher capacity tier.

The basis of our algorithm is the iterative tile collapse procedure; any set of tiles S may be replaced by another tile d provided ψ(S) ≥ Ψ(d) and cap(S) < cap(d). This provides us with a framework for elevating tiles up the hierarchy if more capacity is needed. We will call this the collapse procedure. Formally, collapse is a function that takes the set of tiles T and a tier c.

We maintain the upgrade cost of a tier, Ψ, distinct from the individual tile cost ψ because while these functions are the same in the common case, keeping them distinct allows clients to disable the upgrading behavior in the algorithm by marking the tier cost as ∞ if the hardware does not support flexible core sizes.

When there is no tile on a node that satisfies the cap requirement for a flow, we perform a collapse operation starting at size class c = small. If the total ψ(T) for all T in the size class is less than Ψ(c + 1), we instead increase the class by one size. This repeats until a resulting collapsed tile t’s cost ψ(t) is sufficient to contain the flow or the size class exceeds the defined size categories, in which case the placement terminates in a failure and evicts the node from the candidate placement list.

To solve the multi-flow version of the problem, we extend our definition to create two tensors: the NxF node tensor N and the AxF function tensor F . We perform the placement algorithm described above on F [ f ] [ 0 ] for each f in F at node N [ f ] [ 0 ] . On placement success, the function is removed from F [ f ] . On placement failure, the node is removed from N [ f ] . The placement is considered complete when F = ϵ . Alternatively, if N [ f ] = ϵ , the proposed solution is rejected and the NOS must generate an alternative.

Network flow scheduler

At its core, the Flange NOS acts as a flow-oriented graph solver. By taking in the current state of a network as a graph and comparing it to a desired state in the form of a Flange Assertion Graph we can generate a list of differences. The myriad of components and functions in Flange that we describe in the following section all act in service of this core tenet.

The Flange resolver is responsible for the process of resolving the Flange Assertion Graph into a discrete set of topology changes. The assertion graph is a list of proposed flows, each of which contains a list of facts associated with a candidate flow. We address the particulars of the assertion graph representation in detail when we examine the Flange compiler. The first phase of the resolution process is to take the assertion graph and identifying all possible flows described by the graph. This first phase is called the Flow-Expand pass. It only performs expansion on each candidate flow into a discrete, realized flow based on the current state of the topology at runtime.

To explore the practical intent behind the Flow-Expand pass, consider Program 1 in the Flange DSL (Section 3.7).

Listing 1: sample program

exists node m, flow f :

 forall node n :

  n.type == ”foo” and f == n −> m

This program is semantically congruent to a gather operation from all nodes of type “foo” to a single other node. At compile time this program does not define a number of flows to be generated nor the identity of the node n or m. At run time, the above program would apply the Flow-Expand pass to resolve the forall into a list of all nodes that satisfy the constraints and yield a discrete flow for each as described by the scoped constraints. At this stage, flows are discretized, but have not been realized into full paths. We can now start to narrow the solution space until the flows converge on a set of fully satisfying paths.

When resolving flows, changes are described as either interfering or non-interfering changes. For instance, terminating a flow at a node is a non-interfering change. In theory, terminating many flows at a single endpoint may have knock-on effects. However, for all practical purposes, we assume terminating a flow does not affect other flows in the network. In contrast, mapping a function onto an InPE node is an interfering change; for a node of any capacity, there is a certain number of processed flows, at which point the node’s performance begins to degrade, and packets drop.

For this reason, we cannot solve flows independently. The placement of function λ _n may preclude the placement of λ _m . Instead all flows undergo a sequence of transforms in tandem, starting with the Flow-Path resolution pass described above.

We consider the result of the Flow-Path pass to be a set of candidate flows S . In practice, S is a list of infinite generators, each of which yields a candidate iterative weighted shortest path. This empowers each pass to reject a candidate solution on a flow by flow basis, or reject an entire solution set. If a path is rejected, the solution is recalculated based on the next most optimal flow path.

This set of iterative candidate solutions lends itself naturally to a modular approach to the Flange NOS. The backend is made up of a series of modifier passes. Each modifier is made up of a validator and a resolver. A modifier’s validator is run on candidate paths before resolution is attempted. In doing so, we can preemptively reject paths that are trivially identified as non-satisfying. For instance, if a flow expression included a fact asserting the existence of a function λ, any path matching the top level conditions of the flow that does not contain a programmable InPE node can be rejected before any costly placement calculations are performed. A modifier’s resolver consumes a validated path and performs a difference operation between the current state of the candidate path and the collection of facts. Each modifier defines for itself how to resolve any given fact. Continuing the example above, the InPE resolver would identify an InPE node along the candidate path to place the λ function (Section 3.2). If no such function already exists, the pass emits a delta including the following flange assembly instruction: install λ <node-type> <node-id>.

In contrast, the Routing modifier identifies and injects forwarding instructions into the delta based on the type of each node in the path. During this pass, each forwarding instruction is considered independently and is assumed to be a full-field match.

The aggregation of such instructions across modifiers represents an unordered change list generated by the Flange NOS. Network agents such as the INDIANA Service Registry and SDN controllers consume these changes and modify their internal state as requested to reflect the included instructions.

This naive approach is sufficient for many use cases. However, while the resulting solutions will satisfy the prepositions asserted on the network, it is clear that certain flange assembly instructions will result in poor performance if left in an unordered, non-processed state. Up to this stage, flows are processed simultaneously in order to allow modifiers to identify invalid solutions due to inter-flow interference. The resulting instructions are still generated on a flow by flow basis. As a final pass, we perform the trivial transform on the result from a flow-oriented domain to a node-oriented domain. Then each node’s instructions are aggregated by category and forwarding rules are consolidated into a longest prefix match form where applicable.

Thus far we have described the behavior of the Flange NOS as an independent service. Now we will examine the practicalities of the NOS dependencies, the Flange Assertion Graph and the UNIS network model (El-Hassany et al., 2013) which together form the inputs for the Flange NOS as seen in Figure 7.OPEN IN VIEWER

Flange assertion graph

The Flange Assertion Graph (FlAG) is an entity fact tree. A Flange entity E may be any virtual node or flow. Each entity of discourse is included in the FlAG along with a list of predicates or facts which must validate successfully in a candidate solution for the entity to be considered a satisfying solution. Furthermore, in a General FlAG each entity may contain any number of dependent FlAGs. Entities with children at layer n are only satisfied if at least one child at layer n + 1 is satisfied. Let’s consider the Flange program P in program 2.

Listing 2: INDIANA sample program

exists node e :

 e.type == ”sink” and

 forall flow f :

  exists node s :

   f == s −> e and

    ((s.type == ”A” and foo(f)) or

     (s.type == ”B” and bar(f)) or

      (s.type == ”C” and baz(f)))

Program 2 is an archetypal, if simple, INDIANA program written in the Flange DSL (Section 3.7). It describes a scenario wherein a network contains a set of nodes such that at least one node is of the sink type and that given a collection of flows between node types A, B, and C and the sink node, the flows are mapped from A, B, and C to the functions foo, bar, and baz, respectively. The corresponding FlAG to such a program appears in Figure 8.OPEN IN VIEWER

As a first-order logical language, in practice the general Flange Assertion Graph is a predicate logic tree. As a consequence, we can apply any logical permutations on the tree that is permissible within a first-order logical system. While there are certain advantages to this tree-like formulation of a flange program, it does not lend itself well to the flow-oriented approach of the NOS backend. We need to convert the FlAG into a flat, flow-oriented decision space. Fortunately, this operation is well established: we simply remove the existential quantifiers and replace them with functions that map to corresponding results and flatten the tree, this transforms the tree into a Skolemized disjunctive normal form as seen in Figure 9. Each disjunctive stanza can now be treated as an independent network assertion by the Flange NOS.OPEN IN VIEWER

Flange network model

We use an active network model stored in a NoSQL database using the Unified Network Information Service schema. This model may be populated through in-network probes, SDN controllers and manual administrator configuration. The UNIS schema defines nodes, links, and ports as the primary entities.

For use in the Flange NOS, we need to be able to model complex network interactions for any useful application. UNIS facilitates multi-layer networks through virtual nodes and links layered hierarchically through ports. A node entity may represent a host, switch, or network depending on associated ports. Node capacities and capabilities are included as entity annotations. The Service Registry described in Section 2 is also implemented as annotations in the network model. This keeps the network model as the ground truth record of network state and allows us to map Flange assertions to model fields through a form of duck typing. Any nodal assertion in a Flange program is considered to be valid if and only if the associated annotation exists on the node in the model and the value of the annotation satisfies the comparison operation.

The dual of the node/network relationship is the link/flow relationship, which behaves in the same way. UNIS link entities may either represent a link or a flow. Links are distinguished from flows by their mutability. Links represent existing features of the network. They may have annotations, but these annotations are only used as the basis for invalidating assertions. In contrast, flows are considered mutable and are identified by the layer of their endpoint ports. Conceptually, the network graph can be viewed as a hypergraph with flows as directed hyperedges. In our experiments, however, we do not expand our model to support this feature; point-to-point flows are sufficient to model our testing scenarios.

We refer to this model as the active network model because it can be augmented with live measurements. Any edge E contains an arbitrary set of measurements. These measurements are identified by a metadata record that uniquely defines an event type and subject entity.

These measurements are used by the Flange NOS in both implicit and explicit ways. Implicitly, any backend modifier may reference a measurement in order to validate or resolve candidate paths. Of particular note to INDIANA is the InPE modifier, which uses measurements on existing flows to better schedule function placement. In the placement algorithm described in Section 3.2, we refer to a cost function C . In our implementation, we use the active packet-per-second measurement on established flows multiplied by an estimated function cost defined at compile time for each requested function.

The specifics of how per-flow packet-per-second measurements are generated will depend on the deployment environment but could easily be generated in flight by SDN meters or defined at the source as part of the data generation. Flange itself is agnostic toward the source of the measurement data and assumes the model is a best-effort reflection of the current state of the network. In the absence of a packet-per-second measurement, the behavior is modifier dependent. In the case of InPE, it will fall back to the average rate of existing flows and failing that, use a default estimate defined at compile time.

Alternatively, measurements can be invoked explicitly in a Flange program by calling the measurement as a function on a flow within the program. In Program 3, a single flow between nodes A and B is selected that is sending more than 100 packets/s; a function summarize is then applied on that flow.

Listing 3: INDIANA sample program with measurements

exists node e, node s, flow f :

 e.name == ”B” and s.name == ”A” and

 f == s −> e and

 f.packetspersecond() > 100 and

summarize(f)

During compilation, measurement requests yield a deferred event record. At run time, this event record yields the current state of the measurement. The collection of all event records generated for a given program is considered the program’s event domain.

Passive versus active flow scheduling

The Flange NOS can generate the solution for a program on demand which is then passed to in-network agents that work as actuators on the network, reporting the new state back to the network model. This is the passive execution model of Flange as described thus far. Changes to the network are only applied at the request of the administrator on the execution of a new policy.

This mode of scheduling is insufficient to perform as a production NOS. Conditions in the network change. At the macro level, new data sources may be added, extra links may be connected, and new Programmable Node modules may be installed. At the micro level, data source flow rate may fluctuate or other services may contest the resources used by a program.

In order to address the inherent mutability of the network, we introduce a manager service called the Flange daemon. The Flange daemon primarily acts as a network program scheduler. When compiled, a FlAG is registered with the daemon; newly registered FlAGs are immediately flagged as invalidated. In conventional OS terms, this queues the process as pending.

The Flange daemon runs pending programs against the network state as it appears at execution time. This execution generates two products as described in Section 3.3: a delta list and an event domain. The delta list is immediately deployed to the network where rules are inserted as needed. The event domain is fed back into the Flange daemon as a collection of potentially invalidating conditions. Each condition is registered to the FlAG that generated them.

When a change in the network model is detected, the new state is compared to the event domain of each registered FlAG. If an event fails a validate, the FlAG is marked as invalid and placed in the queue for re-evaluation.

By using this approach, we have traded optimality for performance. Only invalidating changes in the network prompt a re-evaluation of a program. As such, some changes that may result in a more optimal solution will be ignored, since they do not invalidate the current running solution.

In practice, this is preferable, since re-configuring the network involves a substantial cost in terms of network disruption and flow instability until the new solution is fully installed. We can mitigate potential network disruption by using transaction-based transitions, but this incurs a further performance penalty during rule placement. Instead, we minimize network disruption by only modifying the current network state when a program is invalidated. Furthermore, potentially costly re-evaluation is only executed in the case where a member of the event domain is changed.

We can optimize our active resolutions further by tagging event domains with specific DNF stanzas/flow pairs within the FlAG. Since stanzas only interfere if they contain overlapping paths, an event that invalidates a subset of the FlAG only requires a re-evaluation of the invalidated stanzas. This partial re-evaluation is limited to solutions that do not invalidate non-triggered stanzas. In the case of a partial re-evaluation failure, the entire FlAG will be triggered as pending.

This process allows the Flange daemon to maintain the state defined in a set of programs in the face of network topology changes and performance fluctuations.

Flow policy language

The Flange language was designed to codify network flows into a concise, declarative form. Conceptual network models exist in a spectrum of abstractness from physical to logical. A fully physical network model has the advantage of completely defining the behavior of the modeled network, but suffers from its own complexity. Inferring meaningful information from a physical network model is difficult. The behavior of a given node or link in the model is defined by the hardware specification, adjacent entities, levels of encapsulation, etc. Writing a policy to modify the model state is still more complicated. The user needs a full understanding—not only of the individual systems in the network—but the interactions between systems. For this reason, Flange attempts to divest the developer entirely of the physical topology, allowing them to express their intent purely in terms of the logical flow of content. Flange programs take the form of first-order logical expressions over the domain of logical nodes and flows.

Modern SDN projects such as Firmament (Gog et al., 2016; Merlin Soulé et al., 2014) inspired many of the features in Flange and our approach of modeling networks at a higher, more abstract level. It could be said that SDN itself is a continual effort to lift the domain of discourse from physical to logical abstractions. However, existing approaches use node or packet level abstractions when defining behavior. In contrast, Flange is a flow-oriented language. In Flange, non-flow types, such as nodes, exist only to express specificity when validating flows. Flange combines this high-level abstraction with explorations into declarative network specifications such as (Anderson et al., 2014; Chen et al., 2010; Foster et al., 2011; Hinrichs et al., 2009; Monsanto et al., 2012). Programmers express the behavior of flows by defining the matching parameters that shape the flow. For example, in Program 3, we define a flow f. The specifics of the flow source and destination are left to the compiler, provided that the final source and destination are among the nodes that match the facts associated with those endpoints.

The break down of the Flange language structure is defined in the syntax diagram in Table 1. The core notation of Flange is the flow operator, which is denoted by →. In its most primitive form, the flow operator takes two assertions and concatenates them as a directed forwarding path. For example, given a node A and a node B, A → B yields the shortest valid path between A and B. The shortest path is only considered valid given that all facts associated with the flow are satisfied. In the event that a path fails in validation, the search continues where it left off and returns the next shortest path.

OPEN IN VIEWER

Table 1.

Flange syntax diagram.

This formulation of a path is quite powerful; for many applications, simply being able to express point-to-point paths is enough to achieve useful and robust behaviors. In the INDIANA context, we wish to take this approach a step further. As a functional concatenation operator, the flow operator can be chained, Flange will optimize for the outer pair on paths that pass through all vertices requested. This looks like sum(A → B). The expression can be read as the flow from A to B passing through the function sum. This example assumes a stream of numeric data is being generated by A. Function predicates can be chained indefinitely as needed.

Flange uses link virtualization to treat flow predicates as a single edge between two vertices. When the flow is fully resolved, each hop within the virtual edge is annotated with the necessary forwarding changes to realize the described virtual edge. By reducing all flows to a single edge, all flow problems can be generalized into a single overlay topology before finally resolving down the physical topology in the resolver.

Quantifying assertions

In order to fully specify the relationship between network entities we use the forall and exists quantifiers. When viewed as a formal first order logical language, Flange inherits the predicate logic solution here; node and flow types are bound using the existential and universal quantifier. Validating facts are processed over the variables thus quantified. Recall that facts map to predicate expressions in the FlAG consumed by the Flange NOS. There is a more practical application for quantifiers in Flange; however, it is necessary to have a mechanism for distinguishing how a flow should choose constituent elements. Quantifiers help us to distinguish between a generative operation and a filtering operation. The universal quantifier queries a collection of entities that currently satisfies the descendant facts referencing the quantified variable.

In contrast, the existential quantifier can be generative; if a satisfying entity already exists, the NOS will attempt to satisfy the FlAG by iterating over the list of entities that match to predicates for the variable with short circuiting-search will terminate prematurely on a solution. Unlike the universal quantifier, if no satisfying solution is found with the existing entities, Flange will attempt to generate a satisfying entity.

When the Flange NOS receives a request for an existential flow and no existing flow satisfies the descendant predicates, it instead generates a flow de-novo provided some entity exists that satisfies the start and end points for the proposed flow. The flow generation happens as part of the Flow-Path resolution pass provided at least one physical path exists onto which the flow can be injected. Subsequent passes do not need to consider if the flow under consideration has been generated or is an existing flow to be modified. As such, the modifiers can treat all flows as existing flows to be modified, greatly simplifying the system logic.

In the case of an existential node, our current implementation terminates and informs the user that the program is unsatisfiable. Nodal generation is theoretically possible, provided an agent like KVM, Puppet (Benson et al., 2019), or Ansible (Ansible, 2017) capable of generating system configuration for hardware or VMs. This is beyond the scope of this examination of the INDIANA architecture, however.

Recall that we use a disjunctive normal form for expressions fed into the Flange NOS. Disjunctive normal form does not include quantifiers, so we perform Skolemization on the FlAG. This process converts all references to variables to either discrete instances or closures that take the current scope as arguments depending on the type of quantifier used to generate the variable. Universal entities are converted to discrete variables while existential entities are converted into Skolem functions.

Beyond conforming to the formalities of first-order logic, Skolemizing the FlAG provides us with a practical abstraction when interpreting the expression in the NOS. Each reified candidate flow contains a symbol table with associated universal variables. This maps well to our model where each flow is considered a distinct unit satisfied concurrently. Skolem functions are implemented as a generator with memoization across the entire environment. Each Skolem function returns the same result for each closure environment while allowing the Flange NOS to iterate across candidate matching entities.

By compiling the Flange program from a human-writable format to a Skolemized disjunctive normal form, we can interpret the resulting sequence of clauses as discrete flow requests. Each flow request can then be passed through a sequence of modifiers applied to a network instance to generate a final proposed set of instructions to actuate on the provided network.

FireSim evaluations

The following FireSim simulation experiments are run on Amazon Web Services (AWS) F1 FPGA instances (Xilinx Alveo Smart NICs) (Xilinx, 2022) and are designed to collect meaningful real-world parameters to be used in the cost model for our modeling infrastructure, as evaluated below.

We test our compute kernels on the BOOM core, a superscalar out-of-order core with a 7-stage instruction pipeline. The single-core BOOM CPU runs at 3.2 GHz and contains 4 MB of L2 cache and 16 GB of DDR3. The core is deployed as a simulated 2-node cluster connected by a single top-of-rack switch. Each core runs baremetal C code, where the producer sends packets to the consumer at varying message rates for different function kernels for 1 s. To be on par with our previous InPE work, we tested the compute kernels with a 1 Gbps maximum NIC bandwidth. FireSim provides a parameterizable interface for defining network behavior; we use the port-port switching latency of 10 cycles (3.125 ns) and link latency of 6,405 cycles (2 µs) to simulate our system. Table 2 describes the function kernels we have implemented for the experiments.

OPEN IN VIEWER

Table 2.

Function kernel description.

Function	Operation type	Operation	Window size	# Of 64-bit values
rolling-sum	sliding window	sum of a window of elements	10	1
rolling-avg	sliding window	average of a window of elements	10	1
vec-dot-prod	vector	dot product between two vectors A and B (A · B)	NA	8
vec-triad	vector	Scalar multiplication and addition between two vectors A, B and scalar value c (A + cB)	NA	8
mat-mul	matrix	multiply two 4 × 4 matrices A and B (A × B)	NA	16

Figure 10 shows the timing information for the producer running on BOOM. We define the transmission time as the total time taken to send the data packets from producer to consumer, and it depends on the data payload size. As the message rate increases, for the same rate (same number of messages sent to the consumer), the difference between sending different-sized packets (1, 8, and 16 64-bit values) increases. As the NIC egress flow contains memory reads and transferring data via the network, each memory word read adds to the total transmission time. In this experiment, the maximum attainable message rate for the 1 Gbps NIC bandwidth is 6,000,000 packets per second without any loss of packets. We can increase the maximum supported NIC bandwidth to support transmitting more 64-bit data words and message rates on the producer without overwhelming the system.OPEN IN VIEWER

Figure 11 shows the timing information for the consumer running on BOOM. Here, we depict the total execution time, comprising the time taken to receive packets and execute the function kernels on the incoming data. Here, a similar execution time is seen for function kernel pairs (rolling sum and avg, sliding window and vector operations) as an equal number of operations is performed on an equal number of incoming data elements. As the function complexity increases, from simple addition, addition and multiplication between two vectors, and matrix multiplication, the execution time also increases.OPEN IN VIEWER

Function placement performance

In order to evaluate the performance of the Flange NOS, we ran two scaling experiments. We performed these experiments using simulated networks in order to examine a wide range of network scales and degrees of function density. Fortunately, the structure of the Flange ecosystem supports network simulation natively. By providing the model with a simulated topology and discarding the instructions generated by the Flange NOS we can perform placement operations on any arbitrary topology. Doing so fails to correctly simulate the feedback loop used by the Flange daemon in order to provide active network management, but since these experiments are meant to demonstrate placement performance, a simple passive application is sufficient. We considered the following three parameters during simulation: the density of data products, the producer count, and the InPE node capacity.

All placement scaling experiments were run on an Intel i7-8705G at 3.1 GHz and 16 GB of DDR4 2,400 MT/s. Each parameter sweep performs 100 runs per configuration; graphs display the mean performance and one standard deviation per configuration.

In our first scaling experiment, we maintained a simple policy across all runs with three product types and infinite InPE node capacity. Our goal here was to determine the effect of increasing graph size on the placement algorithm on a successful solution; limiting the InPE capacity would have injected failure states that would have increased the error for larger graphs without providing any useful feedback. The Flange NOS is able to perform early detection on flows that exceed the network capacity. This produces an apparent sudden performance improvement when the produced data exceeds network capacity—a useful feature for practical applications, but not ideal for examining the scaling behavior of our implementation.

Figure 12 shows our simple three product policy applied to networks with scaling source node counts. For this experiment, the graph is a simple star topology in which one virtualized InPE node and between 100 and 2,000 data producers are routed through a single programmable switch. Results represent the time required for the Flange NOS to calculate an InPE placement scheme and generate a routing plan for the n nodes through the switch (the cost of the latter is dominated by the former, but it is worth considering that these times also include the routing performance).OPEN IN VIEWER

The choice to model this scenario with a single programmable switch lies in the virtualization techniques used by the Flange NOS. With no route optimization conditions in the program, a more complex routing topology—such as a Clos network—would be functionally reduced in model to a single routing vertex as part of the graph reduction pass. Making these two graphs isomorphic for all practical purposes in this scenario.

We observe a clear polynomial growth in placement performance. This is within our expectations based on our inheritance of the O ( N ∗ log | N | ) Worst-Fit bin packing algorithm. These values are within our expectations for a proof of concept implementation of the algorithm, however, overall performance still leaves much to be desired. In a production environment, recalculating placement is performed rarely enough that an order of minutes compilation time is acceptable in most scenarios, but clearly not ideal. For instance, when using active monitoring with the Flange daemon, this is not sufficiently performant to respond to sudden changes in network congestion; though it is sufficient to support periodic fluctuations such as daily use patterns.

It is our belief that with optimization of the constant factor, we will be able to further refine the placement algorithm to allow for fully responsive reconfiguration.

Interestingly, performance begins to become more unstable past the 1,500 node threshold in this experimental configuration. This is due to the implementation of the virtual InPE node’s properties. Past 1,500, the number of required collapse operations performed increases linearly due to the source cost exceeding the base number of available InPE tiles. Up to this threshold, collapse is performed only when necessary due to a particularly large flow exceeding the tile capacity.

Another observation here is the relative real and usr times. The usr time scales proportionally while IO represents less than 6.6% of the execution time—indicating that external factors such as our network model implementation have minimal impact on the performance of INDIANA.

Figure 13 shows the results of our second Flange scaling experiment in which we used a static 300 source network in a star topology with a single virtualized InPE node. The experiment scaled the function type density from 0.05 (15 function types) to 1.0 (300 function types) over the 300 source nodes in increments of 0.05.OPEN IN VIEWER

The performance scales linearly as function types are added to the solution. This scaling factor is the result of the Flange NOS’s attempt to find an optimal arrangement of functions on the compute node to balance the flows across the available resources.

There is a disruption around 225 function types. This correlates with the point at which the node can no longer place node function in place onto the node and needs to begin performing collapse operations to successfully place all of the function types.

Combining these two results, we confirm the average runtime of our implementation of O ( F ∗ N ∗ log | N | ) where F is the function type density and N is the number of mapped flows.

Low-level framework limitations

Implementing a low-level framework, designed to be immediately placed in or beside high-speed switching hardware, has limitations in the computation it can offer. Specifically, any operation that requires storing state, such as an element of windows, adds more complexity as we need to allocate resources for storage, reducing available resources for computation. Often performing compute-intensive operations also requires complex solutions (Kohler et al., 2018; Xiong and Zilberman, 2019; Zheng and Zilberman, 2021). We are limited in the capability to use existing software libraries known for improving performance. We also run into the problem of a heavily pipelined solution dropping packets in a network-intensive application when memory-intensive and compute-intensive operations dictate performance timing. However, using FPGA hardware accelerated modules and ISA extensions to delegate specific functionality from the core can significantly provide performance improvements. We intend to explore this space of solutions for significant performance improvements in future work.

Swapping workloads and reprogamming cores

In this work, we program each RISC-V core with the C code before starting the simulation using FireSim. Therefore it is equivalent to statically assigning programs at initialization. However, to be a framework supporting dynamic service deployment, we need the capability to swap workloads and reprogram cores on-the-fly. As previously stated, using partial reconfiguration for FPGA designs consumes considerable time. A less complex and faster alternative to reprogramming a core might be to associate a separate fast network path in the SDN-capable switch, introduce tiny packets containing the program code and utilize this network path to program the core via a reset. To realize this implementation, we will have to expose the L1 instruction and data caches and any scratchpads holding function code. We can either replace existing function codes or place the new function code in a separate address space and perform context switching between the hardware threads using the Thread Scheduler. We will be exploring these avenues in our future work.

Flow scheduling pitfalls

In the current implementation of the Flange language and NOS, there are several features that fall short of the intended design. A major hurdle when designing policies in the current implementation of the Flange NOS is the restriction of one logical flow per conjunctive clause. Every flow is considered an independent flow; placement and routing is performed dependently in the sense that flow a may nearly exceed the capacity on a node, preventing flow b from being placed on the same node, but it is impossible to express that a is directly dependent on the existence of b. The Flange language supports these types of assertions as seen in Program 4 but the NOS will reject the program as invalid.

Listing 4: A simple program with dependent flows

exists node e, node s1, node s2,     flow f2, flow f2 :   f2 == s1 −> e and

 f1 == s2 −> e

The logic in this program is similar to Program 5; in both examples, two flows are asserted, but in Program 4 the flows are dependent while in Program 5 each flow can exist or fail to exist independently.

Listing 5: A simple program with dependent flows

exists node e, node s1, node s2:

 forall flow f :

  f == s1 −> e or

  f == s2 −> e

Transforming the solution space from a list of candidate flows to a list of lists containing dependent flows is the obvious correction, but invokes a performance cost for resolving dependent flows. We plan to explore optimizations that reduce the overhead of solving dependent flows in future work.

Policy language limitations

The type space used in the Flange language is ultimately very limiting. We provide the four constant types-strings, integers, floats and booleans-along with the none special type. Variable types are limited to only two types-nodes and flows. It is clear that the addition of arbitrary variable substitution within expressions would greatly increase the expressiveness of the Flange language; consider the example program we have used throughout this paper, Program 2. The version of this program with variable substitution and a map type could be reduced further to Program 6.

Listing 6: An hypothetical example of variable substitution in Flange

exists node e, map M :

e.type == ”sink” and

M == {”A”:foo, ”B”:bar, ”C”:baz} and

forall flow f :

  exists node s, string x :

   f == s −> e and     s.type == x and M [x](f)

Furthermore, functions like the above examples foo, bar, and baz are defined in built-in libraries. Additional functions can be added by registering them through UNIS records, but we hope to implement in-language support for defining functions to support our “network as a single programmable target” philosophy.

Implementing wider support for in language type definition and variable support would greatly expand Flange’s expressive power and is a major task to support future research to solve more generalized flow scheduling problems.