Abstract
Language | English |
---|---|
Pages | 373-396 |
Journal | International Journal of Network Management |
Volume | 22 |
Issue number | 4 |
DOIs | |
Publication status | Published - 3 Sep 2012 |
Fingerprint
Cite this
}
A Practical Network Coding and Routing Scheme based on Maximum Flow Combination. / Wu, Lianlong; Curran, K.
In: International Journal of Network Management, Vol. 22, No. 4, 03.09.2012, p. 373-396.Research output: Contribution to journal › Article
TY - JOUR
T1 - A Practical Network Coding and Routing Scheme based on Maximum Flow Combination
AU - Wu, Lianlong
AU - Curran, K
PY - 2012/9/3
Y1 - 2012/9/3
N2 - 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
AB - 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
U2 - 10.1002/nem.1797
DO - 10.1002/nem.1797
M3 - Article
VL - 22
SP - 373
EP - 396
JO - International Journal of Network Management
T2 - International Journal of Network Management
JF - International Journal of Network Management
SN - 1055-7148
IS - 4
ER -