Re: [dtn-security] Re: SDNV-new : OK

Stephen Farrell <stephen.farrell@cs.tcd.ie> Tue, 07 June 2005 14:03 UTC

Received: from smtp3.tcd.ie (smtp3.tcd.ie [134.226.1.158]) by webbie.berkeley.intel-research.net (8.11.6/8.11.6) with ESMTP id j57E3fV01986 for <dtn-security@mailman.dtnrg.org>; Tue, 7 Jun 2005 07:03:41 -0700
Received: from Vams.smtp3 (smtp3.tcd.ie [134.226.1.158]) by smtp3.tcd.ie (Postfix) with SMTP id 0C0CA14C18D for <dtn-security@mailman.dtnrg.org>; Tue, 7 Jun 2005 15:03:35 +0100 (IST)
Received: from smtp3.tcd.ie ([134.226.1.158]) by smtp3.tcd.ie ([134.226.1.158]) with SMTP (gateway) id A04466EC1C9; Tue, 07 Jun 2005 15:03:34 +0100
Received: from [134.226.36.26] (sfarrel2.dsg.cs.tcd.ie [134.226.36.26]) by smtp3.tcd.ie (Postfix) with ESMTP id BC95C14C18D for <dtn-security@mailman.dtnrg.org>; Tue, 7 Jun 2005 15:03:34 +0100 (IST)
Message-ID: <42A5AA42.8050006@cs.tcd.ie>
Date: Tue, 07 Jun 2005 15:08:02 +0100
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.8) Gecko/20050511
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: dtn-security@mailman.dtnrg.org
Subject: Re: [dtn-security] Re: SDNV-new : OK
References: <200505241854.j4OIsx724035@smtp-bedford-dr.mitre.org> <42944BEF.7090007@cs.tcd.ie> <20050525152006.GA7633@pisco.cs.berkeley.edu> <42949E83.9050000@cs.tcd.ie> <20050525163707.GB14911@pisco.cs.berkeley.edu> <4294ABB9.5010009@jpl.nasa.gov> <4295D547.9080808@cs.tcd.ie> <20050531172941.GA30682@pisco.cs.berkeley.edu> <20050601160110.GF9319@masaka.cs.ohiou.edu> <20050604202950.GC14707@masaka.cs.ohiou.edu>
In-Reply-To: <20050604202950.GC14707@masaka.cs.ohiou.edu>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-AntiVirus-Status: Checked by TCD Vexira. (version=1.55.010 VDF=8.752)
X-AntiVirus-Status: NONE
X-AntiVirus-Status: Action Taken:
X-AntiVirus-Status: Host: smtp3.tcd.ie
X-AntiVirus-Status: MessageID = A14466EC1C9
Sender: dtn-security-admin@mailman.dtnrg.org
Errors-To: dtn-security-admin@mailman.dtnrg.org
X-BeenThere: dtn-security@mailman.dtnrg.org
X-Mailman-Version: 2.0.13
Precedence: bulk
Reply-To: dtn-security@mailman.dtnrg.org
List-Unsubscribe: <http://mailman.dtnrg.org/mailman/listinfo/dtn-security>, <mailto:dtn-security-request@mailman.dtnrg.org?subject=unsubscribe>
List-Id: DTN Security Discussion <dtn-security.mailman.dtnrg.org>
List-Post: <mailto:dtn-security@mailman.dtnrg.org>
List-Help: <mailto:dtn-security-request@mailman.dtnrg.org?subject=help>
List-Subscribe: <http://mailman.dtnrg.org/mailman/listinfo/dtn-security>, <mailto:dtn-security-request@mailman.dtnrg.org?subject=subscribe>
List-Archive: <http://mailman.dtnrg.org/pipermail/dtn-security/>

Just checking another thing on this.

For LTP and bundle security and generally anywhere
we'll have some kind of optional field/extension
mechanism this means we're now moving to a straight
TLV (tag/length/value) scheme with the length being
an SDNV.

While that's ok by me, it is a change and is slightly
less efficient in some cases.

For example, in LTP we previously had extensions
structured like:

    +--------+---------------///-+
    |ext-tag | SDNV-8 spec       |
    +--------+-------------------////-+
    |ext-tag | SDNV-8 spec            |
    +--------+-------------------////-+

