Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/654' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/654' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms | IIT - CNR - Istituto di Informatica e Telematica
IIT Home Page CNR Home Page

Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms

We consider the problem of fast IP address lookup in the forwarding engines of Internet routers. We analyze over 2400 public snapshots of routing tables collected over five years, discovering what we call the middle-class effect. We exploit this effect for tailoring a simple solution to the IP lookup scheme, taking advantage of the skewed distribution of Internet addresses in routing tables. Our algorithmic solution is easy to implement as it is tantamount to performing an indirect memory access. Its performance can be bounded tightly and has very low memory dependence (e.g. just one memory access to off-chip memory in the hardware implementation). It can quickly handle route announcements and withdrawals on the fly, with a small cost which scales well with the number of routes. Concurrent access is permitted during these updates.

 


International Workshop on Efficient and Experimental Algorithms, Santorini iceland, Greece, 2005

Autori: Filippo Geraci, Roberto Grossi
Autori IIT:

Tipo: Articolo in Atti di convegno internazionale con referee
Area di disciplina: Information Technology and Communication Systems

Attività: Algoritmica per tecnologie web