| overview | - | What is our approach to nework management? |
| papers | - | Papers and publications |
| talks | - | Selected presentation slides |
| people | - | Who are we? |
Our research focuses on leveraging support from network elements to build new network primitives and protocols. This typically involves network elements storing some state or performing special actions. One of our projects, Net-Replay, looks at how network elements can aid in enabling communicating pairs of end hosts to characterize the glitches their packets encounter. In our architecture, network elements maintain information about the packets that it has seen within a small interval of time. Packets expose a marking interface using which a network element can indicate whether or not it has seen the packet in the recent past. When end applications observe glitches, they replay the packets that possibly observed the glitch, and network elements provide feedback using the marking interface, which can be useful in determining the type of glitch the earlier packets in the flow were experiencing.
An associated problem with network elements storing a large amount of data is achieving good access times with low cost hardware. The Bufferhash project looks at this challenge in the context of content based systems. Applications like WAN optimization and data deduplication require large hashtables for their operation. One option is to maintain these huge datastructures on disk. But high access times might hurt performance. Another option is to store them in memory, but it might prove to be very costly. We propose an alternate hashtable design using a combination of small DRAM and flash memory. We show that Bufferhash achieves a significantly higher hashtable operations per second per dollar compared to traditional naive approaches.
The core idea behind Bufferhash is to group insert operations in a small hashtable called an 'incarnation'
in memory, and push the incarnation's hashtable to flash in one go. Incarnations are appended to the flash memory
as and when they are flushed from memory. Batching writes significantly improves the average insert operation cost,
since a single write requires erasing a complete flash block, which is slow. The figure
shows the organization of incarnations in the memory and the flash.
Now, < key,value > pairs are stored in incarnation hashtable bins in the order in which they were inserted. A naive lookup would examine each incarnation by age for the key. This would be very slow. To speed this process, we maintain a bloom filter of keys corresponding to each incarnation as shown in the figure. These bloom filters are stored in memory and are consulted during lookup of a key. If a bloom filter indicates the presence of the key in an incarnation, we get the corresponding value from the hashtable stored in flash.