Метод уменьшения размера таблиц маршрутизации в IP-сетях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Шиготаров, Андрей Владимирович

• Шиготаров, Андрей Владимирович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Шиготаров, Андрей Владимирович

Содержание.

Список сокращений.

Введение.

Глава 1. Обзор и анализ существующих методов уменьшения размера таблиц маршрутизации.

§1.1. Маршрутизация, архитектура маршрутизаторов.

§ 1.2. Обзор методов оптимизации поиска в таблицах маршрутизации.

§1.3. Методы уменьшения размера таблиц маршрутизации.

§1.4. Методы минимизации булевых функций большой размерности.

1.4.1 Классификация алгоритмов минимизации булевых функций.

1.4.2 Алгоритмические сложности решения задачи минимизации ДНФ

1.4.3 Точные алгоритмы минимизации ДНФ.

1.4.4 Приближенные алгоритмы.

Выводы.

Глава 2. Разработка метода уменьшения таблиц маршрутизации в IP-сетях.

§2.1. Метод уменьшения размера таблиц маршрутизации.

§ 2.2 Точный алгоритм минимизации булевых функций в классе ДНФ.

2.2.1 Двоичные диаграммы решения.

2.2.2 Генерация всех простых импликант булевой функции.

2.2.3 Упрощение матрицы покрытия.

2.2.4 Построение минимального покрытия.

§2.3 Приближенный алгоритм минимизации ДНФ.

Выводы.

Глава 3. Компьютерное моделирование и экспериментальная оценка разработанного метода уменьшения таблиц маршрутизации.

§3.1. Выбор средств разработки программного пакета.

§3.2 Программная реализация разработанного метода уменьшения таблиц маршрутизации.

3.2.2 Описание программного продукта.

§ 3.3 Применение разработанных методов минимизации ДНФ для уменьшения размера таблиц маршрутизации.

§ 3.4. Оценка зависимости производительности маршрутизатора от размера таблицы маршрутизации.

§ 3.5 Экспериментальная оценка эффективности предложенных алгоритмов для задач из набора MCNC Benchmarks.

Выводы.

Введение диссертации (часть автореферата) на тему «Метод уменьшения размера таблиц маршрутизации в IP-сетях»

Актуальность исследования. Неотъемлемой частью процесса построения быстродействующих сетей является разработка эффективных схем хранения и поиска записей в таблицах маршрутизации (ТМ). Одним из следствий быстрого роста Internet стало значительное увеличение размера таблиц маршрутизации. Данный факт, а также ограниченность ресурсов программного и аппаратного обеспечения, существенно затрудняют возможность их эффективной обработки. Исследователями было предложено большое количество схем для увеличения скорости поиска в таблицах маршрутизации. Алгоритмические методы включают в себя: локальный поиск, двоичный поиск, использование специальных структур данных (бинарные деревья, трие), хеширование и ряд других. Основным недостатком данных подходов является то, что они требуют нескольких обращений к памяти. Требования к производительности современных сетей являются очень высокими, в то время как время отклика современных архитектур памяти ограничивают возможное количество обращений к памяти. Одним из наиболее распространенных и перспективных аппаратных решений является тернарная ассоциативная память (ТСАМ). Главной особенностью ТСАМ является то, что адресация осуществляется на основе содержания данных, поиск нужной записи, при этом, может быть осуществлен за одно обращение к памяти. Значительное число исследований, посвященных проблеме повышения эффективности обработки таблиц маршрутизации, ориентировано на использование данной аппаратной реализации и основано на методах сжатия таблиц маршрутизации [87]. Уменьшение таблиц маршрутизации позволяет повысить скорость поиска нужной записи, использовать память меньшего размера, а также снизить энергопотребление маршрутизатора. Современное состояние дел в данной области знаний во многом основано на работах Х.Лиу (Н. Liu)[56], С. Стергиоу(S.Stergiou)[83], В. Равикумара (V. Ravikumar)[74], Р. Гуо (R.Guo) и Ж. Дельгадо-Фриаса (J.

Delgado-Frias)[45]. Отечественные авторы, например, В. Г. Олифер и Н. А. Олифер[9], внесли вклад в развитие теоретических основ проблем эффективной маршрутизации. Большинство существующих методов сжатия таблиц маршрутизации основано на сведении данной проблемы к задаче минимизации булевых функций в классе дизъюнктивных нормальных форм. При этом используются алгоритмы минимизации, которые были разработаны в первую очередь для оптимизации интегральных схем и не учитывают специфику данной задачи. В связи с этим, возможность их практического применения ограничена задачами небольшой размерности.

Объектом исследования в работе является обработка таблиц маршрутизации в ЕР-сетях. Предметом исследования являются методы сокращения размеров таблиц маршрутизации, как средства повышения скорости обработки пакетов и снижения затрат памяти для хранения информации о маршрутах в сети.

Цели и задачи исследования. Целью настоящей работы является разработка быстродействующего метода уменьшения размера таблиц маршрутизации, позволяющего уменьшить время поиска записей, снизить энергопотребление маршрутизатора и сократить аппаратные затраты. Для выполнения данной цели необходимо решить следующие задачи:

• анализ существующих методов сокращения таблиц маршрутизации;

• построение математической модели таблиц маршрутизации;

• разработка быстродействующих методов сокращения таблиц маршрутизации;

• экспериментальное исследование эффективности предлагаемых алгоритмов.

Методы исследования. При решении поставленных задач использовались методы математического моделирования, дискретной оптимизации, теории графов, линейного программирования.

Научная новизна

1. Предложен подход к решению задачи оптимизации размеров таблиц маршрутизации, использующий для представления IP-адресов импликанты булевых функций. В основу подхода положено применение:

• двоичных диаграмм решения для совместной обработки импликант,

• метода ветвей и границ для ограничения перебора в пространстве возможных решений,

• двухуровневого представления импликант для повышения скорости поиска в множестве всех исходных импликант,

• эвристического алгоритма выборочной генерации простых импликант булевых функций.

Сочетание составных частей подхода по определенным правилам позволяет строить эффективные алгоритмы уменьшения размера таблиц маршрутизации.

2. Разработан точный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на использовании двоичных диаграмм решения и метода ветвей и границ, отличающийся более высокой скоростью работы, по сравнению с известными подходами.

3. Разработан приближенный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на двухуровневом представлении множества импликант функции и эвристическом алгоритме генерации простых импликант. Показана возможность применения предложенного алгоритма для сокращения размера таблиц маршрутизации большой размерности в режиме реального времени.

Основные положения, выносимые на защиту

1. Алгоритмическая модель процесса уменьшения размера таблиц маршрутизации, основанная на использовании разработанных алгоритмов минимизации булевых функций и метода ветвей и границ.

2. Метод уменьшения таблиц маршрутизации, основанный на использовании эвристического алгоритма выборочной генерации простых импликант булевых функций, который обладает большей скоростью вычислений, по сравнению с известными подходами, и позволяет обрабатывать таблицы большой размерности в режиме реального времени.

3. Программный комплекс, реализующий разработанные алгоритмы, компьютерное моделирование и экспериментальная оценка эффективности методов уменьшения таблиц маршрутизации.

Практическая и теоретическая значимость исследований. Результаты диссертационной работы могут найти применение при разработке программных систем, предназначенных для повышения экономичности маршрутизаторов. Разработанные алгоритмы также могут быть использованы в системах автоматизации проектирования интегральных схем.

Достоверность результатов обеспечивается строгостью постановок задач, корректностью выбранного математического аппарата и подтверждается результатами компьютерного моделирования.

Личный вклад автора. Постановка задач исследования осуществлена совместно с научным руководителем А.А.Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.

Апробация работы проведена на шестой всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2009) и ежегодных научно-технических семинарах кафедры

Телекоммуникационные технологии и сети» УлГУ.

Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 - в изданиях из перечня ВАК.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения. Основной текст диссертации изложен на 100 страницах.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Шиготаров, Андрей Владимирович

Выводы

