1. Trang Chủ
  2. Kĩ thuật Viễn thông
  3. Tối ưu hóa lưu trữ nội dung trong mạng ICN

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! +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj

Thể loại Tài liệu miễn phí Kĩ thuật Viễn thông

Số trang 6

Ngày tạo 4/8/2023 3:54:27 AM +00:00

Loại tệp PDF

Kích thước 0.36 M

Tên tệp

Tải Tối ưu hóa lưu trữ nội dung trong mạng ICN (.pdf)

Xem mẫu

  1. +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
  2. 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
  3. 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{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
  4. sӱ dөng rӝng rãi ÿӇ thay thӃ nӝi dung tҥi các nút mҥng. Khi Gӑi ݀௠ là yêu cҫu cӫa ngѭӡi dùng cho nӝi dung thӭ ݉ mӝt nӝi dung mӟi cҫn ÿѭӧc lѭu trӳ, nút mҥng sӁ thay thӃ nӝi trong khoҧng thӡi gian ÿang xét. Khi ngѭӡi dùng gӱi yêu cҫu dung ít ÿѭӧc yêu cҫu gҫn ÿây nhҩt bҵng nӝi dung mӟi. Trong vӅ nӝi dung ݉ tӟi nút mҥng, nӃu nhѭ nӝi dung ݉ ÿã ÿѭӧc lѭu thuұt toán này viӋc tìm kiӃm và thay thӃ ÿѭӧc thӵc hiӋn liên trӳ tҥi nút mҥng này trѭӟc ÿó thì nó sӁ ÿѭӧc gӱi trҧ vӅ cho tөc. Trong khi ÿó, thuұt toán LFU tҥo ra bӝ ÿӃm cho mӛi nӝi ngѭӡi dùng. Ngѭӧc lҥi, nӝi dung ݉ sӁ ÿѭӧc tҧi vӅ tӯ mӝt nút dung ÿang ÿѭӧc lѭu trӳ. Giá trӏ cӫa bӝ ÿӃm này tăng lên nӃu cha vӟi chi phí là ܿ௠ cho mӛi ÿѫn vӏ nӝi dung. nӝi dung ÿѭӧc yêu cҫu. Khi cҫn lѭu trӳ mӝt nӝi dung mӟi, nút Dӵa vào nhu cҫu cӫa ngѭӡi dùng, chúng tôi ÿѭa ra hai mҥng sӁ loҥi bӓ nӝi dung ÿѭӧc yêu cҫu ít nhҩt (có giá trӏ bӝ mөc tiêu chính cҫn phҧi tӕi ѭu hóa trong vҩn ÿӅ lѭu trӳ nӝi ÿӃm nhӓ nhҩt). Tuy nhiên viӋc triӇn khai lҥi tӕn kém bӣi vì dung vӟi các ràng buӝc ÿã trình bày: 1) Tӕi ÿa hóa tӍ lӋ hit tҥi thuұt toán không hӛ trӧ viӋc tìm kiӃm và thay thӃ liên tөc trong nút lѭu trӳ, 2) Tӕi ѭu hóa lѭu lѭӧng nӝi dung tҧi xuӕng tӯ các mӝt khoҧng thӡi gian. cөm nút cha. ĈӇ thӵc hiӋn mөc tiêu ÿҫu tiên, cҫn tӕi ÿa hóa Trong bài báo này chúng tôi mô hình hóa viӋc lѭu trӳ nӝi biӇu thӭc σ௠‫א‬ெ ݀௠ ‫ݔ‬௠ . dung thông qua bài toán Knapsack [19]. Bài toán lѭu trӳ có hai mөc tiêu: tӕi ÿa hóa tӍ lӋ hit tҥi nút mҥng hoһc tӕi thiӇu lѭu Bài toán tӕi ÿa hoá sӕ lѭӧng hit ÿѭӧc mô tҧ nhѭ sau: 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 (max_hit) bài toán quy hoҥch tuyӃn tính xҩp xӍ cӫa bài toán Knapsack, ƒšǤ ෍ ݀௠ ‫ݔ‬௠  chúng tôi ÿӅ xuҩt hai thuұt toán loҥi bӓ nӝi dung, ÿó là max_hit ௠‫א‬ெ và min_transit. •–Ǥ ෍ ‫ݏ‬௠ ‫ݔ‬௠ ൑ ܵǡ ௠‫א‬ெ Mӝt chѭѫng trình mô phӓng ÿѭӧc chúng tôi xây dӵng ÿӇ ‫ א ݔ‬ሼͲǡͳሽǤ so sánh các thuұt toán ÿѭӧc ÿӅ xuҩt vӟi các thuұt toán truyӅn Vӟi mөc tiêu thӭ hai, ÿӇ tӕi ѭu hóa lѭu lѭӧng nӝi dung thӕng khác nhѭ leave-copy-everywhere vӟi LRU hoһc LFU giӳa nút lѭu trӳ ÿang xét và cөm nút cha thì ta cҫn tӕi thiӇu (LCE+LRU, LCE+LFU). KӃt quҧ thu ÿѭӧc cho thҩy thuұt toán biӇu thӭc σ௠‫א‬ெ ݀௠ ‫ݏ‬௠ ܿ௠ ሺͳ െ ‫ݔ‬௠ ሻ. ĈiӅu này tѭѫng ÿѭѫng vӟi mà chúng tôi ÿӅ xuҩt hoҥt ÿӝng tӕt hѫn so vӟi các thuұt toán viӋc tӕi ÿa hóa biӇu thӭc σ௠‫א‬ெ ݀௠ ‫ݏ‬௠ ܿ௠ ‫ݔ‬௠ . truyӅn thӕng trong cùng ÿiӅu kiӋn so sánh. Phҫn còn lҥi cӫa bài báo ÿѭӧc tә chӭc nhѭ sau: Phҫn II Do ÿó mөc tiêu tӕi thiӇu hóa lѭu lѭӧng nӝi dung ÿѭӧc thӇ hiӋn qua bài toán sau: giӟi thiӋu chung vӅ mô hình tӕi ѭu hóa cӫa thuұt toán lѭu trӳ. Phҫn III mô tҧ cө thӇ thuұt toán lѭu trӳ ÿã ÿӅ xuҩt. KӃt quҧ mô (min_transit) phӓng ÿѭӧc trình bày trong phҫn IV và phҫn V là phҫn kӃt ƒšǤ ෍ ݀௠ ‫ݏ‬௠ ܿ௠ ‫ݔ‬௠  ௠‫א‬ெ luұn. •–Ǥ ෍ ‫ݏ‬௠ ‫ݔ‬௠ ൑ ܵǡ ௠‫א‬ெ II. Ĉӄ XUҨT GIҦI THUҰT LѬU TRӲ ‫ א ݔ‬ሼͲǡͳሽǤ Xét mӝt tұp hӧp ‫ ܯ‬bao gӗm các nӝi dung ÿѭӧc lѭu trӳ tҥi III. PHÂN TÍCH GIҦI THUҰT mӝt nút mҥng ÿѫn có khҧ năng lѭu trӳ tӟi ܵ MB. Cѫ chӃ lѭu Vҩn ÿӅ tӕi ÿa hóa tӍ lӋ hit tҥi nút lѭu trӳ và tӕi ѭu hóa lѭu trӳ ӣ ÿây là lѭu trӳ hoàn toàn, tӭc là các nӝi dung ÿѭӧc lѭu trӳ lѭӧng nӝi dung tҧi xuӕng tӯ các cөm nút cha thұt ra chính là vӟi ÿҫy ÿӫ thông tin, kích thѭӟc và không bӏ phân mҧnh. Ký bài toán Knapsack. hiӋu kích thѭӟc cӫa nӝi dung ݉ là ‫ݏ‬௠ . Ĉһt ‫ݔ‬௠ là biӃn nhӏ phân biӇu thӏ nӝi dung ݉ có ÿѭӧc lѭu trӳ tҥi nút mҥng hay không. Mөc tiêu (max_hit) và (min_transit) cNJng là lӡi giҧi cho Tәng dung lѭӧng cӫa các nӝi dung ÿѭӧc lѭu trӳ trên nút phҧi bài toán Knapsack. Kích thѭӟc cӫa mӛi nӝi dung m là sm. Giá bӏ giӟi hҥn bӣi khҧ năng lѭu trӳ cӫa nút: σ௠‫א‬ெ ‫ݏ‬௠ ‫ݔ‬௠ ൑ ܵ. trӏ cӫa nӝi dung cӫa ݉ trong (max_hit) và (min_transit) tѭѫng ӭng lҫn lѭӧt là ݀௠ và ݀௠ ‫ݏ‬௠ ܿ௠ . bài toán Knapsack là bài toán  19
  5. +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
  6. 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) quy hoҥch tuyӃn tính có ÿӝ phӭc tҥp theo hàm mNJ do ÿó cҫn có nút mҥng ICN cө thӇ, khi nhұn ÿѭӧc yêu cҫu cho nӝi dung m thuұt toán xҩp xӍ ÿӇ giҧi. Thuұt toán greedy giҧi quyӃt bài toán tӯ ngѭӡi dùng, sӁ có hai trѭӡng hӧp xҧy ra. Trѭӡng hӧp ÿҫu quy hoҥch tuyӃn tính xҩp xӍ. Theo ÿó, tҩt cҧ các nӝi dung sӁ tiên: dach sách lѭu trӳ cӫa nút mҥng có nӝi dung m, lúc này m ÿѭӧc sҳp xӃp theo chiӅu giҧm dҫn theo giá trӏ cӫa ÿѫn vӏ nӝi sӁ ÿѭӧc trҧ vӅ cho ngѭӡi dùng, ÿӗng thӡi dm tăng thêm 1, hit- dung ÿѭӧc tính bҵng “ ୥୧ž୲୰ዋ୬ዒ୧ୢ୳୬୥ ”. Các nӝi dung sӁ ÿѭӧc counter cNJng tăng thêm 1 ÿѫn vӏ. Trѭӡng hӧp thӭ hai: nӝi dung ୩Àୡ୦୲୦ዛዔୡ୬ዒ୧ୢ୳୬୥ m không ÿѭӧc lѭu trӳ tҥi ÿây, khi ÿó bӝ ÿӃm miss-counter sӁ lѭu trӳ tҥi nút mҥng theo chiӅu giҧm dҫn giá trӏ ÿã nêu cho ÿӃn tăng lên và chuyӇn tiӃp yêu cҫu ÿӃn nút mҥng khác. Khi nӝi khi nút mҥng ÿҫy. Vì kích thѭӟc cӫa các nӝi dung nhӓ hѫn rҩt dung m ÿѭӧc ÿѭӧc trҧ vӅ cho ngѭӡi dùng, nó sӁ ÿi qua nút nhiӅu so vӟi khҧ năng lѭu trӳ cӫa nút mҥng, nên viӋc thӵc hiӋn mҥng ÿang xét, tҥi thӡi ÿiӇm này, nút mҥng sӁ quyӃt ÿӏnh xem giҧi thuұt xҩp xӍ là cách tӕi ѭu ÿӇ giҧi quyӃt bài toán Knapsack. có nên lѭu trӳ nӝi dung ݉ hay không. NӃu bӝ nhӟ còn dѭ cӫa Nút mҥng trong ICN sӁ luôn duy trì mӝt danh sách các nӝi nút mҥng vүn lӟn hѫn kích thѭӟc cӫa nӝi dung thì m sӁ ÿѭӧc dung mà nó ÿang lѭu trӳ. Mӛi nӝi dung ݉ sӁ có bӕn thông sӕ, lѭu trӳ ngay lұp tӭc và danh sách lѭu trӳ sӁ ÿѭӧc cұp nhұt ÿó là: tên nӝi dung-contentID, sӕ lҫn ÿѭӧc yêu cҫu ݀௠ , kích ÿӗng thӡi. Ngѭӧc lҥi, nút mҥng sӁ tính toán giá trӏ nhӓ nhҩt thѭӟc ‫ݏ‬௠ và chi phí ܿ௠ . Vӟi thuұt toán (max_hit), thông tin nӝi theo hàm sӕ ݂ሺܿ௠ ǡ ݀௠ ǡ ‫ݏ‬௠ ሻ cӫa mӛi nӝi dung ÿang ÿѭӧc lѭu dung có giá trӏ ௗ೘ lӟn nhҩt sӁ ÿѭӧc lѭu trӳ tҥi nút mҥng ÿang trӳ. Sau ÿó, nӝi dung có giá trӏ nhӓ nhҩt sӁ bӏ loҥi bӓ ngay lұp ௦೘ tӭc cho ÿӃn khi bӝ nhӟ trӕng cӫa nút mҥng lӟn hѫn hoһc bҵng xét. Còn vӟi thuұt toán (min_transit), nӝi dung nӝi dung có giá vӟi kích thѭӟc cӫa nӝi dung ݉. Sau ÿó, m sӁ ÿѭӧc lѭu trӳ tҥi trӏ ݀௠ ܿ௠ lӟn nhҩt sӁ ÿѭӧc chӑn. Khi ngѭӡi dùng gӱi yêu cҫu nút mҥng này. Giá trӏ nhӓ nhҩt cӫa nӝi dung theo hàm sӕ cho nӝi dung m, nút mҥng nhұn ÿѭӧc sӁ tìm kiӃm trong danh ݂ሺܿ௠ ǡ ݀௠ ǡ ‫ݏ‬௠ ሻ sӁ ÿѭӧc tính toán mӛi lҫn lѭu trӳ ݉. sách nӝi dung cӫa mình, nӃu tên nӝi dung trong danh sách trùng khӟp vӟi tên nӝi dung ÿѭӧc yêu cҫu thì nӝi dung ÿó sӁ Thuұt toán (min_transit) là thuұt toán có tính ÿӃn khҧ năng ÿѭӧc gӱi ÿӃn cho ngѭӡi dùng bҵng chính con ÿѭӡng mà gói tin hӧp tác giӳa các nút mҥng. ĈiӅu này ÿѭӧc thӵc hiӋn thông qua yêu cҫu ÿӃn. Lúc này, giá trӏ ݀௠ cӫa nӝi dung sӁ tăng lên mӝt, giá trӏ ܿ௠ . Xét mӝt vùng mҥng bao gӗm nhiӅu nút mҥng. Khi thông sӕ này sӁ tăng lên mӛi khi nӝi dung ݉ ÿѭӧc yêu cҫu tҥi mӝt nút mҥng nhұn ÿѭӧc yêu cҫu cho nӝi dung ݉ không ÿѭӧc nút mҥng mà nó ÿѭӧc lѭu trӳ. Bên cҥnh ÿó, mӛi nút mҥng lѭu trӳ tҥi nút mҥng ÿó thì bҳt buӝc nó phҧi gӱi yêu cҫu tӟi các cNJng có hai bӝ ÿӃm là hit-counter và miss-counter ÿӇ ghi nhұn nút mҥng hàng xóm khác. Nӝi dung ݉ ÿѭӧc gӱi trҧ vӅ cho nút lҥi sӕ lҫn mà nút mҥng có thӇ ÿáp ӭng yêu cҫu cӫa ngѭӡi dùng. mҥng ÿang xét tӯ các nút mҥng khác nhau vӟi chi phí ܿ௠ khác Mӛi khi nӝi dung yêu cҫu ÿã ÿѭӧc ÿѭӧc lѭu trӳ tҥi nút mҥng nhau. Trong thuұt toán (min_transit), nӝi dung nӝi dung có giá ÿang xét và nút mҥng có thӇ hӗi ÿáp lҥi yêu cҫu ngѭӡi dùng trӏ ݀௠ ܿ௠ lӟn nhҩt sӁ ÿѭӧc chӑn. ĈiӅu này có nghƭa là nӝi dung ngay lұp tӭc thì giá trӏ hit-counter sӁ tăng lên. Ngѭӧc lҥi, khi m vӟi ܿ௠ cao sӁ ÿѭӧc lѭu trӳ tҥi nút mҥng. Bӣi vì khi giá trӏ nút mҥng không lѭu trӳ nӝi dung ÿѭӧc yêu cҫu thì giá trӏ miss- vӟi ܿ௠ cao, chӭng tӓ nӝi dung ݉ ÿӃn ÿѭӧc lѭu trӳ tҥi mӝt nút counter tҥi nút mҥng này sӁ tăng lên, ÿӗng thӡi yêu cҫu tӯ mҥng nҵm cách xa nút mҥng ÿang xét. Do vұy ÿӇ hҥn chӃ lѭu ngѭӡi dùng sӁ ÿѭӧc chuyӇn tiӃp tӟi mӝt nút mҥng tiӅm năng lѭӧng nӝi dung truyӅn tҧi và ÿҧm bҧo băng thông thì nӝi dung khác. m nên ÿѭӧc lѭu trӳ cho nhӳng lҫn yêu cҫu sau này. Trong trѭӡng hӧp nӃu các nút mҥng trong vùng không có nӝi dung m Trong thuұt toán (max_hit), tӍ lӋ hit nӝi dung tҥi các nút mà phҧi gӱi yêu cҫu ra ngoài mҥng Internet thì ݉ sӁ ÿѭӧc ѭu mҥng sӁ ÿѭӧc tӕi ÿa hóa (ÿӗng nghƭa vӟi viӋc tӕi thiӇu hóa tӍ lӋ tiên lѭu trӳ tҥi nút mҥng ÿang xét ÿӇ tránh tiêu tӕn băng thông miss nӝi dung) và tӕi thiӇu hóa lѭu lѭӧng nӝi dung truyӅn tҧi tӯ các cөm nút khác vӟi thuұt toán (min_transit). Ta xét mӝt  20
  7. +ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
  8. 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) khi nhұn nӝi dung tӯ mҥng Internet cho nhӳng lҫn yêu cҫu sau dung chӑn tӯ cөm nút cha. Ĉây là các nӝi dung nҵm trong này. khoҧng tӯ 1 ÿӃn 4.000 cӫa cөm nút mҥng. Do ÿó sӕ lѭӧng nӝi dung ÿѭӧc khӣi tҥo tҥi nút mҥng ÿѫn là lӟn hѫn 1 và bé hѫn Thuұt toán max_hit và min_transit 4,000 thӓa ÿiӅu kiӋn tәng kích thѭӟc các nӝi dung nhӓ phҧi 1: Khӣi tҥo danh sách ‫;ܮ‬ 2: WHILE {mӝt ngѭӡi dùng gӣi mӝt yêu cҫu nӝi dung ݉} hѫn khҧ năng lѭu trӳ tҥi nút ÿang xét là 10 GB. 3: IF (݉ ‫)ܮ א‬ 4: gӣi nӝi dung ݉ ÿӃn ngѭӡi dùng; ĈӇ thӵc hiӋn ÿo lѭӡng ÿánh giá, chѭѫng trình mô phӓng 5: ELSE sӁ tҥo ra 5*105 gói tin trong khoҧng thӡi gian gҫn mӝt ngày 6: ‫ ܮ‬ൌ ‫ ܮ‬൅ ሼ݉ሽ; \* lѭu ݉ *\ cӫa quá trình mô phӓng, tӭc là cӭ mӛi giây thì 6 gói tin sӁ 7: WHILE (‫݁ݖ݅ݏ‬ሺ‫ܮ‬ሻ ൐ ܵ) 8: ‫ ܮ‬ൌ ‫ ܮ‬െ ƒ”‰ ‹௜‫א‬௅ ݂ሺܿ௜ ǡ ݀௜ ǡ ‫ݏ‬௜ ሻ ; \* loҥi bӓ ÿѭӧc tҥo ra. Các gói tin này ÿҥi diӋn cho yêu cҫu cӫa ngѭӡi 9: nӝi dung trong ‫ ܮ‬vӟi giá trӏ ݂ሺܿ௜ ǡ ݀௜ ǡ ‫ݏ‬௜ ሻ nhӓ dùng gӱi tӟi các máy chӫ ÿӇ yêu cҫu thông tin nӝi dung cҫn 10: nhҩt *\ thiӃt. Chúng sӁ ÿѭӧc gӱi lҫn lѭӧt ÿӃn nút mҥng ÿѫn, sau 2.000 11: ENDWHILE; 12: lҫn gӱi ÿҫu tiên sӁ tiӃn hành ÿo lѭӡng. Tӭc là sau khoҧng thӡi ENDIF 13: ENDWHILE gian khӣi ÿӝng vӟi 2.000 gói tin, chѭѫng trình sӁ tính toán tӍ lӋ 14: miss, hit, lѭu lѭӧng nӝi dung tӯ gói tin thӭ 2.001. Trong quá trình gӱi 2.000 gói tin ÿҫu tiên, nút mҥng thӵc hiӋn thuұt toán IV. KӂT QUҦ MÔ PHӒNG ÿã ÿӅ xuҩt ÿӇ lѭu trӳ các nӝi dung phù hӧp cNJng nhѭ loҥi bӓ Chѭѫng trình mô phӓng ÿѭӧc xây dӵng nhҵm ÿo lѭӡng các nӝi dung không cҫn thiӃt ViӋc này ÿѭӧc thӵc hiӋn dӵa vào hiӋu quҧ cӫa các thuұt toán ÿã ÿӅ xuҩt. ViӋc ÿánh giá sӁ dӵa ContentID cӫa mӛi nӝi dung m. Sau khoҧng thӡi gian khӣi trên kӃt quҧ cӫa ba thông sӕ: tӍ lӋ hit, tӍ lӋ miss và lѭu lѭӧng ÿӝng này, danh sách nӝi dung cӫa nút mҥng ÿã ÿѭӧc cұp nhұt nӝi dung truyӅn tҧi. Trong quá trình mô phӓng, chúng tôi giҧ tѭѫng ÿӕi әn ÿӏnh. ÿӏnh rҵng tӗn tҥi các nút mҥng ÿѫn và mӝt cөm các nút mҥng. ContentID trong các gói tin yêu cҫu ÿѭӧc tҥo ra mӝt cách Cөm nút mҥng này có thӇ trҧ lӡi cho tҩt cҧ các yêu cҫu tӯ ngүu nhiên theo phân phӕi xác suҩt, cө thӇ là theo hàm phân ngѭӡi dùng. Ĉây là nѫi ÿҥi diӋn cho các máy chӫ lѭu trӳ trên phӕi Zipf, ÿây là mӝt phân phӕi quy tҳc lNJy thӯa vӟi thông sӕ Internet. Còn nút mҥng ÿѫn sӁ là nѫi nhұn tҩt cҧ các yêu cҫu ߙ thay ÿәi. ߙ càng lӟn thì tҫn sӕ xuҩt hiӋn mӝt sӕ ContentID nӝi dung ÿӃn tӯ các ngѭӡi dùng khác nhau. Nó ÿҥi diӋn cho càng lӟn. Trong chѭѫng trình mô phӓng, chúng tôi sӱ dөng giá các máy chӫ biên ӣ gҫn vӟi ngѭӡi dùng nhҩt. Khi các gói tin trӏ ߙ trong khoҧng tӯ 0.4 ÿӃn 1.1 ÿӇ xác ÿӏnh tӍ lӋ hit, tӍ lӋ miss yêu cҫu tӯ ÿѭӧc chuyӇn tӟi sӁ thông qua các máy chӫ biên ÿӇ và lѭu lѭӧng nӝi dung. Trên Inernet, hàm phân phӕi Zipf có ra ngoài mҥng, do ÿó ÿây là nѫi ÿҫu tiên nhұn ÿѭӧc các yêu tҫn suҩt xuҩt hiӋn rҩt lӟn. Nó có mһt trong mҥng Internet tӯ cҫu vӅ nӝi dung trong mӛi AS. Và nó cNJng sӁ nhұn nӝi dung cҩp ÿӝ ÿӏnh tuyӃn nӝi dung giӳa các vùng khác nhau cho ÿӃn hӗi ÿáp tӯ các cөm nút mҥng khác ÿӇ trҧ vӅ cho ngѭӡi dùng kinh tӃ xã hӝi. Ĉây là lý do các ContentID ÿѭӧc tҥo ra theo hoһc trҧ lӡi bҵng nӝi dung nó ÿang lѭu trӳ nӃu trùng khӟp vӟi hàm Zipf. Các ContentID này ÿóng vai trò là các yêu cҫu tӯ yêu cҫu cӫa ngѭӡi dӫng. Do vұy, viӋc lѭu trӳ nӝi dung ӣ các ngѭӡi dùng gӱi tӟi nút mҥng trong quá trình mô phӓng. TӍ lӋ nút mҥng ÿѫn ÿóng vai trò rҩt quan trӑng trong quá trình hoҥt hit, miss và lѭu lѭӧng nӝi dung cӫa thuұt toán ÿѭӧc tính toán ÿӝng cӫa mҥng ICN. Trong quá trình mô phӓng, chúng tôi giҧ dӵa trên sӕ lҫn trùng khӟp cӫa ContentID yêu cҫu và sӱ rҵng cөm nút mҥng chӭa ÿӃn 10.000 thông tin nӝi dung. ContentID trong danh sách nӝi dung lѭu trӳ cӫa nút mҥng. KӃt Khҧ năng lѭu trӳ cӫa mӛi nút mҥng ÿѫn là 10 TB và kích quҧ thu ÿѭӧc tӯ hai thuұt toán ÿӅ xuҩt sӁ so sánh vӟi nhӳng thѭӟc cӫa mӛi nӝi dung là mӝt sӕ nҵm trong khoҧng 1 ÿӃn 10 GB. Ban ÿҫu nút mҥng ÿѫn có thӇ chӭa mӝt danh sách các nӝi  21
  9. 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{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
  10. thuұt toán lѭu trӳ ÿang ÿѭӧc sӱ dөng hiӋn nay ÿó là LCE-LRU (min_transit) có lѭu lѭӧng truyӅn tҧi thҩp nhҩt trong bӕn thuұt và LCE-LFU. toán. Nhìn mӝt cách tәng quan, hiӋu suҩt lѭu trӳ nӝi dung tҥi nút mҥng ÿѫn sӁ tăng khi Ƚ tăng. Vӟi giá trӏ Ƚ lӟn thì sӵ chênh Sau khi thӵc hiӋn mô phӓng, kӃt quҧ thu ÿѭӧc cho thҩy lӋch giӳa các thuұt toán là không nhiӅu. Ta cNJng nhұn thҩy hai thuұt toán ÿӅ xuҩt hoҥt ÿӝng tӕt hѫn so vӟi giҧi thuұt LCE- rҵng thuұt toán lѭu trӳ LCE vӟi LRU luôn thӇ hiӋn hiӋu quҧ LRU và LCE-LFU. Trong Hình 1, thuұt toán (max_hit) có tӍ lӋ thҩp nhҩt trong tҩt cҧ các trѭӡng hӧp. Riêng thuұt toán LCE hit cao hѫn hҷn so vӟi ba thuұt toán còn lҥi. Vì vұy tӍ lӋ miss vӟi LFU mһc dù cho kӃt quҧ thҩp hѫn (max_hit) nӃu mөc tiêu cӫa thuұt toán (max_hit) luôn luôn thҩp nhҩt trong các thuұt là tӕi ÿa tӍ lӋ hit, nhѭng lҥi tӕt hiӋu quҧ hѫn (min_transit). Còn toán lѭu trӳ ÿang ÿѭӧc mô phӓng (xem Hình 2). Ví dө, vӟi nӃu mөc tiêu ÿһt ra là tӕi thiӇu hóa lѭu lѭӧng nӝi dung truyӅn Ƚ ൌ ͲǤͷ, tӍ lӋ hit cӫa (max_hit) là 53.1%, trong khi LCE+LRU tҧi thì LCE+LFU tӋ hѫn (min_transit) nhѭng lҥi tӕt hѫn là 28.8% và LFU là 42.5%. (max_hit). Vì vұy, LCE+LFU có thӇ xem nhѭ là phѭѫng pháp tҥm thӡi ÿӇ lѭu trӳ nӝi dung nӃu nhѭ nút mҥng chѭa ÿѭӧc triӇn khai mô hình tӕi ѭu hóa lѭu trӳ thông tin, nӝi dung. Hình 1. T͑ l͏ hit theo ߙ Hình 3. L˱u l˱ͫng n͡i dung theo ߙ. V. KӂT LUҰN Khi mà lѭu lѭӧng nӝi dung ÿang ngày mӝt tăng lên thì viӋc xây dӵng mӝt bài toán tӕi ѭu cho viӋc lѭu trӳ nӝi dung phân tán là mӝt vҩn ÿӅ cҩp thiӃt khi xây dӵng mô hình mҥng ICN. Bài báo này ÿѭa ra nhӳng nghiên cӭu ÿӇ xây dӵng mӝt thuұt toán có khҧ năng tính toán tӕi ѭu cho viӋc lѭu trӳ phân tán nӝi dung trên các node mҥng cӫa ICN. Chúng tôi ÿã ÿӅ xuҩt mô hình tӕi ѭu hóa trong viӋc lѭu trӳ nӝi dung trong kiӃn trúc mҥng ICN. Mөc ÿích cӫa các thuұt toán ÿѭӧc ÿӅ xuҩt là tӕi ѭu hóa tӍ lӋ hit và giҧm thiӇu lѭu lѭӧng vұn chuyӇn khi nӝi dung ÿѭӧc yêu cҫu. Dӵa trên viӋc giҧi quyӃt bài toán Knapsack, chúng tôi giӟi thiӋu Hình 2. T͑ l͏ miss theo ߙ. hai thuұt toán lѭu trӳ cho mӝt nút mҥng ÿó là (max_hit) và Hình 3 mô tҧ lѭu lѭӧng nӝi dung truyӅn tҧi trong suӕt quá (min_transit). Tӯ các kӃt quҧ sӕ liӋu cho thҩy hai thuұt toán trình thӵc hiӋn mô phӓng cӫa bӕn thuұt toán vӟi các giá trӏ Ƚ ÿѭӧc ÿӅ xuҩt có hiӋu quҧ nәi trӝi hѫn so vӟi các thuұt toán lѭu khác nhau. KӃt quҧ thu ÿѭӧc cNJng cho thҩy rҵng thuұt toán trӳ truyӅn thӕng là LCE+LRU và LCE+LFU.  22
  11. HộiHội Thảo Quốc Thảo QuốcGia Gia2015 2015về về Điện Tử, Truyền Điện Tử, ThôngvàvàCông Truyền Thông CôngNghệ Nghệ Thông Thông Tin Tin (ECIT (ECIT 2015) 2015) ACKNOWLEDGMENT forest for the trees,” in ACM Workshop on Hot Topics in Networks (HotNets), 2011. TS. Võ Th Lu Phng là tác gi chu trách nhim. Nghiên [12] N. Laoutaris, H. Che, I. Stavrakakis, “The LCD interconnection cu c tài tr bi i hc Quc gia Thành ph H Chí Minh (HQG-HCM) trong khuôn kh  tài mã s C2015-28-01. of LRU caches and its analysis,” Performance Evaluation, vol. 63, no. 7, pp. 609–634, 2006 S. Ihm and V. S. Pai, “Towards understanding modern web traffic,” in ACM Workshop on Information-Centric Networking (ICN), 2011. [13] W. K. Chai, D. He, I. Psaras, and G. Pavlou, “Cache “less for TÀI LIU THAM KHO more” in information-centric networks,” in Proc. of the IFIP- [1] Stanford University TRIAD project. [Online]. Available: TC6 Networking Conference, 2012. http://www-dsg.stanford.edu/triad/. [14] I. Psaras, W. K. Chai, and G. Pavlou, “Probabilistic in-network [2] M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, and I. caching for information-centric networks,” in ACM Workshop Stoica, “ROFL: routing on flat labels,” in ACM SIGCOMM, 2006, on Information-Centric Networking (ICN), 2012. pp. 363–374. [15] G. Carofiglio, V. Gehlen, and D. Perino, “Experimental [3] T. Koponen, M. Chawla, B. Chun, A. Ermolinskiy, K. H. Kim, S. evaluation of memory management in content-centric Shenker, and I. Stoica, “A data-oriented (and beyond) network networking,” in International Conference on Communications architecture,” in ACM SIGCOMM, 2007, pp. 181–192. (ICC), 2011. [4] FP7 PSIRP project. [Online]. Available: http://www.psirp.org/ [16] M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, and I. [5] V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Stoica, “ROFL: routing on flat labels,” in ACM SIGCOMM, Briggs, and R. L. Braynard, “Networking named content,” in 2006, pp. 363–374. ACM CoNEXT, 2009. [17] L. Rizzo and L. Vicisano, “Replacement policies for a proxy [6] FP7 COMET project. [Online]. Available: http://www.comet- cache,” IEEE/ACM Transactions on Networking (ToN), vol.8, project.org/ no.2, pp. 158-170, 2000. [7] FP7 CONVERGENCE project. [Online]. [18] D. Lee, J. Choi, J. H. Kim, S. H. Noh, S. L. Min, Y. Cho, C. S. Available:http://www.ictconvergence.eu/ Kim, “LRFU: A spectrum of policies that subsumes the least [8] NSF Named Data Networking project. [Online]. Available: recently used and least frequently used policies,” IEEE http://www.named-data.net/ Transactions on Computers, vol. 50, no. 12, pp. 1352-1361, [9] FP7 SAIL project. [Online]. Available: http://www.sail- 2001. project.eu/. [19] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack problems. [10] FP7 PURSUIT project. [Online]. Springer Science & Business Media, 2004 Available:http://www.fp7pursuit.eu/PursuitWeb/ [11] A. Ghodsi, S. Shenker, T. Koponen, A. Singla, B. Raghavan, and J. Wilcox, “Information-centric networking: seeing the 23 23
nguon tai.lieu . vn
Kiến trúc - Xây dựng Tự động hoá Điện - Điện tử Kĩ thuật Viễn thông Cơ khí - Chế tạo máy Năng lượng Hoá dầu Hoá học Sinh học