TWO-AGGREGATOR TOPOLOGY OPTIMIZATION USING MULTIPLE PATHS IN DATA CENTER NETWORKS

 

ABSTRACT

In this paper we focus on the problem of dataaggregation using two aggregators in a data center network,where the source racks are allowed to split their data and send tothe aggregators using multiple paths. We show that the problemof finding a topology that minimizes aggregation time is NP-hardfor k = 2, 3, 4, where k is the maximum degree of each ToR switch(number of uplinks in a top-of-rack switch) in the data center. Wealso show that the problem becomes solvable in polynomial timefor k = 5 and 6 and conjecture the same for k > 6. Experimentalresults show that, for k = 6, our topology optimization algorithmreduces the aggregation time by as much as 83.32% and reducestotal network traffic by as much as 99.5% relative to the torusheuristic, proposed in [1], which readily proves the significantimprovement in performance achieved by the proposed algorithm.

EXISTING SYSTEM:

This paper focuses on the two aggregator variant of theproblem addressed by us in, we haveexamined the single-aggregator network topology optimizationwith splitting (SANTOS) problem. Consequently, much of therelated-work section of has been reproduced here andwe have added in a summary of the new results obtained byus in .Multi-path data aggregation has been studied by manyresearchers in the past to seek better performance. Previouswork includes research by Rao et al.Xue et al.  aothers. Rao et al.  have worked on providing transmissiontime guarantees in sending a message of finite length andobtaining a threshold on the maximum time difference betweentwo out of order packets of a sequential message, transmittedat constant rate, from a source to a destination in a computernetwork. Xue [9] presents a polynomial time algorithmfor computing an optimal multi-path end-to-end routing totransmit a given message while the previously published pathbasedalgorithm for this problem is sub-optimal. However ourproblem TANTOS is markedly different from these, becauseTANTOS is defined on a data-center network, where thetopology is constrained by the maximum degree of each ToRswitch (k).

CONCLUSION

In this paper, we have explored the Two Aggregator NetworkTopology Optimization with Splitting (TANTOS) problem.We have proved that TANTOS is NP-hard for k = 2 usingreduction from the standard 2-way Partition problem, wherek is the maximum degree of a ToR switch in the data centernetwork. We have formulated a new problem called the 3-way Partition problem and showed it to be NP-hard usingreduction from the 2-way Partition problem. We have employedreduction from this newly formulated 3-way Partitionproblem to prove that TANTOS is NP-hard for k = 3. We haveproved that TANTOS is NP-hard for k = 4 using reductionfrom the standard 2-way Partition problem. For k = 5 andk = 6, we have proposed polynomial time algorithms to solveTANTOS optimally by exploring all possible instances of theproblem. Based on our observations in k = 5 and 6, we haveconjectured that TANTOS is polynomially solvable for k > 6.Through extensive experiments, we illustrated the improvedperformance by our optimal algorithm for k = 6 compared toa 3D extension of the 2D torus heuristic proposed by Wang etal. in [1]. Our algorithm reduced the data aggregation time andtotal network traffic by up to 83:32% and 99:5%, respectivelyrelative to Wang’s heuristic.

REFERENCES

[1] G. Wang , T.S. Eugene Ng , A. Shaikh, ”Programming your network atrun-time for big data applications”, Proceedings of the first workshopon Hot topics in software defined networks (HotSDN), 2012.

[2] S. Das, S. Sahni, ”Network Topology Optimization for Data Aggregation”,IEEE/ACM International Symposium on Cluster, Cloud, andGrid Computing (CCGrid), 2014, pp 493-501.[3] S. Das, S. Sahni, ”Network topology optimization for data aggregationwith splitting”, IEEE International Symposium on Signal Processingand Information Technology (ISSPIT), 2014, pp 398-403.

[4] S. Das, S. Sahni, ”Network topology optimisation for data aggregationusing multiple paths”, International Journal on Metaheuristics, 2015, pp115-140.

[5] S. Das, S. Sahni, ”Two-aggregator network topology optimization withsplitting”, IEEE Symposium on Computers and Communication (ISCC),2015, pp 683-688.

[6] R. L. Graham, ”Bounds on Multiprocessing Timing Anomalies”, SIAMJOURNAL ON APPLIED MATHEMATICS, 1969, Volume 17, Number2, pp 416-429.

[7] E. G. Coffman Jr., R. Sethi, ”A generalized bound on LPT sequencing”,Proceedings of ACM SIGMETRICS conference on Computer performancemodeling measurement and evaluation, 1976.

[8] N. S. V. Rao, S. G. Batsell, ”QoS Routing via multiple paths usingbandwidth reservation”, Proceedings of the IEEE INFOCOM, 1998, pp11-18.[9] G. Xue, ”Optimal multi-path end-to-end data transmission in networks”,Proceedings of ISCC, 2000, pp. 581-586.[10] A. Hammadi, L. Mhamdi, ”A survey on architectures and energyefficiency in data center networks”, Computer Communications, 2014,vol. 40, no. 0, pp. 1 21.

[11] D. Kliazovich, P. Bouvry, Y. Audzevich, S. Khan, ”Greencloud: apacket-level simulator of energy-aware cloud computing data centers”,Global Telecommunications Conference (GLOBECOM), 2010, pp. 1-5.

[12] Y. Chen, R. Griffith, J. Liu, R.H. Katz, A.D. Joseph, ”Understanding tcpincast throughput collapse in datacenter networks”, Proceedings of the1st ACM Workshop on Research on Enterprise Networking, WREN,2009, pp. 73-82.