Tối ưu hóa lưu trữ nội dung trong mạng ICN

Bài viết đã mô hình hóa việc lưu trữ nội dung thông qua bài toán Knapsack. Bài toán lữu trữ có hai mục tiêu: tối đa hóa lỉ lệ hit tại nút mạng hoặc tối thiểu lưu lượng nội dung trên đường truyền backhaul tương ứng với các bài toán max_hit hoặc min_transit. Từ giải thuật greedy giải bài toán quy hoạch tuyến tính xấp xỉ của bài toán Knapsack, bài viết đề xuất hai thuật toán loại bỏ nội dung đó là max_hit và min_transit. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Tối ưu hóa lưu trữ nội dung trong mạng ICN +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ(&,7 Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) TӔI ѬU HÓA LѬU TRӲ NӜI DUNG TRONG MҤNG ICN NguyӉn Quӕc Anh1, Võ Thӏ Lѭu Phѭѫng2, Lê Tuҩn Anh3 1 Khoa Công NghӋ Thông Tin, Hӑc viӋn Bѭu Chính ViӉn Thông, CN HCM 2 Khoa Công NghӋ Thông Tin, ĈH Quӕc TӃ, ĈHQG HCM 3 Khoa Công NghӋ Thông Tin, ĈH Thӫ Dҫu Mӝt Emails: nqa.it.dlu@gmail.com, vtlphuong@hcmiu.edu.vn, letuanh@tdmu.edu.vn Abstract—Ngày nay, viӋc sӱ dөng Internet ÿang chuyӇn tӯ ÿã ÿѭӧc ÿӅ xuҩt nhѭ: TRIAD [1], ROFL [2], DONA [3], viӋc truyӅn dӳ liӋu giӳa các máy tính ÿҫu cuӕi sang viӋc trao ÿәi PSIRP [4], CCN [5], COMET [6], CONVERGENCE [7], nӝi dung theo hѭӟng ngѭӡi dùng mӝt cách mҥnh mӁ. KiӃn trúc cӫa mҥng Information Centric Network (ICN) ra ÿӡi nhҵm ÿáp NDN [8], SAIL [9], PURSUIT [10], v.v. ӭng nhu cҫu này và nó ÿang là mӝt lƭnh vӵc nghiên cӭu sôi ÿӝng hiӋn nay trên thӃ giӟi. Trong kiӃn trúc ICN, các nӝi dung ÿѭӧc Lѭu trӳ nӝi dung (in-network caching) là mӝt chӭc năng lѭu trӳ tҥi các nút trung gian (in-network caching), do ÿó ngѭӡi quan trӑng trong kiӃn trúc ICN. Bҵng cách lѭu trӳ các nӝi dùng truy xuҩt nӝi dung tҥi các nút trung gian thay vì phҧi truy cұp ÿӃn máy chӫ gӕc ÿӅ tҧi nӝi dung. Do ÿó, chҩt lѭӧng cӫa viӋc dung phә biӃn trên các nút mҥng ICN gҫn ngѭӡi dùng, ngѭӡi truyӅn dӳ liӋu trong mҥng ICN sӁ cao hѫn. Bài toán tӕi ѭu lѭu trӳ các nӝi dung trên nút mҥng ICN sӁ ÿѭӧc nghiên cӭu trong bài dùng chӍ tҧi nӝi dung tҥi các nút mҥng ÿó thay vì phҧi truy xuҩt báo này. Chúng tôi sӁ ÿӅ xuҩt hai thuұt toán nhҵm tӕi ѭu hóa khҧ ÿӃn các máy chӫ gӕc. Khҧ năng lѭu trӳ cӫa các nút ICN là có năng lѭu trӳ cӫa ICN dӵa trên viӋc tӕi ÿa hóa tӍ lӋ hit và tӕi ѭu hóa lѭu lѭӧng dӳ liӋu trên ÿѭӡng truyӅn backhaul. Chúng tôi còn hҥn, do ÿó lѭu trӳ nӝi dung sao cho có hiӋu quҧ nhҩt là mӝt xây dӵng mӝt chѭѫng trình mô phӓng nhҵm hiӋn thӵc hóa thuұt toán ÿã ÿӅ xuҩt. Thông qua ÿó thӇ hiӋn rõ hiӋu quҧ ÿҥt ÿѭӧc cӫa chӫ ÿӅ nghiên cӭu quan trӑng [11, 12]. Hѫn nӳa viӋc triӇn khai thuұt toán. KӃt quҧ thu ÿѭӧc tӯ hai thuұt toán ÿӅ xuҩt sӁ so sánh vӟi nhӳng thuұt toán lѭu trӳ ÿang ÿѭӧc sӱ dөng hiӋn nay ÿó là cѫ chӃ lѭu trӳ nӝi dung cNJng sӁ mӣ ra khҧ năng phӕi hӧp trong LCE-LRU và LCE-LFU. viӋc tӕi ѭu ÿӏnh tuyӃn, chuyӇn tiӃp và quҧn lý lѭu trӳ nӝi dung Keywords —ICN, in-network caching, bài toán Knapsack. trong mҥng. Các nghiên cӭu gҫn ÿây ÿã chӍ ra rҵng các giҧi thuұt lѭu trӳ thông minh sӁ cҧi thiӋn hiӋu năng lѭu trӳ mӝt I. GIӞI THIӊU cách ÿáng kӇ [13][14][15]. Qua nhiӅu năm phát triӇn cùng vӟi cѫ sӣ hҥ tҫng toàn cҫu Internet phân phӕi mӝt lѭӧng lӟn thông tin cho hàng tӍ thiӃt bӏ Thuұt toán lѭu trӳ phә biӃn thѭӡng ÿѭӧc dùng cho ICN là kӃt nӕi. Hàng nghìn tӍ các trang web và exabytes nӝi dung ÿӵӧc chuyӇn hàng năm. Ngѭӡi dùng ngày càng hӭng thú hѫn leave-copy-everywhere (LCE) [16]. Mӝt bҧn sao cӫa mӛi nӝi vӟi viӋc nhұn nӝi dung tӭc thӡi tӯ mӝt nѫi lѭu trӳ nào ÿó hѫn dung ÿѭӧc yêu cҫu và chuyӇn tӟi ngѭӡi dùng sӁ ÿѭӧc nhân là viӋc truy cұp vào mӝt mӝt hӋ thӕng máy tính cө thӇ (host rӝng tҥi mӛi nút mҥng mà nӝi dung ÿó ÿi qua trên ÿѭӡng ÿӃn hoһc server). Tuy nhiên trên thӵc tӃ, Internet vүn dӵa vào mô hình giao tiӃp host-centric yêu cҫu ngѭӡi dùng phҧi chӍ ÿӏnh rõ vӟi ngѭӡi dùng. Khi nӝi dung yêu cҫu trùng khӟp tҥi nút mҥng không chӍ là thông tin muӕn nhұn, mà còn là ÿӏa chӍ ÿҫu cuӕi. cҩp l hoһc máy chӫ gӕc thì bҧn sao cӫa nӝi dung sӁ ÿѭӧc lѭu NӃu không có các chӭc năng add-on ÿѭӧc thêm vào thì cѫ chӃ trӳ tҥi tҩt cҧ các nút mҥng trung gian (cҩp l-1, …, 1) trên cӫa Internet không thӇ xác ÿӏnh và lҩy thông tin yêu cҫu tӯ nguӗn tӕi ѭu nhҩt, trӯ khi ngѭӡi dùng sӱ dөng mӝt cách thӭc ÿѭӡng trӣ vӅ cӫa nӝi dung. Phѭѫng pháp này sӁ gây ra sӵ dѭ nào ÿó ÿӇ xác ÿӏnh các vӏ trí tӕi ѭu khi lҩy nӝi dung cҫn thiӃt. thӯa và tiêu tӕn tài nguyên cӫa các nút mҥng. Bên cҥnh ÿó, các Do ÿó mà kiӃn trúc Information-Centric Networking (ICN) ra nút mҥng lѭu trӳ có thӇ sӱ dөng nhӳng thuұt toán loҥi bӓ nӝi ÿӡi là là mӝt ӭng cӱ viên ÿҫy hӭa hҽn thay cho kiӃn trúc dung không cҫn thiӃt khi lѭu trӳ nhѭ: least recently used (LRU) truyӅn thӕng cӫa Internet. ICN ÿang nhұn ÿѭӧc rҩt nhiӅu sӵ quan tâm cӫa giӟi nghiên cӭu gҫn ÿây. Mӝt sӕ kiӃn trúc ICN [17], least frequently used (LFU) [18]. Thuұt toán LRU ÿѭӧc  ISBN: 978-604-67-0635-9 18 Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJY ...