Subject: Re: [nwcrg] Packet fields

From: jonathan detchart <[email-masked]>
Date: Fri, 27 Feb 2015 17:41:21 +0100

Hi Victor,

Here are my comments:

1. In your list, you are talking about Block. In our implementation, we are not using a block code. If you consider real time transmissions, you must’t use block codes.

2. We are using an elastic encoding window which is a solution complitly different than block based codes. This item must be added in your list.

3. A repair/coded packet/payload/symbol is a combination of a set of sources : in our case, this set is variable, and a repair doesn’t belong to a block. This information must be optional.

4. Our coding vector field only contains the Ids, not the coefficients. Else, it is not scalable. Actually most of the published network coding solutions don't send the coding vectors because of the high overhead. And it's also our case. We should consider this case in the NWC architecture documents.

5. The use of the previous hop IP address is not always useful and have a big overhead (16 bytes with IP v6 !).

6. Last thing, we are using some feedback packets/format. It should be added too.

Jonathan

> On 27 Feb 2015, at 00:26, Victor Firoiu <[email-masked]> wrote:
> 
> 
> Hi Jonathan,
> 
> I'm putting together a list of fields that are necessary for a practical NC protocol, based on existing implementations. I'm planning to add them to an updated version of the NWC architecture.
> 
> Here is a draft list that I have so far for block-based coding. Let me know if you are using other fields in your implementations. If you are using window-based coding, let me know the fields you are using for that as well.
> 
> All the best,
> 
> Victor
> 
> ===
> NC Packet fields for block-based coding, over GF(2^k)
> 
> 1. Information associated with a coded packet (symbol)
> 
> Binary Galois field exponent – exponent k in GF(2^k). 
> 
> Block ID – identifier of the block to which this coded packet (symbol) belongs
> 
> Block Size – Size of the block in number of packets (symbols)
> 
> Coding vector – a vector of coding coefficients that produced the coded payload. The vector size is equal to the block size. The size of each coefficient (k) in bits is equal to the binary Galois field exponent.
> 
> Block remaining life, or time to live, or TTL – remaining life of this block (in milliseconds) after which all packets belonging to this block are discarded.
> 
> Flow ID or Session ID or Subgraph ID – unique identifier of the flow to which this packet belongs.
> 
> Previous hop – IP address of the node that generated (coded and transmitted) this packet. 
> 
> Repair flag – indicates that the packet arrived in response to a repair request
> 
> 2. Information associated with a repair request
> 
> Block to repair – ID of a block in which the requesting node needs a new coded packet, aka a repair packet.
> 
> Null Space Sample – A coding vector that is a (random) sample of the subspace in which the requesting node needs a new coded packet (symbol), aka a repair packet.

---

From: Marie-Jose Montpetit <[email-masked]>
Date: Fri, 27 Feb 2015 17:00:47 +0000

Thanks Jon for bringing to the list!

Is this to define a common header format for the architecture draft?

I have some other comments beyond what you listed below.

- The use of the previous hop ID could become incompatible with Information/Content centric networks that are considering NC for some implementations (and no IP address). Maybe this should be optional or replaced by a more generic ID that points to path information.

- There should be room for application/system specific field; hence I am a huge fan of extension headers for that purpose.

/mjm

Marie-Jose Montpetit, Ph.D.
[email-masked]
@SocialTVMIT

> On Feb 27, 2015, at 11:41 AM, jonathan detchart <[email-masked]> wrote:
> 
> Hi Victor,
> 
> Here are my comments:
> 
>> On 27 Feb 2015, at 00:26, Victor Firoiu <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> 
>> Hi Jonathan,
>> 
> _______________________________________________
> nwcrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/nwcrg

---

From: Victor Firoiu <[email-masked]>
Date: Fri, 27 Feb 2015 13:17:31 -0500

Thanks, Jonathan.

Indeed, there would be two modes (at least), and thus two field sets, one
for block coding and another for window-based. Some of the fields will be
common to both.
More comments in-line.

