Network Design - Chapter 7: Access Network Design Continued - University of Pittsburgh

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

1. Access Network Design Continued David Tipper Associate Professor Department of Information Science and Telecommunications University of Pittsburgh Slides 8 Access Design Problems • Can roughly categorize access AUC EIR design problems HLR IBM VLR – One speed one center design MSC • Capacitated MST problem SD Bay Net works Centi lli on 1400 ETHERLINK RS 232C INS ACT ALM P* 8x 50 RST OO130 A O N 6 PC CARD SD Bay Networks Centillion 1400 ALM PWR ALM AFN0FAN1PWR0PWR1 – Esau-Williams algorithm P* 8x 50 ETHERLINK RS 232C INS ACT ALM RST OO130 A O N 6 PC CARD ALM PWR ALM FAN0 FAN1 PWR0 PWR1 BSC BSC SD – Sharma algorithm Bay Net works Centi lli on 1400 P* 8x 50 ETHERLINK RS 232C INS ACT ALM RST OO130 A O N 6 PC CARD ALM PWR ALM FAN0FAN1PWR0PWR1 BSC •Examples – Local loop in telephone network BS3 –LAN Design BS3 BS2 BS4 BS2 BS4 BS1 – Multi-speed access design BS1 BS7 BS5 BS7 • Have multiple link speeds/types BS5 BS6 BS6 – For example, LAN design from variety of hosts – Multi-center Design • Cellular networks with multiple base station controllers TELCOM 2110 2 1
2. Access Network Design • For Multi-speed and Multi-Center network design need • Traffic Matrix – Specifies traffic between all source-destination pairs –Entry Tij is the traffic from source i to destination j – Source and destination maybe host, LAN, etc. – Developed in conceptual design- usually based on peak busy hour • Cost Matrix – Cost of link capacity Cij between nodes i and j – Cost may depend on traffic demand w needed C,ij(w) • Nodal Weight – The total traffic demand at a node TELCOM 2110 3 Backbone & Access Sites • Given a set of sites N and traffic i Mean data Dallas Denver Vienna matrix T, rate demands – weight(Ni) = Σj (Ti,j+Tj,i). – Weight of a site is the sum of all traffic in and out of the site Dallas 2.1 Mb .1Mb – Link Capacity needed is proportional to weight • Example of corporation in Dallas, Vienna, and Denver Denver .3 Mb .8Mb Weight(Dallas) = 2.2 + 2.8 = 5.0 Mbps Weight(Denver) = 1.1 + 1.6 = 2.7 Mpbs Weight(Vienna) = 4.0+ 2.9 = 6.9 Mbps Vienna 2.5 Mb 1.5 Mb TELCOM 2110 4 2
3. Backbone & Access Sites • Design Principle – Compute the weight of all the nodes to determine if there are natural traffic centers if the network is flat (i.e., no facility hierarchy – Example of corporation - Vienna has largest weight • Generally acceptable for small weight nodes to route their traffic via big weight nodes, but we do not want to route the traffic between big nodes via the small nodes • Not always obvious what is big and small node – Want large difference in weight between the big and small TELCOM 2110 5 Multiple Speed Access Design • Have a hub node to which demand nodes connected via multiple link types – i.e., different link capacities possible to interconnect to hub • Multi-speed Capacitated MST (MCST) problem • Intuitively, – tree should have thin links at the edge – Tree should have higher capacity towards the center (trunk of network) • Formulation/algorithm based on concept of predecessor and ancestor Root Reference R. Cahn, Wide Area Network Design: Concepts and Tools for Optimization 1 2 Morgan Kaufmann ,1998 Ch 5, 6 3 45 6 TELCOM 2110 6 3
4. Multiple Speed Access Design • Formulation/algorithm based on concept of predecessor and ancestor • A tree T rooted at a node Root can be represented uniquely by a predecessor function pred – The function pred( ) gives the node one hop closer to the root from the node in question – pred(6) = 3, pred(3) = 1, pred(1) = root, pred(4) = 2, etc. – pred2(6) = pred(pred(6)) = 1, pred3(6) = root •Definepred(root) = root • Given a tree T and the associated predecessor function, the ancestors of N are all the nodes N’ that are downstream from the node away from the root node. Root Ancestor(1) = {3,6} Ancestor(2) = {4,5} 1 2 Ancestor(3) = {6} (bit of a misnomer !) 3 45 pred n (N’) = N for some n > 0 6 TELCOM 2110 7 Multispeed CMST Problem • Given – set of nodes N0, N1, N2, , Nn. – set of weights (traffic demand) w1, w2, , wn for each node – set of link types L1, L2, , Lm – Set of capacities W1, W2, , Wm – cost matrix C(i, j, k) that gives the cost of a link of type Lk between Ni and Nj • Find: the tree rooted at N0 and the link assignments such that (i) Minimize ∑ C(i, j,l) l∈Links (ii) ∑ w(i) < WLink (N , pred (N )) i∈N ∪Ancestors(N ) TELCOM 2110 8 4
5. Multiple Speed CMST Problem • Consider Multi-speed capacitated MST problem constraint ∑ w(i) < WLink (N , pred (N )) i∈N ∪Ancestors(N ) • Capacity of upstream link can carry demand of downstream nodes Root For example link(2,0) 0 w2 + w4 + w5 < W(2,0) 2 For link(1,0) 1 w1 + w3 + w6 < W(1,0) Objective is the minimize link cost while 3 45 meeting demand requirements. 6 TELCOM 2110 9 Cahn’s Multi-speed Local Access Algorithm • Heuristic Algorithm to solve mCMST similar to Esau-Williams 1. Assign each node n the smallest link capacity Wl possible to directly connect it to the root. 2. For each node n, compute spare_capacity(n)=Wl -wn set pred(n)=0 where 0 denotes root 3. Calculate tradeoffs for each node n – Tradeoffn(i) is savings from linking node n to node i rather than linking directly to the root node 0. Tradeoffn(i)= C(n,i, l) + Upgrade(i,wn) – C(n,0, l ) – May have to upgrade links to carry additional traffic • Need to add un= max(0, wn - spare_capacity(i)) bandwidth • Upgrade(i, un) function determines the cost of adding un units to the links that connect i and 0. – Tradeoff of a node n is the minimum of all tradeoffs Tradeoff(n)= mini (Tradeoffn(i)) 4. Modify tree (add link to relay node/remove direct link to root) for node with minimum tradeoff among all nodes 5. Repeat 3 until all tradeoff values positive TELCOM 2110 10 5
6. MSLA Example Consider network with four access nodes to connect to a hub want a MAXIMUM link utilization of 50% Node Weight (kbps) Link Type Capacity 1 20,000 0 9.6 Kbps 2 2,400 1 56 Kbps 3 9,600 4 4,800 2 64 Kbps Link cost are a piecewise linear function of distance and data rate TELCOM 2110 11 MLSA Example Link Cost Matrices for each link type • Link Costs TELCOM 2110 12 6
7. MSLA Example • Step 1 Connect each node directly to root with minimum link capacity that meets design objective (i.e. 50% link utilization or less) • Initial Cost = 10+7+10+7 = 34 • Step 2 Calculate Spare Capacity L on each link (Max 0 Utilization=0.5) L0 L spare_capacity(1)=0.5*56000- 1 20000=8000 L spare_capacity(2)=0.5*9600- 1 2400=2400 spare_capacity(3)=0.5*56000- 9600=18400 spare_capacity(4)=0.5*9600-4800=0 TELCOM 2110 13 MSLA Example • Step 3 Calculate Tradeoffs for each node Tradeoffn(i)= C(n,i, l) + Upgrade(i,wn) – C(n,0, l ) Example node 1 L0 Tradeoff1(2)= C(1,2, l) + Upgrade(2,20000) – C(1,0, 1 ) L0 = 10 + (15-7) -10 = 8 L1 Tradeoff1(3)= C(1,3, l) + Upgrade(3,20000) – C(1,0, 1 ) L1 = 12 + (20-10) -10 = 12 Tradeoff1(4)= C(1,4, l) + Upgrade(4,20000) – C(1,0, 1 ) = 12 + (15 -7) -10 = 10 Tradeoff(1) = min{8,12,10} = 8 TELCOM 2110 14 7
8. MSLA Example • Step 3 Calculate Tradeoffs for each node For node 2 Tradeoff2(1)= C(2,1, l) + Upgrade(1,2400) – C(2,0, 1 ) = 7 + 0 - 7 = 0 L0 L0 Tradeoff2(3)= C(2,3, l) + Upgrade(3,2400) – C(2,0, 1 ) L = 5 + 0 -7 = -2 1 Tradeoff2(4)= C(2,4, l) + L1 Upgrade(4,2400) – C(2,0, 1 ) = 6 + (15 -7) -7 = 7 Tradeoff(2) = min{0,-2,7} = -2 TELCOM 2110 15 MSLA Example • Step 3 Calculate Tradeoffs for each node For node 3 Tradeoff3(1)= C(3,1, l) + Upgrade(1,9600) – C(3,0, 1 ) = 12 + (20-10) - 10= 12 L0 L0 Tradeoff3(2)= C(3,2, l) + Upgrade(2,9600) – C(3,0, 1 ) L = 12 + (15-7) -10= 10 1 Tradeoff3(4)= C(3,4, l) + L1 Upgrade(4,9600) – C(3,0, 1 ) = 10 + (15 -7) -10 = 8 Tradeoff(3) = min{12,10,8} = 8 TELCOM 2110 16 8
9. MSLA Example • Step 3 Calculate Tradeoffs for each node For node 4 Tradeoff4(1)= C(4,1, l) + Upgrade(1,4800) – C(4,0, 1 ) = 6 + 0 - 7 = -1 L Tradeoff4(2)= C(4,2, l) + Upgrade(2,4800) – 0 C(4,0, 1 ) L0 = 6 + (15-7) -7 = 7 L1 Tradeoff4(3)= C(4,3, l) + Upgrade(3,4800) – C(4,0, 1 ) L = 5 + 0 -7 = -2 1 Tradeoff(4) = min{-1,7,-2} = -2 Comparing the tradeoff values of all four nodes Tradeoff (4)=Tradeoff(2) = -2 arbitrarily pick Node 4 TELCOM 2110 17 MSLA Example Step 4 remove link from 4 to 0 And add link from 4 to 3 which is Iteration 1 It’s lowest tradeoff value node L0 L0 Iteration 1 topology L1 L1 Iteration 2: Note adjust node weights L0 Repeat tradeoff calculations L0 Result is Let N4 goes through N3,no Iteration 2 upgrade is needed and it is the best tradeoff value L1 Iteration 2 topology L1 TELCOM 2110 18 9
10. MSLA Example Iteration 2 L0 L0 L1 L1 L0 L0 • Iteration 3 results in connecting N3 to N1 Final and increase (1,0) to 256 Kbps link. design • All tradeoff values are positive - STOP L1 L2 TELCOM 2110 19 Larger Example of MSLA Algorithm: ‰We have 20 nodes in and the weights of the nodes are generated according to the above TABLE TRAFDIST. ‰Weights of nodes are shown in the TABLE SITES. Note that the weight of N0 is normalized so that it sums to the traffic from all the other sites. ‰To simplify the mathematics, we assume that every line can be used to 100% of capacity. TELCOM 2110 20 10
11. Esau Williams: 20 nodes with 9.6Kbps links Cost = $26,963 Only 9 sites share links to N0, more like a star. TELCOM 2110 21 Esau Williams: 20 nodes with 56Kbps links Cost = $30,160 A nice tree structure, but the cost is higher because out on the periphery of the network there is too much capacity. TELCOM 2110 22 11
12. MSLA: 20 nodes with multispeed links Cost = $22,760 There is a central D56 tree and a peripheral D96 tree TELCOM 2110 23 Access Design Problems AUC EIR • Can roughly categorize HLR IBM VLR access design problems MSC – One speed one center design SD Bay Net works Centi lli on 1400 ETHERLINK RS 232C INS ACT ALM P* 8x 50 RST OO130 A O N 6 PC CARD SD Bay Networks Centillion 1400 ALM PWR ALM AFN0FAN1PWR0PWR1 P* 8x 50 ETHERLINK S R 232C INS ACT ALM RST OO130 A O N 6 PC CARD ALM PWR ALM FAN0 FAN1 PW0R PWR1 BSC BSC SD • Capacitated MST problem Bay Net works Centi lli on 1400 P* 8x 50 ETHERLINK RS 232C INS ACT ALM RST OO130 A O N 6 PC CARD ALM PWR ALM AFN0FAN1PWR0PWR1 BSC – Esau-Williams algorithm BS3 – Sharma algorithm BS3 BS2 BS4 BS2 BS4 BS1 – Multi-speed access design BS1 BS7 BS5 BS7 BS5 BS6 • mCMST – MSLA BS6 – Multi-center Design • Multiple Centers (hubs) – nodes can connect to any center TELCOM 2110 24 12
13. MultiCenter Access Design •Given – A set B of hub or backbone sites {B0, , Bm} – A set N of access nodes {N1, , Nn} • A set of weights {w1, , wn} for each access node • A upper limit on capacity, W (one speed design). • A cost matrix Cost(i,j) giving the costs between each (hub) backbone/access pair of sites. • Build a set of trees that connect each access node to a hub • Constructing a forest of trees – often not interconnected TELCOM 2110 25 MultiCenter Local Access Problem (MCLA) • The multicenter local – access problem is to find a set of trees T1, , Tk such that (1) Exactly 1 backbone site belongs to each tree (2) The link capacity is not violated w < W ∑N ∈T i i j (3) The Cost is minimum C(Node1 , Node2 ) ∑Trees∑l∈ Links l l TELCOM 2110 26 13
14. Example Consider site with 3 backbone nodes Circles : X, Y and Z Have 17 access nodes Squares: A, B, C and D, etc Could represent host and Ethernet switches connected to campus backbone TELCOM 2110 27 MultiCenter Local Access Problem • This problem is a much more complex than the single-center one • Suppose we have n access nodes that we want to partition into sets of M nodes (i.e., one set for each backbone node. The number of possible partitions is : n ⎛ n ⎞ n−M ∑⎜ ⎟2 Even for the modest number n = 21, M = 7 M ⎝ M ⎠ the complexity is daunting . • After partitioning of the access sites must solve M capacitated MST problems (use Esau-Williams algorithm or Sharma algorithm) • How to partition into sets? TELCOM 2110 28 14
15. Nearest-Neighbor Esau-Williams (NNEW) • For each b in B, let Sb={ n∈N | Cost(n,b) < Cost(n,b’) ∀b’∈B} Group nodes in to sets based on nearest backbone node as judged by the direct connection cost • If n is equidistant between several backbone nodes, add n to one Sb at random. • Use Esau-Williams to construct a capacitated MST on each set b∪Sb. ‰ Example: A belongs to X set of nodes (since X is the closest backbone node to A) B to Y D to Z C is equidistant to X and Z so can be placed in either set. TELCOM 2110 29 Nearest-Neighbor Esau-Williams (NNEW) • Assume topology at right • B = {9,10,11} • N = {0,1,2,3,4,5,6,7,8} • Weight of each node is 1, except for nodes 4 and 5, which have weight 2 •Cost C(i,j) is given by the physical distance between nodes i and j • Capacity of link W = 3 • Step 1 is partition nodes into 3 sets using nearest-neighbor algorithm TELCOM 2110 30 15
16. Nearest-Neighbor Esau-Williams (NNEW) • Use Esau-Williams to construct a capacitated MST on each set Sb • Backbone nodes connected separately TELCOM 2110 31 Test of Quality of Design • Test: reattach the leaves to a different tree and see if it reduces the cost. • The quality of NNEW is not that great TELCOM 2110 32 16
17. Nearest-Neighbor Esau-Williams (NNEW) • NNEW algorithm doesn’t always work well • Problem is the location of the other access nodes cannot be ignored when deciding which access nodes should home to which center. • Example two hubs (N1, N2), cheaper design if N5 connects through N9 to N2 - but nearest neighbor prohibits this. TELCOM 2110 33 MultiCenter Esau-Williams (MCEW) • Recall that, in Esau-Williams algorithm – Calculate the tradeoff as the saving by linking Ni to Nj instead of linking it directly to the center/root. Tradeoff(Ni) = minjCost(Ni, Nj) - Cost(Comp(Ni),Center) • MCEW algorithm replaces the tradeoff function with: Tradeoff(Ni) = minjCost(Ni, Nj) - Cost(Comp(Ni),Center(Ni)) • Initially, we set Center(Ni) to be the closest backbone center. • If node Ni is merged with node Nj, update Center(Ni)=Center(Nj). • MCEW has an advantage over NNEW when size of nodes in clusters large TELCOM 2110 34 17
18. NNEW vs. MCEW • Only a slight cost advantage of using MCEW as opposed to NNEW. • Test of quality show MCEW has better solution TELCOM 2110 35 Access Design Problems • Looked at three access design problems – One speed one center design • Capacitated MST problem – Esau-Williams algorithm – Sharma algorithm – Multi-speed access design • mCMST – MSLA – Multi-center Design • NNEW, MCEW • Solution algorithms not cast in stone – often need to add constraints to improve design or make practical TELCOM 2110 36 18
19. Some Branches Have Too Many Nodes. • EW tests only if the combined weight of the two components doesn’t exceed the upper bound weight_limit. • Solution: add additional size_limit constraints that prohibit the merge of two components with too many nodes. TELCOM 2110 37 Some Branches Have Too Many Hops. • Branch with many hops => large delay variation and less reliable • Solution: add depth checking constraint – a hop count limit, i.e., depth-limit the tree built by EW ‰ Each site maintains a value depth[ni] ‰ Initially set to 1, update when we evaluate the tradeoff between n1 and n2, Depth[n2] = max (depth[n2], depth[n1] +1) and compare against threshold. TELCOM 2110 38 19
20. Some Node in Tree Has Too Many Links ‰ Degree of node directly relates to port count, may want to keep port count below a given value • Solution: add degree constraint ‰ Initialize the degree of each site to 1, when we accept the merge from n1 to n2 then we increase the degree of n2 by 1. Do not accept merges that violates the constraint. TELCOM 2110 39 Access Design Problems • Looked at three access design problems – One speed one center design – Multi-speed access design – Multi-center Design • Studied algorithms for each case • Useful for logical layer design • Next consider physical design of access networks. TELCOM 2110 40 20