Abstract | ||
---|---|---|
Compact routing protocols are used to reduce the routing table size at the cost of the optimality of the computed (shortest) paths. Interval Routing ( IR ) is a compact routing scheme, where no des are labeled with unique integers from a continuous range, and the outgoing arcs in every node are labeled with a set of intervals forming a partition of the range. Pivot Interval Routing(PIR) [19, 101] applies IR to an arbitrary weighted network such that the stretch factor (the ratio between the length of a path induced by PIR and the actual distance betwe en theno des) is at most five and three on the average. A self-stabilizing system has the ability to automatically recover from transient faults in finite time [5, 6]. We present a self-stabilizing PIR (SPZR). Our algorithm, with no knowledge of the network layout, tolerates node/link addition and/or failur e, and builds correct routing tables in o(d\sqrt {(a1 + \log n^{} )}) time units (d is the network diameter and n is the maximum number of nodes). The stretch factor and the average stretch factor are preserved. Each node builds its own routing table of size o(n^{1/2} \log ^{3/2} n + \Delta \log n) bits (where \Delta is the node degree) with a total number of o(n^{3/2} \log ^{3/2} n + n\Delta \log (n)) bits for the whole network (\Delta is the maximum degree of a node in the network). |
Year | DOI | Venue |
---|---|---|
2005 | 10.1109/ISPAN.2005.79 | ISPAN |
Keywords | DocType | ISBN |
compact routing protocol,compact routing scheme,stretch factor,arbitrary weighted network,self-stablizing pivot interval routing,network diameter,correct routing table,log n,general networks,own routing table,network layout,node degree,routing table,cost function,tin,computer science,network topology,intelligent networks,routing protocols,computational complexity,computer networks,labeling | Conference | 0-7695-2509-1 |
Citations | PageRank | References |
2 | 0.42 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Doina Bein | 1 | 103 | 21.64 |
Ajoy K. Datta | 2 | 369 | 35.83 |
Vincent Villain | 3 | 544 | 45.77 |