Network coding resources optimization with transmission delay constraint in multicast networks①

Qu Zhijian (曲志堅)

*, Fu Jia**, Liu Xiaohong*, Li Caihong*(*School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, P.R.China)

Network coding resources optimization with transmission delay constraint in multicast networks①

Qu Zhijian (曲志堅)②

*, Fu Jia**, Liu Xiaohong*, Li Caihong*(*School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, P.R.China)

(**School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, P.R.China)

Minimizing network coding resources of multicast networks, such as the number of coding nodes or links, has been proved to be NP-hard, and taking propagation delay into account makes the problem more complicated. To resolve this optimal problem, an integer encoding routing-based genetic algorithm (REGA) is presented to map the optimization problem into a genetic algorithm (GA) framework. Moreover, to speed up the search process of the algorithm, an efficient local search procedure which can reduce the searching space size is designed for searching the feasible solution. Compared with the binary link state encoding representation genetic algorithm (BLSGA), the chromosome length of REGA is shorter and just depends on the number of sinks. Simulation results show the advantages of the algorithm in terms of getting the optimal solution and algorithmic convergence speed.

network coding, genetic algorithm (GA), search space, multicast network

0 Introduction

Network coding provides numerous advantages over store-and-forward based routing solution[1]. In network coding research community, the network coding operations are always assumed that it has to be conducted in all coding-possible nodes to achieve the required throughput. However, it is usually the case that network coding is required only at a subset of the coding-possible nodes[2]. For example, a source node s wishes to transmit multicast messages to all of the destinations at the multicast rate of two. In order to guarantee the required multicast rate, a multicast tree may contains one to three coding nodes according to different multicast tree establishing algorithm. The problem of determining such a minimum coding nodes subset has been proved to be NP-hard[3].

Many scholars have concentrated on this problem and worked for minimizing the number of coding nodes or links. For example, Wang, et al.[4]modified the ant colony algorithm to optimize network coding resources, and Xing, et al.[5-7]proposed some evolutionary algorithms. Qu, et al.[8]proposed an adaptive quantum-inspired evolutionary algorithm based on Hamming distance to optimize the network coding resources in multicast networks. However, their work did not take delay or delay difference constraints into account.

Obviously, network coding will lead to increase the transmission delay and the computational overhead when combining packets in intermediate nodes[9]. To solve this problem, Wu, et al.[10]developed a joint coding and feedback scheme to improve the throughput and reliability in wireless multicast. The results showed that the delay, encoding, and decoding complexities were low even for a large number of receivers. To reduce the packets delay and minimize packet dropping probability, Yu, et al.[11]considered multiple transmission methods and integrated packet scheduling with adaptive network coding method selection, and presented a dynamic coding-aware routing metric, which could increase potential coding opportunities. Those literatures above show the necessity of researching on network coding with delay needs.

In real-time interactive applications, the efficiency of the message transmission and the fairness among receivers should be considered as a must one. The network coding resource optimization problems under the restriction of the end-to-end delay and the delay difference among the source-destination paths (see Ref.[12] for details) will be considered. The investigation of combining network coding resource optimization with delay needs can render realistic significance.

1 Problem formulation

The illustration of transmission delay constraints in network coding based multicast network is shown as follows: Considering the same network scenarios in Fig.1(a), where each link has a unit capacity and source s expects to send data at rate of 2 units to the sink t1, t2, t3, and t4, respectively. The transmission delay for each link is labeled in Fig.1 and both the coding and decoding time is assumed to be 1. Note that the coding-waited time and decoding-waited time should also be highly considered.

Figs1(a), (b), (c), and (d) are 4 kinds of data transmission schemes with different amount of coding nodes. Note that the delay from source s to the sinks just depends on the path with maximum delay among all the source-destination paths. Namely, the original information cannot be recovered until all necessary messages received by a sink are collected. For example, the delays of two paths from s to sink t1are 3 and 10, respectively in Fig.1. Hence, the practical delay between s and sink t1is 10 and the inter-destination delay difference is 20 which is the difference between 30 and 10. Here, the concept of delay difference is defined as follows:

Fig.1 Network coding sub-graph with different coding nodes and path delay property

Delay Difference: The maximum sink delay subtracts the minimum sink delay.

For example, in Table 1, the maximum sink delay is 30 (t3), the minimum sink delay is 10 (t1), thus the delay difference of the multicast scenario is 20. So a triple (1, 30, 20) is got, here the first represents the coding node number, the second represents the maximum sink delay, and the third represents the delay difference of the given multicast scenario.

Table 1 The path from s to each sink with end-to-end delay and inter-destination delay difference for Fig.1(b)

