DOC PREVIEW
UCCS CS 622 - Mesh Network Design

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Mesh Network DesignExamples of Bad Design Too Many Direct Links; Nodes with High DegreeDesign with Only High Speed Links2-Level Design ($96,777)More Reliable DesignA Different Interior TopologyAdd More Backbone NodesEven Lower Cost DesignAlgorithm Complexity and Design Space SizeMentor Algorithm [KKG91]Mid Stage of Threshold Cluster AlgorithmFinal Stage of Threshold ClusteringMentor Algorithm Steps 2-3Restricted Prim-Dijkstra TreeSequencing Node PairsMentor Algorithm Step 5Complexity of Mentor AlgorithmExample of Mentor Algorithm ResultMentor Algorithm Design 2Mentor Algorithm Design 3Cost of Designs vs. a and utilminCost vs. Size of Backbone01/14/19 C. Edward ChowCS622 Page 1Mesh Network Design•Backbone network design goals:•Direct path between source and destination.•Well-utilized components•Use high speed lines to achieve economy of scale.•These goals are self-contradictory.01/14/19 C. Edward ChowCS622 Page 2Examples of Bad DesignToo Many Direct Links; Nodes with High Degree45 node network with cost=$264,411/month01/14/19 C. Edward ChowCS622 Page 3Design with Only High Speed Links•Warning sign: high average number of hops01/14/19 C. Edward ChowCS622 Page 42-Level Design ($96,777)•Pick heavy traffic nodes as interior nodes of the tree.01/14/19 C. Edward ChowCS622 Page 5More Reliable Design•Instead of tree, interior nodes form a 2-connected graph.01/14/19 C. Edward ChowCS622 Page 6A Different Interior Topology •Reduce cost from $112,587$108,72401/14/19 C. Edward ChowCS622 Page 7Add More Backbone Nodes•$103,107 cost reduced.01/14/19 C. Edward ChowCS622 Page 8Even Lower Cost Design•$101,80601/14/19 C. Edward ChowCS622 Page 9Algorithm Complexity and Design Space Size•Even if a subset of designs can be identified we are still dealing with big design space.•Here the number in D is based on 2 c(45,2)01/14/19 C. Edward ChowCS622 Page 10Mentor Algorithm [KKG91]Assume single link type with capacity C.1. Choose backbone sites. (Also called Threshold Cluster Algorithm)•Calculate the normalized weight NW(Ni)=W(Ni)/C•Choose sites with NW(Ni) > WPARM (threshold)•Group end sites around a backbone site, x, based onCost(x, Ni)/MAXCOST < RPARM.Where MAXCOST=Max i,j Cost(Ni, Nj)•If there are sites not covered in groups, compute merit(n)=1/2*(MaxDistCtr-distCtrn)/MaxDistCtr + 1/2*(Weightn/WeightMax)Here andCenter of Mass (xctr, yctr) defined by•Sort the merit functions. The node with largest merit get picked asbackbone node. Group end node around it. Repeat until all nodes are covered in groups.22)()(max yctryxctrxMaxDistCtrnnNn22)()( yctryxctrxDistCtrnnnNnnNnnnWeightWeightxxctrNnnNnnnWeightWeightyyctr01/14/19 C. Edward ChowCS622 Page 11Mid Stage of Threshold Cluster Algorithm•Big Squares are Backbone nodes.01/14/19 C. Edward ChowCS622 Page 12Final Stage of Threshold Clustering•Based on merit(), three backbone nodes are picked.01/14/19 C. Edward ChowCS622 Page 13Mentor Algorithm Steps 2-32. Pick median node (root node of the network) with smallest Moment():3. Build a restricted Prim-Dijkstra tree rooted at median.Here only backbone nodes can be the interior nodes of the tree.4. Sequencing Node Pair: Prepare adding additional direct links to the tree.•Use the tree to list node pair in “sequence”The node pair with longer path will list first•Choose home node H for each node pair (Ni,Nj) (H and Nx are intermediate nodes along the path) that satisfies Cost(Ni, H)+Cost(H,Nj)<= Cost(Ni, Nx)+Cost(Nx,Nj).NnnWeightnndistnMoment ),()(01/14/19 C. Edward ChowCS622 Page 14Restricted Prim-Dijkstra Tree•Note that there is an end node that violate the constraint.01/14/19 C. Edward ChowCS622 Page 15Sequencing Node Pairs01/14/19 C. Edward ChowCS622 Page 16Mentor Algorithm Step 55. Decide which node pairs deserve direct links.•Start with the top node pair (N1,N2) in the sequence.•Calculate the utilization u=Traf(N1,N2)/(n*C)where n=ceil(Traf(N1,N2)/C).•If u>utilmin, add direct link between N1 and N2.•If u< utilmin, add Traf(N1,N2) to Traf(N1,H) and Traf(H,N2). Here H is the home of (N1,N2).•Remove (N1,N2) from the sequence and repeat Step 5 again until all node pairs are processed.01/14/19 C. Edward ChowCS622 Page 17Complexity of Mentor Algorithm•The three basic steps: backbone selection, tree building, and direct link addition are all O(n2).•It can be executed pretty fast.•Typically we will generate a set of designs based on the same threshold parameter, e.g., different  in the restricted Prim-Dijkstra tree, or different node pair sequence (note that the sequence are not unique).•We then pick the best design from the set.01/14/19 C. Edward ChowCS622 Page 18Example of Mentor Algorithm Result•15 sites, 5 backbone nodes01/14/19 C. Edward ChowCS622 Page 19Mentor Algorithm Design 2•$221,590, same 5 backbone nodes, with lower utilmin=0.701/14/19 C. Edward ChowCS622 Page 20•Same 5 backbone nodes but with different tree. $209,220.Mentor Algorithm Design 301/14/19 C. Edward ChowCS622 Page 21Cost of Designs vs.  and utilmin•A=0.1 and 1-utilmin=0.1 is the best value.01/14/19 C. Edward ChowCS622 Page 22Cost vs. Size of


View Full Document

UCCS CS 622 - Mesh Network Design

Documents in this Course
Fast TCP

Fast TCP

34 pages

Load more
Download Mesh Network Design
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Mesh Network Design and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mesh Network Design 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?