{'fraction_non_alphanumeric': 0.042817780893609735, 'fraction_numerical': 0.010593375777486121, 'mean_word_length': 3.9350887074063645, 'pattern_counts': {'":': 0, '<': 111, '<?xml version=': 0, '>': 87, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 59, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Running in Circles: Packet Routing on Ring Networks

I analyze packet routing on unidirectional ring networks, with an eye towards establishing bounds on the expected length of the queues. Suppose we route packets by a greedy"hot potato"protocol. If packets are inserted by a Bernoulli process and have uniform destinations around the ring, and if the nominal load is kept fixed, then I can construct an upper bound on the expected queue length per node that is independent of the size of the ring. If the packets only travel one or two steps, I can calculate the exact expected queue length for rings of any size. I also show some stability results under more general circumstances. If the packets are inserted by any ergodic hidden Markov process with nominal loads less than one, and routed by any greedy protocol, I prove that the ring is ergodic.


The Problem
What is packet routing? In a packet routing network, we populate the nodes of a directed graph with a collection of discrete objects called packets. As time passes, these packets occasionally travel across edges, or depart the network. Sometimes, new packets are inserted. A typical question to ask is: what is the expected number of packets in the system? This thesis is inspired by the following packet routing problem on the ring: Suppose we have a directed graph in the form of a cycle with the edges directed clockwise. Let's label the nodes 1 through N , where for i < N , we have a directed edge from node i to i + 1, and an additional edge from N to 1. See Figure 1  We are going to analyze the network's behavior as it evolves in time, where time is measured in discrete steps. First, we have to specify how packets enter the ring. Let us suppose that with probability p, the probability that a new packet arrives at a node on one time step. With probability 1 − p, no packet arrives. This event occurs independently at every node, on every time step.
Next, we must specify how packets travel along the ring. A packet arriving at node i chooses its destination uniformly from the other N − 1 nodes. We will allow at most one packet to depart from a node in one time step. When a packet arrives at its destination, it is immediately removed; that is, a packet waiting in queue can be inserted into the ring on the same time step. Finally, if there is more than one packet at a node, we must specify which packet advances next. We'll use the Greedy Hot Potato protocol.
Definition 1 In the Greedy Hot Potato protocol, packets travelling in the network have priority over packets waiting in queue. Nodes with non-empty queues always route packets.
This protocol for determining packet priority is called Greedy Hot Potato because a packet being passed along the ring is a "hot potato" that never stops moving until it reaches its destination. It is "greedy" in the sense that whenever a node has the opportunity to route a packet, it always takes it. This protocol resolves all contentions over which packet gets to depart from a node.
By specifying the number of packets waiting at each of the N nodes, and the destination of each packet travelling in the ring, we completely specify the state of the system, and we have a discrete-time Markov chain.
Consider the number of packets in the system that need to use a node n. At most 1 packet can depart from n on each time step. Therefore, if too many new packets arrive, the system is unstable (the Markov chain is not ergodic). In practical terms, this means that the mean total number of packets in the system will diverge to infinity with time. Let us calculate what value of p corresponds to this unstable regime.
Lemma 1 Given the ring network described above, the system is unstable if p > 2 N .
Proof. Consider the node N − 1. (By symmetry of the ring, the expected number of packets that need to cross this node is the same as any other node.) If a packet arrives at node 1, it has a 1/(N − 1) chance of needing to cross n. More generally, a packet arriving at node i has an i/(N − 1) chance of needing to cross n, for i < N . Summing, the increase in congestion on n by new arrivals is: Therefore, if p > 2 N , the expected number of new packets that need to cross n increases by more than 1. However, the maximum possible number of packets that can cross per time step is 1. Therefore, the expected number of packets waiting to cross will increase without bound, so the system is unstable. ✷ If our system is stable, then, we must have 0 ≤ p ≤ 2/N . To make this value appear somewhat less dependent on N , it's useful to define r = p N 2 . We can then fix some 0 ≤ r ≤ 1 and study the system as N gets large. This r is called the nominal load.
I will call this system, as described above, the standard Bernoulli ring.
Definition 2 An N -node standard Bernoulli ring is an N -node directed cycle. Packet arrivals occur according to a Bernoulli arrival process at each node. Packet destinations are uniformly distributed. Packets are routed by the Greedy Hot Potato protocol. The nominal load r is N 2 p.
Coffman et al [14] made the following natural hypothesis: The expected queue length per node of the standard Bernoulli ring, for any fixed nominal load 0 ≤ r < 1, is Θ(1/N ).
The authors performed extensive computer simulations that seemed to support the hypothesis. Then, in Coffman et al [15], the authors partially proved this result: Theorem 1 (Coffman et al.) The expected queue length per node of the standard Bernoulli ring, for any fixed nominal load 0 ≤ r < 1 2 , is Θ(1/N ). Although Coffman et al. [15] established impressive results in the r < 1 2 case, the 1 2 ≤ r < 1 regime was left wide open. It wasn't even clear that the network was ergodic for any N > 2. 1 This thesis began as an attempt to determine the stability of the ring for values of r greater than 1 2 , and find asymptotic bounds for the expected queue length as a function of N (for a fixed r). As I began exploring ring networks more, I discovered that a number of interesting theorems could be proved for much more general arrival processes. This document is the result of my investigations.

A General Overview
In the earlier chapters of this thesis, I begin by examining simple ring networks. As the chapters progress, I analyze increasingly more general rings.
I begin in Chapter 2 by considering a ring network where each packet travels either 1 or 2 nodes. This type of restriction can be considered a kind of localness 2 , where nodes only need to communicate with their nearest few neighbors. I consider a number of different routing protocols and calculate their (exact) expected queue lengths. I also calculate the stationary distribution under the GHP protocol.
In Chapter 3, I consider the standard Bernoulli ring. I prove that it is ergodic (for any r < 1 and sufficiently large N r ), and I construct an O(1) upper bound on the expected queue length per node as N → ∞. This result isn't as tight as the O(1/N ) upper bound postulated in Hypothesis 1, but is a first step towards achieving it. The same techniques can be applied to a host of other rings, and I discuss some of these possibilities at the end of the chapter.
In Chapter 4, I examine the fluid limit method introduced by Dai [20]. The chapter is divided into two halves. In the first half, I translate the fluid limit theorems to discrete time. This half is sufficient to prove the stability of the standard Bernoulli ring whenever r < 1, not merely for large N . In the second half, I generalize the result a bit, so that (for instance) arrivals can be generated by a hidden Markov process, rather than just by arrival processes with i.i.d. interarrival times. This change leads to proofs of the stability and finiteness of expected queue length on rings much more general than the standard Bernoulli ring.
In Chapter 5, I translate a theorem of Zazanis [48] to the discrete time case. This result shows that in the face of Bernoulli arrivals, the expected queue length of an ergodic network is an analytic function of the nominal load r, for r ∈ [0, 1). This means that light traffic calculations of the expected queue length are actually well defined. I can then make some explicit light traffic calculations and draw various conclusions.
The final chapter, Chapter 6, concerns itself with ringlike networks, rather than rings themselves. The wrapped butterfly is an example: a d-dimensional wrapped butterfly shares certain features in common with a d-node ring, as both are regular, layered graphs with very high degrees of symmetry. I extend several of the results of the earlier sections to these more complicated topologies. I begin by proving a fluid-style stability result on all networks that use convex routing. I continue with a result about the graph structure of butterfly networks. I show that, under various conditions, a concatenated pair of butterfly graphs forms a superconcentrator. This means that we can lock down node-disjoint paths between any subset of input and output nodes (of the same size). This result is of a different flavor than the other proofs, being more graph theoretical than probabilistic.
There are also several appendices. Probability and queueing theory foundations are reviewed in Appendix A. For the reader unfamiliar with fluid limits, I include a complete proof of the stability results applicable for packet routing in Appendix B. The results are the same as those of Dai [20] (actually, weaker), but the proofs are much shorter and simpler, and the Appendix is self-contained. In Appendices C and D, I list a number of useful examples and counter-examples from the world of fluid limits. Finally, I wrote many computer programs to help me calculate stationary distributions. I discuss some of the more interesting details of this process in Appendix E.
For ease of reference, I have included an index. It lists the locations of definitions and main theorems.

The New Results
For the reader curious about which of these results are new, here is a brief list.
In Chapter 2: • I calculate the exact expected queue length on an N > 1 node nonstandard Bernoulli ring with parameter L = 2, for protocols GHP, EPF, SIS, CTO, and FTG.
• I calculate the stationary distribution for the nonstandard Bernoulli ring with parameter L = 2 for all N under GHP. This result allows an exact solution for a 3 node standard Bernoulli ring, and a 5 node bidirectional standard Bernoulli ring.
In Chapter 3: • The number of packets in one queue of a standard Bernoulli ring is bound by the number of packets in a single server queue with Bernoulli arrivals and geometric service times. An O(1) bound on the expected queue length per node follows for nominal load r < 1 2 + ǫ, for an explicit (but very small) ǫ.
• For any r < 1, on all sufficiently large standard Bernoulli rings, the network is ergodic.
(But see the stronger results of Chapter 4.) • For any r < 1, the expected queue length per node on a standard Bernoulli ring has an O(1) bound.
• For any r < 1, the expected delay of a packet on an N node standard Bernoulli ring is Θ(N ).
• I briefly discuss how to extend these techniques to other Bernoulli rings: -For a (standard) bidirectional ring, the expected queue length per node has an O(1) upper bound.
-For an N node nonstandard Bernoulli ring with parameter L, if N is constant and L → ∞, the expected queue length per node has a tight Θ(1) bound.
-For an N node nonstandard Bernoulli ring with parameter L, if L is constant and N → ∞, the expected queue length per node is lower bounded by Ω(1) and upper bounded by O(log(N )).
-Suppose that queues are finite, with some bound B N . As N → ∞, we may let B N → ∞. The expected queue length per node has an O(1) bound.
In Chapter 4, determining the novelty of the results is a little bit more complicated; the proofs are very closely tied to a paper by Dai [20]. My own contributions amount to the following: • I prove a discrete time fluid limit theorem. (This result is a modification of a theorem of Dai's.) • A corollary of the previous result is the stability of any ring, under any greedy protocol, for any maximum nominal load r < 1.
• The fluid limit technique holds when the arrival, service, and routing processes are hidden Markov chains. This generalization of Dai's results requires very little proof, because the hard work has already been done by Dai; only some careful definitions and reflection are needed.
In Chapter 5: • I provide a rigorous justification of light traffic limits on Bernoulli rings.
• The stationary distributions for standard Bernoulli rings with N > 3 nodes are not product form.
• The stationary distributions for geometric Bernoulli rings are not product form, except for a finite number of exceptions.
• Computer-aided calculations show that the expected queue length of a 4 node standard Bernoulli ring is not a rational function of degree less than 18.
• Consider the expected total number of packets in queue in a single-class network with rate p Bernoulli arrivals. The expected value is an absolutely monotonic function of p.
In Chapter 6: • On any network with convex routing and nominal loads less than one, with any greedy protocol, the network is ergodic.
• Suppose we have two d dimensional butterflies. Choose two permutations π 1 and π 2 on the d dimensions. Then if we permute the layers of the first butterfly by π 1 and the second butterfly by π 2 , and concatenate the graphs, the resulting graph is a superconcentrator.
• Suppose we take two graphs, each isomorphic to a butterfly, and concatenate them. The resulting graph concentrates subsets whose cardinality is a power of two.
The appendices are mostly abbreviated versions of material that can be found elsewhere. There are a few exceptions. Although the results in Appendix B are similar to (in fact, weaker than) those of Dai [20], the proofs are fairly different. Several of the stability proofs from Appendix C appear to be new, namely the theorems in Sections C.9 and C.10, and the corollaries from Section C.12. Finally, in Appendix E, Theorem 44 is new.

Ring Details
I still have to specify a few more picayune details about the ring. As mentioned before, I will be using a non-blocking model of the ring, so that if a packet departs at node i, then a new packet can be inserted on the same time step.
If we look at the packets waiting at a node, we will consider the packet that is about to move to be in the ring; the other packets are in queue at that node. I sometimes refer to a packet travelling in the ring as a hot potato packet.
It's important to distinguish between the packets "at a node" and those "in queue". The queue doesn't include the packet (if any) in the ring, so there may be one fewer packet in queue than at the node.
In discrete time, there's a non-zero probability that arrivals, departures and routing occur at the same time. Therefore, we have to settle on the order in which these events occur. Let us specify that one time step consists of routing current packets, possibly inducing some of them to depart, and then inserting new arrivals. On a standard Bernoulli ring, the choice of "route, then arrive" or "arrive, then route" only amounts to an O(1/N ) difference in the expected queue length per node, so it doesn't really matter much which model we use.
Finally, packet routing theorists and queueing theorists tend to model packet routing problems slightly differently. Packet routing researchers like to view edges of a network as wires, and allow only one message to cross a wire at a time. Therefore, queues wait on edges. Queueing theorists, on the other hand, prefer to view packets as waiting at nodes. I will be adopting the queueing theorists' point of view. To translate from the first perspective to the second, we can simply consider the edge graph of the packet routing network.

The Bidirectional Ring
Most of my analysis in this thesis will be directed towards the unidirectional ring, where all the packets travel in a fixed direction, e.g. clockwise. It is natural to wonder what happens if we have a bidirectional ring, where packets travel either clockwise or counterclockwise along the shortest path to their destinations. After all, this change halves the expected travel distance on the ring. In certain circumstances, we can reduce these problems to questions about the unidirectional ring.
To make this reduction, we need a slightly more general model than the standard Bernoulli ring: Definition 3 A nonstandard Bernoulli ring with parameter L is identical to a standard Bernoulli ring, except that rather than choosing destinations uniformly from the N − 1 nodes downstream, the destinations are chosen uniformly from the L nodes downstream. (If we select L = N − 1, we regain a standard Bernoulli ring.) The nominal load r is L+1 2 p.
Suppose we have an N -node bidirectional ring with Bernoulli arrivals. (For simplicity, imagine that N is odd, so that there exists a unique shortest path between any pair of nodes.) Suppose further that there are two edges between adjacent nodes: a clockwise edge and a counterclockwise edge. That way, node i can send a packet to node i + 1 at the same time that node i + 1 sends a packet to node i. Consider only the packets that travel in a clockwise direction. These packets form an N -node nonstandard Bernoulli ring with parameter L = (N − 1)/2. The counterclockwise packets form the same system.
These two networks are highly dependent (after all, if a clockwise packet arrives at a node, then a counterclockwise packet cannot). However, by the linearity of expectation, the expected queue length at a node in the bidirectional ring is exactly twice the expected queue length at that node on the nonstandard Bernoulli ring with the L given above. Therefore, the solutions to nonstandard Bernoulli rings in Chapters 2 and 3 translate to results about bidirectional rings.

Standardized Notation
As a kindness to the reader, I have tried to make my notation uniform throughout this thesis. In particular, • The number of nodes in a network is N .
• The maximum lifespan of a packet, i.e. the longest path in the network, is L. (For the standard Bernoulli ring, L = N − 1.) • The probability of a packet arriving at a node on one time step in a Bernoulli network is p.
• The nominal load of a node is r. (For a standard Bernoulli ring, r = N 2 p. For a nonstandard Bernoulli ring, r = L+1 2 p.)

A Little History
There is a large literature pertaining to packet routing on ring networks. I survey some of the results that bear more directly on this thesis below. 3 • Coffman et al, [14] and [15], analyze the geometric Bernoulli ring: Definition 4 An N -node geometric Bernoulli ring is an N -node directed cycle. Packet arrivals occur according to a Bernoulli arrival process at each node. Packet destinations are geometrically distributed. Packets are routed in a greedy fashion.
(Unlike the standard Bernoulli ring, there is essentially only one greedy protocol on a geometric Bernoulli ring.) Through very careful and clever arguments, they show that a geometric Bernoulli ring has Θ(1/N ) expected queue length for any nominal load r < 1. Their argument relies on showing that the greedy protocol is optimal on geometric Bernoulli ring across a wide class of protocols, and then finding another protocol with O(1/N ) expected queue length. 4 (The Ω(1/N ) lower bound follows easily; see Section 3.2.) Coffman et al. observe that the expected queue length of a geometric Bernoulli ring with nominal load r < 1 is an upper bound on the expected queue length of a standard Bernoulli ring with nominal load 2r. (This fact follows readily from a stochastic dominance argument.) It follows that the expected queue length of a standard Bernoulli ring is Θ(1/N ) if 0 ≤ r < 1 2 . Why can't we use the same techniques on the standard Bernoulli ring as we do on the geometric Bernoulli ring? Well, all the packets on a geometric Bernoulli ring are essentially indistinguishable; because of the geometric distribution on travel distances, the past history of a packet doesn't effect its future probability of leaving the ring. This property makes stochastic dominance arguments straightforward, so it's easy to find other, more analytically tractable protocols that can bound the expected queue length of the greedy protocol. On the other hand, the conditional probability that a packet departs the standard Bernoulli ring is very much dependent on how far it's travelled. It is correspondingly very, very difficult to find networks that could stochastically dominate all these conditional probabilities.
Both papers mention Hypothesis 1 as a vexing open question.
• The Greedy Hot Potato protocol may be the most natural to use on the ring, but it's certainly not the easiest to analyze. Kahale and Leighton [33] use generating functions to calculate a bound on the expected packets per node under the Farthest First protocol (where the packet with the most distant destination gets precedence over other packets.) The bound is: These arguments depend very heavily on the protocol, and don't translate to GHP.
• There are some fairly impressive and general results on stability and expected queue length on Markovian networks.

Definition 5 A network is
Markovian if the behavior of any two packets at a queue is stochastically identical. Thus, to specify a Markov chain, it is sufficient to specify how many packets are at each node (as opposed to specifying the class of each packet). A network with this property is also called classless, or single classed.
The geometric Bernoulli ring is an example of a Markovian network.
The first breakthrough in the subject came from Stamoulis and Tsitsiklis [45]. They showed how to bound the expected queue length under a First In, First Out (FIFO) protocol and (continuous time) deterministic service by a processor sharing protocol with exponential service times. It's easy to calculate the expected queue length of the latter network, so the method provides explicit upper bounds on expected total queue length in the network.
Stamoulis and Tsitsiklis used their results on hypercubes and butterfly graphs, but their proofs clearly apply to any layered network. Mitzenmacher [39] used these results to analyze the N × N array, for instance. However, the technique broke down on networks with loops, such as rings or tori.
This problem was very nicely resolved by Harchol-Balter [31] in her dissertation. She showed how to construct the same simple upper bounds for any Markovian network, including those with loops.
If we applied these results naively to a standard Bernoulli ring, we would get an O(1) bound on the expected queue length per node. This result is akin to the O(1) bound in Theorem 2 from Coffman et al. [14] on the geometric Bernoulli ring. Unfortunately, a standard Bernoulli ring is emphatically not Markovian, and the analysis fails.
• Since the standard Bernoulli ring model runs in discrete time, and each packet needs only one unit of time to cross an edge, it is tempting to imagine that there should be some very general solutions for the stationary probabilities, analogous to the solutions to a Kelly network in continuous time. One successful result along those lines is due to Modiano and Ephremides [40]. They show exact solutions for expected queue length on a tree network where all paths lead back to the root node.
Can this result be extended for arbitrary layered graphs? Modiano believes that this is true, but the proof is non-obvious, to say the least. (If true, this would resolve an open question in Stamoulis and Tsitsiklis [45] concerning the expected queue length per node on a butterfly.) Extending it to networks with feedback, like a ring, seems impossible.
• Rene Cruz [18], [19] developed a model of packet routing with "burstiness" constraints. These constraints boil down to the following: for each edge, fix r, s > 0. Then in T time steps, at most ⌊T r + s⌋ packets can arrive. In Cruz [19], he proves a stability result on a model of a 4 node ring.
Georgiadis and Tassiulas [29] show that Cruz's model of the ring is stable under a greedy protocol, on a ring of any size, so long as the nominal loads are less than one.
For stochastic arrival processes like the Bernoulli process, Cruz's burstiness assumptions are too restrictive, so his stability theorems don't apply.
• Cruz can be considered one of the forefathers of adversarial queueing theory. The intent of adversarial queueing theory is to prove that even in the face of maliciously planned packet insertions, certain networks and protocols are still stable.
More specifically, fix an integer T and some 0 ≤ r ≤ 1. Imagine that an adversary injects packets such that for any fixed edge e, the number of packets injected during the previous T time steps that need to use e is less than ⌊rT ⌋. A network and protocol is stable with load r if for any T , there is a maximum number of packets M T that can appear in the network simultaneously. (Thus, the adversary "wins" if he can make the number of packets in the system grow unboundedly.) Adversarial queueing theory was originally introduced by Borodin et al. [4]. The result of interest to us is from Andrews et al. [1], where the authors show that the ring is adversarially stable under any greedy protocol, for any r < 1. A very interesting converse was proved by Goel [30], who showed that any network containing more than one ring is adversarially unstable for some protocol and some r 0 < 1. An equivalent result for stochastic stability is unknown but desirable.
Almost any stochastic arrival process (like the Bernoulli) has a potential for unbounded "burstiness". This fact prevents the adversarial results from applying to a standard Bernoulli ring in any obvious way.
• Around 1995, a major advance was made in the general study of stability on queueing networks. Dai [20] introduced fluid limit models, a method of rescaling a stochastic system to reduce it to a deterministic one. One of the consequences of this theory was a proof that in continuous time, the (generalized Kelly) ring is stable under any greedy protocol, so long as the maximum nominal load on any node is less than one (see Dai and Weiss [22]). Further refinements of the theory allowed proofs of the finiteness of the expected queue length assuming bounded variance of the arrival and service times of the network (see Dai and Meyn [23]). I'll be looking at fluid limits in greater detail in Chapter 4.
• Gamarnik [28] managed to prove an adversarial fluid limit theorem, providing a way to prove adversarial stability by analyzing a more complicated fluid limit. As an example, he provided yet another proof of the adversarial stability of the ring.

Introduction
In this chapter, I'm going to perform exact calculations of the expected queue length and stationary distribution of several families of rings. For a brief review of stationary distributions and discrete time Markov chains, please see Section A.1.
Recall the nonstandard Bernoulli ring with parameter L introduced in Section 1.4. A nonstandard Bernoulli ring can be specified by it's size N and its maximum path length L. If L is fairly small relative to N , then we can imagine that packets only need to communicate in a small local neighborhood of themselves. If, on the other hand, L ≥ N , then a packet can cross the same node more than once.
I can only hope to calculate exact solutions in the simplest cases; even then, some of the proofs are fairly involved. I will exactly calculate the expected queue length for the case of N = 1 for arbitrary L, and L = 1 or 2 for arbitrary N . The results hold for several different protocols. I will also find the stationary distribution for L = 2 and all N under the GHP protocol.

The One Node Ring
Remember that the standard routing protocol for a ring is Greedy Hot Potato (GHP), where packets travelling in the ring have precedence over packets in queue. In a one node ring, this means that the packet which is being serviced remains in service until it leaves the queue (i.e. no pre-emptions occur.) Observe that this protocol is the same as First In, First Out (FIFO): The First In, First Out (FIFO) protocol, as its name suggests, gives priority to earlier arrivals at a node. That is, the nth packet arriving at the node will be the nth packet departing. (Simultaneous arrivals are numbered randomly.) This protocol is also called First Come, First Served (FCFS).
For an N node ring with N > 1, FIFO and GHP are not the same. Note that since a packet doesn't really "travel" anywhere on a N = 1 node ring, some people find it might be more natural to view a packet as having an amount of work associated with it. (So, for example, rather than "travelling" in place for k time steps, we say the packet has k units of work.) However, I will stick with the "travel" metaphor.
Theorem 2 Suppose we have a 1 node nonstandard Bernoulli ring with parameter L, and we are routing using GHP. Suppose that the arrival rate is p = 2 L+1 r. Then the expected queue length is: Note: Therefore, for a fixed r, the expected queue length is O(1) in L.
Proof. Since N = 1, we have a single server queue, and can apply standard tools from queueing theory. The ergodicity of a single server queue for nominal loads less than one follows from typical arguments (e.g. Gallager [27], Chapter 7). For the expected queue length, recall the discrete time version of the Pollaczek-Khinchin formula (Theorem 30): where λ is the arrival rate (i.e. p), and Z is the distribution of service times (i.e. uniform between 1 and L.) So, since we can plug in and get We can also make some qualitative comparisons of expected queue length.
Lemma 2 Suppose we are comparing the expected queue length of greedy protocols A and B on a single node network. Suppose that the mean work of a packet in queue under A is strictly greater than under B. Suppose also that the queue length is independent of the expected work in each packet in the queue. Then it follows than the expected queue length under A is strictly shorter than under B.
Proof. Observe that since we are in the single server regime, the total amount of work in the queue is constant for all greedy protocols. Also, the expected amount of work of the packet in service is also invariant over the protocols (because it's the mean work per packet Consider, then, the Farthest To Go (FTG) protocol, where packets with the greatest distance left to travel have priority over packets with nearer destinations. If a packet arrives with a greater distance to travel than all the other packets in the system, I allow it to serviced immediately (so it spends no time in queue.) On a ring, FTG is a well-defined protocol. 1 We can deduce the following corollary: Corollary 1 Suppose we have a 1 node non-standard Bernoulli ring with parameter L = 2. Then for any arrival rate greater than zero, the expected queue length under GHP is shorter than under FTG.
Note: A queueing theorist would probably express this result by saying that the Least Remaining Work protocol is worse than FIFO.
Proof. By inducting on time, we can show that under FTG, all packets in queue need one unit of service time. At time t = 0, there are no packets in queue, so the result holds. At time t, by induction all packets in queue need one unit of service, so if a packet arrives needing 2 units, it will be immediately serviced, and thus removed from the queue. Thus, at time t + 1, all the packets in queue will need one unit of service.
Therefore, under FTG, the mean work per packet in queue is 1, independent of the queue length. Under GHP (which is identical to FIFO), it's 3/2, independent of the queue length. By Lemma 2, we're done. ✷ This result may give some plausible hint that GHP has shorter expected queues than FTG on larger rings. Nevertheless, in section 2.4, I show that GHP and FTG have identical expected queue length if L = 2 and N > 1, so Corollary 1 is somewhat surprising.

Fixing L in the Nonstandard Bernoulli Ring
First off, let us consider the case of L = 1, for a ring of any size. Since our model of packetrouting is non-blocking, the only node that a packet blocks is the node that it arrives at. Since at most one packet arrives on each time step, and (with any greedy protocol) at least one packet is emitted on each time step from a non-empty queue, it follows that there are never any packets in queue. Therefore, the stationary distribution is of product form, where the probability of a node being empty is 1 − p; the probability of there being one packet at that node is p. ("Product form" is defined in Section A.1.) The expected queue length is identically zero.
The case of L = 2 is much more interesting. I am going to analyze a number of different protocols in the following sections, but the marginal stationary distributions (per node) will all be essentially the same. Because the different protocols have slightly different state spaces, the distributions are formally incomparable, but the probability that a particular node has i packets in it is the same across all the protocols. In particular, the expected queue length per node (as a function of r) is constant across all these protocols. Even more surprisingly, the marginal distribution per node is independent of N , for N > 1. That is, the expected queue length per node is independent not only of which of these protocols are chosen, but also of the size of the ring.
The protocols (which will be defined in Section 2.5) are Exogenous Packets First (EPF), Closest To Origin (CTO), Farthest To Go (FTG), Shortest In System (SIS), and Greedy Hot Potato (GHP). GHP is the protocol specified in the standard Bernoulli ring in Section 1.1, and hence is of particular interest. I calculate its full stationary distribution (not just the marginal distribution per node). This latter proof is substantially longer than any of the other proofs, taking up the majority of this chapter.

The Stationary Distribution and Consequences
As mentioned in Section 2.1, the distributional values (expected queue length, and so forth) are the same for all the protocols I examine. In advance of the proofs of the marginal stationary distributions, I preview the results in this section.
Theorem 3 For the GHP, SIS, CTO, FTG, and EPF protocols, on an N > 1 node ring, with maximum destination L = 2, and packet arrival probability p, the stationary probability that a fixed node has n packets in it is: and for any n > 1, Under GHP, this result also holds if N = 1.
Proof. The proofs follow in the remainder of the chapter. ✷ We can use this theorem to calculate various interesting quantities. The expected queue length per processor is: By Section A.5, the expected number of packets per processor is equal to: (Expected queue length) + (1 − Pr (empty processor)) The expected variance of the queue length per processor (for any N ) is equal to: Finally, just for fun, we can calculate the entropy of the queue length per processor: Pr(n packets in queue) log(Pr(n packets in queue)) Plugging in, we get Observe that the first sum in square brackets is the sum of the probability from all states, which equals 1. The second sum in square brackets is the expected queue length, which we know is p 2 /(2 − 3p). So, It's pretty easy to verify that this entropy function equals 0 when p = 0, diverges to positive infinity at p = 2/3, is continuous on 0 ≤ p < 2/3, and is monotonically increasing. For GHP, since the distribution has product form, the entropy of all N processors is N times the entropy per processor.
These results also allow exact analysis of two cases of special interest.

The 3 Node Standard Bernoulli Ring
If N = 3, then any processor can send a packet to any other processor. Observe that this network is a 3 node standard Bernoulli ring. The previous section allows us to calculate exactly the expected delay, expected queue length, variance, etc.

The 5 Node Bidirectional Ring
Suppose we have a 5-node bidirectional ring, where packets take the (unique) shortest path to their destination, the destinations are distributed uniformly over the other processors, and packets arrive with probability p. Suppose that a processor can send out 2 packets in 1 turn as long as the packets are using different edges. (There are two edges between adjacent nodes, so that node i can send node i + 1 a packet at the same time that i + 1 sends i a packet.) Packets arrive at a node according to a Bernoulli process, per usual. Then, as described in Section 1.4, we can decompose the ring into two unidirectional rings (in opposite directions), each operating with an effective arrival rate ofp = p/2. The arrival processes into these two rings are correlated, but since expectation is linear, this correlation doesn't effect the expected queue length. The expected queue length is then Note that p ≤ 1 ⇒p ≤ 1/2, yet the critical point isp = 2/3. Therefore, the system is always stable. The largest expected queue length occurs when p = 1, giving E(queue length) = 1 4−3 = 1.

The EPF, SIS, CTO, and FTG Protocols
As I'll show below, for the L = 2 case, all four of these protocols can be viewed as functionally identical. (For larger L, this is not necessarily true, and for non-ring networks, it's almost never true.) I will now define each of these protocols in turn.
The Exogenous Packets First (EPF) protocol always prefers an exogenous arrival to an internal arrival. (A packet arrives exogenously if it has just been inserted from the Bernoulli arrival process; an internal arrival is a packet that has been routed from another node in the network.) Simply specifying the priority of exogenous arrivals over internal arrivals does not usually fully specify a protocol for an arbitrary graph. But when the maximum path length is 2 and there are only two classes at each node (exogenous arrivals and internal arrivals), then everything is well defined. Note that, since there is at most one exogenous arrival to a node on each time step, and it has priority, the exogenous packets never wait in queue; a packet is only (possibly) queued after its first step, at which time it has become an internal packet.
The Shortest In System (SIS) protocol dictates that if two packets are contending for an edge, the packet with the most recent insertion into the network gets precedence. This means that if a packet is injected into a node, it is guaranteed to move on the next time step. The only packets that can wait in queues are packets that have already moved one step but have a second step left to take. Therefore, exogenous packets have priority. Thus, SIS is the functionally the same protocol as Exogenous Packets First (EPF).
The Closest To Origin (CTO) protocol gives priority to the packet that is closest to its own origin (i.e. point of arrival to the ring). Since we're on a ring, this specifies a unique class of packets. Since packets travel only one or two spaces, then the packet closest to its origin is the packet that has just been exogenously inserted. In other words, CTO is identical to EPF.
The Farthest To Go (FTG) protocol looks at the destination of the packets in the system and gives priority to the packets that have the greatest distance left to go. Suppose, however, that an exogenous and an internal packet both arrive at a node, and both have exactly one edge left to cross. Which gets precedence? In some sense it doesn't matter; the two packets are interchangeable, so whichever choice we make, the behavior of the system (number of packets in queues) is identical regardless of which packet advances. Therefore, we might as well specify that the exogenous packet advances first. So, if an exogenous arrival has a destination two nodes away, it has priority because it is travelling farther than any other packet at that node; if it has a destination one node away, by the previous observation, it has precedence over internal packets. Thus, FTG is identical to EPF. SIS, CTO, and FTG are all well-defined on any ring network (not just with L = 2), but are not necessarily well-defined on networks with arbitrary topology. They are meaningful if and only if the probability of a packet choosing any particular path is a function of its total path length. EPF can be defined on a network with arbitary topology so long as there are only two classes of packets present at any node: exogenous and internal. (In other words, all internal packets behave identically.) If the maximum path length is two, then EPF is a somewhat natural protocol to use.
We have reduced the problem of understanding SIS, CTO, and FTG to understanding EPF. For ease of reference, I will state this formally: The stationary distributions on a nonstandard Bernoulli ring with L = 2 are identical under the protocols SIS, CTO, FTG, and EPF.
Next, I'll introduce a lemma that hinges on the fact that the maximum path length L is 2.
Lemma 4 Suppose we have an arbitrary network with N nodes. Suppose that • Packets arrive at node i as a p i -rate Bernoulli process.
• The maximum path length is two.
• Packets are routed according to EPF.
• No path crosses itself.
• If node i has j outgoing edges, then an (exogenous) packet leaving node i crosses edge j with probability q i,j . It departs the system with probability 1 − j q i,j . (If a packet is not exogenous, then it has already crossed an edge, and must necessarily depart on its next move.) Then the stationary distribution of internal packets waiting in queue at node i is stochastically identical to the total number of packets at a single server where the arrival process is a sum of Bernoulli arrivals, and the service time is exponentially distributed. (The particular arrival and service distributions are spelled out below.) Proof. Consider node i. Because we are using EPF, the only packets that queue are internal packets. An internal packet arrives at node i only if it arrived exogenously at node j on the previous time step, received priority (because it was exogenous), and then with probability q j,i elected to travel to node i. This event is a Bernoulli arrival process with rate p j q j,i . Since these arrivals at each j are independent of each other, then the total internal arrivals to the queue at node i consist of a sum of independent Bernoulli arrival processes. Suppose that there is a queue of internal packets waiting at node i. We will be able to remove a packet from the queue, unless there is a new exogenous arrival at node i. Imagining an internal packet waiting at the head of the line at node i, it has a 1 − p i chance of leaving on each time step. This behavior is identical to giving each packet an exponentially distributed service time.
(In order to insure that the arrival process and the service times are independent, we needed to assume that no path crosses itself.) ✷ We can also conclude that: Corollary 2 If the assumptions in Lemma 4 are true and the nominal loads are less than one at each node, then the system is ergodic.
Proof. The nominal loads are less than one iff the expected number of packets that arrive on each step that need to use node i is less than one, for all i. In that case, Lemma 4 implies that the marginal distribution of packets queued at each individual node converges to a (marginal) stationary distribution. It follows that the whole system is ergodic. ✷ We can draw another interesting corollary from this lemma: Corollary 3 Suppose that the assumptions of Lemma 4 hold. Suppose further that we can partition the network's nodes into disjoint sets A 1 , . . . , A k such that no two nodes in the same partition share an edge. (For instance, if k = 2, we have a bipartite graph.) Finally, suppose that for any node x ∈ A i , there is at most one edge from x to nodes in A i . Then the marginal distribution of the state of all the nodes in A i is the product of the marginal distribution of each node in A i (which is given in Lemma 4).
Proof. This follows by observing that the arrival and service times of nodes in the same partition are independent of each other, since the partition has no internal edges. ✷ It seems quite likely that the stationary distribution itself is of product form, but I will not investigate that idea at the moment. Instead, let us use Lemma 4 to calculate the marginal stationary distribution of a node on a ring.
Theorem 4 Suppose we have an N node ring, and we are routing packets using either SIS, CTO, FTG, or EPF. Then the system is ergodic if p < 2/3 (i.e. if the nominal load r < 1), and the marginal stationary probability of having n packets in the node is: and for any n > 1, It follows that all the expected queue length calculations from Section 2.4 hold for these protocols.
Proof. From Lemma 3, these four protocols are all interchangeable, so I need only prove the result for EPF. By Corollary 2, the system is ergodic if p + p/2 < 1, i.e. if p < 2/3. Therefore, there exists a stationary distribution whenever p < 2/3. Since the system is unstable if r > 1 by an argument analogous to Lemma 1, we have pretty well characterized stability. (Although I won't prove it, if r = 1 we get a system that is not ergodic, but is null-recurrent.) By Lemma 4, we can calculate the marginal stationary distributions when p < 2/3. Throughout, we consider some fixed node. New internal packets arrive as a rate p/2 Bernoulli process. (That is, they arrive as a rate p Bernoulli process at the previous node, and half of them remain in the system.) An internal packet departs the node (and the system) iff an exogenous packet does not arrive. A non-arrival occurs with probability 1 − p.
This description gives us a fairly standard birth-death process. I've worked out the details of the stationary distribution in Section A.5 (and remember that I'm assuming that on each time step we route old packets, then insert new arrivals, and then measure the state). Let π n be the stationary probability that there are i internal packets at the node. Then the result is: We want to calculate the stationary distribution for all the packets, not just the internal packets. Now, the probability of there being n > 1 packets in the system is the probability of n internal packets and no exogenous packet, plus n − 1 internal packets and 1 exogenous packet. So, Pr(n packets at the node) = Pr(n internal packets) Pr(0 exogenous) + Pr(n − 1 internal packets) Pr(1 exogenous) For the n = 1 case, we have The probability of there being no packets in the system is Pr(0 packets at the node) = π 0 (1 − p) = 1 − 3 2 p and we are done. ✷ Observe that the marginal stationary probability of there being n packets in a queue is identical to the GHP case.

The GHP Protocol
The remainder of this chapter is dedicated to calculating the stationary distribution of the GHP protocol (not just the marginal stationary distribution per node, as with the other protocols). Let us begin with a description of the stationary distribution. The information from Section 2.4 does not give us quite enough information to specify a Markov chain, so I will need to refine the state description.
There are a number of ways of specifying the state of the Markov chain. For instance, we could specify the destination of every packet in the system (including packets in queue). Since the packets waiting in queue are stochastically interchangeable, though, we only really need to specify the destinations of the packets travelling in the ring, and the number (but not the destinations) of the packets in queue. This is the model I will use in this chapter. On the other hand, it is sufficient to know the origin of each packet in the ring, rather than its destination, because the probability of a packet departing on the next step is a function of the number of steps the packet has already travelled. I'll use that model in Chapter 3. However, all the models are essentially equivalent, e.g. the expected queue lengths are identical regardless of the model.
Let us begin with some notation. The state of the ring is determined by the state of each of its processors. I will denote a processor with n packets in its queue and a hot potato with t steps left to travel as: n t and the ground state (no queue, no hot potato) as:

X
Note that on our parameter L = 2 ring, t = 1, 2 or X, that n ∈ IN, and that if t = X then n = 0. My guess for the probability distribution is that it is of product form (so we can calculate the probability of the state of all N processors by multiplying the probability of the state of each processor), and the probability per processor is: Assuming that our guess is correct, it shouldn't be too difficult in principle to verify itwe just check the balance equations: where σ and τ are states of the system, π(σ) is our guess for the stationary probability of state σ, and Pr(τ → σ) is the probability of travelling from τ to σ in one step. Now, calculating π(σ) is fairly simple, and calculating Pr(τ → σ) isn't too bad either, assuming that τ actually precedes σ with non-zero probability. However, finding the τ s that precede σ (i.e. figuring out what states precede any given state) appears to be very difficult to do in general. I'll use a number of tricks to reduce the problem to checking a finite number of states (actually, classes of states), and then verify that the balance equations hold on them.
In general outline, I will begin by verifying the claim for the N = 1 case. I will continue by induction on N . For fixed N , however, there are still an infinite number of cases, so I will reduce the problem to one with bounded queues (all queues of length ≤ 2.) At this point, we can cut the ring at two points and rejoin them to form two smaller subrings and use induction on the smaller rings. Cutting the ring is a fairly delicate operation in some cases, and takes up the body of the proof.

N=1, L=2
I want to verify that the guessed stationary distribution for the ring (Equations 2.1, page 31) satisfies the balance equations for the 1-node ring. This verification is straightforward.

Lemma 5
The stationary distribution for a 1-node nonstandard ring with parameter L = 2 is given by Equations 2.1.
There are 5 cases to consider.
• The ground state, X . By Little's theorem (or the "Utilization law"), the probability that the processor is empty is 1 − r, where r is the fraction of loading, in this case (3/2)p. (See Section A.5 for details.) This matches our guess for the stationary probability.
• The state 1 . If we write down the balance equation for the ground state, we get Pr X = (1 − p) Pr X + Pr 1 Since we now know Pr X , we can solve and find that The state 2 . The probability flowing in is • The state n 2 , for n > 0. The probability flowing in is • The state n 1 , for n > 0. The probability flowing in is Note that the bracketed term is equal to the probability flowing in to n 2 , which we've just shown is equal to our guessed probability. Plugging this in, we get Calculating the probabilities of n 2 and n − 1 2 in terms of the probability of This covers all states for the N = 1 case. ✷

Proof for All N
It's pretty easy to exhaustively verify Equations 2.1 for N = 2 and 3, but it's not clear how to prove it for any N . This section (and its subsections) are devoted to a proof of that fact. I'll prove that the stationary distribution for any N is of product form, where each processor's distribution matching that of equations 2.1.

Theorem 5
The stationary distribution for any N -node nonstandard ring with parameter L = 2 is product form and given by Equations 2.1.
I proceed by induction on N . If N = 1, we're done, by Lemma 5. Assume that N > 1. I will begin by arguing that it is sufficient to analyze the cases where all the queues are of length ≤ 2. Suppose for a moment that processor i has more than two packets in its queue, that is, the processor is in state n h for h = 1 or 2 and n ≥ 3. What is the shortest queue length that the processor could have had on the preceding turn? If a packet arrived from the preceding processor, and a new packet arrived to the queue, then the preceding queue would have had a length of n − 1. This is the shortest it could be. Therefore, for any state τ that has a non-zero probability of preceding our current state σ, the queue length in processor i of state τ is ≥ n − 1 ≥ 2.
Suppose now that we removed a packet from the queue of processor i in state σ. (Let's call this new stateσ.) Suppose that we also remove a packet from the queue of the ith processor in τ , formingτ . Observe thatτ precedesσ with non-zero probability-in fact, the transition probability is exactly the same as τ becoming σ. (It's necessary that n ≥ 2 for this to hold.) Moreover, any stateτ that precedesσ with non-zero probability can also be translated back into a state τ preceding σ.
Observe that if processor i has n ≥ 3 packets in queue, and we remove a packet, the stationary probability of the resulting state is multiplied by ( . The argument in the preceding paragraph shows that the preceding states will all also lose a packet in processor i. Since the minimal queue length of processor i is 2 in any preceding state τ , then it is at least 1 in any stateτ . Thus, the balance equations for σ andσ differ by exactly a factor of in every term. Therefore, if we can show that the balance equations hold when processor i's queue is ≤ 2, we're done. This holds for any i, so we are reduced to showing that the balance equations hold when all queues are of length ≤ 2. Next, I'll reduce the possible configurations of packets travelling in the ring (i.e. hot potatoes), which will ultimately reduce the number of equations we need to check.
Definition 7 Suppose that the current state of the ring is σ and the preceding state was τ . Consider the edge e between processors i and i + 1. If processor i in state τ was holding a hot potato equal to 2, we say that the edge e in σ was crossed, denoted If this did not occur, we say that e was blocked, denoted An unspecified edge is denoted This definition might sound a bit odd, in that I don't consider a packet to cross an edge if it's arriving at its destination. However, since I'm analyzing a non-blocking model of the ring (i.e. a packet can arrive at its destination at the same time that a new packet gets dropped from the destination's queue), this definition proves useful. Note that an edge from processor i to processor i + 1 can only have been crossed if processor i + 1 currently contains a hot potato, and the hot potato equals 1.
Suppose that we are in state σ. Suppose that neither processor i nor j (i = j) contains the hot potato 1. Let e i and e j be the edges preceding processors i and j, respectively. Then note that both e i and e j are blocked.
Let us perform the following operation: we cut edges e i and e j and form two smaller unidirectional rings: ring R i will consist of processors i through j − 1, and ring R j will consist of processors j through i − 1.
Observe that in R i , the edge between processor j − 1 and processor i is blocked (and similarly the edge between processor i − 1 and j in R j is blocked, too). Let us refer to the state of R i as σ i (and similarly for R j and σ j .) (σ i and σ j are determined by σ.) Suppose that some states τ i and τ j preceded σ i and σj, respectively, on the subrings. If we glue τ i and τ j together (by reversing the process that gave us R i and R j originally), we get a state τ that precedes σ, and the probability that τ becomes σ is found by multiplying the respective probabilities on R i and R j . This surprising state of affairs occurs because e i and e j aren't crossed. In some sense, no information about the preceding state arrives at processors i and j. This allows us to view the two parts of the ring (namely i to j − 1 and j to i − 1) independently.
The balance equations now follow easily by induction, since the subrings are smaller than N . By our inductive hypothesis, the sum of the probabilities into σ i is Pr(σ i ), and the probability into σ j is Pr(σ j ). Therefore, the sum of the probabilities into σ is Since our distributions are all product form, this is precisely Pr(σ), as desired.
What states remain to deal with? We can assume that all queues are of length ≤ 2, and at least N − 1 processors contains 1 as a hot potato. I'm going to split the remaining cases into finitely many classes and then verify the balance equations on each class.
First of all, let us choose a processor i. Suppose the state of the system, σ, is Let e 1 be the edge from processor i − 1 to processor i, and e 2 be the edge from processor i to processor i + 1. Each of these edges may be crossed or blocked. By specifying if e 1 and e 2 are crossed or blocked, we partition the states that precede σ into 4 disjoint classes. Of course, as we saw above, if h i = 2 or X, then e 1 must be blocked-in other words, some of the partitions may be empty. Once we know whether e 1 or e 2 are crossed, we can (with some manipulation) reduce the possible prior states on the processors i + 1 through i − 1 to an N − 1 node ring, and use induction. Then we plug the values in, sum over the 4 partitions, and end up with the balance equation. I will first calculate the probability flowing into processor i, then the probability flowing into the remaining N − 1 processors, and finally check all the balance equations in one fell swoop. Here we go.

Probability of Processor i
The probability of the possible prior states to → X →, weighted by the probability of travelling from that state to → X →, is: Probability into → X → is: Probability into → 2 → is: Probability into → 1 2 → is: Probability into → 1 2 → is: Probability into → 2 2 → is: Probability into → 2 2 → is: Probability into → 1 → is: Probability into → 1 → is: Probability into → 1 → is:

Probability of the Other Processors
We now have to deal with the somewhat more complicated problem of the other N − 1 processors. The key to finding the possible preceding states of processors i + 1 through i − 1 is the state of processor i + 1. Recall that at most one processor does not have a hot potato equal to one-therefore, we can assume that the hot potato in processor i + 1 is 1. The queue can be 0, 1, or 2, and the edges e 1 and e 2 can each be crossed or blocked, so there are 12 possibilities. I calculate them below.
To begin, if the queue in processor i + 1 is empty, and neither edge e 1 nor e 2 is crossed, i.e. If no packets cross, then the "1" hot potato that appears in processor i + 1 is newly minted, and with equal probability could have been a "2". But if it were a "2", we would have a guarantee that no packets crossed. Therefore, the sum of the probabilities of the prior states (weighted by transition probabilities) for processors i + 1 through i − 1 on the original ring is equal to the sum of the probabilities of the prior states (weighted by transition probabilities) of an N − 1 node ring, where processor i is removed, and processor i + 1's state is changed to 2 . By induction, this latter weighted sum is equal to the product form probability distribution from equations 2.1. Shifting processor i+1 from 1 to 2 divides the probability by (2 − p), so Next, suppose that the situation is We can use the same kind of reasoning as above, but there's a twist: if we try to view processors i + 1 through i − 1 as an independent N − 1 node ring, where did the packet currently in processor i + 1 come from? Since edge e 1 is blocked, the packet at node i + 1 seems to have arrived out of the fog. However, we can take this behavior into account in determining the possible preceding states to these N − 1 processors. The possible preceding states for nodes i + 1 through i − 1 are the same as those on a N − 1 node ring such that no packets cross edge e (e is the new edge between node i − 1 and i + 1) and where the state of processor i + 1 is now X instead of 1 . (In other words, we replace processor i + 1's state with the value it would have had if processor i hadn't sent its packet over.) So, Next, suppose that the situation is Again, we can use the same kind of reasoning as above. In this case, the N − 1 node ring crosses at e, even though no packet arrives at processor i + 1. Therefore, to account for the packet absorption at processor i, we pad an extra packet onto the state of processor i + 1.
To make sure that we force a crossing at edge e, we calculate There is one new wrinkle, though. Since the packet which remains in queue in our N − 1 node ring actually enters the ring and gets a destination (of 1) in the real N -node ring, we must multiply the probability by 1/2. Thus, Then, using the above arguments, Next, suppose that processor i + 1 has 1 packet in queue. Suppose that the state of edges e 1 and e 2 is Next, suppose that e 1 and e 2 are (The "2" is caused by a packet that doesn't drop in the induced N − 1 node ring.) Next, suppose that e 1 and e 2 are Next, suppose that e 1 and e 2 are Next, suppose that processor i + 1 has 2 packets in queue. Suppose that the state of edges e 1 and e 2 is Next, suppose that the edges e 1 and e 2 are Next, suppose that the edges e 1 and e 2 are Next, suppose that the edges e 1 and e 2 are

The Balance Equations
We're all set to verify the balance equations now. Suppose that we are in state σ, which is: i.e. we are looking at processors i and i + 1, with preceding edges labelled e 1 and e 2 , respectively. As I've argued above, it is sufficient to consider the cases where n i and n i+1 are ≤ 2, and we can assume that h i+1 = 1. If we specify whether or not e 1 and e 2 are open, we split the possible preceding states into 4 disjoint sets. Therefore, the probability flowing into σ is Probability into Probability into In the preceding two sections, I calculated all the values we need to evaluate the above equation. Moreover, I expressed the values as multiples of (Since the probabilities are product form, I trust that the preceding notation makes sense.) Therefore, we can immediately factor out a factor of I only need to verify that the 4 factored terms sum to 1 in all cases. (I will work out the first case with extra details to illustrate what I'm talking about.) The verification of the cases follows: Suppose that h i = X. Suppose that h i+1 = 1 and n i+1 =0. Then the probability flowing into σ is Now, Pr → X → and Pr → X → both equal zero, so the third and fourth terms of the sum go away. Plugging in from our previous calculations, we get: as desired.
Next, suppose that h i = X, h i+1 = 1 and n i+1 =1. If we repeat the reasoning above, we find that the probability flowing in to σ is Note that the coefficients that arise from the situations (regardless of how we set the edges e 1 and e 2 ) are identical to those in the For example, if we deal with the h i = X, h i+1 = 1, and n i+1 = 2 case, we find that the probability flowing in is where the terms marked coef are determined by the state of processor i+1 (i.e. independent of the state of processor i). Therefore, we only need to test if the balance equations work for n i+1 = 0 or 1; the n i+1 = 2 case follows from n i+1 = 1.
Next, observe that if processor i is in state − n i 2 − for n i =0, 1, or 2, then the coefficients that we calculated are identical to those when the state of i is − X −, and we just verified that the balance equations hold for that case. Therefore, we can assume, that h i = 1 for the remaining cases. Suppose that n i = 0 and n i+1 = 0. (We are assuming that h i+1 = 1 in all these cases.) Then the probability flowing in to σ is Suppose that n i = 0 and n i+1 = 1. Then the probability flowing in to σ is As observed above, the fact that the n i+1 = 1 case holds implies that the n i+1 = 2 case holds, too. Suppose n i = 1. Now, if n i+1 = 0, we can just perform this whole procedure on processor i + 1 instead of i, and we are reduced to a prior case. So we are left with n i+1 = 1. Then the probability flowing in to σ is We have now accounted for all cases, completing the proof. ✷

Future Work, and a Warning
Given the surprising number of different protocols present in the statement of Theorem 3, it's natural to surmise that the result holds for any greedy protocol on the ring. Somewhat more optimistically, Lemma 4 suggests that the distribution might hold with any greedy protocol on any network, assuming that the maximum path length is 2. However, there does not seem to be any simple proof along these lines. I should insert a note of caution at this stage. After noting the exact solution to the N = 3 node ring, it's tempting to imagine that the stationary distribution for any N product form, and the stationary probability of a particular state is a rational function of p. After we have some more results about Bernoulli arrivals and analytic functions, I'll be able to show in Section 5.2 that the distributions are not product form, and probably not rational.

Introduction
In this chapter, I analyze stability and expected queue length for standard Bernoulli rings. In order to deal with rings where both the number of nodes N and the maximum path length L are large, I can no longer make exact calculations of the expected queue length, as I did in Chapter 2. Instead, I offer various upper and lower bounds.
Recall from Theorem 1 that, for a fixed nominal load r < 1/2, the expected queue length of an N node standard ring is known to be Θ(1/N ). The case of interest is r ≥ 1/2. I begin by generating a series of lower bounds on expected queue length. The most interesting bounds are Ω(1/N ) for the standard Bernoulli ring, and Ω(1) if either N or L is constant in a non-standard Bernoulli ring.
I start the upper bounds in Section 3.3 by showing that if r < 1/2 + ǫ, then the ring is stable and has an O(1) upper bound on the expected queue length if r < 1/2+ǫ. (The exact value of ǫ can be determined by an equation specified in the proof.) As the improvement in r is so small, this result is mainly interesting in that there are no hidden constants in the upper bound, and in the novelty of the technique.
Then, we get down to brass tacks. In Section 3.4, I construct a potential function for the standard Bernoulli ring, and prove a number of useful lemmas about the function. I use this potential function in Section 3.5 to show that for any r < 1, the ring is stable, and the expected queue length is O(1). A Θ(N ) bound on expected delay per packet follows. Finally, in Section 3.6, I discuss related results on the expected queue lengths of other rings with Bernoulli arrival processes.

Lower Bounds
Lemma 6 Fix the nominal load 0 ≤ r < 1. Consider a family of nonstandard Bernoulli rings of size N (i), with packet lifespans uniformly distributed from 1 to L(i) (where L(i) ≥ 2, to make it non-trivial), for i = 0, 1, 2, . . .. Then the expected queue length per node is Ω(1/L) Proof. I will calculate a bound at node 1; by symmetry, the same bound applies at any node.
In Corollary 12, I will show that all rings are stable. Assuming this result for the moment, we can use Little's Theorem (Theorem 31) to conclude that the probability that there's a packet at node 1 is r. Since we're using a "route, then arrive" method of sampling the state space, and since the probability of a packet arriving at node 1 on any time step is p = 2 L(i)+1 r, then the probability of there being a packet at node 1 after routing, but before exogenous arrivals, is at least Since we assumed that L(i) ≥ 2, then ≥ r 3 So, the probability that there is at least one packet in queue at node 1 after arrivals is at least , this is not always the case, as demonstrated by the next lemma.
Lemma 7 Fix a nominal load r on a family of nonstandard Bernoulli rings, labelled as in Lemma 6. Assume that N = o(L), and that L(i) is increasing. Then there exist constants 0 < α r , β r < 1, depending only on r, such that for all sufficiently large L(i), Proof. The probability that every packet now in the ring departs in (L(i)/3) − N (i) time steps is at least for sufficiently large L(i) (here, we're using N = o(L)). The probability that there is at least 1 exogenous packet arrival in each queue during (the same) (L(i)/3) − N (i) time steps is at least: For sufficiently large L(i), So for some fixed 0 < α r < 1 and all sufficiently large i (and hence L(i)), we can lower bound Equation 3.1 by Note that since there are at least N (i) exogenous packet arrivals and N (i) departures from the ring in (L(i)/3) − N (i) time steps, then by the L(i)/3 time step, there will be N (i) packets inserted, each having travelled less than L(i)/3 steps. The probability that the N (i) packets newly injected into the ring during the first (L(i)/3) time steps survive at least L(i)/3 steps is 2 3 In this event, on time steps L(i)/3 through 2L(i)/3, the entire ring remains full of the same N (i) packets. The probability of at least 1 exogenous packet arriving at node 1 during the time steps for sufficiently large i and some fixed 0 In this case, the packet arriving at node 1 will remain there for at least L(i)/6 time steps. Therefore, with probability at least node 1 has at least one packet in queue for L/6 time steps out of 2L/3 time steps. Since (L/6)/(2L/3) = 1/4, the expected queue length at node 1 is at least gives a much tighter (larger) bound on the expected queue length than Lemma 7 unless L is very large relative to N . Specifically, ifα −N r = o(L), then Lemma 7 is tighter.
We are really interested in certain special cases: be the expected queue length. From Lemma 6, we get: From Lemma 7, we get: What really happens in the regime where N = o(L)? Is Lemma 6 tight, until Lemma 7 takes over? It's not clear what to expect. For the purposes of this thesis, though, Corollary 4 suffices.

Load of 1/2 + ǫ
In Coffman et al. [14] and [15], the authors show how to analyze a standard Bernoulli ring in the case where loading is strictly less than 50% (i.e. r < 1/2). They are able to prove Θ(1/N ) bounds on the expected queue length per node. In this section, I'll show how to prove stability and O(1) upper bounds for a slightly larger range of loads, namely r < 1/2 + ǫ, where the ǫ can be explicitly calculated.
Theorem 6 Suppose we have an N node standard Bernoulli ring in any state at time t = 0, with load r < 1. Choose a node i. Then for any δ there exists N δ such that for any N ≥ N δ , at any time t > N , the probability of an empty cell arriving at node i is at least for any A, B, C, D such that A, B, C, D, (A + B + C + D) ∈ (0, 1). Moreover, the bound holds independently for all t > N .
Note: Observe that for any fixed A, B, C, D, r, we can always choose δ small enough that Equation 3.2 is greater than (1 + ǫ)/N for a sufficiently small ǫ, and all sufficiently large N .
Proof. Let j be the node that is ⌊AN ⌋ nodes downstream of i (so j = i + ⌊AN ⌋ mod N ). Let k be the node that is ⌊BN ⌋ nodes downstream of j, l be the node ⌊CN ⌋ nodes downstream of k, and m the node that is ⌊DN ⌋ nodes downstream of e. For sufficiently large N , these nodes are all distinct. Throughout, I'm going to treat ⌊AN ⌋, ⌊BN ⌋,⌊CN ⌋ and ⌊DN ⌋ as integers; the extent to which they are not leads to the δ error term in the theorem. Please see Figure  Let's follow the slot in the ring that starts out under node i at time 0, and see what packets enter and leave as the slot travels around the ring. What's the probability that any packet in i at time t = 0 departs before reaching node j? Well, suppose that there's a packet in i. Regardless of the packet's point of insertion, the probability that it departs in the next AN steps is at least A. (If there is no packet in i, the event occurs with probability 1.) Given that the original packet (if any) has departed by node i, what's the probability that a new packet will arrive in that slot by node j? If the slot passes under any non-empty queue, it will pick up a packet with probability 1. If not, there's a probability p of a new arrival on each step. Therefore, the probability of a new packet arriving by node k is at least: where the limit is taken as N → ∞.
What's the probability that this first arrival lasts until node k? Well, the earliest it could have arrived is node i + 1, so the probability is at least The probability that this packet leaves by node l is C, since the latest it could have arrived is node k.
The probability that a second packet arrives by node m is 1 − e −2rD , by the same arguments as above.
The chance that this second packet lasts until it reaches node i is Putting all of these (independent) probabilities together, we find their joint probability is: The probability of an empty cell arriving at node i is then (The probability of a packet leaving after one step is always at least 1/N , which gives the 1/N factor in the second term.) Expanding this equation, we get Equation 3.

✷
We can evaluate the theorem with some fortuitously chosen values.
Corollary 5 Set A = C = .217300, B = D = .196640 in Theorem 3.2. Then for any δ > 0, there exists N δ such that for any N > N δ , the probability of an empty slot arriving at node i at any time after t = N is at least We can translate this result into a statement about queue lengths.
Theorem 7 Consider a node in any network. Suppose it has Bernoulli arrivals at rate p, and the chance that no internal packet arrives at the node is at least µ, independently on every step. Suppose that µ > p, and no more than one internal packet can arrive on each time step. Then the time expected queue length at the node is bounded by If this equation (with possibly different values of p and µ) holds at every node in the network, then the network is ergodic.
Proof. Compare the number of packets in the queue in the network to a Bernoulli arrival, geometric service time single server queue with rates p and µ. We can relate the stochastic processes so that arrivals occur at the same time, and if there is a departure from the single server queue, then there is a departure from the original queue, if it is non-empty. (The original network may, possibly, have more departures.) The original network has all the same arrivals, and possibly more departures, than the single server queue does. Therefore, the number of packets in the former is bounded by the number of packets in the latter. The expected queue length for the single queue case is worked out in Theorem 29, giving Equation 3.3.
If the bounds hold at every queue, then the total number of packets in the system is bounded by the sum of these Bernoulli queues. It follows that the original stochastically dominated network is ergodic. ✷

Note:
This basic argument appears in a number of places, including Coffman et alia [14].
Putting together the results so far, we have the following corollary: Corollary 6 There exists an ǫ ≥ .000026802248 such that for all sufficiently large N , an N node ring is stable for loads of r < 1/2 + ǫ, and the expected queue length per processor is O(1).

Lyapunov Lemmas
In this section, I will construct a function Φ on the state space of the standard Bernoulli ring and show that as the ring evolves in time, Φ tends to decrease on average (with exponentially tight bounds on the probability that it increases). This kind of decaying function is sometimes called a Lyapunov or potential function. In the next section, I will use these lemmas to prove that for any r and sufficiently large N , the system is ergodic, and the expected queue length per node is O(1). First, some definitions.

Definition 8
If the probability that a packet crosses (blocks) a node i is greater than zero, then we say that the packet can reach node i.
Next, I will define a function Φ from the state space to the positive reals, and various helper functions.
Suppose we are in state σ. Choose a node i and a packet z. Suppose, for a moment, that packet life times in the ring were uniformly distributed between 1 and (1 + δ)N time steps, rather than between 1 and N − 1. Let f (i, z, σ) be the probability that packet z can reach node i (at least once) if z had a (1 + δ)N distribution on its life span. For instance, if z is from node k, at node j, and we label the nodes such that k ≤ j ≤ i, then Then the sum of f over all packets that can reach i (under the the N − 1 distribution of life spans) is: and our non-negative function on the state space is: It's often clear from context what σ is (namely, the current state of the system), in which case I'll drop it from the notation, and write Φ, φ(i), f (i, z).
Expressed in English, φ(i, σ) is the expected congestion at node i if all the packets had a uniform (1 + δ)N distribution on their life spans. One other piece of notation I'll want to use: Definition 10 Let Q i (σ) be the number of packets waiting in queue in state σ. If we are talking about a fixed state and the σ is implicit, I'll just write Q i .
To motivate why our definition of Φ might be useful, consider the following lemma: That is, if the random variable τ is the state of the system on the next time step, Proof. Since Q i (σ) > 0, then we are guaranteed that a packet will leave node i. This will reduce φ(i) by 1.
A new, exogenous packet arrives j nodes upstream with probability p, and increases Summing over all j, we get an expected increase of Finally, for any packet z in a cell, f (τ, z, i) is precisely the probability of remaining in the system in τ , times the (increased) probability of needing to cross i in τ . If packets had a (1 + δ)N distribution on life spans, the expected change in φ(i) from any packet z would be zero; since the actual life span distribution is stochastically less (i.e. the probability of z's departure is strictly greater), then its contribution to the expected change in φ(i) is negative.
Adding these three factors together, we get Equation 3.5. ✷ Lemma 3.5 is useful for motivating us, but it doesn't directly prove anything about the drift of Φ. It has two failings. First, we need Q i to be greater than zero. Second, we need the drift of the maximum φ(i) to be negative, which requires a bound on the simultaneous decay of all large φ(i). Fortunately, we can dispose of these two problems. First, we need a trick to guarantee that Q i > 0 when we want it to be.
Suppose we are in a fixed state σ. Then a lower bound on φ(i − 1) in terms of φ(i) and Q i is: Note: The reason this equation is useful is that, rearranging, we get a lower bound on Q i : Proof. Define C j as the contribution to φ(j) from hot potatoes (packets in cells), so Then we can write φ(i) as the contribution from packets in cells, plus the contribution from packets in queue.
We take the index of Q i+j modulo N so that it always falls between 1 and N (inclusively). (The packets in queue i + 1 can't reach and block node i, so we start the sum with j = 2 instead of j = 1.) We can write φ(i − 1) in the same way: Let us compare the sums in Equations 3.8 and 3.9. Ignoring the j = N term, the jth term in Equation 3.9 is larger than the jth term in Equation 3.8 by a factor of .10 is minimized when j = N − 1, so every term is larger by a factor of at least Consider the C i−1 − ζC i term. Take any packet in the ring at node j, from node k, that can reach node i, but isn't there yet. Label the nodes so that k ≤ j < i. Then observe that z is more likely to cross node i − 1 than i, so f (i, z) < f (i − 1, z). More precisely, define Therefore g is only really dependent on the difference between i and k, i.e. we can write where the ζ comes from the k = i term. Plugging back in to Equation 3.11, we get Note: Actually, the queue length at φ(i) = Φ is greater than or equal to the mean of all the other queue lengths. This result follows by looking at the preceding theorem a little more carefully. Lemma 8 illustrates the three parts of the drift we have to analyze: • the increase in φ(i) from new, exogenous arrivals; • the increase in φ(i) from packets in the ring that remain in the ring (so that their probability of using node i increases); • and the decrease in φ(i) from packets that depart from node i.
Let's look at each of these three contributions to the drift in turn.
Lemma 10 (Exogenous Arrivals) Fix r (and a corresponding δ andr), and choose any ǫ 0 > 0. Suppose we start in some fixed state σ on an N node ring. Let B(γ, i, t) be the event that in the next t time steps, the increase in φ(i) from exogenous arrivals is greater than (r + ǫ 0 )γt, for any γ ≥ 1. Then there exist N 0 , T 0 , K 0 such that if N ≥ N 0 and t ≥ T 0 , then for any γ ≥ 1, Divide the ring into D = 1/ǫ 1 segments. Each segment is of length L = ǫ 1 N nodes. Label the segments 1, . . . , D. For simplicity, assume that ǫ 1 N, 1/ǫ 1 and δ/ǫ 1 are integral; the analysis for arbitrary values is basically identical. Let β 0 =r +ǫ 0 r+ǫ 0 /2 . Note that β 0 > 1. Let β = β 0 γ. Fix a node i. Suppose without loss of generality that i is in segment D. Consider the contribution to φ(i) from a packet arriving in segment J < D. Since the packet must cross D − J − 1 entire segments between J and D, then the contribution is at most The contribution from a packet arriving in segment D is at most 1, of course, but to maintain consistency, I'll just bound it by Next, we will bound the number of arrivals to each segment. Let A(J, t) be the total number of arrivals to segment J in t steps. Since the total number of arrivals to segment J in t time steps is a sum of Bernoulli processes with mean 2rǫ 1 t, and since β ≥ β 0 > 1, we can use Lemma 23 from Appendix A to conclude that there exists K 1 such that Since J ranges over finitely many values (namely D), we can select a T 0 and K 0 such that By Equation 3.13, and since β = β 0 γ, Therefore, Equation 3.12 holds. ✷ Next, we will bound the expected maximal increase in φ(i) caused by packets travelling in the ring. Suppose a packet z can reach node i. Suppose further that z is a hot potato travelling around the ring. On every time step, if it doesn't depart the ring and if it doesn't cross i, then f (i, z) is strictly increasing. The next two lemmas show that this increase in φ(i) is negligible for all i.
Lemma 11 Assume we are in state σ, where packet z starts at node j, was inserted at node k, and is being measured at node i, and that k ≤ j < i. Suppose that z remains on the ring for one step, to state τ . Then In other words, the largest possible one-step increase in φ contributed by a hot potato packet is less than 1/(δN ).
Proof. Using Equation 3.4, we get And suppose, without loss of generality, that k = 1. Then we have For any fixed i, this equation is maximized when j is large. Since j < i, we get the restriction This equation is maximized when i is large, so we can set i = N − 1 and get Now, let us calculate a bound on the expected change in φ from hot potato packets.
Lemma 12 (Hot Potatoes) Fix r (and a corresponding δ andr), and choose any ǫ 0 > 0. Suppose we start in some fixed state σ on an N node ring. Let G(γ, i, t) be the event that in the next t time steps, the increase in φ(i) contributed by packets travelling in the ring is greater than ǫ 0 γt, where γ ≥ 1. Then there exist constants T 0 and K 0 such that for any t ≥ T 0 , there exists N t , such that for any N ≥ N t , and any γ ≥ 1, Proof. Let We will determine an additional upper bound on ǫ 1 later in the proof. Divide the ring into D = 1/ǫ 1 segments. Each segment is of length L = ǫ 1 N . Label the segments (in order) 1, . . . , D. For simplicity, assume that L and D are integral; the general analysis is pretty much the same. Fix a node i from which we will measure φ(i). Without loss of generality, let i be in segment D. Let us consider a hot potato packet z that can reach node i (and hence contributes to φ(i).) Observe that we can approximately describe a hot potato packet in terms of the segment it arrived in, and the segment it is currently in. If ǫ 1 is small enough, this information is sufficient to get fairly close bounds on f (z, i) and on the probability of packet z departing in a finite number of steps.
More exactly, suppose that packet z is at node j in segment J, originating from node k in segment K. Please see Figure 3-2. It's possible for a packet to enter segment D twice; Assume that we have labelled the nodes so that k ≤ j ≤ i, and K ≤ J ≤ D. Then the probability that z departs on the next step is 1/(N − 1 − (j − k)). We can lower bound this probability by 1 Note that the probability of a packet departing increases with each step it spends travelling on the ring, so the probability that z will depart on the next t time steps is at least , so our lower bound on the probability of a departure is Ct/N .
Suppose that there are at least ǫ 2 L packets in segment J from segment K, for some ǫ 2 > 0 (to be determined later in the proof). Then the number of these packets departing over the next t steps can be lower bounded by a sum of at least ǫ 2 L Bernoulli variables, each of probability Ct/N . We can now use Lemma 24, so for any sufficiently large t, we have an exponential tail on the sum. More precisely, suppose that there are Y packets in the segment class (where ǫ 2 L ≤ Y ≤ L), and X of them depart in t time steps. Then, for any ǫ 3 > 0, there exists T 1 and K 1 such that for any γ ≥ 1, if t ≥ T 1 , (because the mean is bounded below by (Ct/N )Y .) Now, by Equation 3.4, the contribution to φ(i) caused by z is So, the increase in φ(i) over t time steps, should z fail to depart, is We can bound this by (If t and ǫ 2 is fixed and N grows, then eventually L > t holds.) Instantiating W back in, we can further bound the equation.
On the other hand, the minimum value of f (z, i) is We can now combine the bounds above to get some bounds on the change in φ(i) from all the packets in the same segment class as z over the course of t steps. Let s be the segment class of packet z. Suppose that there are Y packets in the segment class, where Y ≥ ǫ 2 L, and that there are . Let ∆ s 1 be the change in φ(i) contributed by these hot potatoes. Then ∆ s 1 can be upper bounded by Y times the maximum increase in φ(i) in t steps, minus X times the minimum value that z can contribute to φ(i). Plugging in, we find that the increase in φ(i) is less than Now, in the limit as ǫ 1 → 0, we get So, suppose we take ǫ 3 < δ/2. (There will be an additional upper bound on ǫ 3 below.) It follows that Therefore, if we take a sufficiently small ǫ 1 , we can make Equation 3.20 less than zero. Thus, Equation 3.20 gives us our second upper bound on ǫ 1 . In summary, we have: In order to get exponential tails on the probabilities, we have to analyze the behavior if X is a bit smaller.
be the corresponding change in φ(i) contributed by the class s hot potatoes. Then , where Z will be determined below (and Z will depend only on δ and ǫ 0 .) (This is the second upper bound on ǫ 3 .) Then Let ∆ s be the change in φ(i) contributed by the class s hot potatoes if Y > ǫ 2 L, with no restriction on X. Using the exponential tail in Equation 3.16 and the linearity of Equation 3.23, we get for some K 2 > 0 and all t ≥ T 2 , for some T 2 . Let ∆ be the change in φ(i) from the hot potatoes in all the (D + 1) 2 segment classes. Then Equation 3.24 gives us for some K 3 > 0 and all t ≥ T 3 , for some T 3 .
If we take a snapshot of all the hot potatoes in the system at time zero, and ask how their contribution to φ(i) has changed by time t, then Equation 3.25 can tell us the change. However, during these t time steps, other new hot potatoes may enter a cell and begin travelling on the ring; these equations don't take those newer hot potatoes into account.
I will call these newly inserted hot potato packets inserted hot potatoes, as distinguished from the original hot potatoes. Recall that in order to satisfy Equation 3.16, we needed t ≥ T 1 . However, we can always make t bigger. Let T 0 = ZT 1 for some sufficiently large integer Z. (We will determine Z below). Let us take intervals of T 0 steps (i.e. set t = T 0 ).
Consider one slot in the ring. We will consider the time intervals (0, Then, the increase in φ(i) by those Y packets during the time interval (jT 1 , (j + 1)T 1 ] has a negative expected value with exponential tails, by Equations 3.25. Let∆ be the total change in φ(i) contributed by hot potatoes travelling during these time intervals. Adding together all Z time intervals, and using Equations 3.25, we get that for γ ≥ 1, for some K 4 > 0 and all t ≥ T 4 , for some T 4 . Note that Equation 3.26 holds simultaneously for all nodes i.
Let us consider the increases in φ(i) from inserted hot potatoes that I didn't account for above. There are two cases. First, there may be fewer than ǫ 2 L packets during a time interval (jT 1 , (j + 1)T 1 ]. Let∆ 2 be the change in φ(i) from these packets. Recall from Lemma 11 that the maximum one-step increase in φ(i) from any packet is 1/δN . Then the maximum increase in φ(i) over all Z such time intervals, over all segment classes in segment J, is at most Summing over all D + 1 segments, we get Second of all, we must account for the initial contributions from the inserted hot potatoes. When a hot potato is inserted, we only started measuring its contributions to φ(i) from time jT 1 onward (for some j). Therefore, each inserted hot potato can travel for up to T 1 time steps before we started measuring its contribution to φ(i) in Equation 3.26. Let∆ 3 be the contribution from all inserted hot potatoes to φ(i) during these unmeasured steps.
How many inserted hot potatoes are there? Well, if there were more than N inserted hot potatoes during the T 0 time steps, then some of the inserted hot potatoes must have been inserted and then departed. More precisely, if there were N + m inserted hot potatoes, then there were at least m inserted hot potatoes that departed. The probability of an inserted hot potato departing in at most T 0 steps is at most T 0 /N . Let W be the total number of inserted hot potatoes. We can use Lemma 23 on the initial N inserted hot potatoes to conclude that for any β > 1, Assume that W − N < βT 0 and that The net increase in φ(i) over all the uncounted time steps is (by Lemma 11)at most Since N > T 0 , and canceling, we get So, our total increase∆ 3 has exponential tails: for some K 5 > 0 and all T 0 ≥ T 5 for some T 5 . The analysis above pretty much accounts for all the significant influences on φ(i) for any i. To get a full bound on φ(i), though, we must consider all the exceptional (and unlikely) cases.
First of all, if a packet crosses node i in T 0 time steps and departs after crossing i, the departure doesn't count (since we're only counting reductions in φ(i) caused by packets leaving the ring.) Let∆ 4 be this contribution to φ(i). However, this effect is negligible: since the maximum increase in a packet that crosses i in T 0 time steps is T 0 /(δN ) (from Lemma 11) and there are at most T 0 such packets, the increase (for a fixed T 0 ) can be bound by∆ For sufficiently large N this quantity can be made arbitrarily small. Next, there is a complication for packets in segment D, since the packets before i and after i have different statistics. I represented this difference by distinguishing the J = 0 and J = D segment classes. Let∆ 5 be the contribution from these two segment classes to φ(i). It's possible to show the increase in φ(i) for every i is well behaved, but it's easier just to consider the worst case: there are at most L such packets, each increasing φ(i) by at most T 0 /(δN ), leading to a maximum possible increase of T 0 ǫ 1 /δ. By the definition of ǫ 1 , we get the bound∆ Finally, suppose that nodes i 1 < i 2 < i 3 are in the same segment (say D), and a packet from node i 2 is travelling on the ring in another segment (say J). Then the packet contributes to φ(i 1 ), but not φ(i 3 ) (since it can't reach i 3 again.) Observe, however, that if the nodes in segment D are i 0 , i 0 + 1, · · · , i 0 + L − 1, then every packet that can reach segment D crosses node i 0 ; some of them may cross i 0 + 1; fewer of them may cross i 0 + 2, and so forth. Fix a segment class (of packets not in D). Consider the last node of D, node i 0 + L − 1. Suppose there are Y i packets from the segment class that can cross node i 0 + i. If Y L−1 < ǫ 2 L, then we know from above that the increase in φ(i 0 + L − 1) is inconsequential. Let us continue backwards across the ring from node i 0 + L − 1 until we hit the first node i 0 + w such that Y w ≥ ǫ 2 L. If there is no such node, we're done, because all the packets in the segment class only contribute inconsequentially to the nodes in segment D. Otherwise, if there exists w 1 such that Y w 1 ≥ ǫ 2 L, then we can take these Y w 1 packets, and perform our bounding analysis from above (and Equation 3.25 applies).
Let us continue even further backwards along segment D until we find the nearest node i 0 + w 2 such that Y w 2 − Y w 1 ≥ ǫ 2 L. We can then take the Y w 2 − Y w 1 packets specified and perform our bounding analysis again. The nodes between i 0 + w 2 and i 0 + w 1 may still be effected by this second batch of packets. However, the effect is that of less than ǫ 2 L packets per node, so it's inconsequential. We can continue this process all the way back to node i 0 . Let∆ 6 be the contribution from these packets to φ(i). Since there are at most L packets in the segment class, and each jump is at least ǫ 2 L, then there are at most 1/ǫ 2 such batches we need to consider, i.e. a finite number of batches. Therefore, for sufficiently large T 0 (i.e. sufficiently large T 1 with fixed Z) and any β ≥ 1, We now have all the equations to complete the proof. We are trying to bound the probability that there exists an i such that G(γ, i, t). For any t ≥ T 0 and γ ≥ 1, we can bound this quantity bỹ .31 tells us that for sufficiently large N T 0 , Pr ∆ 4 > ǫ 0 7 γt is zero. Equations 3.27, and 3.32 tell us that Using Equations 3.26, 3.30 and 3.33, we can conclude that there exists K 0 and T 0 , such that for any t ≥ T 0 , there exists N t , such that for any N ≥ N t , ∆ < e −K 0 γt which implies Equation 3.14, and we're done. Note that the size of T 0 is determined by the size of T 1 , which is determined by the exponentials in Equations 3.26, 3.30, and 3.33. The same equations determine K 0 . The size of N t is determined by Equations 3.17 and 3.29. ✷ Lemma 13 (Main Lemma) Fix any nominal load r < 1. Then there exist sufficiently large constants T 0 , K 0 , and N 0 , and sufficiently small ǫ 0 > 0 such that the following holds. Suppose that we are on an N node ring, for any N ≥ N 0 . Suppose that the network starts in any state σ, and T 0 time steps later is in state τ , where τ is a random variable. If Moreover, we can find sufficiently large constants T 1 , K 1 , and N 1 and sufficiently small Proof. If we combine Lemma 10 and Lemma 12, we get the following the conclusion: Suppose we are in state σ, and take any ǫ 2 > 0 such that 0 < 2ǫ 2 < 1 −r. Let d(i, t) be the increase in φ(i) over the next t time steps from exogenous arrivals and hot potatoes. Let D(γ, i, t) be the event that d(i, t) > (r + ǫ 2 )γt, for any γ ≥ 1. Then there exist N 2 , T 2 , and K 2 such that if N ≥ N 0 , then for any γ ≥ 1, and (assuming we took our T 0 large enough in the Lemmas), . Note that our choice of ǫ 2 was small enough to guarantee that ǫ 0 > 0.
Our first goal will be to establish Equation 3.35. Suppose that a node i has at least T 0 packets waiting in its queue. Then over the next T 0 time steps, it will be guaranteed of ejecting T 0 packets. Thanks to Equation 3.38, the expected change in φ(i) is at most These bounds are all well and good when node i has a sufficiently long queue, but Φ is the maximum over all i. How can we guarantee that every node with large values of φ also has a queue of length at least T 0 ? Lemma 9 will provide the trick we need. Let β > 1 and let We would like to guarantee that Q i is at least, say, 3T 0 . To guarantee this bound, it is sufficient that Let us define Φ N as: Let us suppose, then, that Φ ≥ Φ N . Observe that Φ N is Θ(N ). Therefore, we can find a K 0 such that Φ N ≤ K 0 N , as in the statement of this theorem.
Consider any i. If φ(σ, i) < αΦ(σ), then Equation 3.38 and Equation 3.41 imply that Since T 0 is (much) larger than 1, then To see that Equation 3.36 holds, divide it by η Φ(σ) . Then we need to prove

Ergodicity and Expected Queue Length
Once we have constructed a potential function with negative drift, there are a number of powerful theorems we can draw on. Section A.3 reviews this material. These drift theorems allow us to translate Lemma 13 into statements about the ergodicity and expected queue length of the system. Let us begin with some immediate ergodicity results.
where c j is the expected contribution to φ(i) from the packet in service, and Q j is the length of the jth queue. The c j terms add up to rN/3, but rather than calculate that, I'll just drop the (non-negative) term: , i.e. the expected queue length per node is independent of the node (because of cyclical symmetry).
Now, from Equation 3.43 we can write Because of Little's Theorem, we can translate this result into a tight bound on the expected delay of a packet.

Corollary 7
The expected delay per packet of an N -node standard Bernoulli ring with nominal load r < 1 is Θ(N ).
Proof. The expected delay of a packet consists of the expected delay while waiting in queue, plus the expected delay while travelling along the ring. Since destinations on the ring are uniformly distributed from 1 to N − 1, then the expected delay on the ring is N/2. Therefore, the total expected delay of a packet is Ω(N ).
Little's Theorem (Theorem 31) tells us that the expected delay at a fixed queue is the expected queue length times the arrival rate. Since the arrival rate is p = 2r/N and the expected queue length is O(1) per node, then the expected delay in queue is O(N ). Adding the N/2 expected delay in the ring, we have the expected delay of a packet is O(N ).
Combining the upper and lower bounds, the expected delay of a packet is Θ(N ). ✷

Other Bernoulli Rings
In this section, I will briefly discuss extensions of Sections 3.4 and 3.5. The reasoning is closely related to that of the standard Bernoulli case, so the proofs are only in outline.

The Bidirectional Ring
There is nothing terribly special about the standard Bernoulli ring, as indicated by the following theorem.
Theorem 10 Fix α > 0. Suppose we have a family of nonstandard Bernoulli rings, where the N th ring has N nodes, and parameter L = ⌊αN ⌋. Fix a nominal load r < 1. Then the expected queue length per node is O(1).
Proof. The arguments are identical to those for a standard Bernoulli ring, since the parameter L scales linearly with N . ✷ We can use this result to analyze a bidirectional ring.
Corollary 8 (Bidirectional Ring) For a fixed nominal load r < 1, and a Bernoulli arrival process, the expected queue length per node for a bidirectional ring is O(1).
Proof. Decompose the ring into two unidirectional butterflies, where L = ⌊(N − 1)/2⌋, as in Section 1.4. We then get two O(1) bounds on the expected queue length, which we can add together by the linearity of expectation.
There is a minor detail to worry about if N is even, because there isn't a unique shortest path to the node N/2 hops away. If we specify that these N/2 length paths are all (say) clockwise, then the decomposition above works. If we decide that the packet chooses between the two paths with equal odds, then we need to make some minor (and simple) adjustments, but the proof still follows. ✷

N constant, L → ∞
The technique for the standard Bernoulli ring works fairly well if the size of the ring is fixed.
Corollary 9 Suppose we have an N -node nonstandard Bernoulli ring with parameter L. Suppose that N is constant. Then for any nominal load r < 1, the expected queue length is Θ(1) as L → ∞.
Proof. We can repeat the results of Section 3.4, as in the standard Bernoulli case, but we need to take longer time steps. That is, the T 0 terms, which were O(1) in the standard case, become O(L). However, since there are only a constant number of nodes, we still get an O(L) bound for E [Φ]. As in Section 3.5, we can translate this into an O(1) upper bound on the expected queue length per node. This bound matches the Ω(1) bound from Section 3.2, giving a tight Θ(1) bound. ✷ It's worth considering the following intuitive analysis of the system. Suppose that, for a fixed N , we rescale time by speeding it up by a factor of L, and let L → ∞. Then the network begins to resemble a single-queue network with N servers, where each packet has an amount of work uniformly distributed from 0 to 1. The expected queue length is finite (because the variance is bounded). Changing the time scale of a network doesn't change the expected queue length, so this limit would suggest an O(1) limit for the expected queue length of the original non-standard Bernoulli ring.

L constant, N → ∞
The technique doesn't work quite so nicely if the ring grows while the parameter L is fixed. This weaker result is to be expected; since we are maximizing the φ(i) over all i, and the nodes are fairly independent, then we would expect an order log(N ) result for the maximum φ(i). In all likelihood, the lower bound is tight, and the expected queue length per node is Θ(1). There is probably a way to modify Φ to get the O(1) bound, but it's not obvious how.

Bounded Queue Lengths
If queues have a bounded maximum queue length in any (otherwise) standard Bernoulli ring, how does this effect the queue length? Well, suppose that the nth ring has an upper bound of B n on the number of packets in any queue. If a queue is full, any excess exogenous arrivals are simply deleted.
If the B n are bounded by some B, then obviously the expected queue length per node is O (1). But what happens if the B n are unbounded?
Corollary 11 Suppose we have a family of standard Bernoulli rings, where the nth ring is has a maximum queue length of B n . Then the expected queue length is O(1).
Proof. We can use exactly the same Lyapunov function Φ to show drift in this network; all the proofs are identical. The only difference in the analysis is that certain packets never arrive. This change only helps us to bound Φ (by strictly reducing the exogenous arrival bound in Lemma 10). Therefore, for any fixed nominal load r < 1, the expected queue length is O(1). ✷

Future Work
In order to prove the results in Section 3.4, I had to prove exponential bounds on the tails of unlikely events. These bounds ultimately came from Theorems 23 and 24. It should be possible to prove these sorts of results with any arrival process with appropriate exponential tails. For instance, if the number of packet arrivals in one time step has a geometric or Poisson distribution, then we ought to be able to show O(1) bounds on the expected queue length by using the same techniques from this chapter.
Can we extend these results to a continuous time ring? Consider the number of arrivals to a node in N steps. As N gets large, this distribution converges to a Poisson distribution. (The convergence of a rescaled Bernoulli process to a Poisson process is sometimes called a "baby Bernoulli" approximation.) Perhaps, then, we could construct a continuous time version of the GHP protocol, and show that under a Poisson arrival process, the expected queue length per node is O(1). (The natural continuous time version of the GHP protocol is not obvious, unfortunately.) Finally, let's consider higher dimensional variants on the ring. Suppose we have a ddimensional torus T = N 1 × · · · × N d . Suppose that packets arrive according to a rate p Bernoulli process at every node, and destinations are uniformly distributed throughout the torus. Every node has out-degree d, so suppose we allow a node to route packets along as many of these edges as it can. The appropriate queueing theory model for this network, then, will be its edge graph, T e (since each edge only routes at most one packet per time step), but I'd like to translate the results back to the original network T . (In T , the edges queues wait at the nodes; the queue at node t ∈ T consists of all the queues t e ∈ T e representing edges originating at t.) We still need to specify the protocol. We can route packets using dimensional routing, but not all possible conflicts are resolved. We need a refinement to the protocol. Suppose that we consider a subring R, and consider the packets travelling along it. Let us give precedence to hot potatoes travelling along the ring. Exogenous packets, and packets entering from another ring, all wait (in FIFO order) in queue. This protocol is a kind of higher dimensional GHP.
The techniques of this chapter should suffice to prove an O(d) expected queue length per node for any torus. (Because dimensional routing is inherently asymmetric, it would be difficult to strengthen this to an O(1) expected queue length per node in T e . If we symmetrized the dimensional routing, though, it would probably work.) If the torus had the same size in all dimensions, i.e. if N i = N j for all i, j, then it should follow that the expected delay per packet was Θ(dN ).

Introduction
In Chapters 2 and 3, I analyzed specific models of packet routing on the ring. That is, I specified the arrival process (Bernoulli), the distributions of packet life spans (uniform over some range), and the protocol (GHP, for the most part). Once these details were specified, I could attempt to prove ergodicity results and bounds on the expected queue length.
Could we do more? Might it be possible to prove the stability of the ring under any arrival process, with any protocol?
The answer, more or less, is yes. This chapter is devoted to the development of a technique known as the fluid limit approach. It allows us to establish the ergodicity of vast classes of queueing networks with relative ease.
The idea behind fluid limits is to take a stochastic process of interest (like the length of queues in a network), rescale it in time and space (e.g. speed up time by a factor of T , while simultaneously dividing the queue lengths by T ), and take the limit as the scaling goes to infinity (i.e. T → ∞.) It turns out that this process is well-defined in many cases of interest, and the limit (called the "fluid limit model") can be fairly simple to analyze. Laws of large numbers convert the stochastic system into a deterministic one, and the discrete number of customers in queues is transformed into a continuous ("fluid") quantity.
Fluid limit models are of interest because they give information about the original model. In particular, if the fluid limit model is stable, then the original stochastic system is stable. (I will define fluid stability later in this chapter.) There is a growing body of literature on fluid limits. The seminal paper establishing ergodicity by the fluid limit technique is by Dai [20]. The result was refined by Chen [12], and extended to higher moments (e.g. finiteness of expected queue length) by Dai and Meyn [23]. The fluid stability of the ring was proved by Dai and Weiss [22].
Given all the results I've just referenced, it may sound like there's nothing left to do; we should just look up the ergodicity results and rejoice. Unfortunately, there is a complication. The results apply to continuous time, but specifically exclude discrete time systems. I rectify that problem in Section 4.2, and extend the fluid limit approach to discrete time. We can now apply the other ring stability results from the literature and make conclusions about ergodicity on the (discrete time) ring under any greedy protocol.
A more limiting restriction of the networks studied in the literature is the dynamics of the stochastic processes. Let us consider the arrival process at a particular queue as an example. In a traditional network of queues, we imagine that the interarrival times (the amount of time between adjacent arrivals of packets to the same class) form a series of i.i.d. random variables.
But are interarrival times in packet routing networks really identically distributed? In actual networks, like the internet, there are brief periods with short interarrival times (i.e. lots of new packets arrive), interspersed with long periods of relative silence. These sorts of long-range correlations (and even self-similarity) have been verified empirically. See, for instance, the work of Crovella in [17] and [16].
The situation can be even more dire. Suppose that a malicious hacker decides to destabilize the network. He can inject packets from any node whenever he wants, but if he simply floods the network, he'll be detected and eliminated. Therefore, he'll try to destabilize the network not with brute force, but by timing his packet injections carefully. Because the packet injections are ultimately performed by a computer program (written by the hacker), we can model the adversary as a finite state machine, possibly using randomness in the choice of states (i.e. a randomized FSM). To simplify the problem, let us assume that the machine's state is independent of the state of the network (but simply executes according to its own internal logic). 1 Unfortunately for web surfers everywhere, this concept is modelled after a real-world phenomenon, the Distributed Denial of Service (DDOS) attack. A DDOS attack involves a hacker taking over a large number of computers on the internet, then instructing all of them to download the same web page. Although each computer only requests a few downloads, the number of computers involved and their simultaneity can crash major web pages. A fairly high-profile example of this occurred to Yahoo on February 7th, 2000 (see Richtel [42]).
To model these systems, we'd really like to allow more general stochastic processes. In Section 4.3 and onward, I show how to extend the fluid limit technique to handle hidden Markov processes (which allow us to simulate both long-range correlations and randomized FSMs). An immediate implication is the ergodicity of the ring under any greedy protocol in this more general setting.
[For the reader unfamiliar with fluid limits, or who doesn't trust that these dramaticsounding stability results really follow, I've included Appendix B as a self-contained primer. Contentwise, the appendix amounts to proving a special case of Dai's results. The results are general enough to apply to the Bernoulli ring, though. The proofs themselves are different and much simpler.]

A Drift Criterion for Stability
The first property to consider in a Markov chain is its ergodicity. Definitions of Markov chains and ergodicity can be found in Section A.1. Let us fix some notation:

Definition 11
We are considering a discrete time, irreducible, aperiodic Markov chain X(·). It has a countable state space, X . X y (t) is the state of the Markov chain at time t 1 For the reader familiar with the bounded adversaries of adversarial queueing theory, this model may sound faintly reminiscent. There are two crucial differences. First, the complexity of the bounded adversary is allowed to be arbitrarily great; for instance, the strategy need not even be recursively computable. Second of all, a bounded adversary has some associated constant B, such that it can inject a limited number of packets into any window of B steps. I view a randomized FSM as providing a much more reasonable model of an adversary, in that the complexity is bounded, but there is no artificial length B window to consider. when started in state y.
If t isn't an integer, then we interpret X y (t) as X y (⌊t⌋) I'm going to devote this section to proving that an apparently very weak drift condition is sufficient to establish ergodicity. First, I'll need to define a bounded norm on a countable state space.
Definition 12 Suppose we have a state space X . A bounded norm is a function | · | : X → IR + such that for any integer k, the set {x| |x| ≤ k} is finite.
For example, in many queueing systems, the sum of the queue lengths forms a bounded norm.
Theorem 11 Assume we have an irreducible, aperiodic discrete time Markov chain with a countable state space and a bounded norm, | · |. Suppose there exists T > 0 such that Then X(·) is an ergodic Markov chain.
Note: If you find the notation "lim |x|→∞ " vague, then specify an enumeration of the state space: x 1 , x 2 , . . .. Since for every k there are only finitely many x n with |x n | ≤ k, then lim n→∞ |x n | = ∞. We can then use this ordering {x n } above.
Note: A version of this theorem appears in Dai [20] as Theorem 3.1. Dai's version assumes that the interarrival and service times are unbounded and spread out (Equations 1.4 and 1.5,) which rules out discrete time systems. My proof removes that restriction (in discrete time). The only related discrete time theorem in the literature is by Malyshev and Menshikov [37], and is substantially weaker. The proof below also generalizes the role of the norm, which will be useful later in this chapter.
Proof. The existence of the limit implies that for any ǫ, there exists a sufficiently large bound L such that if |x| > L then 1 Now, consider the following function: Since we chose an L such that L ≥ 1, it follows that n(x) ≥ T for all x. Therefore, for any x, where L 1 , L 2 are some (finite) constants. To see that L 1 is finite, first observe that E |X x (n(x))| ≤ |x|+ (expected number of arrivals in n(x) steps), which is finite for any fixed x. Therefore, we can just take the maximum of E |X x (n(x))| − |x| + ǫL over all x ∈ B.
Since B is a finite set, this maximum exists. We can take L 2 = L 1 + L T ǫ. We now construct a new Markov chain (an "embedded chain"), as follows. We have our original transition probabilities, where p i,j is the probability of changing from state i to state j in one step, and p k i,j is the probability of changing from i to j in exactly k steps. Construct a new Markov chain on the same state space with transition probabilitieŝ The embedded chain (call itX(t)) represents a particular sampling of points from the original chain, namelŷ X(0) = X(0), X(1) = X(n(X(0))), X(2) = X(n(X(n(X(0)))) + n(X(0))), and so on. If we define s(t) by s(0) = 0, and s(t + 1) = n(X(s(t))) + s(t), thenX(t) = X(s(t)). (Note that s(t) isn't a deterministic function; it's a stochastic process.) Let τ B be the first return time to B in X(t); that is, τ B is a stopping time defined as the least time t ≥ 1 such that X(t) ∈ B. Letτ B be the first return time to B inX(t). Then observe that ifX has returned to B by time t, then X has returned to B by time s(t) (and possibly sooner). So, Considering the embedded chain, we can view Equation 4.2 as which tells us about the one-step drift ofX(t). Using the Comparison Theorem (Theorem 27), we conclude that for any x ∈ X , if we set X(0) =X(0) = x, then dividing both sides by ǫ/T and using Equation 4.3, we conclude that Thus, the expected return time to B from any state is finite, so (by Theorem 25), X(t) is a positive recurrent Markov chain. ✷ A more careful examination of the preceding proof reveals that we don't really need the limit to go to zero in Equation 4.1-it is sufficient that lim sup for any fixed ǫ > 0. Theorem 11 is sufficient to establish a universal stability result on the ring.
Corollary 12 Suppose we are routing on an N node ring in discrete time under any greedy protocol. Suppose that the ring is a generalized Kelly network (see page 137). Finally, suppose that the nominal loads are less than one at each node (see page 79), i.e. r < 1 at every node. Then the ring network is ergodic.
Proof. Suppose we replace the probabilistic model of the ring, with discrete packet arrivals, with a deterministic model, with continous quantities of packet "fluid" entering the system. The rates of flow in the fluid model are determined by the expected rates in the probabilistic model. Dai and Weiss [22] show that the fluid model of a ring is stable; that is, all the fluid eventually exits the system. Dai [20] shows that if the fluid model is stable, then Equation 4.1 holds. We can now plug into Theorem 11, and we're done.
If the reader is interested in a self-contained version of this for the standard (or nonstandard) Bernoulli ring, he or she can combine the results of Appendix B and Corollary 16. The more general results of the next sections, combined with Corollary 16, will give Corollary 12 on any ring with constant mean service times (not just Bernoulli ones.) ✷ The amount of time it takes a packet to cross an edge can be much more general than the deterministic behavior of Corollary 12, and the result will still hold. All we really need is that the ring is a generalized Kelly network.

Our Model of Packet Routing
I'm going to lay out all the assumptions I'll make about the packet routing model, and fix some of my notation. I'm making an effort to make this framework very general, so I'm not assuming (for instance) that the time it takes to cross an edge is one time step.
• We're operating in discrete time.
• Packets travel on an N node network, which can be an arbitrary directed graph.
Packets wait at nodes (rather than edges). For packet routing where packets queue on edges, we just consider the edge graph and perform our analysis there.
• Packets are members of a class. There are C classes (where C is finite). A class usually contains information such as a packet's destination, or possibly its destination and priority in the system. By queueing theory convention, each class occurs at only one node. (This is not restrictive-it's just a naming convention.) For a node i, let C i be the constituency of i, i.e. the collection of classes that occur at node i.
• Packets enter a node either from another node, or from outside the network. The first type of packet is called an internal packet, and the second type is called an exogenous packet.
In a traditional network of queues, the exogenous packet arrivals are determined by their "interarrival times". That is, there is a series of i.i.d. random variables that determine how much time passes between each arrival of a class c packet.
We're going to use a more general arrival process. (I'll demonstrate the reduction of the i.i.d. case to the following case later.) The exogenous packet arrivals are determined by a Markov process A(t) on a state space A. • Next, we need to specify the behavior of the internal packets. To avoid trivialities, I'm going to assume that at most one packet departs a node on each time step. The interested reader can generalize this appropriately.
We need to be a bit more careful with the packet routing than with the arrival process. We need to define a different Markov process for each class c.
When a packet leaves a node, it must either follow one of the outgoing edges to another node, or it must leave the network. These decisions are made by a Markov process R c (t ′ ) on a state space R c . ("R" stands for "routing".) For every class c at node n, and every node m with an edge from n to m, there is a subset R m c ⊆ R. The R m c are disjoint.
If a class c packet leaves node n and we're in state σ ∈ R m c , then the packet travels to node m. If σ ∈ R m c for any m, then the packet leaves the system. The t ′ variable in the Markov process R c (t ′ ) is not the time, but rather the number of packets that have been routed from class c so far (so tleqt ′ ). In other words, time only advances for R c (t ′ ) when packets are being routed; otherwise, the Markov chain remains frozen in the same state.
• Next, we need to determine how long it takes a packet to cross a node. As mentioned above, this amount of time is usually deterministically one in the case of traditional packet routing networks, but can be a collection of i.i.d. random variables of arbitary distribution in a more general network of queues.
For each class c, we define a Markov process S c (t ′ ) on the state space S c .
For each class c and integer i > 0, there's a subset S i c ⊆ S c such that for a fixed c, the S i c are disjoint. If we are working on a class c packet and enter class σ ∈ S i c , then i class c packets leave the node (although some may possibly reenter the node immediately, if there's an edge from the node to itself). If there are i 0 < i class c packets in queue, then all i 0 will leave immediately, and the next i − i 0 class c packets that have work done on them will immediately depart, i.e. have service times of zero. This means that it is possible for a packet to travel across several nodes in one time step. (If we set S i c = ∅ for any i > 1 and all c, then this strange node-hopping behavior never occurs.) As with the routing process, the t ′ counts the number of units of time spent servicing class c packets, so t ′ ≤ t.
The state of S c (t ′ ) will only advance after i packets of class c have left; otherwise, we remain frozen in the same state.
• A(t), R c (t) and the S c (t) are mutually independent, irreducible, aperiodic, and ergodic. For any state σ in any of these Markov chains, let p(σ) be the stationary probability of being in state σ.
The mean (exogenous) arrival rate of class c packets is: which we will assume to be finite.
The mean service rate of class c packets is: which we will also assume to be finite.
The mean transition probability of class c packets (from node k) to node l is: Let P be the matrix formed from the P kl . Assume that this matrix is transient, i.e.
I + P + P 2 + · · · is convergent This implies that the expected number of visits to class l by a class k packet is finite, i.e. we have an open queueing network. It follows from this equation that (I − P ′ ) −1 = (I + P + P 2 + · · ·) ′ Then, the effective arrival rate (in vector form) is: For a particular class c, the let λ c be the cth coefficient.
Finally, the nominal load at node n is ρ n = c∈Cn λ c /µ c • Our routing protocol is greedy, or work-conserving-if a queue is non-empty, it will always send some packet across an edge.
For example, a standard Bernoulli ring meets all the requirements listed above. Given a queueing system with all the features described above, it's fairly easy to view it as a Markov chain; we just have to build the state space. The details of the state space are determined to some extent by the protocol. For instance, consider node i under a priority discipline 2 , where certain classes of packets get priority over other classes of packets. We need to store the number of packets of each class currently at node i, to determine who should be serviced. If instead we were using FIFO to determine packet priority, then we would need to keep an ordered list of all packet arrivals, with the earliest arrivals at the front of the list. In order to determine when the packet being serviced (if any) is ready to leave, we need to keep track of our state in S c for every c. We need to store all this information for every node i.
To determine exogenous arrivals, routing choices and service times, we need to keep track of the state of the various hidden Markov processes. (This information is not per node, but for the whole network.) Given all this information (the arrangement of classed packets waiting in queues, along with σ A ∈ A, and, for all c, σ Rc ∈ R c , and σ Sc ∈ S c ), we have a Markov process X(t) on state space X .
We can now complete our definitions and notation for the queueing network.
• X is the queueing network's state space, as defined above.
• Let Q c (t) be the total number of class c packets in the system at time t. (Remember, all class c packets will be at the same node.) • If we start our Markov chain in state x, then the state at time t will be written X x (t).
In general, whenever I want to know the value of a quantity at time t when the system started in state x, I'll denote this by a superscripted x.
Also, it will be useful to refer to time continuously in addition to viewing it in discrete steps. So, for t a non-negative real, define X(t) = X(⌊t⌋), and similarly for the other quantities.

Building a Bounded Norm
I'd like to construct a bounded norm for X . To do this, I need to make a brief digression about countable Markov chains in discrete time. Suppose we have any discrete-time Markov chain M (t) on a countable state space M. Suppose that M (t) is aperiodic, irreducible, and ergodic.
Let us select (any) fixed state σ renew ∈ M. Consider every possible (finite) path through M that begins and ends in σ renew , but doesn't return to it at any other point. Let γ be such a loop. Let p(γ) be the probability that, starting in state σ renew , the Markov chain follows path γ back to σ renew . Because the Markov chain is ergodic, the expected return time to σ renew is finite. Therefore, the probability of M (t) never returning to σ renew is zero.
I'm going to construct a second Markov chain M ′ (t) on state space M ′ . Consider a loop γ = σ renew σ 1 · · · σ k σ renew through M. I'll insert states σ γ renew , σ γ 1 , · · · , σ γ k to M ′ . I'll also insert state transition probabilities such that the probability of changing from σ γ i to σ γ i+1 is 1, and the probability of changing from σ γ k to σ γ renew is 1. (I haven't specified the transitions out of σ γ renew yet.) Insert these σ γ i and edges for all loops γ with p(γ) > 0. Next, associate all the σ γ renew into one node, called σ ′ renew . (Notice that this may induce an edge from σ ′ renew to itself, in case there exists a γ ′ = σ renew σ renew with p(γ ′ ) > 0. If so, remove it.) Let the probability of travelling from σ ′ renew to σ γ 1 be p(γ). (This may re-introduce an appropriately weighted edge from σ ′ renew to itself.) There is a function f : M ′ → M that takes every node in M to the original node that induced it. Observe that we can stochastically couple the two processes such that f (M ′ (t)) = M (t). Now, consider the arrival process A(t). Suppose that we are in state σ ∈ A. As defined in the previous section, there are i arrivals to class c iff σ ∈ A i c . That is, the arrival process is a hidden Markov process, where the underlying process is A(t). So, there is some function h c : A → IN such that the number of class c arrivals at time step t is h c (A(t)). From the previous paragraph, this is equal to h c (f (A ′ (t))). Therefore, we might as well assume that the underlying Markov chain is A ′ (t), and the "hiding" function for determining arrivals is h c • f (). We can perform the same kind of change to the service time and routing processes.
Consider two loops in M ′ : γ = σ renew σ 1 · · · σ k σ renew and γ ′ = σ renew τ 1 · · · τ k σ renew (notice that both loops are k + 2 steps long). Suppose that for i = 1, ..., k, h c (σ i ) = h c (τ i ). If we were looking at the arrival process, for instance, then these two loops would generate the same packet arrivals on the same time steps, and renew in the same amount of time.
Since they are identical from the point of view of arrivals, we will amalgamate them into the same loop. (More precisely, we will remove γ ′ , and add the p(γ ′ ) to the probability of selecting the edge into the γ loop.) This final change will determine our state space M ′ . If we compare M and M ′ , it doesn't really look like we've done anything very useful to the state space. However, suppose we're in state σ ′ ∈ M ′ . Then we can (deterministically) count how many steps it will take until we enter σ ′ renew for the first time. (If we're in state σ ′ renew , this number is zero.) This will allow us to build a bounded norm.
Let us now define a norm on the state space X defined in Section 4.3. Recall that a state in X is determined by: • The arrival process state σ A ′ .
• The routing process states σ R ′ c for each class c of packet. • The service process states σ S ′ c for each class c of packet.
• The queue lengths Q c of each class c.
Then the norm on X is: The function | · | is a bounded norm on X ′ .
Proof. Consider the arrival process for a moment. Observe that if g A ′ (σ A ′ ) = B, then the loop γ that σ A ′ is on is at most of length B; at most B packets arrive across C classes, so there are (as an upper bound) at most (B + 1) CB possible packet arrivals that we will see. Since we are amalgamating loops with identical arrival patterns, that means that there are at most (B + 1) CB possible values for σ A ′ , which is finite. Analogous arguments hold for the other processes. Therefore, the function | · | is a bounded norm on X ′ . ✷

Fluid Limits
The purpose of the fluid limit technique is to find a practical way of checking Equation 4.1 for a system of queues. Dai [20] solved this problem in the case of i.i.d. interarrival and service times and Bernoulli routing in Section 4 of his paper. In this section, I'll show how to alter a few lemmas of his paper in order to translate the result to hidden Markov processes.
For the reader unfamiliar with fluid limits, please consider glancing at Appendix B. It contains a formal exposition of all the ideas behind taking a fluid limit. The appendix applies to the special case of a memoryless discrete-time system, as I feel that that better illuminates the important parts of the theorems.
There are two general points worth making about Dai's theorems before we begin. First of all, because of the generality of the Renewal Reward Theorem (Theorem 32), it is possible to extend many of Dai's results to hidden Markov processes without changing his proofs at all. Second of all, by delaying the fluid limit (considering it only after time fluid t = 1), we can obviate the need for some of the results. (Some of the "initial conditions" of the limits wear off in a finite amount of time, allowing laws of large numbers to take over; if we simply observe the fluid model after this second regime has begun, the mathematics is much more pleasant.) The idea of delaying a fluid limit to simplify it is due to Chen [12]. For our problem, the "initial conditions" are much more complicated than for Dai, and the delay is probably necessary to make the fluid limits well-defined.
Let us begin. Next, let us define some useful functions:

Definition 15
Let ♣A x c (t) be the total number of arrivals at time t to class c, from an initial state of x. (This is analogous to Dai's E x l (t).) Let ♣S x c (t) be the total number of packet departures from class c after t units of service, from an initial state of x. (This is analogous to Dai's S x l (t).) Let ♣R x c,d (t) be the total number of packet departures from class c to class d after t packets have been routed, from an initial state of x. (This is analogous to Dai's Φ k (t).) Extend these functions to non-integral t by rounding down t.
We can now convert Dai's Lemma 4.2 into a form more applicable to our model.
Then as n → ∞, for any t ≥ 1, almost surely Proof. Surprisingly, Dai's proof runs through unchanged. The key observation (using the arrival process as an example) is that by the Renewal Reward Theorem (which Dai calls "the strong law of large numbers for renewal processes"; see Theorem 32 in this thesis). Our hidden Markov processes undergo renewals (because, by assumption, they're ergodic), so we can apply the theorem. Because of our norm, we are guaranteed that the first renewal has occurred by time |x n |, so we don't have to account for the initial delay from x n . ✷ Recall that Q x c (t) is the number of class c packets in queue at time t, if we start in state x. There is one final property of a network of queues that we need to define:

Definition 16
Let T x c (t) be the cumulative amount of time that has been lavished on class c packets by time t. (Note that T is non-decreasing.) Dai's first main theorem, Theorem 4.1, is transformed into the following: Theorem 13 For almost all sample paths ω and any sequence of initial states {x n } ⊆ X with |x n | → ∞, there is a subsequence {x n j } with |x n j | → ∞ such that and for any t ≥ 1, for some functionsT (t) andQ(t).
Proof. By our norm, 1 |x n | Q xn c (0) ≤ 1 so we could use compactness (on [0, 1]) to find a convergent subsequence. However, we want to do this at t = 1. Observe, however, that we can bound the queue length at time |x n | by the sum of all the packets in the system, plus all the new arrivals (to all classes) in those |x n | steps. There may be a certain number of packets destined to arrive based on the initial state of the hidden Markov arrival process, but from the definition of our norm, that will account for at most |x n | new packets. Other new arrivals will be injected after a renewal. After a renewal, we can then use the strong law of large numbers to tell us that almost surely for some B. We can then use compactness (on [0, B]) to find a convergent subsequence. We can use the same reasoning onT . The rest of the proof follows along Dai's lines. ✷

We need one final definition:
Definition 17 Let a queueing discipline be fixed. Any limit (Q(t),T (t)) from Theorem 13 is a fluid limit of the discipline. We say that a fluid limit model of the queueing discipline is stable if there exists a constant t 0 > 0 that depends on α, µ and P only, such that for any fluid limit withQ(1) = 1, and any t ≥ t 0 ,Q(t) = 0.
We can now state the main result.
Theorem 14 Let a queueing discipline be fixed. Suppose we have a network of queues with hidden Markov processes, and the resulting Markov process X(t), as defined in Section 4.3. If (every) fluid limit model of the queueing discipline is stable, then the X(t) is ergodic.
Proof. With the modifications to the original lemmas that we've just made, Dai's proof still works. ✷ Finally, let's show that these hidden Markov processes are actually a generalization of the standard queueing theory results. Proof. This proof is similar to the arguments in Section 4.4.
Suppose we want to generate i.i.d. arrivals such that Pr(interarrival time at class i = k) = d i k . Assume that there exists d i k and at most 1 packet arrives per time step. Then consider a state space consisting of an infinite number of loops, where loop k has k nodes along it. Let all these loops share exactly 1 node in common, called z 0 . When we enter z 0 , we insert a packet. From z 0 , we select the first node in loop k with probability d i k . The existence of a mean arrival rate is equivalent to having finite expected return times to state z 0 , so the system is ergodic. It's pretty clear how to genearlize this process to allow batch arrivals (i.e. more than one arrival per turn to the same class). We have a Markov chain for each class, so if we take the Cartesian product of all these Markov chains, we get one Markov chain which generates all the exogenous arrivals for all classes. ✷

Future Work
In this section, I'm going to discuss some avenues for future research that seem promising.
• In Dai and Meyn [23], the authors show that if the stochastic processes involved in the fluid limits have finite nth moments, then the (n − 1)st moment of the expected queue length is stable. For instance, if the interarrival and service times all have finite variance, then the expected queue length is finite.
It should be straightforward to apply these results to networks with hidden Markov processes, too. The relevant property is probably the nth moment of the hidden process per renewal. For instance, for the arrival process, this variable is the total number of arrivals per renewal period. Continuing the example above, if the return time to state σ renew ∈ X ′ has finite variance for the arrival, service, and routing processes, then the expected queue length should be finite.
• Consider a countable family F of ring networks. Different networks may have different (greedy) protocols, and the rings may be of different sizes. Suppose that there is a maximum nominal load r < 1 for all nodes throughout the family. Suppose, finally, that the interarrival times and service times are i.i.d. and have finite variance, and the same bound on the variances apply to all the networks in F.
If we look at the fluid stability result of Dai and Weiss [22] on the ring (or look carefully at Corollary 16), we'll realize that the amount of time it takes for any fluid limit of any ring in the family to converge to zero can be bounded as a function of r, independent of the particular ring size or protocol.
It is tempting, then, to imagine taking a disjoint union of the state spaces of the rings in F. From any starting configuration, with any limit of initial states stretching over all the rings, the fluid limit will still converge to zero by a fixed point in time dependent only on r. Therefore, the whole family of rings would have a universal bound that would translate into an O(1) bound on the expected queue length. It would follow that for a fixed maximum load r, there is a universal maximum expected queue length Q r for any ring, with any greedy protocol.
There is quite a bit of work to be done to show that this works. The fundamental problem is that the step in Theorem 11 where we select an L fails to work; we have a series of L 0 , L 1 , . . . which may diverge to infinite. This difficulty seems surmountable, but additional assumptions about the family (or a more effective use of the bounded variance) may be necessary.
• If the previous suggestion holds for ring networks, it should also work on the "convex routing" networks discussed in Section 6.2.
• We could also consider taking a fluid limit on a ring with N = ∞. To make this problem well-defined, we must change the norm accordingly; rather than use the sum of the queue lengths, it may be more useful to use their lim sup. In any event, one might optimistically hope to gain knowledge about the asymptotic behavior of large rings by leap-frogging to the infinite.
• Throughout this chapter, I had to assume that all the hidden Markov processes driving the network were ergodic. Ergodicity applies in a more general setting than Markov chains-see, for instance, Dudley [24], Section 8.4. Is it possible to extend the fluid models to include these more general processes?
Because the system doesn't have Markovian renewals, it's probably better to prove stability through the techniques of Dai and Meyn [23] than of Dai [20]. If we try to generalize the proof, the first major difference we find is determining what kind of norm to use on the state. (The "state" now includes the state of the system at all times in the past.) After some thought about the purpose of the norm in fluid limits, we probably want to define a norm such that if we wait |σ| time steps, the ergodicity will have kicked in; in other words, for some fixed ǫ > 0, the observed arrival rates should have begun to converge within a factor of 1 ± ǫ of their expected values. The ergodic theorem tells us that such a value for |σ| ǫ exists.
We can then continue with most of the proof. Unfortunately, we are eventually faced with proving uniform integrability results for this system, and it's not clear how to proceed. Proving this result seems to require some new ideas for fluid limits that haven't been needed before.

Analyticity and Absolute Monotonicity
Consider the expected queue length at one node of a 3 node standard Bernoulli ring. The expected queue length can be expressed as a function of p, where p is the probability of a packet arriving at a node on one time step. From the results of Chapter 2, we know what this function is: Observe that this function is analytic, rational, strictly monotonic, and convex. If we consider the stationary probability of being in any fixed state, this function is also a rational function of p.
It's natural to ask ourselves how many of these properties hold for other packet routing networks. This chapter looks at some analyticity and monotonicity results that can be widely applied.
We mustn't be overly confident with our conjectures, though. Consider the two node Markov chain in Figure 5 switch states with probability p, and remain in the same state with probability 1 − p. If 0 < p < 1, then the probability π 0 (p) of being in state 0 is 1/2. But if p = 0, then π 0 (0) = 1. Therefore, π 0 (p) is discontinuous at p = 0. If we want to prove general smoothness results, we'd better avoid cases like this one.
It will be very useful to consider a strong type of monotonicity from which we can deduce various other smoothness and monotonicity results.
for all non-negative integers n and for all x and h such that Absolute monotonicity is useful because of the following facts: Proof. See Bernstein [2] and Widder [46]. ✷ A slight change in a paper by Zazanis [48] allows us to get our first interesting conclusion.
Theorem 16 (Zazanis) Suppose we have a discrete time queueing system where exogenous packets are inserted to classes according to a rate p Bernoulli arrival processes. Suppose that the system is ergodic if 0 ≤ p < p 0 . Then the expected queue length and the stationary probabilities for any state are analytic functions on 0 ≤ p < p 0 .
Proof. Zazanis [48] proves this result in continuous time for Poisson arrivals. His proof amounts to showing that a particular function is absolutely monotonic, and hence analytic. He begins his Theorem 3 with his Equation (1): (A derivation of this formula, which Zazanis merely quotes, can be found in Brémaud [10], particularly pages 190-191.) The discrete time analogue (where p replaces λ) is The rest of the changes to Zazanis' proof follow immediately from replacing his equation 1 with Equation 5.2 above. ✷ A special case is, of course, a Bernoulli ring: Corollary 13 For any fixed N , the expected queue length per node of a standard Bernoulli ring is an analytic function of p on p ∈ [0, 2 N ). The stationary probability of being in any fixed state is also an analytic function of p on the same interval.
Proof. We established the ergodicity for 0 ≤ p < 2 N in Chapter 4, so we can use Theorem 16. ✷

Light Traffic Limits
Note that the functions in Theorem 16 are analytic at p = 0. This means that the Taylor expansion around p = 0 is well-defined and agrees with the actual function in some ǫneighborhood. Calculations taken in the limit as p → 0 are sometimes called light traffic limits. Theorem 16 shows that for Bernoulli arrivals, the light traffic limits are well defined.

Product Form Results
We can use these light traffic limits to prove that certain stationary distributions are not product form, answering a question posed in Section 2.9 Theorem 17 For N ≤ 3, the stationary distribution of a standard Bernoulli ring is product form. For N ≥ 4, the stationary distribution is not product form.
Proof. Chapter 4 shows the existence of stationary distributions for all N when the nominal load r < 1. The results of Chapter 2 showed that the stationary distribution is product form for N ≤ 3. Assume that N ≥ 4. I will continue to use the state notation of Chapter 2, where · · · − n t − · · · represents a node with n packets in queue, and a hot potato with t steps left to travel (so 1 ≤ t ≤ N − 1). An empty node (no packets in queue, and no hot potato packet in the ring) is represented as · · · − X − · · · Imagine that packets travel from left to right. Consider the state σ where all nodes are empty except for two adjacent nodes: The stationary distribution of Pr[σ] can be Taylor expanded around zero in the form: Define σ 0 to be the ground state, where every node is in state X . In Theorem 44, I show that in order to calculate a i , we only need to consider contributions from states that are reachable from σ 0 by inserting at most i packets. Since it takes two packet arrivals to get to σ from the ground state, then a 0 = a 1 = 0. Let's figure out what terms contribute to a 2 .
We can calculate the stationary probability of σ by adding the stationary probabilities flowing in to it. However, since we're only going to look at terms of order p 2 and lower, then we need only look at states that are attainable with two or fewer packets: =, I mean that the p 2 and lower terms of the Taylor expansion are equal.) Let τ be the result of reversing σ, i.e. all nodes are empty except for two adjacent nodes: If we consider the possible prior states reachable with two or fewer packet arrivals, there is (This asymmetry is due to the fact that three packet arrivals are necessary to get to a state Note that the p 2 term in · · · − 1 N − 2 − X − · · · is 1/(N − 1), which is non-zero. Now, assume for a moment that the distribution were product form. Then the first three terms on the right hand side of Equation 5.3 would equal the three terms on the right hand side of Equation 5.4. Since the p 2 term in · · · − 1 N − 2 − X − · · · is nonzero, it follows that the p 2 term in Pr[σ] is different from the p 2 term in Pr [τ ]. Because these are analytic functions of p at p = 0, it follows that Pr[σ] = Pr[τ ], except at a finite number of points. This fact contradicts the assumption that the distribution was product form. ✷ Another interesting family of rings are the geometric rings of Coffman et alia [14], [15]. (The following theorem doesn't use light traffic limits, but it makes a nice counterpoint to Theorem 17.) Theorem 18 Fix λ, µ, such that 0 < λ < µ. Suppose for any N , we have an N -node ring where a packet arrives at each node with probability p = λ/N , and departs on each step it travels with probability µ/N . Then there are only finitely many N such that the N node ring has a product form stationary distribution.
Proof. Suppose not. Let us restrict our attention to the infinitely many N with product form stationary distributions. Then the probability of the ground state σ (where all the nodes are empty) is the sum of all the stationary probability flowing in to it. A state τ preceding σ has t ≤ N packets travelling in the ring and no packets in queue, and becomes state σ with probability Let Pr X be the marginal probability that a node is empty, and Pr 1 be the marginal probability that a node has one packet (travelling in the ring) in it. Then by the product form, and by applying the product form to the possible previous states, Taking the N th root and simplifying, we get The nominal load at any node is r = λ/µ. Now, by Little's theorem (Theorem 31), Pr X = 1 − r. Therefore, If we take the limit of large N , we get lim N →∞ Next, observe that the expected queue length per processor is greater than the probability the queue is non-empty. In the limit of large N , the probability of a non-empty queue becomes lim Therefore, the expected queue length has an Ω(1) lower bound in N . However, Coffman et al. [14] shows that the expected queue length is o(1), which is a contradiction. ✷

Explicit Calculations
Suppose we perform a Taylor expansion in s = (N − 1)p at s = 0. Since every packet insertion into the ring is one of N − 1 equally likely possibilities, then the coefficients of the Taylor expansion in s are integral. With some care, it's possible to write computer programs to calculate these coefficients exactly, since there are no rounding issues. (I discuss the details in Appendix E.) I include two such calculations for the N = 4 node standard Bernoulli ring.

Theorem 19
The expected queue length per node of the standard Bernoulli ring is not always absolutely monotonic.
Proof. If N = 3, then the expected queue length is absolutely monotonic. However, if N = 4, then observe that the s 10 term in Equation 5.5 is negative, contradicting absolute monotonicity. ✷ As we'll see in the next section, Markovian networks have absolutely monotonic expected queue lengths, so Theorem 19 disproves a natural hypothesis on standard Bernoulli rings.
Next, we analyze the rationality of these functions. Proof. Suppose that we have a partial Taylor expansion of a rational function, something like: γ is too small relative to α and β, we have no hope of reconstructing a(x) or b(x); in other words, for a fixed γ, we can only detect rationality if we assume that α and β are sufficiently small. So, suppose that We can perform a similar operation for the coefficient for the x α+2 term, and so on, up to x α+β+1 . We get a resulting matrix equation: So, given c(x), we can construct the matrix C for any α + β < γ. If the resulting matrix doesn't have an annihilating vector (i.e. is of full rank), then c(x) can not be a rational function with numerator degree ≤ α and denominator degree ≤ β. I checked the resulting matrices for Equations 5.5 and 5.6 for all α + β = 17 exhaustively 1 via computer, and found that every matrix had full rank. (A computational note: it is sufficient to reduce the matrix modulo a large prime and show that the resulting matrix is nonsingular by modular arithmetic.) ✷ Finally, the curious reader may wonder what the first few places of the Taylor expansion of the expected queue length per node looks like as a function of N . It is possible to calculate these values, and it begins: or, in terms of the nominal load r, Observe that the coefficient to r 2 is O(1/N ), as one might suspect. The proof can be extended to the r 3 term, but even the calculations for the r 2 term are too lengthy to include here.

A Class of Absolutely Monotonic Networks
We now turn our attention from multiclass networks to simpler Markovian networks. First, we need a little combinatorial result. Proof. Suppose we have n distinct objects which we are allowed to paint red, green, or blue. We have the restriction that l of the objects must be red, and we weight each combination by (−1) k where k of the objects are green. Then observe that the weighted sum of all valid combinations of objects is exactly Equation 5.7. I will prove the theorem by induction on n. Observe that the theorem holds if n = 1 (and hence l = 0).
Assume, inductively, that the theorem holds on n − 1. Suppose that l > 0. We can sum all the weighted objects as follows. If the last object is red, then there must be l − 1 red objects among the other n − 1 objects. If the last object is green or blue, there must be l red objects among the other n − 1 objects. If it's green, though, we also must invert the weight of the combination. In equations, Let f (x) be a function on [0, P ) that we suspect may be absolutely monotonic. Fix x, h, n ≥ 0, n an integer, such that x + hn < P . Let k = 0, 1, · · · , ⌊ P −x h ⌋.

Lemma 17
The function f (x) is absolutely monotonic iff f n (x + hn) ≥ 0 for all n, x, h as above.
Proof. Observe that if 0 ≤ k ≤ n, then So, if we plug into Equation 5.1, we get Suppose that if p < P , then the maximum nominal load at a node is less than one. Then the network is stable for p < P , and the expected time that a packet spends in the system is an absolutely monotonic function of p, for 0 ≤ p < P .
Proof. The stability is immediate because the network is Markovian; see the discrete time fluid limits from Chapter 4 of this thesis, and Section 5 of Dai [20].
Let f (p) be the expected delay in the system when the arrival rate is p. Define f n (p) as in Equation 5.8.
I'll use what is sometimes called the "method of collective marks" (see, e.g. Kleinrock [34], Chapter 7). We want to compare f (x) with f (x + hl). We need very fine control over our Bernoulli arrival process. We will get this control as follows.
Let S 0 = [0, x). Let S 1 = [x, x + h), and generally, S i = [x + (i − 1)h, x + ih). (Note that the S i are disjoint.) On each time step, at each node, we select a number a from [0, 1] uniformly at random. Suppose that we inject a packet if a ∈ l i=0 S i . Then we have simulated a rate x + lh Bernoulli arrival process.
If a packet arrives because a ∈ S i , let us mark it with an i (hence the name "collective marks".) The packets are now members of class i. Suppose that we give priority to packets based on their mark, so that packets with lower marks get priority over packets with higher marks.
The key observations to make are twofold. First, since the mark 0 packets have priority over all the other packets, they behave as though they were travelling in a system with a rate x Bernoulli arrival processes. Therefore, the expected delay of the mark 0 packets is the same as the expected delay from a rate x Bernoulli process, namely f (x).
Second of all, the increase in expected delays from inserting multiple classes of marked packets is superadditive. To clarify this point, let me give a canonical example (with l = 2). Suppose that we compare the system with arrivals when where m < m. Let us call the expected delay in the systems D 1 , D 2 , D 3 and D 4 , respectively.
In both cases 2 and 3, we have Bernoulli arrival processes of with the same rate. Therefore, D 2 = D 3 . In particular, the increase in expected delay from cases 1 to 2, and from cases 1 to 3 is identical. In the fourth case, the class m packets will be delayed by the class 0 packets, and additionally delayed by the classm packets. Therefore, To see more formally why the delay is superadditive (i.e. that the increase from D 1 to D 4 is at least (D 2 − D 1 ) + (D 3 − D 1 )), let us examine the packets' paths a little more closely. Whenever a packet is ejected from a node, it selects its outgoing edge based on some distribution. Let us fix these decisions ahead of time, per class, rather than dynamically as the system runs. That is, at start up we decide that the sth packet that is marked i at node n will take edge e, for all s, n and i. (If no edge is selected for some s, then the packet must leave the system.) Let us compare the system with the class m and class m packets, versus the system with only the class m packets. I claim that the sth class m packet ejected from node n will be ejected at the same time or later in the m, m system than in the m system. The proof follows immediately by induction on time. (This technique was introduced by Harchol-Balter [31].) Clearly, if the system departures for the class m packets occur no sooner in the m, m system than in the m system, then the expected delay of class m packets in the former system is at least as great as in the latter system. In other words, the delays are superadditive. Now, let us consider f 1 (x + hl). The addition of an additional class of marked packets can only increase the total expected delay. Therefore, if the arrival rate is x+ hl, with l > 0, then and hence, Next, consider f 2 (x + hl). Suppose we let D i be the expected delay from arrivals caused by a ∈ S 0 S i , and D 0 by arrivals caused by a ∈ S 0 alone, for 1 ≤ i ≤ l. There are l 1 = l such S 0 S i arrival processes. First of all, the D i − D 0 increase in delay that each of these processes offers over the S 0 process is identical. Second of all, if we consider the arrival process a ∈ S 0 l i=1 S i , we can simply add all the differences (because the delays are superadditive.) Now, How do we show that this process continues for ∆ n h , for arbitrarily large n? Well, we know that if 0 ≤ k ≤ n − 1, then Suppose, in addition, that for any 0 ≤ k < ⌊ P −x h ⌋, We will prove Equation 5.11 by induction on n. We've already proved the base case (n = 1, 2). Assume it holds for all l < n.
As discussed in the f 2 (x + 2h) case, the delay in packets from f (x + lh) is greater than the sum of • The delay in the packets arriving because a ∈ S 0 .
• The increase in delay caused by the packets arriving in S 0 S m 1 , for 1 ≤ m 1 ≤ l. There are l 1 such S 0 S m 1 sets.
• The increase in delay caused by the packets arriving in • ....

• The increase in delay caused by the packets arriving in
where k = 0, · · · , l and l < n. This sum is precisely equal to So, since f (x + kh) is an upper bound, giving Equation 5.11 as desired. ✷ If we look at the preceding proof a bit more carefully, it is possible to show that the expected delay is strictly increasing and strictly convex. We will deduce some more interesting corollaries on expected queue lengths below.
Corollary 14 Suppose that we have a Markovian network with Bernoulli arrivals of rate p, with nominal loads less than one so long as p < P . Then the expected number of packets in the system is absolutely monotonic, as is the expected (total) number of packets in queue.
Proof. The expected delay in the system is equal to the sum of the expected delay at each node. By Little's Theorem (Theorem 31), the expected number of packets per node is the expected delay per node multiplied by p. Since every packet has a rate p Bernoulli arrival process, the expected number of packets in the whole system is p times the expected delay. Multiplying an absolutely monotonic function by p retains absolute monotonicity, so we're done with the first half of the corollary.
Let E[Q](p) be the expected total number of packets in queue as a function of p, and E[S](p) be the expected total number of packets in the system as a function of p.
Little's Theorem also tells us that if a system is stable, then expected queue length at a node differs from the expected number of packets at that node by exactly the nominal load r. Therefore, by the linearity of expectation, E[S](p) equals E[Q](p) plus the sum of the nominal loads.
The sum of the nominal loads are a linear multiple of p, say M p. Observe that M p is an analytic function. Since absolute monotonicity implies analyticity, then E[S](p) is analytic. Therefore, E[Q](p) is the difference between two analytic functions, and hence analytic.
Consider a Taylor expansion of E[Q](p) around zero. The only coefficient that differs from E[S](p) (and hence the only coefficient that could be negative) is the p 1 term. If this coefficient were negative, then for a sufficiently small p ǫ > 0, E[Q](p ǫ ) would be negative. However, the E[Q] is always non-negative (since it measures a non-negative quantity.) Therefore, the p 1 coefficient is non-negative, and hence E[Q](p) is absolutely monotonic. ✷.
Because an N node ring is symmetric, is possible to translate from expected total queue length to expected queue length per node; we simply divide by N . This fact gives us a final corollary: Corollary 15 A geometric Bernoulli ring is Markovian, and hence its expected queue length per node is absolutely monotonic.

Future Work
Suppose we have a family of Markovian networks with Bernoulli arrivals, A i , for i = 0, 1, .... Suppose q i (r) is the expected number of packets in queue in network A i when the nominal load is r (this presupposes some notion of a system-wide nominal load; for instance, the maximum nominal load on any node.) From the results of the previous section, we know that i q i (r) is absolutely monotonic for 0 ≤ r < 1.
Suppose, finally, that for any r, there exists B r such that i q i (r) < B r . Then there exists a function q(r) absolutely monotonic on 0 ≤ r < 1 and a subsequence i 0 , i 1 , ... such that lim Now, since the q i j are absolutely monotonic, it implies they are monotonically increasing and convex, and hence that q is also monotonically increasing and convex. Convexity implies continuity on open intervals (see Rudin [43], page 61), giving continuity on (0, 1). The monotonicity allows us to extend the continuity to [0, 1). By Dai's [20] Lemma 4.1, the q i j converge uniformly on compact sets, so it follows that q is analytic, and the Taylor coefficients are the limits of the coefficients of the q i j . Therefore, q is absolutely monotonic. Now, recall the known bounds for a standard Bernoulli ring: Suppose that the standard Bernoulli ring were absolutely monotonic. Then the arguments above would let us conclude that the expected queue length converges to an analytic function E[Q], which is identically zero on 0 ≤ r < 1/2, and is analytic on 1/2 ≤ r < 1. By analytic continuation, it follows that E[Q] is zero on the whole interval 0 ≤ r < 1, i.e. the expected queue length per node would be o(1)! Sadly, these arguments don't work. A standard Bernoulli ring is not Markovian, so Theorem 21 doesn't apply; in fact, as we showed in Theorem 19, there exist N for which the N node standard Bernoulli ring is provably not absolutely monotonic. However, an interesting avenue of future research would be to find some smoothness property analogous to absolute monotonicity. Using it, we might be able to make conclusions about r ≥ 1/2 based solely on analytic continuation arguments.

Introduction
A ring is the simplest possible network with feedback. If we wished to generalize results about the ring to other networks, where should we begin?
One way of characterizing a ring is to observe that it is a regular degree 1 directed graph where all nodes are identical. (By identical, I mean that there exists a graph automorphism that sends any node to any other node. This property allows us to calculate the expected queue length per node simply by dividing the total expected queue length by N .) A natural first step in generalization is to increase the degree of the graph, but maintain regularity. I will discuss two possibilities, the butterfly and the torus. First, though, I will define a more general class of networks, of which butterflies and tori are members.

Definition 21
A directed graph is layered if its nodes can be partitioned into k disjoint sets G 1 , . . . , G k such that any edge lies between G i and G i+1 for some i. A layered network is also called feedforward.
A wrapped layered network allows edges from G k to G 1 , too. Now, to define the two graphs of interest: A node is labeled (n 1 , · · · , n d ), where n i is an integer between 0 and N i − 1. There is an edge from (n 1 , · · · , n d ) to (m 1 , · · · , m d ) iff there is an i such that (n i + 1) mod N i = m i , and for all j = i, n j = m j .
If N i = 2 for all i, the torus is called a d-dimensional hypercube.
If k divides N i for all i, then the torus can be written as a wrapped layered network with i layers. Another popular network for packet routing is the butterfly graph.
Definition 23 A (standard) d-dimensional butterfly is a directed, layered graph defined as follows: nodes fall into one of d + 1 disjoint layers, numbered 0 through d. Each layer consists of N = 2 d nodes, which we label with the N binary strings of length d. (So, a node is specified by a binary string and a layer number.) Consider any length d binary string, For each i such that 0 ≤ i < d, there is a directed edge from node b of layer i to node b 1 b 2 · · · b i−1 0b i+1 · · · b d of layer i + 1, and another directed edge from node b of layer i to node b 1 b 2 · · · b i−1 1b i+1 · · · b d of layer i + 1. The nodes on layer 0 are called the input nodes, and the nodes on layer d are the output nodes. A wrapped butterfly is a directed graph where the nodes on the last layer are associated with the nodes on the first layer.
See Figure 6-1 for a drawing of a three-dimensional butterfly graph. Note that tori and includegraphics[height=2in]figures/butterfly3.eps It will be useful to keep these examples in mind during the next section.

Convex Routing
Definition 24 Consider a node n 0 in a network. Let n 1 , ..., n m be the m nodes with directed edges into n 0 . Let p i be the probability that a packet travels from node n i to n 0 , and suppose that the probability is independent of the class of the packet. Suppose that If this equation holds for all nodes n 0 , then we say that the network 1 has the property of convex routing.
For example, if we are on a regular graph, and a packet chooses its next edge uniformly at random, the network has convex routing.

Theorem 22
Suppose we have a generalized Kelly network with convex routing. Suppose further that we use any greedy protocol, and the network has any topology. If the nominal loads are less than one, then the network is stable.
If all the interarrival and service times have finite variance, then the expected queue length is finite, too.
Proof. I'll prove this by using the (delayed) fluid limit technique.
Let n be a node. I'm going to define a potential function φ(n) on the fluid model to be the analogue of the expected congestion at node n (i.e. the expected number of times that packets now in the system will use node n).
To make this precise in the fluid regime, consider a fluid class c and a node n. Suppose that we have a unit of class c fluid, and suppose that class c resides at node n c . Suppose we have a path γ through the network (not necessarily node disjoint), beginning at class c's node and ending at node n. Then some fraction f γ will pass through node n along path γ.
(Note that f γ is independent of the class by the convexity of the routing.) Since we have an open queueing network, all packets almost surely leave the system. In the fluid domain, this means that, summing over all paths γ from n c to n, γ f γ < ∞ Suppose that there is q c quantity of fluid of class c. Then, since there are a finite number of classes c, we can let Notice that φ(n) is the total amount of fluid that would pass through node n if no new fluid arrived in the system. Let Φ = max n φ(n).
Let q(n) be the number of packets in queue at node n (from all classes resident at n). Let a n be the nominal arrival rate at node n. Let s n be the nominal service rate at node n. (Note that a n < s n , since the nominal loads are less than one.) Let ǫ = min n (s n − a n ) > 0 Observe that φ(n) is a Lipschitz function. To see this, note that fluid increases at most at a rate a n , and decreases at most at a rate s n . It follows that Φ is Lipschitz. Now, Lipschitz functions are absolutely continuous, and hence continuous and differentiable almost everywhere. (See, e.g., Rudin [43]). If we can show that Φ > 0 implies that d dt Φ ≤ −ǫ a.e., then it implies fluid stability (because all fluid will empty from the system by time 1/ǫ), and we will be done.
Observe that if q(n) > 0, then d dt φ(n) ≤ −ǫ almost surely. Therefore, if the maximum value of φ(n) is attained at a node with q(n) > 0, then it follows almost surely that d dt Φ ≤ −ǫ. It suffices, therefore, to show that so long as there exists an n with q(n) > 0, then max n φ(n) = max n,q(n)>0 φ(n) (6.2) and we will have proved fluid stability. Assume that Φ > 0. If q(n) > 0 for all n, then Equation 6.2 holds. Assume, then, that there exists a node n 0 such that q(n 0 ) = 0, but φ(n 0 ) > 0.
I am going to construct a tree of all the possible paths γ from node n 1 with q n 1 > 0 to node n, where every intermediate node n 2 on the path has q n 2 = 0. Since q(n 0 ) = 0 but φ(n) > 0, then there must exist some such path, so the tree has more than one node.
It's certainly possible that by the third level of the tree, a node from the network may show up in more than one place in the tree, because there may be multiple paths from the node to n. We treat these as formally distinct nodes. (For instance, if we have a diamond shape, as in Figure 6-2, node n 3 from the network will split into two different nodes in the tree.) The terminal nodes in the tree correspond to nodes in the network with non-zero queues. I will label the terminal nodes to represent the amount of traffic that will follow a given path. More precisely, consider a node n γ in the tree, corresponding to node n 1 in the network, and the path γ from n 1 to n 0 . Let Γ c be the class of paths that start at the node If n γ is a terminal node in the tree, I will label it with ψ(n γ ).
Now, let T be the set of terminal nodes in the tree. Observe that Consider taking a random walk along the tree away from the root node. Given the edges e 1 , . . . , e m leading to node n γ , let the probability of crossing edge e i in our random walk be the probability of crossing the edge e i into node n γ . Because the routing is convex, the sum of the probabilities p γ is p γ ≤ 1 If p γ < 1, then with probability 1 − p γ , we stop the walk in node n γ . Observe that for any terminal node n γ , the probability of stopping at node n γ is f γ . Since we have a distribution, (This inequality can also be proved from the Kraft inequality of data compression theory.) Equations 6.4 and 6.3 combine to tell us that φ(n) is bounded by a convex combination of the terminal nodes.
Note that if we have a convex combination of non-negative reals r i that are all less than some bound B, then there exists an i such that the convex combination is less than or equal to r i . Using the total work in the system as a bound on ψ(), we can conclude that φ(n 0 ) ≤ ψ(n γ ) (6.5) for some particular node n γ .
Finally, observe that if node n 1 in the network corresponds to terminal node n γ in the tree, then (at least) ψ(n γ ) packets currently in the system need to cross n 1 . Therefore, ψ(n γ ) ≤ φ(n 1 ) (6.6) Combining Equations 6.5 and 6.6, we get φ(n) ≤ φ(n 1 ) Note that node n 1 has q(n 1 ) > 0 (because n γ is a terminal node of the tree), so we have established fluid stability. Fluid stability, plus the finite variance of arrivals and service times, implies finiteness of expected queue length. (For details, see Dai and Meyn [23]). ✷

Corollary 16
Any ring network uses convex routing, and thus is universally stable.
Note: The fluid stability of the ring was first proved by Dai and Weiss [22]. These results on convex routing have some fairly natural applications to load balancing. Suppose we have a d-dimensional wrapped butterfly where each nodes is a processor, performing some computations. Occasionally, a node will decide that it has too much work, and will insert a packet into the system, representing one quantum of work. The processor would like to share its work fairly uniformly across the other processors. (For the moment, I won't worry about aggregating the completed work of the system.) Sharing the load can be accomplished fairly easily on a wrapped butterfly. At every node, there are two outgoing edges; if a packet selects each edge with probability 1 2 , then in d (or more) steps, its probability of being at any point in its current layer is uniform. Thus, we have a multi-class convex routing problem, and we can use Theorem 22 to deduce stability.
There is an even more efficient method of sending the load through the network. Since there are two outgoing edges at every node, we can send out up to two packets per time step. Suppose that we select the particular edge at random. Then we maintain convex routing (and hence stability), while still guaranteeing uniform distribution over the final layer in d time steps.
Generally speaking, if we have a d-regular graph, then by selecting each of the outgoing edges with equal probability, we have convex routing. We can also send out d packets instead of 1 packet. Most interestingly, since at most d packets arrive, we can give them precedence over the packets in queue, i.e. use the Greedy Hot Potato algorithm. This choice opens up the possibility of using the techniques from Chapter 3 to get bounds on the expected queue length per node.

Superconcentration on a Pair of Butterflies
The remainder of this chapter will examine some problems in node-disjoint circuit switching. Unlike the stochastic results of the rest of this thesis, these results are more graph-theoretical and structural in flavor. The motivating problem can be described as follows. Suppose we have a directed graph with N input and N output nodes, both labelled from 1 to N . For each input node v, we choose an output node π(v) to be its destination, for some permutation π. The problem is to find a collection of N node-disjoint paths which each run from v to π(v) for all v. A directed graph that can route all permutations π is called rearrangeable. (For some real-world applications of node-disjoint routing, see, for example, [47].) A classic example of rearrangeability is the Beneš network (see [36]). This network (i.e. directed graph) consists of a "forward" butterfly adjoined to a "reversed" butterfly. A natural question to ask is: if we attach two "forward" butterflies, is this network (the double butterfly) still rearrangeable? This problem has been open for several decades. At least one proof is currently under review [11]. This suggests a more general hypothesis. Suppose that we have two graphs, each isomorphic to a butterfly, but not necessarily identical to each other. If we attach the output nodes of the first to the input nodes of the second, is the resulting graph rearrangeable?
At the current time, proving this kind of result seems far too much to hope for. So, rather than show that these types of networks are rearrangeable, I will prove various concentration and superconcentration results.
Definition 25 Consider a directed graph G. Fix n input nodes and n output nodes. Suppose that between any k input and k output nodes there exist k node-disjoint paths. (By "node-disjoint", I mean that a path intersects neither itself nor any other path.) Then we say that G is a k-concentrator. If G is a k-concentrator for all k ≤ n, then we call G a superconcentrator.
(Observe that every selected input and output node occurs on exactly one path. Note also that node-disjointness implies edge-disjointness of the paths. See [41] or [32] for more on superconcentrators.) Clearly, rearrangeability implies subset routing-just choose a permutation that respects v ∈ A iff π(v) ∈ B. However, the converse is not true for arbitrary networks (see Figure 6-3). It's straightforward to show that a single butterfly does not route all subsets, so we need to use at least two butterflies to get interesting concentration results.
In the next several sections, I show that any concatenated pair of d-dimensional butterflies (not necessarily identical to each other) are 2 k -concentrators, for any k ≤ d. I can strengthen this statement in a special case: if the butterflies are standard butterflies with their layers shuffled (e.g. a Beneš network, or the double buttefly in [11]), the network is a superconcentrator.
The rest of this chapter is structured as follows. Section 1 establishes some definitions and fixes notation. Section 2 examines the structure of a graph related to a pair of butterflies that highlights some of its connectivity properties. Section 3 solves the problem in the case where |A| = 2 m for some m, and proves a rearrangeability-type result when |A| ≤ ⌊d/2⌋ on certain networks. Section 4 presents the main result, except for one lemma that I postpone for section 5. Section 6 is dedicated to closing remarks.

Definitions and Notation
Let us begin by defining and fixing notation for a butterfly. A standard d-dimensional butterfly can be viewed as a network with 2 d nodes where we switch the first bit in the first layer of edges, the second bit in the second layer of edges, and so forth. If we choose to switch the bits in a different order, we get a layer-permuted butterfly.
Definition 26 A d-dimensional layer-permuted butterfly is a directed, layered graph defined as follows: nodes fall into one of d+1 disjoint layers, numbered 0 through d. Each layer consists of N = 2 d nodes, which we label with the N binary strings of length d. Take some (fixed) permutation π on d objects. Consider any such binary string, For each i such that 0 ≤ i < d, there is a directed edge from node b of layer i to node b 1 b 2 · · · b π(i)−1 0b π(i)+1 · · · b d of layer i + 1, and another directed edge from node b of layer i to node b 1 b 2 · · · b π(i)−1 1b π(i)+1 · · · b d of layer i + 1.
(Note that these butterflies are all graph-isomorphic to each other.) Finally, the networks we'll be looking at consist of pairs of these butterflies.
Definition 27 Suppose that we have two graphs, G 1 and G 2 . Suppose that G 1 has n output nodes and G 2 has n input nodes, each numbered from 1 to n. Then we say that G is the concatenation of G 1 and G 2 if we form G by associating the output node i of G 1 with the input node i of G 2 .
If G 1 and G 2 are each isomorphic to a standard butterfly (but not necessarily identical to each other), we call G a pair of butterflies. Similarly, if G 1 and G 2 are layer-permuted butterflies, we have a pair of layer-permuted butterflies. Finally, if G 1 and G 2 are both standard butterflies, we have a double butterfly.
Note that these graphs have 2d + 1 layers of nodes (0 through 2d). Since I imagine the paths from inputs to outputs to be running from left to right, I will refer to the butterfly on layers 0 through d as the left butterfly, and the one on layers d through 2d as the right butterfly. Note also an alternate way of specifying a pair of butterflies: consider a network consisting of two standard butterflies, but permute the labels of the output nodes of the left butterfly. Observe that these two definitions give rise to the same class of graphs (up to isomorphism).
Over the course of this chapter, I construct directed node-disjoint paths from input nodes to output nodes. So, for example, a path from an input node to an output node on a pair of butterflies is exactly 2d + 1 nodes long-the path can't double back on the layers.
Suppose I have a set of input nodes A and a set of output nodes B of the same size (i.e. |A| = |B|) Then if I specify a collection of node-disjoint paths from A to B, observe that I can extend these paths into a consistent setting of all the switches in the network. These switches will induce N node disjoint paths from every input to every output node, and retain the feature that a path begins in A iff it ends in B. So, on a switching network, node-disjoint routing of a subset implies there exists a node-disjoint routing of a permutation π such that v ∈ A iff π(v) ∈ B. Since this is an "if and only if" statement, we get the following lemma: Lemma 18 If we can find node-disjoint paths from A to B on a switching network, then we can find node-disjoint paths from the complements A c to B c .
Throughout this chapter, I will use A to represent a collection of input nodes, B a collection of output nodes, and assume that |A| = |B|.

The Sub-Butterfly Connectivity Graph
Suppose we specify a path of length m on a standard butterfly (for m ≤ d) from an input node. By choosing which edge to take, the path changes m bits of its location any way we want. Suppose we select the first bits to be b = b 1 b 2 b 3 · · · b m . Then from layers m + 1 to d, the first m bits will remain equal to b. Let's specify the resulting sub-graph of the butterfly in the following definition: Definition 28 Consider a d dimensional standard butterfly. Take an m bit binary string Consider the sub-graph formed by the nodes on layers m through d (inclusive) whose first m bits are b. Observe that this graph is (isomorphic to) a (d − m)dimensional butterfly. Let us call it the sub-butterfly b * .
If we specify a suffix instead and consider layers 0 through d−m, we get the sub-butterfly * b.
If we have a graph isomorphic to a standard butterfly, the isomorphism will induce (isomorphic) images of the sub-butterfly, so we can meaningfully refer to sub-butterflies on any butterfly-isomorphic graph.
I will be considering sub-butterflies in a pair of butterflies. In this context, b * is the subbutterfly residing on layers m through d (and stopping there), i.e. only in the left butterfly. I'll also be interested in sub-butterflies on the right side. These inhabit layers d through 2d − m.
It will be useful to investigate the structure of the connections between the q-dimensional sub-butterflies on the right and left sides of a d-dimensional pair of butterflies, that is, the sub-butterflies of the form x * or * x where x is a binary string of length m (such that m + q = d). Note that these sub-butterflies inhabit layers m = d − q through d, and d through d + q. Let us represent each sub-butterfly by a vertex in a bipartite graph; the vertex is on the left side of the bipartite graph iff the sub-butterfly is on the left side of the pair of butterflies. I will label each vertex by its associated sub-butterfly, abusing the label notation somewhat. Place an edge between two vertices x * and * y iff the two sub-butterflies are connected, that is, iff x * and * y (as sub-butterflies) share at least one common node on layer d of the pair of butterflies. Equivalently, there is an edge between the nodes in the bipartite graph iff there exists a path from every layer d − q input node of x * to every layer d + q output node of * y. I will refer to this graph as the q-dimensional sub-butterfly connectivity graph, or just the connectivity graph. Observe that there are 2 m vertices on either side of this graph. How are the vertices connected?
I will consider progressively more specialized cases in order to derive various results in later sections. Suppose, first, that we build a bipartite connectivity graph, but if there are x common nodes on layer d between a sub-butterfly on the left and one on the right, we insert x edges (instead of only 1 edge). Let us call this the enriched connectivity graph.

Lemma 19
For any pair of butterflies, its enriched connectivity graph is regular.

Proof.
Since each sub-butterfly has 2 q output nodes, then all nodes in the enriched connectivity graph have degree 2 q . Now we move our attention to the special case of layer-permuted butterflies. First, let us analyze the structure of one connected compnent of the q-dimensional connectivity graph.
Lemma 20 Each connected component in the connectivity graph of a layer-permuted butterfly is a completely connected bipartite graph.
Proof. Suppose that the layer-permuted butterfly on the left has permutation π, and the butterfly on the right has permutation σ. Consider a sub-butterfly b * in the left butterfly. This corresponds to a sub-graph on layers m through d where the value of bit π(i) is b i . Notice that a sub-butterfly b * in the left butterfly connects to a sub-butterfly * c in the right butterfly if and only if Thus, each connected component is a complete bipartite graph (with the same number of nodes on each side.) Next, suppose that we have a pair of layer-permuted butterflies. How does the graph change as we specify one more layer? That is, if we compare the connectivity graphs between q and q − 1 dimensional sub-butterflies, what happens? Therefore, determining the structure of the connectivity graph on pairs of layer-permuted butterflies reduces to determining the connected components. Consider one connected component in the connectivity graph looking at q-dimensional sub-butterflies. When we advance to the (q − 1) dimensional sub-butterflies, each node becomes two nodes (because each q dimensional sub-butterfly splits into two q − 1 dimensional sub-butterflies). There are essentially three cases that can occur.
In the connectivity graph, that means that the connected component doubles the number of nodes, but remains completely connected.
• (Two reused dimensions) Suppose that σ(d − m − 1) = i = π(j) for 1 ≤ j ≤ m + 1 and π(m + 1) = l = σ(k) for d − m − 1 ≤ k ≤ d, and i = l. Then the connected component splits into four connected components, based on the four possible values that the i and l bits can take.

Subsets of Size 2 m
We want to select a collection of node-disjoint paths from input set A to output set B on a pair of butterflies. Although I've expressed this problem in terms of paths, it's often easier to express the proof in terms of packets travelling through the network. In particular, if packets travel forward (node disjointly, and without stopping) from every input node in A, and backwards from every output node in B, and we can match up the packets on level d, then the paths traced by the packets give us the collection of paths we're looking for. I will switch between the path and packet descriptions of the problem whenever it seems helpful.
Lemma 21 Suppose we have a set A of input nodes on a butterfly. By passing from layer 0 to layer 1 of a butterfly, there exist paths that send ⌈|A|/2⌉ of the packets to sub-butterfly 0 * , and ⌊|A|/2⌋ of the packets to sub-butterfly 1 * . Similarly, we could send ⌈|A|/2⌉ of the packets to sub-butterfly 1 * , and ⌊|A|/2⌋ of the packets to sub-butterfly 0 * . Mutatis mutandi, this applies to packets in output nodes travelling backwards, by passing from layer 2d to 2d − 1.
Proof. The N nodes on the first layer of the butterfly can be grouped into N/2 switches, where the nodes labelled T 0 = 0t 2 t 3 · · · t d and T 1 = 1t 2 t 3 · · · t d form one switch. Observe that each switch can be set straight or crossed, that is, we have to send T i to T i on the next layer (for i = both 0 and 1), or T i to T 1−i . Setting switches in one of these two states guarantees that paths are node-disjoint, so I will always set them accordingly. For all the switches such that T 0 , T 1 ∈ A, half of these packets get sent to 0 * , and half to 1 * . If T 0 , T 1 ∈ A, half of these (zero) packets get sent to each sub-butterfly, too. Consider all of the remaining packets. Each of these is the sole packet in the switch. So, by setting ⌈|A|/2⌉ of the switches to send the packets to sub-butterfly 0 * , and ⌊|A|/2⌋ of them to 1 * , we prove the first part of the lemma. The rest follows by symmetry.
This lemma allows a surprisingly simple proof of 2 m concentration. Proof. Consider the left butterfly. We can apply Lemma 21 recursively for m steps. On step 1, we split A so that 2 m−1 packets go to 0 * and 2 m−1 go to 1 * . Since 0 * and 1 * are themselves d − 1 dimensional butterflies, we can apply the lemma again, on each of them, giving us 4 sub-butterflies, each with 2 m−2 paths. After m steps, we end up with 2 m sub-butterflies (which is all of the d − m dimensional sub-butterflies), each of which has exactly 1 packet. Now, on each of these butterflies, we can send the packet along any path we want for the remainder of the left butterfly (i.e. until we hit layer d); since it's the only packet on its sub-butterfly, there's no possibility of any other packet's path crossing its own. We can perform the same construction on the output packets in B, moving backwards toward the input layer. When we reach layer 2d−m, there will be 1 packet per sub-butterfly.
At this point, observe that the sub-butterfly connectivity graph determines the connections between these butterflies. By Lemma 19, this graph is a regular bipartite graph. By Hall's theorem, there exists a perfect matching. This matching in the connectivity graph implies a matching in the set of sub-butterflies, which implies a matching between the (unique) packets in each sub-butterfly. By construction of the connectivity graph, there exists a path (not necessarily unique) between matched packets. As observed above, these paths are node-disjoint, so we're done.

Some Corollaries
We get a very short corollary: Then there exist node-disjoint paths from A to B on a pair of butterflies.
Proof. Use Lemma 18 and Theorem 23 on the complements of A and B.
We can use Theorem 23 to give us information about a kind of rearrangeability on sufficiently small input and output sets.
Corollary 18 Suppose we have a pair of d-dimensional butterflies. Suppose that there is a path between each node on layer ⌊d/2⌋ (in the left butterfly) and each node on layer 2d − ⌊d/2⌋ (in the right butterfly). Then if we select any input set A and output set B with A = B ≤ 2 ⌊d/2⌋ , and any permutation ρ from A to B, there exists a collection of node-disjoint paths from A to B such that for every a ∈ A, the path from a ends at ρ(a).

Proof.
If the corollary holds when A = B = 2 ⌊d/2⌋ , then, by using dummy packets to make up the difference, the corollary holds for A = B ≤ 2 ⌊d/2⌋ . So, suppose that A = B = 2 ⌊d/2⌋ . We can use the same argument in Theorem 23 to split the packets until there is one packet on each ⌈d/2⌉ dimensional sub-butterfly. By the assumption in the corollary, the resulting connectivity graph is a complete bipartite graph on all nodes, so we can select node-disjoint paths between the path originating at any a and send it to the path terminating at ρ(a).
Note that if we have a pair of standard butterflies, the corollary holds. Also, suppose we have a pair of layer-permuted butterflies. Suppose further that we insist that • if i ≤ ⌊d/2⌋, then π(i) ≤ ⌊d/2⌋ (where π is the left layer permutation) on the left butterfly, and • if i ≥ ⌈d/2⌉, then σ(i) ≥ ⌈d/2⌉ (where σ is the right layer permutation) on the right butterfly.
(In other words, we permute the layers but don't send any layer from the left half of the butterfly to the right half.) Then Corollary 18 holds.

The General Case
Proving node-disjoint subset routing for an arbitrary input and output set (of the same size) is somewhat more challenging. However, for pairs of layer-permuted butterflies, the same basic approach from Theorem 23 works. Looking at the proof, there are two parts: first, we split the packets into a number of sub-butterflies, until we have one packet per sub-butterfly. Then, we view the problem as an exact matching problem on a particular bipartite graph, and show that a matching exists. The proof for the general case runs the same way. In order to find a matching, it's clearly necessary that each connected component of the bipartite connectivity graph has as many packets on the left side as on the right. In the next section, I'll prove that this condition (roughly speaking) is sufficient for the existence of a matching on the connectivity graph. But assuming for now that it holds, we can prove the main result: Theorem 24 For any input set A and output set B on a pair of d-dimensional layerpermuted butterflies, such that |A| = |B|, there exist node-disjoint paths from A to B.
Proof. If |A| = 2 d , then we are done, by (for example) Theorem 23. So throughout, we can assume that |A| < 2 d . Suppose that, in binary, |A| = b m b m−1 · · · b 1 , where m ≤ d. I will prove the lemma by induction on m. The exact statement that I will be inducting on is: Over the course of m + 1 steps, we can recursively split the packets over the subbutterflies, so that if sub-butterfly x * has p packets in it, then x0 * will have ⌈p/2⌉ or ⌊p/2⌋ packets, and x1 * will have ⌊p/2⌋ or ⌈p/2⌉ packets, respectively. The same holds on the right butterfly. (There will then be 0 or 1 packets in each sub-butterfly on level m + 1 and level 2d − m − 1). We can then select a matching between the sub-butterflies giving us node-disjoint paths from A to B.
First, the base case: if m=0 or 1, then we are done (by Theorem 23). Next, the inductive step. Fix m and assume the theorem holds for all m ′ < m. Let us try to reproduce the proof of Theorem 23 with 2 m+1 > |A| ≥ 2 m packets to see where complications arise. If |A| = 2 m , then we will not be able to divide the packets evenly in half at every sub-butterfly for m steps. A sub-butterfly x * may have an odd number of packets, so we must send the "extra" packet either to x0 * or x1 * . I will refer to this choice (the "0" or "1") as the rounding decision. Note that there is no actual packet that is distinguished as the "extra" one-there's just a surplus of one more packet that either goes to x0 * or x1 * . But it's helpful to imagine that one of the packets is the extra one when describing the paths. Choose . By induction, we can find node-disjoint paths from A ′ to B ′ . The information that we keep from the induction is not the actual paths themselves. Instead, we keep the rounding decisions that every sub-butterfly makes. Note that even after we've split A ′ until there's only 1 packet per sub-butterfly, we are still splitting with an extra packet; it's just that if p = 1, then ⌈p/2⌉ = 1, and ⌊p/2⌋ = 0. Hence, the almost exact recursive splitting part of the inductive hypothesis holds not just for the first m ′ steps, but for the first m steps. We need to keep this rounding information, too.
Consider, now, the original sets A and B. Using Lemma 21 recursively for m − 1 steps on the right and left butterflies, we can send the "extra" packet on each sub-butterfly the same way on level k < m as we did when routing A ′ to B ′ . To do this, we need to know that the same sub-butterflies have an odd number of packets in them. Observe that if a sub-butterfly on level k that has t packets in it in the (A ′ , B ′ ) case, then it has t + 2 m−k in the (A, B) case. As long as k < m, then t and t + 2 m−k have the same parity; therefore, extra packets exist in the same sub-butterflies. When we reach step m, all the m-level sub-butterflies that had one packet in them in the (A ′ , B ′ ) case now have 2 packets, and all the sub-butterflies that had no packets now have 1.
We shift now to the matching problem on the sub-butterfly connectivity graph. Consider one connected component of the connectivity graph. Every node on the left hand side represents a sub-butterfly with one or two packets on it, as does every node on the right hand side. By induction, the total number of packets on each side is the same. (If they weren't, the packets in the (A ′ , B ′ ) case couldn't match up.) Using Lemma 22 of the next section, we can split the packets over level m (and 2d − m) to get 0 or 1 packet per subbutterfly, with the same number on the LHS and RHS of each of the connected components. By Lemma 20 each component is completely connected, and we're done.
Note that since we're using the direction of the "extra" packet, rather than any particular path, the actual packets going into the upper or lower sub-butterflies are not necessarily the same between the (A ′ , B ′ ) case and the (A, B) case. In particular, A ′ will not necessarily still be routed to B ′ .

The Matching Lemma
Lemma 22 Suppose we have a pair of d-dimensional layer-permuted butterflies. Consider its q-dimensional sub-butterfly connectivity graph, where the sub-butterflies reside on layer m = d − q, and 2d − m. Suppose that each node has 1 or 2 packets on it. Finally, assume that there are the same number of packets on the LHS and the RHS of each connected component.
Then, when passing from the q-dimensional connectivity graph to the (q −1)-dimensional connectivity graph, we can send each packet to a different sub-butterfly such that each connected component has the same number of packets on the LHS and the RHS.
Proof. Since the behavior of the two-packet sub-butterflies is determined (one packet goes to x0 * , one to x1 * ), this proof will eventually come down to making the correct rounding decision for the sub-butterflies with single packets.
There are three cases we have to consider, reflecting the three possible behaviors of the connectivity graph as outlined on page 109. Case 1: (No reused dimensions) If the connected components don't split between the q and q − 1 dimensional sub-butterflies, then the lemma is trivially true.
Case 2: (One reused dimension) Suppose that each connected component splits into two connected components. Consider one connected component C in the q-dimensional connectivity graph that splits into C 0 and C 1 in the q − 1-dimensional connectivity graph.
Suppose that there are x nodes in C with two packets on them, and y nodes with one packet on them. We must send x packets to C 0 and x to C 1 on both the left and the right sides because the behavior of two-packet sub-butterflies is determined. We can send the y packets from one-packet nodes to either component; we simply send ⌊y/2⌋ to C 0 and ⌈y/2⌉ to C 1 on both the left and the right sides. Then the lemma holds.
Case 3: (Two reused dimensions) Suppose that each connected component in the q-dimensional connectivity graph splits into four connected components, e.g. C splits into Let us calculate how many of the packets from the 2-packet butterflies arrive in each of these splintered components.
If we have a sub-butterfly x * on level m with 2 packets in it, then we must send exactly 1 packet to x0 * and one to x1 * . I will refer to these packets as constrained packets. (By contrast, if a sub-butterfly x * on level m has only 1 packet in it, we can send the packet either to x0 * or x1 * ; such a packet is a free packet.) We shift our view back to the corresponding connectivity graph. Let us label the number of constrained packets on each side of each i C j . Observe first of all that because constrained packets come in pairs, for a fixed i = 0 or 1, there are as many constrained packets on the LHS of i C 0 as of i C 1 , and similarly as many on the RHS of 0 C i as of 1  Observe that, since each sub-butterfly in layer m has either one free or two constrained packets, then the number of packets on the LHS is Since the analogous equation holds on the RHS, and since the total number of packets are equal, we get that so there's the same total number of constrained packets on the RHS and the LHS. Therefore, adding up the constrained packets in Figure 6-4 and dividing by two, we get Also, any particular a i or b i can't be larger than 2 m−1 , so Due to symmetry, we can assume w.l.o.g. that a 1 ≥ a 2 , b 1 ≥ b 2 , and a 1 ≥ b 1 . Putting this together, we can assume that Generally speaking, a i = b j , so there will not be the same number of constrained packets on the RHS and LHS of each connected component of Figure 6-4. However, we still have the free packets to allocate. The situation is as drawn in Figure 6-5. Since we assume that a 1 ≥ b 1 ≥ b 2 ≥ a 2 , then in order to balance the packets on the LHS and RHS, we have to add packets as in Figure 6-6. We have to show that there are enough free packets to add. There are three inequalities to check. First, for 1 C 0 and 1 C 1 on the LHS, let us calculate how many free packets are required.
Now, a 1 ≤ 2 m−1 , so we need no more than 2 m−1 − a 2 free packets, which we have. For the other two cases, (namely i = 0 and i = 1), note that

Conclusion
Are all pairs of butterflies superconcentrators? Or only the layer-permuted ones? It's certainly natural to conjecture that the stronger statement is true. As a piece of support, Theorem 23 can be extended to prove that any pair of butterflies is a (2 m + 1) concentrator. Unfortunately, the pathological cases (from unusual butterfly isomorphisms) make the general analysis more complicated than I could solve. The concentration and superconcentration results in this chapter all spring from a splitting and matching approach. This method holds out a tantalizing suggestion of a proof of the rearrangeability of pairs of butterflies. Theorem 24 can be viewed as follows: if we number each input and output node 0 or 1, and have the same number of zeroes among the inputs and outputs, we can route a permutation that sends 0 → 0 and 1 → 1. Suppose we labelled the input and output nodes 0,1,2, or 3, with the same size restraints. The proofs above seem likely to apply to this case, too. If we could just continue doubling the number of labels up to N = 2 d , we'd have proved rearrangeability. Getting the proofs to work for an arbitrary 2 m seems pretty challenging, though.
Another natural network to try these methods on is the hypercube. Typically, rearrangeability on the hypercube requires that each edge is used at most once, ever, and concerns edge-disjointness, rather than node-disjointness. A result analogous to Theorem 24 would be more likely to apply to a hypercube that uses each edge at most once per time step, but possibly multiple times over several time steps. However, edge-disjointness might be strengthened to node-disjointness. Unfortunately, the translation to a hypercube is not trivial.
Proving that a graph is a superconcentrator can also be viewed as a max flow/ min cut problem; thus, Theorem 24 can be viewed as saying that for any collection of k input and k output nodes, it is necessary to delete at least k edges to prevent any (single-pass) paths from the input to the output sets. One might optimistically hope that these results might translate to other max flow problems, at least on switching networks.
On a possibly more practical note, it's interesting to observe that the Theorem 24 makes use of the size of the input set, rather than the set itself (i.e. |A|, not A). It follows that once you calculate the rounding decisions for a particular sized input set, the same rounding decisions solve the problem for all input sets of the same size. This also suggests another method for proving concentration results.

A.1 Markov Chains
The most common stochastic object in this thesis is the Markov chain.
Definition 29 A countable discrete time Markov chain is a stochastic process X(t) defined on a countable state space X at discrete moments in time t ∈ ZZ. It has the property that the distribution of states at time t > t 0 is independent of the distribution of states at time t < t 0 , conditional on the state at time t 0 .
A Markov chain is time independent, if the probability of transfering from state x to y in one time step is independent of the time t.
Suppose that for any pair of states x and y, there is a nonzero probability of travelling from state x to y in a finite number of steps, and from y to x in a finite number of steps. We call such a Markov chainirreducible.
A Markov chain is periodic with period p if the number of time steps it takes to get from any node x back to itself is always a multiple of p, for p > 1. A Markov chain is called aperiodic if it is not periodic.
The Markov chains I will be studying will always be irreducible and aperiodic. The first property of interest in studying Markov chains is their stationary distributions.
Definition 30 Suppose we have an irreducible, aperiodic discrete time Markov chain with a countable state space. Take any state x. Start the Markov chain in state x, and let f x (t) be the amount of time that the Markov chain has spent in state x during time < t. Define Suppose that π forms a distribution on X , i.e. x∈X π(x) = 1 Then we call π a stationary distribution of the Markov chain. If the Markov chain has a stationary distribution, then it is called ergodic. It is also called stable or positive recurrent.
It turns out (see Lawler [35]) that either π(x) = 0 for all x, or π is a distribution on X .
Here are some basic facts about ergodicity and Markov chains: The stationary distribution for an irreducible, aperiodic Markov chain, if it exists, is unique.
Let S σ (t) be the amount of time spent in state σ between time 0 and t. If we have a ergodic, irreducible, aperiodic Markov chain, with stationary distribution π, then almost surely. (i.e. π(σ) equals the average fraction of time spent in state σ a.s.) Suppose we have an irreducible, aperiodic Markov chain, and a state x ∈ X . Then the Markov chain is ergodic iff the expected number of steps between visits to x is finite.
Proof. See Lawler [35]. ✷ Let p(x, y) be the probability of travelling from state x to state y in one time step. Suppose we have a distribution π on X such that for any x, Then there exists a stationary distribution, and the distribution is π. Equation A.1 is actually a family of equations, one for each x ∈ X ; these are sometimes called the Kolmogorov equations. (See Lawler [35]).
Definition 31 Suppose we have a stationary distribution defined on an N node queueing network. The state of the network can be specified by the state of each of its nodes. We can write this as σ = (σ 1 , · · · , σ N ).

Suppose that
Pr(σ i ) for every state σ, i.e. the marginal probabilities multiply together as though they were independent. Then we say that the stationary distribution is of product form.

A.2 Tail Bounds
First, let's construct an exponential upper bound on the tail of sums of Bernoulli random variables. (Bounds of this type sometimes go under the name of "Hoeffding inequalities".)
Proof. See Leighton [36], page 168. Incidentally, β > 1 implies that 1 − 1 β − ln β < 0, as can be seen by taking the derivative, so the bound in the theorem is non-trivial. ✷ Next, a lower bound on sums of Bernoulli random variables.
Note: Equation A.2 implies that if γ > 0, then Proof. It's tempting to try to prove this result by using Lemma 23. Since 1 − X i is also a Bernoulli random variable, then the upper bound of Lemma 23 translates into a lower bound. Unfortunately, if we consider the behavior for large n, our value of β will be order 1 + 1 n , and it becomes difficult to analyze exactly what's going to happen. Instead, I'll prove this using a fresh moment generating function. (This technique is almost identical to the proof of Lemma 23 from Leighton [36].) First, observe that for any λ > 0, since e −λ < 1 and 1 − x ≤ e x for all x. Since the X k 's are independent, it follows that By Markov's inequality, Note that by taking derivatives, it is straightforward to show that if 0 < β < 1, then 1 − 1 β + ln β < 0 so the bound in the theorem is non-trivial. ✷

A.3 The Comparison Theorem and Drift
The Comparison theorem is a powerful theorem that allows us to say, roughly: if a real, non-negative function of the state space has expected negative drift, then the expected return times of the system are finite. The theorem follows from Dynkin's formula. This whole exposition is stolen, pretty much whole hog, from Meyn and Tweedie's book [38]. This theorem works equally well for continuous and discrete time.
We consider a stochastic process X(t) giving the state of a Markov chain at time t = 0, 1, 2, . . .. Let Z be a function from X to the non-negative reals. (This can be made more general, but it's not useful to do so.) For example, Z(X(t)) might be the total queue length of X(t).
For any stopping time τ , define τ n = min{n, τ, inf{k ≥ 0 : Z(X(k)) ≥ n}} Theorem 26 (Dynkin's Formula) For each x ∈ X and non-negative integer n, suppose that X(0) = x. Then Proof. For each n ∈ ZZ + , Taking expectations and noting that E We can use Dynkin's formula to analyze drift in a system. As a corollary of this, we get our main result.

Theorem 27 (The Comparison Theorem)
Suppose that Z, f, and s are functions from X to the non-negative reals. Suppose further that, for X(0) equal to any fixed x, Then for any stopping time τ , Note: The functions Z, f , and s in the Comparison theorem should be interpreted as follows. Z is the function whose drift we're considering, e.g. the total queue length. The amount that Z drifts down by in one step is f . Finally, s is an exception parameter; typically, it equals a constant on some "bad" set of (finitely many) exceptions, and zero everywhere else.
Proof. Since we have a Markov chain, our assumption in Equation A.3 actually tells us that for all t, EZ(X(t + 1)|X(t)) ≤ Z(X(t)) − f (X(t)) + s(X(t)) Fix some integer N > 0 and note that and hence by adding the finite term Letting n → ∞, and then N → ∞ gives the result by the monotone convergence theorem. ✷ Special cases of the Comparison Theorem give some frequently used stability criteria.
Corollary 19 (Foster's Criterion) Suppose we have a discrete time irreducible, aperiodic Markov chain with a countable state space. Suppose we construct a potential function Z : X → IR + . Suppose that for any real B, there are only finitely many states x ∈ X with Z(x) < B.
Proof. This result follows from the Comparison Theorem. It was originally proved (in a slightly weaker form) by Foster [26]. ✷ It's interesting to node that the converse is also true. Suppose we have a stable Markov chain. Fix some state x 0 ∈ X . Define Z(x 0 ) = 0, and otherwise let Z(x) be the expected number of time steps until x returns to x 0 . (By stability, this expectation is finite.) If Z(x) > 1, then the expected change is exactly −1 in one time step.
Foster's Criterion amounts to taking a constant f (x) in the Comparison Theorem. To prove stronger results, we need to let f (x) grow. For example, suppose we wanted to show that the expected queue length was finite, where q(x) is the length of the queue of state x. Then it would suffice to find a B 0 and f (x) such that If we choose a f (x) that grows even faster, we can prove stronger results.
Definition 32 Consider a discrete time Markov chain. Take a β > 0 and f : X → IR + such that f (x) ≥ 1 for all x. Let ∆f (x) be the expected change in f (x) after one time step. Suppose there is a bound B such that for any x ∈ X with f (x) > B, we have Then we say that the Markov chain is geometrically ergodic.
There are a host of interesting facts about geometrically ergodic Markov chains. The two I use in this thesis are the following: Corollary 20 If we have a geometrically ergodic Markov chain, then the return time to any state has an exponential tail. Also,

A.5 Queueing Theory
Theorem 29 Suppose we have a discrete time single server queue. Suppose that packets are inserted by a Bernoulli process such that a packet arrives with probabilityÂ. Suppose that service times are geometrically distributed such that a packet departs with probabilitŷ D.
Define A =Â(1 −D) and D =D(1 −Â). (A is the chance of a net gain of one packet; D is the chance of a net departure of one packet.) Suppose that we measure the system after new packets have arrived and before old packets have departed. Then the stationary distribution is: Suppose that we measure the system after packets have departed and before new packets have arrived. Then the stationary distribution is: so the expected queue length is: Proof. Given the stationary distributions above, it is straightforward to plug them in and verify that they work. ✷ Theorem 30 (Discrete Time Pollaczek-Khinchin Formula) If arrivals are Bernoulli with parameter λ, and Z is the distribution of service times, then Proof. The continuous time version can be found in Gallager [27], pages 85-87. The conversion to discrete time is fairly straightforward. ✷ Why does the regular Pollaczek-Khinchin formula work need to be changed at all, since discrete time queues should be a special case of continuous time? Well, the values of the expected queue length are sampled at discrete intervals, so this skews the formula slightly. This result implies that if a node has nominal load r, then the probability of that node being idle is 1 − r, assuming ergodicity.
Proof. A proof can be found in Gallager [27]. ✷ In the single node case, the 1 − r probability is particularly useful. If r < 1, then the system is ergodic, so Little's Theorem holds. Therefore, the stationary probability that there are no packets in queue is 1 − r. If we have N > 1 nodes in our network, though, it does not generally follow that the probability that all of them are empty is (1 − r) N (unless, for instance, the stationary distribution is product form.) Finally, let us turn to renewal reward functions.
Definition 33 Suppose we have discrete time, aperiodic, irreducible, countable state space Markov chain X(t). Let us specify a special state σ renew , and consider the system to undergo a renewal when it enters that state. If we start this Markov chain in state σ renew , it is called a renewal process; if we start it in an arbitrary state, it's called a delayed renewal process.
(The "delay" refers the time until the first entrance to state σ renew .) Let ω be the path of states leading up to the current state; so, at time t, ω = (X(0), X(1), ..., X(t)) Let Ω be the collection of all such paths. A renewal reward function is a function R : Ω → IR such that R depends only on the last renewal period.
LetX 2 be the expected number of time steps until a renewal. Letω(t) be the path at time t. Then Proof. See Gallager [27], Sections 3.4-3.7. ✷ • Observe that since the arrivals are determined by the sum of a finite number of Bernoulli processes, then there is a maximum arrival rate. Since at most one packet crosses each edge on one time step, there is a maximum departure rate. Let B be the maximum of these two numbers.
As a simple, but hopefully sufficient introduction to fluid limit theorems, I offer the following proofs.

B.2 An Analytic Fact
I'm going to need a result from analysis.
Also, f (t) is a Lipschitz function with Lipschitz coefficientB.
Proof. Order the rationals q 1 , q 2 , . . .. Observe that for any t, |f j (t)| ≤Bt. The set of values for f j (t) for a fixed t and for all j is contained in a compact set (namely [−Bt,Bt].) Therefore, there exists a subsequence j 1 1 , j 1 2 , . . . such that for some constant f (q 1 ). Next, we look for a sub-subsequence f 2 Observe that since this is a sub-subsequence, we still have that We can continue on in this way for all the rationals, constructing {j k i } for k = 1, 2, . . .. Unfortunately, ∩ ∞ k=1 {j k i } may be empty, so we're not done yet. However, consider the diagonal sequence j i defined by j i = j i i for i = 1, 2, . . .. Observe that this sequence is infinite (and non-empty), and that for any i, (because after the first i terms, {j i } is contained in {j i k }.) Therefore, {f j i } converges on all rationals. Now, take any t (not necessarily rational). For any rational q k , for any f j i , we have that So, by taking a series of rationals that converge to t, we can show both lim sup i f j i (t) and lim inf i f j i (t) are finite and equal to each other. Therefore, f (t) exists for all t. Equation B.1 also tells us that f (t) is Lipschitz with the same Lipschitz coefficients. ✷

B.3 Fluid Limits
The purpose of this section (and fluid limit models in general) is to show that Equation 4.1 (page 75) can be proved by certain very natural rescalings of the underlying stochastic process. It takes a while to establish all the limits, but never fear: all will come together in Theorems 34 and 35. Let x be the initial state of the system, i.e. X(0) = x. To indicate that a process starts in state x, I will stick a superscript x on the process, e.g. X x (t) is the state at time t when it started in state X x (0) = x.
We can always view a discrete time process as embedded in continuous time. As an example, let us consider Q(t), the length of a queue at time t. One natural way of converting to continuous time is to use step functions: Q(t) = Q(⌊t⌋). However, in order to get the simplest possible proofs, I'm going to "connect the dots" between integer values: if ⌊t⌋ < t < ⌈t⌉, then Q(t) = (t − ⌊t⌋)Q(⌈t⌉) + (⌈t⌉ − t)Q(⌊t⌋). (In order to preserve Markovity, then, the value at Q(⌈t⌉) must be known when we are at time t 0 > X(⌊t⌋). One simple way to do this is to have Q(t) be the queue length at time t − 1.) Observe that since the discrete time process changes by at most B packets in one time step, then this continuous version is Lipschitz, with coefficient B.
First, some definitions: • A l (t) is the total number of exogenous arrivals to class l by time t, i.e. Note that all three of these quantities are independent of the initial state, e.g. A x l (t) = A l (t).
Lemma 25 Let {x n } ⊆ X be such that lim n→∞ |x n | = ∞. Then almost surely, for any (fixed) t ≥ 0, Proof. Fix t. By the strong law of large numbers, for any i.i.d. random variables X i , almost surely. The lemma follows immediately in all three cases. ✷ A few more definitions: • Suppose that class l occurs at node i. Then define T x l (t) as the cumulative amount of time node i has spent on class l packets by time t, starting in state x. ("T " stands for "throughput".) • For a node i, define I x i (t) to be the cumulative amount of time that node i is idle, i.e.
(Note that the subscript for throughput refers to a class, whereas the subscript for the idleness refers to a node.) Now let's try to calculate the total queue length of class l packets at a particular node at time t. We can figure this out by taking the class l packets that we start out with (in state x), adding all the packets entering class l, and subtracting all the packets that leave it. The departures are equal to the total amount of time spent processing class l packets, fed into the function telling us how many packets depart in that amount of time. This is simpler as an equation: Some other useful facts that follow immediately are Observe that T x l (t) and I x i (t) are Lipschitz functions, hence they are continuous and almosteverywhere differentiable (see Rudin [43], page 146).
The protocols that I'm interested in are all work-conserving, or greedy. That is, a node i should be idle only if its queue is empty (of any class of packets). One way of expressing this is by saying that at node i,İ (B.6) (By the comment above, the derivativeİ x i (t) exists almost everywhere.) Finally, there might be some additional constraints specific to the routing protocol we're using. For completeness, I'll list some additional conditions specific to the routing protocol (B.7) Now we come to our first major fluid limit theorem: Theorem 34 I am going to construct three functions,Q l (t),T l (t), andĨ i (t), that satisfy certain limits below. Consider a greedy routing protocol. For almost all sample paths and any sequence of initial states {x n } ⊆ X with |x n | → ∞, there is a subsequence {z n } ⊆ {x n } with |z n | → ∞ such that, for all classes l, the following finite limits exist Furthermore,Q l (t) andT l (t) satisfy the following: Let class l be served at node i. Theñ Proof. Observe that for any x n , any l, Since [0, 1] is compact, there exists a convergent subsequence that converges to some value between 0 and 1. Similarly, since [0, 1] C is compact, we can choose x n j that simultaneously converge for any l = 1, . . . , C.
Next, let f j (t) = 1 |xn j | T (|x n j |t). Observe that f j (t) is non-decreasing, and grows no faster than t, i.e. for any s, t ≥ 0, Hence, the f j are a collection of Lipschitz functions with the same Lipschitz coefficient (namely 1). Also, f j (0) = 0. This allows us to use Lemma 33 to find a subsequence {z h } ⊆ {x n j } such that for any t, for some functionT l . This implies equations B.8 and B.9. This also tells us that all these objects are Lipschitz functions, and hence continuous and almost-everywhere differentiable.
Next, we're left with the "greedy" condition, formula B.14. Suppose that at some node i, for some t > 0, k∈C iQ k (t) = ǫ > 0. Therefore, for some sufficiently large bound d, Since at most B packets can arrive or leave the system on any given time step, then So, if we take d ′ ≥ d sufficiently large, we can guarantee that for h ≥ d ′ , and hence that if s ∈ G = (min{0, t − ǫ/4B}, t + ǫ/4B), then Therefore, by Equation B.6, (1/|z h )I i (s|z h |) will be constant for every h ≥ d ′ and s ∈ G.
Therefore, the limitĨ i (s) will be constant on G, so˙Ĩ l (s) is identically equal to zero a.e. on the interval. In particular,˙Ĩ of the fluid models.) We say that a fluid limit model (respectively fluid model) is stable if there exists a constant T , depending only on the α l and the P k,l such that for any fluid limit (resp. fluid models) with C k=1Qk = 1, we have for any k, Q k (t) = 0 for any t ≥ T .
Finally, we're ready to illuminate the relationship between stability for the fluid models and stability for the underlying stochastic models.
Theorem 35 Fix a greedy routing protocol. If the fluid limit model of the queueing discipline is stable, then the original Markov chain X is positive recurrent.
Proof. Assume that the fluid model is stable. For any sequence of initial states {x n }, by Theorem 34, there exists a subsequence {x n j } such that for any class l, where this equals zero by fluid stability.
Observe that because we assumed that there was a maximum rate of arrivals, then 0 ≤ 1 |xn j | Q l (|x n j |T ) ≤ B(T + 1). We can then use Corollary 21 from Section A.4 to conclude that lim (Note that the 1 |xn j | is a constant for each j, so we can pull it out of the expectation.) Now, our choice of sequences {x n } was arbitrary. In particular, let {x n } = X in some ordering. Consider lim sup The Lipschitz condition implies that the equation above is bounded, so the lim sup is finite. Let us take a subsequence {x n } ⊆ {x n } that has the lim sup as the limit, i.e.
Therefore, if we take the subsequence {x n j } as above, we get that lim sup where the second equality follows because we are taking a subsequence of a sequence with a limit. Since Q k is non-negative, we conclude that Qx n k (|x k |T ) = 0 so by Theorem 11, the underlying Markov chain is positive recurrent.

✷
One final comment on the relationship between fluid models and fluid limit models. In principal, it would suffice to prove results about fluid limit models, then use Theorem 35 to push the result back to the stochastic case. Unfortunately, it is practically impossible to distinguish the fluid models that arise from fluid limits from the fluid models that exist only as solutions to equations B.10 through B.15. Therefore, in practice, one proves results about all fluid models. The results will then apply to the subset of fluid models that happen to be fluid limits.

B.4 Specific Protocols
Theorem 34, minus Equation B.15, works perfectly well. For example, if you want to show that every greedy protocol on a ring is stable, you're ready to go. However, you may wish to prove that a particular protocol (possibly on a particular network) is stable. In that case, you need to instantiate Equation B.15 with some equation appropriate to the protocol. I'm going to mention just two protocols here; generally speaking, dealing with these sort of limits is technically necessary but not the hard part of the problem.

B.4.1 FIFO
The FIFO protocol demands that the packet that has been waiting for the longest time at a node be the next served. Ties are broken in any manner; in our packet routing model, it doesn't make any difference. To write an equation capturing FIFO, define D x k (t) as the total number of departures from class k by time t. Define W x i (t) as the total amount of work left to do at node i at time t, that is, W x i (t) = k∈C i Q x k (t). Then if class k packets live at node i, the equation specifies FIFO. The fluid limit of this follows pretty easily. More on this can be found in Bramson [8], which also shows that FIFO is always stable on a packet routing network as I've defined it. (Because all edge crossings take one time step, it's a generalized Kelly network.) Note that this contradicts the intuition given by the adversarial result that FIFO is not always stable (against an adversary).
Note also that FIFO either requires an infinite number of classes, or (as is standard) that the packets at each queue are ordered.

B.4.2 Priority Disciplines
A priority discipline always gives precedence to certain classes over others. We have to define, in addition to the regular throughput, a special throughput for all the classes that effect class k packets, i.e. all the packets of greater than or equal priority. Let H k be the set of packets of priority greater than or equal to k's priority that are served at the same node as k. (Note: the only class with priority equal to k's is k itself.) Then, define We then can define We then get a new greediness condition: almost everywhere. The fluid limits to these equations follow pretty readily-the new greediness condition can be proved the same way we proved the old one.

C.2 Layered Networks
Theorem 36 A layered network is stable under any greedy protocol.
A proof of this result can be found in Dai [20], Section 6. Also, for the world's shortest conceivable proof of this, note that the output process of a stable queueing system is itself a hidden Markov process; therefore, the fluid stability of a single node network under the hidden Markov fluid model implies stability for layered networks.
A good example of this technique is the hypercube network defined on page 101. But how should we route packets on a hypercube? Definition 37 Consider a d-dimensional torus. The network 1 uses dimensional routing if packets proceed as follows: to get from (x 1 , . . . , x d ) to (y 1 , . . . , y d ), we find the first i such that x i = y i , travel around that dimension for y i − x i mod l i steps, and repeat for all successive dimensions (in order).
Because the hypercube is a special case of the torus, we can use dimensional routing on it, too. If we consider the edge graph of the hypercube under dimensional routing, it is layered, and hence the network is stable. Formally, Corollary 23 Under any i.i.d. or hidden Markov arrival process, under any greedy protocol, the hypercube is stable under dimensional routing.

C.3 Meta-layered Networks
We can generalize the layered results to a wider class of networks.
Definition 38 Suppose we have a collection of networks N 1 , . . . , N m . Suppose that we add directed edges e such that e crosses from a node in N i to a node in N j only if i < j. Then we will call this network a meta-layered network where we call N i the ith layer.
Theorem 37 Suppose we have a meta-layered network, each of whose layers has a stable fluid limit. Then the meta-layered network is stable.
Proof. This result follows immediately from the hidden Markov stability results. Or, one can reason as follows: Since nothing enters N 1 except for its original arrivals, and we know that the fluid model is stable, then the fluid drains from N 1 by some finite amount of time T 1 . In the first T 1 time steps, the fluid that has pooled in N 2 can only have worsened by a finite, bounded amount. From T 1 onward, the fluid flowing in to N 2 is the same as if N 1 weren't attached, and N 2 just had a higher arrival rate. Since we assume that it's fluid model is stable, there exists a time T 2 such that it has emptied by time T 2 . Proceeding in this fashion, by a finite amount of time T n the whole system will have emptied. ✷ We can apply this result to the torus: Corollary 24 Under any i.i.d. or hidden Markov arrival process, under any greedy protocol, the torus is stable under dimensional routing.
Proof. Viewing each layer of a torus as a ring, which we know has a stable fluid limit from Section C.1, we can use Theorem 37. ✷

C.4 Convex Routing
See Section 6.2. The stability of wrapped butterflies (under convex routing) follows from this result.

C.5 Generalized Kelly Networks with FIFO
This stability result is in Bramson [8]. The parts relevant for implying stochastic stability are a relatively small subset of the paper: Sections 1 through 5, plus one lemma from Section 6, suffice to imply stability when the nominal loads are all less than 1.

C.6 Prioritizing All Paths
Theorem 38 Suppose that we have a simple network, and each class of packet follows a deterministic, fixed path. Suppose that we prioritize all the (finitely many) paths, so that packets travelling along higher priority paths have precedence. Then the network is stable.
Proof. List the classes from highest priority to lowest priority, as c 1 , . . . , c n . Suppose that the total arrival rate in the whole network of class c l packets is λ total l . The class c 1 packets will see a feed-forward network (because the network is simple), and hence all the fluid will drain by some time t 1 regardless of the initial fluid configuration. In this amount of time, the class c 2 packets will have fluid volume at most 1+λ total 2 t 1 (which is finite). Now, there will never be any more class c 1 fluid in queue. However, there is still some processing capacity taken up by the nominal load of this class. Let me make this precise. Suppose that at some node k, the nominal arrival rate of class l packets is λ l , the mean service time is µ l , so the nominal load contributed by class l packets is r l = λ l µ l . The nominal arrival rate at k is, of course, r = r l < 1.
When there is no longer any class c 1 fluid in queue, node k behaves as though µ l had been replaced by µ/(1 − r 1 ) for all classes l, and analogously at each node k. We can now repeat the whole feed-forward argument above on classes c 2 , . . . , c n , and continue (by induction), and we're done. ✷ Note: This analysis is similar to the "push starts" of Dai and Vande Vate [21]. They are interested in non-simple networks, but can only analyze networks with at most two (!) nodes. For packet routing purposes, the above theorem is obviously much more relevant. There are some immediate corollaries of great use for packet routing.

Corollary 25
Suppose that to route a packet to its destination, only its destination and current node are necessary to find the path, and all paths are simple. Suppose that we rank the destinations in any order, and let packets with higher ranked destinations have precedence over packets with lower ranked destinations. Then the network is stable.
Proof. This follows immediately from Theorem 38. ✷

Corollary 26
Suppose we have a simple network, and packets follow fixed paths. When each packet is created, label it with an integer between 1 and P . This integer is called the priority of the packet. If two packets x and y contend for service, and they have priorities

C.8 Closest to Origin
Closest to Origin (CTO) proceeds almost exactly as FTG does. Packets are ranked according to their distance from their origin, with packets closer to their origin getting priority. Ties can be resolved by arbitrary priority, or, in the case of a generalized Kelly network, by FIFO.
Theorem 40 CTO is stable on all simple networks.
Proof. We consider all packets that are at their origin; as in FTG, we show that these are stable, and then renormalize the mean service times. We then consider packets that are distance 1 from their origin, then distance 2, and so forth. By simpleness, there exists a finite l such that no packets travel farther than l steps from their origin, and we're done. ✷ Note: This proof is exactly like FTG, except we induct in the opposite direction.

C.9 Longest In System
It is rumored that Maury Bramson has a proof of the stability of LIS for some class of networks; I haven't been able to find it, so I offer this proof.
First, a technical point. For time-based protocols, like LIS and SIS (see the next section), the reader may become worried about the structure of the state space. If we keep a timestamp on every packet, the system is clearly not going to be stable-since time keeps increasing, we would never get to close to returning to the same state. To solve this problem, every time the system is emptied of all packets, just reset the system clock to zero. This resetting doesn't change the protocol. Proof. Take the fluid limit, but change the norm slightly; rather than take the sum of the queue at each node, take the sum of the remaining expected work of each packet. Because the expected work of each packet is finite, this change still yields a bounded norm, and we can take a fluid limit.
Suppose that we place 1 fluid unit of work in the system, and don't let any new fluid enter. So long as there is a non-empty queue, that queue will be performing work at a rate of one unit per time step. Therefore, by time t ≤ 1, the system will have emptied of all fluid.
So, suppose we place 1 fluid unit of work in the system, and allow new fluid to enter. Because older fluid has priority in LIS, then this fluid behaves as though no new fluid had entered the system, and will empty by time t. Because the nominal loads are less than one (say r < 1), then at most r more units of fluid will enter the system during that initial t < 1 time interval. This fluid will, in turn, empty in at most r time steps. Continuing this process, the entire system will empty by, at the latest, 1 + r + r 2 + r 3 + · · · = 1 1 − r < ∞ ✷ C.10 Shortest In System Theorem 42 All networks are stable under the Shortest In System (SIS) protocol.
Proof. Let us create a work-based norm, as in Theorem 41, and take the fluid limit. New fluid arriving doesn't see any of the (older) fluid queues, and thus immediately exits the system. Therefore, no new fluid is added to queues. Because the nominal loads are less than one, there is a least ǫ > 0 such that every node does work at a rate of at least ǫ when it has a non-empty queue. Therefore, if we start the system with one unit of fluid, it will empty by time 1 ǫ < ∞. ✷

C.11 Nearest To Go for Re-entrant Lines
A re-entrant line is a network where every packet follows the same path. However, there may be multiple classes present at each node, so priority is important. Clearly, if the network is also simple, we have a linear array (which is layered, and hence stable), so this problem is only non-trivial if we have a non-simple network. The stability of NTG in this case (and FTG, for that matter) can be found in Dai and Weiss [22].

C.12 Round Robin
Normally speaking, a node uses a "round robin" protocol if it switches between all the nonempty classes present in that node in some order. The (more general) protocols I'm going to be considering might better be called "weighted round robin", because certain classes might appear several times in the same cycle.
Theorem 43 (Bramson) Consider a fluid model. Let r n c be the nominal load of class c packets at node n. Suppose that there exists an ǫ > 0 such that node n always dedicates at least r n c + ǫ of its resources to class c, for every n, whenever class c is non-empty. Then the protocol is stable.
A proof of this result can be found in Bramson [9]. This gives us some interesting corollaries.
Corollary 27 Suppose that we route packets according to the following protocol: at each node n, for classes c 1 , . . . c m that pass through n, we spend s n c 1 steps passing class c 1 , then s n c 2 steps passing class c 2 packets, and so on. If there are no more packets of class c i , we (immediately) move to the next class.
If s c i m j=1 s c j > r n c j for all c i at all nodes n, then the system is stable. Observe that if the nominal loads are less than one, then such a choice of s c i always exists (and easy to figure out.) Corollary 28 Suppose that we route packets according to the following protocol: Let c 1 , . . . , c m be the classes currently present at node n. Suppose that the nominal loads of these classes at node n are r c 1 , . . . , r cm . When selecting the next packet to go, choose one at random according to some fixed distribution (determined by the classes that are currently present at the node) such that Pr[class c i is chosen] > r c i Then the system is stable.
If the nominal loads are less than one, such distributions always exists.

C.13 Leaky Buckets
The idea of a "leaky bucket" is to reduce the burstiness of the packets travelling in a network. Formally, for every class transition from class c 1 to class c 2 , we insert a new, single class node n c 1 ,c 2 . The packets from c 1 must travel to node n c 1 ,c 2 before bouncing back to the location of the c 2 packets. It turns out that it is possible to stabilize any network with the judicious use of leaky buckets. See Bramson [9] for details.

C.14 The Utility of Adversarial Results
Just as one can prove ergodicity by taking fluid limits, it is possible to prove stability against bounded adversaries by taking a slightly different kind of fluid limit. The details were worked out by Gamarnik [28].
The resulting class of functions that can be the limits of adversarial networks is larger than the functions generated by stochastic fluid limits. Optimistically, then, one might hope that stability results for adversarial queues might have clear fluid analogues, which would then apply to the special case of stochastic fluid limits. Unfortunately, I don't know of any instances of this technique actually producing new theorems yet.

Appendix D Fluid Limit Counterexamples
This appendix is the twin to Appendix C. It consists of surprising examples of instability in queueing networks.

D.1 Nonmonotonic stability
Uriel Fiege [25] has some fascinating results showing how pathological a stability region can be. He constructs a 20 node network with a simple and natural adaptive greedy routing protocol. Packets are injected according to Bernoulli arrival processes at rate q. He shows that the system is stable iff q ∈ [0, 1/3) ∪ (2/3, 1], but unstable for the [1/3, 2/3] region in the middle.

D.2 Virtual Stations and Instability
There is a very clever general technique for generating unstable queueing networks even when the nominal loads are less than one. If two classes at two distinct nodes are never simultaneously in service, then they act as though they were sharing service in the same node, forming a "virtual station". By including virtual stations in a network, it gives extra restrictions on stability, analogous to the restrictions on the nominal load. If these restrictions are violated, the network can easily be shown to be unstable. See Dai and Vande Vate [21] or Bertsimas, Gamarnik and Tsitsiklis [3] for more on this.
The counterexamples in the next three sections all rely on virtual stations for their instability.

D.3 NTG can be Unstable
There is a simple two-node network where Nearest To Go (NTG) is unstable. See Dai and Weiss [22], Figure 4. (I mean "simple" in the sense of Definition 35, not colloquially.)

D.4 Uniformly Generalized Kelly Networks can be Unstable
See Dai and Weiss [22], section 6, remark 2. Observe that their two-node network is a re-entrant line, and not simple.

D.5 A Generalized Kelly Network without Immediate Feedback can be Unstable
A network has immediate feedback if it is possible for a packet to return to a node without travelling to any intervening nodes. An immediate feedback-free generalized Kelly network can be found in Dai and Weiss [22], Figure 5. If you have as much difficulty looking up the reference given by Dai and Weiss as I did, you may prefer to consider the following system. Suppose we have a generalized Kelly network with immediate feedback, and insert extra stations along the edges with immediate feedback. Let each new node have the same mean service time as the (unique) node preceding it. Observe that if we consider the fluid limit and don't place any initial fluid on these new nodes, no fluid will ever queue there. Therefore, the fluid model will evolve identically to the fluid model with immediate feedback, which we can make unstable.

D.7 Adversarially Unstable, Stochastically Stable
Since all generalized Kelly networks are stable under FIFO (see Bramson [8]), then the counterexamples showing FIFO to be adversarially unstable (see Andrews et al. [1]) show this.

D.8 Stochastically Unstable, Adversarially Stable
Consider a one node network (i.e. a single queue) in discrete time. Consider the stochastic arrival process where with probability 1 2 , no packets arrive, and with probability 1 2 , two packets arrive. Each packet takes 1 time step to leave the network.
If we consider the state space generated from the "new packets arrive, then packets depart" cycle, it's easy to see that all states are equally likely. (A state is determined entirely by the number of packets in queue.) Therefore, the network is unstable (but nullrecurrent).
If we consider a rate (1, w) adversary on a single node, i.e. for every window of w steps, no more than w packets can arrive, then it's easy to show that there can never be more than w packets in the system, so the system is stable against a bounded adversary.
At this point, one might expect us to take the limit as time grows large, and try to bound the error in the evolution of the coefficients. Shockingly, the coefficients converge in a finite (and explicitly calculable) amount of time.
Why does this happen? Let's sketch a proof.

Theorem 44
Assume that there is a maximum path length in the network. Then in a finite amount of time, the kth degree Taylor coefficients of the stationary probabilities will converge to their final value.
Proof. We can prove this result by a double induction. First, we induct on the degree of the coefficients. If we consider the p 0 order term, observe that it is always one for state σ 0 , and always zero for all other states. This establishes the base case. For an arbitrary degree k, there are several different terms that contribute to it. The probability of state σ is the weighted sum of all the different possible paths into it. Now, take the collection of states S that are reachable with k packet arrivals. Because packets have maximum path lengths, the state space must empty in a bounded amount of time. Therefore, there are no loops among the states in S (or the state space could cycle through the loop for an unbounded amount of time.) It follows that S forms a directed acyclic graph.
Using the natural ordering on DAGs gives a partial well-ordering, so if we can deal with all the base cases, we can induct on the structure. (This is the second induction in the proof.) The base case consists of the states in S that can only be reached by states with k − 1 or fewer arrivals. By induction, the degree k − 1 and lower coefficients will converge in a finite amount of time; since a packet arrival amounts to multiplying the probability by p, which shifts over the coefficients, then it follows that the degree k terms in the base cases will converge in a finite amount of time.
For the other states in S, observe that they are reachable either by states lower in the partial well-ordering, or by the insertion of new packets. By our inductive assumption on S, the coefficients of the states lower in the partial well-ordering converge in a finite amount of time. By our induction on the degree of the coefficient, the prior states that require packet insertions also contribute coefficients converge in a finite amount of time. Therefore, their sum will converge.
Unfortunately, we're not quite done. As t → ∞, our sample path will converge to the expected value; this follows from ergodicity. If the convergence were uniform in some neighborhood of zero, then the result above would immediately give us the value of the Taylor coefficients of the expected value itself. However, it's not clear how to prove uniformity of convergence, so I'll use a different approach.
As mentioned above, the zero order coefficients are always correct; the coefficient is one if there are no packets, and zero otherwise. Using the same double-induction as above, we can show that all the probabilities of the stationary distribution equal the values we have calculated in finite time. ✷ If we examine the preceding proof more carefully, it is possible to estimate the speed of convergence for a ring fairly tightly. The convergence is quite rapid, so calculating the Taylor coefficients is practical.
What do these coefficients look like, anyway? Well, suppose that we define a new variable, s = p N −1 , and expand in s, instead of p. (Clearly, Theorem 44 applies to s, too.) Whenever a packet arrives, it chooses its particular destination with probability s. With a little thought, it becomes clear that the coefficients will all be integers.
We are now sitting in the catbird seat, computationally speaking. We can set up the finite number of states that have non-zero coefficients of degree less than k + 1, store only this finite set of coefficients per state, and calculate the probability for a finite amount of time. Since the coefficients will all be integers, there won't be any rounding errors. We will then have calculated our stationary probabilities exactly! Moreover, we can calculate other quantities, like the expected queue length. If we're interested in the first k + 1 terms of the expected total queue length, we can just calculate the stationary probability for the finite number of states with non-zero coefficients of degree less than k + 1, and then add them together (weighed by their queue length).

E.2 The Payoff
After proving Theorem 44 and writing a body of code to perform the calculations inherent in the proof, I was able to determine the Taylor expansions that show up in Subsection 5.2.2. As I demonstrate in that subsection, I can use the results to make various conclusions about the stationary distributions.
However, the conclusions are mostly negative (the expected queue length is not absolutely monotonic, nor is it a small-degree rational function.) Is it possible to get more positive results from these values?
It certainly is. I calculated the Taylor expansions for the stationary distribution of several states in a standard 3-node Bernoulli ring. By observing the Taylor coefficients, I recognized some of the rational functions that show up in Chapter 2. Without exact Taylor coefficients, it would have been impossible to guess the functions. Running the program on larger nonstandard rings, with L = 2, I noticed that the marginal distributions were unchanged. These results lead me to guess Equation 2.1 for the stationary distribution.
Once I had guessed the stationary distribution, I still had a fair amount of work to do in proving that it held for all N . However, I never would have tried to prove something like Theorem 5 without the evidence from the Taylor expansions pointing the way.

E.3 Real World Details
In practice, these calculations took about 1 gigabyte of memory, ran a couple of days on 500 MHz processors, and gave, for instance, k = 18 places of accuracy for the 4 node standard Bernoulli ring. The limiting resource for my efforts was always the available memory (RAM) of the machine I was working on. Therefore, it was important to reduce the size of the state space, and the information held at each state.
The most dramatic method of reducing the state space is by not specifying the destination of packets that are still waiting in queue. Because the Greedy Hot Potato algorithm never returns a packet to queue, queued packets are all stochastically identical. Leaving them unspecified amounts to an exponential reduction in state size.
There are a host of small issues to deal with (for instance, how should I deal with overflow, when the coefficients become larger than the 2 31 bit signed integers on a typical machine?), but from a mathematical point of view, they aren't really interesting enough to relate.