Thanks,
Victor

On Fri, Feb 27, 2015 at 11:41 AM, jonathan detchart <
[email-masked]> wrote:

> Hi Victor,
>
> Here are my comments:
>
> 1. In your list, you are talking about Block. In our implementation, we
> are not using a block code. If you consider real time transmissions, you
> must’t use block codes.
>
> 2. We are using an elastic encoding window which is a solution complitly
> different than block based codes. *This item must be added in your list.*
>
> 3. A repair/coded packet/payload/symbol is a combination of a set of
> sources : in our case, this set is variable, and a repair doesn’t belong to
> a block. *This information must be optional.*
>
> Please give more details on what information is needed here.

> 4. Our coding vector field only contains the Ids, not the coefficients.
> Else, it is not scalable. Actually most of the published network coding
> solutions don't send the coding vectors because of the high overhead. And
> it's also our case. *We should consider this case in the NWC architecture
> documents.*
>

Again, Please give more details on what information is needed here.

> big overhead (16 bytes with IP v6 !).

Agreed, this should probably be optional.

> 6. Last thing, we are using some feedback packets/format. *It should be
> added too*.
>
> Please give more details.

Thanks again,

Victor

---

From: Victor Firoiu <[email-masked]>
Date: Fri, 27 Feb 2015 13:33:19 -0500

This is a first step in that direction, to get an idea of what information/
fields are used in existing implementations.
I think some fields would be optional, including previous hop; we'll see
other opinions as well. The actual header format, including extensions,
would be something to tackle after we settle on the field/information set.
Other considerations at that next step would be variants to have compressed
information, such as using indices instead of values for coding
coefficients, as Jonathan mentioned.

Victor

On Fri, Feb 27, 2015 at 12:00 PM, Marie-Jose Montpetit <[email-masked]>
wrote:

> - The use of the previous hop ID could become incompatible with
> Information/Content centric networks that are considering NC for some
> implementations (and no IP address). Maybe this should be optional or
> replaced by a more generic ID that points to path information.
>
> - There should be room for application/system specific field; hence I am a
> huge fan of extension headers for that purpose.
>
> /mjm
>
> I'm putting together a list of fields that are necessary for a practical
> NC protocol, based on existing implementations. I'm planning to add them to
> an updated version of the NWC architecture.
>
> Here is a draft list that I have so far for block-based coding. Let me
> know if you are using other fields in your implementations. If you are
> using window-based coding, let me know the fields you are using for that as
> well.
>
> All the best,
>
> Victor
>
> ===
> Coding vector – a vector of coding coefficients that produced the coded
> payload. The vector size is equal to the block size. The size of each
> coefficient (k) in bits is equal to the binary Galois field exponent.
>
> Block remaining life, or time to live, or TTL – remaining life of this
> block (in milliseconds) after which all packets belonging to this block are
> discarded.
>
> Null Space Sample – A coding vector that is a (random) sample of the
> subspace in which the requesting node needs a new coded packet (symbol),
> aka a repair packet.
>
>

---

From: Cedric Adjih <[email-masked]>
Date: Fri, 27 Feb 2015 21:10:35 +0100 (CET)

Hello NetCoders,

It is nice to see some lively discussion on the list;

With respect to packet format, for DragonCast/DragonNet,
this was separated in 3 parts:
  . flow information
  . state information
  . coded payload information
See: https://tools.ietf.org/id/draft-adjih-dragoncast-00.html#DRAS

