If it can find such an alternative path, it will copy this into its local forwarding table and announce this new preferred path to all its BGP neighbours.
If there is no such alternative path, it will announce a withdrawal to its neighbors, indicating that it no longer can reach this prefix. The first metric of interest is the size of the routing tables. Each router needs to store a local database of all prefixes announced by each routing peer.
In addition, conventional routing design places a complete set of "best" paths into each line card and performs a lookup into this forwarding data structure for each packet. This represents an extremely challenging silicon design problem.
The larger the routing search space, the more challenging the problem! If you look at the internals of a high-speed Internet router operating the default-free zone of the Internet one of the more critical performance aspects of the unit is to make a forwarding decision for each packet within the mean inter-packet arrival time, and preferably within the inter-arrival time of minimum-sized IP packets. If the average memory access cycle time is 10ns then this implies that the router line card processor needs to scan the entire decision space within just 7 memory access operations just to keep pace with the anticipated peak packet rate.
These very high-speed decision tables are often implemented using content-addressable memory to bypass this serial decision limitation. Ternary content-addressable memory TCAM can search its entire contents in a single memory cycle. TCAM size is what you purchase when you buy the router, so you need to pay attention to not only what you need today, but what you may need over the operational lifetime of the unit. If the router is to be useful in, say, 5 years from now, then you need to deploy units that can maintain their switching performance levels five years from now.
That often implies configuring your units with sufficient TCAM memory to contain IPv4 and IPv6 routing tables that are not only adequate for today but are adequate to meet the routing table requirements some years into the future. What this means is this size question is an important question both to network operators and to designers and vendors of network switching equipment.
Secondly, there is the overall stability of the system. Processing a routing update requires several lookups into local data structures as well as local processing steps. Each router has a finite capacity to process updates, and once the update rate exceeds this local processing capability, then the router will start to queue up unprocessed updates. In the worst case, the router will start to lag in real-time, so that the information a BGP speaker is propagating reflects a past local topology, not necessarily the current local topology.
If this lag continues then at some point unprocessed updates may be dropped from the queue. BGP has no inherent periodic refresh capability, so when information is dropped, then the router and its neighbours fall out of sync with the network topology.
At its most benign, the router will advertise "ghost" routes where the prefix is no longer reachable, yet the out-of-sync router will continue to advertise reachability. This may cause saturation of the underlying transmission system and trigger further outages which, in turn, may add to the routing load.
The two critical metrics we are interested in are the size of the routing space and its level of updates, or "churn". Here we will look at the first of these metrics, the size of the routing space, and the changes that occurred through , and use this data to extrapolate forward and look at 5-year projections for the size of the routing table in both IPv4 and IPv6. In trying to analyse long baseline data series the ideal approach is to keep as much of the local data gathering environment as stable as possible.
In this way, the changes that occur in the collected data reflect changes in the larger environment, as distinct from changes in the local configuration of the data collection equipment. There is also no internal routing iBGP component in this measurement setup. While it has been asserted at various times that iBGP is a major contributor to BGP scalability concerns in BGP, the consideration here in trying to measure this assertion is that there is no "standard" iBGP configuration, as each network has its own rather unique configuration of Route Reflectors and iBGP peers.
This makes it hard to generate a "typical" iBGP load profile, let alone analyse the general trends in iBGP update loads over time. In this study, the scope of attention is limited to a simple eBGP configuration that is likely to be found as a "stub" AS at the edge of the Internet.
This AS is not an upstream for any third party, it has no transit role, and does not have a large set of BGP peers. It's a simple view of the routing world that I see when I sit at an edge of the Internet. Like all BGP views, its unique to this network, and every other network will see a slightly different Internet with different metrics. However, the behaviour seen by this stub network at the edge of the Internet is probably similar to most other stub networks at the edge of the Internet.
While the fine details may differ, the overall picture is probably much the same. Measurements of the size of the routing table have been taken regularly since the start of , although highly detailed snapshots of the routing system only date back to early Figure 1 shows a rather unique picture of the size of the routing table, as seen by all the peers of the Route Views route collector on an hourly basis.
I should take a moment to mention the Route Views Project. It was originally intended to offer a multi-perspective real-time view of the inter-domain routing system, allowing network operators to examine the current visibility of route objects from various points in the inter-domain topology. What makes Route Views so unique is that it archives these routing tables every two hours and has done so for more than two decades.
It also archives every BGP update message. This vast collection of data is a valuable research data source in its own right, and here we are just taking a tiny slice of this data set to look at longer term routing growth trends. This is a very unique data set if you are interested in the evolution of the Internet over the years. Several broader events are visible in the history of the routing table, such as the busting of the Internet bubble in , and if one looks closely, the effects of the global financial crisis in What is perhaps surprising is one ongoing event that is not visible in this plot: since the supply of IPv4 addresses has been progressively constrained as the free address pools of the various Regional Internet Registries have been exhausted.
Yet there is no visible impact on the rate of growth of the number of announced prefixes in the global routing system since Figure 1 — IPv4 routing table since as seen by Route Views peers. BGP is not just a reachability protocol. Network operators can manipulate traffic paths using selective advertisement of more specific addresses, allowing BGP to be used as a traffic engineering tool. These more specific advertisements often have a restricted propagation.
There is not a single plot in this figure where each BGP speak sees essentially the same network. There is a variance across the various peers of these route collectors that is around 50, routes. Figure 7 shows the profile of IPv6 updates since The number of withdrawals per day has been growing steadily across this period. This number has been rising since , and during we are saw some 35, updates per day with peaks of more than 80, updates per day. The final months of saw a dramatic rise in the instability in IPv6, with the daily update count rising to 1.
This shows some pathological instability in parts of the IPv6 network which may be due to some form of BGP route oscillation that fails to converge. Figure 8 shows that the number of unstable prefixes has changed since the start of The high count of updated prefixes suggests a topology-based oscillation in one of the upstream feeds for this network that appears to affect one half of the total count of prefixes in the IPv6 routing table.
This instability was partially addressed at the start of but has since returned in the latter months of The issue with running two discrete routing systems within the Internet is that it is sometimes the case that operational attention remains fixated on the IPv4 routing system, while IPv6 is simply assumed to be working on the basis that the IPv4 network is stable. Routing pathologies in the IPv6 network appear to remain unnoticed for many months, and at the end user level the dual stack environment simply masks the issues.
Failure to connect in IPv6 is silently fixed in the happy eyeballs behaviour mode by rapidly switching to use IPv4 for the affected sessions. The average time to reach convergence has been unstable for the IPv6 network Figure 9. The daily average of this convergence time ranges between 70 and seconds. The last half of saw some period of high instability with protracted times of up to seconds to reach convergence for individual prefixes.
It is also evident that the distribution of updates across the set of announced prefixes and originating ASNs is far more skewed than IPv4. The distribution of updates is shown in Figures 10 and It is not immediately obvious why IPv6 has this higher instability component than IPv4. A concern is that this instability remains a persistent condition as the IPv6 network continues to grow, which would create a routing environment that would impose a higher processing overhead than we had anticipated, with its attendant pressures on BGP processing capabilities in the network.
BGP is a distance vector routing protocol that achieves a coordinated stable routing state through repeated iterations of a local update protocol. The efficiency of the protocol depends heavily on the underlying topology of the network. Highly clustered topologies, such as star-based topologies, will converge quickly, whereas arbitrary mesh-based topologies will generally take longer to converge to a stable state. The convergence behaviour of BGP, particularly in the IPv4 network is quite remarkable, and perhaps the best illustration of why this is the case lies in the average AS Path length of the BGP routing table over time Figure Only 14 networks have more than AS adjacencies that are advertised in to the transit network.
In the case of IPv6 there are other factors that appear to influence the overall stability of IPv6. However, the distributions of Figures 10 and 11 need to be remembered. When we are talking average update volumes, we are actually talking about a very small set of prefixes that generate anomalously high numbers of updates. We can look further into these updates to see if there is any visible correlation between routing practices by network operators and BGP instability. If we look at just those updates that refine an already announced address prefix, then we can use a taxonomy of the effect of the routing update.
Figure 16 — Distribution of Update Types in the V4 network. Figure 17 — Distribution of Update Types in the V6 network. It is challenging to understand the rationale for this level of Attribute churn in the IPv4 network given that it has no evident impact on the underlying forwarding decisions or the underlying inter-AS topology The IPv6 network shows a similar pattern, although AS Path changes are slightly more prevalent than Attribute changes by the end of Another way of looking at this data is to remove the absolute volume of updates and look at the update types as a proportion of the total number of updates seen each day Figures 18 and It is likely that much instability is due to BGP oscillation when negotiating routing policies relating to multiple paths.
As a distributed algorithm, BGP itself is not a deterministic process, and when the protocol is attempting to negotiate a stable outcome between the BGP preferences of BGP speakers announcing reachability across multiple egress paths, and BGP listeners applying local preferences across a number of ingress paths, then some level of instability is not unexpected. Indeed, what is perhaps most surprising here is that these BGP updates are so low, particularly when the underlying topology appears to show such a rich level of interconnection.
When a BGP environment becomes unstable and flips between multiple local states that are all equivalent one might expect that the BGP update rate would increase uncontrollably.
BGP will only emit updates every MRAI seconds, and only pass on the current state of each updated prefix at that time, damping out any form of higher frequency local route oscillation. The commonly used value of 27 — 30 seconds varied randomly each MRAI interval is the most likely explanation of why BGP appears to be so well behaved in terms of update rates.
Change in FIB Size. Valid entries. Suppressed RIB entries. Damped entries. History entries. Total address space advertised prefix length. Average address span. Average address span as prefix size. Average prefix length. Entries advertising more specific prefixes of aggregates. Specifics where AS prepended Path matches aggregate.
AS Path matches aggregate. AS Origin matches aggregate. Root Prefixes. Root Prefix Tree Depth. Root Prefixes with depth 0. Root Prefixes with depth 1. Root Prefixes with depth 2.
Root Prefixes with depth 3. Root Prefixes with depth 4. Root Prefixes with depth 5. Root Prefixes with depth 6. Root Prefixes with depth 7. Unique ASes. ASes visible in only one AS path. Origin only ASes. Origin ASs announced via a single AS path. Transit only ASes. Mixed ASes. Multi-Origin Prefixes. ASes originating a single prefix. Average entries per origin AS. Maximum entries for an origin AS AS Average address range span for an origin AS. Maximum address range for an origin AS AS Unique AS Paths.
Unique AS prepended Paths. AS Paths using prepending. AS paths associated with a single FIB entry. AS Paths using private ASs. Average AS path length. Maximum AS Path length. Average address weighted AS path length. Maximum prepended AS Path length. Average entries per AS Path. AS Paths per origin AS. Prefix Count. Root Prefix Count. Addresses by AS distance.
Address percentage by AS distance. Addresses at AS distance 0.
0コメント