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

Michael Demmer <demmer@cs.berkeley.edu> Tue, 31 May 2005 17:29 UTC

Received: from pisco (pisco.CS.Berkeley.EDU [128.32.37.175]) by webbie.berkeley.intel-research.net (8.11.6/8.11.6) with ESMTP id j4VHTgV29864; Tue, 31 May 2005 10:29:42 -0700
Received: from demmer by pisco with local (Exim 4.50) id 1DdAYf-0008BH-VA; Tue, 31 May 2005 10:29:41 -0700
Date: Tue, 31 May 2005 10:29:41 -0700
From: Michael Demmer <demmer@cs.berkeley.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: <20050531172941.GA30682@pisco.cs.berkeley.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>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <4295D547.9080808@cs.tcd.ie>
User-Agent: Mutt/1.4.2i
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/>

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.