Subject: [forces] bitmap representation

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 08:58:45 -0400

While updating the protocol-update I have developed doubts on
bitmaps. I would like to see if it can be removed from mention in the
protocol
update document.

The original intention was for the protocol side to describe how the bitmap
should be packed. i.e a bitmap[N] while looks like a byte[N] cannot simply
be packed into a TLV since the L is a byte/octet counter.
I am sure there are other reasons we said this needs protocol mention,
but i cant recall.

It would simplify the protocol-update document if this becomes part of the
model domain. If we were to define the bitmap as:
{uint32 length, data}
then we could pack upto 2^32 -1 bits in a TLV/ILV where the L would still
count then number of bytes + any padding but the encoded length will count
the number of bits.

Thoughts?

cheers,
jamal

---

From: "Haleplidis Evangelos" <[email-masked]>
Date: Tue, 2 Jul 2013 17:53:11 +0300

Greetings Jamal,

Please see inline.

Regards,

Evangelos Haleplidis.

[ΕΗ] Yes, this won't work and imho defining a specific TLV for bitmaps is
not a good approach (as has been described currently in the model extension
document)

but i cant recall.

[ΕΗ] The main reason we said this needs protocol mention, if I remember
correctly, is that how bitmaps are packed should be defined in a protocol
document instead of a model one.

{uint32 length, data}

the number of bits.

[ΕΗ] While I agree that this would alleviate the need for defining a new
TLV, however is encoding protocol semantics into the model a good practice?

Thoughts?

[ΕΗ] I think that we can safely assume that the LFB knows what is coming for
it as in the case of arrays where it expects an index for a fulldata in
front of each array. Can we use the same concept and word it like "every
bitmap datatype is 32-bit aligned (with padding) and is prefixed with a
32-bit length field that will define the number of used bits"? 

Essentially it's exactly what you described above but encoded in the
protocol instead of the model.

Additionally where would the following text be suitable best, the model or
the protocol?

"The ordering of the bits in a ForCES message MUST be in the order that are
defined in the xml library." 

cheers,

jamal

---

From: Joel <[email-masked]>
Date: Tue, 02 Jul 2013 11:00:07 -0400

Structurally, it really bothers me for the model to discuss bitmaps in 
terms of 32 bit blocks of bits.  A bitmap is a sequence of bits. 
Encoding is a separate matter, and not part of the model.

Yours,
joel

On 7/2/2013 10:53 AM, Haleplidis Evangelos wrote:
> *//*
> */[ΕΗ] Yes, this won’t work and imho defining a specific TLV for bitmaps
> is not a good approach (as has been described currently in the model
> extension document)/*
>
> *//*
> */[ΕΗ] The main reason we said this needs protocol mention, if I
> remember correctly, is that how bitmaps are packed should be defined in
> a protocol document instead of a model one./*
>
> */[ΕΗ] While I agree that this would alleviate the need for defining a
> new TLV, however is encoding protocol semantics into the model a good
> practice?/*
>
> Thoughts?
>
> *//*
>
> */[ΕΗ] I think that we can safely assume that the LFB knows what is
> coming for it as in the case of arrays where it expects an index for a
> fulldata in front of each array. Can we use the same concept and word it
> like “every bitmap datatype is 32-bit aligned (with padding) and is
> prefixed with a 32-bit length field that will define the number of used
> bits”? /*
>
> */Essentially it’s exactly what you described above but encoded in the
> protocol instead of the model./*
>
> *//*
>
> */Additionally where would the following text be suitable best, the
> model or the protocol?/*
>
> */“The ordering of the bits in a ForCES message MUST be in the order
> that are defined in the xml library.” /*
>
> *//*
>
> cheers,
>
> jamal
>
>
>
> _______________________________________________
> forces mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/forces
>

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 12:17:02 -0400

Greetings Evangelos,

On Tue, Jul 2, 2013 at 10:53 AM, Haleplidis Evangelos <[email-masked]>wrote:

>
> **
>
> * *
>
> *[ΕΗ] Yes, this won't work and imho defining a specific TLV for bitmaps
> extension document)*
> **

Not a specific TLV or ILV, rather a way to further refine the description
of the
encode a datatype.
We have an example of such "refinenemt" in the protocol in the form of a
PATH-DATA TLV which is {flags, idcount, idlist, data}
The tuple {flags, idcount, idlist} is always present. It describes the
content
that is encoded which could be a KEY or in the new case TABLE range
If both sides know that we have bitmap on path a/b then both sides
should be able to encode/decode such encapsulation.

 **
>
> I am sure there are other reasons we said this needs protocol mention,****
>
> but i cant recall.****
>
> * *
>
> *[ΕΗ] The main reason we said this needs protocol mention, if I remember
> document instead of a model one.*
>

The question is: why?

> *[ΕΗ] While I agree that this would alleviate the need for defining a new
> *
> **

I am still not seeing this being a protocol semantic.

> *[ΕΗ] I think that we can safely assume that the LFB knows what is coming
> for it as in the case of arrays where it expects an index for a fulldata in
> 32-bit length field that will define the number of used bits"? *
>
> *Essentially it's exactly what you described above but encoded in the
> protocol instead of the model.*
>
> **
>

So at least we have an agreement on the encoding.
If i have a complex type like a struct - I dont need to go to the protocol
and describe it. What i am suggesting is define
this as if it is a struct and then we dont need to say anything at the
protocol level.

> * *
>
> *Additionally where would the following text be suitable best, the model
> or the protocol?*
>
> *"The ordering of the bits in a ForCES message MUST be in the order that
> are defined in the xml library." *
>
> **
>

That is another thing we need to address.
Network order is big endian - and we've always said things go out in
network order - but i am not sure how
well this applies to arbitrary sized bits.

cheers,
jamal

---

From: Joel <[email-masked]>
Date: Tue, 02 Jul 2013 12:22:20 -0400

To answer your "why" question, from my perspective one of the key 
separations between model and protocol is that the encoding of bits on 
the wire is a protocol task.  Providing enough information that bits can 
be encoded is the models task.

Yours,
Joel

On 7/2/2013 12:17 PM, Jamal Hadi Salim wrote:
>     __
>
>     I am sure there are other reasons we said this needs protocol
>     mention,____
>
>     but i cant recall.____
>
>     */__ __/*
>
>     remember correctly, is that how bitmaps are packed should be defined
>     in a protocol document instead of a model one./*
>
>
>
> The question is: why?

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 12:22:36 -0400

On Tue, Jul 2, 2013 at 11:00 AM, Joel <[email-masked]> wrote:

> terms of 32 bit blocks of bits.  A bitmap is a sequence of bits. Encoding
> is a separate matter, and not part of the model.

I am suggesting that this is a model new type. It is a complex struct with
a length followed
by a series of bits. The 32 bit length is just to describe how many bits
exist in the bitmap.
So we have:
   I/TLV,
         L = length in bytes of whats carried including padding
         V =
               length i.e count of bits being carried followed by packed
bits.

cheers,
jamal

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 12:23:30 -0400

Refer to my other email.
If i consider the bitmap entity as a complex type, the protocol is agnostic
to it.

cheers,
jamal

On Tue, Jul 2, 2013 at 12:22 PM, Joel <[email-masked]> wrote:

> separations between model and protocol is that the encoding of bits on the
> wire is a protocol task.  Providing enough information that bits can be
> encoded is the models task.
>
> Yours,
> Joel
>

---

From: Joel <[email-masked]>
Date: Tue, 02 Jul 2013 12:30:15 -0400

It s true that you can, within the current protocol, define a structure 
consisting o a bit count and an array of 32 bit unsigned values.  And 
you can use that for a bitmap.

But from a modeling perspective you are modeling a packing rather than 
modeling a bitmap.  If you want to argue that we do not need to model a 
bitmap of named bits, that's fine.  It is a discussion we should have.

Yours,
Joel

On 7/2/2013 12:23 PM, Jamal Hadi Salim wrote:
> Refer to my other email.
> If i consider the bitmap entity as a complex type, the protocol is
> agnostic to it.
>
> cheers,
> jamal
>
>
> On Tue, Jul 2, 2013 at 12:22 PM, Joel <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     separations between model and protocol is that the encoding of bits
>     on the wire is a protocol task.  Providing enough information that
>     bits can be encoded is the models task.
>
>     Yours,
>     Joel
>

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 13:00:22 -0400

Ok, so let state my case slightly differently.
If i wanted to defined a bitmap as a complex structure which constitutes a
bit-length followed by
the bit-content, I should be able to do that. I dont need to change
anything in the protocol to
accomodate that. I could choose to transport such a type as an ILV or TLV.
The sender and receiver both understand how to de/encode such a complex
type.

If we are on agreement on the above, then:
Given the model defines the base types, i am asking that this complex
struct be made
part of the defined types in the model extension draft.

There may some other ways to express the bitmap in some complex struct -
but what i am
not seeing is the special treatment that a bit map should get from the
protocol that no other
complex struct would need.

cheers,
jamal

On Tue, Jul 2, 2013 at 12:30 PM, Joel <[email-masked]> wrote:

> consisting o a bit count and an array of 32 bit unsigned values.  And you
> can use that for a bitmap.
>
>> <mailto:[email-masked]>**> wrote:
>>

---

From: Joel <[email-masked]>
Date: Tue, 02 Jul 2013 14:54:08 -0400

Clearly, the construct you define is valid within the model and protocol 
and can be used.  I am not sure I would call it a bitmap.
Given tat we are not representing protocol message fields, I am not sure 
what problem is addressed by writing the definition of this data type in 
an RFC for inclusion in other documents that miht want to use it.

Yours,
Joel

On 7/2/2013 1:00 PM, Jamal Hadi Salim wrote:
> If i wanted to defined a bitmap as a complex structure which constitutes
> a bit-length followed by
> On Tue, Jul 2, 2013 at 12:30 PM, Joel <[email-masked]
>     It s true that you can, within the current protocol, define a
>     structure consisting o a bit count and an array of 32 bit unsigned
>     values.  And you can use that for a bitmap.
>
>     But from a modeling perspective you are modeling a packing rather
>     than modeling a bitmap.  If you want to argue that we do not need to
>     model a bitmap of named bits, that's fine.  It is a discussion we
>     should have.
>
>     Yours,
>     Joel
>
>
>         <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>__>
>         wrote:
>
>                       */[ΕΗ] The main reason we said this needs protocol
>         mention,
>                  if I
>
>                       remember correctly, is that how bitmaps are packed
>         should
>                  be defined

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 2 Jul 2013 16:37:29 -0400

> and can be used.  I am not sure I would call it a bitmap.

There are probably more optimal ways of representing a set of bits.

> what problem is addressed by writing

the definition of this data type in an RFC for inclusion in other documents
> that miht want to use it.
>

I will be fine with removing it from both docs.
The reason it showed up to begin with was we found that a bit
representation of some form or other was
frequently used in exchanges between the CE and FE - and that with the
current atomic and base types
definition there was no optimal way to send a set of bits on the wire.

cheers,
jamal

>>         <mailto:[email-masked] <mailto:[email-masked]>**
>> >__>
>>
>>         wrote:
>>

---

From: "Haleplidis Evangelos" <[email-masked]>
Date: Wed, 3 Jul 2013 02:57:23 +0300

Greetings Jamal and Joel,

Clearly, the construct you define is valid within the model and protocol and
can be used.  I am not sure I would call it a bitmap.

[ΕΗ] I agree that this is not a bitmap, as well imho I don't think that's a
datatype. The reason for this is that there are protocol semantics in the
model and I don't think that there should be. The question is why would the
actual data contain information for the protocol on how the message is to be
parsed? And it's not for a special datatype, but for a base datatype.

 

The reason it showed up to begin with was we found that a bit representation
of some form or other was

[ΕΗ] I have no problem as well if it will cause more damage than good. There
is always a way to represent a bitmap as an array or a struct of Boolean,
but as you say it's not optimal. Or you can use another datatype of 1byte or
2 or 4 or 8 bytes to use as a bitmap. The problem here is that you can't
specify the meaning of each bit.