1. Построена логическая модель программного пакета, основанная на использовании диаграмм языка UML — диаграммы прецедентов, диаграммы классов, диаграммы последовательности действий.

2. Проанализированы и обоснованно выбраны программные средства разработки для реализации разработанных алгоритмов. Проведено тестирование разработанных программных средств с помощью утилит, определяющих степень покрытия кода.

3. Показано, что в среднем коэффициент уменьшения размера таблиц маршрутизации составляет 1.9. Сокращение таблиц маршрутизации позволяет снизить энергопотребление модулей памяти на 38-45%, а также увеличить скорость поиска в среднем на 5.7%.

4. Показано, что сокращение таблиц маршрутизации в маршрутизаторах, использующих кэширование, позволяет увеличить долю успешных обращений к кэшу в среднем на 5%.

5. Получена экспериментальная оценка эффективности точного метода минимизации ДНФ на наборе MCNS Benchmarks, который состоит из задач, используемых для сравнения алгоритмов оптимизации цифровых устройств. Показано, что разработанные методы позволяют получить решение за меньшее время, в сравнении с известными подходами.

Заключение

В диссертационной работе разработан и исследован метод сокращения таблиц маршрутизации, основанный на использовании алгоритмов минимизации булевых функций в классе дизъюнктивных нормальных форм.

Поставленные задачи были решены, к основным результатам диссертационного исследования следует отнести:

1. Разработка эффективных схем хранения и поиска записей в таблицах маршрутизации является важнейшим этапом построения быстродействующих сетей. Уменьшение размера таблиц маршрутизации позволяет увеличить скорость обработки входящих пакетов и уменьшить энергопотребление модулей памяти.

2. По результатам сравнительного анализа работ, связанных с уменьшением размера таблиц маршрутизации, были выявлены основные недостатки известных подходов, а также предложено использовать математическую модель таблиц маршрутизации, основанную на применении аппарата булевых функций.

3. Разработан быстродействующий и эффективный алгоритм сокращения размера таблиц маршрутизации, который в отличие от известных подходов позволяет обрабатывать таблицы маршрутизации большой размерности в режиме реального времени.

4. Проведено компьютерное моделирование программных реализаций предложенного алгоритма уменьшения таблиц маршрутизации, которое подтвердило правильность и корректность исходных посылок и возможность их использования в реальных ГР-сетях.

5. Результаты компьютерного моделирования показали, что применение на практике разработанного подхода позволяет уменьшить размер реальных таблиц маршрутизации более чем в 1.9 раз, что приводит к снижению энергопотребления модулей памяти на 38-45%, а также к увеличению скорости поиска в среднем на 5.7%. Показано, что сокращение таблиц маршрутизации в маршрутизаторах, использующих кэширование, позволяет увеличить долю успешных обращений к кэшу в среднем на 5%.

Полученные результаты могут быть использованы как в теоретических исследованиях - для дальнейшего исследования алгоритмов минимизации ДНФ и методов сокращения таблиц маршрутизации, так и на практике - организациями, предоставляющими доступ к сети Интернет с целью увеличения эффективности работы маршрутизаторов. Еще одной возможной областью приложения разработанных методов является их использование для увеличения производительности систем автоматизации проектирования интегральных схем, которые применяют минимизацию булевых функций на этапе логического проектирования.

Список литературы диссертационного исследования кандидат технических наук Шиготаров, Андрей Владимирович, 2010 год

1. Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь, 1987 - 136 с.

2. Буч Г., Рамбо Д., Джекобсон И. UML. Руководство пользователя. -М.:ДМК, 2001-432 с.

3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981-366 с.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982 - 416 с.

5. Журавлев Ю.И. О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логик в одном классе алгоритмов // Докл. АН СССР, 1960, 132, № 3, с. 504—506 (РЖМат, 1961, 4А84).

6. Закревский А.Д. Логический синтез каскадных схем. Москва: Наука. 1981. 416 с.

7. Куроуз Дж., Росс К. Компьютерные сети. СПб.:Питер, 2004 - 765 с.

