New Congestion Avoidance Methods for IP Networks

This research presentation highlights the challenges of IP network failures, focusing on planned and unplanned scenarios. Dr. Simon Tembo discusses innovative methods to prevent congestion during failures, including a backup topology design for unplanned failures and a congestion avoidance approach for planned failures. The study aims to improve network reliability and minimize disruptions, particularly in the context of increasing demands on Internet backbones. The presentation outlines the background, objectives, and research parts, emphasizing the importance of enhancing IP network architectures for a connected Africa.

• IP networks
• Congestion avoidance
• Network failures
• Africa
• Research

khick Follow

Uploaded on Sep 07, 2024 | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. 3rdSG13 Regional Workshop for Africa on ITU-T Standardization Challenges for Developing Countries Working for a Connected Africa (Livingstone, Zambia, 23-24 February 2015) New Congestion Avoidance Methods during Planned and Unplanned Failures for IP Network Architectures Dr. Simon Tembo (Dr.Eng., M.Eng., B.Eng., MIEEE, MEIZ, REng) Assistant Dean Postgraduate Studies School of Engineering University of Zambia simon.tembo@unza.zm simontembo6@gmail.com This Research was a Collaboration and Funded by Nippon Telegraph & Telephone (NTT) Corp. of JAPAN.

2. PRESENTATION OUTLINE 1. 2. 3. BACKGROUND OBJECTIVES PRESENT TWO CONGESTION AVOIDANCE METHODS: (1) For Unplanned Failures A New Backup Topology Design Method for Congestion Avoidance in IP Fast Reroute International Journal of Networks and Communications 2012, Vol.2, No.5, pp. 123-131, September 2012 (2) For Planned Failures A Method to Avoid Congestion during Transient Link Cost Update in IP Networks Plans to Submit for publication to the IEICE Transaction on Communications, Japan SUMMARY ACKNOWLEDGEMENTS 4. 5. 2

3. BACKGROUND Due to increase in the use of Internet Backbones by carrying Voice, Video and Data traffics, ISPs have SLAs with Customers to guarantee Quality of Service (e.g. 99.999% Network Availability). Research shows that there are 2 Major Classes of Network failures in IP Network Architecture[1]: Planned Failures 20% Unplanned Failures 80% PLANNED FAILURES UNPLANNED FAILURES 3 [1] : Characterization of Failures in an IP Backbone, by A. Markopoulou et. al , IEEE INFOCOM 2004

4. BACKGROUND IP Network Failures Planned Failures (20%) Unplanned Failures (80%) Man made failures Not Man made failures e.g. Engineers shutting down a Link for Maintenance Routine e.g. System or Equipment Failure 4

5. BACKGROUND 2 MAJOR OF CAUSES OF CONGESTION 5

6. OBJECTIVE 6

7. RESEARCH PARTS 1. Unplanned Failures : Present a new backup topology design method to avoid congestion during IP Fast Reroute (IPFRR): by using fewer backup topologies to reduce the size of routing tables (i.e. reducing the router memory size) 2. Planned Failures : Present a link cost update method to avoid congestion during transient link cost updates: Performing link cost updates is a Permutation Problem; But selecting a congestion free link cost update during transient period for Huge Permutations is a big challenge for ISPs. 7

8. PART 1: CONGESTION AVOIDANCE FOR UNPLANNED FAILURE A New Backup Topology Design Method for Congestion Avoidance in IP Fast Reroute 1. INTRODUCTION Existing Method: Multiple Routing Configurations (MRC) Problem Statement Research Originality 2. RESEARCH APPROACH Overview Algorithm 3. RESULTS & DISCUSSION 4. CONCLUSION 8

9. INTRODUCTION TRADITIONAL IP NETWORKS Backuppath is calculated after Network Failure Computation process to recalculate the new path Fault Notification to sent all routers Failure occurred Re-Routing IP FAST REROUTE METHOD Backup path is calculated before Network Failure Failure occurs Re-Routing Backup path is pre-arranged to shortening the processing In Traditional IP networks, failure recovery takes time. IP Fast Reroute method, failure recovery is faster .

10. INTRODUCTION EXAMPLE Fault detected Fault detected Detour Route Pre-computed After failure, fault notice is sent to all routers Link Failure 2 2 6 1 5 6 1 5 3 3 After receiving the failure notice, Router 1 then computes an detour route 4 4 TRADITIONAL IP NETWORK IP FAST REROUTE NETWORK 10

11. INTRODUCTION Multiple Routing Configurations (MRC) [2] Original Topology Backup Topology Traffic is Re-routed Fault detected src src This link is protected dst dst Link Fails, connectivity? Link sever has backup topology pre-computed to provide backup route for continuous connectivity when this link fails. 11 [2] A.Kvalbein, et.al, Fast IP Network Recovery using Multiple Routing Configurations, IEEE INFOCOM, Apr.2006.