Imho, I don't think that we can express the bitmap in any way using the
current ForCES model/protocol that will allow us without any changes in the
protocol to define a bitmap in any way while allowing an optimal way to send
bitmaps. 

The reason is that the smallest amount of a ForCES datatype is a byte. We
don't deal with bits. Therefore if the wg agrees that there is a need for
being able to model bitmaps we'll have to discuss on the protocol extension
how that is encoded.

Imho, there are a few cases where bitmaps may be useful. Mostly for
capabilities though, for example when you have many 

capabilities of a similar nature, e.g. speed links that you may support, you
can describe it as a bitmap instead of having multiple booleans.

cheers,

jamal

Yours,
Joel

cheers,
jamal

    Yours,
    Joel

        Refer to my other email.

        cheers,
        jamal

        wrote:

             To answer your "why" question, from my perspective one of
        the key
             separations between model and protocol is that the encoding
        of bits
             on the wire is a protocol task.  Providing enough
        information that
             bits can be encoded is the models task.

             Yours,
             Joel

                      __

                      I am sure there are other reasons we said this
        needs protocol
                      mention,____

                      but i cant recall.____

                      */__ __/*

                 The question is: why?

---

From: Jamal Hadi Salim <[email-masked]>
Date: Wed, 3 Jul 2013 06:44:12 -0400

Ok, so how i make the update release for now with a place holder for
bitmap and we can talk about this at the meeting then?
I am going to post a new version of the draft

cheers,
jamal

On Tue, Jul 2, 2013 at 7:57 PM, Haleplidis Evangelos <[email-masked]>wrote:

> Greetings Jamal and Joel,****
>
> ** **
>
> and can be used.  I am not sure I would call it a bitmap.****
>
> ** **
>
> *[ΕΗ] I agree that this is not a bitmap, as well imho I don’t think
> that’s a datatype. The reason for this is that there are protocol semantics
> in the model and I don’t think that there should be. The question is why
> would the actual data contain information for the protocol on how the
> message is to be parsed? And it’s not for a special datatype, but for a
> base datatype.*
>
> ** **
>
> There are probably more optimal ways of representing a set of bits.****
>
>  ****
>
> what problem is addressed by writing ****
>
> the definition of this data type in an RFC for inclusion in other
> documents that miht want to use it.****
>
> ** **
>
> ** **
>
> I will be fine with removing it from both docs.****
>
> representation of some form or other was****
>
> current atomic and base types****
>
> definition there was no optimal way to send a set of bits on the wire.****
>
> ** **
>
> *[ΕΗ] I have no problem as well if it will cause more damage than good.
> There is always a way to represent a bitmap as an array or a struct of
> Boolean, but as you say it’s not optimal. Or you can use another datatype
> of 1byte or 2 or 4 or 8 bytes to use as a bitmap. The problem here is that
> you can’t specify the meaning of each bit.*
>
> * *
>
> *Imho, I don’t think that we can express the bitmap in any way using the
> protocol to define a bitmap in any way while allowing an optimal way to
> send bitmaps. *
>
> *The reason is that the smallest amount of a ForCES datatype is a byte.
> We don’t deal with bits. Therefore if the wg agrees that there is a need
> for being able to model bitmaps we’ll have to discuss on the protocol
> extension how that is encoded.*
>
> * *
>
> *Imho, there are a few cases where bitmaps may be useful. Mostly for
> capabilities though, for example when you have many *
>
> *capabilities of a similar nature, e.g. speed links that you may support,
> you can describe it as a bitmap instead of having multiple booleans.*
>
> ** **
>
> cheers,****
>
> jamal****
>
> ** **
>
>  ****
>
>
> Yours,
> Joel****
>
>
>
> On 7/2/2013 1:00 PM, Jamal Hadi Salim wrote:****
>
>
> On Tue, Jul 2, 2013 at 12:30 PM, Joel <[email-masked]****
>
>         <mailto:[email-masked]>****
>
>         <mailto:[email-masked] <mailto:[email-masked]>>__>**
> **
>
>
>         wrote:
>
> ****
> ** **