Subject: [nwcrg] Network Coding Taxonomy draft

From: Victor Firoiu <[email-masked]>
Date: Thu, 20 Feb 2014 18:40:57 -0500

Dear NetCoders,

Here is a first draft of a Taxonomy document based on our presentation
at last meeting and your subsequent feedback.

There are several areas in need of your inputs, such as:
- concepts for the sliding window coding method
- concepts related to security combined with network coding, such as
homomorphic encryption
- references to papers where the various concepts collected here have
(first) been defined or used.

Please send you comments on this mail list. We will also discuss it at
our meeting in London.

Best,

Victor

---

From: Frank Fitzek <[email-masked]>
Date: Fri, 21 Feb 2014 00:46:15 +0100

Dear all,

maybe the text below from KODO can help for the defining

https://kodo.readthedocs.org/en/latest/overview.html

and some text for the existing text (e.g. elements)

https://kodo.readthedocs.org/en/latest/faq.html

All the best

On 21.02.2014 00:40, Victor Firoiu wrote:
> _______________________________________________
> nwcrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/nwcrg

-- 
Professor Dr.-Ing. Frank H.P. Fitzek
Aalborg University
Niels Jernes Vej 12, room A3 208 DK-9220 Aalborg Denmark
Phone:+49 173 548 29 47 or +45 9940 8678 Fax:+45 9815 1583
email:[email-masked] web:www.fitzek.net

---

From: Victor Firoiu <[email-masked]>
Date: Fri, 21 Feb 2014 16:46:21 -0500

Thanks, Frank,

Indeed, we can add some definitions from your references. For others,
we have definitions but with different names, such as symbol (as usual
in coding theory) vs payload (more usual in networking, and currently
used in this draft).  This was also pointed out by Vincent in an
earlier message along with similar pairs such as application-level
payloads vs. source symbols. Clearly this is one topic we need to
discuss in the upcoming meeting.

Victor

---

From: Cedric Adjih <[email-masked]>
Date: Sun, 23 Feb 2014 20:29:56 +0100 (CET)

Hello All,

  Thank you Victor for this first version of the taxonomy.

  Here is a little more terminology for Sliding Window Network Coding that might be of interest (with some sample references, not necessarily the first):

***

indices:
  the original payloads are numbered with indices 1,2, . . . N

degrees of freedom ([1,4] & before) = Rank of Payload Set

sliding window/(en)coding window [2,3,4,5]:
  The sliding window is a set of consecutive indices of original payloads: a node generates coded payloads that are linear combinations of original payloads with indices in its current sliding window.
  
sliding window size [5,3,4]:
  the number of consecutive indices of the window

seen (original payload seen at a receiver) [1,4,5,6]:
  an original payload is “seen”, when the receiver can compute a linear combination with this payload and original payloads with only higher indices.
Otherwise it is unseen.

sensed (original payload sensed at a receiver) [6]:
  at a receiver, an original payload is “sensed” when it is present in at least in one of the received coded payloads. Otherwise it is unsensed.

lowest index/highest index of coded payload [3]:
  the minimum (resp. maximum) index of original payloads involved in a coded payload. 

acknowledgment:
 information about state of the payload set of a receiver

***

Note that the some of the terminology actually assumes Gaussian Elimination;
when the matrix is in “reduced row echelon form” (see for instance http://mathworld.wolfram.com/EchelonForm.html), consider an original payload and its corresponding index:
- “seen” = the index corresponds to a “pivot” of the reduced matrix
- “sensed” = there is one or several non-zero coefficient(s) in the column of the matrix corresponding to the index.

***

[1] Sundararajan, Jay Kumar, Devavrat Shah, and Muriel Médard. "ARQ for network coding." In Information Theory, 2008. ISIT 2008. IEEE International Symposium on, pp. 1651-1655. IEEE, 2008.
[2] Lacan, Jérôme, and Emmanuel Lochin. "Rethinking reliability for long-delay networks." In Satellite and Space Communications, 2008. IWSSC 2008. IEEE International Workshop on, pp. 90-94. IEEE, 2008.
[3] Song-Yean Cho and C. Adjih, "Wireless Broadcast with Network Coding: DRAGONCAST", Inria Research Report  RR-6569, July 2008.
[4] Sundararajan, Jay Kumar, Devavrat Shah, Muriel Médard, Michael Mitzenmacher, and Joao Barros. "Network coding meets TCP." In INFOCOM 2009, IEEE, pp. 280-288. IEEE, 2009.
[5] Lin, Yunfeng, Ben Liang, and Baochun Li. "SlideOR: Online opportunistic network coding in wireless mesh networks." In INFOCOM, 2010 Proceedings IEEE, pp. 1-5. IEEE, 2010.
[6] Bao, Wei, Vahid Shah-Mansouri, Vincent WS Wong, and Victor Leung. "TCP VON: Joint congestion control and online network coding for wireless networks." In Global Communications Conference (GLOBECOM), 2012 IEEE, pp. 125-130. IEEE, 2012.

Best Regards,
-- Cedric

----- Original Message -----
From: "Victor Firoiu" <[email-masked]>
To: [email-masked]
Sent: Friday, February 21, 2014 12:40:57 AM
Subject: [nwcrg] Network Coding Taxonomy draft

Dear NetCoders,

Best,

Victor

---

From: Frank Fitzek <[email-masked]>
Date: Sun, 23 Feb 2014 20:39:01 +0100

Also some comments from my side

FF