SourceSinkPathsPathdelayDelaydifferencest1t2t3t4s-1-3-t1;s-2-4-c1-10-t1s-1-3-c1-7-t2s-2-4-c2-8-t2s-1-5-c2-8-t3s-2-6-c3-9-t3s-1-5-c3-9-t4s-2-6-t4310615203025320

The triples of
Figs1(b)～(d) are (1, 30, 20), (1, 24, 14), and (1, 24, 15). It is easy to understand that, even though the number of coding nodes is the same, the performance of delay is quite different in different transmission scenarios. If the maximum end-to-end delay and delay difference bounds are confirmed, the feasible transmission scenarios will be determined. This is a very important problem, but the algorithm proposed by Kim, et al. and Xing, et al. just dedicated their efforts to minimize coding nodes/links without considering the delay requirements. So their coding sub-graph may contain paths severely violating the delay constraints, which deteriorates the benefits that network coding is characterized to a certain extent.

2 Mathematic model

The problem is to find the minimal set of coding links where the network coding scenario is required to 1) achieve multicast rate r, 2) meet the end-to-end delay requirements, and 3) meet the inter-destination delay difference constraints. The given multicast network is represented by a directed acyclic graph G = (V, E), where V denotes the set of vertices and E is the set of edges. The capacity of each edge e∈E is unit, and if there has an edge exceeding unit capacity, it is represented by multiple unit edges. The multicast problem is considered with one source s∈V and a sink set T?V-{s}, a link delay function d:E→R+, delay tolerance Θ, delay difference Ω , and the rate r. Here rate r is an integer and it can be achievable if a transmission scheme can guarantee all |T| sinks receiving packets from the source at least rate r. More specifically, to achieve rate r, there should be at least r link-disjoint paths to each sink subject to:

(1)

where Pi(s,vk) denotes the i-th path from source s to the k-th sink vk.This multicast problem can be converted into a multi-objective optimization problem, and stated mathematically as

Minimize:

(2)

where c represents the amount of coding links employed in network coding.

Subject to:

min{R(s,vi)|vi∈T, i=1,2,…,|T|}≥r

(3)

(4)

(5)

xi∈{0, 1} i=1,2,…,n

(6)

where symbol x including n elements, denotes the output links of an intermediate node with multiple input links. If xi=1, it means that the i-th output link must be linearly coded; otherwise, it means that no coding operation is required over this link. Here the concept of merging node is presented.

Merging Node: The intermediate nodes which have multiple input links are called merging nodes.

All the output links of a merging node are named as potential coding links.

Fig.2 An example of determining the output link states of a merging node

In Eq.(3), R(s,vi) represents the rate from source s to sink viunder the current multicast tree. To achieve the desired multicast rate r, the minimum R(s,vi) among all the sinks should observe Eq.(3). Namely, for each sink, at least r link-disjoint paths from source to each one must be guaranteed. Eqs(4) and (5) are referred to as source-destination delay constraint and inter-destination delay difference constraint, respectively. The end-to-end delay for sink viactually depends on the one that has the maximum delay among r link-disjoint paths and is calculated by δvi(i=1,2,…,|D|; vi∈D) for each sink vi, which is defined as

(7)

here Pj(s,vi) means the j-th path from s to sink vi. After computing the end-to-end delay of each sink, the inter-destination delay variation can be obtained by Eq.(5). Therefore, the objective is to minimize Eq.(2) subjected to Eqs(3), (4), (5) and (6). Note that in Eqs(4) and (5), the coding-waited time is not considered, which will be explained and calculated in the following REGA.

3 Solutions

A routing-based encoding representation approach[13]is employed to map the optimization problem to a GA framework. The given multicast topology is decomposed to a secondary graph (see more details in the Ref.[8]), and then the path array Pi(i=1,2,…,|T|) which contains all paths from s to each sink tisubject to Eq.(4) is gotten. For the i-th path array Pi, all possible combinations are selected each of which consists of r link-disjoint paths. If the number of the selected combinations is mi, the combinations are numbered sequentially from 1 to mi, and then Piis updated by micombinations. Therefore, array Piconsists of r·mipaths. Table 2 shows all possible r link-disjoint paths in array Pi.

Table 2 Array Piincludes all possible r link-disjoint paths

Fig.3 Integer encoding representation

An integer encoding routing-based genetic algorithm (REGA) is presented to search the optimal solution. The flowchart of REGA is shown in Fig.4.

The algorithm starts from an initial population Qpopcontaining k chromosomes. The fitness function is given in Eq.(8), where α is the number of coding links, λ and β are constants, dnis the number of source-destination paths, dvdenotes the maximum inter-destination delay variation and p(dv, Ω) is a penalty function which is defined in Eq.(9).

