Design and Verification of Hardware Supported Forwarding Algorithms

OData support
Supervisor:
Horváth Dániel
Department of Telecommunications and Media Informatics

Nowadays computer networks have an increasing role in daily life. More and more applications are appearing with high bandwidth demands. Network elements in the networks are forwarding data using specialized hardware modules. These hardware modules can boost performance of the forwarding compared to software processing, and decrease the delay the data spend in the network element. The hardware usually does a table lookup to find the information e.g. the output port to where it has to forward the data. These can be stored in different memory types: TCAMs, SD RAMS or DDR RAMs. The performance of the lookup can be defined as the number of table lookups it needs to find the correct entry. This performance is highly depending on the used table lookup algorithm.

In this thesis I have written about the computer network types used today. The difference in the access networks and the backbone networks is discussed. Different protocol technologies such as Ethernet, Internet Protocol and Multiprotocol Label Switching are mentioned with respect to the network type they are used in. Four table lookup algorithms are described, namely the Naive algorithm, the Binary algorithm, the Hash based algorithm, and the Bloom Filter algorithm. The latter two are partitioning algorithms using buckets and hash functions. Then the design of theses algorithms to a given architecture using Ethernet forwarding protocol is presented. The environment and the interfaces to my implementation are shown. For each algorithm I define the entry format and show the algorithms flow charts adjusted to the specific environment. The designs are implemented in SystemC, and verified with different test cases. Then with simulations I show that the Naive algorithm need O(n), the Binary algorithm need O(log(n)) and both the Hash based and the Bloom Filter need O(c) memory accesses for tale lookup searches. An advantage of the Bloom Filter is that it better distributes entries in buckets. It is an advantage compared to the Hash based algorithm due to its better support for collisions. I will also show that the Bloom Filter has a disadvantage of needing more memory accesses when inserting an element incrementally compare to Hash based algorithm.

Downloads

Please sign in to download the files of this thesis.