Fast and efficient address search in System-on-a-Programmable-Chip using binary trees

Abstract

One processing task in Ethernet nodes is to manage Media Access Control (MAC) addresses: search, insert new, and delete old ones. For this purpose, Content-Addressable Memorys (CAMs) offer low latency and no collisions; however, they consume too many electronic resources, and working frequency is constrained. On the other hand, hash tables demand few circuits allowing fast operations; unfortunately, collisions often occur, causing delays in the process. Finally, binary trees arise as one efficient technique to search addresses by hardware, although updating them is complex.

The design presented in this paper, based on an Adelson-Velsky and Landis (AVL) binary tree, takes advantage of the mixed hardware/software capabilities of Multiprocessor Programmable System-on-a-Chip (MPSoC) devices. It forwards frames on the fly: a hardware core, searches addresses in an AVL tree, and a program inserts and deletes them. This solution requires few resources and, to the best of our knowledge, is the first to manage MAC addresses in an AVL tree and to exploit a hardware/software System-on-a-Chip (SoC) for this purpose.