Authors S.V. Makov, D.V. Timofeev, D.Yu. Chernyshov
Month, Year 11, 2015 @en
Index UDC 004.71
Abstract The target of current studying is increasing of memory using efficiency for designing the associative lookup MAC-tables. These tables are used in network bridges and switches for traffic filtering. In the paper author discusses efficiency criteria of tables design methods. As criteria of efficiency was taken following: the amount of memory needed to allocate of the filtering table and the hash collision probability. In the paper is formulized a mathematical problem of determining of filtering table overflow probability based on algorithm of convenient way of the collision resolving. According the conditions of collision author formulize the combinatory problem. The solution of this problem allows determinate expression to compute collision probability for hash-table with convenient way of collision resolving by method of blocks. We propose method of filtering table design “without storing the address”. This method allows dramatically decrees the memory amount for table allocation. To comparison of efficiency of convenient and proposed methods we determinate the conditions of collision in hash-table designed by proposed method. Using these conditions we come up to expression that allows to determinate the collision probability of proposed hash-table design. We compared the overflow probability for proposed and convenient methods on similar conditions of using. We gave the recommendation for their usage. In result we found that for proposed method the overflow probability is more than 10 times lower in comparison with well-known method.

Download PDF

Keywords Lookup table; hash table; hash collision; network bridge; network switch.
References 1. Robert M. Metcalfe, David R. Boggs. Ethernet: Distributed packet switching for local computer networks, Communications of the ACMб July 1976, Vol. 19, No. 7б pp. 395-404.
2. IEEE Std 802.1D, 1998 Edition, Part 3: Media Access Control (MAC) Bridges.
3. Olifer V.G., Olifer N.A. Komp'yuternye seti: Printsipy, tekhnologii, protokoly Computer networks: Principles, technologies, protocols]. 3 ed. St. Petersburg: Piter, 2008, 958 p.
4. Michels T.S. et al. Network switching device with disparate database formats. Patent USA No. 6678269, 2004.
5. Mitchell G.R., Houdek M.E. Hash index table hash generator apparatus. Patent USA No. 4215402, 1980.
6. Wang Y., Wu S., McNeil Jr R. Using CRC-15 as hash function for MAC bridge filter design. Patent USA № 7620043, 2009.
7. Yik J., Wang L. High speed MAC address search engine. Patent USA No. 6697873, 2004.
8. Lim H., Chung Y. IP address lookup using either a hashing table or multiple hash functions. Patent USA No. 7418505, 2008.
9. Brady D. M. et al. MAC address table search unit. Patent USA No. 5914938, 1999.
10. Kormen T.Kh., Leyzerson Ch.I., Rivest R.L., Shtayn K. Algoritmy: postroenie i analiz [Algorithms: construction and analysis]. 2nd ed.: Translation from English, Ed. by I.V. Krasikova. Moscow: Izdatel'skiy dom «Vil'yams», 2005, 1296 p.
11. Knut D. Iskusstvo programmirovaniya dlya EVM [The art of computer programming]. Vol. 3. Sortirovka i poisk [Sorting and searching]: Translation from English. Moscow: Mir, 1978, 845 p.
12. Al'fred V. Akho, Dzhon Khopkroft, Dzheffri D. Ul'man. Struktury dannykh i algoritmy [Data structures and algorithms]: Translation from English: tutorial. Moscow: Vil'yams, 2000, 384 p.
13. Dumey A. Indexing for Rapid Random Access Memory Systems, Computers and Automation, 1956, Vol. 4, No. 12, pp. 6-9.
14. Knut Donal'd E. Iskusstvo programmirovaniya [The art of computer programming]. Vol. 4. Issue 3 Generatsiya vsekh sochetaniy i razbieniy [Generating all combinations and partitions]: Translation from English. Moscow: OOO «I.D. Vil'yams», 2007, 208 p.
15. Grekhem R., Knut D., Patashnik O. Konkretnaya matematika. Osnovanie informatiki [Concrete mathematics. The Foundation of information science]: Translation from English. Moscow: Mir, 1998, 703 p.
16. Makov S.V., Shrayfel' I.S. Otsenka effektivnosti fil'tratsii trafika v mezhsetevykh mostakh i kommutatorakh [Assessment of the effectiveness of traffic filtering in firewall bridges and switches], Servis v Rossii i za rubezhom [Services in Russia and abroad], 2011, Vol. 24, No. 5.
17. Makov S.V., Lityuk V.I. Organizatsiya tablits fil'tratsii «bez khraneniya adresov» v mezhsetevykh mostakh i kommutatorakh metodom parallel'nogo kheshirovaniya [The organization of tables of the filter "without the" in firewall bridges and switches the parallel method of hashing], Servis v Rossii i za rubezhom [Services in Russia and abroad], 2011, Vol. 24, No. 5.
18. Makov S. et al. Method of frame filtering table design without searching keys storing, Proc. IEEE ICSP, 2014, pp. 1542-1545. ISBN: 978-1-4799-2188-1.
19. Makov S. V. et al. A method for ultra fast search-ing within traffic filtering tables in networking hardware, IS&T/SPIE Electronic Imaging. – International Society for Optics and Photonics, 201, pp. 94100M-94100M-7.
20. Cyclone II: Device Handbook. Vol. 1, ALTERA. Available at: literature/hb/cyc2/cyc2_cii5v1.pdf.

Comments are closed.