A hardware-engine for layer-2 classification in low-storage, ultra-high bandwidth environments

ABSTRACT

Ethernet is the most common Layer-2 network protocol, and it is currently being deployed beyond the tight borders of LANs. In order to accommodate the needs of MANs and WANs, several QoS mechanisms employed at the MAC sublayer of Ethernet have been proposed. These QoS mechanisms require identification of network flows and the classification of Ethernet packets according to certain Ethernet header fields. In this paper, we propose a classification engine employed at the MAC sublayer which uses an innovative hashing scheme and internal replacement of MAC Vendor IDs; the Hash Based Classification Engine (HBCE) compacts the tables containing the rules associated with certain MAC addresses and supports extremely high speed decisions --at a rate of more than 100Gb/sec-, while its memory needs are significantly lower compared to those of the similar schemes currently used. This engine has been implemented in hardware utilizing less than 0.1mm² in a state of the art CMOS technology. As a result HBCE is a very promising candidate for the next-generation Ethernet equipments that need to support classification at Data Link Layer at multi-Gigabit per second network speeds, whereas due to its very low memory requirements and low implementation complexity, it can also be employed very efficiently in lower-bandwidth wireless environments that utilize MAC mechanisms.

REFERENCES

• 1: IEEE 802.1q Standard, "Virtual Bridged Local Area Networks",
• 2: Giovanni Pau et. al, "A Cross-Layer Framework for Wireless LAN QoS Support", IEEE ITRE, August 11--13, 2003, Newark, New Jersey, USA
• 3: IEEE 802.1p Standard, "LAN Layer 2 QoS/CoS Protocol for Traffic Prioritization".
• 4: Enterprise Rack Mount Switches, http://www.ncasia.com/rfq/24port_0303.cfm?rfq=Enterprise_24-port_rack-mount_switch
• 5: R. A. Kempke and A. J. McAuley, "Ternary CAM Memory Architecture and Methodology." United States Patent 5,841,874, November 1998. Motorola, Inc.
• 6: P. Gupta and N. McKeown, "Algorithms for Packet Classification", IEEE Network, March/April 2001, vol. 15, no. 2, pp 24--32.
• 7: N. McKeown, B. Prabhakar, "Lectures on Packet Switch Architectures II -- Address Lookup and Classification", Stanford University
• 8: R. Jain, "A Comparison of Hashing Schemes for Address Lookup in Computer Networks", IEEE Transactions on Communications, Vol. 40, No. 3, October 1992, pp. 1570--1573
• 9: VIA Networking Atlantic#8482; VT6510A Switch Controller
• 10: V. Papaefstathiou , I. Papaefstathiou, A Memory Efficient, 100 Gb/sec MAC Classification Engine, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.470-471, November 15-17, 2005 [doi>10.1109/LCN.2005.9]
• 11: IEEE OUI and Company_id Assignments, http://standards.ieee.org/regauth/oui/index.shtml
• 12: A. Nikologiannis, M. Katevenis: "Efficient Per-Flow Queueing in DRAM at OC-192 Line Rate using Out-of-Order Execution Techniques", IEEE Int. Conf. on Communications (ICC'2001), June 2001, Helsinki, Finland, pp. 2048--2052