Graph Theory
[Pacharintanakul-Tipper-2009 (doi).]
Peera Pacharintanakul and David Tipper,
“Crosslayer Survivable Mapping in Overlay-IP-WDM Networks“,
The 7th IEEE International Workshop on the Design of Reliable Communication Networks (DRCN),
Washington DC, October 2009, 168–174
ResiliNets Keywords: survivability
Keywords: crosslayer survivable mapping, joint capacity allocation, multilayer networks, survivability
Abstract: “Survivability is a critical requirement for reliable services in any network. As the Internet moves towards a three layer architecture consisting of Overlay on top of IP on top of WDM-based networks incorporating the interaction between and among network layers is crucial for efficient and effective implementation of survivability. This paper highlights the challenges of providing survivability in three-layer networks and develops a novel approach crosslayer survivable mapping to offer such survivability in an efficient way. We investigate the impacts of overlay network dependency on lower layer network layout in terms of the capacity allocated to overlay paths. The results demonstrate the impact due to layer dependency that it is more severe than initially anticipated making it clear that single layer network design is inadequate to assure service guarantees and efficient capacity allocation.”
Notes:
[Sidhu-Nair-Abdallah 1991 (doi) .]
Deepinder Sidhu, Raj Nair, Shukri Abdallah,
"Finding disjoint paths in networks",
Proceedings of the conference on Communications architecture & protocols, 1991, pp. 43-51, Zurich, Switzerland
ResiliNets Keywords: routing, redundancy, node disjoint paths
Keywords: C.2 COMPUTER-COMMUNICATION NETWORKS; F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2 Nonnumerical Algorithms and Problems, Subjects: Computations on discrete structures; G.2 DISCRETE MATHEMATICS, G.2.2 Graph Theory, Subjects: Path and circuit problems
Abstract: "Routing is an important function implemented in computer communication networks. There has been extensive research interest in distributed algorithms for single path routing. In many instances, it is desirable to have multiple disjoint paths between pairs of nodes in a network. Multiple disjoint paths can increase the effective bandwidth between pairs of nodes, reduce congestion in a network and reduce the probability of dropped packets. This paper presents a distributed distance-vector algorithm that finds multiple disjoint paths to a destination. The algorithm includes the shortest path as one of the disjoint paths. We describe the algorithm, evaluate its performance using simulation and compare it with another disjoint-path routing algorithm. We conclude that our algorithm requires 3 to 4 times fewer messages to discover paths of comparable quality."
[Dall-Christensen-2008 (doi) .]
Jesper Dall and Michael Christensen
“Random Geometric Graphs”,
Physical Review E, vol.66, #1, July 2002
ResiliNets Keywords:
Keywords: Networks, percolation, phase transitions, random graphs, scaling, graph, bi-partitioning
Abstract: “We analyze graphs in which each vertex is assigned random coordinates in a geometric space of arbitrary dimensionality and only edges between adjacent points are present. The critical connectivity is found numerically by examining the size of the largest cluster. We derive an analytical expression for the cluster coefficient, which shows that the graphs are distinctly different from standard random graphs, even for infinite dimensionality. Insights relevant for graph bipartitioning are included.”
Notes:
