Graph theoretic expansion of Borei Cayley Graphs with an optimal and distributed routing algorithm
| Autor: | K. Wendy Tang, Dongsoo Kim, Eric Noel |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Dynamic Source Routing
Static routing Distance-vector routing protocol Theoretical computer science Link-state routing protocol Computer science Equal-cost multi-path routing Routing table Multipath routing Computer Science::Networking and Internet Architecture Astrophysics::Cosmology and Extragalactic Astrophysics Destination-Sequenced Distance Vector routing Topology |
| Zdroj: | IPCCC |
| DOI: | 10.1109/pccc.2012.6407762 |
| Popis: | In our previous work, we reported Borei Cayley Graphs (BCGs) have prominent properties such as outstanding topologlcal properties, ultrafast consensus speed and optimal routing algorithm. However, the network performance of BCGs Intensively relies on generating parameters p and k, where p Is a prime number and k Is a factor of p — 1. In this paper, we propose the Expanded BCGs (Er-BCGs) to theoretically expand BCGs to eliminate the dependence on the parameters with node ID space expansion and extended connection rule. The E∗-BCGs preserve outstanding topological properties of BCGs and enable nodes to be represented as Generalized Chordal Ring (GCR). Furthermore, the E∗-BCGs have class-level vertex transitivity which allows the networks viewed by vertices in the same class have an identical structure. Based on these properties, we present the class-level vertex transitive (CVT) routing algorithm for Er-BCGs. The CVT routing algorithm is an optimal, distributed algorithm and incorporates with the routing table which is generated by the GCR constant based routing table generation requiring a low size complexity of O{dk), where d is a node degree. To further improve the CVT routing efficiency, we provide the routing table folding scheme to reduce the number of routing table entries from Nd to Nd/n, where N is a network size and n is an expansion factor. In the routing simulation with All-to-All and All-to-M traffic patterns, Er-BCGs outperform the benchmark networks in reachability, end-to-end delay and the mean number of packets at node with a variety of packet generation ratios. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|