The fast increase of the Internet routing table size on the Default-free Zone (DFZ) is becoming a major concern to IP carriers all over the world. The number of active BGP entries on border routers is increasing at a quadratic if not exponential rate (see figure below). The future unhindered scalability of the Internet is in doubt. In spite of the use of Border Gateway Protocol (BGP), inter domain routing does not scale any more these days as the volume of routing information keeps on growing by the day and it is not clear if the current routing technology will keep pace with this growth and still do it cost effectively. Today it costs more for border routers to exchange routing information than it did few years ago due to investment in more powerful routers that can keep up with this growth.
The depletion of the IPv4 address space and the inevitable adoption of the IPv6 addressing scheme means that routers will now have to exchange much larger routing tables because the vast amount of IPv6 addresses require even more prefixes to be announced in the Default-free Zone. This problem will be compounded by the desire by network operators to announce more specific ( and hence longer prefix) routes to their critical infrastructure such as DNS and Content Delivery Networks (CDNs) in the now wider prefixes in IPv6. This tendency to announce very specific routes by use of longer prefixes stems from the desire to prevent prefix hijacking by malicious Autonomous Systems (AS’s) as was the case in 2008 when an AS owned by Pakistan Telecom announced the Youtube IP space with a longer prefix leading to Youtube traffic being redirected to Pakistan because it was the more specific route. With cyber crime rates increasing worldwide, network engineers want to ensure high availability of their networks on the Internet and end up announcing very long prefixes that have an effect of making the Internet routing table unnecessarily larger. This is the reason why I still think the old rule of eBGP routers filtering any route to a network longer than a /22 should still be in force. A peek on some Internet routing tables will show the existence of even /25’s.
The growing size of the Internet and its inevitable changes and failures leads to a large rate of routing table updates that stresses router CPUs and there have been several proposals made to modify BGP to make it scale. The current routing tables are linear and its high time logarithmic scale routing was introduced that can summarize routes in a logarithmic fashion. By this I mean that summarization of prefixes should be much more intense at the longer side and less intense as the prefixes become shorter.
The above can be achieved in three ways namely:
Aggregation proxies: In this way, ISPs will announce or redistribute routes to their networks via a non BGP protocols to a router aggregation proxy. This proxy will receive many long prefixes and aggregate them into shorter ones for eventual announcement via BGP. The regional allocation of IPs through organizations such as LAPNIC, RIPE, AfriNIC and the rest make aggregation proxies a very viable path because the regional allocation of IP spaces is not random (e.g. any IP starting with 196. or with 41. is from an African ISP). AfriNIC can therefore host aggregation proxies that speak to African border routers via a non BGP protocol and this aggregation proxy can then announce a single entry of say the 196 range to the Internet. the other local aggregation servers in Americas, Europe and Asia can then have filters to reject any inbound traffic to the Africa IP’s because that would be IP hijacking. The downside to aggregation proxies is that paths will now be longer as the proxy introduces an extra hop. the trade-off between a massive reduction of the routing table size and path elongation has to be weighted to see if this is a viable alternative.
DNS-like lookup system: This system will apply to non routable prefixes. in this concept, all the long prefixes are retained and recorded in a DNS-like lookup system in which a particular IP space is mapped to a specific border router. Anyone wishing to communicate with this IP space will do a lookup to get a next hop IP address and send this traffic to it. As a result, the long prefixes are not routable on the Internet but the lookup system knows a router from which the traffic can be forwarded without the use of inter-domain routing information. In simple terms this will be like a DNS not for domain names but for long prefix IP spaces. This proposal will eliminate the need to have long prefixes on the Internet routing table and a bar can be set to filter anything longer than say a /19 from being announced on the now cleaner DFZ. This will have the advantage of returning control of what appears on the DFZ routing table to regional organizations such as AfriNIC as opposed to AS managers who can sometimes be selfish.
Locator-Identifier split (Loc/ID): Whereas the above two methods overlay the existing BGP and enhance it, this approach replaces the existing inter domain routing as we know it. The Locator-Identifier split (Loc/ID) proposes the scraping of IP addressing as we know it and coming up with 2-level routing architecture to replace the current hierarchical inter-domain system. The argument behind Loc/ID is that the reason why IP-based routing is not scalable is because the IP address assigned to a device is now being used as its unique Identifier as opposed to it serving the dual role of it being both a locator and identifier. By splitting it into a Locator section and an ID section, then summarizing the locators on the DFZ, considerable reductions can be achieved on the routing table because routing on the DFZ will be based on locators and not on both locators and identifiers. Cisco recently developed the Loc/ID separation Protocol (LISP) that is hoped will replace BGP in future as BGP will no longer be able to scale a bigger IPv6 Internet. Read more about LISP by clicking here. Cisco is currently promoting LISP as an open standard and not a proprietary standard in the hope that the Internet Engineering Task Force (IETF) will adopt it.
In summary, network operators need to be aware of the non-scalability of BGP and start preparing their networks for the adoption of either of the 3 proposals above. I would however bet that the Loc/ID way of doing things will prevail and LISP will replace BGP as the inter domain routing protocol of choice on the Internet.