20-06-2014, 04:20 PM
Single Failure Resiliency In Greedy Routing
[attachment=65120]
INTRODUCTION.
Greedy routing can be considered as an alternative to IP routing for future Internet.
Greedy routing is based on greedy embedding.
Greedy embedding based on the spanning tree of the network.
Recovery techniques to cope with network failures in greedy routing without the re-calculation of the coordinates.
Guarantee single failure resiliency.
SPANNING TREE
Suppose you have a connected undirected graph,
Connected: every node is reachable from every other node.
Undirected: edges do not have an associated direction.
...then a spanning tree of the graph is a connected subgraph in which there are no cycles.
FACE ROUTING
Face routing is one solution to cope with local minima or void in greedy routing.
Use face routing to bypass the void and reach a node which greedy routing can be resumed
Face routing techniques suffer of two types of issues:
i) Local graph parts must be planar, and
ii) Cannot always be guaranteed
to be found
Why space is hyperbolic?
Greedy routing is always successful in hyperbolic space.
Nodes in real complex networks can often be classified hierarchically.
Hierarchies are tree-like structures.
Hyperbolic geometry is the geometry of tree-like structures.
Formally: trees embed almost isometrically in hyperbolic spaces, not in Euclidean ones.
Greedy embedding based on the spanning tree
Local minima -drawback of greedy routing.
Simple greedy embedding (numbering) of nodes which is based on the spanning tree of the network-solution
LFR contd…
Select the node with maximum degree as the root node.
2) Search for the shortest cycle which includes the root.
3) Determine the paths for the blue and red trees by traversing the cycle/path in two opposite directions.
4) Search for new paths/cycles (shortest), starting from a visited node closer to the root.
5) Go to step 3.
Two colored trees are divided in to primary and secondary tree.
To recover a tree-edge failure- distinguish it in to upward and downward failure.
Further routing is lead to the destination of the packet
CONCLUSION
Here discussed two recovery methods for single link and node failure in greedy routing and also explained a simple embedding based on the spanning tree of the network in order to perform the greedy routing. In the scenario of a link failure, backup trees were used and for node failure scenarios, backup paths were considered. Using these techniques, there is no need to re-calculate the coordinates of the nodes.
[attachment=65120]
INTRODUCTION.
Greedy routing can be considered as an alternative to IP routing for future Internet.
Greedy routing is based on greedy embedding.
Greedy embedding based on the spanning tree of the network.
Recovery techniques to cope with network failures in greedy routing without the re-calculation of the coordinates.
Guarantee single failure resiliency.
SPANNING TREE
Suppose you have a connected undirected graph,
Connected: every node is reachable from every other node.
Undirected: edges do not have an associated direction.
...then a spanning tree of the graph is a connected subgraph in which there are no cycles.
FACE ROUTING
Face routing is one solution to cope with local minima or void in greedy routing.
Use face routing to bypass the void and reach a node which greedy routing can be resumed
Face routing techniques suffer of two types of issues:
i) Local graph parts must be planar, and
ii) Cannot always be guaranteed
to be found
Why space is hyperbolic?
Greedy routing is always successful in hyperbolic space.
Nodes in real complex networks can often be classified hierarchically.
Hierarchies are tree-like structures.
Hyperbolic geometry is the geometry of tree-like structures.
Formally: trees embed almost isometrically in hyperbolic spaces, not in Euclidean ones.
Greedy embedding based on the spanning tree
Local minima -drawback of greedy routing.
Simple greedy embedding (numbering) of nodes which is based on the spanning tree of the network-solution
LFR contd…
Select the node with maximum degree as the root node.
2) Search for the shortest cycle which includes the root.
3) Determine the paths for the blue and red trees by traversing the cycle/path in two opposite directions.
4) Search for new paths/cycles (shortest), starting from a visited node closer to the root.
5) Go to step 3.
Two colored trees are divided in to primary and secondary tree.
To recover a tree-edge failure- distinguish it in to upward and downward failure.
Further routing is lead to the destination of the packet
CONCLUSION
Here discussed two recovery methods for single link and node failure in greedy routing and also explained a simple embedding based on the spanning tree of the network in order to perform the greedy routing. In the scenario of a link failure, backup trees were used and for node failure scenarios, backup paths were considered. Using these techniques, there is no need to re-calculate the coordinates of the nodes.