8. Нигматуллин Р.Г. Сложность булевых функций. М.:Наука, 1991. - 208 с.

9. Олифер В.Г., Олифер Н. А. Компьютерные сети: принципы, технологии, протоколы. СПб.:Питер, 2001 - 672 с.

10. Самофалов К.Г, Романкевич A.M. Прикладная теория цифровых автоматов. Киев "Вища школа", 1987 - 375 с.

11. П.Сапоженко А.А, Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм. // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет., М., 1987 — 68—116 с.

12. Смагин А.А., Шиготаров А.В. Метод оптимизации таблиц маршрутизации // Инфокоммуникационные технологии, Самара, 2009. -т. 7, № 3. с. 5962.

13. Страуструп Б. Дизайн и эволюция языка С++. -М.: ДМК, 2000 448 с.

14. Страуструп Б. Язык программирования С++. —СПб.:Невский диалект, 2001 -1099 с.

15. Схрейвер А. Теория линейного и целочисленного программирования : в 2-х т. — М.: Мир, 1991

16. Таненбаум Э. Компьютерные сети. СПб.:Питер, 2007 - 992 с.

17. Шиготаров А.В. Неявные алгоритмы минимизации булевых функций в классе дизъюнктивных нормальных форм // Техника и Технология-Москва. Изд-во Спутник-Плюс, 2009. № 5. - с. 34-36.

18. Шиготаров А.В. Об одном алгоритме минимизации дизъюнктивных нормальных форм // Автоматизация процессов управления — Ульяновск. ФНПЦ ОАО «НПО МАРС», 2008 №4(14) с. 12-16.

19. Яблонский С.В. Введение в дискретную математику. М.:"Высшая школа", 2003 - 384 с.

20. Ahmad S, Mahapatra R. An Efficient Approach to On-Chip Logic Minimization // IEEE Transactions on very large scale integration (VLSI) Systems, 2007, vol. 15, № 9, pp. 1040-1050.

21. Agrawal В., Sherwood T. Ternary CAM Power and Delay Model: Extensions and Uses // IEEE Transactions on very large scale integration (VLSI) Systems, 2008, vol. 16, № 5, pp. 554-564.

22. BGP Routing Table Analysis Reports, http://bgp.potaroo.net/ 25.03.2010

23. Brayton R. K. et al. Logic Minimization Algorithms for VLSI Synthesis. -Kluwer Academic Publishers, 1984 193 p.

24. The Click modular router, http://read.cs.ucla.edu/click/ 25.03.2010

25. Bryant R. A graph-based algorithms for Boolean functions manipulation // IEEE Trans.on Computers, №8 ,1986 -pp.677-691

26. Bryant R., Meinel C. Ordered Binary Decision Diagrams In Electronic Design Automation: Foundations, Applications and Innovations, www.mathematik.uni-trier.de/tf702 20.ps 25.03.2010

27. Chandra A.K., Markowsky G. On the number of prime implicants Discrete Mathematics 24(1978), pp 7-11

28. Chao H. Next generation routers // Proceedings of the IEEE, 2002, 90 (9), pp. 1518-1558.

29. Coudert O. Doing Two-Level Logic Minimization 100 Times Faster // Proc. of Symposium on Discrete Algorithms (SODA), San Francisco CA, 1995, pp. 112 -121.

30. Coudert O., Madre J. C. Implicit and incremental computation of primes and essential primes of Boolean functions // Proc.of the Design Automation Conf. (Anaheim, CA, 1992), pp 36-39.

31. Coudert O., Madre J. C. New ideas for solving covering problems // In Proc. ofthe Design Automation Conference, 1995, pp 641-645.

32. Coudert O. On Solving Covering Problems //Proc. of 33rd DAC, Las Vegas, 1996-pp. 197-202

33. Coudert O, Madre J. C., Fraisse H. A New Viewpoint on Two-Level Logic Minimization // Proc. of 30th DAC, Dallas TX, USA, 1993 pp. 625-630

