通信网理论基础（工程硕士）：Ch5 Routing in Data Networks1

1、Ch5: Routing in Data Networks10/1/20221Shortest Path Routing ReviewThe Bellman-Ford & Dijkstras algorithm10/1/20222The Floyd-Warshall algorithmFind the shortest paths between all pairs of nodes togetherProcedureStart with single arc distancesCalculate shortest path only node 1 used as intermediate n

2、odeOnly node 1 and node 2Example10/1/20223SummaryThe Bellman-Ford algorithm iterates on the number of arcs in a pathThe Dijkstra algorithm iterates on the length of the pathThe Floyd-Warshall algorithm iterates on the set of nodes that are allowed as intermediate nodes on the paths.10/1/20224View ro

3、uting as a “global” optimization problem Assumptions: The cost of using a link is a function of the flow on that link The total network cost is the sum of the link costs The required traffic rate between each source-destination pair is known in advance Traffic between source-destination pair can be

4、split along multiple paths with infinite precision Find the paths (and associated traffic flows) along which to route all of the traffic such that the total cost is minimized Optimal Routing10/1/2022Formulation of optimal routingLet Dij (Fij) be the cost function for using link (i,j) with flow Fij F

5、ij is the total traffic flow along link (i,j) Let D(F) be the total cost for the network with flow vector F The total cost:For S-D pair w with total rate rw Pw is the set of paths between S and D Xp is the rate sent along path p Pw 10/1/20226Formulation continuedOptimal routing problem can now be wr

6、itten as: 10/1/20227Optimal model limitationThe choice of the cost functionhypothesis: without paying attention to other aspects of the traffic statistics undesirable behavior associated with high variance and with correlations of packet inter arrival times and transmission times. 10/1/20228Topologi

7、cal design problemOverviewAssumptionsA collection of terminals with geographical locationsInput traffic flow from each terminal to othersDesignThe topology of a communication subnet to service the traffic demands of the terminalsThe local access network of terminalsObjectiveDelay constraintsGuarante

8、e the reliability Minimize cost10/1/20229Design and optimizationThe problem is divided into two parts Subnet design problemLAN design problem10/1/202210Subnet Design ProblemGiven location of subnet nodes and traffic flow for these nodesSelect the capacity and flow of each linkMeet the delay and reli

9、ability constraintsMinimizing costsA difficult combinatorial problem!Simple versionchoose the link capacities so as to minimize a linear cost. Capacity assignment problem10/1/202211Capacity assignment problemMinimize the linear costAccording M/M/1 model, the delay constraint r is the total arrival r

10、ate into the network The optimal value 10/1/202212Substitute the capability in cost function, the optimal cost is expressed as Consider optimizing the network cost with respect to both Cij and Fij Local minimaDifficult to minimizeHeuristic methods10/1/202213Capacity assignment problemHeuristic metho

11、ds for capacity assignmentSuppose there is a current best topology and a trial topologyBest means it satisfies the delay and reliability constraints and meanwhile has the lowest cost that has been foundDecide whether uses trial topo to replace current best topo10/1/202214Generate new trial TopoPossi

12、bilitiesLower the capacity (or delete) of underutilized linkIncrease the capacity of overutilized linkBranch exchange heuristicA combination of these possibilitiesone link is deleted and another link is addedsaturated cut method10/1/202215Network reliability issuesReliability requirementThe network

13、is k-connected.K-connectedK-connected between two nodesTwo nodes are connected by deleting (k-1) nodesA graph is k-connected if every pair of nodes are k-connected. 10/1/202216Network reliability issuesCheck k-connectivityCheck each pair of nodes is too slowMore efficient method is expectedKleitman

14、method1) Choose an arbitrary node and check it k-connectivity to others2) Delete the checked node and its arcs, and check another nodes (k-1)-connectivity3) Continue untilthe last second node is checked to be 1-connected, orStop at some (k-i)-connectivity of some node10/1/202217Local Access Network

15、DesignConcentrator location problemConnect the n sources to m concentratorsThe cost functionConsider the variables xij where Total cost10/1/202218AssumptionsOne source is connected to one concentrator a maximum number of sources that can be handled by concentrator j.The problem can be converted to a linear transportation problem. 10/1/202219Optimization