12. INTRODUCTION Creating Many Backup Topologies -> NOT GOOD STRATEGY Because :- 1)It increases the size of routing tables kept in routers (Memory Problem). 2)It Increases link-state messages transmitted in the network. 3 Possible Backup Topologies for possible network failures (with at most 10 Available Links) Link Failure src Backup Topology #0 dst Original Topology with 14 Available Links Backup Topology #2 Backup Topology #1 Protected Link 12

13. INTRODUCTION PROBLEM STATEMENT Reducing Number of Backup Topologies -> Fairly Good Strategy We need to recover traffic with fewer backup topologies for scalability purposes. 1.But reducing the number of backup topologies results in limited available links for back up routes. 2.Due to fewer backup routes, rerouted traffic can cause congestion if not carefully split among the backup routes according to the available capacity. 13

14. INTRODUCTION PROBLEM STATEMENT Problem with the existing approach (MRC) is the placement of the fewer available links for backup routes; it lacks diverse routes such that: 1) it causes congestion. 2) route optimization is not possible. CONGESTION 3 Possible Backup Topologies for all possible network failures Backup Topology #0 is Selected 1 2 3 src Backup Topology #0 4 5 7 6 8 dst Backup Topology #2 Backup Topology #1 Original Topology High-load node Protected Link 14 14

15. RESEARCH APPROACH- RESEARCH ORIGINALITY Proposed approach is to optimize the placement of protected links by: 1) Maximizing available links to overloaded nodes. 2) Splitting traffic on high load links to other links. Proposed Approach Existing Approach Maximizing available links to Overloaded Nodes High-load node Special Node: Identify High-load node and maximize the number of the available links Protected Link The key idea is the establishment of a SPECIAL NODE; i.e. Node with 1)High TrafficVolume - LOAD ORDER METHOD 2)High Node Degree DEGREE ORDER METHOD 15

16. EXAMPLE OF SPECIAL NODE FOR LOAD ORDER & DEGREE ORDER METHODS (HLDA NETWORK MODEL) Top K Nodes = 3 2 METHODS OF DECIDING SPECIAL NODE (1) LOAD ORDER METHOD 9 1 1000 Traffic Volume 800 4 600 400 3 200 0 2 1 2 3 4 5 6 7 8 9 10 11 5 Node ID 10 1 2 3 4 5 6 7 8 9 10 11 8 (2) DEGREE ORDER METHOD 11 10 6 7 8 Node Degree 2 METHODS OF SELECTING SPECIAL NODE 6 4 1) Top K method: Top-K influential nodes (i.e. most influential nodes). 2) Swapping K method: Takes into consideration the node position, when selecting from the Top-K influential nodes Avoid selecting Neighbor node as Special Node to that already chosen. 2 0 1 2 3 4 5 Node ID 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11

17. RESEARCH APPROACH RESEARCH APPROACH ALGORITHM OVERVIEW ALGORITHM OVERVIEW PROPOSED ALGORITHM STARTS BY: 1. Choosing the Special Node 2. Then maximize number of available links to the Special Node. Existing Approach Proposed Approach Input information Topology information Traffic Exchange Topology information STEP1 Selection of Special Node Subdivision STEP2 All nodes will have Link protection arrangement Special Nodes Link protection arrangement STEP3 Other nodes Link protection arrangement Output Information Backup Topology Backup Topology 17

18. COST 239 Actual European Network Model (i.e. 11 nodes, 50 links) The Evaluation involves quantitative measure of the link load after a link failure COPENHAGEN 6 LONDON 3 AMSTERDAM BERLIN 7 5 LUXEMBOURG PRAGUE 4 2 8 BRUSSELS ZURICH 1 0 VIENNA 9 PARIS 10 MILAN 18 18

19. COST 266 Actual European Network Model (i.e. 26 nodes, 100 links) The Evaluation involves quantitative measure of the link load after a link failure

20. PERFORMANCE EVALUATION Evaluation Method Quantitative evaluation of the link load after a link failure Evaluated : Proposed Algorithm vs. Existing Algorithm Proposed : (Load Order Method and Degree Order Method) Conventional : Existing Method with no Special Node (K = 0) Evaluation Index Link load: total amount of traffic received in the link Evaluation Criteria Actual European Network Model COST 239 (Smaller Network) COST 266 (Larger Network) Traffic Model: Gravity model according to the population distribution 20

