Algoritmo De Dijkstra Wan

CS 622 Distributed Networks
Multi-center Access Network Design

Dr. Xiaobo Zhou Department of Computer Science

CS622 MCAccessNetworks.1

UC. ColoradoSprings

Review: One-speed One-center CMST Problem
° CMST problem: Given a central node N0 and a set of other nodes (N1, …, Nn), a set of weights(w1,…,wn) foreach node, the capacity of a link, W, and a cost matrix Cost(i, j), find a set of trees T1, …, Tk such that each Ni belongs to exactly one Tj and each Tj containsN0, and

i∈T j , i > 0

∑w 0 • If m = 1, the problem is reduced to CMST ° MSLA algorithm
UC. Colorado Springs

CS622 MCAccessNetworks.3

Multi-CenterOne-speed Local-Access (MCLA) Problem
° If a network has multiple centers, instead of building a tree, we now want to build a forest. Definition 7.1 A forest, F =(V, E), is a simple graph without cycles • A forest need not be connected.

CS622 MCAccessNetworks.4

UC. Colorado Springs

Formalization of MCLA ProblemGiven ° ° ° ° a set of backbone sites B = (B0,…,Bm): multi-centers a set of access nodes N = (N1,…,Nn) A set of weights (w1,…,wn) for each access node A cost matrixCost(i,j) for each backbone/access pair

Find a set of trees T1,…,Tk such that ° ° Exactly 1 backbone site/center belongs to each tree

ΣNi∈Tj wi 1. Byadjust α we limit the links connect to a center Solution 2: Use NNEW or MCEW with initial center assignment of some nodes to low utilization center (load balancing) °Some site fails too often Solution: Mark it as not being choice for predecessor of other sites

° ° °

CS622 MCAccessNetworks.14

UC. Colorado Springs