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

Yonggong Wang; Gaogang Xie; Mohamed Ali Kaafar

doi:10.1109/ISCC.2012.6249275

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

Yonggong Wang^*, Gaogang Xie, Mohamed Ali Kaafar

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

4 Citations (Scopus)

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

Original language	English
Title of host publication	2012 IEEE Symposium on Computers and Communications, ISCC 2012
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	102-107
Number of pages	6
ISBN (Print)	9781467327121
DOIs	https://doi.org/10.1109/ISCC.2012.6249275
Publication status	Published - 2012
Externally published	Yes
Event	17th IEEE Symposium on Computers and Communication, ISCC 2012 - Cappadocia, Turkey Duration: 1 Jul 2012 → 4 Jul 2012

Conference

Conference	17th IEEE Symposium on Computers and Communication, ISCC 2012
Country/Territory	Turkey
City	Cappadocia
Period	1/07/12 → 4/07/12

Keywords

greedy routing
path compression
scale-free network
self-organized

Access to Document

10.1109/ISCC.2012.6249275

Cite this

@inproceedings{08f139ade3704a9aae2c6dde91ebd593,

title = "FPC: A self-organized greedy routing in scale-free networks",

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

keywords = "greedy routing, path compression, scale-free network, self-organized",

author = "Yonggong Wang and Gaogang Xie and Kaafar, {Mohamed Ali}",

year = "2012",

doi = "10.1109/ISCC.2012.6249275",

language = "English",

isbn = "9781467327121",

pages = "102--107",

booktitle = "2012 IEEE Symposium on Computers and Communications, ISCC 2012",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "17th IEEE Symposium on Computers and Communication, ISCC 2012 ; Conference date: 01-07-2012 Through 04-07-2012",

}

Wang, Y, Xie, G & Kaafar, MA 2012, FPC: A self-organized greedy routing in scale-free networks. in 2012 IEEE Symposium on Computers and Communications, ISCC 2012., 6249275, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, pp. 102-107, 17th IEEE Symposium on Computers and Communication, ISCC 2012, Cappadocia, Turkey, 1/07/12. https://doi.org/10.1109/ISCC.2012.6249275

FPC: A self-organized greedy routing in scale-free networks. / Wang, Yonggong; Xie, Gaogang; Kaafar, Mohamed Ali.
2012 IEEE Symposium on Computers and Communications, ISCC 2012. Piscataway: Institute of Electrical and Electronics Engineers (IEEE), 2012. p. 102-107 6249275.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - FPC

T2 - 17th IEEE Symposium on Computers and Communication, ISCC 2012

AU - Wang, Yonggong

AU - Xie, Gaogang

AU - Kaafar, Mohamed Ali

PY - 2012

Y1 - 2012

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

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

KW - greedy routing

KW - path compression

KW - scale-free network

KW - self-organized

UR - http://www.scopus.com/inward/record.url?scp=84866604948&partnerID=8YFLogxK

U2 - 10.1109/ISCC.2012.6249275

DO - 10.1109/ISCC.2012.6249275

M3 - Conference proceeding contribution

AN - SCOPUS:84866604948

SN - 9781467327121

SP - 102

EP - 107

BT - 2012 IEEE Symposium on Computers and Communications, ISCC 2012

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway

Y2 - 1 July 2012 through 4 July 2012

ER -

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this