Sparse communication networks and efficient routing in the plane
| Autor: | David Peleg, Yehuda Hassin |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Static routing
Dynamic Source Routing Computer Networks and Communications Computer science business.industry Distributed computing Routing table Policy-based routing Theoretical Computer Science Computational Theory and Mathematics Routing domain Link-state routing protocol Hardware and Architecture Multipath routing Computer Science::Networking and Internet Architecture business Hierarchical routing Computer network |
| Zdroj: | Distributed Computing. 14:205-215 |
| ISSN: | 1432-0452 0178-2770 |
| Popis: | Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously. This approach is explored by considering the design of communication networks supporting efficient routing in the special case of points located in the Euclidean plane. The desirable network parameters considered include low degree and small number of communication links. The desirable routing parameters considered include small routing tables, small number of hops and low routing stretch. Two rather different schemes are presented, one based on direct navigation in the plane and the other based on efficient hierarchical tree covers. On a collection of n sites with diameter D, these methods yield networks with maximum degree O(logD) (hence a total of O(nlogD) communication links), coupled with routing schemes with constant routing stretch, O(logn logD) memory bits per vertex and routes with at most logn or logD hops. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink