CST 303 Computer Networks Module 3 Questions and Answers PDF

MODULE 3 CST303 COMPUTER NETWORKS CST 303 COMPUTER NETWORKS Module 3 Important Questions Q1:Explain the optimality principle. What is a sink tree? A: Optimality ref...

MODULE 3 CST303 COMPUTER NETWORKS CST 303 COMPUTER NETWORKS Module 3 Important Questions Q1:Explain the optimality principle. What is a sink tree? A: Optimality refers to the capability of a routing algorithm to select the best route. Optimality principle states that if router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. To see this, we call the part of the route from I to J as r1 and the rest of the route as r2. If a route better than r2 existed from J to K, it could be concatenated with r1 to improve the route from I to K, contradicting our statement that r1r2 is optimal. The set of optimal routes from all sources to a given destination form a tree rooted at the destination, such a tree is called a sink tree, where the distance metric is the number of hops. Note that a sink tree is not necessarily unique; other trees with the same path lengths may exist. The goal of all routing algorithms is to discover and use the sink trees for all routers. Eg: a) A subnet b) A sink tree for router B Q2: Discuss the shortest path routing. Also explain the Dijkstra's algorithm in detail SCET S5 CSA BATCH 2020-25 Page 1 Downloaded from Ktunotes.in  MODULE 3 CST303 COMPUTER NETWORKS A: -It is one of the simple static routing algorithms that are widely used for routing in the network. -The basic idea is to build a graph with each node representing a router and each line representing a communication link. - A path selected can be called shortest in many contexts. If cost is selected as the criteria then the shortest path is the route which is least expensive. The cost is determined depending upon the criteria to be optimized, they include: Minimum number of hops: If each link is given a unit cost, the shortest path is the one with minimum number of hops. Such a route is easily obtained by a breadth first search method. This is easy to implement but ignores load, link capacity etc. Transmission and Propagation Delays: If the cost is fixed as a function of transmission and propagation delays, it will reflect the link capacities and the geographical distances. However these costs are essentially static and do not consider the varying load conditions. Queuing Delays: If the cost of a link is determined through its queuing delays, it takes care of the varying load conditions, but not of the propagation delays. Dijkstra’s algorithm It is a single-source shortest path algorithm, i.e. only one source is given, and we have to find the shortest path from the source to all the nodes. STEPS: 1. Consider any vertex as the source vertex. Here, let's take 0 as the source. eg: 2. Set the distance of all vertices from the source as infinity. 3. Find the distance from source to the directly connected vertices and update them. Use the formula: If d(x) + c(x,y) < d(y) Then, d(y)= d(x) + c(x,y) {here, d(x) is the distance between source and x. c(x,y) is the cost or distance between the vertices x and y} Here in the example, 1 and 4 are directly connected to the source 0. so , d(1)=d(0) + c(0,1) < ∞ I.e. d(1)= 0+4=4 < ∞ Similarly, d(4)= d(0) + c(0,4)