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

Manikantan Ramadas <mramadas@masaka.cs.ohiou.edu> Wed, 01 June 2005 16:01 UTC

Received: from masaka.cs.ohiou.edu (masaka.cs.ohiou.edu [132.235.3.154]) by webbie.berkeley.intel-research.net (8.11.6/8.11.6) with ESMTP id j51G1GV07859; Wed, 1 Jun 2005 09:01:16 -0700
Received: from masaka.cs.ohiou.edu (localhost [127.0.0.1]) by masaka.cs.ohiou.edu (8.12.10+Sun/8.12.8) with ESMTP id j51G1A9e023509; Wed, 1 Jun 2005 12:01:10 -0400 (EDT)
Received: (from mramadas@localhost) by masaka.cs.ohiou.edu (8.12.10+Sun/8.12.10/Submit) id j51G1ArO023506; Wed, 1 Jun 2005 12:01:10 -0400 (EDT)
Date: Wed, 01 Jun 2005 12:01:10 -0400
From: Manikantan Ramadas <mramadas@masaka.cs.ohiou.edu>
To: dtn-security@mailman.dtnrg.org
Cc: dtn-dev@mailman.dtnrg.org
Subject: Re: [dtn-security] Re: [dtn-dev] Re: SDNV-new
Message-ID: <20050601160110.GF9319@masaka.cs.ohiou.edu>
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>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="CXFpZVxO6m2Ol4tQ"
Content-Disposition: inline
In-Reply-To: <20050531172941.GA30682@pisco.cs.berkeley.edu>
User-Agent: Mutt/1.4.1i
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/>

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 *
____________________________________________________________________