 Kurdistan Journal of Applied Research (KJAR) | Print-ISSN: 2411-7684 – Electronic-ISSN: 2411-7706 | kjar.spu.edu.iq Volume 2 | Issue 3 | August 2017 | DOI: 10.24017/science.2017.3.19 A proposed P2P Kurdistan Academic Network Backbone (KANB), Based on Random Linear Network Coding Rami S.Youeel ISE Erbil Polytechnic University Erbil, Iraq r.rami.samir@gmail.com Raghad Z.Yousif Applied Physics. Communication Salahaddin University Hawler, Iraq Raghad.Yousif@su.edu.krd Ferman I.Kareem Erbil Administrative Technical institute Erbil Polytechnic University Erbil, Iraq ferman.ibrahim@gmail.com Abstract: The current rate of growth in computer network usage is a problematic issue motivates the inspiration to investigate less conventional solutions, similar to Network Coding (NC) which has attracted a lot of attention lately, to improve the bandwidth utilization and latency in computer networks. The objective of this paper is to show that the usage of Network coding is possible on enhancing the execution of Kurdistan Academic Network Backbone (KANB) to associate the primary ten urban communities in Kurdistan Region that almost contains a greater part of academic institutions. The proposed model applies peer to peer (P2P) multicasting on KANB, which does not require any centralized knowledge about the topology of the network. The Random Linear Network Coding (RLNC) has been utilized for its superior properties to address the problems of delay, throughput and lake of security associated with store-and-forward based classical networks. Simulation results point out the advantages of using network coding over the classical (store and forward) technique in term of improving the throughput gain and latency reduction. Hawler city the capital and greatest city in Kurdistan Region have been chosen as a source node while Slemani city has been elected as a sink, node. Thus, Network coding is applied at intermediate nodes. Keywords: Network Coding, Random Liner Network coding, Galois field, P2P Multicasting, Network Security, and Throughput. 1. INTRODUCTION Network Coding operation is performed by combining data words (packets) traveling through the network which combines two or more packets into one packet. End nodes, with knowledge of the data sent, can decode received packet. A network that applies NC can be interpreted as a network where the nodes in the network do operations on the received or generated packets rather than just store and forward them as in a traditional packet switched network [1]. In traditional Routing technique, the intermediate nodes simply (store and forward) packets, means the node receives the packets from incoming edges, makes a copy for them, store and forward these packets by outgoing edges. In contrast, using network coding intermediate nodes who have received a number of these packets, can form recorded packets by combining two or more packets coming from incoming edges, the nodes can perform some mathematical operations on the incoming packets then generate one packet and send it to next node as one packet [2][3][4]. The network coding is performed in three different steps: encoding, recoding, and decoding. The server and all clients who have obtained the complete file constructs encode packets by creating linear combinations of partitions of the original data. The encoded packets are transmitted with the corresponding encoding vectors to interconnected nodes. When sufficient linear independent packets and encoding vectors have been received, the original data can be reconstructed by decoding the encoded packets [5]. RLNC is optimal since only channel packets are needed by the receiver to obtain the original source packets with a very high probability [6]. The aim of the proposed system is to design and build a package which simulates (P2P) multicasting (KANB) based on (RLNC). The proposed system fits the requirements of KANB for many reasons: It is decentralized topology. Each peer can act as a peer or as the router. It is beneficial for sending videos streaming between educational institutions in Kurdistan from the main server which is located in region Capital Hawler. 2. LITERATURE REVIEW Numbers of the network coding scheme have been proposed in past for multicast networks some are explaining as follows: Ahlswede et al, they point out the benefit of network coding with the famous butterfly network with one source by using Finite Field in increasing the throughput, they showed that the result of their paper can be equal to the max-flow- min cut approach with applying network coding which means instead of routing and forwarding to multicast information from source to destination, using Network coding will increase the throughput in this network [7]. Yeung et al. They interested in how fast each node can receive all incoming information, they showed that the randomized coding over a finite field will make the network more robust and, also the information would be compressed [8]. Tracy. Ho et al, in their paper were present a new approach for data compression and transmission in multicasting networks depending on a random linear network coding [9]. Richard D. Wesel et al. published paper, describing network coding with a single source and two sinks, the source has a number of messages and each terminal (sink) is interested in a set of these messages from the source node [10]. Baochun Li and Di Niu were demonstrating that the random network coding is a mailto:r.rami.samir@gmail.com mailto:Email@univ.com mailto:ferman.ibrahim@gmail.com practical solution for real-world application in peer-to- peer (P2P) networks [11]. M. Hay et al. they proved that currently, With Network Coding, multiple sources can transmit packets over bottleneck edges at a same time that leads to achieving the max-flow-min-cut throughput and increasing network capacity [12]. T.Manoranjitham et al. proposed a Dynamic Source Routing based on Network Coding to reduce the number of transmissions also to increase the throughput in mobile ad hoc networks, they showed that the throughput with network coding is improved [13]. 3. METHODS AND MATERIALS Linear network coding extends simple network coding by adding some additional information to the packet payload. A node can multiply some coefficient over a finite field with a fixed size of data in the original message, and combine its data with these coefficients as shown in [15][16]. When performing a network coding, the intermediate nodes have to combine incoming blocks and produce one packet. It means, converting these packets to one packet and send it over outgoing links. With linear network coding, outgoing packets are linear combinations of the original packets, where addition and multiplication are performed over the finite field GF as showed in [7] [ 15][14], and also has been described by an example in [16] .In Linear Network Coding, each unit of data is processed using finite fields , which q is a prime number or, assuming a Galois Field (GF), for some integer m, where GF(2 m ) refers to [0, 2 m -1]. It means the elements of coding are in this range. Figure 1 illustrates an acyclic network with w = 2 imaginary channels appended at the source node S. For better understanding the linear network coding using Butterfly network which is the best choice. T U W X R2R1        0 1 fos        1 0 'fos        rp qn ks  tsk T   vukU        x w kw  zykx         p n tsf ),(        r q usf ),(        ps ns wtf ),(        pt nt rtf )1,(        ru qu wuf ),(        rv qv ruf )2,(          ruxpsw quxnsw xwf ),(          ruxypswy quxynswy rxf )1,(          ruxzpswz quxznswz rxf )2,( M 1 M 2 S Figure 1 LNC examples with Local/global encoding Vectors. The source node generates the messages; each message would be associated with an element of GF, and then sent over the network. The network coding is performed by three steps: encoding, recoding, and decoding. The source node and all receiving nodes who have obtained the complete file forms the encoded packets by making linear combinations of partitions of the original data. The encoded packets are transmitted with the corresponding encoding vectors to interconnected nodes. Intermediate peers who have received a number of these packets, can form recoded packets by combining encoded data. When sufficient linear independent packets and encoding vectors received, the original data can be reconstructed by decoding the encoded packets. 3.1 Local / Global Encoding Vectors For every node N, let In (N) represent the set of incoming links to N and Out (N) denotes the set of outgoing links from N. And assuming a pair of channels be called an adjacent pair, and there exists a node N with Є In (N) and e Є Out (N). And also, the In(S) has w imaginary channels. The vector is called the global encoding vector for the channel . The scalar called the local encoding vector for the adjacent pair , which means the local encoding vectors at the node N. Assuming the source generates a message in the form of a w-dimensional row vector. A node N receives the symbols , Є In (N), from which it calculates the symbol for sending onto each channel Є Out (N) via the linear formula: )1().(. )( ,    d NInd ede fxkfx 3.2 Random Linear Network Coding (RLNC) In RLNC, instead of carefully designing a linear network code in the linear information flow algorithm, the local encoding vector is simply chosen completely at random. The difference between (LNC) and (RLNC) is that the elements of F (2 m ) are selected randomly. The Encoding Process As demonstrated in figure 1, starts by splitting the data into a number of original packets at the source node. In linear network coding, each packet through the network is associated with a sequence of coefficients which belong to the field GF ( ), so there is one coefficient for each original packet [8]. The coding operation performed by each node is the same for every node. Received packets are stored in the memory of the node, and packets are formed have to be sent with random linear combinations of its memory contents whenever a packet sending occurs on an outgoing link. The coefficients of the combination are selected uniformly from Galois field. In (RLNC) the coefficients are selected randomly and independently. The coding coefficients are in the form of vector called (Global Encoding Vector) which will be sent in the header of the packet containing a data called (Information vector) Y. ∑ The addition has been implemented over the finite field GF ( ). In each symbol position, the summation has to occur for every symbol position, i.e. ∑ Where and are the symbol of and . With Random Linear Network Coding, the arithmetic operations like addition and multiplications performed over GF ( ), so the resulted packets have the same size with the original packets. Figure 2 demonstrate the length of a packet. Figure 2 NC packets length Where L is a length of the packets and S for s bits of .The re-encoding process can be performed to these packets that were already encoded. Assuming a node that has received a set ( ( of encoded packets. This node can generate a new packet depending on a set of coefficients , these elements belong to GF ( ). So, the new information vector is given as: ∑ And a new encoding vector is equal to ∑ The decoding process will be performed at the sink node (receiver) by using a Gaussian elimination equation, in which the inverse of the coefficients matrix is to be calculated. Sink node has to retrieve the messages which have been generated by the source node. The sink nodes can decode correctly if and only if the overall transfer matrix from the sources to each sink is invertible [18]. The encoded packets carry two types of data: the encoding vector (header) and the information vector . When the sink receives t numbers of s (t ≥ n), it means that the number of received packets needs to be at least as large as the number of original packets. It can decode them and get the original packets. To perform the decoding process this equation must be solved in order to retrieve the original packets. [ ] [ ] [ ] = [ ] (6) Receiver Node d can recover the source symbols as long as the matrix formed by the global encoding vectors. [ ] [ ] The decoding process can be performed by the inverse of coefficients matrix, for a successful decoding process, the determinant of coefficients matrix must not be zero, if it is equal zero, so the matrix has not inverse. Decoding at any node can be achieved by collecting or more packets in a given generation. 4. Proposed system The main interface window of proposed package is depicted in figure 3. Using this interface window, the system features can be activated. Thus by clicking on the button network the tables of nodes interconnection and connection of nodes are generated number of interconnected nodes and edges are also shown. The network information table consist of three columns, the first column lists the name of city, while the second column gives city corresponding node number it’s clear that Erbil city has been decimated into two nodes Hawler-Data which is an imaginary node and Hawler- source which is a source node, the third column indicates the status (function) of each node which is classified into imaginary node, Source node, NC-Router node (perform network coding) and Final-node which is Slemani node. Figure 3 The network Button Clicking results The other table displayed is (Connection of Nodes) table. This table generates a matrix of nodes interconnection, each row in this table contains a combination of zeros and ones, and number one indicates connected incoming and outgoing nodes whereas number zero indicates no connection case. The biography for proposed (KANB) is depicted in figure 4. This graph is generated by clicking on network button in the first interface window. The network hierarchy starts from Erbil city as a top and source node ends with Halabja as an imaginary node. This hierarchy has been suggested based on the city size and by depending on the shortest distance between cities. Figure 4. KANB Biograph Diagram. The system simulation is started when a source node generates packets by multiplying the incoming data with the coefficients that were chosen from a finite field. The destination node (Slemani) regenerates the incoming packets depending on some arithmetic operations described before. The (RLNC) is performed at each one of the seven intermediate nodes (Kirkuk, Zakho, Duhok, Koya, Ranya, Chamchamal, and Soran). The button (Send Image) in main interface window initiate another window named (Network simulation window) as shown in figure 5. This window enables the user to send an image through (KANB) and also display all intermediate results generated when each packet is traveling from source to sink node or destination node. It gives an ability to select any image with any format and size by browsing it after clicking on (Choose File) button. the sent file packets are delivered to all peers in proposed backbone, in another word it shared between all nodes. Finally, the received image is displayed and transmitted the image in two separated fields' axes to show sent image and axes. The package at this level also gives the user the ability to select the number of transmitted blocks at each transmission period which is bounded by three numbers (1, 2 and 3) blocks. Later the effect of a number of blocks on the proposed system throughput is to be studied. All intermediate coding results have been displayed by figure (5). Figure 5 the Main GUI to send an image using (RLNC) 5. RESULTS When the simulation finished, the results are recorded to mark the effect of network coding on the network performance. the entire simulation is carried out using MATLAB R 2015. The table below describes proposed network characteristics Table 1: Proposed Network Characteristics Network type Network Media type Link Capacity Queuing type Without NC Wired 1 byte / observation time Store and Forward / FIFO With NC Wired 1 byte / observation time No queuing needed 5.1 Throughput Gain at each node The most important advantage of using network coding is to improve network throughput. The throughput at each node has been calculated as shown in figure 6. At the end of transmission period using the following formula: (8) The simulation results show that the throughput with network coding is improved. Figure 4-2 reflects the this fact, the throughput is improved at all nodes where network coding is applied in (Soran, Zakho,….) nodes using one block per transmission duration .A comparable throughput values have been observed in other nodes (didn’t perform network coding) like in (Duhok, Koya) nodes. Figure 6 Throughput at each node with & without NC, Figure (7) and Figure (8) depict the effect of increasing number of blocks (two and three blocks respectively) transmitted per transmission period. Figure 7 Throughput at each node with NC, case of two blocks multicasting Figure 8 Throughput at each node with NC, case of three blocks multicasting. It’s clear that increasing the number transmitted Blocks leads to improve the throughput. For example, at Ranya node a throughput gain of approximately 3.2 KB/sec is observed. 5.2 Instantaneous Throughput With / Without NC Figure (9) illustrates the calculation of instantaneous throughput in sending a file of total size of 8 Kb to Zakho node using 1 block in each transmission duration. This node has two input links and one output link, so the (RLNC) is performed at this node, it's clear that the throughput is improved by using NC. Network Coding combines the packets that come from two or more input link(s) and send them to the outgoing link(s) as one packet. Figure 9 Throughput from node Zakho with /without NC 1 block 5.3 Instantaneous latency at Nodes At Ranya node, the instantaneous delay has been calculated as an example and indicated by figure (10) the delay is reduced to the half as compared to the case without network coding. In case of performing RLNC the delay time is reduced because this node combines two packets and sends the output as one packet. Figure 10 Instantaneous Latency in Ranya node 5.4 Transmitted packets security Data security is one of the expected advantages of network coding. The proposed system has investigated this advantage by multicasting a file of 100 bytes size at four different nodes two nodes where network coding is carried out at (Kirkuk and Zakho) nodes, while the third and fourth nodes(Duhok,Koya) point where selected because no network coding is implemented by theses nodes . The difference between original figure (11) (a)(b) and the corresponding encoded bytes transmitted (at outgoing link) are very large as compared to cases of no network coding has been implemented figure(11)(c)(d) by the randomly chosen elements; these elements are belonging to the Galois field. Figure .11 security imposed by network coding 6 DISCUSSION Comprehensive package has been proposed to design, simulate and investigate the impact of RLNC on KANB. (a) (b) (c) (d) 7 Conclusion In this research, a multicast (P2P) system based on (RLNC) is presented to replace the traditional (Store- and-Forward) packet switching technique in proposed design of (KANB) which contains ten nodes represent different cities in Kurdistan. This research investigates the advantages of using network coding technology in improving Backbone throughput, reducing coding and decoding latency with different transmitted data file size. The simulation results showed that by increasing the file size of transmitted data, the throughput and latency gain increased. Also, the security imposed by network coding has been investigated by scattering graph which marks the amount of scattering (randomness) added by network coding technique. 8 REFERENCE [1] L. K. Johansen, Performance Enhancements in Wi- Fi using Network Coding, Norwegian University of Science and Technology press, Trondheim, 2013. [2] Medrad,network coding Fundamentals and Applications, Elsevier Inc press, 1 st ed,2013. [3] R. W. Yeung, “Information Theory and Network Coding,” Springer, New York, NY, USA, 1 st Edition, 2008. [4] Ho, T. and Lun, D. S, Network Coding: An Introduction, Cambridge University Press, Cambridge, UK, 2008. [5] M.V. Pedersen, J. Heide, F.H.P.Fitzek & T. Larsen. “Picture Viewer - A Mobile Application using Network Coding”.In proceeding of European Wireless Conference Aalborg, Denmark ,pp.267- 273, 2009. [6] S. V. Solms, Sune & Helberg “The Implementation of Avalanche Decoding in Random Network Coding Networks”. In the proceeding of (SATNAC) Conference, At Spier Estate.South Africa. Sep. 2010.[online]Available:http://www.satnac.org.za/pr oceedings/2010/papers/management/von%20Solms %20FP%20379.pdf[Accepted:Sep2010] [7] R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung. “Network information Flow,” IEEE Trans. on Information Theory, vol. 46, pp. 1204-1216. 2000. [8] S. Y. R. Li, R. W. Yeung, N. Cai. “Linear Network Coding”, IEEE Transactions on Information Theory, Vol. 49, No. 2, pp. 371–381, 2003. [9] T. Ho, M. Médard, R. Koetter et al., “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006. [10] A.Ramamoorthy and R. D. Wesel, “The single source two terminal network with network coding,”[online] ArXiv e-prints, 2009, available: on http://arxiv.org/abs/0908.2847. [11] B.Li, D. Niu, “Random network coding in peer-to- peer networks: from theory to practice,” in Proceedings of the IEEE, vol. 99(3), pp. 513-523, March 2011. [12] M. Hay, B. Saeed, C. H. Lung, T. Kunz and A. Srinivasan, "Network Coding and Quality of Service metrics for Mobile Ad-hoc Networks," 2013 9 th International Wireless Communications and Mobile Computing Conference (IWCMC), Sardinia, , pp. 521-526, 2013. [13] T.Manoranjitham,V.Nagarajan,"Performance Enhancement Using Network Coding in Dynamic Source Routing", 3 rd International Conference on Recent Trends in Computing 2015 (ICRTC-2015), vol. 57, pp. 896-906, 2015 [14] C. Fragouli, E. Soljanin. “Network coding fundamentals,” Foundations and Trends in Networking, vol. 2, no. 1, pp. 1-133, 2007. [15] Salah A. Aly, Ahmed E. Kamal," Encoding of Network Protection Codes Against Link and Node Failures Over Finite Field," Journal arXiv preprint arXiv:0905.1778, may. 12 ,2009. [Online].Available:https://arxiv.org/pdf/0905.1778.p df. [16] S.-Y. R. Li, N. Cai, and R. W. Yeung, "On Theory of Linear Network Coding," Proceeding of the 2005 IEEE International Symposium on Information Theory (ISIT.05), pp. 273-277, Sep. 2005. [17] R. Koetter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782–795, 2003. [18] A.T. Campo and A. Grant. Robustness of random network coding to interfering sources. In Proc. 7 th Australian Communications Theory Workshop, pages (120-124), Feb. 2006. Biography Asst. Prof. Dr. Raghad was born in Baghdad 1975.He Received a B.S. in Electronic and Communication Engineering from College of Engineering Baghdad University Department of Electronic and Communication Eng. in 1998, M.S. in Electronic and Communication Engineering form department of Electrical Engineering Al-Mustansriyha university –Baghdad in 2001 , then he received a Ph.D. degree in communication Engineering from Baghdad University of Technology Department of Electronics and Electrical Engineering in 2005 .He is currently an Assistance Professor in Department of Applied Physics –Communication at Salahaddin University also he is the lecturer at Department Information technology at CUE(Catholic university in Erbil). His Fields of interest are Network Coding, Medical Imaging, Swarms, Wireless Communication system, and optical communication system and data security. He is a supervisor of many MSc thesis and Ph.D. thesis he was also a member of examination committee of many MSc and Ph.D. theses. He was Awarded the prize of third best Arabic research in data security in the age of Information technology in 2003 awarded by the Association if Arab Universities. http://www.satnac.org.za/proceedings/2010/papers/management/von%20Solms%20FP%20379.pdf http://www.satnac.org.za/proceedings/2010/papers/management/von%20Solms%20FP%20379.pdf http://www.satnac.org.za/proceedings/2010/papers/management/von%20Solms%20FP%20379.pdf http://arxiv.org/abs/0908.2847