A practical Network Coding and Routing Scheme based on Maximum Flow Combination
Download 1.23 Mb.
|
- Navigate this page:
- Table of Contents
- List of Figures
- Abstract
- Introduction
| 111Equation Chapter 1 Section 1
A Practical Network Coding and Routing Scheme based on Maximum Flow Combination Lianlong Wu BSc (Hons) Computer Science School of Computing and Intelligent Systems University of Ulster, United Kingdom Supervisor: Kevin Curran April 2010 Table of ContentsTable of Contents 2 List of Figures 6 Acknowledgements 7 Abstract 8 1Introduction 9 1Network Coding 13 1.1Challenges in Network Coding 14 1.2Current Research Focus 15 1.2.1Centralized Network Coding 15 1.2.2Distributed Network Coding 15 1.3Applications 16 2Network Coding Fundamental Theory 19 2.1Definition of Graph 19 2.2Min-Cut and Max-Flow 19 2.3Min-Cut Max-Flow Theorem 22 2.4Multicast Problem 22 2.5Max-flow Bound Theorem 22 2.6Linear Network Coding 24 2.7Random Linear Coding 25 2.8Routing for Network Coding 25 2.8.1Coding at Merging Node 25 2.8.2Multicast Coding Routing 25 3Requirement Analysis and Specification 27 3.1Problem Description 27 3.2Algorithm Design Objectives 27 3.3Implementation Specification 27 3.4 Network Example 28 4Algorithm Design for the Coding - Routing Scheme 30 4.1Construction of Multicast Flow Graph 30 4.1.1Max-Flow Algorithms 30 4.1.2Labelling Algorithm 30 4.1.3Merging Max-Flow for Obtaining Multicast Flow Graph 32 4.1.4The Target Set of an Edge 34 4.2Packet Representation and Operations 36 4.2.1Representation of Packet 36 4.2.2Split Target Set of Packet 37 4.2.3Coding Data Blocks of Two Packets 38 4.3Algorithm for Construction of Coding and Routing Scheme 38 4.3.1Node Arrangement in Topological Order 38 4.3.2Forward Operation 39 4.3.3Multicast Operation 40 4.3.4Coding Operation 42 4.3.5Coding and Routing Scheme Example 44 4.3.6Identification of Node Types 45 5Implementation of the Proposed Algorithm 47 5.1Development Environment 47 5.1.1Python Programming Language 47 5.1.2Graph Visualization with Graphviz 47 5.2Data Structures 47 5.3Data File Format 49 5.3.1Input File format 49 5.3.2Output File Format 49 5.4Flow Chart of Program 51 5.5Code Examples 53 5.5.1Codes for Drawing Figures 53 5.5.2Code for Topological Sorting 54 6Testing and Experimental Results 55 6.1Test Cases for Max-Flow Module 55 6.2Test Cases for Proposed Algorithm 57 6.2.1Typical Test Cases 57 6.2.2Random Test Cases 61 6.3Validation of the Coding and Routing Scheme 63 6.3.1Capacity Validation 63 6.3.2Decoding Validation 63 6.4Experimental Results 64 6.4.1Optimizing Number of Coding Nodes 64 6.4.2Comparison Number of Coding Links 67 6.4.3 Comparison Running Time 67 7Conclusion 69 2References 70 List of FiguresI would like to thank my supervisor Dr Kevin Curran for helping me with the research topic and for guiding me through every step of the research with great expertise and patience. Una McGinley, a librarian in the University of Ulster, kindly ordered newly published books in my field on my behalf thus helping me with my research. Finally, I am deeply grateful to my family for their strong support encouragement.
In order to obtain the scheme, the paths of multiple max-flows are worked out. Edges are divided into overlapped and normal type based on the merged max-flows. The transmitting data is represented using packets in a specific format. Multicast, forward and coding operations are defined to transmit data at the nodes. The nodes are classified according to the type of operations. A dynamic coding and routing algorithm is proposed to route packets gradually from source node to destinations in topological sorting order by the three operations on the path of merged max-flows. Based on simulation of random and real network benchmark topologies, it shows that network coding is necessary at a few nodes and links, the number of coding node and link is less than widely used rule and the result of evolutionary approach. Furthermore, it was proved that the use of simple xor operation could satisfy most of the network topologies. The running time of the algorithm presented here is less than one second for most of the benchmark and random data sets. In the past half century, information flow being transferred in the network was following a way similar to the highway transportation or the water pipe systems in the real life. Packets in the digital network or signals in the analogue network were transmitted independently under different transportation stream without overlap. However, unlike the cars or water in the world, the information could be recombined in the transport systems so that the path of different information could be overlapped. Network Coding (NC) is a recent research area in information theory [Ahl00]. It dramatically changes the traditional information processing and transportation style. For example, in the traditional computer networks, information packets are transmitted from the source through intermediate nodes by store-and-forward method. There is no extra processing except replication. With network coding, the operations such as xor or linear combinations between two or more different packets are allowed to join different information flows, and the original binary packet could be recombined or extracted later in the receivers. In the other words, data streams are not necessary to be kept independently in the communication networks. The classical butterfly network model is shown in Figure 1.. One source node S intends to send both packets a and b to the target node T1 and T2. For the traditional store and forward method demonstrated in Figure 1.(a), two channels are required between V3 and V4. By using the xor coding as shown in Figure 1.(b), the bandwidth between V3 and V4 is reduced to one channel. Node T1 receives packets a and a⊕b, and packet b could be obtained by a⊕(a⊕b). Similar packet a could be decoded at T2 with b and a⊕b. Hence, half of the bandwidth between V3 and V4 is saved. 
Butterfly Network Coding Scheme Another example of the wireless satellite multicast communication is shown in Figure 2.. Node S stands for the satellite, node V1 and V2 are two ground stations. V1 sends packet a to V2 through the satellite S and V2 sends packet b inversely. By traditional methods, four time units are required: V1 sends a to S; V2 sends b to S; S sends a to V2; S sends b to V1. If satellite broadcast a⊕b to both stations at the same time, each station could decode the other packet with the one it send. Thereby one time unit is saved. 
Network Coding on Wireless Network Communication Application With Network Coding, the theory max flow upper bound indicated by Shannon can be achieved. It was proved that applying Linear Network Coding might help to achieve the multicasting upper bound under one source multiple receivers’ situation [LiS03]. Linear Network Coding combines the coding and routing together from the physics layer and network layer respectively. Two problems need addressing in order to apply Network Coding in Multicasting: Establish the routing for transportation Adopt the coding pattern or code algorithm Some efficient methods have been proposed to resolve the second issue. Random Network Coding (RNC) is a distributed implementation and widely used in current research. Compared with other coding approaches, such as heuristic, exponential or polynomial algorithms, Random Network Coding has lower complexity and could be easily applied in real network systems. Little research has been done about the multicast routing issue and most efforts have concentrated to date on the theory aspect, such as demonstrating the feasibility of Network Coding theoretically or how to apply the coding on a specific network. However, the establishment of routing is a precondition of the network multicasting. In the traditional IP multicasting, the routing is set up through multicast Steiner Tree [Zos02]. The next sections are aimed at finding out feasible methods to determine the routing for network coding in multicast communications and construct the complete network coding scheme. Directory: dissertations dissertations -> Second Life on a Mobile Phone Nii Annan September 2011 Dissertation submitted in partial fulfilment for the degree of Master of Science in Information Technology Department of Computing Science and Mathematics University of Stirling dissertations -> Architectures for Controlling an Intelligent Autonomous Vehicle dissertations -> A historical audio and video guidebook for an Android smartphone/tablet John Reid September 2011 Dissertation submitted in partial fulfilment for the degree Download 1.23 Mb. Share with your friends:
|