Access Network DesignA Simple Access DesignStarCheaper Local-Access DesignTwo concentratorsMove to MSTMSTs not always Optimal Access DesignsAn Optimal DesignFrame Relay DesignFrame Relay vs. Lease-Line CostChoosing Backbone Nodes3 Types of Local Access ProblemsOne-speed One-Center DesignSPT(Star)MSTPrim-Dijkstra with a=0.3How Many possible Trees to Search for Optimal Designs?Constraint Minimum Spanning Tree ProblemGreedy CMST AlgorithmEsau-William AlgorithmApply Esau-William AlgorithmApply Esau-William Algorithm(2)Apply Esau-William Algorithm(3)Apply Esau-William Algorithm(4)Creditability of Esau-Williams AlgorithmEsau-Williams and InHomogenous TrafficLine Crossing and Esau-WilliamsSharma’s AlgorithmSharma’s Algorithm ResultCreditability of Sharma AlgorithmSharma vs. Esau-WilliamsMultispeed CMST ProblemMultispeed Local Access Algorithm (MSLA)MSLA ExampleMSLA (2)MSLA (3)Esau Williams 20 nodes with 9.6kbps linksMSLA 20 nodes with multispeed linksMultiCenter Local-Access (MCLA) ProblemNearest-Neighbor Esau-WilliamsCreditability TestMultiCenter Esau-WilliamsNNEW vs. MCEWPractical ConsiderationsHomework #6: Local Access DesignSolution to Hw#6Solution to Hw#6(2)Solution to Hw#6(3)Solution to Hw#6(4)01/13/19 C. Edward ChowCS622 Page 1Access Network Design•A Backbone network connects major sites.•Access networks connect small sites to the backbone network.•How to decide which sites should be in the backbone network?–Traffic volume–Close to multiple small sites•Access network collect traffic from small sites into the high speed backbone network.•Sharing high speed links, enjoy economic of scale benefit.•Examples of local access networks–Local subscriber loop connects users of a central office.–Lottery network–ATM network–ISP’s local access network.01/13/19 C. Edward ChowCS622 Page 2A Simple Access Design•7 nodes. N1 is the backbone site. Symmetric traffic.Piecewise linear cost:Fixed cost=400$3.00/km/mofirst 300km$1.75/km/moafter 300km01/13/19 C. Edward ChowCS622 Page 3Star •Cost=$9650; Max. Utilization=23.2%01/13/19 C. Edward ChowCS622 Page 4Cheaper Local-Access Design•N2 serves as a concentrator for N6 and N7. •Local link can use shorter less expensive link.01/13/19 C. Edward ChowCS622 Page 5Two concentrators•N2 for N6 and N7; N4 for N3.01/13/19 C. Edward ChowCS622 Page 6Move to MST•Choose N7 as concentrator instead of N2. Become MST01/13/19 C. Edward ChowCS622 Page 7MSTs not always Optimal Access Designs•When traffic grows 50%, MST costs $10,616 and the links to concentrators N4 and N7 must have two links to keep utilization below 50%.01/13/19 C. Edward ChowCS622 Page 8An Optimal Design•Constraint MST problem. Note that N3 connect directly to N1 since through N4 will violate the utilization constraint.01/13/19 C. Edward ChowCS622 Page 9Frame Relay Design•Current frame relay provide permanent virtual circuit (PVC). They are moving to offer Switched virtual circuit (SVC).•PVC is fixed pipe. SVC is dialed pipe.•Packets exceed Committed Information Rate (CIR) will have discard eligibility (DE) bit set.•Three classes of charges: access link costs, provider port costs (cost to frame relay), and CIR costs.•It is volume dependent and not distance dependent. Port Charges CIR charges per PVC01/13/19 C. Edward ChowCS622 Page 10Frame Relay vs. Lease-Line Cost•Let x be the distance from the site to the center.•Fixed cost=$400/month; $3.00/km/month.•Leased-line cost=6*400+6*3.00*x•Assume frame relay provider has point of presence (pop) at each site. Each site connects to the frame relay network.•N1 uses 128 kbps link, others use 56kbps links.•Port charges=6*250+500=2000.•Access charges=7*(400+3.0*20)=7*460=3220•CIR charges=4*30+2*25=170 if 4 PVCs with 16kbps CIR and 2PVCs with 8kbps.•Frame relay cost=2000+3220+170=$6290/mo•Solve 2400+18*x=6290  x=216.11 km. Break even point.•Most WAN are larger than this Frame Relay is a good candidate.01/13/19 C. Edward ChowCS622 Page 11Choosing Backbone Nodes•Definition 5.1: Given a set of sites Ni and traffic matrix T(i,j), weight(Ni)=j(T(i,j)+T(j,i)).•Sometimes, the weights of nodes indicate the choices of backbone nodes or traffic centers.•Design Principle 5.3: It is acceptable for small nodes to route their traffic via big nodes, but generally we do not want to route the traffic between big nodes via the small nodes.01/13/19 C. Edward ChowCS622 Page 123 Types of Local Access Problems1. Access node’s traffic are considerably smaller than the smallest link. But occasionally, they may need to download huge file Use frame relay or access tree (capacitated spanning tree building problem.)2. Access node’s traffic is comparable to the capacity of the smallest link. Choices: connect them directly to hub or put concentrator between hub and those nodes. (Concentrator placement problem, local access tree problem.)3. Access node’s traffic can fill several low-speed access lines. Choices: multiple links to multiple backbone nodes; or high speed link to a backbone node. They are nature choices for concentrator locations.01/13/19 C. Edward ChowCS622 Page 13One-speed One-Center Design•Example: 19 nodes to a hub, N14.•4 sites can share a line. Each link is 1200 bps.•Use 9600 bps link. 50% utilization.•The problem becomes a tree building problem.•Solution:–SPT–MST–Prim-Dijkstra with 0<<1.–Other algorithm?01/13/19 C. Edward ChowCS622 Page 14SPT(Star)•Cost=$2635801/13/19 C. Edward ChowCS622 Page 15MST•$18,73001/13/19 C. Edward ChowCS622 Page 16Prim-Dijkstra with =0.3•$15930. N11 can go through N4; Two clusters with N18 and N9 as concentrators.01/13/19 C. Edward ChowCS622 Page 17How Many possible Trees to Search for Optimal Designs?•Cayley’s Theorem: Given n nodes, there are nn-2 different spanning tree.•For 20 nodes, there are 2018=2.621*1023 trees.01/13/19 C. Edward ChowCS622 Page 18Constraint Minimum Spanning Tree Problem•It solves the problem of creating capacitated (constraint) minimum spanning tree (CMST).•CMST problem: Given a central node N0 and a set of other nodes (N1, …, Nn), a set of weights(w1,…,wn) for each 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 contains N0, and 0,iTiijWw Trees LinkslllendendCost )2,1(min01/13/19 C. Edward ChowCS622 Page 19Greedy