Nghiên cứu các vấn đề định tuyến multicast lớp ứng dụng

Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> <br /> Nghiªn cøu C¸C VÊN §Ò ®Þnh tuyÕn<br /> Multicast líp øng dông<br /> Vò ThÞ Thóy Hµ, l£ H÷U LËP, L£ NHËT TH¡NG<br /> Tãm tắt: Multicast líp øng dông ALM cã rÊt nhiÒu ­u ®iÓm so víi IP<br /> multicast [1,3,6]. Thø nhÊt, nã triÓn khai dÔ dµng vµ chi phÝ thÊp; Multicast líp<br /> øng dông chØ yªu cÇu líp nÒn t¶ng IP hç trî chøc n¨ng truyÒn th«ng unicast<br /> kh«ng cÇn ph¶i thay ®æi c¬ së h¹ tÇng m¹ng IP hiÖn cã. Thø hai, nã cã tÝnh linh<br /> ho¹t, multicast líp øng dông ®­îc thùc hiÖn t¹i c¸c thiÕt bÞ ®Çu cuèi ra nhËp vµo<br /> m¹ng Internet. Thø ba, nã phï hîp víi triÓn khai trªn quy m« lín nh­ m¹ng<br /> Internet. Môc tiªu chÝnh cña ®Þnh tuyÕn Multicast lµ x©y dùng c©y multicast tèi<br /> ­u ®¸p øng c¸c yªu cÇu chÊt l­îng dÞch vô. Bµi b¸o ph©n tÝch vµ tæng hîp c¸c<br /> vÊn ®Ò vÒ ®Þnh tuyÕn, c¸c gi¶i ph¸p tèi ­u cho c©y ®Þnh tuyÕn Multicast líp øng<br /> dông vµ ®­a ra h­íng nghiªn cøu tiÕp ®Ó c¶i thiÖn hiÖu n¨ng giao thøc ®Þnh tuyÕn<br /> multicast líp øng dông cã tÝnh ®Õn c¶ QoS cña dÞch vô yªu cÇu.<br /> Tõ khãa: Mạng che phủ, Định tuyến Multicast, Lớp ứng dụng multicast-ALM, Chất lượng dịch vụ - QOS,<br /> Cơ sở hạ tầng ứng dụng Multicast –ALMI.<br /> <br /> <br /> 1. ®Æt vÊn ®Ò<br /> Trong thêi gian gÇn ®©y h¹ tÇng Internet ph¸t triÓn víi tèc ®é chãng mÆt, ®·<br /> lµm xuÊt hiÖn nhiÒu øng dông míi sö dông truyÒn tin multicast thêi gian thùc nh­<br /> truyÒn h×nh qua giao thøc IP, héi nghÞ cã h×nh vv. Chóng ®ang lµm thay ®æi c¸ch<br /> giao tiÕp cña con ng­êi, thu hÑp mäi kho¶ng c¸ch vËt lý, mang ®Õn cho chóng ta<br /> nh÷ng tr¶i nghiÖm míi mÎ. IP multicast cã thÓ xem lµ ph­¬ng ph¸p multicast chÝnh<br /> thèng, hiÖu qu¶ nhÊt. Tõ gãc ®é kü thuËt, triÓn khai, qu¶n lý vµ ho¹t ®éng cña IP<br /> multicast rÊt phøc t¹p vµ tèn kÐm. §Ó ®¸p øng nhu cÇu trao ®æi d÷ liÖu ®a ph­¬ng<br /> tiÖn quy m« lín qua m¹ng Internet, nhiÒu nghiªn cøu tËp trung vµo truyÒn<br /> Multicast líp øng dông - ALM [1,3,6]. ALM thùc hiÖn c¸c chøc n¨ng multicast<br /> nh­ mét dÞch vô líp øng dông thay v× lµ dÞch vô líp m¹ng. Nã cã ­u ®iÓm v­ît tréi<br /> víi multicast IP, nã cã thÓ triÓn khai mét c¸ch dÔ dµng vµ nhanh chãng trªn m¹ng<br /> Internet mµ kh«ng cÇn cã bÊt kú thay ®æi c¬ së h¹ tÇng cña m¹ng nÒn t¶ng , nh­ng<br /> vÉn gi¶i quyÕt ®­îc c¸c vÊn ®Ò sö dông hiÖu qu¶ nguån tµi nguyªn vµ b¨ng th«ng<br /> cña ng­êi sö dông vµ cung cÊp ®­îc c¸c dÞch vô míi ®¶m b¶o QOS vµ hiÖu qu¶ vÒ<br /> chi phÝ. Tuy nhiªn, khi triÓn khai truyÒn multicast trªn líp øng dông còng gÆp<br /> kh«ng Ýt vÊn ®Ò. Thay v× nh©n b¶n c¸c gãi tin t¹i c¸c bé ®Þnh tuyÕn nh­ IP multicast<br /> th× c¬ chÕ multicast trªn líp øng dông l¹i nh©n b¶n c¸c gãi tin trªn c¸c m¸y ®Çu<br /> cuèi. Do ®ã, viÖc tèi ­u c©y multicast nh»m t¹o sù c©n b»ng t¶i trªn toµn m¹ng<br /> còng lµ mét vÊn ®Ò. Mét vÊn ®Ò n÷a lµ ph¶i tÝnh ®Õn ®é trÔ. C¸c gãi tin liªn tôc ph¶i<br /> lu©n chuyÓn qua nhiÒu vÞ trÝ ®Çu cuèi nªn ®é trÔ sÏ t¨ng cao. ViÖc x©y dùng mét<br /> c©y multicast phï hîp ®Ó gi¶m thiÓu ®é trÔ còng lµ mét h­íng nghiªn cøu. Nh­ng<br /> do c©y multicast kÕt nèi logic trªn nÒn cña m¹ng IP v× vËy ®Þnh tuyÕn tåi h¬n ®Þnh<br /> tuyÕn IP vµ nã ®· trë thµnh vÊn ®Ò chÝnh cña rÊt nhiÒu c«ng tr×nh nghiªn cøu. Bµi<br /> b¸o tæng hîp vµ ph©n tÝch c¸c vÊn ®Ò tèi ­u c©y ®Þnh tuyÕn Multicast líp øng dông,<br /> x©y dùng bµi to¸n tèi ­u c©y ®Þnh tuyÕn vµ so s¸nh hiÖu n¨ng gi÷a hai giao thøc<br /> NICE va ZIGZAG, tõ ®ã ®­a ra h­íng nghiªn cøu tiÕp.<br /> <br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12- 2014 33<br />  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> 2. Ph©n lo¹i c¸c gi¶i thuËt ®Þnh tuyÕn ALM<br /> C¸c giao thøc ®Þnh tuyÕn líp øng dông ®­îc ph©n lo¹i dùa vµo cÊu tróc t«p«<br /> m¹ng vµ kiÓu ®iÒu khiÓn. Qua kh¶o s¸t nghiªn cøu th× ®Þnh tuyÕn Multicast ®­îc<br /> chia thµnh hai kiÓu: tËp trung vµ ph©n t¸n. KiÓu tËp trung toµn bé viÖc tÝnh to¸n<br /> th«ng tin ®Þnh tuyÕn vµ thu thËp th«ng tin tr¹ng th¸i m¹ng Multicast ®Òu do trung<br /> t©m ®iÒu khiÓn. KiÓu ph©n t¸n th× viÖc ®Þnh tuyÕn vµ thu thËp th«ng tin tr¹ng th¸i<br /> ®­îc ph©n t¸n cho c¸c hÖ thèng ®Çu cuèi tõ ®ã tæ chøc cÊu tróc c©y multicast. KiÓu<br /> ph©n t¸n cã mét sè c¸ch ®Ó t¹o cÊu tróc m¹ng chång phñ : Dùa trªn l­íi (Mesh<br /> first) vµ dùa trªn c©y (Tree first).<br /> TËp trung: Trong ph­¬ng ph¸p nµy, nót qu¶n lý c©y hoÆc bé ®iÒu khiÓn trung t©m<br /> thùc hiÖn tÝnh to¸n c©y ®­êng ®i ng¾n nhÊt MST (Minimum Spanning Tree) dùa<br /> trªn bé tham sè ®o hiÖu n¨ng cña øng dông cô thÓ (nh­ trÔ ®Çu cuèi, b¨ng th«ng cã<br /> s½n). Ch¼ng h¹n, ALMI[2] sö dông lÖnh ping ®o thêi gian trÔ ®­îc thùc hiÖn bëi<br /> c¸c thµnh viªn nhãm, v× trÔ lµ tiªu chÝ cho nhiÒu øng dông vµ còng kh¸ dÔ dµng ®Ó<br /> kiÓm so¸t. MÆc dï, hiÖu qu¶ cña c¸c c©y multicast ALMI gÇn b»ng hiÖu qu¶ cña<br /> c¸c c©y Multicast IP nh­ng kh¶ n¨ng më réng kÐm, ALMI chØ øng dông trong<br /> m¹ng cã quy m« nhá. §èi víi c¸c hÖ thèng quy m« lín hiÖu n¨ng hÖ thèng gi¶m<br /> do hiÖn t­îng nghÏn cæ chai t¹i c¸c bé ®iÒu khiÓn trung t©m.<br /> Mesh -first[3,8] : Lµ c¸ch tiÕp cËn CAN (Content-Addressable Networks) , Narada,<br /> Scattercast, Bayeux. Trong m« h×nh mesh – first, c¸c nót muèn tham gia vµo qu¸<br /> tr×nh truyÒn hoÆc nhËn d÷ liÖu multicast sÏ tham gia vµo mét m¹ng phñ h×nh thµnh<br /> nªn mét cÊu tróc d¹ng l­íi liªn kÕt c¸c nót víi nhau. C©y multicast sÏ ®­îc x©y<br /> dùng dùa trªn c¸c liªn kÕt cña m¹ng phñ nµy. Sau khi cÊu tróc m¹ng ®­îc h×nh<br /> thµnh th× nót nguån sÏ sö dông thuËt to¸n ®Þnh tuyÕn ®Ó truyÒn multicast th«ng qua<br /> m¹ng ®ã. Th«ng th­êng c©y multicast t¹o ra tõ ph­¬ng thøc nµy kh«ng ®­îc tèi ­u<br /> do gÆp ph¶i vÊn ®Ò “nót th¾t cæ chai” khi mét nót cã tµi nguyªn kÐm mµ ph¶i chÞu<br /> t¶i cao. H¬n n÷a, viÖc duy tr× m¹ng phñ còng ®ßi hái mét phÇn b¨ng th«ng cho c¸c<br /> th«ng tin ®iÒu khiÓn m¹ng. Tuy nhiªn, lîi thÕ cña m« h×nh nµy lµ kh¶ n¨ng chÞu lçi<br /> cao bëi c¸c nót trong c©y kh«ng chØ biÕt ®Õn nót cha cña nã mµ cßn biÕt th«ng tin<br /> vÒ c¸c nót kh¸c. M« h×nh nµy th­êng ®­îc sö dông víi c¸c øng dông ®a nguån<br /> multicast nh­ héi nghÞ cã h×nh. Tuy nhiªn, nh­îc ®iÓm cña m« h×nh nµy lµ rÊt khã<br /> ®Ó thùc hiÖn c©n b»ng t¶i vµ c©n b»ng ®é trÔ gi÷a c¸c nót do phô thuéc vµo<br /> kiÕn tróc m¹ng phñ. Víi nh­îc ®iÓm nµy th× kh«ng phï hîp víi truyÒn video<br /> streaming do c¸c gãi tin cã ®é trÔ kh¸c nhau, gãi tin göi tr­íc cã thÓ ®Õn sau,<br /> gãi tin göi sau ®Õn tr­íc. ViÖc kh«ng c©n b»ng ®é trÔ sÏ lµm ¶nh h­ëng ®Õn<br /> viÖc tr×nh diÔn d÷ liÖu.<br /> Tree first[3,8] : Lµ c¸ch tiÕp cËn YOID, HMTP, NICE, ZIGZAG. Víi m« h×nh<br /> Tree- first, c©y multicast ®­îc h×nh thµnh mµ kh«ng cÇn c¸c nót t¹o thµnh m¹ng<br /> phñ víi nhau. Mét nót chän cha cña nã tõ mét sè thµnh viªn ®· biÕt trong c©y. ViÖc<br /> chän cha th­êng ®­îc thùc hiÖn dùa trªn mét sè tiªu chÝ nh­ c©n b»ng b¨ng th«ng<br /> gi÷a c¸c nót hoÆc ®¶m b¶o ®é s©u cña c©y c©n b»ng gi÷a c¸c nh¸nh. ¦u ®iÓm cña<br /> m« h×nh nµy lµ c¸c nót cã thÓ chän nót cha, do ®ã cã thÓ tr¸nh ®­îc t×nh tr¹ng mét<br /> nót nµo ®ã ph¶i chÞu t¶i qu¸ cao. M« h×nh nµy cÇn cã thuËt to¸n ph¸t hiÖn vµ tr¸nh<br /> lÆp x¶y ra trong c©y multicast. C¸c nót trong c©y sÏ chän ®­îc vÞ trÝ tèi ­u nhÊt<br /> <br /> <br /> <br /> 34 V.T.T. Hµ, L.H.LËp, L.N.Th¨ng, ”Nghiªn cøu c¸c vÊn ®Ò ®Þnh tuyÕn … líp øng dông.”<br /> Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> nh»m tr¸nh hiÖn t­îng “nót th¾t cæ chai”. Tuy nhiªn, ®iÒu nµy cã thÓ dÉn ®Õn c©y<br /> bÞ lÖch. H¬n n÷a khi mét nót bÞ lçi hoÆc rêi m¹ng th× viÖc kh«i phôc l¹i c©y<br /> multicast sÏ khã kh¨n h¬n rÊt nhiÒu so víi m« h×nh mesh- first. HMTP dùa trªn<br /> mét thuËt to¸n ®Ö quy ®Ó x©y dùng c©y: Mét nót míi ®Õn sÏ liªn hÖ víi gèc cña<br /> c©y, chän nót tèt nhÊt trong sè con cña gèc, vµ lÆp ®i lÆp l¹i qu¸ tr×nh nµy tõ trªn<br /> xuèng cho ®Õn khi nã t×m thÊy mét nót cha thÝch hîp. C¸c gi¶i ph¸p nhãm<br /> (clustering) ®iÒu khiÓn ph©n t¸n nh­ NICE, SDHC, ZIGZAG t¹o thµnh c¸c nhãm<br /> ph©n cÊp, c¸c nót trong nhãm th­êng cã kho¶ng c¸ch gÇn nhau. ¦u ®iÓm cña c¸c<br /> giao thøc nhãm ph©n cÊp lµ mµo ®Çu ®iÒu khiÓn nhá vµ chi phÝ x©y dùng vµ duy tr×<br /> c©y multicast lµ thÊp.<br /> 3. X©y dùng bµi to¸n tèi ­u c©y multicast<br /> 3.1. Kh¸i niÖm c©y Multicast líp øng dông<br /> XÐt m¹ng IP nh­ ®å thÞ G=(N,E) , N lµ tËp hîp c¸c nót , vµ E lµ mét tËp hîp<br /> cña c¸c c¹nh. Mét nót  i  N biÓu thÞ router, vµ mét c¹nh  i , j  E lµ kÕt nèi vËt lý<br /> 2 chiÒu. C©y multicast qua líp øng dông o  ( s, D, N 0 , E0 ) , s lµ nót nguån ( nót<br /> cha), D lµ tËp hîp c¸c tr¹m ®Ých ( nót con) , N 0 N lµ tËp hîp c¸c nót trong m¹ng<br /> IP däc theo c¸c liªn kÕt chång phñ E 0 lµ tËp hîp c¸c liªn kÕt m¹ng phñ ®­îc ®Þnh<br /> nghÜa nh­ sau: TËp hîp c¸c m¸y chñ H 0 bao gåm s vµ D trong c©y o, nghÜa lµ<br />  <br /> H 0 s  D . Liªn kÕt chång phñ e0  d s ,0 ,...,ls , d r  E0 víi d s  H 0 , i  N 0<br /> , d r  D vµ mçi node nhËn  D cã thÓ xuÊt hiÖn mét lÇn t¹i vÞ trÝ cuèi cïng cña liªn<br /> kÕt, nh­ng cã thÓ xuÊt hiÖn nhiÒu lÇn t¹i vÞ trÝ ®Çu tiªn cña mét liªn kÕt chång phñ<br /> kh¸c. C¸c liªn kÕt chång phñ TCP hoÆc UDP ®­îc kÕt nèi bëi c¸c giao thøc líp<br /> chång phñ. C¸c router i cã thÓ xuÊt hiÖn nhiÒu lÇn trong mét liªn kÕt chång phñ<br /> e 0  E0 ,vÝ dô m¹ng chång phñ cã 6 liªn kÕt chång phñ nh­ h×nh vÏ 1 .<br /> <br /> <br /> <br /> <br /> H×nh 1. C©y multicast chång phñ qua m¹ng IP.<br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12- 2014 35<br />  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> 3.2. X©y dùng bµi to¸n tèi ­u c©y ®Þnh tuyÕn líp øng dông<br /> C©y ALM ®­îc h×nh thµnh do c¸c liªn kÕt ¶o gi÷a c¸c thiÕt bÞ ®Çu cuèi . Nót<br /> nguån göi d÷ liÖu ®Õn nót nhËn däc theo c©y multicast, mçi nót kh«ng ph¶i nót l¸<br /> nhËn ®­îc d÷ liÖu, vµ truyÒn l¹i d÷ liÖu ®Õn c¸c nót con kh¸c cïng mét lóc. C©y<br /> multicast ®­îc x©y dùng trªn líp m¹ng IP, v× vËy vÊn ®Ò lµ ph¶i gi¶m trÔ liªn kÕt lµ<br /> rÊt cÇn thiÕt. M« h×nh m¹ng multicast líp øng dông ®­îc ®­a ra tõ quan ®iÓm<br /> nh»m tèi ­u hãa ®­êng ®Þnh tuyÕn multicast. Cho v H 0 , Bin (v) ®­îc gäi lµ b¨ng<br /> th«ng cùc ®¹i cña nót v, Bout (v) b¨ng th«ng chuyÓn tiÕp tèi ®a v, Cp (V) lµ chi phÝ<br /> cña nót. Cho e E 0 , e lµ c¹nh kÕt nèi gi÷a nót u ®Õn v, C1 (u, v ) b¨ng th«ng tèi ®a<br /> mµ nót u vµ v cã thÓ ®¹t ®­îc trªn e. C2 (u, v ) lµ trÔ truyÒn gãi gi÷a hai nót,<br /> C3 (u, v ) lµ biÕn ®éng trÔ jitter, Cost (e) lµ chi phÝ mµo ®Çu.<br /> Dùa trªn m« h×nh th× bµi to¸n ®Þnh tuyÕn qua líp øng dông cã thÓ m« t¶ nh­<br /> sau: C©y multicast líp øng dông o  ( s, D, N 0 , E0 ) P tËp c¸c con ®­êng, nót nguån<br /> s ( nót cha), D lµ tËp hîp c¸c tr¹m ®Ých ( nót con), t×m mét con ®­êng p mµ ®i tõ s<br /> ®Õn D, víi p  P , sao cho chi phÝ nhá nhÊt, vµ ®¸p øng mét sè c¸c ®iÒu kiÖn rµng<br /> buéc. NÕu ë ®ã cã k ®iÒu kiÖn rµng buéc vµ hµm môc tiªu O, ®Þnh tuyÕn cã nhiÖm<br /> vô x©y dùng mét c©y tèi ­u o, sao cho chi phÝ lµ nhá nhÊt ( u, v )P Cost(u, v ) vµ ®¹t<br /> ®­îc c¸c tiªu chÝ cña hµm môc tiªu tèi ­u O, vµ tháa m·n  ( u , v )P<br /> Ci (u, v )  Ci mµ<br /> Ci  C ,1  i  k . §Ó gi¶i quyÕt c¸c vÊn ®Ò ®Þnh tuyÕn ALM môc tiªu chÝnh lµ tèi<br /> ­u c¸c tiªu chÝ vµ ®iÖu kiÖn rµng buéc. Môc tiªu tèi ­u ®­îc chia thµnh hai lo¹i :<br /> Tèi ­u nót vµ x©y dùng c©y tèi ­u, ®iÒu kiÖn rµng buéc ®­îc chia thµnh hai lo¹i :<br /> rµng buéc nót vµ c©y. ViÖc tèi ­u nót vµ rµng buéc nót lµ h­íng ®Õn c¸c nót cã<br /> thuéc tÝnh liªn quan, ch¼ng h¹n nh­ b¨ng th«ng nót, chi phÝ, ®é s©u cña c©y, vµ c¸c<br /> c©y tèi ­u vµ rµng buéc c©y b»ng c¸c ®Æc tÝnh liªn quan ®Õn c©y Multicast, ch¼ng<br /> h¹n b¸n kÝnh trÔ c©y , trÔ trung b×nh vµ chi phÝ. KÕt hîp c¸c môc tiªu tèi ­u vµ<br /> ®iÒu kiÖn rµng buéc h×nh thµnh nªn c¸c gi¶i thuËt ®Þnh tuyÕn Multicats líp phñ<br /> kh¸c nhau. C¸c thuËt to¸n ®Þnh tuyÕn multicast dùa trªn tèi ­u bao gåm RT [ 11 ]<br /> vµ dHCPS [ 12] ®­îc øng dông trong hÖ thèng luång ph­¬ng tiÖn thêi gian thùc<br /> P2P. §Ó n©ng cao chÊt l­îng dÞch vô vµ sö dông tµi nguyªn m¹ng hiÖu qu¶, thuËt<br /> to¸n ®Þnh tuyÕn líp phñ cÇn ph¶i t×m ®­îc mét con ®­êng tèi ­u hoÆc mét con<br /> ®­êng tháa m·n c¸c yÕu tè rµng buéc. HiÖu n¨ng cña c¸c thuËt to¸n ®Þnh tuyÕn<br /> ®­îc ®¸nh gi¸ dùa trªn mét sè c¸c tiªu chÝ :<br /> HiÖu qu¶ Multicast: Chñ yÕu ®­îc ph¶n ¸nh qua trÔ tõ nguån tíi ®Ých vµ b¨ng<br /> th«ng sö dông, th«ng th­êng dùa vµo mét sè c¸c tham sè trÔ<br /> Chi phÝ c©y (Tcost ) lµ tæng trÔ trªn c¸c liªn kÕt c©y. (Tcost ) thÓ hiÖn tµi nguyªn m¹ng<br /> bÞ tiªu tèn trªn c©y<br /> N 1<br /> Tcos t   Ldelay (i )<br /> i 1<br /> <br /> TrÔ c©y (Tdelay  overlay ( x, y )) lµ trÔ tõ nót x ®Õn nót y. T­¬ng tù (Tdelay  unicast ( x, y )) lµ<br /> trÔ tõ x ®Õn y ®i theo ®­êng unicast:<br /> <br /> <br /> <br /> 36 V.T.T. Hµ, L.H.LËp, L.N.Th¨ng, ”Nghiªn cøu c¸c vÊn ®Ò ®Þnh tuyÕn … líp øng dông.”<br /> Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> N 1<br /> <br /> <br /> N 1<br /> T<br /> j 1, i  j<br /> delay  overlay (i , j )<br />  i 1<br /> (<br /> N 1<br /> )<br /> Tdelay  overlay <br /> N<br /> N 1<br /> <br /> <br /> N 1<br /> T<br /> j 1, i  j<br /> delay  unicast (i , j )<br /> <br /> N 1i 1<br /> ) (<br /> Tdelay  unicast <br /> N<br /> Tû lÖ trÔ c©y multicast qua líp øng dông vµ trÔ unicast gäi lµ tû lÖ trÔ<br /> ( rdelay ) (stretch)<br /> Tdelay  overlay<br /> rdelay <br /> Tdelay  unicast<br /> <br /> T¶i liªn kÕt ( stress(Si)): Lµ sè l­îng b¶n sao gièng hÖt nhau cña mét gãi thùc hiÖn<br /> bëi mét liªn kÕt vËt lý. Stress ®­îc thÓ hiÖn hiÖu qu¶ sö dông tµi nguyªn m¹ng:<br /> L<br /> resourceusage   si xLdelay (i )<br /> i 1<br /> TÝnh thÝch nghi: Trong c¸c phiªn ALM, mçi tr¹m ®Çu cuèi cã thÓ gia nhËp hoÆc rêi<br /> bá nhãm tïy ý. Nh÷ng thay ®æi ®éng cã thÓ cã nh÷ng ¶nh h­ëng lín ®Õn cÊu tróc<br /> m¹ng. V× vËy, trong ALM mét th¸ch thøc kh¸c lµ thÝch nghi víi nh÷ng thay ®æi<br /> cña m¹ng .<br /> Mµo ®Çu ®iÒu khiÓn: Mét trong nh÷ng tham sè hiÖu n¨ng c¬ b¶n ®ª ®¸nh gi¸ gi¶i<br /> thuËt to¸n ®Þnh tuyÕn hoÆc giao thøc lµ c¸c chi phÝ cho phÇn mµo ®Çu ®iÒu khiÓn,<br /> do ®ã sù c©n b»ng gi÷a c¸c tham sè hiÖu n¨ng ®Þnh tuyÕn vµ chi phÝ ®iÒu khiÓn ®Ó<br /> ®¹t ®­îc hiÖu n¨ng ®ã sÏ ®­îc xem xÐt trong c¸c thuËt to¸n ®Þnh tuyÕn multicast.<br /> Rctrl ( N )  Rmu ( N )  Rtu ( N ) trong ®ã Rmu (N ) chi phÝ ®Ó ®¹t ®­îc c¸c tham sè hiÖu<br /> n¨ng; Rtu (N ) chi phÝ cËp nhËt sù thay ®æi cÊu tróc m¹ng.<br /> 4. so s¸nh hiÖu n¨ng cña c¸c giao thøc ®Þnh tuyÕn ALM<br /> Bµi b¸o kh¶o s¸t vµ so s¸nh 2 giao thøc NICE [5] vµ ZIGZAG[4]. NICE lµ hÖ<br /> thèng phæ biÕn nhÊt sö dông c¸ch tiÕp cËn dùa trªn c©y. NICE lµ tõ (The Internet<br /> Cooperative Environment) ®· ®Ò xuÊt ph­¬ng thøc x©y dùng xÕp chång hoµn toµn<br /> kh¸c so víi c¸c giao thøc tr­íc ®©y. Nã lµ mét khung lµm viÖc hîp t¸c sö dông<br /> thuËt to¸n ph©n t¸n qua ®ã c¸c nót ®­îc tù tæ chøc thµnh ph©n cÊp cao-thÊp (top-<br /> bottom). Mçi thµnh viªn ph¶i gia nhËp líp thÊp nhÊt vµ giao thøc nhãm ph©n t¸n t¹i<br /> mçi líp ph©n chia nh÷ng thµnh viªn nµy thµnh mét tËp c¸c nhãm. ChØ mét nót cña<br /> mçi nhãm cã thÓ ®­îc bÇu lµm chñ nhãm ®Ó gia nhËp vµo líp cao h¬n kÕ tiÕp.<br /> Th«ng th­êng, chñ nhãm sÏ n»m t¹i vÞ trÝ trung t©m cña nhãm vÒ mÆt ®Þa lý. Líp 0<br /> chøa tÊt c¶ c¸c nót, trong khi ®ã líp cao nhÊt chØ chøa mét tr¹m ®Çu cuèi. ThiÕt kÕ<br /> ph©n líp lµm ®¬n gi¶n viÖc qu¶n lý thµnh viªn vµ gióp nã më réng quy m« tèt h¬n.<br /> Gièng nh­ Narada, NICE sö dông RP ®Ó gióp khëi t¹o c¸c thµnh viªn míi. §Çu<br /> tiªn, thµnh viªn míi gia nhËp liªn hÖ víi RP, RP göi cho mét danh s¸ch tÊt c¶ c¸c<br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12- 2014 37<br />  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> thµnh viªn cña líp cao nhÊt. B»ng viÖc th¨m dß mçi thµnh viªn trong danh s¸ch<br /> nµy, thµnh viªn míi sÏ t×m thµnh viªn gÇn nhÊt vµ liªn hÖ víi thµnh viªn nµy ®Ó<br /> nhËn ®­îc b¶n danh s¸ch tÊt c¶ c¸c thµnh viªn cña nhãm cã s½n kh¸c ë líp thÊp<br /> h¬n. TiÕn tr×nh nµy lÆp ®i lÆp l¹i cho ®Õn khi thµnh viªn míi (tr¹m ®Çu cuèi míi)<br /> gia nhËp nhãm x¸c ®Þnh t¹i líp thÊp nhÊt, gäi lµ líp 0. H¬n n÷a, mçi chñ nhãm t¹i<br /> mét líp bÊt kú ph¶i kiÓm tra ®Þnh kú kÝch cì cña nhãm. NÕu kÝch cì cña nhãm v­ît<br /> mét ng­ìng x¸c ®Þnh th× nã sÏ tù chia thµnh hai nhãm con cã kÝch cì b»ng nhau.<br /> NÕu kÝch cì nhãm rÊt nhá so víi ng­ìng ®· x¸c ®Þnh, nã sÏ kÕt hîp víi nhãm cã<br /> kÝch cì nhá h¬n kh¸c ®Ó t¹o thµnh nhãm lín h¬n. §Ó chuyÓn tiÕp d÷ liÖu, mçi<br /> thµnh viªn sÏ sao chÐp vµ chuyÓn c¸c gãi nhËn ®­îc tíi c¸c nhãm l©n cËn cña nã<br /> mµ t¹i líp ®ã nã lµ thµnh viªn cña nhãm. Trong c¬ chÕ chuyÓn tiÕp nµy, tr¹m NICE<br /> cã thÓ cã O (k logkN ) nót däc theo tuyÕn d÷ liÖu cña nã.<br /> <br /> <br /> <br /> <br /> H×nh 2. KiÕn tróc c¸c tr¹m cuèi s¾p xÕp trong NICE[5].<br /> Tuy nhiªn, mçi thµnh viªn míi gia nhËp nhãm ph¶i dù ®o¸n trÔ ®Çu cuèi tõ líp<br /> bªn trªn ®Õn líp thÊp nhÊt. NICE ®­îc chØ ra lµ cã kh¶ n¨ng më réng quy m« tèt vµ<br /> mét trong nh÷ng môc tiªu chÝnh ®Ó thiÕt kÕ hÖ thèng ph©n phèi néi dung cã kh¶<br /> n¨ng më réng quy m«.<br /> ZIGZAG [3,4] ®· ®­îc ®Ò nghÞ bëi tr­êng ®¹i häc Central Florida vµ ®Ó c¶i<br /> thiÖn giao thøc NICE. Tæ chøc c©y rÊt gièng víi mét trong nh÷ng ®Ò xuÊt cña<br /> NICE. C¸c thuËt to¸n ®Ó x©y dùng cÊu tróc vµ duy tr× kh¸ gièng NICE vµ tÊt c¶ c¸c<br /> thuéc tÝnh cÊu tróc cña NICE vÉn cßn hiÖu lùc. Tæ chøc ZIGZAG nhËn vµo mét hÖ<br /> thèng c¸c côm vµ x©y dùng c©y munlticast trªn hÖ thèng ph©n cÊp nµy theo mét bé<br /> quy t¾c ®­îc gäi lµ quy t¾c C. Mét côm cã mét nót ®øng ®Çu vµ mét nót ®Ó liªn<br /> kÕt. Nót ®øng ®Çu chÞu tr¸ch nhiÖm gi¸m s¸t c¸c thµnh viªn cña nhãm vµ nót liªn<br /> kÕt chÞu tr¸ch nhiªm truyÒn t¶i nh÷ng néi dung cho c¸c thµnh viªn trong nhãm. V×<br /> vËy nÕu nót ®øng ®Çu bÞ lçi kh«ng ¶nh h­ëng ®Õn tÝnh liªn tôc dÞch vô cña c¸c<br /> thµnh viªn kh¸c hoÆc trong tr­êng hîp nót liªn kÕt t¸ch ra, thµnh viªn ®øng ®Çu vÉn<br /> cßn ho¹t ®éng vµ cã thÓ chØ ®Þnh mét ®Çu liªn kÕt míi nhanh chãng. Trong khi ë<br /> NICE tÊt c¶ mäi thø ®­îc chuyÓn tiÕp bëi c¸c nót ®øng ®Çu nhãm. Chi phÝ mµo ®Çu<br /> cña ZIGZAG lµ thÊp. N¬i nhËn cÇn trao ®æi th«ng tin ®iÒu khiÓn tíi O(LogN) víi<br /> c¸c ®Çu cuèi kh¸c trong tr­êng hîp xÊu nhÊt. ZIGZAG tËp trung vµo nguån ph­¬ng<br /> tiÖn truyÒn th«ng trùc tuyÕn.<br /> Sö dông phÇn mÒm OverSim[11], tiÕn hµnh so s¸nh hiÖu n¨ng gi÷a NICE vµ<br /> ZIGZAG qua hai tham sè trÔ stretch vµ stress. KÕt qu¶ cho thÊy giao thøc ZIGZAG<br /> cã kh¶ n¨ng phôc håi lçi tèt h¬n so víi NICE v× ZIGZAG ®· t¸ch biÖt nót chÞu<br /> tr¸ch nhiÖm ®iÒu khiÓn vµ nót chÞu tr¸ch nhiÖm truyÒn th«ng multicast. Tuy nhiªn<br /> c¶ hai giai thøc ®Òu tÝnh hµm chi phÝ dùa vµo trÔ ®­îc ®o b»ng lÖnh ping ®Ó tèi ­u<br /> <br /> <br /> 38 V.T.T. Hµ, L.H.LËp, L.N.Th¨ng, ”Nghiªn cøu c¸c vÊn ®Ò ®Þnh tuyÕn … líp øng dông.”<br /> Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> c©y Multicast, mµ kh«ng xÐt c¸c yÕu tè kh¸c nh­ sù ®ãng gãp cña c¸c nót<br /> tr­ëng nhãm, nót liªn kÕt, chÊt l­îng yªu cÇu cña c¸c dÞch vô, b¨ng th«ng s½n<br /> cã cña c¸c nót.<br /> <br /> <br /> <br /> <br /> Hình 3. Stress với xác xuất lỗi. Hình 4. Stretch với xác xuất lỗi.<br /> <br /> 4. KÕt luËn<br /> Bµi b¸o ®· ph©n tÝch c¸c vÊn ®Ò cÇn quan t©m khi tèi ­u c©y ®Þnh tuyÕn ALM.<br /> §Þnh tuyÕn tèi ­u lµ t×m ra ®­îc mét con ®­êng tháa m·n tèi ­u tham sè hiÖu n¨ng<br /> mµ chi phÝ cho mµo ®Çu ®iÒu khiÓn lµ nhá nhÊt. Nh­ng trong øng dông thùc tÕ, ®Ó<br /> ®¹t ®­îc tÊt c¶ c¸c tiªu chÝ lµ rÊt khã. C¸c øng dông ®a ph­¬ng tiÖn cã c¸c yªu cÇu<br /> kh¸c nhau vÒ b¨ng th«ng, ®é trÔ vµ biÕn ®éng trÔ cho tõng lo¹i dÞch vô. VÊn ®Ò cña<br /> ®Þnh tuyÕn multicast rÊt phøc t¹p vµ cã rÊt nhiÒu c¸c nghiªn cøu ®· ®­a ra c¸c gi¶i<br /> thuËt tèi ­u, tuy nhiªn c¸c nghiªn cøu ®Òu míi dõng ë tèi ­u 1 tiªu chÝ, ch¼ng h¹n<br /> nh­ chi phÝ b¨ng th«ng m¸y chñ vµ kh¶ n¨ng më réng cña hÖ thèng [7], trÔ liªn kÕt<br /> [8], vµ chi phÝ c©y multicast [9]. Tõ quan ®iÓm cña ng­êi dïng, tèi ­u hãa mét<br /> tiªu chÝ, ch¼ng h¹n nh­ chi phÝ c©y, cã thÓ kh«ng ®¶m b¶o chÊt l­îng tr¶i nghiÖm<br /> tèt cña ng­êi dïng. Trong nghiªn cøu tiÕp theo chóng t«i sÏ nghiªn cøu ®Ò xuÊt<br /> mét hµm chi phÝ cã tÝnh ®Õn trÔ, b¨ng th«ng ®ãng gãp vµ b¨ng th«ng s½n cã cña c¸c<br /> nót vµ yªu cÇu QOS cña dÞch vô. Tèi ­u gi÷a chi phÝ vµ hiÖu n¨ng dùa vµo phÇn<br /> mµo ®Çu ®iÒu khiÓn. TriÓn khai ®¸nh gi¸ so s¸nh trªn hai giao thøc NICE vµ<br /> ZIGZAG.<br /> Tµi liÖu tham kh¶o<br /> [1]. R. Besharati, M. Bag-Mohammadi, and M. A. Dezfouli, “A Topology-aware<br /> Application Layer Multicast Protocol,” in Proc. CCNC 2010.<br /> [2]. D. Pendarakis, S. Shi, D. Verma, and M. Waldvogal, “ALMI:an application level<br /> multicast infrastructure,” Proc. 3rd USITS, 2001, pp.49-60.<br /> [3]. M. Hosseini, D. T. Ahmed, S. Shirmohammadi, and N. D.Georganas, “A survey<br /> of application-layer multicast protocols,"IEEE Communications Surveys &<br /> Tutorials, vol. 9, no. 3, pp.5874, 2007.<br /> [4]. Duc A. Tran, Kien A. Hua, and Tai T. Do. Zigzag, “An efficient peer-to-peer<br /> scheme for media streaming,” IEEE INFOCOM’03, April 2003<br /> [5]. S. Banerjee, B. Bhattacharjee. “Analysis of the NICE Application Layer<br /> Multicast Protocol” [R]: Department of Computer Science, University of<br /> Maryland, College Park, UMIACSTR 2002-60 and CS-TR 4380, June 2002.<br /> [6]. Chen Liangbin,Li Qiang , Feng Xiang “Research on Multicast Routing Algorithm<br /> for P2P Overlay Network,” Proceedings of the 2nd International Conference on<br /> Computer Science and Electronics Engineering (ICCSEE 2013)<br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12- 2014 39<br />  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> [7]. T. Small, B. Li, and B. Liang, “Outreach: Peer-To-Peer Topology Construction<br /> towards Minimized Server Bandwidth Costs,” IEEE Journal on Selected Areas in<br /> Communications, 2007, pp.35-45<br /> [8]. F. Wang, Y. Xiong, and J. Liu, "mTreebone: A Hybrid Tree/Mesh Overlay for<br /> Application-Layer Live Video Multicast," Proc. ICDCS, 2007<br /> [9]. D. Ren, Y.-T. Hillman Li, and S.-H. Gary Chan, “On Reducing Mesh Delay for<br /> Peer-to-Peer Live Streaming,” Proc. INFOCOM, 2008, pp.1058-1066.<br /> [10]. D.A. Helder and S. Jamin, “End-Host Multicast Communication Using Switch-<br /> Trees Protocols,” in Proc. IEEE/ACM International Symposium on Cluster,<br /> Cloud, and Grid Computing (CCGRID), 2002, pp.419-424.<br /> [11]. OMNeT++ Community Site (2012), “OMNET++ Discrete Event Simulation<br /> System [Online]”, Available http://www.omnetpp.org/<br /> abstract<br /> Research on Multicast Routing for Aplication layer<br /> <br /> Application Layer Multicast has many advantages compared to the IP<br /> multicast [1]. First, it is easy deployment and low cost, ALM requires only class IP<br /> platform supports unicast communication functions do not need to change the IP<br /> network infrastructure is available. Second, it is flexible. Third, it is suitable for<br /> deployment in large -scale networks such as the Internet. The main objective of<br /> Multicast routing is the optimal multicast tree construction to meet quality of<br /> service requirements. This paper analyzes and synthesis of routing problems, the<br /> optimal solution for ALM routing trees and provide direction for further research<br /> to improve the performance multicast routing protocol the QOS requirements of<br /> service .<br /> Keywords: Overlay network; multicast routing; algrithm,Application layer multicats-ALM<br /> <br /> <br /> <br /> <br /> NhËn bµi ngµy 11 th¸ng 05 n¨m 2014<br /> Hoµn thiÖn ngµy 02 th¸ng 10 n¨m 2014<br /> ChÊp nhËn ®¨ng ngµy 04 th¸ng 12 n¨m 2014<br /> <br /> <br /> <br /> <br /> §Þa chØ: Häc viÖn C«ng nghÖ B­u chÝnh ViÔn th«ng, 122 Hoµng Quèc ViÖt, Hµ Néi, ViÖt Nam,<br /> E-mail: havt@ptit.edu.vn; Sè ®iÖn tho¹i: 0915054369.<br /> <br /> <br /> <br /> <br /> 40 V.T.T. Hµ, L.H.LËp, L.N.Th¨ng, ”Nghiªn cøu c¸c vÊn ®Ò ®Þnh tuyÕn … líp øng dông.”<br />