Internet and Intranet Applications and Protocols

Prof. Arthur P. Goldberg

Spring, 2004

QUERY flooding algorithm:

Assume each node has a list of adjacent nodes called ‘neighbors’.

 

Start node:

Send query <query>:

M = new Message()

M.ID = unique_query_ID()

M.query = <query>

M.send_time = now()

M.hops = 0

M.sender = me

Send M to all neighbors

 

All nodes:

Queries_seen: a list of messages;

Database: the data;

integer max_hops // the maximum number of hops a query should travel

integer max_age  // the maximum allowed age for a query

 

Receive a query message Q:

if( Database.has_answer( Q.query ) )

{

   send Database.get_answer( Q.query )to Q.sender;

   return;

}

 

if( not Queries_seen.find( Q.ID ) &&

    Q.send_time - now() < max_age &&

    Q.hops < max_hops )

{

   Q.hops += 1

   send Q to all neighbors, except the one that sent Q

   add (Q.ID, Q.send_time) to Queries_seen

   remove all entries from Queries_seen older than max_age

}

 

Algorithm properties:

Maximum number of copies of each message sent is 2n (n nodes in the network)

Maximum memory used at each node is O( message rate x max_age )