Some of the world's top network engineers are engaged in a research effort that could lead to the most radical redesign of the Internet's underlying routing architecture since it was developed in the 1980s.

The IRTF (Internet Research Task Force) is searching for a new routing architecture that would improve the Internet's ability to scale to support potentially billions of new users in developing countries. The IRTF is a sister organisation of the Internet Engineering Task Force, one of the Internet's leading standards bodies.

Under debate by the IRTF is how the Internet's backbone routers operate. Owned by carriers and some large corporations and government agencies, these backbone routers run the Border Gateway Protocol (BGP) to exchange routing information across the many interconnected networks that form the Internet.

The BGP routing table is a master list of network destinations that is stored in backbone routers and is used to determine the best available path from one network to another. Experts are worried about explosive growth in the BGP routing table, which is straining the processing and memory requirements of the Internet's core routers.

Why BGP growth matters

BGP routing table growth is significant because it drives up carrier costs, experts say.

"What CIOs really care about is the cost of their Internet connections, and if the cost of the service providers goes up because the routing table becomes unwieldy, that will lead to incremental costs for everybody," says Tony Li, co-chair of the IRTF's Routing Research Group. "We're interested in avoiding that scenario."

Slowing routing table growth would provide other benefits to enterprise network operators, too. It would make it easier to split network traffic over multiple carriers in a process called multihoming.

"One of the major causes of routing table growth is due to the pervasive practice of site multihoming," says Lixia Zhang, co-chair of the Routing Research Group. "Multihoming substantially increases the number of global routing table entries, and the Routing Research Group is working toward decoupling multihoming from the global routing table growth."

Zhang says another benefit will be easier renumbering of networks when enterprises switch carriers.

"One of our design goals is to eliminate the need for corporations to renumber their networks when they change providers," she adds. "Renumbering is considered a very expensive and complex process."

Seeking a new router architecture

The IRTF's Routing Research Group has existed for many years, but it was rechartered six months ago to look at future routing architectures.

As a sign of how serious it was about revitalising its Routing Research Group, the IRTF in February replaced former chair, Swedish professor Avri Doria, with two high-profile experts: uber router designer Tony Li, who has worked at Cisco, Juniper and Procket and is now back at Cisco; and Lixia Zhang, a computer science professor at the University of California at Los Angeles.

Since the Routing Research Group was revitalised, dozens of network engineers and researchers from around the world have participated in its thrice-annual meetings and online discussions. Among the network equipment vendors and service providers involved in the debate are Cisco, Juniper, Ericsson, Alcatel-Lucent, Huawei, AT&T, BT and Arbor Networks.

"The new focus of the working group is to work on a possible routing architecture that includes new ways of addressing, new ways of doing routing for the global Internet," Li says. "The IP address has both the identification of the node and the location of the node. The question becomes: Can we separate the identification from the locator semantics, and can we still run an Internet with that kind of architecture?"

The IRTF's Routing Research Group is "the most radical rethinking of routing ever," says Geoff Huston, a BGP routing table expert and chief scientist at the Asia Pacific Network Information Centre in Brisbane, Australia. "Routing and addressing are entirely connected concepts. They're joined at the hip. We did a significant rethinking about addressing when we adopted IPv6 [an upgrade to the Internet's main communications protocol, IPv4]. Now some of those ideas are resurfacing inside routing. We're looking at why we are routing and what we are doing."

Huston says the IRTF's Routing Research Group is considering making " a very, very big change for the architecture of routers. It has massive effects on the assumptions made in many applications."

Routing table growth

The IRTF's Routing Research Group is seeking new solutions to an old problem: BGP routing table growth.

Internet experts have known for years that explosive growth in the size of the BGP routing tables was a problem. It was a hot topic in 2001, but interest cooled when the dotcom bust resulted in a slowdown in the BGP routing table. The BGP routing table size has ramped up again rapidly in the last two years, and the issue has come to the forefront once again.

Today, the BGP routing table has around 240,000 routes, up from 195,000 a year ago and 100,000 six years ago.

"The trend over the last year and a half has been exponential growth," says Huston, who tracks BGP table growth for the Internet engineering community.

Huston says some older routers could fail when the routing table tops 244,000 entries.

"One of the deployed pieces of hardware out there has a configured upper limit in the content-addressable memory of 244,000 routes before it has a major problem," Huston says. "We are at the point where some of the deployed hardware is hitting its limits."

Growth in the BGP routing tables is tied to the number of corporations multihoming their networks as well as the number of service providers peering with others.

No one polices the BGP routing table. Any company can add a route to the routing table without paying extra for it, and everyone else in the backbone network has to carry the route at their own expense.

Huston says continued exponential growth in the routing table will shorten the life cycle of routers and increase their footprint, cost and power requirements. The unit cost of routing could get higher as routers get bigger, he says.

"What if a router two times the size was four times the price?" Huston asks. "Then everything we've ever thought about routing changes."

John Scudder, a participant in the IRTF group and a distinguished engineer with Juniper, says he is confident that router manufacturers will be able to support exponential growth in the BGP routing table for at least five years.

"Hardware that's on the leading edge of our product line and going forward is pretty well positioned to handle forwarding table growth," Scudder says. "The Juniper MX 960 and MX120 have the ability today to handle a million routes.... Going forward, the chips available now can scale up to 10 million."

Scudder adds that the IETF has "quite a few tricks up our sleeves to make the BGP protocol even more scaleable than it is today. And the nice thing is that this is incrementally deployable."

Still, Scudder admits that the BGP routing table is worrisome.

"Any time you see a growth curve is accelerating, it makes every engineer worried," he says. "I think we will be able to continue to keep pace with it as long as we don't take our eye off the ball."

Leading proposals emerge

The IRTF's Routing Research Group is in the early stages of its research, and it is still soliciting proposals from academic and corporate researchers for alternative routing architectures.

So far, two proposals have generated the most interest:

  • Locator/ID Separation Protocol (LISP), which was created by a group of Cisco engineers led by Dino Farinacci. LISP outlines a technique for separating Internet addresses into endpoint identifiers and routing locators. This design introduces the concept of tunnel routers, which add LISP headers to packets and strip the headers prior to final delivery. This approach reduces routing table size by cutting the number of globally visible routable prefixes.
  • Six/One, which was created by Christian Vogt at Ericsson, offers an alternative approach to multihoming that was designed for IPv6 networks. With Six/One, enterprises would have provider-dependent IP addresses from each of their service providers, and hosts use addressing spaces from all providers interchangeably. The host addresses differ only in their high order bits, which enables an edge network or a provider to change the address in a packet on the fly depending on the provider to which the packet is routed.
  • Neither proposal is a sure thing.

    The group is "very much in the discovery phase," says Tony Li, co-chair of the Routing Research Group. "We heard numerous proposals from various different researchers and engineers. We have, in my mind, a few proposals on the table, but those are still very much in the process of going from a framework to a more fleshed-out proposal."

    It's possible the Routing Research Group will recommend scrapping BGP altogether.

    "What we're trying to do is look at the fundamental routing architecture and make appropriate changes to that," Zhang says. "Once we've decided what the new routing architecture should look like, we can examine whether BGP may also require changes and what the changes may be."

    Huston says any change to BGP will be significant.

    "BGP exists on hundreds of thousands of routers out there, and changing BGP is not something that is going to be done lightly," Huston says.

    That's why Huston recommends keeping BGP but tweaking it so that it carries different, preferably less, information.

    "Maybe BGP won't carry the entire noise of the Internet and all the destinations, but instead it may carry a much smaller set of visible landmarks," he says.

    Leaders of the IRTF's Routing Research Group hope participants will agree on a solution within two or three years.

    "We don't know if there's a successful workable solution," Li says. "Until we discover one, it's an open-ended process."

    Any solution that the Routing Research Group comes up with is at least five years away from commercial availability, experts agree.

    "To expect anything deployed in the near future would be unlikely," Huston says. "This is quite deep research, and it's going to take quite a long time."

    Li and Zhang say they are cautiously optimistic about the group's ability to solve the routing table growth problem. They agree that whatever solution they come up with must be incrementally deployable and transparent to end users.

    "It is possible to make a significant change on the routing architecture, with very little disturbance in the currently deployed user base," Zhang says.

    If the Routing Research Group is unsuccessful, the Internet's backbone routers won't crash, experts say. But they will become increasingly expensive to run.

    Routing table growth is "not going to cause things to stop. It's just going to increase the pain level for certain people," Li says. If the routing table growth ever outstrips the ability of computer hardware to improve to handle it, "then the costs will start to get very ugly, very quickly," he adds.

    The Routing Research Group will hold its next meeting in December in Vancouver, British Columbia.

    The group is "only going to be significant if we do indeed have a deployable solution and it does get deployed," Li says. "If we're unsuccessful, then the group is irrelevant."