Network Design - Chapter 6: Access Network Design - University of Pittsburgh

Nội dung text: Network Design - Chapter 6: Access Network Design - University of Pittsburgh

1. Access Network Design David Tipper Associate Professor Department of Information Science and Telecommunications University of Pittsburgh Slides 6 Access Network Design • Backbone or Wide Area Networks connect major sites. – Backbone networks (UUNET, Verizon) – Corporate VPN – Campus backbone • Access networks connect “small” sites to the backbone network. – Access networks are the “ends” and “tails” of networks that connect the smallest sites into the network. – In some cases access networks only function if they are attached to a backbone. – LAN, Metro networks, VLAN, cellular networks, Wireless LAN Local access in phone network, Bank ATM machines – Historically informal back of the envelope design procedures – becoming more mathematical based TELCOM 2110 5 1
2. Access Network Example • Can make Access/Backbone analogy with transportation networks • Visit to Gauley River for whitewater rafting in WV • The trip involves 4 segments: – Travel from home in Pittsburgh via city streets to interstate – Then traverse the 279, 79 Interstate backbone to the location closest to Gauley River - U.S. Highway 19 exit – Then you travel on U.S. highway 19 to get to Summersville, WV (this is like a concentrator – is a four lane highway (with traffic lights etc) – Travel local state highways roads from Summersville to get to Gauley River TELCOM 2110 6 Access Network Example See similar – access to backbone behavior in networks For example, LAN segments connecting to campus backbone TELCOM 2110 7 2
3. Access Network Design • Backbone/access division is efficient for transportation networks and efficient for telecommunications networks. • Access network collect traffic from small sites into the high speed backbone network. • Sharing high speed links, enjoy economy of scale benefit. • Local access often represents most of the total network cost – e.g, telephone network TELCOM 2110 8 A Simple Access Design Problem • A problem with 6 access locations and 1 backbone site N1 Traffic is symmetric and shown table . • Piecewise linear cost function • Using Leased Lines : • Cost=$400 + ($3.00/km/month for the first 300km and a cost of $1.75/km/month after 300km) Cost Matrix for 56Kbps Lines TELCOM 2110 9 3
4. Star Design • Cost=$9650; Maximum Utilization=23.2% TELCOM 2110 10 One Concentrator • N2 serves as a concentrator for N6 and N7. • Shorter less expensive links are used from N6 and N7 • Cost=$8660; Maximum Utilization=46.4% TELCOM 2110 11 4
5. Two Concentrators • N2 for N6 and N7; N4 for N3. • Cost=$8158; Maximum Utilization=46.4% TELCOM 2110 12 MST Design • Using MST algorithm, chooses N7, N4 as concentrators • Cost=$7659; Maximum Utilization=46.4% TELCOM 2110 13 5
6. MSTs Are 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%. TELCOM 2110 14 Access Design Problems • Can roughly categorize AUC EIR access design problems HLR IBM VLR – One speed one center MSC design SD Bay Net works Centillion 1400 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD SD Bay Net works Centillion 1400 ALM PW R ALM FAN0 FAN1 PWR0 PW R1 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD ALM PW R ALM FAN0 FAN1 PWR0 PW R1 BSC • For example, local loop in BSC SD Bay Net works Centillion 1400 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD ALM PW R ALM FAN0 FAN1 PWR0 PW R1 telephone network BSC – Multi-speed access design BS3 BS3 BS2 BS4 • For example, LAN design BS2 BS4 BS1 from variety of hosts BS1 BS7 BS5 BS7 BS5 – Multi-center Design BS6 BS6 • For example, cellular networks with multiple base station controllers TELCOM 2110 15 6
7. One-speed One-Center Design Problem: Connecting sites to one backbone node (switch, router) all links with the same capacity OR OR TELCOM 2110 16 Approaches • Shortest Path Tree (Dijkstra’s Algorithm) – Expensive, low utilizaton, good delay • Minimum Spanning Tree (Prim’s Algorithm) – Cheap, possibly high delay due to longer path length • Comprise (Prim-Dijkstra Algorithms) – Better results, harder to determine • Exhaustive Search (consider all possible trees) – Cayley’s Theorem: Given n nodes, there are nn-2 different spanning trees. – For 20 nodes, there are 2018=2.621*1023 different trees. – obviously this approach won’t scale TELCOM 2110 17 7
8. One-speed One-Center Example • Problem: Connect a large number of sites to a hub – 19 nodes that are to be connected to a hub – N14 is the hub location – Up to 4 sites can share a line – Traffic to and from each node Ni is 1200bps – Capacity of the links is 9600bps – Limit the utilization to 50% • Compare different solution approaches TELCOM 2110 18 SPT(Star) • Cost= $26358 • Very low link utilization and expensive TELCOM 2110 19 8
9. MST • Cost= $18,730 • More cost effective but has higher delays TELCOM 2110 20 Prim-Dijkstra with α=0.3 • Cost= $15930. • N11 should connect to N4, Two clusters based at N18 and N9. • Better results but higher complexity of calculation TELCOM 2110 21 9
10. Capacitated Minimum Spanning Tree (CMST) • CMST problem: Given a center node N0 set of other nodes (N1, , Nn), set of weights(w1, ,wn) for each node, the capacity of each link, W 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 the following holds ∑ wi 0 min ∑ ∑Cost(end1l ,end2l ) Treesl∈ Links TELCOM 2110 22 The Esau-Williams Algorithm • Heuristic Algorithm but guarantees the tree meets the capacity constraint • Each node starts off in a tree with 1 node. • Compute the tradeoff function for each node: Tradeoff(Nk)=minj Cost(Nk, Nj)-Cost(Comp(Nk), Center N0) – Tradeoff function for merging components Nk and Nj computes the potential savings of going to a neighbor instead of going to the center node. • If the tradeoff is negative, a merge is attractive • Pick the node with smallest tradeoff value for merger with nearest neighbor TELCOM 2110 24 10
11. The Esau-Williams Algorithm • Merger is allowed if the link capacity is not exceeded – that is weight of nodes less than link speed weight(Comp(NK )) + weight(Comp(NJ )) ≤ W • If the merger is disallowed one moves to the node with the next smallest tradeoff value • Algorithm terminates when all tradeoffs are positive or the list of possible merges is exhausted • Since Heuristic - solution is not always optimal TELCOM 2110 25 Esau-Williams Example • W=3, each node has wi=1 • Tradeoff(1)=minj Cost(N1,NJ)- Cost(Comp(N1),Center) Initial topology =minj Cost(N1,N3) - (Comp(N1) dashed lines contains N0) =3-5= -2 (pick closest neighbor, N3) 2 • Tradeoff(2)=4-6= -2 5 • Tradeoff(3)=3-9= -6 8 • Tradeoff(4)=5-12= -7 6 4 12 4 • Tradeoff(5)=6-15= -9 7 12 6 15 5 • Tradeoff(5) is the smallest 0 9 6 • Accept link(5,3) merger to the solution 3 10 8 since weight constraint on component 5 tree with nodes 5 and 3 is not violated. 3 Σwi =w5+w3=2<=W=3 1 TELCOM 2110 26 11
12. Esau-Williams Example • Next Iteration – Tradeoff(1)=3-5= -2 – Tradeoff(2)=4-6= -2 Topology after 1 – Tradeoff(3)=3-9= -6 iteration – Tradeoff(4)=5-12= -7 2 – Update Tradeoff(5)=7-9= -2 5 next shortest link out of 5 is (5,4) 8 6 (Comp(5)=9,node 5 goes through 4 12 4 node 3 to center) 7 – Tradeoff(5)=7-9= -2 12 6 15 5 0 • Pick Tradeoff(4) as smallest 9 6 • Accept (4,2) merger since 3 10 8 weight constraint on component 5 trees with nodes 4 and 2 is not 3 violated. 1 Σwi =w4+w2=2<=W=3 TELCOM 2110 27 Esau-Williams Example • Next iteration – Tradeoff(1)=3-5= -2 Topology after iteration 2 – Tradeoff(2)=4-6= -2 – Tradeoff(3)=3-9= -6 2 – Update Tradeoff(4)=6-6= 0 5 8 – Tradeoff(5)=7-9= -2 6 – Pick Tradeoff(3) 4 12 4 7 12 • Accept link (3,1) since 6 15 5 weight constraint on 0 component 9 6 3 with nodes 1, 3 and 5 are 10 8 5 not violated. 3 Σwi =w1+w3 +w5 =3<=W=3 1 TELCOM 2110 28 12
13. Esau-Williams Example • Next Iteration – Tradeoff(1)=4-5= -1 Topology after iteration 3 – Tradeoff(2)=4-6= -2 – Tradeoff(3)=6-5= 1 which is Final topology – Tradeoff(4)=6-6=0 – Since nodes 5 and 3 now go 2 through node 1 to Center, update Tradeoff(5)=7-5=2 5 8 • Tradeoff(2) is lowest but 6 adding link(2,1) results a 4 12 4 component 7 with 4 nodes violate w <=3. 12 Σ i 6 15 5 • Reject(2,1) 0 recompute Tradeoff(2)=6-6=0 9 6 • Reject(1,2) similar reason. 3 Recompute Tradeoff(1)=5-5=0 10 8 • The access network is complete 5 3 1 TELCOM 2110 29 Example 2 • Consider the grid network below. – This network can occur in a cellular network in a downtown urban environment. Where the nodes represent base stations and the hub/central node a base station controller – For the example Node 0 is the central node. – The weight of each individual node is 1, except for nodes 4 and 5, which have a weight of 2. The cost function C(i,,j) is given by the physical distance between nodes i and j. W=3 – Design a capacitated access tree using Esau-Williams algorithm. 0 1 2 1 3 4 5 1 6 78 TELCOM 2110 1 1 30 13
14. Example 2 Tradeoff(i)=minj Cost(Ni,NJ) -Cost(Comp(Ni),Center) Tradeoff(1) = 1 -1 = 0 Tradeoff(2) = 1 -2 = -1 Tradeoff(3) = 1 – 1 = 0 Tradeoff(4) = 1 – sqrt(2) = -.414 Tradeoff(5) = 1 – sqrt(5) = -1.236 Tradeoff(6) =1-2 = -1 Tradeoff(7) = 1-sqrt(5) = -1.236 Tradeoff(8) = 1-sqrt(8) = - 1.828 Pick 8 to merge with either 7 or 5 0 1 2 Pick 7 since it has lower weight = 1 1 Checking capacity w +w = 2 ≤ W = 3 7 8 3 4 5 1 6 78 1 1 TELCOM 2110 31 Example 2 Iteration 2 Tradeoff(1) = 1 -1 = 0 Tradeoff(2) = 1 -2 = -1 Tradeoff(3) = 1 – 1 = 0 Tradeoff(4) = 1 – sqrt(2) = -.414 Tradeoff(5) = 1 – sqrt(5) = -1.236 Tradeoff(6) =1-2 = -1 Tradeoff(7) = 1-sqrt(5) = -1.236 Tradeoff(8) = 1-sqrt(5) = - 1.236 Pick 5 to merge with node 2 0 1 2 Note node 4 or 8 merge is not allowed 1 by capacity constraint 3 4 5 Checking capacity w5+w2 = 3 ≤ W = 3 1 6 78 1 1 TELCOM 2110 32 14
15. Example 2 Iteration 3 Tradeoff(1) = 1 -1 = 0 Tradeoff(2) = 1 -2 = -1 Tradeoff(3) = 1 – 1 = 0 Tradeoff(4) = 1 – sqrt(2) = -.414 Tradeoff(5) = 1 – 2 = -1 – not allowed Tradeoff(6) =1-2 = -1 Tradeoff(7) = 1-sqrt(5) = -1.236 Tradeoff(8) = 1-sqrt(5) = - 1.236 Pick 7 to merge with node 6 0 1 2 Note node 4 is not allowed by capacity 1 constraint 3 4 5 Checking capacity w6+w7 + w8= 3 ≤ W 1 6 78 1 1 TELCOM 2110 33 Example 2 Iteration 4 Tradeoff(1) = 1 -1 = 0 Tradeoff(2) = 1 -2 = -1 not allowed Tradeoff(3) = 1 – 1 = 0 Tradeoff(4) = 1 – sqrt(2) = -.414 Tradeoff(5) = 1 – 2 = -1 not allowed Tradeoff(6) =1-2 = -1 not allowed Tradeoff(7) = 1-2 = -1 not allowed Tradeoff(8) = 1-2 = -1 not allowed Pick 4 to merge with node 3 or 1 0 1 2 Checking capacity w3+w4 = 3 ≤ W 1 Note all allowed merges have positive 3 4 5 Tradoffs so final topology with cost 10 1 6 78 1 1 TELCOM 2110 34 15
16. Esau-Williams Algorithm • How Good is solution? 1-exchange test: Given a set of sites N and a capacitated tree T, we check that no cheaper link can be substituted for an existing link without violating the capacity constraints. TELCOM 2110 35 Esau-Williams and Inhomogeneous Traffic • Algorithm does as well if the sites have a variety of different traffic. • Links are 9600bps • 50% of sites require 2400bps • Others require 4800bps TELCOM 2110 36 16
17. Line Crossings in Access Designs • A 20 node Esau-Williams design – sometimes has line crossings TELCOM 2110 37 Sharma’s Algorithm • Heuristic algorithm to create networks with no lines crossing Useful when physical constraints (duct for running cable) dictate that no lines cross 1. Compute the angle θs from each site S to the central site C. If S and C have the same coordinate, set θs = 0. 2. Sort the angles θs from smallest to largest 3. Beginning at a site Sfirst, create a set of nodes clockwise (or counterclockwise) from Sfirst. A set is complete when adding the next node would put Σsetw(site) > W. The next set starts with that node. 4. The design is completed by building a MST on each set with the addition of the central node C. Comment If the angles θs are distinct, then if the cost function is a linear or piecewise linear metric, Sharma’s algorithm builds CMSTs without crossings provided that all the central angles are less than π. TELCOM 2110 38 17
18. Example of Sharma’s algorithm • Consider the grid network below. – This network can occur in a cellular network in a downtown urban environment. Where the nodes represent base stations and the hub/central node a base station controller – For the example Node 0 is the central node. – The weight of each individual node is 1, except for nodes 4 and 5, which have a weight of 2. The cost function C(i,,j) is given by the physical distance between nodes i and j. W=3 0 1 2 1 3 4 5 1 6 78 TELCOM 2110 1 1 39 Example of Sharma’s algorithm Angle of each node θ1 = 0, θ2 = 0 θ3 = -90 θ4 = -45 θ5 = -22.5 θ6 = -90 θ7 = -72.5 θ8 = -45 0 1 2 1 Sorted angles 3 4 5 {θ1 θ2 θ5 θ4 θ8 θ7 θ3 θ6 } 1 6 78 1 1 TELCOM 2110 40 18
19. Example of Sharma’s algorithm From Sorted angles {θ1 θ2 θ5 θ4 θ8 θ7 θ3 θ6 } Form Sets {θ1 θ2 } note θ5 not included because sum of weight of nodes would exceed capacity constraint. {θ1 θ2 } , { θ5 θ8}, { θ4 θ7}, { θ3 θ6} Running MST for each set yields the following topology Cost of topology is 11 which is 0 1 2 greater than E-W design but no 1 3 4 5 crossed lines. 1 6 78 1 1 TELCOM 2110 41 Sharma’s Algorithm Example Consider 20 node network, node 16 is hub, W = 4 Working counter clockwise on angles Sorted Angles 17 19 13 12 18 5 6 5 1 6 8 1 14 18 19 14 13 9 12 17 8 9 4 11 0 15 15 7 16 3 2 10 10 3 7 4 2 11 0 TELCOM 2110 42 19
20. Sharma’s Algorithm Design • Cost= $16021, Sfirst = N17 TELCOM 2110 43 The Creditability of Sharma Designs • Designs look nice but most of them fail the creditability test. • Much higher failure rate than Esau-Williams’. TELCOM 2110 44 20
21. Sharma vs. Esau-Williams • EW_Ratio=SharmaCost/EWCost; S_Ratio=EWCost/SharmaCost • In general use Esau- Williams unless require no lines cross TELCOM 2110 45 Access Design AUC EIR • Considered One HLR IBM VLR speed one center MSC design SD Bay Net works Centillion 1400 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD SD Bay Net works Centillion 1400 ALM PW R ALM FAN0 FAN1 PWR0 PW R1 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD • Local loop in ALM PW R ALM FAN0 FAN1 PWR0 PW R1 BSC BSC SD Bay Net works Centillion 1400 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD ALM PW R ALM FAN0 FAN1 PWR0 PW R1 telephone network BSC • Cellular network BS3 connecting BS to BSC BS3 BS2 BS4 BS2 BS4 BS1 • LAN, host to hub or BS1 BS7 BS5 BS7 BS5 switch BS6 BS6 • Two algorithms 1. Esau-Williams 2. Sharma TELCOM 2110 46 21