[Scamper-dev] scamper notes draft 1

[Bradley Huffaker]

-------------------------- Ken's first response -----------------------

On Tue, May 18, 2004 at 07:12:34PM -0700, Bradley Huffaker wrote:
> We have decided to split the role of list managment and list probing
> into to two processes.  Scamper will be the probing process and there
> will also be a ListManager process to handle the list creation and
> interleaving of different lists.
> 
> On a local port, or some other communication channel, Scamper will request
> the next batch of IPs from the List Manager.  The List manager may send it
> an IP Object, Begin List Object, or End List Object.  

Two processes is the most likely way to do it, but other possibilities
include two threads, or just two sets of functions/classes.  In any
case, the communication between them is limited to a one-way (List
Manager to Prober) stream of commands as brad described.  In the
two-process implementation, the best communication channel is
probably a named pipe.

> To help me explain the behavor we would like scampe to have I will assume,
> for now, that it has the following lists:
>     Active Window - the list of IP Object which are currently being probed
>     Input Queue - the list of Objects which were passed by the List Manager
> 	but have yet to be processed or moved to the active list
>     Pending Queue - each ListId gets a pending queue which holds
> 	Object from a different cycle then the current cycle.
>     Blocked Queue - holds a list of IP Objects which are blocked
> 	because their IP address is currently in the queue.  These
> 	Lists are stored with the active IP Object which is blocking 
> 	them.

We never really discussed the handling of timeouts.  I propose:  An
IP stays in the Active Window until it recieves all expected
responses, OR it times out.  (Perhaps we should wait for some
(shorter) timeout after all expected responses, in case there are
unexpected responses?)  When it is removed, its Trace record is
written out, and it is forgotten completely; any response that
arrives after that is ignored.  Timing out can easily be handled
by a queue, ordered by time; periodically remove timed-out items
from the head of this queue.

> Scampe should garrentee that the following two statements are true:
>     * IP addresses from different Cycles, but the same List are not 
>       probed, in the active list, simultaneously.

This is what we agreed on at the meeting, but on further thought,
I think this is not necessary.

Consider also a related requirement that was not mentioned in the
meeting or in brad's email, but I think may have been implied:
at the end of a cycle, we must wait for some timeout to elapse
to allow responses to come back, before we can start the next cycle.
Both of these requirements together could be described as the "No
Overlapping Cycles" requirements, and both require essentially the
same queueing of commands for the next cycle.

Eliminating these requirements will eliminate all of the complexity
of Pending and Blocked Queues.  Then (assuming there are no duplicates
in the list, and the list is sorted the same way in every cycle),
the only way the same address will occur twice in the active window
is if the time it takes to probe the entire cycle is shorter than
the timeout for a single non-responding address.  (If this is true,
it probably means we're probing EVERY address in the list too
frequently.)  I think it would be acceptable to handle this case
by simply throwing away a new instance of an address if the same
address from the same list but different cycle is already active
or awaiting a response.

This does mean the Prober needs to keep track of more than one
active Cycle (with all its options) for a given List.  This is the
only additional complexity, but it's outweighed by eliminating all
the address queueing complexity.

There is no problem in the Prober output, since we have an End
Of Cycle record.  For example, the Prober output may contain a
sequence like:

    ... T1W T1X T1Y SOC2 T2A T1Z EOC1 T2B ...

(where my shorthand "T1W" means "Trace of addr W in cycle 1"; SOC2
means "Start of Cycle 2"; EOC1 means "End of Cycle 1".)

The post-processing sorter that splits cycles into separate files
will open a file for writing when it sees an SOC, and close it when
it sees a corresponding EOC.  Between SOC2 and EOC1 it has two files
open, but this is no harder than having multiple files open to handle
multiple lists.

-- 
Ken Keys
kkeys at caida.org