Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các kết quả không thể xấp xỉ và thuật toán không tối ưu cho việc đặt bộ nhớ cache tối thiểu thời gian trễ trong các mạng trường học với các bộ định tuyến theo nội dung
Tóm tắt
Chúng tôi xem xét vấn đề đặt bộ nhớ cache trong các mạng trường học, nơi các bộ định tuyến có khả năng bộ nhớ cache không đồng nhất và mục tiêu là giảm thiểu tổng thời gian trễ của tất cả các yêu cầu. Chúng tôi chứng minh rằng vấn đề này là NP-khoảng trong việc xấp xỉ với bất kỳ yếu tố nào nhỏ hơn $$n/m^{\epsilon }+\hbox{poly}(m)$$, trong đó n là số lượng bộ định tuyến, m là số nội dung, $$\epsilon$$ là hằng số dương cố định bất kỳ và $$\hbox{poly}(m)$$ là bất kỳ hàm đa thức nào của m. Chúng tôi đề xuất các thuật toán chính xác (thời gian exponential) dựa trên lập trình tuyến tính nguyên và đề xuất các kỹ thuật để phân rã mạng lưới và loại bỏ các biến dư thừa nhằm tăng tốc độ tính toán. Bằng cách nới lỏng các chương trình lập trình tuyến tính nguyên, chúng tôi cũng đề xuất ba thuật toán heuristic (thời gian đa thức). Kết quả số cho thấy rằng các thuật toán đề xuất cho thời gian trễ ngắn hơn so với các thuật toán quyết định bộ nhớ cache hiện có cho các mạng dựa trên nội dung.
Từ khóa
#bộ nhớ cache #mạng trường học #bộ định tuyến theo nội dung #lập trình tuyến tính nguyên #thuật toán heuristic #thời gian trễTài liệu tham khảo
Cisco, Vni global fixed and mobile internet traffic forecasts. http://www.cisco.com. Accessed 16 July 2018
Xylomenos G, Ververidis CN, Siris VA, Fotiou N, Tsilopoulos C, Vasilakos X, Katsaros KV, Polyzos GC (2014) A survey of information-centric networking research. IEEE Commun Surv Tutor 16(2):1024–1049
Jacobson V, Smetters DK, Thornton JD, Plass MF, Briggs N, Braynard R (2012) Networking named content. Commun ACM 55(1):117–124
Amokrane A, Langar R, Boutaba R, Pujolle G (2015) Flow-based management for energy efficient campus networks. IEEE Trans Netwo Serv Manag 12(4):565–579
Poularakis K, Tassiulas L (2016) On the complexity of optimal content placement in hierarchical caching networks. IEEE Trans Commun 64(5):2092–2103
Josilo S, Pacifici V, Dan G (2017) Distributed algorithms for content placement in hierarchical cache networks. Comput Netw 125:160–171
Ming Z, Xu M, Wang D (2012) Age-based cooperative caching in information-centric networks. In: Proceedings of INFOCOM WKSHPS’12
Psaras I, Chai WK, Pavlou G (2012) Probabilistic in-network caching for information-centric networks. In: Proceedings of ICN’12
Chai WK, He D, Psaras I, Pavlou G (2013) Cache less for more in information-centric networks (extended version). Comput Commun 36(7):758–770
Psaras I, Chai WK, Pavlou G (2014) In-network cache management and resource allocation for information-centric networks. IEEE Trans Parallel Distrib Syst 25(11):2920–2931
Laoutaris N, Che H, Stavrakakis I (2006) The LCD interconnection of LRU caches and its analysis. Perform Eval 63(7):609–634
Abdullahi I, Arif S, Hassan S (2015) Survey on caching approaches in information centric networking. J Netw Comput Appl 56(C):48–59
Che H, Tung Y, Wang Z (2002) Hierarchical web caching systems: modeling, design and experimental results. IEEE J Sel Areas Commun 20(7):1305–1314
Karamchandani N, Niesen U, Maddah-Ali MA, Diggavi SN (2016) Hierarchical coded caching. IEEE Trans Inf Theory 62(6):3212–3229
Sun Y, Fayaz SK, Guo Y, Sekar V, Jin Y, Kâafar MA, Uhlig S (2014) Trace-driven analysis of ICN caching algorithms on video-on-demand workloads. In: Proceedings of CoNEXT’10
Tyson G, Kaune S, Miles S, El-khatib Y, Mauthe A, Taweel A (2012) A trace-driven analysis of caching in content-centric networks. In: Proceedings of ICCCN’12
Rossi D, Rossini G (2012) On sizing CCN content stores by exploiting topological information. In: Proceedings of INFOCOM WKSHPS’12
Xu Y, Li Y, Lin T, Wang Z, Niu W, Tang H, Ci S (2014) A novel cache size optimization scheme based on manifold learning in content centric networking. J Netw Comput Appl 37:273–281
Wang Y, Li Z, Tyson G, Uhlig S, Xie G (2016) Design and evaluation of the optimal cache allocation for content-centric networking. IEEE Trans Comput 65(1):95–107
Abani N, Braun T, Gerla M (2017) Proactive caching with mobility prediction under uncertainty in information-centric networks. In: Proceedings of ICN
Zhang M, Luo H, Zhang H (2015) A survey of caching mechanisms in information-centric networking. IEEE Commun Surv Tutor 17(3):1473–1499
Seetharam A (2017) On caching and routing in information-centric networks. IEEE Commun Mag 99:1–6
Shen M, Chen B, Zhu X, Zhao Y (2016) Towards optimal cache decision for campus networks with content-centric network routers. In: Proceedings of ISCC’16
McKeown N, Anderson T, Balakrishnan H, Parulkar GM, Peterson LL, Rexford J, Shenker S, Turner JS (2008) Openflow: enabling innovation in campus networks. Comput Commun Rev 38(2):69–74
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., San Francisco
Zhu X, Li Q, Mao W, Chen G (2014) Online vector scheduling and generalized load balancing. J Parallel Distrib Comput 74(4):2304–2309
lp solve. http://lpsolve.sourceforge.net/5.5/. Accessed 7 Jan 2016