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

Lianlong Wu, K Curran

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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
LanguageEnglish
Pages373-396
JournalInternational Journal of Network Management
Volume22
Issue number4
DOIs
Publication statusPublished - 3 Sep 2012

Fingerprint

Network routing
Network coding
Information theory
Routing algorithms
Sorting
Topology

Cite this

@article{c84957f685064a6888d439b86793e491,
title = "A Practical Network Coding and Routing Scheme based on Maximum Flow Combination",
abstract = "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",
author = "Lianlong Wu and K Curran",
year = "2012",
month = "9",
day = "3",
doi = "10.1002/nem.1797",
language = "English",
volume = "22",
pages = "373--396",
journal = "International Journal of Network Management",
issn = "1055-7148",
number = "4",

}

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 journalArticle

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 -