Subject: RE: [manet] Regarding packetbb constraints on ordering and uniqueness.

From: "Justin Dean" <[email-masked]>
Date: Wed, 7 Nov 2007 11:43:10 -0500

Included in this email is my reply followed by a reply from Chris Dearlove.

As for encoding a graph within packetbb.  As I see it there are two main
ways of using the TLV structure for conveying directed graph information.
One is more efficient for sparse types of graphs and one is more efficient
for dense graphs.  There are other methods and Chris gets into some ideas
for sending efficiently sending trees or other structured graphs.

General directed dense graph:
List in the address block all the nodes within the graph.  To convey edge
information I would design a multi value TLV which has a bit array for every
address listing the outgoing edges.  The bit array would have to be of
length #ofaddresses rounded up to the nearest byte.  The indexes of the bits
within the (one address) value would match the indexes of the address block.

General directed sparse graph:
List in the address block all the nodes within the graph.  To convey edge
information I would use a TLV for each starting vertex which had a list of
indexes indicating the outgoing edges.  Chris describes this better in his
reply.  

Both of these methods only use one TLV per address and convey all the
information needed.  There are many other ways of transmitting this
information depending on how the TLV is defined some more efficient than
others in different situations. 

Justin Dean

> -----Original Message-----
> From: Dearlove, Christopher (UK) 
> I'm not going to go into this in massive detail, but some comments
> 
> - First, I don't actually find this to be something
>   that a MANET routing protocol is really going to
>   need. So I would regard it as sufficient to be
>   able to do it moderately efficiently, rather than
>   absolutely efficiently. (You can't make everything
>   maximally efficient.) There is one exception to
>   this, my next point.
> 
> - More likely is to want to send a tree, rooted at the
>   sending node. That's done for example by TBRPF. Sending
>   a tree has at least one efficient encoding - use an
>   address block to send the addresses ordered appropriately
>   to a tree traversal, and use a TLV to indicate how each
>   relates to the previous (level change). This can be one
>   multi-value TLV. You may be able to find a yet better
>   way.
> 
> - With regard to a general graph, I can think of at least two
>   reasonably efficient approaches. I'm going to assume a
>   directed graph. The first, and most obvious, is that we
>   list all the "from" node addresses in an address block,
>   and each gets a TLV listing the "to" addresses in what
>   is, in packetbb terms, a single-value TLV, that actually
>   contains multiple values (addresses). (See what we've
>   done in timetlv for comparison.) Of course we don't need
>   to include the full address, as we already have the
>   addresses listed (add in the ones only appearing as "to"
>   addresses) so we can just use indices. The second is to
>   have two address blocks, one for "from" addresses, one
>   for "to" addresses, both of the same length, and there
>   is automatically a link from the first to the first, the
>   second to the second, etc. This is only appropriate for
>   a sparse graph. (Note that there's absolutely nothing to
>   stop you assigning meaning to address blocks in this
>   way.)
> 
> - There's a very good chance that someone who's better at
>   data structures than I am can find an even better solution,
>   using packetbb as is.
> 
> Christopher Dearlove
> 
> 
> -----Original Message-----
> From: Joseph Kopena [mailto:[email-masked]]
> Sent: 02 November 2007 21:10
> To: Manet
> Subject: Re: [manet] Regarding packetbb constraints on 
> ordering and uniqueness.
> 
> 
>                *** WARNING ***
> 
> This mail has originated outside your organization,
> either from an external partner or the Global Internet. 
>      Keep this in mind if you answer this message. 
> 
> On 11/1/07, Justin Dean <[email-masked]> wrote:
> > What I really have a hard time with myself is I haven't seen a
> compelling
> > example of something you couldn't do with the current TLV structure
> > including the restrictions.  There have been some examples, 
> which have
> been
> > discussed on this list, which were slightly smaller in size in some
> cases
> > but which were much less clear in the content which was being
> conveyed.  I
> > am not saying saving bytes is not a worthwhile goal but with the
> current
> > setup there are already multiple ways to encode data and 
> which is most
> > efficient depends on the data being encoded.
> 
> Hi Justin,
> 
> As I mentioned previously, I'm curious about the consensus encoding
> for a graph or two-hop neighborhood that preserves fulltype
> uniqueness.  This may have been covered in previous examples but I
> haven't seen it.  If so, I apologize.  All I'm coming up with is
> either cramming multiple values into a single value or using multiple
> address or message blocks, so I'm curious how to represent this
> information in PacketBB succinctly.
> 
> Thx!
> 
> -- 
> - joe kopena
>   shelter from the storm
> 
> 
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
> 
> 
> ********************************************************************
> This email and any attachments are confidential to the intended
> recipient and may also be privileged. If you are not the intended
> recipient please delete it from your system and notify the sender.
> You should not copy it or use it for any purpose nor disclose or
> distribute its contents to any other person.
> ********************************************************************
> 

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet