Network Design - Chapter 13: WAN Network Design III - University of Pittsburgh

Nội dung text: Network Design - Chapter 13: WAN Network Design III - University of Pittsburgh

1. WANWAN NetworkNetwork DesignDesign IIIIII Telcom 2110 Network Design University of Pittsburgh Slides 13
2. Basic WAN Network Design • Minimize total cost • Subject to Constraints for example – Link capacity must exceed some min, and be less than some max – Average Packet Delay must be < maximum – Reliability requirements – Throughput, etc. • General goals – Short path between all sources and destinations. – Well-utilized components with high speed lines to achieve economy of scale. – These are somewhat contradictory goals TELCOM 2110 Spring 06 2
3. WAN Network Design • WAN typically have a backbone/edge structure • Backbone is almost always a mesh or ring design • Mesh topologies introduce the problem of routing traffic • Many optimization formulations and design tools for WAN network design – Optimization Techniques usually form the initial basis of the formulation – Often use a heuristic or meta-heuristic solution technique • Formulation depends – Network layer (e.g., WDM, SONET, MPLS, etc.), – Technology, – QoS requirements – Reliability goals – Other constraints TELCOM 2110 Spring 06 3
4. Optimization Based Design • Good Reference is M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kauffman 2004 Maximize (or minimize): f (x1, x2 Kxn ) Objective Subject to: gxx112( ,K xn ) {≤≥= ,,} b 1 gxx212(){},K xn ≤≥= ,, b 2 Constraints gmn( xx12,K x) {≤≥= ,,} b m wherex1, x2 Kxn are the decision variables Formulations usually either • Linear Programming problems (objective and constraints linear) • Integer Programming problems (linear objective and constraints but integer design variables) • Mixed Integer Programming problems • Nonlinear MIPs, etc. TELCOMTelcom 2110 2110 Spring Spring 06 2006 7 4
5. Simple Design Problem • indices – d=1,2, ,D set of demands (source-destination pairs) – p=1,2, ,Pd possible paths for flows of demand d – e=1,2, ,E links • Input parameters (constants) –hd offered traffic load of demand d –ce upper bound on capacity of link e – ξe unit (marginal) cost of link e – δedp = 1 if e belongs to path p realizing demand d; 0, otherwise • variables –xdp flow of demand d on path p –ye capacity of each link TELCOM 2110 Spring 06 6
6. Capacitated flow allocation problem LP formulation • Objective: minimize F(y)= Σe ξeye • constraints Σp xdp = hd d=1,2, ,D Σd Σp δedpxdp ≤ ye e=1,2, ,E ye ≤ ce e=1,2, ,E – flow and capacity variables are continuous and non-negative xdp ≥ 0, ye ≥ 0 LP problem solve using Simplex method Many variations to tailor to network design TELCOM 2110 Spring 06 7
7. Modular Link Capacity Flow Allocation • Modular Link capacity • Additional Input Parameter • M – size of link capacity module (T1, DS3, etc.) • Objective: minimize F(y)= Σe ξeye • constraints Σp xdp = hd d=1,2, ,D Σd Σp δedpxdp ≤ Mye e=1,2, ,E Mye ≤ ce e=1,2, ,E – flow variables are continuous and non-negative xdp ≥ 0, capacity variables are non-negative integers ye ≥ 0 MIP problem solve using Branch and Bound TELCOM 2110 Spring 06 8
8. Single path for traffic Flows • Many variations possible based on adding/modifying constraints for example • Force traffic to a single path so the traffic is not bifurcated • Additional variables udp binary flow variable corresponding to demand d and path p • Constraints (1) and (2) become Σp udp = 1 d=1,2, ,D Σd Σp δedphdudp ≤ Mye e=1,2, ,E – u binary, ye integers TELCOM 2110 Spring 06 9
9. Circuit Switched Design Problem • indices – d=1,2, ,D set of demands (source-destination pairs) – p=1,2, ,Pd possible paths for flows of demand d – e=1,2, ,E links • Input parameters (constants) –hd offered traffic load of demand d in Erlangs – M modular capacity of link e – ξe unit modular capacity cost on link e –be call blocking requirement on link e – δedp = 1 if e belongs to path p realizing demand d; 0, otherwise • variables –xdp flow of demand d on path p –ye capacity of each link in terms of number of modules M TELCOM 2110 Spring 06 10
10. Digital Circuit Switched Design with Modular Capacity • Objective: minimize F(y)= Σe ξeye • constraints Σp xdp = hd d=1,2, ,D Fe(Σd Σp δedpxdp) ≤ Mye e=1,2, ,E – flow variables are continuous and non-negative xdp ≥ 0, capacity variables are non-negative integers ye ≥ 0 Where Fe(a) is the inverse of the Erlang Blocking formula for offered load a and blocking be Many more technology based formulations given in M. Pioro and D. Medhi book - posted sample formulations on class web page Thus far talked about Mesh networks TELCOM 2110 Spring 06 11
11. Ring vs Mesh Architectures Advantages of Rings: • More cost efficient at low traffic volumes • Fast protection switching, some capacity sharing Advantages of Mesh: • More cost efficient at high traffic volumes • Facilitates capacity and cost efficient mesh restoration • More flexible channel re- configuration TELCOM 2110 Spring 06 12
12. Self-healing Rings (SHRs) • SHR is a topology connecting a set of nodes by one (or more) rings. • Two types of SHRs : – Uni-directional ring (USHR) • Nodes are connected to two rings forwarding traffic in opposite direction. – Bi-directional ring (BSHR) • Four rings are used as two working and two standby routes. • An extension of 1:1 Automatic Protection Switching TELCOM 2110 Spring 06 13
13. USHR USHR also called Unidirectional Path-switched Ring Unidirectional - because in normal operation all working demand flows in one direction only. i.e., A sends to B clockwise, B also sends to A clockwise Path-switched - because in restoration each receiver selects an alternate end-to-end path through ring, regardless of where actual break occurred. Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 15
14. USHR Animation Working fibre 1 Tail-end Switch 5 2 Protection fibre 3 4 λ1 Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 16
15. USHR Capacity Requirement A A -> B • Consider a bi-directional demand quantity between nodes A, B: d . E B A,B - A to B may go on the short route - then B to A must go around the longer route B -> A • Thus, every (bi-directional) demand pair D C circumnavigates the entire ring. • Hence in any cross section of the ring, we would find one unidirectional instance of every demand flow between nodes of the ring. “ The UPSR must have a line rate (capacity) greater (or equal to) • Therefore, the line capacity of the UPSR the sum of all the (bi-directional) must be: demand quantities between nodes of cdUPSR≥ ∑ ij the ring. “ ij> Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 17
16. BSHR Loop Back Cable cut (a) Normal Operation (before failure) (b) Protection Operation (after failure) TELCOM 2110 Spring 06 18
17. BSHR Bi-directional - because in normal operation working demand flows travel in opposite directions over the same Loop Back route through the ring Cable cut Also called Bi-directional Line-switched Ring (BLSR) (a) Normal Operation (before failure) (b) Protection Operation (after failure) Line-switched - because in restoration the composite optical line transmission signal is switched to “ The BLSR must have a line rate the other direction around the ring (on the other fibre pair) (capacity) greater (or equal to) specifically around the failed section. the largest sum of demands routed over any one span of Note implication: Protection fibre capacity must equal the ring. “ the largest-working capacity cross-section of any span on the ring. TELCOM 2110 Spring 06 19
18. BSHR Working fibres 1 Loop-back 5 2 Protection fibres 3 4 λ1 Loop-back Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 20
19. SHRs Restoration Capability •USHR – 100% restoration for a single link failure but no protection against a node failure. •BSHR – 100% restoration for a single link or ADM failure. – Fully automatic for a fast restoration. – Spare capacity of each link can be shared between two working paths. – Expensive. TELCOM 2110 Spring 06 21
20. SHRs Interconnection Architecture • Due to geographical/bandwidth limitation, multiple, interconnected rings are deployed. • Multi-Ring network design • Capacity assignment at all links on the ring can needs to be minimum. • For traffic restoration, a larger logical self- healing ring can be formed from an interconnection of two or more rings. TELCOM 2110 Spring 06 22
21. Two possible Ring Interconnections TELCOM 2110 Spring 06 23
22. DCS Backbone Network ADM ADM ADM DCS DCS DCS Ring DCS DCS ADM ADM ADM TELCOM 2110 Spring 06 24
23. Dual-ring Interconnect When connecting two rings at a transit node want to have redundancy – several methods Below is drop-and-continue method for BSHRs C 5 C (primary) C the primary gateway 1 3 node has a 1+1 receive 1A 3A selection setup here. r r 1 2 C C 2 (secondary) 4 2A 4A protected by protected by protected by BLSR line-loopback 1+1 APS inter-ring BLSR line-loopback reaction in r1 setup reaction in r2 TELCOM 2110 Spring 06 25
24. Rings • SONET rings operate at OC-n line rates and the STS-1 tributaries are the “channels” • The nodes of a ring are equipment called “Add-Drop Multiplexers”(ADMs) • SONET rings may have a maximum of 16 active nodes, plus “glass-through” sites •“Glass-throughs” are just nodes transited by the ring, but where no ADM is present • “Glass-throughs” may be simply fiber splices or a regenerator point (“pass throughs”) • Demand splitting refers to whether or not the total demand exchanged between two nodes has to be kept together on the same route of a ring or can be ‘split’ • Time slot interchange (TSI) refers to whether the ADMs have the ability to cross- connect timeslot contents (assign a new time slot to a demand on the next span) • More recent Optical rings have a DWDM optical line signal and add / drop single wavelengths or wave-bands - the logical “channel” is a wavelength (λ) or waveband - UPSR OPPR (Optical Path Protection Ring) - BLSR OSPR (Optical Shared Protection Ring) - ADM OADM - TSI (Time slot interchange) λ conversion TELCOM 2110 Spring 06 26
25. Multi-ring Design Problem • Given: - a two-connected (or bi-connected) graph - a set of “ring technologies” and costs. e.g OC-192 4/BLSR, OC-48 UPSR, etc including 1+1 APS - a set of demands to be served. - a subset of node locations where demands may transit from ring-to-ring • Determine: - the number, size, type and placement of all rings - the location of glass-throughs (and ADM terminals) on all rings - the end-to-end routing of each demand That results in minimal cost of all rings placed, including costs associated with demands transiting from ring to ring. Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 27
26. On the complexity of multi-ring design • Upper bound on number of ring candidates to consider: logic: Every combination of 2, 3, 4 up to N nodes defines a prospective collection of active ADM nodes that could be grouped together to define one ring. N ⎛⎞N N QN≈≤−−∑⎜⎟21 i=2 ⎝⎠i • Upper bound on the number of different multi-ring designs that exist: logic: Now, every combination of 1, 2, 3, 4 up to some pre-determined maximum number of rings can be considered for feasibility and cost as a multi-ring design solution. - in ideal case of rings with no capacity limit, can show that more than N-1 rings not needed. N −1⎛⎞Q →Θ≥∑⎜⎟ and also multiply by the number of “ring technologies” j=1 ⎝⎠j being considered. TELCOM 2110 Spring 06 28
27. Question: How big is Θ? 70 10 60 10 50 10 40 10 30 10 20 No. of Possible Designs 10 10 10 0 10 3 4 5 6 7 8 9 10111213141516 No. of Nodes illustration: a 10 node network: 1013 possible rings, 1021 possible multi-ring networks (over 100 million years to evaluate all designs at 10 6 design evaluations / sec.) ! TELCOM 2110 Spring 06 29
28. Key concepts in multi-ring design Concept • graph coverage: a set of rings that covers every edge of the graph. This is one class of ring network. in a BLSR, how well are the w quantities “balanced” ? (since • Balance i the largest of them dictates the protection capacity). to what extent does a given ring tend to serve demands that • Capture both originate and terminate in the same ring. a multi-ring design may not “cover” all graph edges, • Span elimination if the working demands can take non-shortest path routes. for the highest service availability, some demands may employ • Dual-ring interconnect geographically redundant duplicate inter-ring transfers • transit sites not all nodes may be sites where demands can switch rings. each ring needs ADMs where demands add / drop, but not •glass-throughs elsewhere ( ~> Express rings etc.). TELCOM 2110 Spring 06 30
29. Graph coverage • a set of rings that uses or overlies all edges of the physical facilities graph is called a “ring cover”. • “Coverage-based” design is a special (simpler) case of multi-ring design. • More generally the aim is to protect all demands, not necessarily to “cover all spans.” “span eliminations” example a single ring design a three ring “cover” that may also serve all demands Q. what is implied? Source: W. D. Grover, ECE 681, UofA, Fall 2004 TELCOM 2110 Spring 06 31
30. Net Solver (Gardner, et al., Globecom ‘95) • Objective – Find min-cost ring design that serves all demands. • Key Assumptions & Constraints – Cost is calculated based on fixed and variable costs. – Requires an initial ring design. – Ring capacity is fixed and modular (rings not “ideal”). • Methodology 1. Route demands over the initial set of rings using either (1) shortest path, (2) shortest ring transition, or (3) minimum congestion routing (user-defined). 2. Compute the total cost of the initial design. 3. Generate a set of alternative ring designs by modifying the initial ring design using three different ring operations: (1) split; (2) merge; and (3) enlargement. TELCOM 2110 Spring 06 32
31. Net Solver • Ring Operations R R1 R2 (a) Split operation R1 R R2 (b) Merge operation R R’ (c) Enlargement operation TELCOM 2110 Spring 06 33
32. Net Solver (cont’d) • Methodology (cont’d) 4. Route demands and compute the total cost for each alternative design. 5. Select the design with the lowest total cost. 6. Repeat steps 3-5 until no further improvements in cost can be obtained. • Capabilities – BLSR, UPSR and mixed designs. – Accounts for fixed ring capacities. – Identifies the location of active/passive nodes and demand routing. TELCOM 2110 Spring 06 34
33. Optimization Formulation Notation demands and routing J - set of candidate rings (BLSRs). K - set of all demands. S - set of spans in the network topology. dk - size of demand bundle k. costs & capacities I - set of routes for all demands. bij - add/drop cost of carrying route i on ring j. Fi - flow of working route i. c j - “fixed cost” (optical line costs) of ring j. Gij - flow of route i carried by ring j. ei - termination cost for route i. ws - working load on span s. m j - capacity of BLSR j. decision variables X j - copies of candidate ring j in design. TELCOM 2110 Spring 06 35
34. Pure span coverage IP • Span Coverage (SCIP) 1. Route demands over network topology and calculate working load ws on each span. 2. Generate a set of ring candidates (topology, ring type and capacity) and calculate ring candidate costs. SCIP Minimize: (1) ∑c j X j j∈J Subject to: ∑ m j X j ≥ ws ∀s ∈ S (2) j∈J ()s , X j ≤ 0 integer, ∀j ∈ J (3) , TELCOM 2110 Spring 06 36
35. “Fixed Charge and Routing” • Fixed Charge and Routing (FCIP) 1. Generate a set of several possible routes for each demand. 2. Generate a set of ring candidates (topology and ring type) and calculate ring candidate costs. FCRIP Minimize: ∑c j X j + ∑ ∑bijGij (1) j∈J ii∈∈I j J ( ) (2) Subject to: ∑ Fi = dk , ∀k ∈ K i∈I (k ) (3) ∑Gij ≥ Fi ,,∀i ∈ I ∀s ∈ S j∈J (s) (4) ∑Gij ≤ m j X j , ∀j ∈ J, ∀s ∈ S i∈I (s) TELCOM 2110 Spring 06 37
36. Understanding “Fixed Charge and Routing” approach Key idea: Solver is free to choose rings are routing of flows jointly, to min cost of rings plus inter-ring add/ drop transition costs (3) amongst “stacked” ring spans allocation of D each ring’s portion of flow sums to total on the given route for that O-D pair ring jJ∈ (“fixed” optical line cost) three possible routes for demand pair k, I(k) route O ring jJ∈ and flow add/ drop for other costs (2) sum of flow F(i) to each sp an demand s routing dependent route I(k) = dk pairs add/ drop costs (4) capacity greater than sum of flows crossing span TELCOM 2110 Spring 06 38
37. Numerical Comparison 1 5 10 0 • Test Networks 2 9 3 4 3 2 4 11 15 13 19 15 14 7 Metro 7 10 6 14 9 11 8 6 12 17 5 13 12 1 18 16 8 Net15 Net20 29 40 10 39 12 3 30 13 11 26 27 38 15 42 1 28 22 21 14 17 20 5 33 43 16 11 2 12 15 7 16 18 22 23 10 4 27 19 41 3 14 32 26 24 6 17 Long-haul 24 28 1 21 31 13 36 37 29 4 32 8 6 18 8 25 31 5 25 2 30 9 7 9 23 20 19 35 34 Net32 Net43 TELCOM 2110 Spring 06 Source: W. D. Grover, ECE 681, UofA, Fall 2004 39
38. Numerical Results • Modeling Assumptions – Ring types: 12-λ OSPR and 48-λ OSPR. – Cost model: 4 times capacity for twice the cost. – No restrictions on inter-ring transition locations. • Experimental Procedure 1.Formulated each IP in AMPL mathematical programming language. 2.Populated AMPL data sets. 3.Generated problem instances using AMPL and solved with CPLEX. 4.Entered solutions into SONET Planner (Nortel Networks) to obtain final detailed costing. TELCOM 2110 Spring 06 40
39. Results Cost ($000s) RingBuilder SCIP FCRIP Net15 6,535 5,810 7,187* Net20 9,886 10,083 8,953* Net32 91,596 90,291 96,368* Net45 116,674 130,100* - * - time limit exceeded, best feasible solution shown. TELCOM 2110 Spring 06 41
40. Results (cont’d) Runtime* (seconds) RingBuilder SCIP FCRIP Net15 6.2 1.6 43,200 Net20 10.5 38.7 43200 Net32 8.5 361 43,200 Net45 1,233 43,200 - 43,200 sec = 12 hour run-time limit TELCOM 2110 Spring 06 42