21. RESEARCH RESULTS - LINK LOAD FOR COST 239 MODEL (with 3 Backup Topologies ) Swapping K Method For unplanned failure able to Avoid Congestion Top K Method For unplanned failure able to Avoid Congestion Load Order Degree Order Load Order Degree Order 4.50 4.50 75% Load Reduction 75% Load Reduction 4.00 4.00 Maximum Link Load Maximum Link Load 3.50 3.50 3.00 3.00 2.50 2.50 2.00 2.00 1.50 1.50 1.00 1.00 0.50 0.50 0.00 0.00 0 1 2 3 4 5 0 1 2 3 4 5 Number of Special Nodes (K) Number of Special Nodes (K) CONVENTIONAL METHOD CONGESTION FREE; NORMAL CONDITION Conventional Method Load Order Method Degree Order Method 21

22. RESULTS AND DISCUSSION-LINK LOAD FOR COST 266 MODEL (with 4 Backup Topologies ) Top K Method For unplanned failure able to Reduce Congestion Swapping K Method For unplanned failure able to Avoid Congestion Load Order Degree Order Load Order Degree Order 2.00 2.00 33% Load Reduction 44% Load Reduction 1.80 1.80 1.60 Maximum Link Load 1.60 Maximum Link Load 1.40 1.40 1.20 1.20 1.00 1.00 0.80 0.80 0.60 0.60 0.40 0.40 0.20 0.20 0.00 0.00 0 1 2 3 4 5 0 1 2 3 4 5 Number of Special Nodes (K) Number of Special Nodes (K) CONVENTIONAL METHOD CONGESTION FREE; NORMAL CONDITION Conventional Method Load Order Method Degree Order Method 22

23. RESULTS AND DISCUSSION COST 239 & COST266 MODELS The Proposed IPFRR method provides Congestion Avoidance compared to the Existing IPFRR method (MRC method). Network Model Load Order (Traffic Volume) Degree Order (Node Degree) COST239 (Smaller) COST 266 (Larger) 1. In both European Network Models: Load Order does Avoid Congestion during unplanned failure than the Degree Order. In Larger Networks: Load Order is only better than Degree Order when node position of Special Nodes is considered. 2. DEFINITION OF SYMBOL AVOID CONGESTION 23 REDUCE CONGESTION

24. CONCLUSION PART 1 1. Presented the Backup Topology design method to avoid congestion for efficient IP Fast Reroute (IPFRR) during unplanned failures. The key idea of the method is the establishment of a Special Node in a backup topology. Using the proposed method we able to effect a load reduction to about 75% as compared to existing method. 2. 3. Paper:- S. Tembo, et. al. A New Backup Topology Design Method for Congestion Avoidance in IP Fast Reroute , International Journal of Networks and Communications 2012, Vol.2, No.5, pp. 123-131, September 2012, (http://www.sapub.org/journal/archive.aspx?journalid=1097). Conference:- S. Tembo, et. al. Dispersing Hotspot Traffic in Backup Topology for IP Fast Reroute , Proceedings of IEEE International Conference on Communications 2011 (IEEE ICC 2011), 5-9 June, Kyoto, Japan. 24

25. PART 2:- CONGESTION AVOIDANCE FOR PLANNED FAILURES A Method to Avoid Congestion during Transient Link Cost Update in IP Networks 1. INTRODUCTION Example of Link Cost Update Problem Statement Research Originality 2. RESEARCH APPROACH Overview Algorithm 3. RESULTS & DISCUSSION 4. CONCLUSION 25

26. INTRODUCTION EXAMPLE OF LINK COST UPDATE Example of link cost update from Initial Link Cost state to Target Link Cost state for Traffic Engineering (TE) reason. TARGET LINK COST STATE INITIAL LINK COST STATE High Load Link High Load Link 5 7 1 7 3 1 3 1 1 1 1 2 1 1 2 1 4 6 4 6 2 1 2 2 1 2 2 2 2 1 2 1 5 8 5 8 1 1 dst 1 1 1 10 src Routing Link Cost Link 1-5 is scheduled for Maintenance Routine There are 2 links needed to be updated. Which link do we update 1st between Link 1-5 & Link 3-7 to avoid congestion in link 3-7? 26

27. INTRODUCTION EXAMPLE OF LINK COST UPDATE Performing link cost updates for several different links is a Permutation Problem. Example: For 3 different letters say A, B, C the permutations are 6: i.e. 1. ABC 2. ACB 3. BAC 4. BCA 5. CAB 6. CBA 27

28. INTRODUCTION - PROBLEM STATEMENT PROBLEM STATEMENT Performing a link cost update for several different links for TE purpose is a big challenge for Service Providers. Finding a link cost update sequence order which is Congestion free is not a practical computation time for Huge Permutations. For Evaluation we use COST 239 (An European Network Model): Present a method to avoid congestion free during transient states. TOPOLOGY NODES LINKS UPDATABLE LINKS 6 PERMUTATIONS COST 239 11 50 720 HUGE PERMUTATIONS 28

29. PERFORMANCE EVALUATION EVALUATION METHOD Quantitative Evaluation of the Maximum Link Load EVALUATED : OUR ALGORITHMS VS. RANDOM ALGORITHM Random Method : Using Brute Force approach without applying the Our Priority Link Cost Update Sequence Order (ULLN) method . Proposed : Using Brute Force [4] approach together with Our Priority Link Cost Update Sequence Order (ULLN) method . EVALUATION INDEX Maximum Load in the Network EVALUATION CRITERIA Topology network model COST 239 (A European Network Model) Traffic Model: Gravity Model according to the population distribution Configuration : Initial Link Cost & Target Link Cost DEFINITION OF OPTIMUM ROUTING AND CONGESTION 1) Optimum routing is when we have minimum maximum load in the Network. 2) Congestion occurs when the transient maximum load exceeds that of the initial state. 29 [4] : Software Development by NTT Network Service Laboratories

