Một thuật toán gen cho thiết kế topology mạng có khả năng hồi phục

In network designing phase, one of QoS problems is designing survivable networks to assure that services are not disrupted when a failure happens. On an ATM, MPLS, GMPLS based-on network techonologies, there are many approaches for designing survivable networks. This paper introduces a genetic algorithm for topological design of survivable networks by a repetitively-restorable method.
Nội dung trích xuất từ tài liệu:
Một thuật toán gen cho thiết kế topology mạng có khả năng hồi phục’Tap ch´ Tin hoc v` Diˆu khiˆ n hoc, T.23, S.1 (2007), 59—70ıee.. a `.´´ˆˆ´ˆˆMOT THUAT TOAN GEN CHO THIET KE TOPOLOGY..`’ ˘´ˆMANG CO KHA NANG HOI PHUC..˜´ˆ´ˆˆNGUYEN QUY MINH HI` N, PHAM QUOC HUYE.Viˆn Khoa hoc K˜ thuˆt Bu.u diˆneyae....Abstract. Today, telecommunication technologies and services are deploying rapidly in NGN (NextGeneration Network) networks. Quality of Service (QoS) problems in NGN networks are addressed innetwork designing, deploying, maintaining phases. In network designing phase, one of QoS problemsis designing survivable networks to assure that services are not disrupted when a failure happens. Onan ATM, MPLS, GMPLS based-on network techonologies, there are many approaches for designingsurvivable networks. This paper introduces a genetic algorithm for topological design of survivablenetworks by a repetitively-restorable method.’´`T´m t˘t. Hiˆn nay, v´.i viˆc triˆ n khai cˆng nghˆ mang NGN, c´c dich vu thˆng tin truyˆn thˆngoaeoeeoe .a .eo.... o.o.c ph´t triˆ n rˆ t nhanh ch´ng v´.i nhiˆu loai h` dich vu. Mˆt trong nh˜.ng vˆ n dˆ d˘t ra’ ´`´ e .dang du .ae aooeınh .oua ` a...’´ ´´’’ a’’ad´ l` cˆn phai thiˆt kˆ, triˆ n khai mang c´ kha n˘ng dam bao chˆ t lu.o.ng dich vu cho c´c loai dicho a `ae eeoa.... ..’´´ ´ouao ovu triˆ n khai trˆn d´. Mˆt trong nh˜.ng yˆu cˆu vˆ chˆ t lu.o.ng dich vu d˘t ra dˆi v´.i viˆc thiˆt kˆee oe ` ` aa e ´ee e...... .’`´´’ o’ a’ao a .oe ’a .oamang, d´ l` mang phai c´ kha n˘ng hˆ i phuc dˆ dam bao cung cˆ p dich vu v´.i chˆ t lu.o.ng nhu. d˜.....i kh´ch h`ng ngay trong nh˜.ng tru.`.ng ho.p mang c´ su. cˆ. Trˆn co. so. c´c cˆng nghˆ´´’ a ocam kˆt v´e oaauoeo . oe...’``´ .’’ a’oe aue a e ’omang nhu. ATM, MPLS, GMPLS, c´ nhiˆu c´ch th´.c tiˆp cˆn dˆ dam bao kha n˘ng hˆ i phuc cua..`´ ´’ amang. B`i b´o n`y gi´.i thiˆu mˆt thuˆt to´n thiˆt kˆ topology v´.i kha n˘ng hˆ i phuc du.a trˆna a aoeoaae eooe......```a oeeoophu.o.ng ph´p hˆ i phuc l˘p trˆn nhiˆu du.`.ng hˆ i phuc.. a..´.ˆ1. GIO I THIEU.’ ´ e´’aTrˆn mang trong qu´ tr` khai th´c c´ thˆ xuˆ t hiˆn nh˜.ng su. cˆ gˆy tro. ngai cho qu´ea ınha o e au. o a...’`´ .´p dich vu. Nh˜.ng su. cˆ c´ thˆ l` d´.t c´p, mˆ t nguˆ n diˆn, hong h´c thiˆt bi,´ o e a u a´’eoetr` cung cˆ .ınhauao... o’ ’`´´`’n˘ m ngo`i su. diˆu khiˆn cua ngu.`.i vˆn h`nh. Mˆt sˆ su. cˆ kh´c n˘ m trong diˆu h`nh cuaaa . `o a ao o . o a `aeee a...`.i d´ l` kho.i dˆng, cˆ u h` lai hˆ thˆng, nˆng cˆ p hˆ thˆng, mˆ t diˆu khiˆn hˆ thˆng.’ e o´ ınh . e o´´ e o´´ `´’ oaaaaeengu o o a....’´´´´´oa o eaooe a . o uuNh˜.ng su. cˆ nhu. vˆy c´ thˆ quy th`nh hai nh´m: su. cˆ tuyˆn v` su. cˆ n´t. Nh˜.ng su. cˆu.... o. cˆ dˆ n dˆn tuyˆn l`m viˆc khˆng ch´ x´c ho˘c ng`.ng c´c luˆ ng thˆng˜ e`´´ ’aooe aeoınh aautuyˆn xay ra khi su o a ´e. ´..´´ e a e .´o uaue oe u o atin trˆn tuyˆn. Nh˜.ng su. cˆ n´ t xuˆt hiˆn gˆy nˆn su. ng`.ng trˆ thˆng tin trˆn n´t d´ v`eeu...’ ´ e o`´`´ ´ ´ ´o e ae .ocho c´c tuyˆn kˆt nˆi dˆn n´t n`y. Thu.c tˆ trˆn mang c´ thˆ xuˆ t hiˆn dˆ ng th`.i nhiˆu su.ae e o e u a. e e...i hai su. cˆ trˆn mang l` rˆ t thˆ p. Ch´ v` vˆy`´´´ e o´´´cˆ, tuy nhiˆn, x´c suˆ t xuˆ t hiˆn dˆ ng th`oeaaao ea aaınh ı ao....˜’´´´` o a’’e u aaee . oe .oo ephˆn l´.n c´c nghiˆn c´.u tˆp trung v`o viˆc giai quyˆt su. cˆ theo gia thiˆt tai mˆi th`.i diˆ ma..´’ o o . ochı c´ mˆt su. cˆ..’’’`´’ a oaeuMˆt chiˆn lu.o.c hˆ i phuc c´ thˆ triˆn khai o. c´c l´.p kh´c nhau theo quan diˆm giao th´.coe. o. o e e.. hˆ i phuc tai l´.p vˆt l´, kˆt nˆi, mang ho˘c dˆ ng th`.i trˆn nhiˆu l´.p. Tai mˆi˜``´ ´` oa oeo emang OSI nhu o. . o a y e o.... o..p, c´c chiˆn lu.o.c hˆ i phuc c´ nh˜.ng d˘c t´ kh´c nhau. V´.i l´.p vˆt l´, c´c chiˆn lu.o.c`´´a ınh ao ol´oaeoa y ae... o u..˜´ˆ´ˆˆNGUYEN QUY MINH HI` N, PHAM QUOC HUYE.60```´´’oaaehˆ i phuc c´ th`.i gian hˆ i phuc nhanh nhˆ t khoang 50ms. C´c chiˆn lu.o.c hˆ i phuc tai l´.po.. o. . o. o o.`.ng d`ng cho c´c mang hu.´.ng kˆt nˆi nhu. ATM v` MPLS. C´c kiˆn tr´c mang´ ´´´ ´uaoe oaaeukˆt nˆi thu oe o..’’’n mach nh˜n thiˆt lˆp du.`.ng dˆ n chuyˆ n mach nh˜n LSP (Label Switch Path) chuyˆ n˜´ aoaeaechuyˆeae ....u lu.o.ng gi˜.a n´ t nguˆ n v` d´.o.c tai l´.p n`y l` hˆ i phuc``´´u uo a ıch. Muc tiˆu cua c´c chiˆn lu . . o a a oe ’ aetiˆp lue....u lu.o.ng trˆn c´c LSP m` bi anh hu.o.ng bo.i su. cˆ. C´c chiˆn lu.o.c hˆ i phuc tai l´.p`´ a´`’’ . oe aa . ’ephˆn lua.. o. . o’`´ ´`’ .’oaaaaaekˆt nˆi c´ nhiˆu diˆ m linh hoat nhu. khˆng phˆn nho mang th`nh c´c phˆn nho ho.n ho˘ce o oe..’´ a´´’’’’ o akhˆng phai gia thiˆt r˘ ng topology cua mang phai c´ cˆ u tr´c. C´c tuyˆn v` c´c n´ t c´ thˆoe `uae a a u o e..o.c hˆ i phuc. Su. dung c´c thuˆt to´n hoach dinh tru.´.c, thu.`.ng d`ng`´’ .tham gia trong chiˆn lu . oeaaaoou.....c tˆt nhˆ t dinh tuyˆn lu.u lu.o.ng khi c´ su. cˆ xay ra, v´ du nhu. trong’´´´a .o . o ’ı .dˆ x´c dinh c´ch th´ oe a .au ´e.’’`´n lu.o.c hˆ i phuc du.`.ng, s˜ su. dung mˆt du.`.ng kh´c dˆ chuyˆn lu.u lu.o.ng khi xay ra su.’ .’oeoa eoechiˆe.. o....i gian cho viˆc dinh tuyˆn lai lu.u lu.o.ng trong tru.`.ng ho.p th´. nhˆ t l´.n´´´e .ou a ocˆ mang. M˘c d` th`o .a u oe .....`´’ho.n tru.`.ng ho.p th´. hai, nhu.ng c´c phu.o.ng ph´p trong [2, 5, 8, 12] chı ra r˘ ng hiˆu suˆ t su.oaaaea ’u...p kˆt nˆi l´.n ho.n d´ng kˆ so v´.i khi hˆ i phuc tai l´.p vˆt l´.’``odung b˘ng thˆng hˆ i phuc ...