Статья

Название статьи ЭФФЕКТИВНОЕ ИСПОЛЬЗОВАНИЕ ПАМЯТИ ПРИ ОРГАНИЗАЦИИ ТАБЛИЦ MAC-АДРЕСОВ В МЕЖСЕТЕВЫХ КОММУТАТОРАХ
Автор С.В. Маков, Д.В. Тимофеев, Д.Ю. Чернышов
Рубрика РАЗДЕЛ III. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, ПРИКЛАДНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ И СЕТИ
Месяц, год 11, 2015
Индекс УДК 004.71
DOI
Аннотация Целью данного исследования является увеличение эффективности использования памяти, необходимой для размещения ассоциативных таблиц поиска MAC-адресов, применяемых для фильтрации трафика в межсетевых мостах и коммутаторах. Рассмотрены критерии эффективности организации таких таблиц. В качестве критериев эффективности определены объем памяти, требуемой для размещения таблицы фильтрации, и вероятность переполнения таблицы фильтрации, вызванной коллизией хеширования. На основании алгоритма работы известного способа разрешения коллизий сформулирована математическая задача определения вероятности переполнения таблиц фильтрации. В соответствии с условиями появления коллизий была поставлена комбинаторная задача, решение которой позволило получить аналитическое выражение, позволяющее определить вероятность переполнения таблицы фильтрации, организованной известным способом с разрешением коллизий методом блоков. Предложен способ организации таблиц фильтрации «без хранения адресов», позволяющий значительно уменьшить требуемый объем памяти. Для сравнения эффективности известного и предложенного методов были определены условия появления коллизий в хешированных таблицах, организованных предложенным способом. На основании этих условий было получено аналитическое выражение, позволяющее определить вероятность переполнения таблицы фильтрации для предложенного способа. Проведено сравнение вероятности переполнения таблиц фильтрации, организованных известным и предложенным способом, при решении одинаковой задачи и даны рекомендации для применения предложенного и известного способов организации таблиц фильтрации. Установлено, что предложенный метод позволяет уменьшить вероятность переполнения таблицы фильтрации более чем в 10 раз при заданном объеме памяти для размещения таблицы по сравнению с известным.

Скачать в PDF

Ключевые слова Таблицы поиска; хешированные таблицы; коллизии хеширования; межсетевой мост; коммутация кадров.
Библиографический список 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. – P. 395-404.
2. IEEE Std 802.1D, 1998 Edition, Part 3: Media Access Control (MAC) Bridges.
3. Олифер В.Г., Олифер Н.А. Компьютерные сети: Принципы, технологии, протоколы. – 3-е изд. – СПб.: Питер, 2008. – 958 с.
4. Michels T.S. et al. Network switching device with disparate database formats. Патент № 6678269 США. – 2004.
5. Mitchell G.R., Houdek M.E. Hash index table hash generator apparatus. Патент № 4215402 США. – 1980.
6. Wang Y., Wu S., McNeil Jr R. Using CRC-15 as hash function for MAC bridge filter design. Патент 7620043 США. – 2009.
7. Yik J., Wang L. High speed MAC address search engine. Патент № 6697873 США. – 2004.
8. Lim H., Chung Y. IP address lookup using either a hashing table or multiple hash functions: Патент 7418505 США. – 2008.
9. Brady D. M. et al. MAC address table search unit. Патент № 5914938 США. – 1999.
10. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ. / под ред. И.В. Красикова. – 2-е изд. – М.: Издательский дом «Вильямс», 2005. – 1296 с.
11. Кнут Д. Искусство программирования для ЭВМ. T. 3. Сортировка и поиск: Пер. с англ. – М.: Мир, 1978. – 845 с.
12. Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы: пер. с англ.: учеб. пос. – М.: Изд. дом «Вильямс», 2000. – 384 c.
13. Dumey A. Indexing for Rapid Random Access Memory Systems // Computers and Automation. – 1956. – Vol. 4, No. 12. – P. 6-9.
14. Кнут Дональд Э. Искусство программирования. T. 4. Вып. 3. Генерация всех сочетаний и разбиений: пер. с англ. – М.: Изд. дом «Вильямс», 2007. – 208 с.
15. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. – М.: Мир, 1998. – 703 с.
16. Маков С.В., Шрайфель И.С. Оценка эффективности фильтрации трафика в межсетевых мостах и коммутаторах // Сервис в России и за рубежом. – 2011. – Т. 24, №. 5.
17. Маков С.В., Литюк В.И. Организация таблиц фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах методом параллельного хеширования // Сервис в России и за рубежом. – 2011. – Т. 24, №. 5.
18. Makov S. et al. Method of frame filtering table design without searching keys storing // Proc. IEEE ICSP. – 2014. – C. 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, 2015. – P. 94100M-94100M-7.
20. Cyclone II: Device Handbook. Vol. 1 // ALTERA. URL: http://www.altera.com/literature/hb/cyc2/cyc2_cii5v1.pdf.

Comments are closed.