(8)

(9)

When performing the algorithm, the fittest chromosome is directly copied into the new population. This elitism strategy shows great improvement for the algorithmic performance in our simulation. Roulette selection and single crossover are carried out and followed by a random mutation which helps escaping from the local optimal. Moreover, it is widely demonstrated that the infeasible chromosomes also help population evolve rapidly. Hence, according to the level of violation, different scale penalties are imposed on the infeasible solutions while determining their fitness, which speed up search from not only feasible domain but also infeasible domain.

Fig.4 The flowchart of REGA

4 Simulation and analysis

To evaluate the performance of REGA, comparisons have been carried out with BLSGA[3]over the 2 fixed multicast networks and 1 random multicast network. The 2 fixed networks are 3-copy and 7-copy networks which have been used in Ref.[3]. Fig.5 illustrates an example of n-copy network, where Fig.5(a) is the original network and Fig.5(b) is a 3-copy network constructed by cascading 3 copies of the original network. For the n-copy network, the source node is at the top, and the sinks are at the bottom. According to Fig.5, it is known that the n-copy network contains n+1 sinks.

Fig.5 Illustration the n-copy network

The parameters of the 3 test networks shown in Table 3.

Table 3 Network parameters

The parameters for REGA are set as following: delay∈(0,1] with arbitrary unit which is uniformly distributed, crossover operator pc=0.8, mutation operator pm=0.1, and λ=10, β=100. In addition, the size of population (Popsize) and the number of iteration (NI) shown in following result tables vary with the size of solution space. Moreover, all simulations are run on a Windows XP computer with Intel(R) Core(TM) 2 Quad CPU, 2.40GHz, 3.25G RAM

With regard to BLSGA, note that it is developed for a non-delay-constrained network coding resource optimization problem. Hence to provide an apple-to-apple comparison, some adjustments for BLSGA should be enforced to introduce link delay. For each individual in the population, it represents a multicast tree which is checked whether the current transmission scheme can guarantee the given multicast rate achievable. If the rate can be achieved, Ford-Fulkson algorithm is used to compute the end-to-end paths for each sink, and then the end-to-end delay for each source-destination path can be calculated. Correspondingly, the inter-destination delay variation is obtained. Due to the introduction of delay requirements, fitness function has to be adjusted and re-defined as

(10)

where nmaxis the number of potential coding links. The definition of dnand p(dv, Ω) is identical with that of REGA and β=100. If anyone of the constraints Eqs(3), (4), and (5) is violated, chromosome y is infeasible and corresponding penalty is added in the process of fitness evaluation.

Before comparing the searching result under the delay restriction, the convergence speed of the 2 algorithms are tested firstly. Table 4 and Table 5 list the algorithmic parameters used in this test. Fig.6 and Fig.7 show the convergence speed over 15-copy and 31-copy networks. The index called mean network coding operation times (MNCO) is employed in the simulation, and it is defined as Eq.(11). Here ntrialsindicates the times of algorithmic trial and t is the number of evolutionary generation. b(t,i) denotes the best fitness (namely, the number of minimal coding links) so far when the population evolves to the t-th generation in the i-th trial. In the simulation ntrials=30.

Table 4 Algorithmic parameters of REGA

Table 5 Algorithmic parameters of BLSGA

(11)

In Fig.6 only 13 generation evolutions are required to hit the best solution. However, in order to get a best solution, BLSGA needs a huge population 150 and a big evolutionary generation 1000. From Fig.7, it can be seen that even using such prominent parameters, however, the performance is still worse than that of REGA. It is clear that the convergence speed of REGA is better, especially in the larger multicast networks (such as 31-copy network). The result provides a solid demonstration about the efficiency of REGA.

Fig.6 Convergence speed of REGA

Moreover, the simulation results about searching for the best solution under the delay restriction are shown in Table 6, Table 7, Table 8. The numeric results in a row in parentheses indicate coding number (CN), maximum end-to-end delay (MD), maximum delay difference (MDD), computational time (CT, the unit is second), Popsize, and NI, respectively. Therefor the numbers in the brackets from Table 6 to Table 8 indicate the numerical result of (CN, MD, MDD, CT, Popsize, NI) respectively. Actually, each algorithm in tables has been run for 30 times, and the best result among those 30 trials is chosen.

