Independent Directed
Acyclic Graphs for Resilient Multipath Routing
ABSTRACT:
In order to
achieve resilient multipath routing, we introduce the concept of independent
directed acyclic graphs (IDAGs) in this paper. Link-independent
(node-independent) DAGs satisfy the property that any path from a source to the
root on one DAG is link-disjoint (node-disjoint) with any path from the source
to the root on the other DAG. Given a network, we develop polynomial- time
algorithms to compute link-independent and node-independent DAGs. The algorithm
developed in this paper: 1) provides multipath routing; 2) utilizes all
possible edges; 3) guarantees recovery from single link failure; and 4)
achieves all these with at most one bit per packet as overhead when routing is
based on destination address and incoming edge. We show the effectiveness of the
proposed IDAGs approach by comparing key performance indices to that of the
independent trees and multiple pairs of independent trees techniques through
extensive simulations.
EXISTING
SYSTEM:
When multiple routing tables are
employed, a packet has to carry in its header the routing table to be used for
forwarding. When the corresponding forwarding edge is not available, the packet
needs to be dropped. This dropping is forced due to the potential looping of
packets when transferred from one routing table to another.
Techniques
developed for fast recovery from single link failures provide more than one
forwarding edge to route a packet to a destination. The techniques may be
classified depending on the nature in which the backup edges are employed. A
method to augment any given tree rooted at a destination with “backup
forwarding ports.” Whenever the default forwarding edge fails or a packet is
received from the node attached to the default forwarding edge for the
destination, the packets are re-routed on the backup ports.
Maximum
Alternative Routing Algorithm (MARA) constructs a DAG that utilizes all edges
in the network to increase the number of paths significantly.
DISADVANTAGES
OF EXISTING SYSTEM:
Whenever
the default forwarding edge fails or a packet is received from the node
attached to the default forwarding edge for the destination, the packets are
re-routed on the backup ports.
Maximum
Alternative Routing Algorithm (MARA) does not provide a mechanism for backup
forwarding when encountering a single link or node failure.
PROPOSED
SYSTEM:
Two trees
are constructed per destination node such that the paths from any node to the
root on the two trees are disjoint. The trees may be constructed to obtain
link-disjoint or node-disjoint paths if the network is two-edge or two-vertex
connected, respectively. This approach is similar to those employing multiple
routing tables, except that only two tables are required. Every packet may
carry an extra bit in its header to indicate the tree to be used for routing.
This overhead bit may be avoided by employing a routing based on the
destination address and the incoming edge over which the packet was received,
as every incoming edge will be present on exactly one of the trees.
The colored
tree approach allows every node to split its traffic between the two trees,
thus offering disjoint multipath routing. In addition, when a forwarding link
on a tree fails, the packet may be switched to the other tree. A packet may be
transferred from one tree to another at most once as the colored tree approach
is guaranteed to recover from only a single link failure. The colored trees are
also referred to as “independent trees” in the literature.
ADVANTAGES
OF PROPOSED SYSTEM:
ü Robustness
ü Load
balancing
ü Bandwidth
aggregation
ü Congestion
reduction and
ü Security
In the
Proposed system, we introduced the concept of independent
directed acyclic graphs (IDAGs) and developed a methodology for resilient
multipath routing using two IDAGs. We developed polynomial-time algorithms to
construct node-independent and link-independent DAGs using all possible edges
in the network
MODULES
v Topology Construction
v Resilient Routing
v Node Independent DAG
v Link Independent DAG
MODULES DESCRIPTION:
Topology Construction
This module is used to
construct the topology. The user gives the number of node used to construct the
topology. The node is added in given name, IP address and port number of that
node. Unique nodes are created so that it can be logged in separately. After
adding the node, the source node name, neighbor node name and weight of that
path will be given for path connection. The node details are stored in database
table called Nodedetails. Routing details are stored in the routing table.
Resilient Routing
The network is assumed to
employ link-state protocol, hence every node has the view of the entire network
topology. Every node computes DAGs, for each destination and maintains one or
more forwarding entries per destination per DAG. DAG to be employed for routing
is carried in an overhead bit (DAG bit) in every packet header. Any DAG first
(ADF), a packet may be transmitted by the source DAG. In addition to the DAG
bit, every packet also carries an additional bit that indicates whether the
packet has been transferred from one DAG to another (Transfer bit). A packet is
routed on the DAG indicated in its packet header. If no forwarding edges are
available in that DAG and if the packet has not encountered a DAG transfer
already, it is transferred to the other DAG.
Node Independent DAG
Two-vertex-connectivity is
the necessary and sufficient requirement for constructing two node-independent
DAGs utilizing all the edges except those emanating from the given destination
node. This necessary part of the requirement follows directly from the
condition required for constructing two node-independent trees – a special case
of DAG.
Initialize the partial order
for the nodes on the two DAGs. Compute the first cycle to be augmented. Compute
successive paths to be augmented. The path starts and ends at distinct nodes
that are already added to the DAGs, hence the paths from every node to the root
of the DAG are node-disjoint. Note that the difference between the path
augmentation employed for DAG construction here and that employed for tree
construction.
Link Independent DAG
Two-edge connectivity is a
necessary and sufficient condition for constructing two link-independent DAGs.
Similar to the requirement of node-independent DAGs, the necessary part of the
requirement follows from the independent tree construction. The procedure to
construct two link independent DAGs. Divide the network into two vertex-
connected (2V) components. A node may appear in more than 2V-component and the
removal of such a node (articulation node) would disconnect the graph. In
addition, any two 2V-components may share at most one node in common. Given a
destination node d, identify the root node for every component – the unique
node through which every path connecting a node in that component and d must
traverse. In components that contain node d, the root node is assumed to be d.
SYSTEM
REQUIREMENTS:
HARDWARE
REQUIREMENTS:
•
System : Pentium IV 2.4 GHz.
•
Hard
Disk : 40 GB.
•
Floppy
Drive : 1.44 Mb.
•
Monitor : 15 VGA Colour.
•
Mouse : Logitech.
•
Ram : 512 Mb.
SOFTWARE
REQUIREMENTS:
•
Operating system : - Windows XP.
•
Coding Language : JAVA
•
DATABASE :
SQL-SERVER-2005
REFERENCE:
Sangman Cho, Theodore Elhourani, and
Srinivasan Ramasubramanian, “Independent Directed Acyclic Graphs for
Resilient Multipath Routing”, IEEE/ACM
TRANSACTIONS ON NETWORKING, VOL. 20, NO. 1, FEBRUARY 2012.