Optimal broadcasting in injured hypercubes using directed safety levels
✍ Scribed by Jie Wu
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 238 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Reliable communication in injured hypercubes with faulty links/nodes using directed safety levels is studied in this paper. In this approach, each node u in an n-dimensional hypercube (n-cube) is associated with a sequence of directed safety levels. A directed safety level associated with node u is an approximated measure of broadcast capability of performing optimal broadcasting from u in an ðn À 1Þ-subcube containing u: By optimal broadcasting, we mean that the broadcast message reaches each destination through a shortest path (i.e., the length of each path is equal to the Hamming distance between the source and destination). Directed safety levels are based on a special coding scheme generalized from Wu's safety level model and are calculated through n À 1 rounds of information exchanges and updates among neighboring nodes. In this model, fault information of nodes within distance-d is precisely represented to better capture link faults, whereas fault information of nodes outside distance-d is approximated as in the regular safety level model. Optimal broadcasting at node u is guaranteed if node u is globally safe, which is defined in terms of the directed safety levels associated with u: The directed safety level model with d ¼ 1 or d ¼ 2 has the same asymptotic complexity as the regular safety level model. Simulation results show a significant improvement in terms of optimal broadcast capability in injured hypercubes.