Prabhdeep Grewal
Routing mechanisms in the networks find the paths for packet transfer and route the packets on that path. Majority of the routing techniques prevalent in the industry use the shortest path to send the traffic throughout the network. This shortest path calculation technique has found application in various protocols like OSPF, BGP, ISIS, and AODV. These all use different algorithms to find the shortest paths (OSPF uses the s algorithm). The shortest path however can not guarantee the best quality path for routing as the path can be congested with traffic or may not have enough bandwidths on the links as required by the sender. To customize the user requests and allowing the users to be more specific about the type of service we have to include more constraints in the path calculation and routing mechanisms. There are three types of constraints that can be used for the path calculations that are additive, multiplicative and min/max constraints. Involving more than one additive/multiplicative constraint in the path calculation makes the problem NP hard. The Min/Max constraints on the other hand are easier to deal with as the links not having enough bandwidth can be pruned from the network calculations. There are two techniques to handle multiple constraints. First one uses a single constraint, which is defined as a function of all constraints, to find the optimal paths for the traffic. In this technique we can not do justice to each constraint individually as we optimize the overall calculated metric. Second one finds the path using all the constraints individually and hence does justice to all the constraints. The second technique has disadvantage of high computation complexity. We will discuss a mechanism that converts the additive metrics to a single metric and optimizes the paths based on that metric.