A Practical Network Coding and Routing Scheme based on Maximum Flow Combination

Network coding is a novel field of information theory and coding theory. It is a breakthrough over the traditional store-and-forward routing methods by allowing coding of two or more packets together. From an information flow aspect, multiple flows could be overlapped in a routing scheme. Hence the theoretical upper bound of multicast capacity could be achieved by network coding. In this project, a complete routing and coding scheme is constructed to realize the maximum multicast transportation task. In order to implement the scheme, the paths of multiple max-flows are determined. Edges are divided into overlapped and normal type based on the merged max-flows. The transmitting data are 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 operation. 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. We show that the use of simple XOR operations can satisfy most of the network topologies. The running time of the algorithm presented here is less than 1 second for most of the benchmark and random datasets