34. Coudert O., Sasao T. Two-Level Logic Minimization // Logic Synthesis and Verification, S. Hassoun & T. Sasao Editors, Kluwer Academic Publishers, Chapter 1,2001 pp. 167-196

35. Czort S. The complexity of minimizing disjunctive normal form formulas. Master thesis, 1999 53 p.

36. С++ Википедия. http://ru.wikIPedia.org/wiki/C%2B%2B 25.03.2010

37. Feldmeier D. Improving gateway performance with a routing-table cache // in:Proceedings of INFOCOM, 1988, pp. 298-307.

38. Fiser P., Hlavicka J. BOOM A Heuristic Boolean Minimizer // Proc. ICCAD-2001, San Jose(USA) - pp 439-442.

39. GLPK (GNU Linear Programming Kit), http://www.gnu.org/software/glpk/ 25.03.2010

40. Goldberg E.I., Carloni L.P., Villa Т., Brayton R.K., Sangiovanni-Vincentelli A.L. Negative thinking in branch-and-bound: the case of unate covering IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000-pp. 1-16.

41. Guo R., Delgado-Frias J. G. IP Routing table compaction and sampling schemes to enhance TCAM cache performance // Journal of Systems Architecture, vol. 55,2009, pp. 61-69

42. Gupta P., Lin S., McKeown N. Routing lookups in hardware at memory access speeds // in Proceedings of InfoCom'98, San Francisco, 1998, pp. 1240-1247.

43. Hayashi Т., Miyazaki T. High-Speed Table Lookup Engine for IPv6 Longest Prefix Match // Proc. IEEE Globecom, vol. 2, IEEE Press, Piscataway, N. J.,1999.- pp. 1576-1581.

44. Kohler E. The Click modular router. PhD thesis, 2001, 127p. http://pdos.csail. mit.edu/papers/click:kohler-phd/thesis.pdf25.03.201051.1psolve project, lpsolve.sourceforge.net 25.03.2010

45. Li X.Y., Brglez F., Stallmann M.F. Effective Bounding Techniques For Solving Unate and Binate Covering Problems // Proceedings of the 42nd annual Design Automation Conference, 2005 pp 385-290.

46. Liao S., Devadas S. Solving covering problems using lpr-based lower bounds // Proc. of the 34th Design Automation Conference, 1997 pp. 117-120.

47. Liu H. Reducing Cache Miss Ratio For Routing Prefix Cache // In proc. GLOBECOM, 2002, vol. 3, pp. 2323- 2327

48. Liu H. Routing Prefix Caching in Network Processor Design // in Tenth International Conference on Computer Communications and Networks, 2001, pp. 18-23.

49. Liu H. Routing Table Compaction in Ternary-CAM // IEEE Micro, Jan/Feb 2002, pp. 58-64.

50. Lysecky R., Vahid F. On-chip logic minimization//Proc. ACM IEEE Design Automation Conference, 2003 — pp. 334-337.

51. McAuley A., Francis P. Fast Routing Table Lookup Using CAMs // Proc. IEEE Infocom, vol. 3, IEEE CS Press, Los Alamitos, Calif., 1993, pp. 13821391.

52. Meinel C., Theobald T. Algorithms and data structures in VLSI design, Springer-Verlag NY, 1998. 267 p.

53. Minato S. Calculation of Unate Cube Set Algebra Using Zero-Suppressed

54. BDDs. // Proc. of DAC , 1994, pp. 420-424.

55. Minato S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems // Proc. of 30th ACM/IEEE Design Automation Conference (DAC'93), 1993 pp. 272-277

56. Mishchenko A. EXTRA Library of the DD procedures. http://www.ee.pdx.edu/~alanmi/research/extra.htm 25.03.2010

57. Mishchenko A. An introduction to zero-suppressed binary decision diagrams // Technical report, Portland State University, June 2001 http://www.eecs.berkelev.edu/~alanmi/publications/2001/techO 1 zdd.pdf 25.03.2010

58. Mishchenko A., Perkowski M. Fast heuristic minimization of exclusive-sums-of-products // Proc. Reed-Muller Workshop, 2001, pp. 242-250.

