FPC: A self-organized greedy routing in scale-free networks

Y. Wang 1 Gaogang Xie 1 Mohamed Ali Kaafar 2, *
* Corresponding author
2 PLANETE - Protocols and applications for the Internet
Inria Grenoble - Rhône-Alpes, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we propose FPC -- a Force-based layout and Path Compressing routing schema for scale-free network. As opposed to previous work, our algorithm employs a quasi-greedy but self-organized and configuration-free embedding method force based layout. In order to eliminate the negative influences of the "quasi" greedy property, we present a two-stage routing strategy, which combines the greedy routing with source routing. The greedy routing path discovered and compressed in a first stage is then used by the following source-routing stage. The detailed evaluation based on synthetic topologies as well as on a real Internet AS topology shows that: FPC guarantees 100% delivery rates on scale-free networks with an attractive low stretch (e.g. less than 1.2 on the real Internet AS topology).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00748157
Contributor : Mohamed Ali Kaafar <>
Submitted on : Monday, November 5, 2012 - 6:42:51 AM
Last modification on : Wednesday, April 11, 2018 - 1:54:07 AM

Identifiers

Collections

Citation

Y. Wang, Gaogang Xie, Mohamed Ali Kaafar. FPC: A self-organized greedy routing in scale-free networks. ISCC 2012 - 17th IEEE Symposium on Computers and Communications, Jul 2012, Cappadocia, Turkey. pp.000102--000107, ⟨10.1109/ISCC.2012.6249275⟩. ⟨hal-00748157⟩

Share

Metrics

Record views

161