Abstract | ||
---|---|---|
In this paper the computational complexity of finding packet routing schemes provably efficient with respect to the end-to-end delay is studied. The attention is focused on polynomial-time algorithms able to optimize the end-to-end delay when the number of packets in the network increases, and the number of packets that can be accepted in the network in order to keep the end-to-end delay within a constant value. In particular, the hardness of approximating in polynomial time both the minimum end-to-end delay and the maximum number of accepted packets within any sublinear error in the number of packets is proved. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1016/S0304-3975(97)00198-9 | Theor. Comput. Sci. |
Keywords | Field | DocType |
efficient delay routing | Topology,Equal-cost multi-path routing,Dynamic Source Routing,Triangular routing,Computer science,Static routing,Network packet,Parallel computing,DSRFLOW,Routing table,Elmore delay | Journal |
Volume | Issue | ISSN |
196 | 1-2 | Theoretical Computer Science |
Citations | PageRank | References |
5 | 0.45 | 16 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Miriam di Ianni | 1 | 144 | 17.27 |