Thursday, April 23, 2009

Will Network Coding Become Part of the Network? A Class Experiment

This week in my graduate class on networking algorithms, I asked my class to focus on the question of whether network coding will become a part of "the network" (whatever you choose that to mean). Given the wealth of papers that have appeared its clear the academic community has embraced the notion of network coding, and there's certainly lots of interesting theory. But I don't know of what I would call a significant real-world deployment -- will we see one in the next decade or so? This is, to me, an important question -- certainly I'd be more inclined to work on network coding problems if I think there's a potential for real-world impact. The class has read a few current papers, and I wondered what they would think.

Interestingly, the class pretty much split down the middle, with perhaps a slight bias toward no. The main reasons cited against the development of practical network coding was that there didn't seem to be an immediate killer applications, and the gains, while non-trivial, weren't enough to cover many of the inherent problems (network support, backward compatibility, etc.) in deploying network coding. A common example given was that there were many challenges in mesh/ad hoc networks, and network coding (while useful) wasn't solving the really important ones. On the more optimistic side, several students saw situations (wireless mesh network, "closed" networks where complete control is centralized so network coding can be set up easily) and possible important issues (can network coding improve energy usage?) that would lead to more widespread network coding use in the years to come.

The discussion reminded me of short survey I once wrote up on "Digital Fountains" (and hey, when Googling I see the powers-that-be even posted my slides) where besides discussing their applications I asked why they weren't now in widespread use. The issues sound familiar.

I'd be happy to have others offer their opinions to my class on this issue. Feel free to comment on whether you think we'll see real-world deployments of network coding systems in the future (or let me know of any in existence now!), and what you see the challenges being for network coding going from an interesting idea to a deployed solution.


Anonymous said...

Raptor/Luby codes aren't used because of patents.

Michael Mitzenmacher said...

Anon #1: Yes.... I raise that issue in the survey linked to on the post. (It's not clear that the only reason they're not widely used, but it's a reason.)

Anonymous said...

In the survey you mention the "perceived complexity" in designing
fountain codes as a draw back: Is it your contention that the 3GPP and
DVB specifications for raptor codes are inadequate or suboptimal in
some way?

Anonymous said...

In wireless and mesh networks, interference is the real killer. Network coding for all its hype, does not really solve that problem.
I am not sure whether this is proven yet, but I cant think of a wireless example where NC gain can be greater than two. Furthurmore, NC gain does not necessarily come on top of directional transmission and/or MIMO, so if I have to choose between these two axis, there is more bang for the buck for just adding an additional hardware. NC solutions themselves are a bit raw right now. Perhaps I dont understand things correctly, but from my reading too many papers are trying to convince me that rank is the same thing as decoding. Without going into details, we really dont have convincing/elegant enough solution which brings traditional mechanisms like window flow, queue shaping etc with network coding, even as decoding at the reciver remains low complexity. Gaussian elemination unless it is like done by Burshstein etc aint an option in my opnion. I personally am quite fascinated by certain Avalanche like apps of network coding, particularly those using Lt codes. However, again here we need to move a bit away from theory and start developing codes which allow intermediate recovery, unequal protection while acutally taking into markov dependencies of a video source. Perhaps I just repeated the discussion in your class :). So NC seems fun, but more valuable problems are out there.

Christian Esteve Rothenberg said...

Exactly this discussion appeared last week in a panel on "what are the hot topics in networking?" at Infocom. The distinguished panelists (Keith Ross, N. Shroff, Sajal Das and Don Towsley) and the audience seemed not to disagree that after a hype of research on NC its practical application to real world networking scenarios was still missing.

The requirements of large multicast traffic over specific topologies makes their use case, specially in wired settings, hard to justify (despite Gbps performance issues).

The Generic Path approach within the EU 4Ward project proposes two "real-world" applications: 1) considering MPLS and a signling plane to trigger the NC operations, and 2) NC over Ethernet Passive Optical Networks for traffic between end-users attached to the same EPON splitter and exploiting the broadcast nature of passive optical downlinks. (See: D-5.2.0 Description of Generic Path Mechanism_PU.pdf)

Addtional uses cases include DTN and swarm communications (cf. D-5.1 Architecture of a Generic Path_PU.pdf)

Find here some additional thoughts on the hot topics in networking discussed at Infocom 2009.

Andrew Eckford said...

NC will eventually find niche applications. However, someone in a position to know once told me the following: the limiting factor in large-scale wired networks is not bandwidth, it's computational complexity at the routers. Since NC would exacerbate this problem, it will never achieve widespread deployment in large-scale wired networks, even if you were allowed to, e.g., redesign a future Internet from scratch.

Kiyan said...

my name is kayhan iam doing phd on nework coding in vanet.could you please tell me about packet structure of coded packet or encoded packet.also i am fACING so many difficulties in my phd due to network coding can some body help me to solve the problems.

Unknown said...

I like to use a good network because i usually am online all the time.Once I Saw costa rica homes for sale and i though it was very nice, because is a great country.