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
