Optimal Packet-oblivious Stable Routing in Multi-hop Wireless Networks
Vicent Cholvi Paweł Garncarek Tomasz Jurdzinski Dariusz R. Kowalski


Gluon polarization measurements from longitudinally polarized proton-proton collisions at STAR
    Zilong Chang for the STAR Collaboration
    
==============================================================================================





Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. 

In this paper, we introduce  a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies, we  propose a packet-oblivious routing algorithm which is working without using any global topological information, and guarantees stability for certain injection rates.  We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed.

Furthermore, we also introduce a packet-oblivious routing algorithm that guarantees stability for higher traffic. This algorithm is optimal regarding the injection rate for which stability is guaranteed. However, it needs to use some global information of the system topology. 








§ INTRODUCTION



Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. The importance of such an issue is obvious, since if one cannot guarantee stability, then one cannot hope to be able to ensure deterministic guarantees for most of the network performance metrics.


For many years, the common belief was that only overloaded queues (i.e., when the total arrival rate is greater than the service rate) could generate instability, while underloaded ones could only induce delays that are longer than desired, but always remain stable. However, this belief was shown to be wrong when it was observed that, in some networks, the backlogs in specific queues could grow indefinitely even when such queues were not overloaded <cit.>. These later results aroused an interest in understanding the stability properties of packet-switched networks, so that a substantial effort has been invested in that area. Among the obtained results, stability of specific scheduling policies was considered for example in <cit.>.  The impact of network topologies on injection rates that guarantee stability was considered in <cit.>. A systematic account of issues related to universal stability was given in <cit.>.


Whereas in  wireline networks a node can transmit data over any outgoing link and simultaneously receive data over any incoming link, the situation is different in wireless networks. Indeed, nearby wireless signal transmissions that overlap in time can interfere with one another, to the effect that none can be  transmitted successfully. This makes the study of stability in wireless networks more complex. As in the wireline case, a substantial effort has been invested in investigating stability in that setting. Stability in  wireless networks without explicit interferences was first studied by Andrews and Zhang <cit.> and Cholvi and Kowalski <cit.>.   Chlebus et al. <cit.> and Anantharamu et al. <cit.> studied adversarial broadcasting with interferences in the case of using single-hop radio networks. In multi-hop networks with interferences, Chlebus et al. <cit.> considered interactions among components of routing in wireless networks, which included transmission policies, scheduling policies and control mechanisms to coordinate transmissions with scheduling. In <cit.>, the authors demonstrated that there is no routing algorithm guaranteeing stability for an injection rate greater than 1/L, where the parameter L is the largest number of nodes which a packet needs to traverse while routed to its destination. They also provided a routing algorithm that guarantees stability for injection rates smaller than 1/L.
Their approach, however, 

is not accurate for studying stability of longer-distance packets;
therefore, in this work we study how the stability of routing depends of the conflict graph (which we will formally define later) of the underlying wireless networks, which is independent of the lengths of the packets' routes.



  
*Our results

In this paper, we study the stability of dynamic routing in multi-hop radio networks with a specific methodology of adversarial traffic that reflects interferences. We focus on packet-oblivious routing protocols; that is, algorithms that do not take into account any historical information about packets or carried out by packets. Such protocols are well motivated in practice, as real forwarding protocols and corresponding data-link layer architectures are typically packet-oblivious.






First, we give a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies such as Longest In System (LIS), Shortest In System (SIS), Nearest From Source (NFS) and Furthest To Go (FTG), we  propose a local-knowledge packet-oblivious routing algorithm (i.e., which is working without using any global topological information) that guarantees stability for certain injection rates.  We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed, mainly, for Θ(1/Δ^H), where Δ^H is the maximum vertex degree of the conflict graph of the wireless network.

Later, we introduce a packet-oblivious routing algorithm that, by using the same queueing policies, guarantees stability for higher injection rates. This algorithm is optimal regarding the injection rate for which stability is guaranteed. However, it needs to use some global information of the system topology (so called global-knowledge). 

Table <ref> summarizes the main results of this paper.




The rest of the paper is structured as follows. Section 2 contains the technical preliminaries. In Section 3, we introduce and study universally strong selectors, which are the core components of the deterministic local-knowledge routing algorithm that is developed in Section 4, where we show that it is asymptotically optimal. In Section 5, we present a global-knowledge routing algorithm that guarantees universal stability for higher traffic,  we also show that it is  optimal. 
In  Section 6, we extend the results obtained for the Longest-In-System scheduling policy in Section 4 to other policies,
mainly, SIS, NFS and FTG. This extension is based on different technical tools, mainly, on reduction to the wired model with failures studied in <cit.>, in which SIS, NFS and FTG are stable. 
We conclude with future directions in Section 7.  Some technical details and proofs are deferred to the Appendix.



§ MODEL AND PROBLEM DEFINITION




  
*Wireless radio network

We consider a wireless radio network represented by a directed symmetric network graph G=(V_G, E_G). 
It consists of nodes in V_G representing devices, and directed edges,
called links, representing the fact that a transmission
from the starting node of the link could be directly delivered to the ending node. 
The graph is symmetric in the sense that if some (i,j) ∈ E_G  then (j,i) ∈ E_G too. 
Each node has a unique ID number and it  knows some upper bounds on the number m of edges in the network and the network in-degree 
(i.e., the largest number of links incoming to a network node).[In which case the performance will depend on these known estimates, instead of the actual values.]

Nodes communicate via the underlying wireless network G.
Communication is in synchronous rounds.
In each round a node could be either transmitting or listening. 
Node i receives a message from a node j i in a round if j is the only transmitting in-neighbor of i in this round and node i does not transmit in this round;
we say that the message was successfully sent/transmitted from j to i.



  
*Conflict graphs

We define the conflict graph H(G)=(V_H(G), E_H(G)) of a network G as follows: (1) its vertices are 
links of the network (i.e., V_H(G) = E_G) and, (2) a directed edge (u,v) ∈ E_H(G) if and only if a message across link v ∈ E_G cannot be successfully
transmitted while link u ∈ E_G transmits.
Note that, accordingly with the radio model, a conflict occurs if and only if the transmitter in u is also a receiver in v or the transmitter in u is a neighbor of the receiver in v (see Figure <ref> for an illustrative example).
If network G is clear from the context, we skip the parameter G in H(G) (i.e., we will use  H). 
Note that, the links in our definition are directed in order 
to distinguish which transmission is blocked by which.










  
*Routing protocols and transmission schedules

We consider packet-oblivious routing protocols,
that is, protocols which only use their hardwired memory
and basic parameters of the stored packets assigned to them at injection time (such as
source, destination, injection time, route) in order to decide
which packet to send and when.

We distinguish between global-knowledge protocols
which can use topological information given as input, and
local-knowledge protocols that are given only
basic system parameters such as the number of links or the network's in-degree.

All our protocols will be based on pre-defined transmission
schedules, which will be circularly repeated — the properties
of these schedules will guarantee stability for certain
injection rates. These schedules will be different for different types of protocols, due to the available information based on which these schedules could be created.




  
*Adversaries


We model dynamic injection of packets by way of an adversarial model, in the spirit of similar approaches used in <cit.>. An adversary represents the users that generate packets to be routed in a given radio network. The constraints imposed on packet generation by the adversary allow considering worst-case performance of deterministic routing algorithms handling dynamic traffic.

Over time, an adversary injects packets to some nodes. The adversary decides on a path a packet has to traverse upon its injection. Our task is to develop a packet-oblivious routing protocol such that the network remains stable; that is, the number of packets simultaneously queued is bounded by a constant in all rounds.

Since an unbounded adversary can exceed the capability of a network to transmit messages, we limit its power in the following way:
for any time window of any length T, the adversary can inject packets (with their paths) in such a way that each link is traversed by at most ρ· T + b packets, for some 0≤ρ≤ 1 and b ∈ℕ^+. We call such an adversary a (ρ, b)-adversary.





§ SELECTORS AS TRANSMISSION SCHEDULERS



In this section, we introduce a family of combinatorial structures, widely called selectors <cit.>, that are the core of the deterministic routing algorithm presented in Section <ref>. In short, we will use specific type of selectors to provide a set of transmission schedules that assure stability when combined with suitable queuing policies.
 

There are many different types of selectors, with the more general one being described below:



Given integers k, m and n, with 1 ≤ m ≤ k ≤ n, we say that a boolean matrix M with t rows and n columns is a (n, k, m)-selector if any submatrix of M obtained by choosing k out of n arbitrary columns of M contains at least m distinct rows of the identity matrix I_k.  The integer t is referred as the size of the (n, k, m)-selector.



In order to use selectors as transmission schedules, the parameter n is intended to refer to the number of nodes in the network, k refers to the maximum number of nodes that can compete to transmit (i.e., k=Δ+1, where Δ is the maximum degree of the network), and m refers to the number of nodes that are guaranteed to successfully transmit during the t-round schedule. Therefore, each column of the matrix M is used to define the whole transmission schedule of each node. Rows are used to decide which nodes should transmit at each time slot: In the i-th time slot, node v will transmit iff M_i,v = 1 (and v has a packet queued);  the schedule is repeated after each t time slots.


Taking into account the above-mentioned approach, selectors may be used to guarantee that during the schedule, every node will successfully receive some messages. 

A (n,k,1)-selector guarantees that, for each node, one of its neighbors will successfully transmit during at least 1 round per schedule cycle (that is, that node will successfully receive at least one message). However, whereas the above use of selectors is helpful in broadcasting (since there is progress every time any node receives a message from a neighbor), it happens that many neighbors may have something to send, but only one of them has something for that node. Therefore, the above presented selector guarantees that each node will receive at least one message, but not necessarily will receive the one addressed to it.

A (n,k,k)-selector (which is known as strong selector <cit.>) guarantees that every node that has exactly k neighbors will receive a message from each one of them. However, it has been shown that its size t=Ω(min{n, (k^2 / log k) log n}). This means that k packets will be received, but during a long amount of time.

In order to solve the above mentioned problems with known selectors, now we introduce a new type of selectors, which we call universally strong. Namely, a (n,k,ϵ)-universally-strong selector of length t guarantees that every node will receive ϵ· t /k successful messages from every neighbor during t rounds. More formally:





A (n,k,ϵ)-universally-strong selector 𝒮 is a family of t sets T_1,…,T_t⊆[n] such that for every set A⊆[n] of at most k elements and for every element a ∈ A there exist at least ϵ· t/k sets T_i ∈𝒮 such that T_i ∩ A = {a}.







 §.§ Universally strong selectors of polynomial size


