Network Coding as a Service Da´vid Szabo´1, Attila Csoma1, Pe´ter Megyesi1, Andra´s Gulya´s1 2, Frank H.P. Fitzek3 4 Abstract Network Coding (NC) shows great potential in various communication scenarios through changing the packet forwarding principles of current networks. It can improve not only throughput, latency, reliability and security but also alleviates the need of coordination in many cases. However, it is still controversial due to widespread misunderstandings on how to exploit the advantages of it. The aim of the paper is to facilitate the usage of NC by (i) explaining how it can improve the performance of thenetwork(regardlesstheexistenceofanybutterflyinthenetwork),(ii)showinghowSoftwareDefinedNetworking(SDN)can resolve the crucial problems of deployment and orchestration of NC elements, and (iii) providing a prototype architecture with measurement results on the performance of our network coding capable software router implementation compared by fountain codes. 6 Index Terms 1 0 Network Coding; SDN; Click; VNF 2 n I. INTRODUCTION a According to the traditional concept of packet switched networks independent data flows may share network devices but the J informationitselfremainsseparated.NCbreaksupthisprincipleasittreatstheseflowsasalgebraicallycombinableinformation, 3 thereby when two flows f , f enter a node Kirchoff’s law doesn’t hold any more; the output appears not as f +f but 1 2 1 2 1 F(f ,f ). 1 2 ] In the seminal paper [1] Ahlswede at al. show a butterfly topology for illustrating that even a simple bitwise XOR, i.e. NI F(f1,f2)=f1XORf2, used at the proper node of the network can lead to a considerable throughput gain. Unfortunately this nice example also caused confusion as many people mistakenly think that NC can only be used in such a far-fetched, artificial . s situation. This misunderstanding often appears in literature [2] and overshadows its intense evolution during the last decade. c Nowadays NC is not only about butterflies and XOR operations but instead creating linear combinations in a distributed way [ usingrandomnumbergenerators,knownas“randomlinearnetworkcode”(RLNC)[3].RLNCalsointroducesrecoding,i.e.to 1 recombine the flows without first decoding them thus fundamentally changes nodes’ behaviour since it replaces the store-and- v forward approach with compute-and-forward. This is ground breaking to all other coding strategies that are only end-to-end 1 based (Reed-Solomon, Raptor, etc.) and leads to gain not only for throughput, but for latency, security and complexity as well, 0 2 furthermore it is feasible for any topology. 3 However, for the efficient use of RLNC we have to deploy encoder, decoder and recoder elements in the network and we 0 have to take care of steering the traffic properly over them. At this point Software Defined Networking with Network Function . 1 Virtualization(NFV)canbethe“dooropener”technologiesforRLNC,sincetheyenabletoimplementRLNCspecificfeatures 0 asVirtualizedNetworkFunctions(VNFs)[4]thatcanbeconnected,orchained,tocreatecommunicationservices.TheseVNFs 6 then can easily be orchestrated by the control layer of SDN. 1 The integration of network coding into SDN has alreay been proposed. [5] and [6] discuss the possibilities of using XOR : v type network coding through the extension of OpenFlow protocol [7] and functions of switches. In [8] authors investigate the i delay bounds in survivable routing with network coding in SDN. In this paper we extend our prior works [9], [10] that is X orthogonal to the aforementioned ones as we investigate the usability of RLNC through NFV in SDNs, that doesn’t require to r a modify existing devices or protocols (e.g. OpenFlow), and also provide a proof of concept. In the following we give an overview about RLNC and also highlight its features that make it fundamentally different from the generally used block codes (Section II), then we describe our SDN prototype architecture - with implementation details - that enables the definition, configuration and automated deployment of RLNC specific VNFs (Section III), finally we provide anextensivecomparisonabouttheperformanceofRLNCandblockcodeswithanalyticalandmeasurementresultsside-by-side (Section IV). Section V concludes the paper with future work. II. RANDOMLINEARNETWORKCODING A. Fundamentals RLNC treats data in the form of generations and symbols. A symbol (cid:126)s is a vector of Galois Field (GF) elements that represent some data depending on the number of elements n and the size of the GF f according to |(cid:126)s| = n·log (f) [byte]. 2 1BudapestUniversityofTechnologyandEconomics,Hungary 1HSNLab,Dept.ofTelecommunicationsandMediaInformatics 2MTA-BMEInformationsystemsresearchgroup 3TechnischeUniversita¨tDresden,Germany 45GLabGermany Email:{szabod,csoma,megyesi,gulyas}@tmit.bme.hufrank.fi[email protected] 1 ε ε ε ε ε ε ε ε ε E x x D E D/E D/E D E R1 R2 D dp dp dp G G G β latency β latency β latency (a) end−to−end (b) hop−by−hop (c) RLNC Fig. 1: Illustration of end−to−end, hop−by−hop and RLNC coding schemes for sending a message of 2 packets (G) through three hops with 50% probability loss on each link (ε=0.5). β stands for redundancy (700%, 50% and 50% for E2E, HbH and RLNC, respectively) and d for propagation delay. p For example 8 elements in GF(2) can represent 1 byte. A generation G comprises g symbols of size |(cid:126)s|, so it can represent g·|(cid:126)s| bytes of data and it is arranged into a matrix M=[s (cid:124),s (cid:124),...,s (cid:124)]. 1 2 g In order to create a coded symbol s(cid:126) a coding vector (cid:126)v is required, that contains a coefficient – which is an element of c GF – for each symbol in the generation. To encode a new symbol s(cid:126) from a generation at the source M is multiplied with a c randomly generated coding vector(cid:126)v of length g, s(cid:126) =M·(cid:126)v(cid:124). In this way we can produce g+e coded symbols, where e∈Z c is the number of extra symbols as RLNC is a rate-less code. When a coded symbol is transmitted on the network it is accompanied by its coding vector, and together they form a coded packet p = {(cid:126)v,s(cid:126)}. In order to successfully decode a generation the decoder has to receive g linearly independent symbols c c (cid:124) (cid:124) (cid:124) and coding vectors from that generation. All received symbols are placed in the matrix S =[s(cid:126) ,s(cid:126) ,...,s(cid:126) ] and all coding c c1 c2 cg vectors are placed in the matrix V=[v(cid:126)(cid:124),v(cid:126)(cid:124),...,v(cid:126) (cid:124)]. The original data then can be decoded as M=S ·V−1. 1 2 g c Inpracticeapproximatelyanyg codedsymbolsareenoughforasuccessfuldecodingofgenerationG.Certainlyitispossible toreceivealinearlydependentsymbolbutthechancesofthisisnegligiblebyusingatleastGF(8),furthermore,sendinganother randomly coded symbol is a much looser constraint compared to when no coding is used, where exactly all g unique, original symbols have to be collected. However, the most important feature of RLNC is recoding. Any node that received at least g(cid:48) ∈[2,g] linearly independent symbols from a generation and its rank is equal to the rank of V, can recode. All received symbols are placed in the matrix (cid:124) (cid:124) (cid:124) (cid:124) (cid:124) (cid:124) S = [s(cid:126) ,s(cid:126) ,...,s(cid:126) ] and all coding vectors in the matrix V = [v(cid:126) ,v(cid:126) ,...,v(cid:126) ]. To recode a symbol these matrices are c c1 c2 cg(cid:48) 1 2 g(cid:48) multiplied with a randomly generated vector w(cid:126) of length g(cid:48),(cid:126)v =V·w(cid:126)(cid:124), s(cid:126) =S ·w(cid:126)(cid:124). In practice this means that a node that c c have received more than one symbol can recombine those symbols into recoded symbols, similar to the way coded symbols are constructed at the source, but without having to wait for the whole generation. In other words, a node can change its behaviour from store-and-forward to compute-and-forward. B. Insights of the benefits of RLNC In order to shed some more light on this conceptual change we take a closer look on three different coding schemes that are carried out on a single path - multihop channel. This restriction may seem strange at first glance but we have two good reasons for doing this: (i) packet forwarding on the Internet is mostly carried out in this way, and (ii) we would like to dispel the common misunderstanding that NC cannot be used in any other case than multicast. Accordingly we assume an encoder E that delivers a message comprises G packets to a decoder D. Along the path packets forwarded by multiple relay nodes (Xs) and we also assume error prone links with loss probability 0 ≤ ε ≤ 1 (Fig. 1). We consider the following three cases: Block codes in end-to-end manner (E2E): In this scheme encoding and decoding are performed only once by E and D, respectively. The relay nodes only store-and-forward each successfully received packet, implying that E should emit enough amount of extra packets for the whole channel to compensate the loss and to make sure that D can reconstruct the message (Fig. 1a). This eventuates unnecessary traffic loads on the links closer to E, which is particularly painful when losses occur only on links far from E, and also increase latency. Blockcodesinhop-by-hopmanner(HbH):Inthisschemeweassumethatrelaynodescanalsoperformencodinganddecoding that enables to generate extra packets per hop in a distributed way (Fig. 1b). This unburdens the network from the unnecessary packets but also infuse extra latency as every relay has to wait to start encoding until the full message is decoded. Random Linear Network Coding: RLNC enables for relays to perform recoding, that is to create a coded packet from the received ones without decoding them first (Fig. 1c). This is far less complex than decode/encode procedure, hence eventuates immediate forwarding, furthermore, it is completely transparent, so decoding doesn’t require extra effort. This greatly reduces latency and as it is carried out per hop requires the same number of packets as the HbH scheme. However, in order to use 2 RLNC efficiently, first we have to deploy elements with encoding, decoding and recoding capabilities and we have to take care of steering the traffic over them. In Section IV we provide an extensive comparison of RLNC and block codes supported both analytical and measurement results, but as the measurements were carried out on our SDN architecture first we show how SDN and virtualization can facilitate the integration process of RLNC in a seamless way. III. SDNPROTOTYPEARCHITECTURE Here we give a brief introduction about SDN and Network Function Virtualization (NFV), followed by the implementation details of RLNC capable elements, finally we introduce the architecture which enables the definition, configuration and automated deployment of these novel elements implementing code centric operation in the network. A. SDN and virtualization The basic concept of SDN is to enable network innovation - realizing new capabilities and addressing persistent problems with networking -, which is almost impossible nowadays. The problem lies in the distributed and heterogen nature of current networks. There are closed, vendor specific hardwares, softwares and firmwares across the network managed by distributed control functions through different interfaces. This leads to difficult and extensive design and operation. SDNaimstochangethisbycreatingwelldefinedabstractionsofdifferentnetworklayers,thateachhasitsproperfunctionality andinterfaces.InthissensetheideaissomewhatsimilartotheISO/OSIconception,butinsteadofindividualdevicesitconcerns thenetworkasawholewiththefollowingfeatures:(i)maintainstheseparationofthedataandcontrolplanes,(ii)usesuniform vendor-agnostic interface – one of the most commonly used is OpenFlow [7] – between control and data planes, (iii) treats the control plane in a logically, centralized way that is realized using a network operating system that constructs and presents a logical map of the entire network to services or control applications implemented on top of it, and (iv) slices and virtualises the underlying physical network. Duringitstwodecadesevolution[11]theconceptofSDNinspiredseveralnoveltechnologiesandturnedoutthatitsynergizes wellwithmanyexistingones.OnethatreallyshinesoutamongstthemisNetworkFunctionVirtualization(NFV).NFVenables to implement any hardware middleboxes (a network device that manipulates traffic, e.g. firewall, network address translator, etc.) intosoftware bycreating Virtualized NetworkFunctions (VNFs).These VNFs hasexactly thesame functionality butthey don’t require specific hardware and hundreds of them can be installed - even remotely - on a single device. This offers nice synergy with SDN as the control layer is capable to orchestrate the installation, configuration and traffic steering over VNFs in an automated way. Such orchestration and steering is in perfect agreement with the current practice of Internet Service Providers (ISPs) that services are implemented in the form of appropriately concatenated middleboxes, also known as service chains [12]. However, todays service chains are usually built around special purpose networking hardware elements, configuring and operating these chains is a highly non-trivial task which still requires human interaction. SDN and virtualization can be a promising way out of this managerial trap as they enable flexible and automated deployment of service chains comprising our RLNC capable VNFs. B. Implementation of RLNC Software Router Prototype SinceVNFsarerunonNFVplatformsthefirstdesignstepistochooseonefromthemanyexistingones([13],[14],[15],[16]). Our design choice was ClickOS [17], as ClickOS virtual machines are extremely small (5 Mb), can boot very quickly (about 30 ms), add small delay (around 45 µs) and hundreds of them can run concurrently with a throughput around 10 Gb/s. ClickOS requires VNFs created by the Click modular router platform [18], which enables to built custom routers by creating configurations pieced together from built-in or own-developed elements that implement atomic functionality like packet classifying, scheduling, queuing etc. Using the Kodo [19] network coding software library we have developed the RLNC encoder, recoder and decoder Click elements and using built-in modules we have created fully-fledged compute and forward software routers. The Click interpreter reads configurations written in a Click-specific language. These config files describe a directed graph withelementsatverticesandedgesspecifyingpossiblepathsforthepacketswithintherouter.Thebehaviouroftheelementsare given by C++ code. At the code level each element is a subclass of the Element class, which has around 20 virtual functions and most subclasses have to override only up to six of them. The most simple subclass implementation, the NullElement, contains only 8 lines of code and overrides five Element class functions. Similarly, we have implemented our code-centric elements which encode, recode and decode the incoming packets using Kodo. Kodo offers a number of different erasure correcting codes of which we chose Full Random Linear Network Code (Full RLNC),asitisoneofthemostcommonRLNCvariantsandprovidesseveraloftheadvantagesthatRLNCshaveovertraditional erasure correcting codes. Accordingly our three custom Click elements are FullRLNCEncoder, FullRLNCDecoder and FullRLNCRecoder.Allofthemtakearound120-150linesofC++code(withnoparticularoptimization)andoverrideseven 3 N enevxieVrocNnuFmti o enn t OCNET Kreocdood er1 Mininet H1 F N N OCNET OVS enevxieVrocNnuFmti o enn t OCNET dKeocdood er F F Code centric router! OVS OVS OVS Kodo recoder2 NE T VNF SLOT 2 C enevxieVrocNnuFmti o enn t OCNNET eKnocdood er VNF SLOT 3 ONF H2 F Dataplane connections OVS Service chains Packet switched service Packet switched Code centric NCOEopTdeCen OFcleNonwFtric service enevxieVrocNnuFmti o enn t OCNNET Kreocdood er3 H1 H2 H1 E RR D H2 F R Fig. 2: The prototype architecture. virtual functions of the Element class. They have one input and one output port and the coding parameters can be tuned through input arguments: SYMBOLS, SYMBOL SIZE, GF SIZE, EXTRA. The SYMBOLS argument stands for the generation size and tells the maximal number of symbols that can be combined into a coded symbol by the encoder. Increasing the generation size also increases the decoding delay, since the decoder has to receive at least SYMBOLS number of packets to be able to decode the whole generation. SYMBOL SIZE represents the size of each symbol in bytes. Increasing this eventuates increased coding complexity. So the SYMBOLS∗SYMBOL SIZE product should be considered carefully and large data typically sent through multiple generations. The GF SIZE argument stands for the size of the Galois Field, which has influence on the probability that an encoded packet doesn’t carry any useful information. Finally the EXTRA parameter represents the ratio of redundancy, in other words tells how many extra packet should be generated. This parameter is required only for the encoder and the recoder. Since other built-in Click elements can preprocess UDP1 packets (i.e. strip IP and UDP headers) the general behaviour of our code-centric elements is quite simple: After a packet arrives extract the payload, encode/recode/decode it by calling the proper functions of Kodo, update IP and UDP headers (size and checksum fields as we slightly increase the packet size by adding the coding coefficients) and forward the packet. In this way our router configurations implement the compute and forward router as a VNF that performs code-centric operations on the packet going through and can easily be deployed into SDN environment. C. Architecture For showing the seamless integration of network coding and SDN we have built a prototype of the code centric network architecture. In a real network it would be a practical choice for operators to place NC encoder and decoder elements as close to the edge of the network as possible, while recoders operate in the most efficient way at intermediate nodes where they can aggreagate traffic flows. To test our proof-of-concept we created a smaller network to model a similar topology where every packet between two users traverses an encoder a recoder and a decoder (in this order). To simulate such network we implementedourarchitectureintheESCAPEprototypingenvironment.Welldetaileddescriptionaboutitcanbefoundin[20], however, here we recollect the most important information of the components. ESCAPE is capable to simulate OpenFlow networks combining Mininet network virtualizer [21] using Open vSwitch (OVS) [22] instances and a POX netowork control prototyping software [23], which contains a steering module handling the flow tables according to the configuration of the running service chains. ESCAPE is designed in such way that it can initiate Mininet virtual containers which capable to run binaries or source codes written in Click language. To use these containers as VNFs ESCAPE configure OVS elements with POX in such way that all traffic between end users traverse them. Typically after an initial deployment process OVS configuration remains the same during the simulation. Since the controller canautomaticallydeployVNFsimplementedinClickandoursoftwarerouterinSec.III-BisimplementedintheClickplatform too,ourworkherewastotranslateourClickconfigurationsaccordingtothetemplatesusedbyESCAPEandinstallallsoftware required to run ESCAPE and Kodo. Note that the traffic steering in a real network with multiple users, diverse requirements 1OurcurrentimplementationcanprocessUDPpacketsonly.ThehandlingofTCPflowsisinourfutureworklist. 4 and huge amount of independent flows raises several open questions. However, in this paper we restricted ourselves only to provide a proof of concept implementation which requires a minimalistic network with a few traffic flows. Fig.2presentsascenarioofourcode-centricprototype.WebuildanOpenFlow1.0networkofthreeOpenvSwitchinstances (OVS), two hosts (H1/H2) and three VNF containers. These containers (yellow boxes) are advanced Mininet hosts which can start a given VNF process. This solution stands for the case when we run VNFs outside the routers e.g. in a near OpenStack [24]datacenter.Inthesecontainerswedeployedourcomputeandforwardsoftwarerouterconfiguredtoencode/recode/decode packets similarly to our scenarios in Fig. 1 for implementing our coding schemes (E2E, HbH and RLNC). This solution may slightly increase latency but provides the possibility of scaling out in the presence of massive network loads combined with more complex coding schemes (e.g. more efficient random linear codes using larger GF field size). Alternatively, we have also built a visionary prototype of the code centric router (green box). This router consists of a standard OVS (no modifications in OpenFlow) instance but has the capability to execute VNFs. Using code centric routers addslessdelaybutthereisnowaytoscaleoutbeyondtherouter’shardwareresources.ThePOXorchestratormodulereceives service chains as inputs (can be given by GUI), configure the switches and start the appropriate VNFs accordingly. IV. COMPARINGRLNCWITHBLOCKCODES A comprehensive analysis can be found in [25] and [26] about the performance of difference coding schemes including complexity, delay, memory requirement, achievable rate, and adaptability. However, in order to facilitate understanding we recall the most important claims on the number of sent packets and latency adjusted to the communication scenarios described in Section II-B and provide measurements results for a wide range of parameter settings side-by-side. For the measurements we realized all the three scenarios as service chains in our prototype architecture and besides the properties of the links (erasure probability and bitrate) we varied the number of hops, packet size and coding generation as well (Table I). Parameter Values erasureprobability(cid:15) 10%,20%,30%,40%,50% packetsizeL 250B,500B,750B,1000B,1450B generationsizeG 16,32,64,128 numberofhopsH 2,3,4,5,6,7 channelrate 0.25,0.5,1,2,4,8Mbps TABLE I: The parameter set for the measurements. During the analysis we assume a single path - multihop channel (described in Section II), where the encoder E delivers a message of G packets through H number of links to a decoder D, we also assume error prone links with loss probability 0≤ε≤1. A. Number of Sent Packets Now we calculate the overall number of sent packets required D to successfully decode the message. In the case of E2E this is the sum of packets sent per hop - comprises extra packets for compensating losses - on the rest of the channel, which depends on generation size G, number of hops H and loss probability ε: H H (cid:88) (cid:89) 1 P = G (1) E2E 1−(cid:15) i h=1 i=h For HbH and RLNC it is again the sum of the packets sent individually but here losses have only local impact due to the decode/encode procedure carried out at each hop: H (cid:88) 1 P =P =G· (2) HbH RLNC 1−(cid:15) i i=h In Fig. 3 the number of overall packets conveyed in a three hop communication network versus the erasure probability per link for the three forwarding schemes is given for the theoretical (indicated by (T) in the figure) and for the measurement results. The figure show that the results of the theory and measurements are consistent with each other. HbH and RLNC use thesameamountofpackets,andwhiletheyincreasethenumberofpacketslinearlywiththelossprobability,theE2Eapproach increases exponentially. 5 End−to−end (T) ● Hop−by−hop / RLNC (T) End−to−end 0 0 Hop−by−hop / RLNC s 6 t e k c ● a ● p 00 ● ● ● ● 2 0 0 10 20 30 40 50 loss [%] Fig. 3: Number of overall packets conveyed in the network versus channel loss probability (Packets 64 - Size 250 B - Hops 3) 0 0 0 ] 5 ● s ● m 0 ● y [ 50 ● c ● n e ● t 0 a 5 ● End−to−end (T) End−to−end l Hop−by−hop (T) Hop−by−hop 0 RLNC (T) RLNC 1 0 2 4 6 8 bitrate [Mb/s] Fig. 4: Latency in the network versus channel rate for three coding approaches and no losses (Packets 64 - Size 1450 B - Loss 0% - Hops 3) B. Latency Based on packet numbers we can calculate the time required for decoding the message successfully. In other words, we are interested in the time that takes to deliver all packets of G from E to D and we also calculate with an inter packet time τ P which is the multiplicative inverse of the packet sanding rate and link delay τ that each packet suffers during forwarding (we L assume the same dealy for every H links). In the case of E2E this is the sum of packets emitted at first hop - comprises extra packets as well - and an extra delay per hop (since packets are forwarded immediately and in parallel at each hop): H (cid:89) 1 D =G· ·τ +H ·τ (3) E2E 1−(cid:15) P L i i=1 100 100 10 10 10 6 80 8 80 60 8 6 8 4 y [s]y [s] 60 40 y [s]y [s] 6 4 y [s]y [s] 6 2 encenc 40 20 encenc 4 2 encenc 4 latlat 20 0 latlat 2 0 latlat 2 0 0 0 0 2 3hop4 5 6 7 0 10 2lo0ss 3[%0]40 50 2 3hop4 5 6 7 0 10 2lo0ss 3[%0]40 50 2 3hop4 5 6 7 0 10 2lo0ss 3[%0]40 50 (a) end−to−end (b) hop−by−hop (c) RLNC Fig. 6: Latency for the three transmission schemes depending on number of hops and loss (Packets 64 - Size 250 B - Bitrate 0.25 Mb/s). 6 ● 0 ● 0 ● ] 0 s 5 ● m ● [ ● y c n 0 e 0 t 1 ● End−to−end (T) End−to−end a l Hop−by−hop (T) Hop−by−hop 0 RLNC (T) RLNC 1 0 2 4 6 8 bitrate [Mb/s] Fig. 5: Latency in the network versus channel rate for three coding approaches and high losses (Packets 64 - Size 1450 B - Loss 50% - Hops 3) For HbH this is the time for the first hop multiplied by the number of hops as every node has to perform decoding/encoding before forwarding even the first packet: H (cid:88) 1 D =G·τ · +H ·τ (4) HbH P 1−(cid:15) L i i=1 The case of RLNC scheme comprises the best part from both E2E and HbH, since packets are forwarded immediately and in parallel with the same number of packets per hop as in HbH: 1 D =G·τ · +H ·τ (5) RLNC P 1− max (cid:15) L i 1≤i≤H Fig.4presentsthelatencyinathreehopcommunicationnetworkversuschannelratewithoutanylossesforthethreecoding approaches. If there are no losses E2E and RLNC have the same latency values (since no extra packets are required to send, which would slow E2E), while the HbH ends up in higher latency values because each intermediate node needs to wait for all packet of G. The gain of RLNC over HbH remains constant for the higher values which means that the ratio of latency is independent from the bandwidth. Roughly, the ratio of the gain in latency equals to H, when G is significantly higher than H. The latency results change a lot if the channel is error prone as given in Fig. 5 with an error probability of 50%. Now the advantage of RLNC over the other two schemes becomes evident and E2E is now even worse than HbH. After having a look again at Fig. 1 this is not so surprising, since E2E have to send through all redundancy on the whole channel. While HbH can unburden the network, as redundancy have to be sent per hop, there the store and forward behaviour increases latency. However, in Fig. 5 it can be observed that while measurement follows theory well for E2E and HbH we got much higher values for RLNC. In [25] authors already proved that in the case of a two-hop network with identical links the delay function √ grows as n thus it does not follows the original formula in Eq. 5. We investigated this phenomenon further and discuss the reasons in Appendix A. Suffice it to say for now that RLNC performs a bit worse as theory would suggest when the error probabilities of the links are similar. InthefollowingsweextendthemeasurementsforawidevariationofparametersandbasedonthefactthatRLNCperforms worse than expected when error probabilities are close to each other we set the values accordingly in order to show that even in this case RLNC outperforms the other coding schemes. In Fig. 6 latency for the three transmission schemes depending on number of hops and loss probabilities is given. In the case of small number of hops with low loss E2E can keep pace with RLNC, at the expense of more sent packets. However, the latency increases significantly for large number of hops that are highly error prone. For HbH it increases linearly with the number of hops and increases with the probability of losses as given in Equation 4. RLNC has a lower latency than the other two schemes over a wide range of parameters. In Fig. 7 the gain of RLNC over the two schemes are given, namely E2E versus RLNC and HbH versus RLNC in Fig. 7a and Fig. 7b, respectively for a better comparison of the three schemes. The gain is calculated by the division of the latency either for E2E or HbH and RLNC. The plots in Fig. 7 show a clear gain of RLNC over the other schemes. The maximum gain over E2E and HbH for the given parameters is 16x and 6x, respectively. Note, in Fig. 7b the axes have been switched in order to increase visibility. In Fig. 8 the loss probability is still set to 10% and the latency is plotted against the number of hops and the packet size. Most communication scenarios will use the maximum transfer unit (MTU) size of ∼1500 bytes, but smaller packet size will 7 probably come up in future. For all three forwarding schemes latency increases linearly with packet size but HbH suffers the most as it is slower up to 4 times – and E2E is up to 1.5 times – compared to RLNC. Considering that the rate of loss is small what really makes the difference here is the different packet forwarding mechanisms described in Fig. 1. So with very small losses E2E can operate almost as efficient as RLNC, because the few number of extra packets, but HbH still slow due to the decoding-encoding at the middle nodes. So summing up the cases observed RLNC does not resonate as much as the other two schemes and breaks new grounds for future networking systems. V. CONCLUSIONANDFUTUREWORK In this paper we have investigated some of the most important advantages of RLNC, the modern form of network coding, and we have shed some light on its application possibilities. We have provided a detailed comparison of RLNC and other coding strategies in terms of latency and traffic imposed to the network. In order to facilitate the use of RLNC we have also presented a prototype architecture demonstrating a feasible integration in SDN environment by using Virtualized Networking Functions. The VNFs implement RLNC functionality that enables us to leave all the management and traffic steering tasks on the SDN controller. This lead to flexible and automated deployment of service chains comprising network coding specific features, hereby introducing the code centric networking in SDN environment which is at same time compatible with the traditional packet switched networks. Accordingtoourresults-bothanalyticalandmeasurement-RLNCnotonlyoutperformstheothers,asefficientlydecreasing latency and number of sent packets, but also introducing flexibility by enabling packet forwarding without a centralized scheduling logic. In the future we will extend the measurements and the SDN prototype with multi-path functionality, since multipathcommunicationwillnotonlyincreasethethroughoutandresilience,butalsocontributetoafurtherdecreasedlatency. The need for RLNC over other coding techniques will become even more evident in the multipath context. Instead of the FullRLNC mode of Kodo, in the future we can use the sliding window approach that will reduce further the packet delay significantly. APPENDIXA RECURSIVEFORMULAFORCALCULATINGLATENCYINATWOHOPSYSTEM To take a closer look on the difference between measurements and theory in Fig. 5 for RLNC we created a simulation environment for the most simple case of RLNC comprising only one encoder, one recoder and one decoder with two error prone links between them. For the sake of simplicity, in the simulation we calculated link delay as zero and used time slots as an analogy for inter packet time, so each node sends one packet per slot. Fig. 10 shows the latency as number of time slots required until the full message was decoded in dependency of the two channel error probabilities (cid:15) and (cid:15) . It can be seen 1 2 that difference occurs between theory and simulation only when error probabilities are close to each other ((cid:15) ≈ (cid:15) ), which 1 2 suggests that Eq. 5 isn’t precise but what actually happens is that due to the finite generation sizes the actual loss on the two channels during the simulation is not exactly (cid:15) and (cid:15) but slightly differs from them as a random variable. When the error 1 2 rate on one channel is significantly higher than the rate on the other the impact of this effect is very small since there is very low chance that more packet will be lost on the lower error rate channel (we can say that the higher error suppresses the lower). When the two error rates are close to each other we always have to calculate with the higher random value thus the result will be higher than expected from the theory. To check our intuition we created a recursive formula based on the forwarding process that can calculate the latency in this 2 hop case. Since forwarding ends when the full generation comprising G packets is delivered to the decoder, let (g,r) be the state of the system, where g is the number of packets that has to be delivered to the decoder and r the number of 16 16 8 16 12 14 6 12 8 1102 4 gaingain 8 4 gain 68 2 4 0 4 0 2 0 0 2 3hop4 5 6 7 0 10 2lo0ss 3[%0]40 50 0lo1s0s [%20] 30 40 507 6 5 4hop3 2 (a) Gain of RLNC over E2E (b) Gain of RLNC over HbH Fig. 7: Gains for the three transmission schemes (Packets 64 - Size 250 B - Bitrate 0.25 Mb/s). 8 9 24 6 24 24 21 24 latency [s]latency [s] 1112258169 036 latency [s]latency [s] 1112258169 0369111258 latency [s]latency [s] 1112258169 03 3 3 3 02 1500 02 1500 02 1500 3 3 3 4 1000 4 1000 4 1000 hop 5 6 500packet size [byte] hop 5 6 500packet size [byte] hop 5 6 500packet size [byte] 7 0 7 0 7 0 (a) end−to−end (b) hop−by−hop (c) RLNC Fig. 8: Latency for the three transmission schemes depending on number of hops and packet size (Packets 64 - Loss 10% - Bitrate 0.25 Mb/s). (g,r) (g,0) 1-ε₁ ε₁ 1-ε₁ ε₁ (g,0) 1-ε₂ ε₂ 1-ε₂ ε₂ 1-ε₂ ε₂ (g-1,r) (g,r+1) (g-1,r-1) (g,r) (g-1,0) (g,1) (b) State transition graph when the recoder has at least (a) State transition graph when the recoder is empty. on linearly independent packet. Fig.9:Graphicalrepresentationofatwohopsystem:g isthenumberofpacketsthatthedecoderstillneedsinordertodecode the full generation, r is the number of linearly independent packets in the recoder. ## 1000 5710500000 ## 1000 5710500000 me slot]me slot] 1 0705 257150500 packetpacket 257505 0000 1 0.8 0e.26 0.4 0.2 0 0 0.2 0.4 0.e6 01.8 1 0250 packetpacket 257505 0000 1 0.8 0e.26 0.4 0.2 0 0 0.2 0.4 0.e6 01.8 1 0250 (latency [tilatency [tic) 25T 500h 1e d 0i.f8fe r0ee.26nc 0e.4b e0t.w2e e0n 0th 0e.2 t0h.4 e0o.e6 r01y.8 1i n0Eq. (a)LatencycalculatedfromtheoryinEq.(5). (b) Latency calculated from simulations. (5) and the simulations. Fig. 10: Number of time slots required to successfully send one generation of packets using RLNC through a two channel network with loss probabilities of (cid:15) and (cid:15) . 1 2 packet#packet#(a 1) 0257L0505 00000a 1ten 0c.y8c 0ea.26lc u0l.4at e0d.2fr o0m 0r e0.c2 u0.r4 s0i.ev6 01e.8 1f o02571r5050m00000ulapacket#packet# 1 02570505 00000 1 0.8 0e.26 0.4 0.2 0 0 0.2 0.4 0.e6 01.8 1 02571505000000 (latency [time slot]latency [time slot]c) 1 0257T 05050h 1e d0i.8ffe 0er.2e6n c0.e4b 0e.2tw e0en 0t 0h.e2 0.v4 0a.le6 u01.e8 1s 02571c5050a0lcu- (b) Latency calculated from simulations. lated from the recursive formula in Eq. (7) in Eq. (7). and the simulations. Fig. 11: Number of time slots required to successfully send one generation of packets using RLNC through a two channel network with loss probabilities of (cid:15) and (cid:15) . 1 2 linear independent – i.e. the useful – packets the recoder has and can send innovative packets based on them. This let us to distinguish two fundamentally different situations (Fig. 9), (i) when recoder is running dry (Fig. 9a) and (ii) when the recoder has useful packets to forward an innovative packet (Fig. 9a). When the recoder is running dry it means that if the packet from the encoder is lost the recoder can not send an innovative packet to the decoder thus the system stays in the same (g,0) state but one time slot wasted. In [25] authors present a similar model for delay calculation in RLNC and they state that a closed formula is too complex when g is larger than 4. After that they use a random variable for modelling the delay thus -due to our 9 knowledge- we are the first ones to present a closed recursive formula for delay in RLNC using arbitrary generation number and link losses in a two hop network. We differentiate three cases as follows. 1) Ifr =g:incasetherecorerhasenoughnumberoflinearlyindependentpacketstosendthereminderofthegenerationto the decoder, it does not need any extra packet from the encoder. Thus it means that we have to send g number of packet through a single link with an error probability of (cid:15) . In this case the expected number of time slots can be calculated as 2 follows. 1 E(g,g)=g· (6) 1−(cid:15) 2 2) If r = 0: in this situation if the packet from the encoder get lost the recoder can not send an innovative packet to the controller (see Fig. 9a). The expected number of time slot needed for sending the remaining packet can be calculated with the following recursive formula. E(g,0)=1+(1−(cid:15) )(1−(cid:15) )E(g−1,0) 1 2 +(1−(cid:15) )(cid:15) E(g,1)+(cid:15) E(g,0) 1 2 1 1 = +(1−(cid:15) )E(g−1,0)+(cid:15) E(g,1) 1−(cid:15) 2 2 1 (7) 3) If 0<r <g: in this case the recoder already has r number of linearly independent packets thus even when the packet from the encoder to the recoder get lost the recoder can send an innovative packet to the decoder (see Fig. 9b). The expected number of time slot needed for sending the remaining packet can be calculated with the following recursive formula. E(g,r)=1+(1−(cid:15) )(1−(cid:15) )E(g−1,r) 1 2 +(1−(cid:15) )(cid:15) E(g,r+1) 1 2 +(cid:15) (1−(cid:15) )E(g−1,r−1) 1 2 +(cid:15) (cid:15) E(g,r) 1 2 1 = 1−(cid:15) (cid:15) 1 2 (1−(cid:15) )(1−(cid:15) ) + 1 2 E(g−1,r) 1−(cid:15) (cid:15) 1 2 (1−(cid:15) )(cid:15) + 1 2E(g,r+1) 1−(cid:15) (cid:15) 1 2 (cid:15) (1−(cid:15) ) + 1 2 E(g−1,r−1) (8) 1−(cid:15) (cid:15) 1 2 On Fig. 11 we compared again the simulations with the values derived from the recursive formula and we get almost no difference, so this formula describes the process precisely. However, generalizing this recursive formula for H number of hops has exponential complexity since the state system can be described by H number of variables (the number of packets that the decoder still needs to decode the full generation and the linearly independent packets in every H −1 recoders). REFERENCES [1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” Information Theory, IEEE Transactions on, vol. 46, no. 4, pp. 1204–1216,2000. [2] M.Medard,M.-J.Montpetit,C.Rosenberg,andF.Fitzek,“Networkcodingmythbusting:Whyitisnotaboutbutterfliesanymore,”2012. [3] R. Koetter and M. Me´dard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking (TON), vol. 11, no. 5, pp. 782–795, 2003. [4] “Etsiportal, networkfunctionsvirtualisation: An introduction, benefits, enablers, challenges and call for action.” October2012. [Online]. Available: ”http://portal.etsi.org/NFV/NFV White Paper.pdf” [5] F.Ne´meth,A´.Stipkovits,B.Sonkoly,andA.Gulya´s,“Towardssmartflow:casestudiesonenhancedprogrammableforwardinginopenflowswitches,” ACMSIGCOMMComputerCommunicationReview,vol.42,no.4,pp.85–86,2012. [6] S.LiuandB.Hua,“Ncos:Aframeworkforrealizingnetworkcodingoversoftware-definednetwork,”inLocalComputerNetworks(LCN),2014IEEE 39thConferenceon. IEEE,2014,pp.474–477. [7] N.McKeownetal.,“OpenFlow:enablinginnovationincampusnetworks,”SIGCOMMComput.Commun.Rev.,vol.38,no.2,pp.69–74,2008. [8] A.PasˇicandP.Babarczi,“Delayawaresurvivableroutingwithnetworkcodinginsoftwaredefinednetworks,”2015. [9] D.Szabo´,A.Gulya´s,F.Fitzek,andD.E.L.Roetter,“Towardsthetactileinternet:Decreasingcommunicationlatencywithnetworkcodingandsoftware definednetworking.” [10] D.Szabo´,F.Ne´meth,B.Sonkoly,A.Gulya´s,andF.H.Fitzek,“Towardsthe5grevolution:Asoftwaredefinednetworkarchitectureexploitingnetwork codingasaservice,”inProceedingsofthe2015ACMConferenceonSpecialInterestGrouponDataCommunication,ser.SIGCOMM’15,2015,pp. 105–106. [11] N.Feamster,J.Rexford,andE.Zegura,“Theroadtosdn,”Queue,vol.11,no.12,p.20,2013.