59. Mishchenko A., Sasao T. Large-scale SOP minimization using decomposition and functional properties // Proc. DAC , 2003, pp. 149-154

60. McCluskey E. J. Minimization of Boolean functions // The Bell System Technical Journal, 1956, 35, №5, pp. 1417-1444.

61. McGeer P. et al. ESPRESSO-SIGNATURE: a new exact minimizer for logic functions // Proc. DAC, 1993 pp. 618-624

62. Nilsson S., Karlsson G. IP-Address Lookup Using LC-tries // IEEE J. Selected Areas Comm., vol. 17, no. 6, June 1999. pp. 1083-1092.

63. Null L., Lobur L. The Essentials of Computer Organization and Architecture, Second Edition, Jones and Barlett, 2006, 799 p.

64. PostgreSql Википедия. http://ru.wikIPedia.org/wiki/PostgreSOL 25.03.2010

65. Quine W. V., The problem of simplifying truth functions // Am. Math. Month. 1952, 59, pp. 521-531.

66. Quine W. V. On cores and prime implicants of truth functions. Amer. Math Monthly, 66, №9,1959. - pp. 755-760.

67. Qt- Википедия. http://ru.wikIPedia.org/wiki/Qt 25.03.2010

68. Ravikumar V. С., Bhuyan L. N., Mahapatra R. N., EaseCAM: An Energy and Storage Efficient TCAM-Based Router Architecture for IP Lookup // IEEE Transactions on Computers, vol. 54, 2005, 521-533.

69. RONDO: Two Level Sum-of-Product Minimization, http://web.cecs. pdx.edu/~alanmi/researcIx/min/rondo.exe 25.03.2010

70. Rooney, J.J. Delgado-Frias, J.G. Summerville, D.H. Associative ternary cache for IP routing // IEE Proc., Comput. Digit. Tech., 2004 vol. 151, Issue 6, pp. 409—416.

71. RouteViews Project, http://www.routeviews.org/ 25.03.2010

72. Rudell R. Multiple-valued minimization for PLA synthesis. UCB technical report M86/65, 1986.

73. Sapra S., Theobald M., Clarke E. SAT-Based Algorithms for Logic Minimization // IEEE International Conference on Computer Design, 2003, p. 510.

74. Sasao Т., Matsuura M., Iguchi Y., Nagayama S. Compact BDD Representations for MultlPle-Output Functions // VLSI-SOC, Montpellier, France, 2001, pp. 406-411.

75. Somenzi F. CUDD Package, Release 2.3.1. http://vlsi.Colorado.EDU/ -fabio/CUDD/cuddlntro.html 25.03.2010

76. Srinivasan V. and Varghese G. Fast Address Lookups Using Controlled Prefix Expansion // ACM Trans. Computer Systems, vol. 17, no. 1, Oct. 1999. pp. 1-40.

77. Stergiou S., Jain J. Optimizing Routing Tables on Systems-on-ChIP with Content-Addressable Memories //Proc. IEEE International System-on-Chip Symposium, 2008, pp 1-6.

78. Talbot В., Sherwood Т., and Lin B. Ip caching for terabit speed routers // In proc. Globecom, 1999, vol. 2, pp. 1565-1569

79. Umans C., Villa Т., Sangiovanni-Vincentelli A. Complexity of two-level logicminimization // IEEE Transactions on Computer-Aided design, 2006, pp 12301246.

80. Waldvogel M. Fast Longest Prefix Matching: Algorithms, Analysis, and Applications. PhD thesis number 13266, ETH Zurich, 2000 - 154 p.

81. Wu W. Packet Forwarding Technologies. Auerbach Publications, 2007, 4461. P

82. Zane F., Narlikar G., Basu A. CoolCAMs: Power-Efficient TCAMs for Forwarding Engines // IEEE Infocom, 2003, vol. 1, pp. 42-52.

83. Zheng К., Ни C., Liu H., Liu B. An ultra high throughput and power efficient TCAM-based IP lookup engine // INFOCOM, 2004, vol. 3., pp. 19841994.