[ntar-workers] On Markers and Bookmarks
Gianluca Varenni
gianluca.varenni at gmail.com
Tue Jul 5 02:21:39 GMT 2005
----- Original Message -----
From: "Christian Kreibich" <christian at whoop.org>
To: "NTAR workers" <ntar-workers at winpcap.org>
Sent: Friday, July 01, 2005 7:21 PM
Subject: Re: [ntar-workers] On Markers and Bookmarks
> Ciao Gianluca,
>
> On Thu, 2005-06-30 at 22:48 -0700, Gianluca Varenni wrote:
>>
>> In general, I like the idea of having some indexing records to the file.
>> And
>> maybe they could be put at the very end of a section, in order to avoid
>> recomputing the offsets).
>
> cool! That was exactly my plan with the Section End Block.
>
>> My question is: what is the best/most useful
>> indexing scheme we should use? I think it heavily depends on the
>> application
>> processing the trace file. Maybe the best approach is to put some very
>> simple markers (as several folks here on the mailing list proposed) at
>> *reasonable* places (optional, of course), leaving the application to
>> build
>> its own tree/db/whatever data structure to fast access the data.
>
> So what's the verdict on the PacketsBlock/GoPBlock idea?
My verdict would be to use markers and sections, and not make use of
GoPBlocks. Actually, I'm still thinking of what is the best approach. In
general GoPBlocks introduce a real hierarchy of blocks in the file format,
and a hierarchical file format was discarded last year when the pcap-ng was
first discussed.
> Given that, I
> think it wouldn't be that hard to do the following:
>
> - Fix a baseline granularity for indexing, say a GoPBlock size on the
> order of a few megabytes. We build and index on the timestamps of the
> first packet in GoPBlocks, yielding the start offsets of those
> GoPBlocks.
> - The contents of an index block would encode a search tree structure.
> For small sections, this'll be equivalent to a list, and as the traces
> grow bigger, represent more and more complex trees -- think B-tree. Each
> node contains a number of slots (encoding of their number, or whether it
> can be fixed etc, to be discussed etc), each of which is labelled by a
> timestamp and either pointing to another node or containing a file
> offset.
>
> Internal node:
>
> 0 1 2 3
> 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Tree node ID |0|
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Node pointer |x|
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Timestamp (High) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Timestamp (Low) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> ...
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Node pointer |x|
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Timestamp (High) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Timestamp (Low) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Node pointer |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>
>
> Leaf node:
>
> 0 1 2 3
> 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | Tree node ID |1|
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | File Offset (High) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> | File Offset (Low) |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>
> (MSB of first word = node type, internal (0) or leaf (1). x = unused)
>
> To navigate, you read the index block into memory, building up the tree
> structure, and then walk the tree to find the GoPBlock closest to what
> you need by comparing the timestamp you're looking for to the ones
> stored inside the node slots. Inside that resulting GoPBlock, you search
> sequentially.
>
> The other way round, you could build up the tree structure in memory as
> you pump out the packets and GoPBlocks, and when you stop the capture,
> you serialize it out as an index block inside the SEB.
>
> A 1TB file would have roughly 200K 5MB GoPBlocks. Even with generous
> node sizes the entire tree structure should fit within a few megabytes.
> (Thinking *very* back-of-envelope -- don't yell at me :)
>
> I'm pretty shafted at the moment but if you like the idea I could likely
> offer around a day or so per week in July to hack this up.
I think that the idea of the indexing block is worth more discussion, maybe
before trying to implement it; moreover, I'm still working quite heavily on
the library to clean it and offer some missing features that are needed for
these new block types (in particular, something to allow random access to
the blocks of a file).
Some random issues/ideas/thoughts that came to my mind in the last days:
- do we really need markers? can the indexing block can point to packet
blocks?
- we should remember that two ntar files can be concatenated using "cat". As
a consequence, the file offsets should be relative.
- can the indexing block index block in multiple sections? There can be byte
order and interface id issues.
- Is the timestamp information to seek in the file enough for the majority
of apps?
- how is the timestamp represented? pcap-ng does not have a fixed
representation for the timestamp precision: the interface description block
contains a specific option that tells the precision of the timestamps for
the packets captured on that interface. By default it's microseconds.
Have a nice day
GV
>
> Cheers,
> Christian.
> --
> ________________________________________________________________________
> http://www.cl.cam.ac.uk/~cpk25
> http://www.whoop.org
>
>
> _______________________________________________
> ntar-workers mailing list
> ntar-workers at winpcap.org
> https://www.winpcap.org/mailman/listinfo/ntar-workers
More information about the ntar-workers
mailing list