25-08-2014, 12:13 PM
Single Failure Resiliency In Greedy Routing Seminar Report
Single Failure Resiliency.pptx (Size: 420.27 KB / Downloads: 12)
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.
GREEDY ROUTING
Every node in the network is assigned a coordinate in a metric space.
Network topology is embedded in a geometric space
To reach a destination, each node forwards the packet to the neighbor that is closest to the destination in the space
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
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
Nodes numbering
Required steps of a sample node numbering
1) First the spanning tree of the network is constructed.
2) The neighbors of a node in the spanning tree of the network are numbered from 1 to d.
3) Each node can calculate the coordinates of its children by adding the integer number assigned to each child after the last non-zero field in its own coordinate.
The number of non-zero fields in a coordinate represents the
level of that node in the spanning tree of the network
Recovery techniques in greedy routing
Change in the connectivity of spanning tree might affect the greedy embedding causing the packets to reach a dead end or link/node failure
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.
NFR contd
The forwarding process upon facing a node failure:-
1) Select the correct backup path based on the destination coordinate (the one which leads to the direction of the destination, use tree numbering).
2) Add the hub nodes corresponding to that backup path to the header of the packet.
3) Greedy route to the first hub, second hub and so on until reaching the end node of the backup path.
4) Resume greedy routing to the destination
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.