of 90
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

When the cure is worse than the disease: The impact of graceful IGP operations on BGP

Category:

Letters

Publish on:

Views: 4 | Pages: 90

Extension: PDF | Download: 0

Share
Description
When the cure is worse than the disease: The imact of graceful IGP oerations on BGP Laurent Vanbever Princeton University & University of Louvain IEEE INFOCOM Aril 18, 13 Joint work with Stefano Vissicchio,
Transcript
When the cure is worse than the disease: The imact of graceful IGP oerations on BGP Laurent Vanbever Princeton University & University of Louvain IEEE INFOCOM Aril 18, 13 Joint work with Stefano Vissicchio, Luca Cittadini, and Olivier Bonaventure Interior Gateway Protocols (IGP) are frequently reconfigured Interior Gateway Protocols (IGP) are frequently reconfigured Motivation Reconfiguration oeration Traffic engineering && green networking Change link weights Interior Gateway Protocols (IGP) are frequently reconfigured Motivation Reconfiguration oeration Traffic engineering && green networking Change link weights Maintenance Cost-out links and/or routers Interior Gateway Protocols (IGP) are frequently reconfigured Motivation Reconfiguration oeration Traffic engineering && green networking Change link weights Maintenance Cost-out links and/or routers Service deloyment && scaling/erformance Protocol changes, hierarchy deloyment Reconfiguring the IGP can create numerous roblems IGP reconfiguration can lead to forwarding loo network congestion blackhole or any combination of those A lot of research has been made to solve these roblems forwarding loo network congestion blackhole [Francois05-07], [Alimi08], [Fu08], [Vanbever12] [Raza09], [Shi09] [Alimi08], [Vanbever12] Most of these research works exclusively focus on the IGP but BGP routers deend on the underlying IGP to discriminate between equivalent routes Most network traffic in an ISP is due to BGP the IGP is used as a reachability mechanism Problem Can safely reconfiguring the IGP create BGP anomalies? Most of these research works exclusively focus on the IGP but BGP routers deend on the underlying IGP to discriminate between equivalent routes Most network traffic in an ISP is due to BGP the IGP is used as a reachability mechanism Problem Can safely reconfiguring the IGP create BGP anomalies? The answer is YES! Safely reconfiguring the IGP can and do create BGP anomalies Dataset IGP and BGP configuration of a Tier1 backbone 0+ routers, 150+ links Reresentative BGP route feed Reconfiguration Randomly reweight 5,, 15 links using rovably correct IGP reconfiguration technique [Vanbever12] Exeriments Measure the amount of BGP-induced loo 1.0 cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) Safely reconfiguring the IGP can create numerous BGP anomalies 1.0 cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) In the worst case, tens of thousands of loos can be created 1.0 k loos in the worst case cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) In the worst case, tens of thousands of loos can be created cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) k loos in the worst case 30k 0k Most IGP reconfiguration triggers BGP-induced loos 1.0 cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) 40% of exeriments exhibit loos, in the best case Most IGP reconfiguration triggers BGP-induced loos 1.0 cumulated frequency reweighting 5 links reweighting links reweighting 15 links 1 0 1k k 0k 1M # of BGP induced forwarding loos (log) 40% of exeriments exhibit loos, in the best case 70% 90% Our contributions range from ractice, to theory, and back to ractice Theory Comlexity Guidelines Our contributions range from ractice, to theory, and back to ractice Theory Reconfiguring IGP can introduce any BGP anomaly even with state-of-the-art IGP reconfiguration Comlexity Guidelines Our contributions range from ractice, to theory, and back to ractice Theory Reconfiguring IGP can introduce any BGP anomaly even with state-of-the-art IGP reconfiguration Comlexity Deciding if an anomaly-free IGP reconfiguration triggers BGP anomaly is NP-hard Guidelines Our contributions range from ractice, to theory, and back to ractice Theory Reconfiguring IGP can introduce any BGP anomaly even with state-of-the-art IGP reconfiguration Comlexity Deciding if an anomaly-free IGP reconfiguration triggers BGP anomaly is NP-hard Guidelines Sufficient conditions and configuration guidelines that guarantee the absence of BGP-induced anomalies When the cure is worse than the disease: The imact of graceful IGP oerations on BGP The cure IGP reconfiguration The side effects BGP-induced anomalies The solutions sufficient conditions When the cure is worse than the disease: The imact of graceful IGP oerations on BGP 1 The cure IGP reconfiguration The side effects BGP-induced anomalies The solutions sufficient conditions Intradomain routing rotocols (IGP) rule traffic forwarding within a routing domain B A C D 50 1 E F forwarding aths towards C IGP reconfiguration consists in changing some IGP arameters, such as link weights B B A C D A C D E F E F initial IGP final IGP IGP reconfiguration can imact the forwarding aths B B A C D A C D E F E F initial IGP final IGP IGP reconfiguration can imact the forwarding aths B B A C D A C D E F E F initial IGP final IGP If not handled correctly, aths change can lead to forwarding loos Changing the metric of link (D,F) from 1 to can create a loo B B A C D A C D E F E F initial IGP final IGP If not handled correctly, aths change can lead to forwarding loos Changing the metric of link (D,F) from 1 to can create a loo B B A C D A C D E F E F final IGP If not handled correctly, aths change can lead to forwarding loos F and D are the first to notice the change and immediately udate their forwarding table B B A C D A C D E F E F final IGP If not handled correctly, aths change can lead to forwarding loos F and D are the first to notice the change and immediately udate their forwarding table B B A C D A C D E F E F final IGP If not handled correctly, aths change can lead to forwarding loos A forwarding loo is created as long as E is not udated B B A C D A C D E F E F forwarding loo final IGP Safe IGP reconfiguration techniques ugrade the forwarding entries in a recise order Metric-Increment [Francois07] Procedure consecutive metric changes Theoretical guarantees YES, loo-freeness Works Today YES Safe IGP reconfiguration techniques ugrade the forwarding entries in a recise order Metric-Increment [Francois07] Procedure consecutive metric changes Theoretical guarantees YES, loo-freeness Works Today YES Metric increment sequentially increases link metric to make remote routers transition first metric sequence [1,31,51, ] B B A C D A C D E F E F Metric increment sequentially increases link metric to make remote routers transition first metric sequence [1,31,51, ] B B A C D A C D E F E F Metric increment sequentially increases link metric to make remote routers transition first metric sequence [1,31,51, ] B B A C D A C D E F E F Metric increment sequentially increases link metric to make remote routers transition first metric sequence [1,31,51, ] B B A C D A C D E F E F Metric increment sequentially increases link metric to make remote routers transition first metric sequence [1,31,51, ] B B A C D A C D E F E F When the cure is worse than the disease: The imact of graceful IGP oerations on BGP The cure IGP reconfiguration 2 The side effects BGP induced anomalies The solutions sufficient conditions Interdomain routing rotocols (BGP) rule traffic forwarding across routing domains AS AS30 AS AS40 AS50 BGP comes in two flavors AS AS30 AS AS50 AS40 external BGP (ebgp) exchanges reachability information between ASes AS AS30 AS ebgp session AS50 AS40 internal BGP (ibgp) distributes externally learned routes internally AS AS30 AS AS50 AS40 ibgp session In this work, we focus on ibgp AS SEAT SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS BGP is a single-route rotocol. Each router selects one route for each destination SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 BGP is a single-route rotocol. Each router selects one route for each destination When learning equivalent BGP routes, a router will refer the closest one SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 KANS BGP Routing table dest /24 next-ho ATLA SEAT /24 SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 KANS BGP Routing table KANS IGP Routing table dest next-ho dest weight /24 ATLA ATLA 1735 SEAT /24 SEAT SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 KANS BGP Routing table KANS IGP Routing table dest next-ho dest weight /24 ATLA ATLA 1735 SEAT /24 SEAT SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 KANS BGP Routing table KANS IGP Routing table dest next-ho dest weight best BGP route /24 ATLA ATLA 1735 SEAT /24 SEAT SEAT / SALT CHIC 1181 NEWY LOSA KANS WASH ATLA HOUS /24 Reconfiguring the IGP can create any BGP anomaly IGP reconfiguration can lead to unavoidable BGP-induced: forwarding loos routing oscillations network congestion blackholes Reconfiguring the IGP can create any BGP anomaly IGP reconfiguration can lead to unavoidable BGP-induced: forwarding loos routing oscillations network congestion blackholes even if the initial and the final configurations are correct Reconfiguring the IGP can create any BGP anomaly IGP reconfiguration can lead to unavoidable BGP-induced: forwarding loos routing oscillations network congestion blackholes even if the initial and the final configurations are correct Reconfiguring the IGP can create forwarding loos s references R R5 R5 R4 IGP toology ibgp toology R4 s references Due to ibgp roagation rules, never learns the route roagated by R R5 R5 R4 IGP toology ibgp toology By default, egress routers refer their external routes R R5 R5 R4 IGP toology ibgp toology receives two routes, from and, and refer due to IGP distance R R5 R5 R4 IGP toology ibgp toology receives two routes, from and, and refer due to IGP distance R R5 R5 R4 IGP toology ibgp toology R4 first receives the route and refers it R R5 R5 R4 IGP toology ibgp toology R4 then learns the route via R4 and refers it due to the IGP distance R R5 R5 R4 IGP toology ibgp toology R4 then learns the route via R4 and refers it due to the IGP distance R R5 R5 R4 IGP toology ibgp toology R5 learns the route via and refers it R R5 R5 R4 IGP toology ibgp toology The initial forwarding state is loo-free R R5 R5 R4 IGP toology ibgp toology The initial forwarding state is loo-free R R5 R5 R4 IGP toology ibgp toology Let s roceed to the first metric-increment R R5 R5 R4 IGP toology ibgp toology Let s roceed to the first metric-increment R R5 R5 R4 IGP toology ibgp toology R4 is now closer to (distance 30) than (distance 31) R R5 R5 R4 IGP toology ibgp toology R4 is now closer to (distance 30) than (distance 31) R R5 R5 R4 IGP toology ibgp toology R4 is now closer to (distance 30) than (distance 31) R R5 R5 R4 IGP toology ibgp toology Since R4 also receives the route directly, it starts using it R R5 R5 R4 IGP toology ibgp toology Since R4 also receives the route directly, it starts using it R R5 R5 R4 IGP toology ibgp toology still refers (distance 41) to (distance ) R R5 R5 R4 IGP toology ibgp toology A forwarding loo is created between and R4 as R4 uses to reach R R5 R5 R4 IGP toology ibgp toology A forwarding loo is created between and R4 as R4 uses to reach R R5 R5 R4 IGP toology ibgp toology The loo disaears when we roceed to the second increment R R5 R5 R4 IGP toology ibgp toology Let s now roceed to the second increment R R5 R5 R4 IGP toology ibgp toology is now closer to (distance ) than (distance 60) R R5 R5 R4 IGP toology ibgp toology is now closer to (distance ) than (distance 60) R R5 R5 R4 IGP toology ibgp toology Since also receives the route directly, it starts using it R R5 R5 R4 IGP toology ibgp toology which solves the loo R R5 R5 R4 IGP toology ibgp toology A BGP-induced loo in the wild Deciding if reconfiguring the IGP will create BGP anomaly is hard Problem Given one ibgp toology and two IGP toologies: a and b, Decide if any IGP reconfiguration from a to b is free of any BGP anomaly Deciding if reconfiguring the IGP will create BGP anomaly is hard Problem Given one ibgp toology and two IGP toologies: a and b, Decide if any IGP reconfiguration from a to b is free of any BGP anomaly This roblem is NP-hard When the cure is worse than the disease: The imact of graceful IGP oerations on BGP The cure IGP reconfiguration The side effects BGP induced anomalies 3 The solutions sufficient conditions Both IGP and BGP safety can be ensured An IGP reconfiguration will not trigger BGP anomaly if #1 the relative BGP references do not change since no BGP router will change its decision Both IGP and BGP safety can be ensured An IGP reconfiguration will not trigger BGP anomaly if #1 the relative BGP references do not change since no BGP router will change its decision #2 the BGP configuration comlies with the two known sufficient conditions for ensuring routing correctness the refer-client and the no-surious OVER conditions Both IGP and BGP safety can be ensured An IGP reconfiguration will not trigger BGP anomaly if #1 the relative BGP references do not change since no BGP router will change its decision #2 the BGP configuration comlies with the two known sufficient conditions for ensuring routing correctness the refer-client and the no-surious OVER conditions #3 an encasulation mechanism is used for forwarding as only one IP looku is erformed within the network When the cure is worse than the disease: The imact of graceful IGP oerations on BGP The cure IGP reconfiguration The side effects BGP induced anomalies The solutions sufficient conditions For truly safe network reconfiguration, the entire rotocol stack must be considered IGP reconfiguration techniques can create BGP anomalies leading to more disrution than the one they aim to avoid Guaranteeing BGP safety is hard, in the general case sufficient conditions exist, for articular cases Decouling BGP from the IGP solves the roblem but require rotocol changes When the cure is worse than the disease: The imact of graceful IGP oerations on BGP Laurent Vanbever IEEE INFOCOM Aril 18, 13
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks