𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Space-Efficiency for Routing Schemes of Stretch Factor Three

✍ Scribed by Cyril Gavoille; Marc Gengler

Book ID
102601456
Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
133 KB
Volume
61
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

We deal with deterministic distributed routing algorithms on arbitrary n-node networks. For each router, we want to minimize the amount of routing information that must be stored in order to implement the local routing algorithm, even if the names of the routers can be chosen in advance. We take also into account the length of the routing paths and consider the stretch factor, which is the maximum ratio between the length of the paths computed by the routing algorithm and the distance between the source and the destination. We show that there exists an n-node network on which every routing algorithm of stretch factor s<3 requires at least a total of 0(n 2 ) bits of routing information. We show a similar result for networks of diameter 2.

πŸ“œ SIMILAR VOLUMES

High accuracy difference schemes for a c
High accuracy difference schemes for a class of three space dimensional singular parabolic equations with variable coefficients
✍ R.K. Mohanty πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 617 KB

In this article, two-level implicit difference methods of O(k2+ h 4) using 19-spatial grid points for the solution of three space dimensional heat conduction equation and unsteady Navier-Stokes' equations in polar coordinates are proposed. Unconditionally stable ADI methods for the solution of the h