Exploiting Chemistry for Better Packet Flow Management 2: Formal Model

# Exploiting Chemistry for Better Packet Flow Management 2: Formal Model

This post is the second breaking down a report/review of a technical report by Meyer and Tschudin [11] that modifies the formal notion of an artificial chemistry and creates an artificial packets chemistry with the goal of designing better flow management by exploiting the natural behavior of chemical reactions.

Note: for those more interested in the application and implementation review and discussion, this section can be skipped.

## Formal Model of Artificial Packet Chemistry

### Artificial Chemistry

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}$.1

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):

1. Stochastic Molecular Collisions.  Every single molecule is worked with, where a sample of molecules from the reaction vessel $\mathcal{P}$ is drawn and the algorithm checks to see if a particular rule $r \in \mathcal{R}$ applies.
2. Differential Rate Equations: This approach seeks to describe the dynamics of a chemical system using concentrations of molecular species. The rules under this algorithm take a species approach: $$r: a_{1}s_{1} + a_{2}s_{2} + \ldots a_{N}s_{N} \longrightarrow b_{1}s_{1} + b_{2}s_{2} + \ldots + b_{N}s_{N}$$
Here, the $s_{i}$‘s are species, not individual molecules. The coefficients are stoichiometric factors of the reaction. They are simply indicator functions to denote whether species $s_{i}$ is a reactant or product. That is $a_{i} = 1$ if and only if $s_{i}$ is a reactant in the rule $r$, and $b_{i} = 1$ if and only if $s_{i}$ is a product in the rule $r$. It is this form of $\mathcal{A}$ that Meyer and Tschudin [11] utilize in their packet chemistry.

The change of overall concentration (concentration denoted $c_{s_{i}}$) is given by a system of differential equations
$$\frac{\text{d}c_{s_{i}}}{\text{d}t} = (b_{i}-a_{i})\prod_{j=1}^{N}c_{s_{j}}^{a_{j}}, \quad i=1,\ldots,N$$
according to the Law of Mass Action discussed earlier. There may be multiple rules/reactions $r \in \mathcal{R}$ that affect the concentration of species $s_{i}$, so
$$\frac{\text{d}c_{s_{i}}}{\text{d}t} = \sum_{r\in \mathcal{R}}\left[(b_{i}^{r}-a_{i}^{r})\prod_{j=1}^{N}c_{s_{j}}^{a_{j}^{r}}\right], \quad i=1,\ldots,N$$
3. Others: There are other options, such as metadynamics (where the number of species and thus differential equations may change over time), mixed approaches, or symbolic analysis of the differential equations. As this article would be far too cumbersome to discuss these, they are omitted, but may be found in [1].

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.

### Artificial Packet Chemistry

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.2

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.

## Continuation

The next post in the series will discuss the mathematical analyses of the artificial packet chemistry described here.

## References

1. Dittrich, P., Ziegler, J., and Banzhaf, W. Artificial chemistries – a review. Artificial Life 7(2001), 225–275.
1. Feinburg, M. Complex balancing in general kinetic systems. Archive for Rational Mechanics and Analysis 49 (1972).
2. Gadgil, C., Lee, C., and Othmer, H. A stochastic analysis of first-order reaction networks. Bulletin of Mathematical Biology 67 (2005), 901–946.
3. Gibson, M., and Bruck, J. Effcient stochastic simulation of chemical systems with many species and many channels. Journal of Physical Chemistry 104 (2000), 1876–1889.
4. Gillespie, D. The chemical langevin equation. Journal of Chemical Physics 113 (2000).
5. Gillespie, D. The chemical langevin and fokker-planck equations for the reversible isomerizationreaction. Journal of Physical Chemistry 106 (2002), 5063–5071.
6. Horn, F. On a connexion between stability and graphs in chemical kinetics. Proceedings of the RoyalSociety of London 334 (1973), 299–330.
7. Kamimura, K., Hoshino, H., and Shishikui, Y. Constant delay queuing for jitter-sensitive iptvdistribution on home network. IEEE Global Telecommunications Conference (2008).
8. Laidler, K. Chemical Kinetics. McGraw-Hill, 1950.
9. McQuarrie, D. Stochastic approach to chemical kinetics. Journal of Applied Probability 4 (1967), 413–478.
10.  Meyer, T., and Tschudin, C. Flow management in packet networks through interacting queues and law-of-mass-action-scheduling. Technical report, University of Basel.
11.  Pocher, H. L., Leung, V., and Gilles, D. An application- and management-based approach to atm scheduling. Telecommunication Systems 12 (1999), 103–122.
12. Tschudin, C. Fraglets- a metabolistic execution model for communication protocols. Proceedings of the 2nd annual symposium on autonomous intelligent networks and systems (2003).