One thing engineers learned long ago was to study the world around them, work with it, and emulate it in their designs. Network engineering should be no different. In a technical report from 2011, authors Thomas Meyer and Christian Tschudin from the University of Basel describe a highly elegant natural flow management method [11] that exploits much of the hard work done in the chemistry sector in chemical kinetics. They describe a scheduling approach that creates an artificial chemistry as an analogue of a queueing network, and uses the Law of Mass Action to schedule events naturally. The analysis of such networks utilizing their implementation is simplified regardless of the depth one wishes to go into. In addition, they show a congestion control algorithm based on this framework is TCP fair and give evidence of actual implementation (a relief to practitioners).
This report will discuss their paper at length with a goal of covering not only their work, but the underlying ideas. Since the paper requires knowledge of chemical kinetics, probability, queueing theory, and networking, it should be of interest to specialists in these disciplines, but a comprehensive discussion of the fundamentals glossed over in the paper would make dissemination more likely.
Just as in chemistry and physics, packet flow in a network has microscopic behavior controlled by various protocols, and macro-level dynamics. We see this in queueing theory as well--we can study (typically in steady-state to help us out, but in transient state as well) the stochastic behavior of a queue, but find in many cases that even simple attempts to scale the analysis up to networks (such as retaining memorylessness) can become overwhelming. What ends up happening in many applied cases is a shift to an expression of the macro-level properties of the network in terms of average flow. The cost of such smoothing is an unpreparedness to model and thus deal effectively with erratic behavior. This leads to overprovisioning and other undesirable and costly design choices to mitigate those risks.
Meyer and Tschudin have adapted decades of work in the chemical and physical literature to take advantage of the Law of Mass Action, designing an artifical chemistry that takes an unconventional non-work-conserving approach to scheduling. Non-work-conserving queues add a delay to packets and have tended to be avoided for various reasons, typically efficiency. Put simply, they guarantee a constant wait time of a packet regardless of the number of packets in a queue by varying the processing rate with fill level of the queue. The more packets in queue, the faster the server processes those packets.
This should actually look somewhat similar to problems seem in basic calculus courses as well. The rate of change of draining the reactant is a direct function of the current concentration.
The reaction rate $r_{f}$ of a forward reaction is proportional to the concentrations of the reactants:
$$r_{f} = k_{f}c_{A_{1}}c_{A_{1}}\cdots c_{A_{N}}$$ for a set of reactants $\{A_{i}\}$.
The figure above from the technical report shows how a small system of reactions looks in the chemical space and the queuing space. Where analysis and scheduling can get complicated is in the coupled nature of the two reactions. The servers both drain packets from queue $Y$, so they are required to coordinate their actions in some way. It's important to note here that this equivalence rests on treating the queuing system as M/M/1 queues with a slightly modified birth-death process representation.
Typically, in an M/M/1 queue, the mean service rate is constant. That is, the service rate is independent of the state the birth-death process is in. However, if we model the Law of Mass Action using a birth-death process, we'd see that the rate of service (analogously, the reaction rate) changes depending on the fill-level of the queue (or concentration of the reactant). We'll investigate this further in the next sections, discussing their formal analysis.
The notion of an formal artificial chemistry has been around for some time. There is an excellent paper by Dittrich, Ziegler, and Banzhaf that gives a survey of the work in this area[1]. Put simply, an artificial chemistry is a tuple $(\mathcal{S},\mathcal{R},\mathcal{A}) $ where $\mathcal{S} = \{s_{1},s_{2},\ldots s_{n}\} $ is a set of all valid molecules, $\mathcal{R} $ is a set of rules $r $ that describe interactions between molecules, and $\mathcal{A} $ is the reactor algorithm that determines how the set of rules in $\mathcal{R} $ is applied to a collection of molecules termed $\mathcal{P} $. $\mathcal{P} $ may be a reaction vessel, reactor, or "soup" (as Dittrich et al call it). It's also notable that $\mathcal{P} $ cannot be identical to $\mathcal{S} $. The reason given in the paper is that some molecules might be present in many exemplars, but not all.
To expand a bit more, we'll note that the rules $r \in \mathcal{R} $ all take the form $$s_{1} + s_{2} + \ldots s_{n}\longrightarrow \tilde{s}_{1}+\tilde{s}_{2}+\ldots \tilde{s}_{m} $$ where all $s, \tilde{s} \in \mathcal{S} $. These rules are fairly abstract, and don't explicitly seem to describe just a reactant to product type reaction. These can be collisions or other types of interactions. The set $\mathcal{S} $ of valid molecules presumably can be partitioned into disjoint subsets of different species of molecule as well, though the representation in [1] is more general. Regarding the reactor algorithm $\mathcal{A} $, Dittrich et al [1] give several different descriptions/approaches by which it can be defined, depending on whether each molecule is treated explicitly, or all molecules of a type are represented by a single number (frequency or concentration):According to Dittrich et al [1], the reactor algorithm $\mathcal{A} $ depends on the representation of the elements of $s_{i} $ and thus the population. Meyer and Tschudin [11] utilize the second approach, though they do not explicitly state this.
Meyer and Tschudin adapt the artificial chemistry in the previous section to suit their queuing networks in a given computer network. They add an element $\mathcal{G} $ to the artificial chemistry tuple to get an artificial packet chemistry $PC = (\mathcal{G},\mathcal{S},\mathcal{R},\mathcal{A}) $, where $\mathcal{G} $ is the digraph that gives the topology of the computer network. $\mathcal{G} $ consists of a set of nodes $V_{\mathcal{G}} $ which represent the chemical reaction vessels. (These were the $\mathcal{P} $ in the previous section.), and $E_{\mathcal{G}} $ is the set of directed arcs that represent network links connecting adjacent nodes. (That is, if flow between nodes can happen in both directions, they will be represented by two arcs. One going in one direction, one in the other.)
Here, since a molecular species is the analogue of a queue, $\mathcal{S} = \cup_{i \in V}\{S_{i}\} $. Here, $\{S_{i}\} $ is a set of all queue instances in a particular node $i $. At this point, some discussion on clarity is warranted. It is possible to have more than one queueing instance (more than one molecular species) inside each reaction vessel (here the nodes of the network). I don't think this is meant to be a disjoint union, since a reaction species can show up in more than one reaction vessel, so there may be repeats of certain species in this representation of $\mathcal{S} $ when written this way. Perhaps it's just a nitpick, but it's worth mentioning.
$\mathcal{R} = \cup_{i \in V}\{R_{i}\} $ gives all the flow relations among the queues. Here the rules $r $ take form 2 of $\mathcal{A} $: $$r \in R_{i}: \sum_{s \in S_{i}}a_{s,r}s \longrightarrow \sum_{s \in S_{i} \cup \{S_{j}\} : j \in N_{i}}b_{s,r}s $$ The reaction rules basically describe what's going on in a particular reaction vessel. We can send packets to neighboring nodes/vessels ( $N_{i} $ is the notation for the neighborhood of node $i $, or the set of adjacent nodes), or we can keep packets in the same node after the reaction is done. The reactions that send packets to neighboring nodes are transmissions. The mean reaction rate $\nu_{r} $ of each reaction is given by the Law of Mass Action as applied to forward reactions: $$\nu_{r} = k_{r}\prod_{s\in S}c_{s}^{a_{s,r}} $$ just as described in the previous section.
Figure 3 from Meyer and Tschudin [11] gives an explicit example to help solidify these abstract ideas. The network consists of 4 nodes, so $V = \{n_{1}, n_{2}, n_{3}, n_{4}\} $. Each node has a bidirectional link with its neighbors, so $E = \{n_{1}n_{2}, n_{2}n_{1}, n_{2}n_{3}, n_{3}n_{2}, n_{2}n_{4}, n_{4}n_{2}, n_{3}n_{4}, n_{4}n_{3}\} $. In this case, we only have one species of molecule (one queue) per node, so $\mathcal{S} = \{X_{1}, X_{2}, X_{3}, X_{4}\} $. The set of reactions is simply a first-order reaction per arc: $\mathcal{R} = \{r_{a,b}: X_{a} \to X_{b}: ab \in E\} $
From a review standpoint, I would have liked to see a less trivial example, such as one with multiple queues in a node, and rules that may keep packets in a node instead of just transmitting. These types of scenarios would be interesting to model this way, and demonstrate better the power of this approach.
The authors give a formal convergence proof that the example network above converges to a stable fixed point and is asymptotically stable, comparing it to the proof of a similar protocol Push-Sum(a gossip protocol in computer networks).
Here we'll recount an explicit example that illustrates the concept. If we return to Figure 1 reproduced below, we can walk through Meyer and Tschudin's scheduler implementation.
There are two queues, $X$ and $Y$. Reaction 1 (Server 1) is bimolecular: $X+Y \rightarrow Z$, so the server pulls packets from two queues to execute the service. Reaction 2 (Server 2) is unimolecular, pulling only from queue $Y$. If we assume the reaction constants $k_{1} = 1000/(\text{packet}\cdot s)$ and $k_{2} = 1000/\text{s}$, that $X$ begins with two packets in its queue, and $Y$ begins with 3 packets in its queue, then the reaction rates $\nu_{r}$, $r=1,2$ are respectively $\nu_{1} = k_{1}c_{X}c_{Y} = 1000\cdot 2 \cdot 3 = 6000$ and $\nu_{2} = k_{2}c_{Y} = 1000\cdot 3 = 3000$. The occurrence time is the reciprocal of the reaction rate, so the occurrence times $\tau_{r}$ are respectively $\tau_{1} = \frac{1}{6} ms$ and $\tau_{2} = \frac{1}{3} ms$. That means the first server executes its action first, extracting packets from both $X$ and $Y$.
Since the occurrence time of $r_{2}$ is coupled with $r_{1}$ (both servers pull from queue $Y$), the action of $r_{1}$ requires a rescheduling of $r_{2}$. After $r_{1}$ pulls a packet each from $X$ and $Y$, there is 1 packet left in $X$ and 2 in $Y$, which means we have to recalculate the rate $\nu_{2} = 1000\cdot 2 = 2000$. The occurrence time of $r_{2}$ is at ms $\frac{1}{3}$, so its time of execution hasn't arrived. But thanks for $r_{1}$'s effect, we have to rescale and reschedule the occurrence time of $r_{2}$. This is done by the following:
$$\tau_{r,\text{new}}-\frac{\nu_{r,\text{new}}}{\nu_{r,\text{old}}}(\tau_{r,\text{old}}-t_{\text{now}}) + t_{\text{now}},$$ where $(\tau_{r,\text{old}} -t_{\text{now}})$ is the time remaining between the original execution time and the current time. The multiplier in front is a scaling effect.In this example, at $t_{\text{now}} = 1/6 ms$, $r_{2}$ was supposed to go at time $1/3 ms$, but will now be prolonged.
A note here, I did the math for their specific example, and it seems off. I think the multiplier should be as I've written above. The authors wrote the reciprocal, which prolongs too far.
There are other timed scheduling algorithms utilized in computer networking, such as Earliest Deadline First, which require tagging each packet with a timestamp. This scheduler does not require such an imposition.
Here, the authors describe what they term as a chemical control plane that is intended to avoid the messy necessity of sending packets through a complex queueing network in order to shape packet flow as desired. The control plane takes advantage of concepts in enzymatic chemical reactions in order to control flow. This is a different application than the flow networks discussed thus far (as I understand it).
Here the forwarding plane which executes actions is separated from the control plane which will shape the flow of packets in the forwarding plane.
The chemical control plane will dynamically determine the service rates; the servers do not have them predefined. There are some number of FIFO queues $n$, one for each type of ingress packet flow and they are drained by one server each, representing a unimolecular reaction. In the control plane, each queue is represented by an input species $X_{i}$ and product species $X_{i}^{*}$. The chemical reaction network lives abstractly in the control plane, which is designed by a traffic engineer and can look like any digraph or network he wishes.
Here we note the difference here between the prior sections, which dealt with physical flows modeled by a chemical reaction network, and moving the chemical reaction network to an abstract control plane. The queues now are not necessarily physically linked together, but we can choose to couple them abstractly to shape traffic.
When a packet physically enters one of the queues, the control plane injects one instance of the corresponding molecule species into the abstract network. The scheduler described previously is implemented and eventually an instance of the output species is generated. Once this happens, the corresponding server in the forwarding plane physically processes the packet and dequeues the next. The advantage here is that the abstract molecules in the control plane have no payload, so implementation of this model only requires storing an integer value for each species that keeps track of the number of packets in each queue. This allows analysis of behavior at the design phase.
In the simplest case, a unimolecular reaction $X \to X^{*}$ in the chemical control plane acts like a low-pass filter to the packet flow, smoothing bursts with high frequency components. If the differential equation $\dot{x} = \lambda-kx$ that approximates a unimolecular reaction is converted to the frequency domain via the Laplace transform, the transfer function $F(s)$ has a cut-off frequency at $k$, the reaction constant:
$$F(s) = \frac{\mu(s)}{\lambda(s)} = \frac{k}{s+k}$$That is, higher-frequency flows will be attenuated, much like dark glasses do with sunlight. Applying this filter at an ingress point of a network leads to less chaotic traffic patterns, but with a cost of a delay $\frac{1}{k}$ and memory to buffer the packets. Therefore, the mean queue length for this single queue will grow proportionally with the delay and flow rate. That is, $\hat{x} = \frac{\lambda}{k}$.
Another consideration of the LoMA queues described by Meyer and Tschudin that differs from the standard M/M/1 queuing models is that the service rate is ultimately unbounded (for infinite capacity queues/networks), since it is proportional to the queue length. This is undesirable to allow in a network, and thus the authors borrow from biological systems and design an abstract enzymatic reaction to limit the rate of packet flow.
In biological systems, enzymes bind to reactant molecules X, called substrates in order to prevent a particular molecule from reacting immediately. Some amount of enzyme molecules E exist, and they can either exist free-form or bound in a complex (EX). The more enzyme molecules in bound form, the slower the rateof transmission grows for an increasing arrival rate. At equilibrium, the influx and efflux of substrate-enzyme complex molecules are equal according to Kirchoff's Law, so
$$k_{w}c_{X}c_{E} = k_{s}c_{EX}$$ Take a look at Figure 8 above in the chemical control plane to see this action. The number of enzymes is constant, so $c_{E} + c_{EX} = e_{0}$, which yields the Michaelis-Menten equation, expressing the transmission rate $\mu$ in terms of the queue length $c_{X}$. $$\mu = \nu_{\max}\frac{c_{X}}{K_{M} + c_{X}},$$which yields a hyperbolic saturation curve. $\nu_{\max} = k_{s}e_{0}$, and $K_{M} = \frac{k_{s}}{k_{w}}$ and specifies the concentration of $X$ at which half of $\nu_{\max}$ is reached.
When the queue length at queue $X$ is high, the transmission rate converges to $\nu_{\max}$, and behaves like a normal unimolecular reaction when queue length is short.
The authors also extend this model to handle dynamic changes to the topology of the queuing network, which means that instances of queues and flow relations can be generated "on the fly,'' as it were. Tschudin[13] has created an executable string and multiset rewriting system called Fragletsthat allow for the implementation and running of protocols based on the ideas put forth thus far. They describe in the paper how to implement explicitly the enzymatic rate-limiter in the chemical control plane in Figure 8. In this implementation, rather than flow interactions being static and determined at the design phase, each fraglet (packet) sorts itself into a queue. After a packet is serviced, the header of a fraglet is treated as code, allowing a packet to determine its route comparable to active networking. The relationship between the abstract model and execution layer remains, which allows a mathematical model of the behavior of a Fraglets implementation to be generated automatically, and a queuing network to be design and then realized easily in Fraglets language.
As a final application of chemical networks, the authors combine LoMA-scheduled queues and flow-filtering patterns to schedule segments of a transport protocol to control congestion. To illustrate, they re-implement the additive increase/multiplicative decrease of the congestion avoidance mode of TCP-Reno. The congestion control algorithm reacts to packet loss automatically and naturally.
The reproduced figure above shows how the chemical congestion control is implemented as a chemical reaction network (and by extension, a queueing network).
Figure 12 shows the only two motifs provided by the authors. One for rate limiting (a) and the other bimolecular reaction to compute the difference between arrival rates for two queues. The concept of using these as design elements is extremely intriguing, and it was unfortunate that the authors did not choose to expand this further.