In this paper we consider the method of routing table optimization based on the boolean function minimization algorithm. The experimental results obtained on the routing table information from large Internet exchange points show high performance of the method for high dimension tasks. Keywords: routing table optimization, boolean function minimization, binary decision diagram, set cover problem.

About the authors

A A Smagin

A V Shigotarov


  1. 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. - P. 36-39.
  2. Coudert O., Madre J.C. New ideas for solving covering problems // Proc. of the Design Automation Conference, 1995. - P. 641-645.
  3. Hayashi T., Miyazaki T. High-Speed Table Lookup Engine for IPv6 Longest Prefix Match // Proc. IEEE Globecom, vol. 2, IEEE Press, Piscataway, N. J., 1999. - P. 1576-1581.
  4. Liu H. Routing Table Compaction in Ternary-CAM // IEEE Micro. Jan/Feb, 2002. - P. 58-64.
  5. Meinel C., Theobald T. Algorithms and data structures in VLSI design. Springer-Verlag NY, 1998. - 267 p.
  6. McAuley A., Francis P. Fast Routing Table Lookup Using CAMs // Proc. IEEE Infocom. Vol. 3. IEEE CS Press, Los Alamitos, Calif., 1993. - P. 1382-1391.
  7. Rudell R. Multiple-valued minimization for PLA synthesis. UCB technical report M86/65, 1986.
  9. edu/~fabio/



Abstract - 17

PDF (Russian) - 1


Article Metrics

Metrics Loading ...

Copyright (c) 2009 Smagin A.A., Shigotarov A.V.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies