Editing Border Gateway Protocol (section)

===512k day===
A [[Year 2000 problem|Y2K]]-like overflow triggered in 2014 for those models that were not appropriately updated.

While a full IPv4 BGP table {{as of|August 2014|lc=on}} (512k day)<ref>{{Cite web|url=https://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/117712-problemsolution-cat6500-00.html#.U-okMKwClYO.twitter|title=CAT 6500 and 7600 Series Routers and Switches TCAM Allocation Adjustment Procedures|website=Cisco}}</ref><ref>{{cite web |url=http://www.renesys.com/2014/08/internet-512k-global-routes |title=Internet Touches Half Million Routes: Outages Possible Next Week|work = renesys.com|date = 13 August 2014|first = Jim|last = Cowie|archive-url = https://web.archive.org/web/20140813232628/http://www.renesys.com/2014/08/internet-512k-global-routes/ |archive-date = 13 August 2014}}</ref> was in excess of 512,000 prefixes,<ref name= "Potaroo&nbsp;— BGP Table data">{{cite web|url=http://bgp.potaroo.net/index-bgp.html|title=BGP Reports|work=potaroo.net}}</ref> many older routers had a limit of 512k (512,000–524,288)<ref>{{cite web|url=http://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/117712-problemsolution-cat6500-00.html#.U-okMKwClYO.twitter |title= CAT 6500 and 7600 Series Routers and Switches TCAM Allocation Adjustment Procedures|date=9 March 2015|work=Cisco}}</ref><ref>{{cite web|url=http://www.renesys.com/2014/08/internet-512k-global-routes/|title=Internet Touches Half Million Routes: Outages Possible Next Week|author=Jim Cowie|work=Dyn Research|access-date=2015-01-02|archive-date=2014-08-17|archive-url=https://web.archive.org/web/20140817205028/http://www.renesys.com/2014/08/internet-512k-global-routes/|url-status=dead}}</ref> routing table entries. On August 12, 2014, outages resulting from full tables hit [[eBay]], [[LastPass]] and [[Microsoft Azure]] among others.<ref>{{cite news|title=Internet infrastructure 'needs updating or more blackouts will happen'|first1= Juliette |last1=Garside|first2= Samuel|last2= Gibbs|newspaper=The Guardian|date=14 August 2014|url=https://www.theguardian.com/technology/2014/aug/14/internet-infrastructure-needs-updating-more-blackouts-will-happen |access-date=15 Aug 2014}}</ref> A number of Cisco routers commonly in use had [[Ternary Content-Addressable Memory|TCAM]], a form of high-speed [[content-addressable memory]], for storing BGP advertised routes. On impacted routers, the TCAM was by default allocated as 512k IPv4 routes and 256k IPv6 routes. While the reported number of IPv6 advertised routes was only about 20k, the number of advertised IPv4 routes reached the default limit, causing a [[spillover effect]] as routers attempted to compensate for the issue by using slow software routing (as opposed to fast hardware routing via TCAM). The main method for dealing with this issue involves operators changing the TCAM allocation to allow more IPv4 entries, by reallocating some of the TCAM reserved for IPv6 routes, which requires a reboot on most routers. The 512k problem was predicted by a number of IT professionals.<ref>{{cite web|url=https://www.nanog.org/meetings/nanog39/presentations/bof-report.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.nanog.org/meetings/nanog39/presentations/bof-report.pdf |archive-date=2022-10-09 |url-status=live |title=BOF report |publisher= www.nanog.org |access-date=2019-12-17}}</ref><ref>{{cite web|url=http://etherealmind.com/tcam-detail-review/|title=TCAM&nbsp;— a Deeper Look and the impact of IPv6|author=Greg Ferro|work=EtherealMind|date=26 January 2011}}</ref><ref>{{cite web|url=http://www.ipv4depletion.com/?p=672|title=The IPv4 Depletion site|work=ipv4depletion.com}}</ref>

The actual allocations which pushed the number of routes above 512k was the announcement of about 15,000 new routes in short order, starting at 07:48 UTC. Almost all of these routes were to [[Verizon]] [[Autonomous system (Internet)|Autonomous Systems]] 701 and 705, created as a result of deaggregation of larger blocks, introducing thousands of new {{IPaddr||24}} routes, and making the routing table reach 515,000 entries. The new routes appear to have been reaggregated within 5 minutes, but instability across the Internet apparently continued for a number of hours.<ref>{{cite web|url=https://www.bgpmon.net/what-caused-todays-internet-hiccup/|title=What caused today's Internet hiccup|work=bgpmon.net}}</ref> Even if Verizon had not caused the routing table to exceed 512k entries in the short spike, it would have soon happened through natural growth.

[[Route summarization]] is often used to improve aggregation of the BGP global routing table, thereby reducing the necessary table size in routers of an AS. Consider AS1 has been allocated the big address space of {{IPaddr|172.16.0.0|16}}, this would be counted as one route in the table, but due to customer requirements or traffic engineering purposes, AS1 wants to announce smaller, more specific routes of {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}. The prefix {{IPaddr|172.16.192.0|18}} does not have any hosts so AS1 does not announce a specific route {{IPaddr|172.16.192.0|18}}. This all counts as AS1 announcing four routes.

AS2 will see the four routes from AS1 ({{IPaddr|172.16.0.0|16}}, {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}) and it is up to the routing policy of AS2 to decide whether or not to take a copy of the four routes or, as {{IPaddr|172.16.0.0|16}} overlaps all the other specific routes, to just store the summary, {{IPaddr|172.16.0.0|16}}.

If AS2 wants to send data to prefix {{IPaddr|172.16.192.0|18}}, it will be sent to the routers of AS1 on route {{IPaddr|172.16.0.0|16}}. At AS1, it will either be dropped or a destination unreachable [[ICMP]] message will be sent back, depending on the configuration of AS1's routers.

If AS1 later decides to drop the route {{IPaddr|172.16.0.0|16}}, leaving {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}, the number of routes AS1 announces drops to three. Depending on the routing policy of AS2, it will store a copy of the three routes, or aggregate {{IPaddr|172.16.0.0|18}} and {{IPaddr|172.16.64.0|18}} to {{IPaddr|172.16.0.0|17}}, thereby reducing the number of routes AS2 stores to two ({{IPaddr|172.16.0.0|17}} and {{IPaddr|172.16.128.0|18}}).

If AS2 now wants to send data to prefix {{IPaddr|172.16.192.0|18}}, it will be dropped or a destination unreachable ICMP message will be sent back at the routers of AS2 (not AS1 as before), because {{IPaddr|172.16.192.0|18}} is not in the routing table.