Abstract | ||
---|---|---|
We address the problem of deciding whether a given network is stable in the Adversarial Queueing Model when considering farthest-from-source (FFS) as the queueing policy to schedule the packets through its links. We show a characterisation of the networks which are stable under FFS in terms of a family of forbidden subgraphs. We show that the set of networks stable under FFS coincide with the set of universally stable networks. Since universal stability of networks can be checked in polynomial time, we obtain that stability under FFS can also be decided in polynomial time. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.ipl.2004.02.016 | Information Processing Letters |
Keywords | Field | DocType |
queueing policy,adversarial queueing model,polynomial time,universal stability,Adversarial Queueing Model,stable network | Discrete mathematics,Combinatorics,Lien,Information processing,Polynomial,Network packet,Queueing theory,Time complexity,Numerical stability,Mathematics,Adversarial system | Journal |
Volume | Issue | ISSN |
90 | 5 | 0020-0190 |
Citations | PageRank | References |
3 | 0.41 | 5 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
cristobalina rodriguez alvarez | 1 | 3 | 0.41 |
maria j blesa | 2 | 41 | 3.32 |
Josep Díaz | 3 | 65 | 7.03 |
andrey velasquez fernandez | 4 | 3 | 0.41 |
M. Serna | 5 | 31 | 4.28 |