Re: Compressing Large Indices?

[Juergen Schoenwaelder <schoenw@ibr.cs.tu-bs.de>]

>>>>> Tim Jenkins writes:

Tim> I have a question related to the IPsec Monitoring MIBs that John
Tim> Shriver and I are working on.

Tim> We have a table that has a number of indices. It's actually a
Tim> helper table to look up specific rows of another table that has
Tim> an arbitrary integer as index. Unfortunately, two of the indices
Tim> of the first table are variable length octet strings. (They're
Tim> actually the phase 1 IDs used in IKE, so have a type as well as a
Tim> raw octet buffer.)

Tim> This violates the sub-identifier length limits, as well as
Tim> chewing up lots of space on the wire. 

Lets see if I understand the problem. The saByCreatorsEntry is indexed
as follows

    saByCreatorsLocalIdType : IpsecDoiIdentType
    saByCreatorsLocalId	    : IpsecRawId
    saByCreatorsPeerIdType  : IpsecDoiIdentType
    saByCreatorsPeerId	    : IpsecRawId
    saByCreatorsIndex	    : Unsigned32

and the suiteByCreatorsEntry is indexed as 

    suiteByCreatorsP1LocalIdType  : IpsecDoiIdentType
    suiteByCreatorsP1LocalId      : IpsecRawId
    suiteByCreatorsP1RemoteIdType : IpsecDoiIdentType
    suiteByCreatorsP1RemoteId     : IpsecRawId
    suiteByCreatorsIndex          : Unsigned32

where

    IpsecDoiIdentType ::= INTEGER
    IpsecRawId ::= OCTET STRING (SIZE (0..255)).

Obviously, you can't use a raw IpsecRawId in any INDEX clauses since
its size exceeds the SMIv2 max OID length.

Tim> So, it was suggested that we use a hash of the desired indices
Tim> that are variable length to be the real indices and put the
Tim> desired indices (the IDs) in the table. Alternatively, I was
Tim> thinking about using a single hash whose inputs are all of the
Tim> desired indices of this table, since there are a few of them.

Tim> So, the questions are: 1) Is this the best approach?  2) If so,
Tim> what hash should we use? (I guess I'm looking for a precedent,
Tim> rather than inventing something.)

Tim> For the hash selection, we can tolerate a hash function that is
Tim> not particularly collision resistant, since there's already the
Tim> possibility of duplicates based on the raw IDs and we have to
Tim> deal with that, but the potential table size is very large in
Tim> some vendors' implementations, certainly exceeding 10,000
Tim> entries, and perhaps even an order of magnitude larger.

You are saying that a (IpsecDoiIdentType, IpsecRawId) pair is not
necessarily unique, even if you have a size of 0..255? Is there any
architectural reason for the size limitation of 0..255 in the first
place? (I am just curious.)

Back to your question. I have not read the IPsec MIBs and my comments
may be stupid. But in general, it is desirable to use unique and
reasonably short values (or even human readable names) to index MIB
tables. Since your IpsecRawId is way to long and since it may not be
unique (if I read your comments above correctly), why do you not
define secondary names (keys) that are shorter and unique?

This does not have to be done by a hashing algorithm - you can also
provide a mapping table which is for example indexed by the first N
bytes of the raw ID plus the unique name (preferably human readable)
the agent implementation wants to assign. Then you use the unique name
throughout the MIBs to index the tables. The read-only column of the
mapping table would contain the IpsecRawId value. A manager who needs
to map a raw ID into the unique name used throughout the MIBs would
walk the subtree with the raw ID prefix to lookup the MIB internal ID.

As I said, I have no clue about the IPsec MIBs and the suggestion
above may be non-sense in the context of IPsec. But in general, it is
worthwhile to have short unique names (or numbers) as table indexes if
you can't use the natural keys. It may pay off to have mappings from
more complex external data structures to MIB internal names if that
simplifies the indexing structure of MIB tables considerably. It is
possible to speedup lookups by indexing the mapping table(s) with
portions of the complex data structure so that an intelligent manager
only needs to retrieve parts of the mapping table.

/js

-- 
Juergen Schoenwaelder      Technical University Braunschweig
<schoenw@ibr.cs.tu-bs.de>  Dept. Operating Systems & Computer Networks
Phone: +49 531 391 3289    Bueltenweg 74/75, 38106 Braunschweig, Germany
Fax:   +49 531 391 5936    <URL:http://www.ibr.cs.tu-bs.de/~schoenw/>