›
›

Network Design - Chapter 11: WAN Network Design - University of Pittsburgh

pdf 32 trang hoanguyen 3450
Download
Bạn đang xem 20 trang mẫu của tài liệu "Network Design - Chapter 11: WAN Network Design - University of Pittsburgh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfnetwork_design_chapter_11_wan_network_design_university_of_p.pdf

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

  1. WAN Network Design Telcom 2110 Network Design University of Pittsburgh Slides 11 WAN Network Design •Given – Node locations (or potential locations) – Traffic Demand (mean, peak, etc) – Performance Goals (blocking rate, delay,etc.) • Determine Topology – Link/node location – Link capacity – Traffic Routing TELCOM 2110 Spring 06 2 1
  2. WAN Network Design •Design Variables • Network Topology (possibly facility location as well) • Channel Capacity • Routing Policy •Performance Metrics depends on network application and layer • Circuit Switched Network •Call Blocking, Availability • Packet network • Delay • Delay Jitter • Throughput • Packet Loss TELCOM 2110 Spring 06 3 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 4 2
  3. Example of Tradeoffs/Designs • Consider an example to see design issues/tradeoffs all designs use same algorithm with different parameter settings • 45 nodes labeled N1-N45 • 2 large data centers, N1 and N45. Each data center terminates and sends 1 Mbps. • 4 data servers, N2, N3, N43, and N44. Each data server sends and receives 150 Kbps. • The remainder of the sites are small. Each sends and receives 25 Kbps. • Assume link costs are greater than node costs • The links available: TELCOM 2110 Spring 06 5 Example Design 1 Tree type of design, cost reduced to $133,584/month. The average number of hops, 7.84, is high. Design has only high speed links (T1 and 256Kbps lines) Poor reliability TELCOM 2110 Spring 06 7 3
  4. Example Design 2 Two level design – backbone with edge nodes Data centers and servers are interior nodes of the backbone tree. Cost reduced to $96,777; average hops= 3.41 Reliability poor – if backbone link failure – large impact TELCOM 2110 Spring 06 8 Example Design 3 Instead of tree, interior (backbone) nodes are connected with high-speed links to form a 2-connected graph. Cost = $ 112,587/month, better reliability TELCOM 2110 Spring 06 9 4
  5. Example Design 4 Alternate 2 connected backbone design with slightly lower cost $112,587Æ$108,724 per month TELCOM 2110 Spring 06 10 Can Cost Be Reduced Further? • We will look for costs improvements by expanding the backbone. • Look at the $112K Example 3 Design: • There are 2 large clusters centered at N2 and N45. • Can we locate a new backbone in these clusters and reduce the cost? TELCOM 2110 Spring 06 11 5
  6. Example Design 5 Adding more backbone nodes by placing 2 concentrators at N10 and N13 lowers the cost to $103,107/per month Ring like backbone structure TELCOM 2110 Spring 06 12 Example Design 6 Expanding the backbone further by additing concentrators at N4, N10, and N13; slightly reduces the cost = $101,806/month TELCOM 2110 Spring 06 13 6
  7. Examples of Real WAN Backbone Networks Worldcom: TELCOM 2110 Spring 06 14 Sprint IP Backbone TELCOM 2110 Spring 06 15 7
  8. Example of Real WAN Networks British Telecom Backbone TELCOM 2110 Spring 06 16 WAN Network Design • WAN typically have a backbone/edge structure • Trees are not a good backbone (not reliable enough) • Backbone => mesh or ring design • Mesh topologies introduce the problem of routing traffic • How to evaluate mesh design? – Cost vs. Performance – Optimal design difficult – Rules of thumb - poor design if high average nodal degree or high average number of hops – Should consider several alternatives • Many algorithms/optimization formulations/design tools for WAN packet network design TELCOM 2110 Spring 06 17 8
  9. Network Layers Traffic at higher layers is demand at lower layers San Francisco New York Packet Logical Trunk Group of n x DS1 Data Switch Switch link Service Layer n x DS3 DCS Circuit OCn Switched Optical layer Transport Layer TELCOM 2110 Spring 06 18 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 19 9
  10. Mesh Network Design Algorithms ™ Mentor (MEsh Network Topological Optimization and Routing) Algorithm 1. Backbone selection (classify backbone/edge sites) 9 Threshold clustering 2. Creation of the initial topology 9 Prim-Dijkstra tree or Backbone tour 3. Link addition 9 Home-based routing or ISP-based routing 4. Access topology 9 Star , Esau-William, MSLA, etc. Widely used – low complexity – reasonable quality TELCOM 2110 Spring 06 20 Mentor Algorithm Step 1 • Divide sites into backbone sites and edge sites • Backbone sites are traffic aggregation points and node in the routing mesh • Inputs are nodes Ni and their locations and node weights (i.e., sum of all traffic demand at a node) W(Ni) • Initially assume a single link type with capacity C • Highly parameterized procedure – can produce many alternative backbone node groups – example designs made by changing parameter settings in Mentor algorithm • Parameters are –Radius (RPARM) – Weight Limit (WPARM) • Use threshold clustering assign nodes to groups TELCOM 2110 Spring 06 21 10
  11. Mentor Algorithm Step 1 • Choose backbone sites. (Threshold Cluster Algorithm) • Calculate the normalized weight NW(Ni)=W(Ni)/C • In NW(Ni) > WPARM, select Ni as a backbone node, • Group end sites Nj around a backbone site, Ni, based on Cost(Nj, Ni)/MAXCOST < RPARM. • Where MAXCOST=Max i,j Cost(Nj, Ni) The middle stage of clustering Big squares are backbone nodes Nodes on or within circles are edges associated with that backbone node What to do with nodes not assigned to backbone or edge status? TELCOM 2110 Spring 06 22 Mentor Algorithm Step 1 Merit Functions Merit function – gives equal value to proximity to center of network and weight merit(n)= 0.5(MaxDistCtr-distCtrn)/MaxDistCtr + 0.5(Wn/W_Max) Here 2 2 DistCtrn = (xn − xctr) + (yn − yctr) ∑ x n × Weight n n∈ N and 2 2 xctr = MaxDistCtr = max (xn − xctr) + (yn − yctr) Weight n∈N ∑ n n∈ N Center of Mass (xctr, yctr) defined by ∑ y n × Weight n yctr = n∈ N Weight • Sort the merit functions. The node with ∑ n n∈ N largest merit get picked as backbone node. Group end node around it. Repeat until all nodes are covered in groups. The final clustering Based on merit(), three backbone nodes are picked. TELCOM 2110 Spring 06 23 11
  12. Mentor Algorithm Step 2 • Pick a backbone node to be center of the network (called median node) • Median determined by computing the moment for each backbone node – smallest moment is selected ′ Moment (n) = ∑ dist (n, n ) × Weight n′ n′∈N TELCOM 2110 Spring 06 24 Mentor Algorithm Step 3 • Build a tree rooted at median connecting all nodes – Try to restrict interior tree nodes to backbone nodes • Tree can be build using MST or SPT , but Prim-Dijkstra is often recommended, recall link cost in Prim-Dijkstra: 0 ≤ α ≤1 minneighbors (α ×dist(root,neighbor) + dist(neighbor,node)) TELCOM 2110 Spring 06 25 12
  13. Mentor Algorithm Step 4 •Sequencing node pairs to prepare adding additional direct links to the tree. Use the tree to list node pair in “sequence”. The node pair with longer path will be listed first – OUTSIDE IN ORDERING For Example ‰ Note sequence is not unique ‰ It obeys an outside-in ordering: ‰ Do not sequence the pair (N1, N2) until we sequence all pairs (N3, N4) such that N1 and N2 lie on the path between N3 and N4. ‰ If n nodes in network have ⎛ n ⎞ ⎜ ⎟ pairs in sequence ⎝ 2 ⎠ TELCOM 2110 Spring 06 26 Mentor Algorithm Step 5 Homing •For each nonadjacent node pair in the tree (Ni,Nj), select a home node H •In (Ni,Nj) are two hops apart, home node is node between them •If more than two hops apart, there are multiple candidates for home node H. For example consider (N1,N2) separated by N3 and N4. •Where N3 is first node in path from N1 to N2 and N4 is the first node in path from N2 to N1 if Cost(N1, N3) + Cost(N3,N2) <= Cost(N1, N4) + Cost(N4,N3) then N3 is the home otherwise N4 •In general pick H that gives minimum cost Cost(Ni, H) + Cost(H,Nj) <= Cost(Ni, Nx) + Cost(Nx,Nj). - H and Nx are intermediate nodes along the path. TELCOM 2110 Spring 06 27 13
  14. Mentor Algorithm Step 6 • Decide which node pairs deserve direct links. • Start with the top node pair (N1,N2) in the sequence. • Calculate the number of basic links needed n=ceil(Traf(N1,N2)/C). • Compute resulting link utlization u=Traf(N1,N2)/(n*C) • If u > utilmin, add direct link between N1 and N2. • If u < utilmin, do not add direct link, but instead direct traffic 1 hop through the tree, • Add Traf(N1,N2) to Traf(N1,H) and Traf(H,N2). Here H is the home of (N1,N2). • Remove (N1,N2) from the sequence and repeat Step 6 again until all node pairs are processed. • Idea is to aggregate traffic to justify links connecting sites several hops apart in tree TELCOM 2110 Spring 06 28 Complexity of Mentor Algorithm • The three basic steps: backbone selection, tree building, and direct link addition are all O(n2) where n is the number of nodes. • It can be executed pretty fast. • Typically we will generate a set of designs based on the same threshold parameter WPARM, RPARM, –Use vary α in the restricted Prim-Dijkstra tree and/or vary utilmin . 9 Prim-Dijkstra tree is parameterized by α 0 ≤ α ≤1 minneighbors (α ×dist(root,neighbor) + dist(neighbor,node)) 9 The smaller the value of utilmin, the easier it is to add direct links. • We then pick the best design from the set • Note previous example designs 1-6 made with mentor algorithm with different parameter settings TELCOM 2110 Spring 06 29 14
  15. Example of Mentor Algorithm 15 sites, 5 backbone nodes N2, N4, N8, N9 and N13. Cost= $ 269,785/month utilmin= 0.9 Generated with file mux1.inp as input to Delite program TELCOM 2110 Spring 06 30 Example of Mentor Algorithm Same 5 backbone nodes, with lower utilmin=0.7 Cost= $221,590/month, TELCOM 2110 Spring 06 31 15
  16. Example of Mentor Algorithm Same 5 backbone nodes but with α=0.1, utilmin=0.9 Cost = $209,220/month. TELCOM 2110 Spring 06 32 Effect of varying alpha and utilmin α=0.1 and 1-utilmin=0.1 is the best value. TELCOM 2110 Spring 06 33 16
  17. Cost vs. Size of Backbone • Varying WPARM, RPARM changes number of backbone nodes – leaving other parameters fixed • Nine nodes give min cost TELCOM 2110 Spring 06 34 Reliability/Survivability ƒ What do we mean by “reliability”? Given a network of nodes and links, the reliability of the network is the probability that the working nodes are connected. ƒ So far the cost-optimised networks that we have studied are often tree like. Tree designs have low reliability in many cases. ƒ One measure of reliability is the connectedness of the network – a network is K –connected if it can loose K links and a path still exist between every source-destination pair. ƒ Real Backbone networks are almost always 2 or more connected ƒ Survivability looks at performance as well as connectedness TELCOM 2110 Spring 06 35 17
  18. 2-Connected Backbones • Suppose we have completed an initial backbone design We have further identified a subset of backbone nodes that require 2- connectivity. • We will divide the sites into two subsets 1. H = {sites requiring more reliability} 2. L={sites requiring less reliability} • Our approach is to include the sites in H in the backbones and then make sure that the backbone is 2-connected. • If using MENTOR algorithm, one can simply change the parameters WPRAM, RPARM, α, utilmin to make the network more dense (at a greater cost ) • Alternative is MENTour algorithm TELCOM 2110 Spring 06 36 MENTour ™ Remember steps in Mentor Algorithm 1. Backbone selection (classify backbone/edge sites) 9 Threshold clustering 2. Creation of the initial topology 9 Prim-Dijkstra tree 3. Link addition 9 Home-based routing or ISP-based routing 4. Access topology 9 Star , Esau-William, MSLA, etc. 9 MENTour modifies Step 2 replacing tree rooted at median node with a Ring (tour) using nearest neighbor algorithm TELCOM 2110 Spring 06 37 18
  19. Example 45 Node Example used earlier – Example 1-6 The initial topology for MENTour Example 2 Design TELCOM 2110 Spring 06 38 Example A final design by MENTour has lower cost TELCOM 2110 Spring 06 39 19
  20. WAN Packet Network Design • Two basic approaches – Design topology – then route traffic – Route traffic – then capacitate design • Routing Approaches are variation on minimum cost – Min Average Delay given max cost (bandwidth) – Max throughput given max delay and cost –Etc. TELCOM 2110 Spring 06 40 Routing Based Approach ƒ Given node locations and traffic matrix and initial topology 1. Route traffic according to appropriate routing algorithms 2. Determine traffic on each link 3. Check or assign capacity to each link 4. Check Delay 5. Check Cost and possibly iterate by generating a new initial topology TELCOM 2110 Spring 06 41 20
  21. Delay Calculations ƒ Given a topology and traffic matrix and traffic routing ƒ Estimate the network delay using Jackson queueing network model, that is assume each queue is a M/M/1 ƒ Assume there are M links in the network at Link i •Fi is the total traffic arrival rate (flow) in bps •Ci is the link capacity in bps • For stability Ci >Fi • Mean Delay 1 Di = (Ci − Fi ) TELCOM 2110 Spring 06 42 Delay Calculations • For the network as a whole •let γsd denote the mean traffic rate from source s to destination d, •let γ denote the total offered network traffic load γ = ∑ γ sd s,d • Average delay in the network T is M M Fi 1 Fi T = ∑ Di = ∑ i=1 γ γ i=1 (Ci − Fi ) TELCOM 2110 Spring 06 43 21
  22. Delay Calculations • Average delay for each source destination pair (s,d) • determined by summing link delays on the path Ds,d = ∑ Di i∈path(s,d ) • In general one tries to minimize some function of the network delay or capacity f (T ) or ∑cost(Ci ) i TELCOM 2110 Spring 06 44 Minimize Delay Formulation ƒ Minimize Average Network Delay 1 M F T = ∑ i γ i=1 (Ci − Fi ) ƒ With respect to Ci ƒ Under constraint (where C = total capacity) M C = ∑ Ci i=1 TELCOM 2110 Spring 06 45 22
  23. Solution to Minimization Problem ƒ Use Lagrange Multiplier technique ƒ Let α denote the Lagrange multiplier ƒ Incorporate the constraint and minimize the following with respect to Cij and M M 1 Fi ⎡⎛ ⎞ ⎤ Q = ∑ +α⎢⎜∑Ci ⎟ −C⎥ γ i=1 (Ci − Fi ) ⎣⎝ i=1 ⎠ ⎦ ƒ Minimize by taking partial derivatives setting equal to zero TELCOM 2110 Spring 06 46 Solution to Minimization Problem ƒ Yields ∂Q = 0 M equations ∂Ci ∂Q = 0 1 equation from constraint ∂α ƒ M+1 (non-linear) equations with M+1 unknowns ƒ Solve using algebra TELCOM 2110 Spring 06 47 23
  24. Solution to Minimization Problem ƒ Yields M Fi Ci = Fi + (C − ∑ Fi ) M i=1 ∑ Fi i=1 for i = 1, 2, , M ƒ Fi is the minimum Ci since ρi = Fi/Ci < 1 M ( C − F ) ƒ The excess capacity ∑ i should be i = 1 distributed among the links in proportion to the square root of the traffic TELCOM 2110 Spring 06 48 Mean Network Delay ƒ Resulting Average Network Delay 2 ⎛ M ⎞ ⎜ F ⎟ 1 M F ∑ i T = ∑ i = ⎝ i=1 ⎠ γ i=1 (Ci − Fi ) γC(1− ρ) ƒ Where ρ denotes the mean network traffic intensity. 1 M ρ = ∑ Fi C i=1 TELCOM 2110 Spring 06 49 24
  25. Example ƒ Consider mesh topology below ƒ links are numbered for reference ƒ traffic matrix gives mean rate from source to destination in packets per second, ƒ average packet length = 1000 bits ƒ budget for link bandwidth results in C = 48 Kbps TELCOM 2110 Spring 06 50 Routing/Flows ƒ Assume Static routing ƒ Traffic routed on shortest hop paths ƒ Where multiple shortest hop paths ƒ Traffic 1 to/from 4 routed through 2 ƒ Traffic 1 to/from 5 routed through 3 ƒ Traffic 2 to/from 5 routed through 4 ƒ Links are bi-directional and symmetric ƒ Consider traffic in 1 direction – for example ƒ F1 = γ12 + γ14 = .75 x 1000 + 2.4 x 1000 = 3150 bps ƒ F2 = γ13 + γ15 = .61 x 1000 + 2.94 x 1000 = 3550 bps TELCOM 2110 Spring 06 51 25
  26. Routing/Flows Link PPS Fi Ci Di 1 3.15 3150 6546 .294 2 3.55 3550 7155 .277 3 .13 130 820 1.45 4 3.64 3640 7291 .274 TELCOM 2110 Spring 06 52 Routing/Flows Link PPS Fi Ci Di 5 .82 820 2553 .577 6 3.88 3880 7649 .265 7 9.95 9950 15986 .116 Total/Avg 25.12 25120 48000 .249 TELCOM 2110 Spring 06 53 26
  27. Min-Max Capacity ƒ Notice, while minimizing delay, the capacity assignment – favors links with high arrival rates – they get lower delay. ƒ Alternate approach ƒ minimize maximum delay: min-max solution ƒ Seek to make delays equal for all links ƒ Results in M 1 Ci = Fi + (C − ∑ Fi ) i=1 M TELCOM 2110 Spring 06 54 Repeat Example Using Min-Max Link Ci Di 1 6418.6 .306 2 6418.6 .306 3 3398.6 .306 4 6908.6 .306 5 4088.6 .306 6 7148.6 .306 7 13218.6 .306 TELCOM 2110 Spring 06 55 27
  28. Cost Constraint Functions ƒ More realistic Cost constraint. • Fixed cost per link, ai. • Distance-based or other variable factor per link, di M J = ∑ (d iCi + ai ) i=1 • Available cost Ja M J a = J − ∑ (d i Fi + ai ) i=1 • Results are similar to previous on excess capacity TELCOM 2110 Spring 06 56 Solution ƒ Yields for Minimum Average Delay ⎛ ⎞ ⎜ ⎟ J d F C = F + a ⎜ i i ⎟ i i ⎜ M ⎟ d i ⎜ ∑ d i Fi ⎟ ⎝ i =1 ⎠ ƒ For the min-max delay case J a C i = F i + M ∑ d i i = 1 TELCOM 2110 Spring 06 57 28
  29. Example • Consider a star type of topology where three branch offices connect to a central database and the main office – C1: West Branch ; 20 terminals, 10 miles from main office – C2: North Branch : 20 terminals, 30 miles from main office – C3: East Branch: 1 terminal, 30 miles from main office All terminals have identical statistics: mean packet rate 2000 /sec mean packet length 128 bytes •Cost – Variable: $0.002 bps per mile – Fixed: $1000. per link – Allowed total cost J = $4M TELCOM 2110 Spring 06 58 Example Link KPkt/s Fi (Mbps) di ($/bps) 1 40 40.96 .02 2 40 40.96 .06 3 2 2.048 .06 TELCOM 2110 Spring 06 59 29
  30. Minimum Delay Example Link Ci (Mbps) Di Costi ($M) (msec) diCi + ai 1 50.53 .107 1.01 2 46.49 .185 2.79 3 3.28 .828 .20 Total 100.3 Mean = .163 4.00 ⎛ ⎞ ⎜ ⎟ J d F C = F + a ⎜ i i ⎟ i i ⎜ M ⎟ d i ⎜ ∑ d i Fi ⎟ ⎝ i =1 ⎠ TELCOM 2110 Spring 06 60 Min-Max Example Link Ci Di (msec) Costi ($M) 1 45.23 .24 .91 2 45.23 .24 2.71 3 6.31 .24 .38 Total 96.77 .24 4.00 J a C i = F i + M ∑ d i i = 1 TELCOM 2110 Spring 06 61 30
  31. WAN Packet Design • Note many alternative routing based design approaches based on tradeoff of cost,capacity, performance • A simple extension to the routing based approaches discussed is successive minimum cost routing • Route traffic – create initial topology – evaluate performance metrics (cost, delay etc.) try to improve by rerouting traffic. TELCOM 2110 Spring 06 62 Heuristic Algorithm Heuristic Begin Let D = set of traffic demands or flows; Let E = set of all potential links; do { randomly select an order of traffic demands in D to be routed; for each traffic demand k in the order { if (traffic demand k has an existing route) temporarily remove its required bandwidth along the route; calculate new link-cost metric for all links in E based on the updated topology, reserved bandwidth, and traffic demand k; find minimum-cost path from the calculated link metric for traffic demand k; if (new route has been found) update network topology for new links and capacity; else maintain previous solution; } } until ( update improvement max_iteration); TELCOM 2110 SpringEnd 06 63 31
  32. Summary • Consider basic WAN network design issues • Two approaches to WAN Packet Design • Topology then routing (MENTOR) • Routing then topology (Min. Delay) • Both are used and integrated into commercial tools TELCOM 2110 Spring 06 64 32