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

Y. Wang (1) , Gaogang Xie (1) , Mohamed Ali Kaafar (2)

1 ICT - Key Lab of Computer System and Architecture, Institute of Computing Technology [Beijing]
2 PLANETE - Protocols and applications for the Internet

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).

Domaines: Réseaux et télécommunications [cs.NI]

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⟩