30. COST 239 A European Network Model Which 6 links when updated gives Optimum Routing? COPENHAGEN 6 LONDON AMSTERDAM 3 BERLIN 7 5 LUXEMBOURG PRAGUE 4 2 8 BRUSSELS ZURICH 1 0 VIENNA 9 PARIS 10 MILAN 30 30

31. RANDOM UPDATE METHOD: USING BRUTE FORCE WITHOUT APPLYING PROPOSED METHOD Congestion occurs when the transient maximum load exceeds that of the initial state. CONGESTION 0.88 Overflow Threshold 0.86 0.84 MAXIMUM LOAD 0.82 0.8 0.78 0.76 INITIAL STATE 0.74 INITIAL 1 2 3 4 5 TARGET 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1) 2) 3) Congestion occurs during transient link cost update Only 3 out of 24 patterns achieve optimum routing,(i.e. patterns 13, 16, & 22). Optimum Routing Performance is 12.5% (3/24). 31

32. ANOTHER RANDOM UPDATE METHOD: USING BRUTE FORCE WITHOUT APPLYING PROPOSED METHOD Congestion occurs when the transient maximum load exceeds that of the initial state. 0.88 0.86 Overflow Threshold 0.84 MAXIMUM LOAD 0.82 0.8 0.78 0.76 0.74 CONGESTION INITIAL STATE 0.72 0.7 INITIAL 1 2 3 4 5 TARGET 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1) 2) 3) Congestion occurs during transient link cost update In this setup, it is not possible to achieve the optimum routing. Therefore the optimum routing performance is 0% (i.e. 0/24). 32

33. PROPOSED METHOD TO DETERMINE UPDATABLE LINKS FOR OPTIMUM ROUTING INPUT INFORMATION Topology information Traffic Information Identify High Load Link + Construct Forwarding Tree STEP 1 Identify Leaf Nodes, then select Link-Leaf Node, which if updated will optimize maximum load STEP 2 STEP 3 The Link then qualifies as Updatable Link OUTPUT INFORMATION Optimum Routing Updatable Topology 33

34. PROPOSED UPDATE METHOD: USING BRUTE FORCE TOGETHER WITH OUR PRIORITY LINK COST UPDATE METHOD Overflow Threshold 0.88 0.86 0.84 MAXIMUM LOAD 0.82 INITIAL STATE 0.8 0.78 0.76 0.74 0.72 0.7 INITIAL 1 2 3 4 5 TARGET 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1) 2) 3) No Congestion Occurs All 24 patterns give Optimum Routing. The Optimum Routing Performance is 100% (i.e. 24/24). 34

35. PERFORMANCE OF RANDOM METHOD Vs. PROPOSED METHOD METHOD CONGESTION RANDOM CONGESTION OCCURS PROPOSED (ULLN) CONGESTION FREE 100% OPTIMUM ROUTING 100.00% 80.00% 60.00% 40.00% 12.50% 20.00% 0.00% RANDOM METHOD ULLN METHOD OPTIMUM ROUTING PERFORMANCE 35

36. CONCLUSION PART 2 Presented is a Link Cost Updatemethod to avoid congestion during planned failures. Using this method we can achieve 100% optimum routing METHOD CONGESTION PERFOMANCE RANDOM OCCURS 12.5% PROPOSED (ULLN ) NOTHING 100% Paper:- S. Tembo, et. al. A Method to Avoid Link Overflow During Transient Link Cost Update in IP Networks . Planning to Submit for publication to the IEICE Transaction on Communications. 36

37. SUMMARY 37

38. SUMMARY 38

39. Acknowledgements My gratitude goes to the Doctoral Supervisory Committee members at Akita University (Japan): 1. Prof. Ken-ichi YUKIMATSU, 2. Prof. Hideo TAMAMOTO, 3. Prof. Akihiro YAMAMURA and 4. Prof. Hitoshi OBARA for their Academic advise and support. I would like to sincerely thank NTT for funding the research. 39

40. THANK YOU 40