High-Speed Router Functions

Participants
Institutions
  • Department of Computer and Information Science
  • WG Waldvogel (Distributed Systems)
Publications
  Zink, Thomas; Waldvogel, Marcel (2011): Exploiting Degrees of Freedom for Efficient Hashing in Network Applications

Exploiting Degrees of Freedom for Efficient Hashing in Network Applications

×

Hashing has yet to be widely accepted as a component of hard real-time systems and hardware implementations, due to still ex- isting prejudices concerning the unpredictability of space and time re- quirements resulting from collisions. While in theory perfect hashing can provide optimal mapping, in practice, finding a perfect hash function is too expensive, especially in the context of high-speed applications.
The introduction of hashing with multiple choices, d-left hashing and Bloom filter-based hash table summaries, has caused a shift towards guaranteed single-DRAM access. However, these guarantees come at a high price. High amounts of rare and expensive high-speed SRAM needs to be traded off for predictability. Moreover, it is infeasible for many applications to provide enough on-chip memory.
In this paper we show that previous suggestions suffer from the false pre- condition of full generality. To provide a workable solution, our approach exploits four individual degrees of freedom available in many practical applications, especially hardware and high-speed lookups. This reduces the requirement of on-chip memory up to an order of magnitude at the cost of only minute amounts of additional hardware. Our design makes fast hash table implementations cheaper, more predictable and above all, more practical.

Origin (projects)

  Zink, Thomas (2009): A Survey of Hash Tables with Summaries for IP Lookup Applications

A Survey of Hash Tables with Summaries for IP Lookup Applications

×

Efficient IPv6 packet forwarding is still a major bottleneck in todays networks. Especially in the internet core we are faced with very large routing tables and a high number of high-speed links. In addition economical restrains exist in terms of manufacturing and operation costs. So demand is high for efficient IPv6 packet forwarding mechanisms. In the last few years a lot of work has been done on hash tables and summaries that allow compact representations and constant lookup time. The features sound attractive for IPv6 routing, thus a survey and evaluation of these data structures seems appropriate.

Origin (projects)

  Zink, Thomas; Waldvogel, Marcel (2009): Packet Forwarding using Efficient Hash Tables

Packet Forwarding using Efficient Hash Tables

×

This report discusses our proposed improvements to Fast Hash Ta- bles (FHT) which we name 'Efficient Hash Table' (EHT) where 'efficient' relates to both memory efficiency and lookup performance. The mecha- nism we use to design the EHT lead to improvements in terms of sram memory requirements by the factor of ten over the FHT. Our results back the theoretical analysis and allow accurate predictions. A cost function is provided that allows the adjustment of EHT parameter to different user requirements.

Origin (projects)

    Fischer, Fabian; Mansmann, Florian; Keim, Daniel A.; Pietzko, Stephan; Waldvogel, Marcel (2008): Large-scale Network Monitoring for Visual Analysis of Attacks GOODALL, John R., ed., Gregory CONTI, ed., Kwan-Liu MA, ed.. Visualization for Computer Security. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 111-118. Lecture Notes in Computer Science. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-85931-4. Available under: doi: 10.1007/978-3-540-85933-8_11

Large-scale Network Monitoring for Visual Analysis of Attacks

×

The importance of the Internet and our dependency on computer networks are steadily growing, which results in high costs and substantial consequences in case of successful intrusions, stolen data, and interrupted services. At the same time, a trend towards massive attacks against the network infrastructure is noticeable. Therefore, monitoring large networks has become an importatnt field in practice and research. Through monitoring systems, attacks can be detected and analyzed to gain knowledge of how to better protect the network in the future. In the scope of this paper, we present a system to analyze NetFlow data using a relational database system. NetFlow records are linked with alerts from an intrusion detection system to enable efficient exploration of suspicious activity within the monitored network. Within the system, the monitored network is mapped to a TreeMap visualization, the attackers are arranged at the borders and linked using splines parameterized with prefix information. In a series of case studies, we demonstrate how the tool can be used to judge the relevance of alerts, to reveal massive distributed attacks, and to analyze service usage within a network.

Origin (projects)

    Waldvogel, Marcel; Hurley, Paul (2007): Bloom Filters: One Size Fits All? 32nd IEEE Conference on Local Computer Networks (LCN 2007). IEEE, 2007, pp. 183-190. ISBN 0-7695-3000-1. Available under: doi: 10.1109/LCN.2007.17

Bloom Filters: One Size Fits All?

×

Bloom filters impress by their sheer elegance and have become a widely and indiscriminately used tool in network applications, although, as we show, their performance can often be far from optimal. Notably in application areas where false negatives are tolerable, other techniques can clearly be better. We show that, at least for a specific area in the parameter space, Bloom filters are significantly outperformed even by a simple scheme. We show that many application areas where Bloom filters are deployed do not require the strong policy of no false negatives and sometimes even prefer false negatives. We analyze, through modelling, how far Bloom filters are from the optimal and then examine application specific issues in a distributed web caching scenario. We hope to open up and seed discussion towards domain-specific alternatives to Bloom filters while perhaps sparking ideas for a general-purpose alternative.

Origin (projects)

Further information
Period: 01.11.2007 – 30.04.2011