Information Technology
Pipelined Lookup Grid Architecture (PLUG)–Fast, Cool and Flexible Network Processing
WARF: P09094US
Inventors: Cristian Estan, Karthikeyan Sankaralingam
The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing an Internet infrastructure component that can efficiently implement a wide range of performance-critical tasks in network processing.
Overview
Computer networks function by connecting spatially separated computers with “links” – electrical conductors, fiber optics and radio waves. The majority of network protocols work by dividing a data message into data packets, each attached to a destination address. A router (or sometimes a switch) reads this address and steers the data packets along a route through the complex and dynamic “links” of a network. Routers perform a variety of performance-critical tasks which require the router to look up addresses or other packet features from memory repeatedly and rapidly. The capacity of the router depends largely on how quickly these memory lookups are performed.
With existing technology, network equipment performs lookup operations with hardware that is inflexible and power-hungry. One approach for lookup is to read a table implemented in random access memory, which requires searching through multiple addresses and is generally a time-consuming process. High performance routers may use ternary content addressable memories (TCAM), which allow the entire memory to be searched in parallel and substantially reduces the time required to complete the search. However, this process consumes considerable power and generates greater amounts of heat. Networks are growing more complicated and routers are depended upon for additional tasks. Hence, future routers must support changes to the data structures and must easily allow deployment of new functionality and new lookups.
With existing technology, network equipment performs lookup operations with hardware that is inflexible and power-hungry. One approach for lookup is to read a table implemented in random access memory, which requires searching through multiple addresses and is generally a time-consuming process. High performance routers may use ternary content addressable memories (TCAM), which allow the entire memory to be searched in parallel and substantially reduces the time required to complete the search. However, this process consumes considerable power and generates greater amounts of heat. Networks are growing more complicated and routers are depended upon for additional tasks. Hence, future routers must support changes to the data structures and must easily allow deployment of new functionality and new lookups.
The Invention
UW-Madison researchers have developed Pipelined LookUp Grid (PLUG) as a component that can accommodate many types of lookup operations performed by network equipment while processing traffic. PLUGs offer a hybrid of storage and computation functions to address the energy efficiency and performance requirements of network devices.
PLUGs provide a specialized circuit for performing lookup operations in which the memory of a lookup table is divided into “tiles.” The connections between these tiles may be flexibly changed to match the particular problem being addressed. When a tree-type lookup is preferred, such as with IP addresses, the tiles can be configured into a tree structure. Conversely, when a hash table is preferred, such as in Ethernet-type lookups, the tiles can be reconfigured in parallel ranks suitable for hash tables. The ability to programmably configure individual memory elements allows the router to flexibly move between protocols and to manage lookup decisions at a phenomenally high rate (1 to 1.5 billion decisions per second).
PLUGs provide a specialized circuit for performing lookup operations in which the memory of a lookup table is divided into “tiles.” The connections between these tiles may be flexibly changed to match the particular problem being addressed. When a tree-type lookup is preferred, such as with IP addresses, the tiles can be configured into a tree structure. Conversely, when a hash table is preferred, such as in Ethernet-type lookups, the tiles can be reconfigured in parallel ranks suitable for hash tables. The ability to programmably configure individual memory elements allows the router to flexibly move between protocols and to manage lookup decisions at a phenomenally high rate (1 to 1.5 billion decisions per second).
Applications
- Improves flexibility, speed and power efficiency of Internet infrastructure
Key Benefits
- Achieves high lookup decision speeds
- Simple hardware
- Consumes low energy
- Reconfigures to manage different protocol types
- Matches or outperforms TCAM based solutions with far less power
Stage of Development
The development of this technology was supported by WARF Accelerator. WARF Accelerator selects WARF's most commercially promising technologies and provides expert assistance and funding to enable achievement of commercially significant milestones. WARF believes that these technologies are especially attractive opportunities for licensing.
Additional Information
For More Information About the Inventors
Publications
- De Carli L., Pan Y., Kumar A., Estan C. and Sankaralingam K. 2009. PLUG: Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers. SIGCOMM ’09, 207-218.
Tech Fields
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842