Browse Prior Art Database

Quality-of-Search concept for communication-related search operations

IP.com Disclosure Number: IPCOM000015528D
Original Publication Date: 2002-Jan-26
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 30K

Publishing Venue

IBM

Abstract

Internet routers and other network equipment such as firewalls perform for each incoming packet several searches using information extracted from the packet header/payload on data structures such as routing tables, firewall rules, access control lists, routing policies, load balancing rules, etc. Although these searches typically involve similar search types (e.g., exact matches, prefix matches, range matches), the performance requirements of those searches can be significantly different. Also, the update requirements (for inserting and deleting information into and from the search data structures) can be different between the various searches, but also for certain parts of the same data structure. For example, certain rules of a firewall application will never be removed (static rules), whereas other rules might be only entered for the duration of a connection (dynamic rules).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 3

Quality-of-Search concept for communication-related search operations

   Internet routers and other network equipment such as firewalls
perform for each incoming packet several searches using information
extracted from the packet header/payload on data structures such as
routing tables, firewall rules, access control lists, routing
policies, load balancing rules, etc. Although these searches
typically involve similar search types (e.g., exact matches, prefix
matches, range matches), the performance requirements of those
searches can be significantly different. Also, the update
requirements (for inserting and deleting information into and from
the search data structures) can be different between the various
searches, but also for certain parts of the same data structure.
For example, certain rules of a firewall application will never be
removed (static rules), whereas other rules might be only entered
for the duration of a connection (dynamic rules).

Several search algorithms used for the above applications have
the ability to make trade-offs between performance parameters.
For example, for applications involving static data structures
that will not be modified so often, it would be more efficient to
spend some more time on update operations in order to minimize
the storage requirements through improved compression. In case of
highly dynamic data structures, improved update performance might
be achieved by compromising on storage requirements by applying a
less efficient compression allowing faster updates. Entries in a
routing table, that are expected to be "hit" more often during
the search process, can be inserted in the data structure such
that the lookup performance is improved, for example by locating
this entry in a separate cache or locating it closer to the root
in case of a tree search. These trade-offs can also be applied on
other parameters such as memory bandwidth and memory
fragmentation (memory management).

Until now, however, there is no means to provide the "search
application" with this sort of information that would a...