The shortest path not taken

It's been nearly 50 years since Dutch computer scientist Edsger Dijkstra created the algorithm that would form the basis of the widely used routing protocol known as Open Shortest Path First.

A new set of pressures, perhaps unforeseeable then, is converging on carrier networks these days, including escalating traffic volumes and evolving classes of service. And so new algorithms have been proposed to maximize efficiency in metro networks, from start-up suppliers such as Ethos Networks and Soapstone Networks. One of the latest comes from Gridpoint Systems, whose one-rack-unit metro edge node, the 3400, was unveiled last week, proposed in conjunction with the vendor's control plane software, and scheduled for availability in October.

Whereas some element management systems on the market view the network on a hop-by-hop basis, Gridpoint said its gear looks at the network holistically to determine optimum provisioning routes, and those aren't always the shortest path.

“Often times the shortest path in the network becomes a congestion point in the network, and the rest of the resources around it are underutilized,” said Jim Arseneault, president and CEO of Gridpoint.

In Gridpoint's system, deciding which path to provision depends in part on the specific characteristics of the traffic being provisioned, the service level agreements it entails and the characteristics of network routes beyond mere distance. Carriers can input “business rules” into the system that take into account considerations such as which paths are less desirable because they are leased from competitors, for example.

“For a low-quality Internet service, as opposed to video service, [a network operator] may choose to put it through a path that's a little more meandering but uses underutilized resources, so that he can leave that core path — the high-cost, high-quality path — for new video services or more [voice-over-IP] trunks,” Arseneault said.

In trials Gridpoint performed with Tier 1 carriers, an existing operations support system (OSS) provisioning solution asked Gridpoint's software to determine optimum paths to provision, after which the OSS provisioned the link itself, communicating directly with network nodes.

Gridpoint's technology is based on provider backbone transport and provider backbone bridging techniques and operations, administration and maintenance standards 802.1ag (from the IEEE) and Y1731 (from the ITU). And it uses its own algorithm for what it calls “multiconstraint routing,” rather than Dijkstra's famous algorithm.

“The Dijkstra algorithm finds one path with one constraint,” said Brian Smith, chief technology officer and vice president of R&D for Gridpoint. “A lot of people today pick ‘cost’ or ‘hops’ or ‘delay,’ but they don't look at all of those parameters. We find all paths that meet those requirements. Then we look at our business rules, which may be load-balancing, and pick the path that meets the objectives with the least amount of bandwidth on it.”