Of course a lot of the information is what all of you proposed.
Below, the list of fields; those suggested also by Victor are marked 
with "(*)",  the fields removed in our implementation for sensor 
networks are marked with "(-)" (see pp33-36 of   
http://getrf.gforge.inria.fr/category/Docs/getrf_livrable3.pdf )

- Flow information (constant parameters + coded payload identifier)
  . (*) Flow-ID (-)
  . (*) Block ID (-)
  . (*) Block size
  . Sliding-window size
  . Source rate

- Node state information (strongly coupled to the protocol)
  . (*) node id
  . rank 
  . lifetime (e.g. of the node state information)
  . number of neighbors
  . high index
  . low index

- Coded payload information
  . (*) encoding type and coding parameters (GF, ...) (-)
  . encoding vector data size
  . (*) encoding vector data
  . first index of encoding vector
  . (*) coded payload size
  . (*) coded payload 

(In "CISEW", only the node state information would be augmented
 http://tools.ietf.org/html/draft-amdouni-nwcrg-cisew-00.html )

best regards,
-- Cedric

----- Original Message -----
| From: "Victor Firoiu" <[email-masked]>
| To: "Marie-Jose Montpetit" <[email-masked]>
| Cc: [email-masked], "jonathan detchart" <[email-masked]>
| Sent: Friday, February 27, 2015 7:33:19 PM
| Subject: Re: [nwcrg] Packet fields
| 
| 
| 
| 
| 
| This is a first step in that direction, to get an idea of what
| information/ fields are used in existing implementations.
| 
| 
| I think some fields would be optional, including previous hop; we'll
| see other opinions as well. The actual header format, including
| extensions, would be something to tackle after we settle on the
| field/information set. Other considerations at that next step would
| be variants to have compressed information, such as using indices
| instead of values for coding coefficients, as Jonathan mentioned.
| 
| 
| Victor
| 
| 
| On Fri, Feb 27, 2015 at 12:00 PM, Marie-Jose Montpetit <
| [email-masked] > wrote:
| 
| 
| 
| 
| Thanks Jon for bringing to the list!
| 
| Is this to define a common header format for the architecture draft?
| 
| 
| I have some other comments beyond what you listed below.
| 
| 
| 
| - The use of the previous hop ID could become incompatible with
| Information/Content centric networks that are considering NC for
| some implementations (and no IP address). Maybe this should be
| optional or replaced by a more generic ID that points to path
| information.
| 
| 
| - There should be room for application/system specific field; hence I
| am a huge fan of extension headers for that purpose.
| 
| 
| /mjm
| 
| 
| 
| 
| Marie-Jose Montpetit, Ph.D.
| [email-masked]
| @SocialTVMIT
| 
| 
| 
| 
| On Feb 27, 2015, at 11:41 AM, jonathan detchart <
| [email-masked] > wrote:
| 
| 
| 
| Hi Victor,
| 
| 
| Here are my comments:
| 
| 
| 1. In your list, you are talking about Block. In our implementation,
| we are not using a block code. If you consider real time
| transmissions, you must’t use block codes.
| 
| 
| 2. We are using an elastic encoding window which is a solution
| complitly different than block based codes. This item must be added
| in your list.
| 
| 
| 3. A repair/coded packet/payload/symbol is a combination of a set of
| sources : in our case, this set is variable, and a repair doesn’t
| belong to a block. This information must be optional.
| 
| 
| 4. Our coding vector field only contains the Ids, not the
| coefficients. Else, it is not scalable. Actually most of the
| published network coding solutions don't send the coding vectors
| because of the high overhead. And it's also our case. We should
| consider this case in the NWC architecture documents.
| 
| 
| 5. The use of the previous hop IP address is not always useful and
| have a big overhead (16 bytes with IP v6 !).
| 
| 
| 6. Last thing, we are using some feedback packets/format. It should
| be added too .
| 
| 
| Jonathan
| 
| 
| 
| 
| 
| On 27 Feb 2015, at 00:26, Victor Firoiu < [email-masked] > wrote:
| 
| 
| 
| 
| 
| Hi Jonathan,
| 
| 
| I'm putting together a list of fields that are necessary for a
| practical NC protocol, based on existing implementations. I'm
| planning to add them to an updated version of the NWC architecture.
| 
| 
| Here is a draft list that I have so far for block-based coding. Let
| me know if you are using other fields in your implementations. If
| you are using window-based coding, let me know the fields you are
| using for that as well.
| 
| 
| All the best,
| 
| 
| Victor
| 
| 
| ===
| 
| NC Packet fields for block-based coding, over GF(2^k)
| 
| 
| 1. Information associated with a coded packet (symbol)
| 
| 
| Binary Galois field exponent – exponent k in GF(2^k).
| 
| 
| Block ID – identifier of the block to which this coded packet
| (symbol) belongs
| 
| 
| Block Size – Size of the block in number of packets (symbols)
| 
| 
| Coding vector – a vector of coding coefficients that produced the
| coded payload. The vector size is equal to the block size. The size
| of each coefficient (k) in bits is equal to the binary Galois field
| exponent.
| 
| 
| Block remaining life, or time to live, or TTL – remaining life of
| this block (in milliseconds) after which all packets belonging to
| this block are discarded.
| 
| 
| Flow ID or Session ID or Subgraph ID – unique identifier of the flow
| to which this packet belongs.
| 
| 
| Previous hop – IP address of the node that generated (coded and
| transmitted) this packet.
| 
| 
| Repair flag – indicates that the packet arrived in response to a
| repair request
| 
| 
| 2. Information associated with a repair request
| 
| 
| Block to repair – ID of a block in which the requesting node needs a
| new coded packet, aka a repair packet.
| 
| 
| Null Space Sample – A coding vector that is a (random) sample of the
| subspace in which the requesting node needs a new coded packet
| (symbol), aka a repair packet.
| _______________________________________________
| nwcrg mailing list
| [email-masked]
| https://www.irtf.org/mailman/listinfo/nwcrg
| 
| 
| 
| _______________________________________________
| nwcrg mailing list
| [email-masked]
| https://www.irtf.org/mailman/listinfo/nwcrg
|

---

From: "Tracey Ho" <[email-masked]>
Date: Fri, 27 Feb 2015 11:51:24 -0800

Hi Victor and all,

Definitely agree that we need variants for different ways to represent coding vector information, since different network scenarios/topologies would not have the same information requirements. For repair requests, it may be useful to include the number of degrees of freedom needed. We can also consider repair requests spanning multiple blocks.

Best,

Tracey

From: nwcrg [mailto:[email-masked]] On Behalf Of Victor Firoiu
Sent: Friday, February 27, 2015 10:33 AM
To: Marie-Jose Montpetit
Cc: [email-masked]; jonathan detchart
Subject: Re: [nwcrg] Packet fields

This is a first step in that direction, to get an idea of what information/ fields are used in existing implementations.

I think some fields would be optional, including previous hop; we'll see other opinions as well. The actual header format, including extensions, would be something to tackle after we settle on the field/information set. Other considerations at that next step would be variants to have compressed information, such as using indices instead of values for coding coefficients, as Jonathan mentioned.

Victor

On Fri, Feb 27, 2015 at 12:00 PM, Marie-Jose Montpetit <[email-masked]> wrote:

/mjm

@SocialTVMIT

Hi Victor,

Here are my comments:

Jonathan

 

Hi Jonathan,

All the best,

Victor

===

---

From: "Tracey Ho" <[email-masked]>
Date: Fri, 27 Feb 2015 12:48:57 -0800

Hi all,

Best,

Tracey

 

Victor

/mjm

@SocialTVMIT

Hi Victor,

Here are my comments:

Jonathan

 

Hi Jonathan,

All the best,

Victor

===

---

From: Vincent Roca <[email-masked]>
Date: Fri, 27 Feb 2015 21:56:09 +0100

Hi everybody,

A few comments…

It’s certainly useful to have an idea of what is being used by existing solutions.
However it also adds complexity since we merge everything together, whereas
parts of it are for very specific use-cases.

If we want to follow a Building Block approach (i.e. « divide to conquer »), we’d
better (1) classify the pieces of information needed according to the BB they belong
to, as Cedric began to do for instance, and (2) leave some tricky details related to
a very specific BB for the future, while specifying this BB.

In any case I prefer to focus on « signaling mechanisms » in general rather than
« header fields » which are just one aspect of signaling.

Cheers,

  Vincent