Whereas now we'll have to have it as:

    +--------+---------------///--------------+
    |ext-tag | length (SDNV) | value (octets) |
    +--------+-------------------////-----------+
    |ext-tag | length (SDNV) | value (octets)   |
    +--------+-------------------////-----------+

The same will of course be true of other fields.

The inefficiency occurs when the tag is such that
the value's length is fixed and the value would
fit within an SDNV. In that case we're probably
using up just one additional byte. (We can't
omit the length since that's the only way that
code not supporting this tag can skip to the
next one.)

However, I'm fine with this approach - TLV being
the traditional route after all,
Stephen.

PS: If someone's got time/energy, it might be worthwhile
comparing this to the ASN.1 packed encoding rules (PER) for
integer values. I guess we're ending up fairly similar.


Manikantan Ramadas wrote:

> Hi folks,
> 
>   After an offline discussion with Scott, I have come around to joining the
> consensus for dropping the SDNV-8/SDNV-16s in favour of the proposed SDNV
> scheme (the 1/2/3/4/5/6/7/8) which allows an SDNV of total size atmost 9
> bytes with value range 0-2^68-1. We don't have a real feel for how
> frequently the range 4096-32767 is likely to be used in LTP, and our current
> speculations don't predict a large hit-ratio for the range. Therefore, 
> it seems better to be homogeneous with the rest of the bundle protocol suite
> and adopt the proposed SDNV scheme.
> 
> - Mani.
> 
> On Wed, Jun 01, 2005 at 12:01:10PM -0400, Manikantan Ramadas wrote:
> 
>>Folks,
>>
>>  My apologies for falling way beyond on this thread, but I have caught up
>>finally.
>>
>>To summarize this "one true SDNV" scheme,   
>>we have eaten up 4 bits into the SDNV discriminant at the cost of the
>>maximum size of SDNV; it was 2^1024-1, which now becomes 2^68-1.
>>
>>I tend to agree with the general consensus in this thread that we should
>>probably quit worrying about fitting cryptographic keys in an SDNV, as they
>>are ever bit hungry, and it is only a matter of time before they overflow
>>any SDNV scheme we offer. It seems like a good idea for crypto. fields in
>>the DTN security specs, LTP extension specs, and other places to be encoded
>>to have their length field be an SDNV, and have the data of the indicated
>>length follow. Good.
>>
>>I think Rajesh mentioned that the real value of the SDNV scheme shows up
>>only for relatively smaller values. I tend
>>to agree with that, and hence would like to point out a key point that was
>>missing in our discussion here. SDNV-16's were designed to let you store
>>values from 128-32767 in just two octets (as opposed to SDNV-8 - the original
>>SDNV - which takes 2 octets for 128-255, 3 octets for 256-65535). SDNV16s,
>>as you can see, were designed to be optimal for data typically falling in
>>this range 128-32767. Note that they do need two bytes even to store data in
>>the range 0-127, and less optimal for this range compared to SDNV8s.
>>
>>With our current proposal, we can store only values from 128-4095 in two
>>octets, and requires three octets for 4096-2^20-1. While this is clearly
>>more optimal than SDNV8's, it is not so when compared to SDNV16s.
>>Laying them out :
>>
>>	Octets Required			SDNV16			proposed SDNV
>>    ---------------         ------			-------------
>>    	1					  --			0-127					
>>    	2					0-32767			128-4095
>>		3					32768-65535		4096-2^20-1
>>        4					2^16-2^24-1		2^20-2^28-1
>>        5					2^24-2^32-1		2^28-2^36-1
>>		..........
>>
>>Note that the way SDNV16 is defined, it always needs atleast 2 octets to
>>encode. 
>>
>>So, when we go to the octets required field being greater than 4, the
>>benefits of eating into the discriminant begin to show. It is the 2 octet
>>case that makes me a little nervous about the new scheme. It costs an octet
>>more for values in the range 4096-32767. We have quite a few fields like 
>>blockoffsets and chunk length, in LTP reception reports that might fall in
>>this range, and we lose the benefits of SDNV16 with this scheme. If those
>>fields take values greater than 32768, the new scheme beats it, sure. 
>>
>>Hence I can't yet make up my mind on giving away SDNV16's altogether. That
>>said, I am in principle, in favor of having a one true SDNV scheme that
>>would make life simpler. But can't make up my mind just yet on how
>>frequently the range 4096-32767 is likely to be used in LTP.
>>
>>Thoughts?
>>
>>- Mani.
>>
>>On Tue, May 31, 2005 at 10:29:41AM -0700, Michael Demmer wrote: 
>>
>>>I took a pass at changing the language from the original LTP spec to
>>>match my new proposal for SDNV encodings:
>>>
>>>---
>>>
>>>Self-Delimiting Numeric Value (SDNV)
>>>
>>>   The design of LTP attempts to reconcile minimal consumption of
>>>   transmission bandwidth with
>>>
>>>      (a) extensibility to satisfy requirements not yet identified and
>>>      (b) scalability across a very wide range of network sizes and
>>>          transmission payload sizes.
>>>
>>>   A key strategic element in the design is the use of self-delimiting
>>>   numeric values (SDNVs) that are similar in design to the Abstract
>>>   Syntax Notation One [ASN1] encoding of data structures. An SDNV can
>>>   be used to encode a numeric value in the range 0 .. (2^68 - 1),
>>>   using 1 to 9 octets.
>>>
>>>   The first octet of an SDNV -- the "discriminant" -- characterizes
>>>   the SDNV. If the most significant bit of the discriminant is zero,
>>>   the length of the SDNV is 1 octet and the remaining 7 bits of the
>>>   discriminant, treated as an unsigned integer, is the value of the
>>>   SDNV. An integer in the range of 0 to 127 can be encoded this way.
>>>
>>>   Otherwise (if the most significant bit of the discriminant is 1),
>>>   the next 3 bits of the discriminant encode the length of the SDNV.
>>>   If the content of these 3 length bits, treated as an unsigned
>>>   integer, has the value N, then N+1 additional octets are used to
>>>   represent the value. The value is found by concatenating the
>>>   remaining 4 bits of the discriminant with octets 2 through N+2 of
>>>   the SDNV, and treating this result as an unsigned integer.
>>>
>>>   The following table outlines the SDNV encoding for all value
>>>   ranges, their associated discriminant encodings, and the total
>>>   length in octets of the SDNV.
>>>
>>>   Value Range         Discriminant     SDNV Length 
>>>   ----------------    ------------     -----------
>>>   0        127         0XXX XXXX            1
>>>   128      4095        1000 XXXX            2
>>>   4096     1048575     1001 XXXX            3
>>>   2^20     2^28 - 1    1010 XXXX            4
>>>   2^28     2^36 - 1    1011 XXXX            5
>>>   2^36     2^44 - 1    1100 XXXX            6
>>>   2^44     2^52 - 1    1101 XXXX            7
>>>   2^52     2^60 - 1    1110 XXXX            8
>>>   2^60     2^68 - 1    1111 XXXX            9
>>>
>>>   An SDNV can therefore be used to efficiently represent both large
>>>   and small integer values. However, SDNV is clearly not the best way
>>>   to represent every numeric value. When the maximum possible value
>>>   of a number is known without question, the cost of an additional 8
>>>   bits of discriminant may not be justified. For example, an SDNV is
>>>   a poor way to represent an integer whose value typically falls in
>>>   the range 128 to 255.
>>>
>>>   In general, though, we believe that SDNV representation of selected
>>>   numeric values in LTP segments yields the smallest segment sizes
>>>   without sacrificing scalability.
>>>_______________________________________________
>>>dtn-security mailing list
>>>dtn-security@mailman.dtnrg.org
>>>http://mailman.dtnrg.org/mailman/listinfo/dtn-security
>>
>>-- 
>>"'Beauty is truth, truth beauty,'--that is all
>>  Ye know on earth, and all ye need to know." - John Keats
>>____________________________________________________________________
>>  
>>* Manikantan Ramadas * IRG, OU * http://irg.cs.ohiou.edu/~mramadas *
>>____________________________________________________________________
> 
> 
> 
>