Network Design - Chapter 12: WAN Network Design II - University of Pittsburgh

Nội dung text: Network Design - Chapter 12: WAN Network Design II - University of Pittsburgh

1. WAN Network Design II Telcom 2110 Network Design University of Pittsburgh Slides 12 WAN Packet Network Design • Many algorithms - optimization formulations for WAN packet network design • Commercial tools – VPIsystems, WANDL, OPNET, etc. • Basic approaches – Design topology – then route traffic – Route traffic – then capacitate design – Joint Optimization –Hybrids TELCOM 2110 Spring 06 2 1
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 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 4 2
3. 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: g112( xx,K xn ) {≤≥= , ,} b 1 g212(){}xx,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 5 Optimization Based Network Design Procedure Input Data ¾ Node Locations ¾ Potential Links ¾ Traffic Demands ¾ Cost function/parameters Network Design Optimizer Find working path Find backup Survivability for traffic paths for given demands failure scenarios requirements Network design strategy/ Network optimization model Network topology & Technology, QoS Link capacity assignment requirements, etc Output Results ¾ Network Cost ¾ Network Topology ¾ Capacity of Links ¾ Working Paths ¾ Backup Paths TELCOM 2110 Spring 06 6 3
4. Virtual Private Network • A Virtual Private Network (VPN) refers to “ A class of service that use a shared network to emulate the characteristics of a private network.” • Private link emulation over a shared infrastructure – Leased virtual trunks in circuit switched telco network – Virtual Path network over ATM backbone – Virtual LAN over Fast Ethernet infrastructure – Virtual IP WAN network over IP/MPLS infrastructure • Transparency between provider and customer network. • Full-mesh trunks are usually created for a VPN over a backbone. TELCOM 2110 Spring 06 7 VPN Networks Concept of a transport network: one physical network many VPN logical network possibilities through cross- connects, routing etc. K B C D A Z TELCOM 2110 Spring 06 8 4
5. VPN Overlay Network Overlay VPN B Network C A B2 B3 B1 Service Provider C1 Network C2 C3 A1 A2 TELCOM 2110 Spring 06 9 Basic VPN Network Design • Goals of VPN network design same as general network design – just an overlay connecting a subset of network nodes – 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. –Variations • Only difference is physical topology defined – multiple VPNs are usually deployed • Consider MPLS case TELCOM 2110 Spring 06 10 5
6. MPLS Background • Multi-Protocol Label Switching (MPLS) is expected to be used over IP infrastructure to deliver QoS performance to different service classes, provide security, VPNs • MPLS use a label-swapping forwarding technique. • Labels are assigned when the packet enters into the network. • MPLS routers forward packets based on the label value. • Fields: Label, Class of Service, Stack bit, Time-to-Live 0 20 32 Label CoS S TTL IP header MPLS header TELCOM 2110 Spring 06 11 MPLS Network “ Packet Classification ” 12 TELCOM 2110 Spring 06 12 6
7. MPLS Packet Forwarding In In Address Out Out In In Address Out Out I/F Lab Prefix I/F Lab I/F Lab Prefix I/F Lab 4 X 171.68.10 3 5 0 5 171.68.10 1 3 MPLS Network 171.68.10 / 24 LSR - A LSR - B LSR - C IP packet Label=5 Label=3 171.68.10.12 IP packet IP packet 171.68.10.12 171.68.10.12 13 TELCOM 2110 Spring 06 13 Forward Equivalent Class • Packets entering MPLS domain will be classified into different Forward Equivalent Class (FEC). • FEC can be defined to distinct granularity of packet forwarding decision – Destination-based (unicast) routing – Multicast routing – Traffic engineering – VPNs –QoS – Security, etc • Different levels of traffic aggregation are possible. – Aggregate traffic based on its IP destination pre-fixed. – Aggregate traffic based on its egress node. – etc TELCOM 2110 Spring 06 14 7
8. Label Assignment and Distribution • Labels have local significance • Labels are assigned and exchanged between adjacent LSRs from downstream to upstream direction. - Unsolicited downstream LSRs assign a label to each FEC and distribute labels to all its upstream neighbors. - Downstream on demand For each FEC, upstream LSR request label binding to its downstream LSRs. • In MPLS, A forwarding path can be a sink-tree path or a multipoint-to-point path ending at an egress node. TELCOM 2110 Spring 06 15 Downstream on Demand Label Assignment Use label 5 for Use label 3 for Destination 171.68.10 / 24 Destination 171.68.10 / 24 171.68.40 / 24 171.68.10 / 24 LSR - A LSR - B LSR - C Request label for Request label for Destination 171.68.10 / 24 Destination 171.68.10 / 24 16 TELCOM 2110 Spring 06 16 8
9. Label Switched Path • A label-switched path (LSP) is a path through which packets of a particular FEC will be forwarded. • Two types of LSPs 1. Prefixed-based ¾ LSPs created based on “route” advertisement ¾ Controlled by routing or signaling ¾ Traditional IP-OSPF routing ( No QoS or CoS support ) 2. Tunnel based ¾ LSPs created between specific MPLS end-points ¾ Controlled by signaling (RSVP-TE, CR-LDP) ¾ Used for traffic engineering, QoS provision, VPN service, etc • LSPs are always unidirectional TELCOM 2110 Spring 06 17 VPN over MPLS backbone • MPLS is expected to be used over the IP infrastructure to deliver QoS performance to different classes of service (CoS). • Using explicit path setup in MPLS, a QoS-based VPN can be efficiently built over the infrastructure. • Different FECs may be used to classify traffic from different VPNs which may or may not – use the same forwarding path. – share the same portion of network bandwidth. TELCOM 2110 Spring 06 18 9
10. Logical Network Topology Provider Edge (PE) Router Provider Core Router C Overlay A VPN Network B Service Provider IP/MPLS Network TELCOM 2110 Spring 06 19 Point-to-Point LSPs Provider Edge (PE) Router Provider Core Router C Label Switch Path (LSP) Overlay A VPN Network B 1 2 Service Provider 5 MPLS Network 3 4 6 TELCOM 2110 Spring 06 20 10
11. Multipoint-to-point LSPs Provider Edge (PE) Router Provider Core Router C Label Switch Path (LSP) Overlay A VPN Network B 1 Service Provider 2 MPLS Network 3 “ Shared-BW links” TELCOM 2110 Spring 06 21 VPN Design Problem • Given – Physical network topology – Link capacity and its cost – VPNs requirements (i.e., traffic demands, QoS) • Find the optimal logical sink-trees and their dimension such that – Objective : • Minimize (total virtual network cost, number of LSPs) – Constraints : • QoS requirements (packet-level parameters) • GoS requirements (call-level parameters) • Link capacity limitation TELCOM 2110 Spring 06 22 11
12. VPN Design Procedure • Three main tasks 1)Path generation • Candidate tree(s) generation • Feasible tree(s) selection 2)Virtual link dimensioning • Logical link bandwidth sizing of a given demand. 3)Network routing optimization • Route selection for each VPN logical link TELCOM 2110 Spring 06 23 Tree Selection • Possible set of 1 candidate trees Depth = 1 – All distinct spanning 2 3 4 n trees (i) Sink-tree with 1-hop depth – Steiner trees n spanning over M ⊆ N nodes 3 – Disjoint shortest-path Depth = n-1 trees 2 1 (ii) Sink-tree with (n-1)-hop depth TELCOM• Feasible2110 Spring 06 trees selection 24 12
13. Link Dimensioning ‹ “Effective bandwidth” calculation will be used to determine the link capacity requirement at each link. ‹ For example, Assured Service traffic with source characteristic (Source peak rate- , Utilization factor-ρ , Mean burst period-b ) R peak Equivalent capacity estimation for each source cˆi a −1+ ()a −1 2 + 4ρ a cˆ = R i peak 2a where b a = − ()1− ρ lnε B Packet loss ratio Buffer size TELCOM 2110 Spring 06 25 Link Dimensioning (cont.) ‹ At a merged link, an aggregated bandwidth will be determined. For η traffic connections multiplexed ˆ Allocated BW : C ≤ η ∗ Rpeak ˆ C = min {η ⋅m +α′⋅σ , η ⋅cˆi} α′ = − 2 ln(ε ) − ln(2π ) Packet loss ratio ‹ Bandwidth and LSPs efficiency is achieved when traffic is merged into the same pipe. TELCOM 2110 Spring 06 26 13
14. General Case • Mathematical models for VPN design problem are needed for a traffic demand matrix of – Multiple VPNs. – Multiple service classes. – Multi-hour period. • Point-to-point traffic demand is considered. • A traffic demand is classified/routed based on an exit node. • Two cases : – No bandwidth aggregation – Bandwidth aggregation is possible when traffic is merged/multiplexed on a sink-tree paths. TELCOM 2110 Spring 06 28 Special Case • Simplified formulations can be derived from general case models – One VPN traffic class – Single service class. – One-hour period. • Point-to-point traffic demand. • A traffic demand is classified/routed based on an exit node. TELCOM 2110 Spring 06 29 14
15. Mathematical Formulation ψ ∗Y Minimize ∑ l l Total VPN capacity cost l∈L Given αl , Cl Link utilization factor , Maximum link capacity d Dk , Bk Traffic demand , Bandwidth requirement l Pk , γ p, d Set of precomputed sink-tree paths , Link path incidence matrix Obtain Yl Link BW allocations p X k Routing path 32 TELCOM 2110 Spring 06 32 Special Case (without BW aggregation) Formulation-III ψ ∗Y Minimize ∑ l l Total VPN capacity cost l∈L Subject to : Path selection criteria p ( 1 ) ∑ X k = 1 ; for all k ∈ K p∈Pk Link capacity requirement ⎛ ⎞ Eqv Bd , T, QoS ∗ ⎜ γ l ∗ X p ⎟ ≤ Y ( 2 ) ∑∑()k ⎜ ∑p, d k ⎟ l k ∈∈K d D p ∈P k ⎝ k ⎠ ; for all l ∈ L Link capacity limitation ( 3 ) Yl ≤ αl ⋅ Cl ; for all l ∈ L 33 TELCOM 2110 Spring 06 33 15
16. Special Case (with BW aggregation) Formulation-IV ψ ∗Y Minimize ∑ l l Total VPN capacity cost l∈L Subject to : Path selection criteria p ( 1 ) ∑ X k = 1 ; for all k ∈ K p∈Pk Link capacity requirement ⎛⎛ ⎞ ⎞ ⎜⎜ d l p ⎟ ⎟ ∑∑Eqv ∑ B ∗ γ ∗ X , T, QoS ≤ Yl ; for all l ∈ L ( 2 ) ⎜⎜ k p, d k ⎟ ⎟ k∈∈K ⎝⎝ d∈Dk p Pk ⎠ ⎠ Link capacity limitation ( 3 ) Yl ≤ αl ⋅ Cl ; for all l ∈ L 34 TELCOM 2110 Spring 06 34 Numerical Study • The design model is a mixed Integer programming problem of NP-hard type. • The problem is translated using AMPL model description language and solution is obtain using CPLEX 6.6 solver. • Benchmark is obtained for a small network where LP bound is easy to establish. TELCOM 2110 Spring 06 35 16
17. Tested Networks 8-node Network 10-node Network TELCOM 2110 Spring 06 36 Sample Results Topolo Full-Mesh Design Sink-Tree(s) Design Sink-Tree(s) Design gy (w/o BW aggregation) (with BW aggregation) Optim Simplex No. Optim Simplex No. of Optim Simplex No. of al Iteration of al Iteration LSPs al Iteration LSPs Cost s LSPs Cost s Cost s 8-node 104 54 56 104 241 8 56 473 8 10- 174 65 90 174 736 10 90 1503 10 node TELCOM 2110 Spring 06 37 17
18. Multiple VPN Design Problem • Given – Physical network topology – Link capacity and its cost – Number of VPNs and their requirements • Traffic demands , QoS, etc. May have 100 or 1000s of VPNs to provision over infrastructure • Find the logical layout and their dimension such that – Objective : • Minimize (total virtual network cost, number of LSPs) – Constraints : • QoS requirements (packet-level parameters) • GoS requirements (call-level parameters) • Link capacity limitations TELCOM 2110 Spring 06 42 Multiple VPN Overlays TELCOM 2110 Spring 06 43 18
19. Multiple VPN Design Problem • Heuristic Solution 1. Assign each VPN a weight = Sum (traffic demand x distance) 2. Sort VPNs on weight 3. Use a standard algorithm to layout VPN i (Mentor, Routing approach, optimization formulation, etc.) 4. Subtract VPN i bandwidth requirements from physical network capacity where used. 5. Repeat step 3 and 4 until all VPNs are provisioned. – Note VPNs with small weight are likely to have non- shortest path routes through the physical network. TELCOM 2110 Spring 06 44 19