From the numerical results it can be known that BLSGA even cannot find a satisfied solution. Several reasons may be responsible for this. First, due to the binary link state representation in BLSGA, the size of solution space is too large to handle, especially in such strict constraints. Thereby an increment for BLSGA on both Popsize and NI has to be imposed to promote the search ability, which extremely enhance CT. Besides, according to the chromosome encoding principle, the length of the string in REGA just depends on the number of sinks and is evidently much shorter than that of BLSGA, which can reduce the computing complexity and speed up the algorithm operation. On the other hand, compared with the constitution of solution space of REGA, BLSGA search space has too many infeasible solutions while in REGA only the solutions subject to Eqs(3) and (4) can be covered.

Table 6 Numerical results of 3-copy network

Table 7 Numerical results 7 copy network

Table 8 Numerical results of random network

Moreover, the simulation results also indicate that the coding numbers will be influenced by different delay constraints in a same multicast network. When the QoS level becomes severer, the encoding cost will increase, hence it should play a trade-off between the encoding cost and delay constraints. As for the performance of the algorithms, thanks to the RE and some excellent evolutionary schemes, such as fitness penalty and elitism strategy, REGA outperforms significantly over the BLSGA in terms of the ability to get a satisfied solution and the computational time.

5 Conclusions

In this study, the problem of minimizing the coding cost with required data rate and delay constraints in network coding based multicast networks is studied. An algorithm named REGA, has been proposed to address this problem. In REGA, an efficient and problem-specific local search scheme is designed to help the algorithm to obtain the optimality more quickly. Then it is demonstrated that even under the severe delay constraints, the proposed REGA can still render a feasible solution for real application in such coding resources optimization area. The distinguished suboptimal solutions obtained by REGA prove the capability and efficiency of the utility in this field.

[1] Ahlswede R, Cai N, Li S, et al. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216

[2] Minkyu K, Varun A, Una-May O, et al. Genetic representations for evolutionary minimization of network coding resources. Computer Science, 2007, 4448:21-31

[3] Minkyu K, Médard, Aggarwal V, et al. Evolutionary approaches to minimize network coding resources. In: Proceedings of the 26th IEEE International Conference on Computer Communications, Anchorage, USA, 2007. 1991-1999

[4] Wang Z, Xing H, Li T, et al. A modified ant colony optimization algorithm for network coding resource minimization. IEEE Transactions on Evolutionary Computation, 2016, 20(3): 325-342

[5] Xing H, Qu R, Bai L, et al. On minimizing coding operations in network coding based multicast: an evolutionary algorithm. Applied Intelligence, 2014, 41(3): 820-836

[6] Xing H, Qu R. A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems. Information Sciences, 2013, 233(6): 36-53

[7] Xing H, Qu R, Kendall G, et al. A path-oriented encoding evolutionary algorithm for network coding resource minimization. Journal of the Operational Research Society, 2014, 65(8): 1261-1277

[8] Qu Z, Liu X, Zhang X, et al. Hamming-distance-based adaptive quantum-inspired evolutionary algorithm for network coding resources optimization. The Journal of China Universities of Posts and Telecommunications, 2015, 22(3): 92-99

[9] Keshavarz-Haddad A, Riedi R. Bounds on the benefit of network coding for wireless multicast and unicast. IEEE Transactions on Mobile Computing, 2014, 13(1), 102-115

[10] Wu F, Sun Y, Yang Y, et al. Constant-delay and constant-feedback moving window network coding for wireless multicast: design and asymptotic analysis. IEEE Journal on Selected Areas in Communications, 2015, 33(2): 127-140

[11] Yu Y, Peng Y, Li X, et al. Distributed packet-aware routing scheme based on dynamic network coding. China Communications, 2016, 13(10): 20-28

[12] Rouskas G, Baldine I. Multicasting routing with end-to-end delay and delay variation constraints. In: Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies, Networking the Next Generation, San Francisco, USA, 1996. 353-360

[13] Hadj-Alouane A, Bean J. A genetic algorithm for the multiple-choice integer program. Operations Research, 1997, 45(1): 92-101

Qu Zhijian, born in 1980. He received his Ph.D degrees in Information and Communication Engineering Department of Beijing University of Posts and Telecommunications in 2011. He is currently an associate professor in the School of Computer Science and Technology, Shandong University of Technology. His research interests include network coding, intelligence algorithm, and optical multicast.

10.3772/j.issn.1006-6748.2017.01.005

①Supported by the National Natural Science Foundation of China (No. 61473179), Shandong Province Higher Educational Science and Technology Program (No. J16LN20), Natural Science Foundation of Shandong Province (No. ZR2016FM18) and the Youth Scholars Development Program of Shandong University of Technology.

②To whom correspondence should be addressed. E-mail: zhijianqu@sdut.edu.cn Received on Feb. 22， 2016