Clearly, universally strong selectors make sense provided they exist and their size is moderate. In the next theorem, we prove that, for any ϵ≤ 1/e, there exists a (n,k,ϵ)-universally-strong selector of polynomial size. 




For any ϵ≤ 1/e, there exists a (n,k,ϵ)-universally-strong selector of size O(k^2 ln n).



The proof relies on the probabilistic method.

Consider a random matrix M with t rows and n columns, where M_i,j = 1 with probability p and M_i,j = 0 otherwise. Given a row i and columns j_1,…, j_k, the probability that M_i, j_1=1 and M_i,j_2 = … = M_i,j_k = 0 (i.e., that node j_1's transmission is not interrupted by  nodes j_2,…,j_k in round i) is P = p(1-p)^k-1 and is maximized with p=1/k. In further considerations, we use matrix M generated with p=1/k.

Given columns C= {j_1,…, j_k}, let X(C) be the number of “good” rows i such that M_i, j_1=1 and M_i,j_2 = … = M_i,j_k = 0.

We will use the following Chernoff bound: 

    Pr[X(C) ≤ (1-δ)E[X(C)]] ≤ exp(-E[X(C)]δ^2/2)

 for  0 ≤δ≤ 1. 

Using E[X(C)]=Pt and δ = (kP-ϵ)/(kP), we obtain:

    Pr[X(C) ≤ϵ t / k] ≤ exp(-Ptδ^2/2).


Consider a “bad” event ℰ such that for at least one set of columns of size at most k, there are few good rows. More specifically, X(C) ≤ϵ t/k for at least one set of columns C, where |C| = k. The probability R of event ℰ happening fulfills the following inequality:

    R ≤  knk exp(-Ptδ^2/2).


Therefore R < 1 if 

    exp(-Ptδ^2/2) < 1/ [knk]


    -Ptδ^2/2 < -ln(knk)


    Pt(kP-ϵkP)^2/2 > ln(knk)


Let c=kP. Using nk≤(nek)^k, provided c ≠ϵ, we obtain the following:

    t(c-ϵ)^2/(2ck) > ln k + ln(nek)^k


    t > [2ck ln k + 2ck^2 ln(nek)] / (c-ϵ)^2


Therefore, as long as 0 ≤δ = c-ϵ/c≤ 1 (so that we can use the Chernoff bound) and ϵ≠ c, the probability of generating a random matrix M such that event ℰ occurs is less than 1. Thus, there exists a matrix M such that, for every set of k columns j_1,…, j_k, there are at least ϵ t/k rows such that M_i, j_1=1 and M_i,j_2 = … = M_i,j_k = 0. Trivially, such matrix M guarantees the above property for any set of at most k columns. Hence, M represents a 
(n,k,ϵ)-universally-strong selector, provided that ϵ < c = kP. Next, we calculate which values of ϵ fulfill that inequality.


Consider a sequence a_i = (1+1/i)^i. a_i is known as a lower bound on the Euler's number e (i.e., ∀ i   a_i < e). Note that c = kP = (1-1/k)^k-1 = 1/a_k-1 > 1/e for all k ≥ 2. This implies that any ϵ≤ 1/e fulfills the requirement of δ > 0 and results in the existence of a (n,k,ϵ)-universally-strong selector.






 §.§ Obtaining  universally strong selectors of polynomial size in polynomial time



In the proof of Theorem <ref>, we have introduced a family of universally strong selectors of polynomial size. However, obtaining them by derandomizing would be very inefficient  (all the approaches we know are, at least, exponential in n). Here, we present an algorithm, which we call Poly-Universally-Strong, that computes universally strong selectors of polynomial size in polynomial time (they only have slightly lower values of ϵ comparing to the existential result in Theorem <ref>).






The algorithm, whose code is shown in Figure <ref>, has to be executed by each node in the network taking the same polynomials, so that all nodes will obtain exactly the same matrix that defines the transmission schedule.










The next theorem shows that, indeed, it constructs a (n,k,ϵ)-universally-strong selector of polynomial size with ϵ= 1/(4 log_k n). 



Poly-Universally-Strong constructs (by using c=2) a (n,k,ϵ)-universally-strong selector of size 4 · k^2 ·⌈log_k n ⌉^2 with ϵ = 1/(4 log_k n). 



First, note that two polynomials P_i and P_j of degree d with i ≠ j, can have equal values for at most d different arguments. This is because they have equal values for arguments x for which P_i(x) - P_j(x)=0. However, P_i - P_j is a polynomial of degree at most d, so it can have at most d zeroes. So, P_i(x) = P_j(x) for at most d different arguments x.

Take any polynomial P_i and any k polynomials P_j still represented in M (so excluding columns/polynomials removed from consideration in step <ref>). There are at most k · d different arguments where one of the k polynomials can be equal to P_i. So, for q-k · d different arguments, the values of the polynomial P_i are unique. Therefore, if we look at rows with 1 in column i of matrix M (there are q of those rows, one for each argument), at least q-k · d of them have 0s in chosen k columns. Since there are q^2 rows, so a fraction (q-k · d)/q^2 of rows have the desired property (i.e., there is value 1 in column i and value 0 in the chosen k columns):


    q-k · dq^2 = (c-1) · k · d(c · k · d)^2 = c-1c^2 · k · d≜ f(c)  .


Let us find the value of c that maximizes the function f. To do it, we compute its differential 


    f'(c) = (c-1c^2 · k · d)' = 1·(c^2 · k · d)-(c-1)· k · d · 2cc^4 · k^2 · d^2 =
 

    = -c^2 · k · d + 2c · k · dc^4 · k^2 · d^2 = -c + 2c^3 · k · d.
 

Thus, f'(c)=0 for c=0 or c=2. The value c=2 maximizes f, giving 
f(c)≤ f(2) = 1/(4k · d) = 1/(4k ·log_k n).

Therefore, we can construct a (n,k,ϵ)-universally-strong selector with ϵ = f(2) · k = 1/(4d) = 1/(4 log_k n) of length 4k^2 ·⌈log_k n ⌉^2 (which means that an f(2) = 1/(4k ·log_k n) fraction of the selector's sets have the desired property).








§ A LOCAL-KNOWLEDGE ROUTING ALGORITHM



In this section, we introduce a local-knowledge packet-oblivious routing algorithm that makes use of the family of  universally strong selectors introduced in Section <ref> as transmission schedules (i.e., the time instants when packets stored at each one node must be transmitted to a receiving node). As it has been mentioned previously, local-knowledge routing algorithms work without using any topological information, except for maybe some network's features that do not require full knowledge of its topology. In our particular case, that will consists of some upper bounds on the number of links and on the network's degree.

The code of the proposed algorithm, which we call USS-plus-Alg, is shown in Figure <ref>. Given a graph G with a number of links bounded by m, and an in-degree of its conflict graph H  (which we denote as Δ_in^H) bounded by Δ≥ 1, it uses a (m,Δ+1,ϵ)-universally-strong selector as a schedule: assuming the selector is represented by matrix M with t rows, each link z ∈ E_G will transmit at time i iff M_i  t, z=1. Notice that here each link is assumed to have an independent queue, and therefore they will act as a sort of “nodes” (in terms of selectors, such as it has been stated in the previous section). This means that each individual link will have its own schedule. 







 §.§ The USS-plus-LIS algorithm


Next, we show that  the USS-plus-LIS algorithm (i.e., the  USS-plus-Alg algorithm where Alg is the Longest-In-System scheduling policy), guarantees stability, provided a given packets' injection admissibility condition is fulfilled. But first, we define what is a (ρ',T)-frequent schedule.



A (ρ,T)-frequent schedule for graph G is an algorithm that decides which links of graph G transmit at every round in such a way that each link is guaranteed to successfuly (without radio network collisions) transmit at least ρ· T times in any window of length T (provided at least ρ· T packets await for transmission at the link at the start of the window).



At this point, we note that the transmission schedules provided by our universally strong selectors can be seen as (ρ,T)-frequent schedules. 


We now proceed with the main result in this section.




Given a network G, the USS-plus-LIS algorithm is stable against any (ρ,b)-adversary, for ρ < ϵ/Δ+1.


Let us take any arbitrary link z∈ E_G and consider the set of all other links that conflict with link z, of which there are at most Δ. This means that there exist at least ϵ·  t/(Δ+1) rows i in M such that M_i  t ,z=1 and M_i  t,c_1 = … = M_i  t,c_j = 0. Therefore, at time i, link z will transmit a message, and no link that conflicts with the link z will transmit. This guarantees that each link will successfully transmit, at least, ϵ· t/(Δ+1) messages during any schedule of length t (i.e., we obtained a (ϵ/(Δ+1),t)-frequent schedule 𝒮). Then, we can apply the result Lemma <ref>  in the Appendix <ref> to deduce that such an algorithm is stable against any (ρ,b)-adversary, where ρ < ϵ/Δ+1. 


By using the selectors provided by the  Poly-Universally-Strong algorithm in USS-plus-LIS, we have the following result:


Given a network G, the USS-plus-LIS algorithm using a universally strong selector computed by the Poly-Universally-Strong algorithm is a stable algorithm against any (ρ,b)-adversary, for ρ < 1/4(Δ+1)log_Δ+1m.



If instead of the selectors provided by the Poly-Universally-Strong algorithm, we use a selector from Theorem <ref>, we have that:



Given a network G, there exists a universally strong selector that, used in the USS-plus-LIS algorithm, provides a stable algorithm against any (ρ,b)-adversary, for ρ < 1/e · (Δ+1).






























As it can be readily seen, the USS-plus-LIS algorithm for a network G requires some knowledge of the value of the in-degree of its conflict graph H (i.e., of Δ_in^H). In order to obtain H it is necessary to gather the whole topology of G.   However, as the next lemma shows, Δ_in^H can be bounded by the in-degree of the network G (denoted Δ_G).



Δ_in^H ≤Δ_G^2 + Δ_G -1, provided Δ_G >0.


If Δ_in^H=0, then the lemma is trivially true. Otherwise, consider a vertex e in H of maximum in-degree deg(e) = Δ_in^H. Since Δ_in^H ≠ 0, there is at least one edge (e',e) ∈ H such that, in G,  e cannot successfully transmit at the same time instant when e' transmits. Let us denote e=(u,v) and e'=(u',v'), and let us consider the different scenarios where e and e' may conflict.

Now, we make a case analysis regarding the possible conflicts in G (note that its in-degree is equal to its  out-degree, since G is symmetric):


  * u' = u and v' ≠ v (a node u=u' cannot transmit messages to 2 different receivers): there are at most Δ_G-1 such links e', given fixed link e.


  * u' = v (if u' transmits, it cannot listen at the same time): there are at most Δ_G such links e', given fixed link e.


  * u' ≠ u is a neighbor of v (i.e., v can hear both from u and u'): there are at most Δ_G-1 neighbors of v different than node u, and each of them has, at most, Δ_G different links. This gives Δ_G^2 - Δ_G such links e', given fixed link e.


Therefore, in overall there are at most (Δ_G-1) + Δ_G  + (Δ_G^2 - Δ_G) = Δ_G^2 + Δ_G -1 such links. 





The previous lemma shows that USS-plus-LIS can be seen as a local-knowledge algorithm, in the sense that it only requires some knowledge about two basic system parameters: the number of links and the network's in-degree.  In Section <ref>

we will also look at a solution that 

requires some  global-knowledge of G.




 §.§ Optimality of the USS-plus-LIS algorithm







In the next theorem, we show an impossibility result regarding routing algorithms, either based on selectors or not, that only make use of upper bounds on the number of links and on the network's degree.[To be strict, it is also necessary that each node v decides whether or not to an outgoing edge e=(u,v) should transmit at time t based on t and on the ID of node u.]




No routing algorithm that only makes use of upper bounds on the number of links and on the network's degree guarantees stability for all networks of degree at most Δ, provided the injection rate ρ = ω(1 / Δ^2).


See Appendix <ref>.


If we apply Theorem <ref> to USS-plus-LIS, then our goal  is to find how close to ρ = O(1/Δ_G^2) is its maximum injection rate for which it guarantees stability.

If we consider Theorem <ref> with Δ=Δ_in^H, we have that USS-plus-LIS can be stable for ρ = O(1/Δ_in^H). Furthermore, by Lemma <ref> we know that Δ_in^H can be as large as Θ(Δ_G^2). Then, we have that USS-plus-LIS  guarantees stability for ρ = O(1/Δ_G^2)  for all networks G, which matches the result in Theorem <ref>. This proves that the USS-plus-LIS algorithm is asymptotically optimal regarding the injection rate for which stability is guaranteed.



§ A GLOBAL-KNOWLEDGE ROUTING ALGORITHM



In this section, we introduce a global-knowledge packet-oblivious routing algorithm, which we call Coloring-plus-Alg, that is based on using graph coloring as transmission schedules. Such an algorithm  does not take into account any historical information. However, it has to be seeded by some information about the network topology (i.e., it is a global-knowledge routing algorithm).


Next, we show that  the Coloring-plus-LIS algorithm (i.e., the  Coloring-plus-Alg algorithm where Alg is the Longest-In-System scheduling policy), guarantees stability, provided a given packets' injection admissibility condition is fulfilled. 
 
 
Now, we proceed withe the main results in this section. But before we introduce the Coloring-plus-Alg routing algorithm, we state the following fact regarding the relationship between vertex coloring in a conflict graph, and its use as a transmission schedule.


[<cit.>]
	Vertex coloring of the conflict graph H(G) using x colors is equivalent to a schedule of length x that successfully transmits a packet via each directed link of network G. 




Note that every set of vertices of same color can be extended to a maximal independent set. The resulting family of independent sets is still a feasible schedule that guarantees no conflicts and is no worse than just coloring. In fact, it may allow some links to transmit more than once during the schedule, without increasing the length of the schedule.



Following, we show that coloring of a collision graph can be used to obtain a transmission schedule, where each link is guaranteed to regularly transmit.





A k-coloring of collision graph H provides a (1/k, k)-frequent schedule.



Let us split the vertices V_H of the graph H into sets V_H^i for i = 0,1,…,k-1, where every vertex in V_H^i is assigned the i-th color in the vertex coloring of graph H. Each link in the graph G is represented by one vertex in V_H, and therefore each link is assigned a unique color. According to the definition of the conflict graph H, if there is no edge (u,v) ∈ E_H, then links u ∈ E_G and v ∈ E_G can deliver their packets simultaneously, without a collision. Therefore, if at a given round t only links of (t  i)-th color transmit, then no collision occurs. Since each link has a color i ∈{0,1,…, k-1} assigned to it, then each link will successfully transmit a packet once each k consecutive rounds (as far as there is one packet waiting in its queue). 


Since χ(H)-coloring is an optimal coloring of graph H, we have the following result.



An optimal coloring of collision graph H provides a (1/χ(H), χ(H))-frequent schedule.


Once we have made it clear  that coloring of a collision graph can be used to obtain a transmission schedule, the code of the Coloring-plus-Alg algorithm is shown in Figure <ref>. 







 §.§ The Coloring-plus-LIS algorithm


Now, we show that Coloring-plus-LIS (i.e., the  Coloring-plus-Alg algorithm where Alg is the Longest-In-System scheduling policy), guarantees stability, provided a given packets' injection admissibility condition is fulfilled. 





The Coloring-plus-LIS algorithm is stable provided ρ < 1/χ(H), where χ(H) is the chromatic number of the conflict graph H of the network G.



We start the proof with referring to Corollary <ref>, which shows that coloring of a collision graph can be used to obtain a (1/χ(H),χ(H))-frequent schedule 𝒞.


Let us take any ρ = 1/χ(H) - ϵ, for some ϵ>0. We can use Lemma <ref> in the Appendix <ref> with 𝒮=𝒞 (so, ρ' = 1/χ(H)) to show that Coloring-plus-LIS is stable against any (ρ,b)-adversary in the radio network model. 



Observe that, contrary to the USS-plus-LIS protocol, the Coloring-plus-LIS algorithm requires global-knowledge of the structure of the graph: first, to construct H, and then to obtain its optimal coloring.



 §.§ Optimality of the  Coloring-plus-LIS algorithm


Now, we show that the  Coloring-plus-LIS algorithm is optimal regarding the injection rate, in the sense that no algorithm can guarantee stability for a higher injection rate that that provide by it.




No algorithm can be stable for all networks against a (ρ,b)-adversary for ρ>1/χ(H).


See Appendix <ref>.




 §.§ Global-knowledge vs local-knowledge  routing  protocols


Regarding the Coloring-plus-LIS protocol, by the Brooks' theorem <cit.>, we have that χ(H) ≤Δ^H +1. Let indeg^H(e) (and outdeg^H(e)) denote the indegree (outdegree) of node e in graph H. Recall that each edge in the network graph was replaced by two oppositely directed links. This means that, if a link e blocks outdeg^H(e) other links, then the opposite link e' is blocked by  indeg^H(e') = outdeg^H(e) links.

Therefore, Δ^H = Θ(Δ^H_in).

 Then, Theorem <ref> guarantees stability for ρ=O(1/Δ^H_in). 

On the other hand, from the result in Corollary <ref>, we have that USS-plus-LIS can only guarantee stability for ρ=O(1/(e ·Δ_in^H)). This implies that, by using the Coloring-plus-LIS protocol, it is possible to guarantee stability for a wider range of injection rates than by using the USS-plus-LIS protocol: namely, the injection rate for which stability is guaranteed is e times higher.









§ EXTENSION OF THE RESULTS TO OTHER SCHEDULING POLICIES



In this section, we show that the results obtained in sections <ref> and <ref> for routing combined with LIS (Longest In System) can be extended to other scheduling policies; namely, NFS (Nearest-From-Source), SIS (Shortest-In-System) and FTG (Farthest-To-Go). Indeed, for such a scheduling policies, Theorems <ref> and <ref> respectively parallelize the analogous results in Theorems <ref> and <ref> obtained for LIS.




Given a network G, the USS-plus-Alg algorithm, where Alg∈{NFS,SIS,FTG}, is stable against any (ρ,b)-adversary, for ρ < ϵ/Δ+1.


The proof is similar to that in Theorem <ref>. The only difference is that, instead of Lemma <ref>, we can apply the results in Lemma <ref> for NFS, SIS and FTG  (see Appendix <ref>) to deduce that such an algorithm is stable against any (ρ,b)-adversary, where ρ < ϵ/Δ+1. 




The Coloring-plus-Alg algorithm, where Alg∈{NFS,SIS,FTG}, is stable provided ρ < 1/χ(H), where χ(H) is the chromatic number of the conflict graph H of the network G.


We will reduce the packet scheduling in radio network problem to the problem of packet scheduling in the wired failure model <cit.>, in which these policies are known to be stable.

We start the proof with referring to Corollary <ref>, which shows that coloring of a collision graph can be used to obtain a (1/χ(H),χ(H))-frequent schedule 𝒞.

Let us take any ρ = 1/χ(H) - ϵ, for some ϵ>0. Now, we can use Lemma <ref> with 𝒮=𝒞 (so, ρ' = 1/χ(H)) and Alg∈{NFS,SIS,FTG} (with ρ”=1-ϵ) to show that we can build an algorithm that is stable against any (ρ,b)-adversary in the radio network model (see Appendix <ref>). Note that Coloring-plus-Alg is a special case of the algorithm built in the proof of Lemma <ref> with 𝒮=𝒞. Therefore Coloring-plus-Alg with Alg∈{NFS,SIS,FTG} is stable against any (ρ,b)-adversary in the radio network model.  





§ CONCLUSIONS AND FUTURE WORK



In this work, we studied the fundamental problem of stability in multi-hop wireless networks.

We introduced  a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies, we  propose a packet-oblivious routing algorithm which is working without using any global topological information, and guarantees stability for certain injection rates.  We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed.

Furthermore, we also introduced a packet-oblivious routing algorithm that guarantees stability for higher traffic. We also show that this protocol is optimal regarding the injection rate for which stability is guaranteed.
However, it needs to use some global information of the system topology. 



A natural direction would be to study other classes of protocols; for instance, when packets are injected without pre-defined routes. 
Universally strong selectors are interesting on its own right – finding more applications for them is a promising open direction.
Finally, exploring the reductions between various settings of adversarial routing could lead to new discoveries, as demonstrated in the last part of this work.


plain







§ AUXILIARY LEMMA



Here, we show that LIS, combined with a transmission schedule that guarantees a number of successful transmissions in some time interval, makes the resulting routing protocol stable (these lemmas  are adapted versions of analogous results about universal stability of the LIS protocol in wired network <cit.>).  



If there exists a (ρ',T)-frequent schedule 𝒮, then using LIS as the queueing policy guarantees stability of the resulting routing protocol against any (ρ, b)-adversary for ρ < ρ'.


Before we prove this lemma, we will introduce some additional notations and auxiliary lemmas.

Let L be the length of the longest route in the system. Let us denote by class i the set of packets injected during i-th window. A class i is said to be active during a window w if and only if at some time during window w there is some packet in the system of class i' ≤ i. 


Consider some packet p injected during window W_0, whose path crosses links e_1, e_2, …, e_L, in this order. We use W_i to denote the window, during which p crossed link e_i. Let c_w denote the number of active classes during window w. We define c = max_ w ∈ [W_0,W_L)  c_w. Then, we can bound the number of windows to deliver p.




    W_L - W_0 ≤1-(1-ρ/ρ')^L/ρ· T· (b-1) + c ·[1-(1-ρ/ρ')^L]  .





The packet p reaches link e_i for the first time in window W_i-1. Since p is in the system, during window W_i-1 all classes [W_0,W_i-1] are active. Therefore, according to the definition of c, there are at most c - (W_i-1 - W_0) active classes with packets older than packet p. Packets in those classes are the only packets that take priority over packet p on link e_i. The oldest such packet was injected during window w_first = W_0 - [c - (W_i-1 - W_0)] = W_i-1 - c. Since its injection, at most (W_0 - w_first) ·ρ· T + b = [c - (W_i-1 - W_0)] ·ρ· T + b packets older than p could be injected into the system. Therefore, there are at most [c - (W_i-1 - W_0)] ·ρ· T + b - 1 packets that will take priority over packet p on link e_i. Since each link transmits at least ρ' T times per window, the number of windows until p transgresses link e_i is at most

    W_i - W_i-1≤ρ· T · (c + W_0 - W_i-1) + b -1/ρ' · T .

Hence, 

    W_i ≤(1-ρ/ρ') W_i-1 + ρ/ρ'(c + W_0) + b-1/ρ' · T .


Therefore, solving the recurrence, we get:










    W_L   ≤   W_0 + c[ 1-(1-ρ/ρ')^L ] + 1-(1-ρ/ρ')^L/ρ· T (b-1),

which proves the lemma. 



Now we have a bound on how long packet p can be in the system, depending on value c. We will show that c is bounded by a constant, depending only on network and adversary parameters, i.e., L, ρ and b, and value ρ' from Lemma <ref>.




There are never more than 

    (b-1) ·1-(1-ρ/ρ')^L/(1-ρ/ρ')^L ·ρ· T

active classes in the system.


Let c' =(b-1) ·1-(1-ρ/ρ')^L/(1-ρ/ρ')^L ·ρ· T + 1/(1-ρ/ρ')^L. Assume, by contradiction, that a window w is the first window during which there are at least c'+1 active classes. Hence, at the end of window w-1, there is a packet q that was in the system for c' windows, and no more than c' classes were active until the end of window w-1.

According to Lemma <ref>, packet q is delivered in at most 

    c'[ 1-(1-ρ/ρ')^L ] + 1-(1-ρ/ρ')^L/ρ· T (b-1) =
 

    = c'[ 1-(1-ρ/ρ')^L ] + (c' - 1/(1-ρ/ρ')^L) · (1-ρ/ρ')^L =


    = c' - 1

windows, which gives a contradiction.


Now that we have proven that any packet p spends bounded time in the system, we can prove Lemma <ref>.


In Lemma <ref>, it has been shown that c is bounded. By Lemma <ref>, this implies that W_L - W_0 is also bounded. This result guarantees that each packet spends a bounded time in the system. That means that such system is stable against any (ρ,b)-adversary, provided that ρ' > ρ, which completes the proof of the lemma. 





§ PROOF OF THEOREM <REF>




*the:impossibilityTheorem <ref>

\beginthe:impossibility
No routing algorithm that only makes use of upper bounds on the number of links and on the network's degree guarantees stability for all networks of degree at most Δ, provided the injection rate ρ = ω(1 / Δ^2).
\endthe:impossibility

Assume, to the contrary, that there exists a routing algorithm ALG such that, given any network of which it is aware of both its number of links and its degree, it guarantees that there are no more than Q_max packets in the system at all times against all adversaries with injection rate ρ = ω(1 / Δ^2).
Note that Q_max could be a function on ρ,n, but a constant with respect to time.





Consider a complete Δ-regular tree T of depth 2, rooted at r. Let us denote the nodes at distance 1 from r as x_i, for i=1,…,Δ and leaves adjacent to x_i as l_i^j for j=1,…,Δ-1. Let us generate a family  of trees T_i,j as follows: swap the root r of T with leaf l_i,j of T (see Figure <ref>).

Note that edges (x_i,r) and (x_i,l_i,j) swapped places, edges (x_k,r) for k≠ i were removed and in their place edges (x_k,l_i,j) appeared. Other edges, i.e., (x_k, l_k,a) for a=1,…,Δ-1 and (x_i, l_i,b) for b≠ j, remain in the same place in both T and T_i,j.

Note that edges (x_k, l_k,a) (for k=1,…,Δ and a=1,…,Δ-1) exist in every tree in ∪{T}. Let us denote the set of these edges as E.

Consider an adversary A that, starting from round 0, injects 1 packet into every edge outgoing from x_i (for i=1,…,Δ) every 1 / ρ rounds. Such adversary is a (ρ,1)-adversary in each tree in ∪{T}.

Note that each packet injected into an edge incoming into the root of a tree T' ∈∪{T} cannot be simultaneously transmitted with any other packet injected by A. In particular, it cannot be simultaneously transmitted with any other packet on edges in E.

Consider a time prefix of length τ rounds. Consider any edge e ∈ E. Edge e is incident to the root in some tree T' ∈∪{T}. ALG must successfully transmit from e in T' in at least ρτ - Q_max rounds during the considered prefix, since ALG is stable. This means that all other edges in E must not transmit in those rounds. Since there are Δ (Δ-1) possible choices of edge e ∈ E, each choice requiring all other edges in E not to transmit in ρτ - Q_max rounds, we get that each edge in E must not transmit in Δ (Δ-1) · (ρτ - Q_max) rounds and must transmit in ρτ - Q_max rounds, for a total of  Δ^2 · (ρτ - Q_max) rounds in the prefix of length τ. For ρ = ω(1/Δ^2), we can choose τ such that Δ^2 · (ρτ - Q_max) > τ, which gives us a contradiction. 






§ PROOF OF THEOREM <REF>



*theorem:optimality_coloringTheorem <ref>

\begintheorem:optimality_coloring
No algorithm can be stable for all networks against a (ρ,b)-adversary for ρ>1/χ(H).
\endtheorem:optimality_coloring

Let us consider a network graph G on n nodes that is a clique. For such network, the collision graph H is also a clique, since each link is in conflict with each other link. Collision graph H has n^2-n vertices and requires n^2-n colors to be colored, i.e., χ(H) = n^2-n.

Consider a (1/χ(H) + ε, 2)-adversary for some ε>0 that after every χ(H) rounds injects one packet into each link (starting in round 0) and simulateously after each 1/ε rounds injects another packet into each link (starting in round 0). Therefore, in any prefix of T = k ·χ(H) rounds for k ∈ℕ, the adversary injects (k+1) + ⌊ T/ε⌋+1 packets into each link, i.e., I=(k + ⌊ T/ε⌋ + 2) · (n^2-n) packets into the system.

On the other hand, since G is a clique, any algorithm can successfully transmit at most 1 packet per round in the entire network. Therefore, in T = k ·χ(H) = k · (n^2-n) rounds at most k · (n^2-n) packets can be transmitted. So, at the end of a prefix of length T, there are at least I - k · (n^2-n) = (⌊ T/ε⌋ + 2) · (n^2-n) packets remaining in the system. For T approaching infinity, the number of packets remaining in the queues grows to infinity. This means that the queues are not bounded and the algorithm is not stable.






§ REDUCTION TO THE FAILURE MODEL



First, let us explain the (wired) failure model <cit.>. Given is a network graph G. A (ρ,b)-adversary in the failure model injects paths (packets) into G and generates failures in such a way that in any interval I the following inequality holds:

    Arr_e(I) + Fail_e(I) ≤ρ |I| + b,

where Arr_e(I) is the number of packets injected during interval I that pass through edge e and Fail_e(I) is the number of failures on edge e generated during interval I. Each link e that has some packets waiting in its queue can transmit a packet in every round, i.e., there are no collisions between edges.

There are known stable algorithms for packet scheduling in the failure model, such as NFS (Nearest-From-Source), SIS (Shortest-In-System), or FTG (Farthest-To-Go) against (ρ, b)-adversary with any ρ < 1 <cit.>.



Suppose we have a stable algorithm Alg  against any (ρ”,b)-adversary ADV_fail in the failure model on graph G. Suppose we have a 
(ρ', T)-frequent schedule 𝒮.

Then we can build a stable algorithm 𝒮-Plus-Alg against any (ρ,b)-adversary ADV_RN in the radio network model on graph G, for any ρ such that ρ < ρ' and ρ”≥ 1+ρ-ρ'.


The stable algorithm in each round has two steps:


  * Determine which links transmit, according to a (ρ', T)-frequent schedule 𝒮 for some parameters ρ' and T,

  * Determine, for each link e, which packet awaiting in a queue of link e to transmit, according to Alg.


We can think of rounds when 𝒮 does not successfully transmit a packet via link e due to a collision as failures on link e in the failure model. 
Schedule 𝒮 guarantees that each link e has at most (1-ρ')T transmission blocked in any interval I of length T. This means that each link e has at most Fail_e(I) ≤ (1-ρ')T failures during I. Furthermore, ADV_RN can inject at most Arr_e(I) ≤ρ T + b packets passing through each edge e during I.

    Arr_e(I) + Fail_e(I) ≤ρ T + b +  (1-ρ')T = T(1+ρ-ρ') + b

Therefore, the graph G with packet arrivals from ADV_RN and failures being collisions generated by 𝒮 is an instance of the failure model with a
(1+ρ -ρ', b)-adversary. That means that using Alg to compute which packet to chose for each link at each round guarantees stability, provided ρ”≥ 1+ρ-ρ'.






