Deciding stability under FIFO in the adversarial queuing model in polynomial time

Deciding Stability under FIFO in the Adversarial Queuing model in polynomial time Maria J. Blesa Report LSI–05–03–R 2nd February 2005 Deciding Stability under FIFO in the Adversarial Queuing model in polynomial time? Maria J. Blesa ALBCOM research group Dept. Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Ω-213 Campus Nord, E-08034 Barcelona, Spain [email protected] Abstract. In spite of the importance of the fifo protocol and the research efforts invested in obtaining results for it, deciding whether a given network is stable under fifo was still an open question. In this work, we address the general case of this problem and try to characterize the property of stability under fifo in terms of network topologies. We show that this property is decidable in polynomial time. ?Partially supported by the FET Programme of the EU under contract number IST-2001-33116 (FLAGS), and by the Spanish CICYT projects TIC-2001-4917-E and TIC-2002-04498-C05-03 (TRACER). ALBCOM states for “Algorithms, Bioinformatics, Complexity and Formal Methods”,http://albcom.lsi.upc.edu. III 1 Introduction Since the emergence of computer networks, protocols were used for the establishment of ordered communications among computers. Communication takes place at different levels: low level protocols define for example the bit- and byte-ordering, their transmission, and the error detection and correction of the bit stream; high level protocols deal for example with the data packet formatting, the packet routing and the packet scheduling. In this paper, we are interested in this latter functionality, in which the protocol (also called scheduling policy) determines the order in which the packets requiring to cross a link are scheduled to be forwarded. Most scheduling protocols aim at moving information across a network in an efficient and reliable manner. This often requires congestion and flow control, error detection and correction, and handshaking to coordinate the information transfer. Most network communication protocols are implemented as part of the operating system on the computers wishing to communicate. The first-in-first-out (fifo) protocol is still one of the most popular, important and effective scheduling policies, in spite of its simplicity. The fifo protocol schedules queued packets according to a local criterion in which the highest priority is given to the packet that has arrived first in the queue. This locality property makes the fifo protocol easy to be implemented. Appropriate models to study networking systems that implement specific communication protocols are needed. Those models could help us to understand better the dynamics of nowadays’ communication networks, and therefore to detect and overcome the conditions leading to undesirable negative effects, as well as helping on their further prevention. One of those undesirable negative effects is the lack of stability. Stability refers to the fact that the number of packets in the system remains bounded1as the system dynamically evolves in time. Stability is studied in relation to the three main components forming a synchronous communication system (G,A,P): the network G, the traffic pattern defined by A, and the protocol P.Networks are modeled by directed graphs in which the nodes represent the hosts, and the arcs represent the links between those hosts. The traffic pattern controls where and how packets join the system and defines their trajectory. The protocols considered are usually greedy.2 A strongest notion of stability is that of universal stability. Universal stability can be addressed from the network or from the protocol point of view. A network Gis universally stable if, for any protocol and any traffic pattern, the resulting system is stable. A protocol Pis universally stable if, for any network and any adversary the resulting system is stable. According to the classification introduced in [4], we will also differentiate and refer to the property of stability in the case in which packets follow simple paths as simple-path stability, leaving then the term stability to refer to the case in which packets follow paths.3 1This bound, which can be a function of the system parameters, is not dependent on time. 2(Store and forward) greedy protocols are those forwarding a packet across a link ewhenever there is at least one packet waiting to traverse e. Three types of packets may wait to traverse a link in a particular instant of time: the incoming packets arriving from adjacent links, the packets injected directly into the link, and the packets that could not be forwarded in previous steps. At each time step, only one packet from those waiting is forwarded through the link; the rest are kept in a queue at the link. Greedy protocols are also called work-conserving protocols. 3We consider a path through a digraph a traversal of consecutive vertices along a sequence of arcs, in which repeated edges (but no vertices) within the path are permissible. When there are no repeated vertices in the path (and therefore no edges either), then it is called a simple path. IV The Adversarial Queueing Theory (aqt) model proposed by Borodin et al. [7] has become an important model to study stability issues in packet-switched communication networks. These models have been shown to be good theoretical frameworks for describing the traffic pattern in both connectionless networks (such as the Internet) and short-term connection networks, as well as connection-oriented networks (such as atm networks). Adversarial models allow to analyze the system in a worst-case scenario, since they have replaced traditional stochastic arrival assumptions in the traffic pattern by worst-case inputs. The aqt model considers the time evolution of a packet-routing network as a game between an adversary, which produces the traffic pattern, and a queueing policy. The system is considered to be synchronous. At each time step the adversary may inject a set of packets to some of the nodes. For each packet, the adversary specifies the route that it must traverse (static routing) before arriving to its destination and disappear from the system. If more than one packet wishes to cross an edge eat the same time step, then the queueing policy chooses exactly one of these packets. The remaining packets wait in the queue. This game then advances to the next time step. The goal of the adversary is to try to prevent the protocol from guaranteeing load and delay bounds. On the contrary, the main goal of the model is to study conditions for stability of the network under different protocols. In order not to trivially overload the system and in order to be able to guarantee delay bounds, it is necessary to restrict the traffic arriving to the network. The constraints on the traffic pattern must ensure that, over long periods of time, the maximum traffic injected in a link is roughly the amount of traffic that the link can forward. Two parameters (r, b) constraint an adversary in the aqt model, where b≥0 is the burstiness and 0 <r<1 is the injection rate. Let Ne(I) be the number of packets injected by the adversary in a time interval I, whose path require to traverse a particular edge e. The adversary must obey the following (leaky-bucket) constraint: Ne(I)≤ dr|I|e +b. (1) Recent research on stability has mainly considered the aqt model and has put special interest in the fifo protocol (see, e.g., [7,5,8,17,18,9,6,19]). Our motivations and contributions. Universal stability of networks is a non-trivial property; since it is a predicate quantified over all protocols and adversaries, it might at first appear that it is not a decidable property. One of the deepest results in the context of network stability in the adversarial queueing model establishes that, to the contrary, this is not the case [5]. The question of characterizing networks that are universally stable, and algorithmically recognizing such networks, naturally arises next. This question was also recently answered in [4] by fully characterizing the property under different network representation and considering different restrictions on the packet trajectories. Moreover, in the same work it is shown that deciding universal stability of networks requires polynomial time. Concerning the protocol point of view, it is known that ftg,nfs,sis and lis are universally stable, while fifo,lifo,ntg and ffs are not [5].4For those queueing polices which are not universally stable, a weaker notion of stability is addressed, that of the stability under a protocol. 4The protocol last-in-first-out (lifo) gives priority to the packet which entered the queue the latest. Concerning injection times, shortest-in-system (sis) gives priority to the packet introduced last into the system, while longest-in-system (lis) gives it to the one that has been in the system the longest. Concerning the distance to the destination, nearest-to-go (ntg) assigns highest priority to the packet that is closest to its destination and ftg (Furthest To Go) to the packet that is farthest. Similarly, nearest-from-source (nfs) and farthest-from-source (ffs) consider the distance to the source. V   e1 e2 f Fig. 1. Digraph U1for which still many questions about its stability are not solved. The (open) characterization proposed in this work revolves around it. Here the problem is to decide which networks are stable, and which are not, under a fixed queuing policy P. In the best case, a characterization of stability under the protocol Pcan be obtained. To the best of our knowledge, only two results are known in this sense: Deciding stability under the ntg-lis5and ffs protocols is polynomially solvable and it is, moreover, equivalent to deciding universal stability of networks [4,1]. In this paper we address the problem of deciding stability under the fifo protocol. In spite of the importance of this property and this protocol, the aspects concerning its decidability and complexity were still an open question . In this work, we show that the property of stability under fifo is decidable in polynomial time. Taking the characterization of (network) universal stability as starting reference, we propose an (open) characterization of the stability under fifo. The characterization is composed by two candidate sets of forbidden subgraphs. The eligibility of one or the other candidate set as the decisive characterization depends on the stability of the digraph U1(see Figure 1). In the case that U1is unstable under fifo, the characterization would be the same as the characterization of the digraphs that are universally stable [4]. This would have some nice implications since, in the case this holds, a digraph would be universally stable if and only if it is stable under fifo. In spite of the simplicity of the network topology in U1, some important questions about it remain still open nowadays. One of these particular questions is concerned with its stability under the fifo protocol. Organization. The paper is organized as follows. In Section 2 we introduce some preliminaries of the work; this includes a review of the results existing in the literature which are concerned with stability under fifo, and also the notation used in the forthcoming of the paper. In Section 3, the family of digraphs which are stable under fifo are presented. Also in this section, the family of digraphs which are not stable are introduced by its minimal representants. The property of stability under fifo is characterized in Section 4 in terms of those unstable minimal representants. In the same section, a polynomial-time algorithm is given for deciding the property of stability under the fifo protocol. The work concludes in Section 5, where some open questions as well as some possible extensions of the work are pointed out. Most proofs of the lemmas and theorems in this work are posted as appendix. 2 Preliminaries The first-in-first-out (fifo) greedy protocol is probably one of the most commonly used scheduling protocols. fifo is used in many contexts in computer environments, either internally (e.g., in operating systems to process I/O device interruptions or information exchange between processes) or externally (e.g., as communication protocol for information exchange between computers). One of its main advantages, specially when implementing it, is that its criterion to 5The protocol ntg-lis works as ntg, but solves ties using the lis protocol. VI schedule packets is completely based on local properties. In the fifo protocol, highest priority is given to the packet that has arrived first in the queue. Observe that, when two packets arrive to the queue at the same time then they have to be queued in some order, which we will assume that is decided arbitrarily by the adversary. 2.1 Previous results on FIFO in the AQT model Due to its relevance, much attention has been put on the study of stability conditions in aqt under the fifo protocol. Already the pioneering work of Borodin et al. [7] showed that ring topologies are not stable under fifo for the extreme injection rate r= 1. It is however of higher interest to find bounds when adversaries work in underloaded conditions, i.e., when their injection rate r < 1. Thus, the consecutive improvement of the lower bounds for instability under fifo was one of the research subjects in the last years. As time and research advanced, this lower bound was dropping from r≥0.85 [5], to r≥0.84 [11], r≥0.8357 [8], r≥0.771 [17], r≥0.749 [16], and finally to r > 0.5 [19]. A further step was done recently, when fifo was shown to be unstable at arbitrarily low rates [6,15]. Meanwhile, the upper bound for the stability of fifo was also improved from r < 1/9 [17] to r < 0.1428 [8]. The existence of a network-dependent upper bound was shown in [8], which was recently generalized to r≤1/d [19,9], where dis the length of the longest route traversed by any packet. In spite of the importance of this protocol and all these results, deciding whether a given network is stable under fifo remains still an open question in many cases. This work aims at doing a step forward into solving the problem of deciding stability in the aqt model under the fifo protocol and study its complexity. As we have said before, the decisive characterization depends on the stability of the digraph U1(see Figure 1). 2.2 Graph subdivision operations In the following, we use standard graph terminology to denote the following digraphs: directed k-cycles,acyclic digraphs, and unicyclic digraphs. A directed k-cycle is a directed cycle with k vertices, where k≥2. A unicyclic digraph is a digraph that contains only one cycle. We will characterize the property of stability under fifo in terms of a family of forbidden subgraphs. To this aim, we first need to identify the families of digraphs which are stable under this protocol. Then the simplest digraphs which are not stable should be identified. The family of the digraphs which are not stable under fifo will be then defined by iteratively applying subdivision operations to those simplest digraphs. We consider the following subdivision operations: – The subdivision of an arc (u, v) in a digraph Gconsists in the addition of a new vertex w and the replacement of (u, v) by the two arcs (u, w) and (w, v). – The subdivision of a 2-cycle (u, v), (v, u) in a digraph Gconsists in the addition of a new vertex wand the replacement of (u, v), (v, u) by the arcs (u, w), (w, u), (v, w) and (w, v). Then, given a digraph G, we will denote as E(G) the family of digraphs formed by Gand all the digraphs obtained from Gby successive arc or 2-cycle subdivisions. Note that, a strongly connected digraph remains so when applying arc or 2-cycle subdivisions to it. In the following, we will be using digraphs and networks as synonyms. All the digraphs considered in this paper are strongly connected and they may have multiple edges (arcs) but no VII loops.6We consider that a packet transmitted over those digraphs follows a predefined path. To keep lighter the notation, a path is specified by the sequence of its edges or by the concatenation of subpaths. Moreover, the names used to denote the digraphs and their edges correspond to the ones depicted in Figure 2. 3 Stability of digraphs under FIFO In this section, we show which digraphs are stable under fifo as well as those simplest digraphs which are not stable under this protocol. By applying subdivision operations to those simplest unstable digraphs the whole family of digraphs which are not stable under fifo will be determined. All directed acyclic graphs7and (isolated) directed cycles on any number of vertices are known to be universally stable [7,5], thus being also stable under the fifo protocol. Let us re-write this consequence as Lemma 1. Lemma 1 ([7,5]). All acyclic digraphs and k-cycles (where k≥2) are stable under fifo. This property is maintained when acyclically connecting digraphs which are stable under fifo. Given two digraphs G1and G2, let us denote as G1→2the family of digraphs formed by joining G1and G2with arcs that go only from G1to G2. Lemma 2. If digraphs G1and G2are stable under fifo, then so is any graph G ∈ G1→2. Proof. Assume that the adversary working against Ghas rate rand burstiness b. Any packet injected into G1by this adversary will get out of G1within a bounded number of time steps t1, because G1is stable under fifo. Some of the packets leaving G1might join G2. Let us consider a time interval of t2steps starting right after the t1time steps mentioned before. The packets joining G2during that t2time steps must have been introduced in the system during the last t1+t2steps; moreover, there are at most r(t1+t2) + bof those packets. We want to show that all the packets coming from G1together with the packets injected directly in G2could have been generated by an adversary working only against G2. Consider that such an adversary has rate 1 > r0> r and burstiness b0≥b. During any interval t≥t2, the total amount of packets introduced into G2would be r0t+b0. In order for those packets to be generated by the mentioned adversary, it must hold that r0t+b0=r0t+b0−((r0−r)t2+b0−rt1−b), which holds when considering t2=rt1/(r0−r). As a consequence of the previous lemma we have, Corollary 1. All unicyclic digraphs are stable under fifo. Corollary 2. A digraph Gwith more than one cycle is stable under fifo if and only if no pair of cycles shares vertices, i.e., if and only if the cycles are acyclically connected by directed paths. Theorem 1. A digraph Gis stable under fifo if and only if all its strongly connected components are stable under fifo. 6Multiple edges share the same pair of different endpoints. The endpoints of a loop is the same vertex. 7Note that this includes directed trees and multi-trees, i.e., directed trees with single arcs and multi-arcs. VIII   e1 e2 f U1  e1 f2 f1 e2 U2   e1 e2 f U1 1 e3   e1 e2 U2 1 f1 f2    e2 e1 f2f1 U3 1    e1 f e21 e22 U4 1 Fig. 2. Minimum forbidden subgraphs characterizing stability under fifo. The two candidate sets to consider are either {U1,U2}or U1 1,U2 1,U3 1,U4 1,U2; the former would characterize the stability under fifo in the case that U1is not stable under that protocol, while the latter would characterize it in the case that U1is stable under fifo. In a strongly connected digraph, every vertex can be accessed from any other vertex of the digraph. Note that all the directed acyclic digraphs as well as all the digraphs formed by acyclic connections are not strongly connected. However, in the context of communication networks strongly connected topologies are of highest interest. Beyond the directed cycle, the next networks to consider are then the digraphs U1and U2depicted in Figure 2, which are the smallest non-unicyclic strongly connected digraphs, i.e., the smallest strongly-connected digraphs with more than one cycle. In the following, we show that neither the digraph U2, nor any of its extensions, are stable under fifo. Lemma 3. The digraphs in E(U2)are not stable under fifo. However, it remains still an open question (as it was already pointed out in [4]) whether the digraph U1is stable under fifo. Instead, let us consider the digraphs U1 1,U2 1,U3 1and U4 1 depicted in Figure 2, which are the next strongly connected digraphs to consider after U1(in terms of their size). Digraphs U1 1and U2 1are obtained from U1when considering multi-edges, while digraphs U3 1and U4 1are obtained from U1when subdividing arcs. The digraphs that result from 2-cycle subdivisions of U1contain U2as a subgraph, and so they can be made unstable under the fifo protocol. Although no result concerning the stability of U1under fifo is known, we show in the following that neither digraphs U1 1,U2 1,U3 1or U4 1, nor any of their extensions are stable under fifo. Lemma 4. The digraphs in EU1 1∪ E U2 1∪ E U3 1∪ E U4 1are not stable under fifo. However, a quite high injection rate (r≥0.929, see appendix) is needed to produce instability in this networks, which indicates that, although possible, it is not “easy” to make a system unstable under fifo with these underlying topologies. This behavior was already observed while trying to improve the lower bound for the instability of the fifo protocol [5,11,8,17,16,19]. Observe that, by considering the family of digraphs composed by U2,U1 1,U2 1,U3 1,U4 1and their extensions, the only graphs which are not included are those which have as subgraph a graph in E(U1)\E(U2)∪ E U1 1∪ E U2 1∪ E U3 1∪ E U4 1, i.e., those whose strongly connected components are exactly U1. If U1is stable under fifo, then those digraphs are also because of Lemma 2; if U1is not stable under fifo, then those digraphs can be made also unstable but, in this case, they would not be the smallest forbidden subgraphs because they contain U1. IX 4 Characterizing stability under FIFO In this section two candidate sets of forbidden subgraphs are proposed for the characterization of the stability under fifo. The choice of the right candidate has a penchant for one subset or the other depending on the stability of U1. Whatever the decisive characterization is, we can state the stability under fifo can be decided in polynomial time. Theorem 2. If the digraph U1is not stable under fifo, then any digraph Gis stable under fifo if and only if it does not contain as subgraph a digraph from E(U1)∪ E (U2). Otherwise, if the digraph U1is stable under fifo, then any digraph Gis stable under fifo if and only if it does not contain as subgraph a digraph from EU1 1∪ E U2 1∪ E U3 1∪ E U4 1∪ E (U2). Proof. If the digraph U1is not stable under fifo then, according to Theorem 3 and the fact that the instability of a subgraph implies the instability of the whole digraph, no digraph G containing as subgraph a digraph from E(U1)∪ E (U2) is not stable. If Gdoes not contain as subgraph a digraph from E(U1)∪E (U2) then all its strongly connected components must consist of at most one simple directed cycle. Therefore, Gis stable under fifo according to Lemma 1 and Theorem 1. If the digraph U1is stable under fifo then, according to Lemmas 3 and 4, together with the fact that the instability of a subgraph implies the instability of the whole digraph, no digraph Gcontaining as subgraph a digraph from EU1 1∪ E U2 1∪ E U3 1∪ E U4 1∪ E (U2) is stable. If, on the contrary, Gdoes not contain as subgraph a digraph from that set, then all its strongly connected components either consist of at most one simple directed cycle (and then, according to Lemma 1 and Theorem 1, Gwould be stable under fifo), or they contain as a subgraph the digraph U1(which here we have assumed that is stable under fifo). This result can be stated in terms of digraphs’ properties. Corollary 3. If the digraph U1is not stable under fifo, then a strongly connected digraph G is stable under fifo if and only if Gis a directed k-cycle (on any number of vertices k≥2). Otherwise, if the digraph U1is stable under fifo, then a strongly connected digraph Gis stable under fifo if and only if Gis a directed k-cycle (k≥3) or a 2-cycle with at most one multi-edge. Then, instead of detecting the proposed forbidden subgraphs by means of subgraph homeomorphism (which would be NP-complete [10]), the stability of digraphs under fifo can be decided in polynomial time by detecting the proposed forbidden subgraphs in terms of the digraphs’ properties outlined in Corollaries 1, 2, and 3. Theorem 3. The stability under fifo of a given digraph can be decided in polynomial time. Proof. Algorithms 1 and 2 check stability under fifo of a given strongly connected digraph Gaccording to Corollaries 1, 2, and 3. The total execution time of each of the algorithm is polynomial. Algorithm 1 would be applied in the case that U1is not stable under fifo, while Algorithm 2 would be applied in the case that U2is stable under fifo. According to Theorem 1, the strongly connected components of the digraph need to be computed first. Thus the result follows by combining the computation of the strongly connected components of the given digraph (which requires polynomial time) either with Algorithm 1, or with Algorithms 2. IV are desynchronized with the other single injections), and r5spackets requiring only e3remain queued in that edge. Round 6: for r5ssteps, the adversary introduces r6ssingle injections of the form (e3). These injections get mixed with the injections queued from the previous round. At the end of the sixth round, there are r6s+r5s/(r+ 1)packets queued in e3and requiring only that edge. The adversary described here achieves that the system (U1 1,fifo) is not stable whether r5+r6+r7> r + 1. This holds for any r≥0.929. Digraphs in EU1 1:Let Gbe a proper extension of U1 1, i.e., a G ∈ E U1 1\ U1 1described at Figure 4(b).8Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. In G ∈ E U1 1\ U1 1, let |α| ≥ 1, |β| ≥ 1, |γ| ≥ 1, |δ| ≥ 1. We define an adversary with an strategy analogous to the adversary used for U1 1by extending the trajectories of the packets according to the corresponding current paths. At the beginning there are spackets queued in the first edge of δ, which require to traverse the path (δe3). Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (δe3αfβe1), which get all blocked at the first edge of the path δ. Round 2: for rs steps, the adversary injects r2spackets of the form (δe3αfγe2) and r2spackets of the form (βe1). The former are all blocked at the first edge of the path δ. The latter get mixed with the packets from the previous round and, at the end, there are r2s−r(|δ|+|α|) packets all waiting to traverse the path (βe1). Round 3: for r2ssteps, the adversary injects r3spackets of the form (βe1) and r3spackets of the form (αfγe2). From the former, r3s−r(|δ|+|α|) remain blocked at the begining of the path β, while the latter get mixed with the packets from the previous round flowing trough δand e3. From that mixure, a total amount of r3s−r|δ|packets of the form (αfγe2) will remain at the begining of the path α. Round 4: for r3s−r|δ|steps, the adversary injects r4s−r2|δ|packets of the form (βe1αfδe3) and r4s−r2|δ|packets of the form (γe2). From the former, r4s−r2|δ| − r(2|δ|+|α|) packets remain blocked at the begining of β, while the latter get mixed with packets from the previous round flowing from αthrough f. A total quantity of r4s−r2|δ| − r|α|requiring to traverse the path (γe2) remain queued in the first edge of γat the end of the round. Round 5: for r4s−r2|δ| − r|α|steps, the adversary injects r5s−r3|δ| − r2|α|packets of the form (γe2). These injections get all blocked at the origin. Moreover, the adversary injects r5s−r3|δ|− r2|α|packets of the form (αf) and, desynchronized one step in time with these ones, it injects another r5s−r3|δ| − r2|α|packets of the form (δe3). The injections with path (αf) get mixed with the packets from the previous round. The mixure is composed by (r(r5s−r3|δ| − r2|α| − r|β|))/(r+ 1) packets of the form (αf) and (r4s−r2|δ|−r(2|δ|+|α|)−|β|)/(r+1) of the form (αfδe3). The injections in δe3get also mixed with the packets from the previous round (because they are desynchronized with the other single 8Observe that the digraphs that result from 2-cycle subdivisions of U1 1contain U2as a subgraph, and so they can be made unstable under the fifo protocol by an adversary that only uses the U2subgraph and uses an strategy as described in Lemma 6. V injections), and r4s−r2|δ| − r(2|δ|+|α|)− |β| − |α| − ((r5s−r3|δ| − r2|α| − r2|β|)/(r+ 1)) packets9requiring to traverse still the path (δe3) remain queued at the begining of δ. Round 6: for r5ssteps, the adversary introduces r6ssingle injections of the form (δe3). These injections get mixed with the injections queued from the previous round. At the end of the sixth round, there are r4s−r2|δ| − r(2|δ|+|α|)− |β| − |α| − ((r5s−r3|δ| − r2|α| − r2|β|)/(r+ 1)) + r6s−r5spackets queued at the begining of δwhich require to traverse δin order to rearch their destination at edge e3. The adversary described above only uses path trajectories and makes any digraph G ∈ E U1 1\ U1 1unstable when r4s−r2|δ| − r(2|δ|+|α|)− |β| − |α| − r5s−r3|δ| − r2|α| − r2|β| r+ 1 +r6s−r5s > s. (3) Note that the relations between |β|,|γ|and |δ|are not important for the statement to hold because the role of the paths (δe3), (γe2) and (βe1) can be exchange indistinctly. Assuming the necessary conditions to assure that at every round the number of queued packets is positive, independently of the relation of |α|with the length of the other paths β,γand δ, and also independently of which are the values of those lengths, the statement can hold for a big enough s, i.e., an injection rate rcan be found such that the inequality in (3) holds. Lemma 8. The digraphs in EU2 1are not stable under fifo. Proof. Since we consider paths in which every vertex can be visited more than once but every edge can only be traversed once, then the same adversaries as the ones described in Lemma 6 for the digraph U2and the family E(U2) can make any system (G,fifo), where G ∈ E U2 1, not to be stable. Lemma 9. The digraphs in EU3 1,fifoare not stable under fifo. Proof. We first prove that the system (U3 1,fifo) can be made unstable. Then, we show that the systems with a network which is a proper extension of U3 1, can also be made unstable under the fifo protocol. Digraph U3 1:At the beginning there are spackets queued in f1requiring to traverse only edge f1. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (f1f2e2). These injections will all get blocked in f1. Round 2: for rs steps, the adversary injects r2spackets of the form (f1f2e1) and r2spackets of the form (e2). Since the packets injected in the previous round flow now, the former will remain all blocked in f1and the latter will mix in e2. From this mix, r2spackets of the form (e2) will remain in the queue of e2. Round 3: for the next r2ssteps, the adversary injects r3spackets of the form (e2) and r3s packets of the form (f2e1). The former will be blocked in e2by the packets there from the 9((r5s−r3|δ| − r2|α| − r2|β|)/(r+ 1)) is the quantity of injections of the from (αf) that flow through, i.e., that are not blocked at their origin. VI previous round. The latter will mix at f2with the packets flowing from the previous round and, at the end, r3sof them will remain queued in f2with path (f2e1). Round 4: for the next r3ssteps, the adversary injects r4spackets of the form (e2) and r4s packets of the form (f2e1f1). Both sets of injections blocked in the first edge of their paths by the queued injections from the previous round. Round 5: for the next r4ssteps, the adversary injects r5spackets of the form (e2f1) and r5s packets of the form (e1). The former remain queued in e2. The later mix in e1with the injections from the previous round (which are flowing in this round), and queue a total amount of r5s packets in the following proportions: r6 r+1 sof the form (e1), and r5 r+1 sof the form (e1f1). Round 6: for the next r5ssteps, the adversary injects r6spackets of the form (f1). These injections get mixed with the injections queued from the previous round. At the end of the sixth round, there are r6s+r5s r+1 packets queued in f1and requiring only that edge. The adversary described here achieves that the system (U3 1,fifo) is not stable whether r6+r5 r+1 s > s, i.e., whether r5+r6+r7> r + 1. This holds for any r≥0.929. Digraphs in EU3 1:Let Gbe a proper extension of U3 1, i.e., a G ∈ E U3 1\ U3 1described at Figure 4(b).10 Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. In G ∈ E U3 1\ U3 1, let |α| ≥ 1, |β| ≥ 1, and |γ| ≥ 1. We define an adversary with an strategy analogous to the adversary used for U3 1by extending the trajectories of the packets according to the corresponding current paths. At the beginning there are spackets queued in f1requiring to traverse only edge f1. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (f1αf2γe2). These injections will all get blocked in f1. Round 2: for rs steps, the adversary injects r2spackets of the form (f1αf2βe1) and r2spackets of the form (γe2). Since the packets injected in the previous round flow now, the former will remain all blocked in f1and the latter will mix in the first edge of γ. From this mix, r2s−r|α| packets with trajectory (γe2) will remain in the queue of the first edge in γ. Round 3: for the next r2ssteps, the adversary injects r3spackets of the form (γe2) and r3s packets of the form (f2βe1). From the former, r3s−r|α|will be blocked in the first edge of γ by the packets there from the previous round. The latter will mix at f2with the packets flowing from the previous round and, at the end, r3s−r|α|of them will remain queued in f2with trajectory (f2βe1). Round 4: for the next r3s−r|α|steps, the adversary injects r4s−r2|α|packets of the form (γe2) and r4s−r2|α|packets of the form (f2βe1f1). Both sets of injections blocked in the first edge of their paths by the queued injections from the previous round. Round 5: for the next r4s−r2|α|steps, the adversary injects r5s−r3|α|packets of the form (γe2f1) and r5s−r3|α|packets of the form (βe1). The former remain queued in the first edge of γ. The later mix in the first edge of βwith the injections from the previous round (which 10 Observe that the digraphs that result from 2-cycle subdivisions of U3 1contain U2as a subgraph, and so they can be made unstable under the fifo protocol by an adversary that only uses the U2subgraph and uses an strategy as described in Lemma 6. VII are flowing in this round), and queue a total amount of r5s−r3|α|packets in the following proportions: (r6s−r4|α|)/(r+1) of the form (βe1), and (r5s−r3|α|)/(r+1) of the form (βe1f1). Round 6: for the next r5s−r3|α|steps, the adversary injects r6s−r4|α|packets of the form (f1). These injections get mixed with the injections queued from the previous round. At the end of the sixth round, there are more than ((r5s−r3|α|)/(r+ 1)) + r6s−r4|α| − r(|β|+|γ|) packets queued in f1, which require to cross that edge. The adversary described above only uses path trajectories and makes any digraph G ∈ E U3 1\ U3 1unstable when r5s−r3|α| r+ 1 +r6s−r4|α| − r(|β|+|γ|)> s. (4) Note that the relation between |β|and |γ|is not important for the statement to hold because the role of the paths (βe1) and (γe2) can be exchange indistinctly. Assuming the necessary conditions to assure that at every round the number of queued packets is positive, independently of the relation of |α|with the length of the other paths βand γ, and also independently of which are the values of those lengths, the statement can hold for a big enough s, i.e., an injection rate rcan be found such that the inequality in (4) holds. Lemma 10. The digraphs in EU4 1are not stable under fifo. Proof. We first prove that the system (U4 1,fifo) can be made unstable. Then, we show that the systems with a network which is a proper extension of U4 1, can also be made unstable under the fifo protocol. Digraph U4 1:The digraph U4 1was already shown in [11] not to be stable under fifo, although in there was a mistake in the counting of the last two rounds of the inductive reasoning (and thus, on the resulting injection rate). Doing the right calculations, and with the same adversary as in [11], we get that the digraph U4 1can be made unstable when (r7s+r6s+r5s)/(r+ 1) > s, i.e., for injection rate r≥0.929. Digraphs in EU4 1:Let Gbe a proper extension of U4 1, i.e., a G ∈ E U4 1\ U4 1described at Figure 4(b).11 Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. In G ∈ E U4 1\ U4 1, let |α| ≥ 1, |β| ≥ 1, and |γ| ≥ 1. We define an adversary with an strategy analogous to the adversary used for U4 1by extending the trajectories of the packets according to the corresponding current paths. At the beginning there are spackets queued in frequiring to traverse only edge f. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (fαβe1). These injections get all blocked at the queue of f. Round 2: for rs steps, the adversary injects r2spackets with trajectory (fαe21γe22), and r2s injections more with trajectory (βe1). The former get all blocked at the queue in f. The latter get mixed with the packets flowing from the previous round; at the end of the round, this mixure 11 Observe that the digraphs that result from 2-cycle subdivisions of U4 1contain U2as a subgraph, and so they can be made unstable under the fifo protocol by an adversary that only uses the U2subgraph and uses an strategy as described in Lemma 6. VIII is composed by r2s−r|α|packets, queued at the first edge of the path β, and with a trajectory (βe1). Round 3: for r2s+r3s−r|α|steps, the adversary injects r3s+r4s−r2|α|packets with trajectory (βe1), and r3s+r4s−r2|α|packets more with trajectory (e21γe22f). From the former, r4s−r2|α| remain blocked at the first edge of β. From the latter, a total amount of r4s−r2|α|packets with trajectory (e21γe22f) are queued at e21. Round 4: for r4s−r2|α|steps, the adversary inject r5s−r3|α|packets with trajectory (βe1f), and another r5s−r3|α|packets with trajectory (e22). The former get all blocked at the first edge of β. The latter get mixed with the packets from the previous round that flow through e22 after traversing γ; a total amount of r5s−r3|α| − r|γ|packets remain at the end of the round in the queue of e22 (from them, (r5s−r3|α| − r|γ|)/(r+ 1) packets require to traverse both e22 and f, while the rest only requires e22). Round 5: for r5s−r3|α|steps, the adversary injects r6s−r4|α|injections that only require to traverse (f). At the end of the fifth round, there are ((r5s−r3|α| − r|γ|)/(r+ 1)) − |β|+r6s−r4packets queued in f, which require to cross (only) that edge. The adversary described above only uses path trajectories and makes any digraph G ∈ E U4 1\ U4 1unstable when r5s−r3|α| − r|γ| r+ 1 − |β|+r6s−r4> s. (5) Assuming the necessary conditions to assure that at every round the number of queued packets is positive, independently of the relation of |α|with the length of the other paths βand γ, and also independently of which are the values of those lengths, the statement can hold for a big enough s, i.e., an injection rate rcan be found such that the inequality in (5) holds. A.2 Simple-path instability under FIFO For clarity reasons, we split the proof of Lemma 5 in the following two lemmas (Lemmas 11 and 12). Moreover, in each of the lemmas, we first prove that the smallest digraph Gof the family can be made unstable under the fifo protocol and then, we show that the systems with a network which is a proper extension of it, i.e., G0∈ E (G)\ G, can also be made unstable under the fifo protocol. By showing first the instability in the smallest forbidden digraphs, one gets a better intuition on how is the strategy of the adversary and which contention power it has. The strategy used when the network is an extension of the smallest forbidden digraph is usually the natural extension to paths of the strategy used there. The only requirement that the fact of dealing with an network extension imposes is that, the initial configuration of the system has to have enough initial packets (the quantity will depend on the length of the edge extensions) to allow the accumulation. Lemma 11. The digraphs in E(S3)are not simple-path stable under fifo. Proof. We first prove that the system (S3,fifo) can be made simple-path unstable. Then, we show that the systems with a network which is a proper extension of S3, can also be made simple-path unstable under the fifo protocol. IX Digraph S3:At the beginning there are spackets queued in e21 requiring to traverse only edge e21. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (e21e22). These injections will all get blocked in e21. Round 2: for rs steps, the adversary injects r2spackets of the form (e22f1). These packets will mix in e22 with packets from the previous round. From this mix, r3s/(r+ 1) are from the injections of these round and r2/(r+1) are still packets from the previous round. The important think is thtat the total queue at e22 has size r2s. Round 3: for the next r2ssteps, the adversary injects r3spackets of the form (e22f1e1). They will be blocked in e22 by the packets there from the previous round. Round 4: for the next r3ssteps, the adversary injects r4spackets of the form (e22f1) and r4s packets of the form (e1f22). The former are blocked at e22, while the latter get mixed with the packets flowing from the previous round. Round 5: for the next r4ssteps, the adversary injects the same type of packets as in the previous round. Thus, at the end there are r5spackets of the form (e22f1) and r5spackets of the form (e1f22). Round 6: for the next r5ssteps, the adversary injects r6spackets of the form (e22f1) and r6s packets of the form (f22f21e21). The former get all blocked. The latter get mixed with the ones flowing from the previous round but the total quantity of packets blocked is r6s. Round 7: for the next r6ssteps, the adversary injects r7spackets of the form (f1) and r7smore of the form (f22f21e21). The latter get all blocked, while the former get mixed at f1with the packets (e22f1) flowing from the previous round. From this mix, a total amount of r7spackets will be queued at f1. Round 8: for the next r7ssteps, the adversary injects r8spackets with path (f1e21) and r8s packets with path (f21). The former get all blocked in f1, while the latter get mixed with the ones flowing from the previous round. In this mix there are r8s/(r+ 1) packets with path (f22f21e21) and r9s/(r+ 1) with path (f21). Round 9: for the next r8ssteps, the adversary injects r9spackets with path (e21). At the end of the nineth round, there are r8s r+1 +r9spackets queued in e21 and requiring only that edge. The adversary described here achieves that the system (S3,fifo) is not simple-path stable whether (r8+r9+r10)s/(r+ 1) > s, i.e., whether r8+r9+r10 > r + 1. This holds for any r≥0.954. Digraphs in E(S3):Let Gbe a proper extension of S3, i.e., a G ∈ E (S3)\ S3described at Figure 5(b). Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. Moreover |α| ≥ 1 and |γ| ≥ 1. We define an adversary with an strategy analogous to the adversary used for S3by extending the trajectories of the packets according to the corresponding current paths. At the beginning there are spackets queued in e21 requiring to traverse only edge e21. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (e21e22α). These injections will all get blocked in e21. X      e21 e22 f1e1 f22 f21 S3       e21 e22 f1e1 f22 f21 g2 g1 S4 (a)        e22 α e21 f1e1 f21 γ f22 E(S3)       ...      e22 α e21 f1 g21 g11 g22 g12 g2β g1β e1 f21 γ f22 E(S4) (b) Extensions of the digraphs in Figure 5(a). Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. In the middle of the graph representing E(S4) there are 1+|β|2-cycles. By definition, |α| ≥ 0,|β| ≥ 0, and |γ| ≥ 0; in a proper extension, |α| ≥ 1,|β| ≥ 1, and |γ| ≥ 1. Fig. 5. Members of the family of forbidden subgraphs characterizing simple-path stability under fifo. Round 2: for rs steps, the adversary injects r2spackets of the form (e22αf1). These packets will mix in e22 with packets from the previous round. From this mix, the queue at e22 will keep a total amount of r2spackets. Round 3: for the next r2ssteps, the adversary injects r3spackets of the form (e22αf1e1). They will be blocked in e22 by the packets there from the previous round. Round 4: for the next r3ssteps, the adversary injects r4spackets of the form (e22αf1) and r4s packets of the form (e1γf22). The former are blocked at e22, while the latter get mixed with the packets flowing from the previous round, and a total amount of r4s−r|α|packets are kept in the queue of e1. Round 5: for the next r4ssteps, the adversary injects the same type of packets as in the previous round. Thus, at the end there are r5spackets of the form (e22αf1) queued at e22 and r5s−r|α| packets of the form (e1γf22) queued at e1. Round 6: for the next r5ssteps, the adversary injects r6spackets of the form (e22αf1) and r6s packets of the form (γf22f21e21). The former get all blocked. The latter get mixed with the ones flowing from the previous round but the total quantity of packets blocked at the first edge of γ is r6s−r|α|. Round 7: for the next r6ssteps, the adversary injects r7spackets of the form (f1) and r7smore of the form (γf22f21e21). From the latter, r7s−r|α|get blocked, while the former get mixed at f1with the packets flowing from the previous round. From this mix, a total amount of r7s−r|α| packets will remain queued at f1. Round 8: for the next r7s−r|α|steps, the adversary injects r8s−r2|α|packets with path (f1e21) and r8s−r2|α|packets with path (f21). The former get all blocked in f1, while the latter get mixed at f21 with the ones flowing from the previous round. In this mix there are ((r8s−r2|α|)/(r+ 1)) − |γ|packets with path (f21e21). Round 9: for the next r8s−r2|α|steps, the adversary injects r9s−r3|α|packets with path (e21). At the end of the nineth round, there are more than r9s−r3|α|− |γ|+((r8s−r2|α|)/(r+ 1)) packets queued in e21 and requiring to traverse only that edge. The adversary described above XI only uses simple-path trajectories and makes any digraph G ∈ E (S3)\ S3unstable when r9s−r3|α| − |γ|+r8s−r2|α| r+ 1 > s. (6) Assuming the necessary conditions to assure that at every round the number of queued packets is positive, independently of the relation between |α|and |γ|, and also independently of which are the values of those lengths, the statement can hold for a big enough s, i.e., an injection rate rcan be found such that the inequality in (6) holds. Lemma 12. The digraphs in E(S4)are not simple-path stable under fifo. Proof. We first prove that the system (S4,fifo) can be made simple-path unstable. Then, we show that the systems with a network which is a proper extension of S4, can also be made simple-path unstable under the fifo protocol. The strategies used by the adversaries to achieve instability are similar to those used in Lemma 11 to show the instability of any digraphs in E(S3) under fifo. Digraph S4:At the beginning there are spackets queued in e21 requiring to traverse only edge e21. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (e21e22). These injections will all get blocked in e21. Round 2: for rs steps, the adversary injects r2spackets of the form (e22f1). These packets will mix in e22 with packets from the previous round. From this mix, r3s/(r+ 1) are from the injections of these round (with path (e22f1)) and r2/(r+ 1) are still packets from the previous round (with path (e22)). The total queue at e22 has size r2s. Round 3: for the next r2ssteps, the adversary injects r3spackets of the form (e22f1g2e1). They will be blocked in e22 by the packets there from the previous round. Round 4: for the next r3ssteps, the adversary injects r4spackets of the form (e22f1g2) and r4s packets of the form (e1f22). The former are blocked at e22, while the latter get mixed with the packets flowing from the previous round. The queue at e1has total size r4s. Round 5: for the next r4ssteps, the adversary injects the same type of packets as in the previous round. Thus, at the end there are r5spackets of the form (e22f1g2) and r5spackets of the form (e1f22). Round 6: for the next r5ssteps, the adversary injects r6spackets of the form (e22f1g2) and r6s packets of the form (f22f21g1e21). The former get all blocked. The latter get mixed with the ones flowing from the previous round but the total quantity of packets blocked at f22 is r6s. Round 7: for the next r6ssteps, the adversary injects r7spackets of the form (f1) and r7smore of the form (f22f21g1e21). The latter get all blocked, while the former get mixed at f1with the packets (e22f1g2) flowing from the previous round. From this mix, a total amount of r7spackets will be queued at f1. Round 8: for the next r7ssteps, the adversary injects r8spackets with path (f1e21) and r8s packets with path (f21). The former get all blocked in f1, while the latter get mixed with the XII ones flowing from the previous round. In this mix there are r8s/(r+ 1) packets with path (f22f21g1e21) and r9s/(r+ 1) with path (f21). Round 9: for the next r8ssteps, the adversary injects r9spackets with path (e21). At the end of the nineth round, there are r8s r+1 +r9spackets queued in e21 and requiring only that edge. The adversary described here achieves that the system (S4,fifo) is not simple-path stable whether (r8+r9+r10)s/(r+ 1) > s, i.e., whether r8+r9+r10 > r + 1. This holds for any r≥0.954. Digraphs in E(S4):Let Gbe a proper extension of S4, i.e., a G ∈ E (S4)\ S4described at Figure 5(b). Let us denote with a dashed style not an arc but a directed path. Arcs are labelled with latin letters, while paths are labelled with greek letters. Moreover |α| ≥ 1,|β| ≥ 1, and |γ| ≥ 1. In the middle there are 1 + |β|2-cycles, each one sharing one vertex with the (unique) previous and the other vertex with the (unique) next. We define an adversary with an strategy analogous to the adversary used for S4by extending the trajectories of the packets according to the corresponding current paths. At the beginning there are spackets queued in e21 requiring to traverse only edge e21. Then the adversary will play infinitely the following rounds: Round 1: for ssteps, the adversary injects rs packets of the form (e21e22α). These injections will all get blocked in e21. Round 2: for rs steps, the adversary injects r2spackets of the form (e22αf1). These packets will mix in e22 with packets from the previous round. From this mix, the queue at e22 will keep a total amount of r2spackets. Round 3: for the next r2ssteps, the adversary injects r3spackets with path trajectory (e22αf1g21 . . . g2βe1). They will be blocked in e22 by the packets there from the previous round. Round 4: for the next r3ssteps, the adversary injects r4spackets of the form (e22αf1g21 . . . g2β) and r4spackets of the form (e1γf22). The former are blocked at e22, while the latter get mixed with the packets flowing from the previous round, and a total amount of r4s−r(|α|+|β|) packets are kept in the queue of e1. Round 5: for the next r4ssteps, the adversary injects the same type of packets as in the previous round. Thus, at the end there are r5spackets of the form (e22αf1g21 . . . g2β) queued at e22 and r5s−r(|α|+|β|) packets of the form (e1γf22) queued at e1. Round 6: for the next r5ssteps, the adversary injects r6spackets of the form (e22αf1g21 . . . g2β) and r6spackets of the form (γf22f21g1β. . . g11e21). The former get all blocked. The latter get mixed with the ones flowing from the previous round but the total quantity of packets blocked at the first edge of γis r6s−r(|α|+|β|). Round 7: for the next r6ssteps, the adversary injects r7spackets of the form (f1) and r7smore of the form (γf22f21g1β. . . g11e21). From the latter, r7s−r(|α|+|β|) get blocked, while the former get mixed at f1with the packets flowing from the previous round. From this mix, a total amount of r7s−r|α|packets will remain queued at f1. Round 8: for the next r7s−r|α|steps, the adversary injects r8s−r2|α|packets with path (f1e21) and r8s−r2|α|packets with path (g11). The former get all blocked in f1, while the latter get mixed at g11 with the ones flowing from the previous round. In this mix there are ((r8s−r2(|α|+|β|))/(r+ 1)) −(|β|+|γ|) packets with path (g11e21). XIII Round 9: for the next r8s−r2|α|steps, the adversary injects r9s−r3|α|packets with path (e21). At the end of the nineth round, there are more than r9s−r3|α| − |β| − |γ|+ (r8s−r2(|α|+ |β|))/(r+ 1) packets queued in e21 and requiring to traverse only that edge. The adversary described above only uses simple-path trajectories and makes any digraph G ∈ E (S4)\ S4 unstable when r9s−r3|α| − |β| − |γ|+r8s−r2(|α|+|β|) r+ 1 > s. (7) Assuming the necessary conditions to assure that at every round the number of queued packets is positive, independently of the relation between |α|,|β|and |γ|, and also independently of which are the values of those lengths, the statement can hold for a big enough s, i.e., an injection rate rcan be found such that the inequality in (7) holds.