intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Luận văn thạc sĩ: Xây dựng chương trình tối ưu hóa quá trình định tuyến trên mạng IP dựa vào giải thuật di truyền

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:26

127
lượt xem
16
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xây dựng chương trình tối ưu hóa quá trình định tuyến trên mạng IP dựa vào giải thuật di truyền nhằm giảm thiểu chi phí và nâng cao chất lượng dịch vụ Iternet .

Chủ đề:
Lưu

Nội dung Text: Luận văn thạc sĩ: Xây dựng chương trình tối ưu hóa quá trình định tuyến trên mạng IP dựa vào giải thuật di truyền

  1. B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG HUỲNH NGUY N NG C TH O XÂY D NG CHƯƠNG TRÌNH T I ƯU HÓA QUÁ TRÌNH Đ NH TUY N TRÊN M NG IP D A VÀO GI I THU T DI TRUY N Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011
  2. Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TSKH. Tr n Qu c Chi n Ph n bi n 1: PGS.TS. Phan Huy Khánh Ph n bi n 2: PGS.TS. Đoàn Văn Ban Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 11 tháng 09 năm 2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng
  3. 1 M Đ U 1. Lý do ch n ñ tài Khi t m t máy tính này ñ n m t máy tính khác và t m ng này ñ n m t m ng khác cũng ngày càng tr nên ph c t p. Nh m ñáp ng các nhu c u h t s c ña d ng và phong phú c a ngư i s d ng Internet, các nhà c Internet ngày càng phát tri n thì v n ñ ñ nh tuy n lưu lư ng ung c p d ch v m ng c n s d ng m t cách hi u qu cơ s h t ng m ng c a mình ñ có th ñưa ra các d ch v v i ch t lư ng cao mà không c n ph i nâng c p thi t b ph n c ng nh m gi m thi u chi phí, vì v y c n ph i có gi i pháp nh m khai thác m t cách t t nh t thi t b h t ng m ng, mà ñi n hình là vi c cho phép cân b ng t i tr ng trên t t c các k t n i, tránh tình tr ng ñư ng truy n này thì r nh trong khi các ñư ng truy n khác l i b t c ngh n ñi u này ñòi h i c n ph i có các nghi th c truy n thông ho t ñ ng m t cách hi u qu , ñây chính là m c tiêu c a vi c t i ưu hóa quá trình ñ nh tuy n trên m ng. Đó là lý do tôi ch n ñ tài: “Xây d ng chương trình t i ưu hóa quá trình ñ nh tuy n trên m ng IP d a vào gi i thu t di truy n”. 2. M c ñích nghiên c u Vi c nghiên c u và ñ xu t ñ tài này ñ gi m thi u chi phí và nâng cao ch t lư ng d ch v Internet trong hoàn c nh ngày càng có nhi u d ch v m i ra ñ i chi m d ng băng thông l n như hi n nay. 3. Đ i tư ng và ph m vi nghiên c u S phát tri n c a Internet cũng ñ ng nghĩa v i vi c tăng trư ng v quy mô và công ngh nhi u lo i m ng LAN, WAN… và
  4. 2 ñ c bi t là lưu lư ng thông tin trên m ng tăng ñáng k . Chính ñi u ñó ñã làm cho v n ñ ñi u ph i lu ng thông tin trên m ng hay là v n ñ ñ nh tuy n tr nên quan tr ng hơn bao gi h t. Trong vi c thi t k m ng vi c l a ch n giao th c ñ nh tuy n sao cho phù h p v i chi phí, tài nguyên c a t ch c là ñ c bi t quan tr ng. Internet phát tri n càng m nh, lư ng ngư i truy nh p càng tăng yêu c u ñ nh tuy n càng ph i tin c y, t c ñ chuy n m ch nhanh và không gây ra l p và m t d li u trên m ng. Hơn n a khi nhi u t ch c tham gia vào m ng thì nhi u giao th c ñư c ñưa vào s d ng d n ñ n s ph c t p v ñ nh tuy n cũng gia tăng, và s lư ng các giao th c ñ ph c v cho vi c ñ nh tuy n cũng có r t nhi u.Vi c hi u bi t và thi t k các m ng thông tin c l n có s d ng các thi t b ñ nh tuy n ñang tr thành m t nhu c u vô cùng c p thi t trong th c t . Nó ñòi h i ngư i thi t k m ng ph i có s hi u bi t sâu v giao th c s s d ng cho vi c thi t k m ng cũng như các lo i giao th c ñ nh tuy n khác. 4. Phương pháp nghiên c u Phương pháp nghiên c u tư li u: Các tài li u mà giáo viên hư ng d n ñưa, trên các trang web và các bài báo khoa h c g n ñây có liên quan ñ n ñ tài, sách giáo trình, tài li u tham kh o, t p chí khoa h c, các ñ tài nghiên c u có liên quan… 5. Ý nghĩa khoa h c Quá trình t i ưu c n ñưa ra m t gi i pháp nh m ñáp ng t t nh t nhu c u truy n thông là quá trình ch n l c các tuy n ñư ng nh m tìm ra m t b tr ng s thích h p. Đ i v i nh ng m ng nh chúng ta có th gi i ñư c bài toán m t cách nhanh chóng b ng
  5. 3 phương pháp quy ho ch tuy n tính, tuy nhiên, ñ i v i các m ng l n (s lư ng b ñ nh tuy n lên ñ n hàng nghìn, hàng v n) thì phương pháp quy ho ch tuy n tính h u như không kh thì. Vì v y, ñ tài này s nêu ra m t phương pháp m i áp d ng gi i thu t di truy n (Genetic Algorithm -GA) ñ tìm ra m t b các tr ng s t i ưu s ñư c gán vào cho các thi t b ñ nh tuy n. 6. C u trúc lu n văn V i ñ nh hư ng như trên, ngoài ph n M ñ u và ph n K t lu n và hư ng phát tri n, lu n văn g m 3 chương: Chương 1: T ng quan v ñ nh tuy n m ng Chương 2: Bài toán ư c lư ng nhu c u truy n thông Chương 3: T i ưu hóa quá trình ñ nh tuy n m ng b ng gi i thu t di truy n.
  6. 4 CHƯƠNG 1 T NG QUAN V Đ NH TUY N M NG 1.1. CÁC KHÁI NI M CƠ B N 1.1.1. H th ng t tr (Autonomous System - AS) Internet toàn c u ñư c t ch c theo t ng kh i riêng l , ho t ñ ng tương ñ i ñ c l p v i nhau g i là nh ng h th ng t tr (Autonomous System - AS). M i AS bao g m m t ho c m t s nhóm các ñ a ch IP, m i nhóm tư ng trưng cho m t m ng con, s d ng chung m t chính sách c th , rõ ràng cho vi c ñ nh tuy n và cũng ho t ñ ng dư i s ki m soát c a m t t p th các chuyên gia ñi u hành m ng. Công vi c thi t k m ng thư ng ñư c gi i h n trong ph m vi m t h th ng t tr AS. Có th nh n th y rõ r ng, n u các AS cũng ñư c xây d ng và v n hành theo m t phương th c thì toàn b h th ng Internet s ho t ñ ng t t hơn v i chi phí th p và hi u su t cao, tuy nhiên th c t l i hoàn toàn không ph i như v y, m i AS hay ngay c trong t ng m ng con c a m t AS cũng thư ng ñư c xây d ng và v n hành m t cách ñ c l p v i nhau, ch nh ng nơi nào c n thi t m i có nh ng h p ñ ng, th a thu n nh m ñ m b o chúng k t n i ñư c v i nhau. 1.1.2. Ðư ng ñi t i ưu cơ b n 1.2. T NG QUAN V Đ NH TUY N M NG 1.2.1. Khái ni m ñ nh tuy n m ng Đ nh tuy n (routing) là quá trình ch n l a các ñư ng ñi trên m t m ng máy tính ñ g i d li u qua ñó.
  7. 5 Đ nh tuy n m ng ñư c dùng trong lĩnh v c truy n thông Internet ñ ch quá trình g m hai thao tác: xác ñ nh ñư ng truy n (path determination) và chuy n gói tin (forwarding) theo con ñư ng ñã ch n, hai thao tác này luôn luôn ñi kèm v i nhau trong thi t b ph n c ng chuyên dùng ñư c g i là b ñ nh tuy n (router). Trong các m ng thông tin khác nhau, vi c xác ñ nh ñư ng truy n cũng di n ra khác nhau. Tuy nhiên, cách xác ñ nh ñư ng truy n nào cũng g m hai công vi c cơ b n : Th nh t, là thu th p và phân phát thông tin v tình tr ng c a m ng (như tr ng thái ñư ng truy n, tình tr ng t c ngh n...) và c a thông tin c n truy n (như lưu lư ng, băng thông, t c ñ , yêu c u d ch v ...). Các thông tin này s ñư c s d ng làm cơ s cho vi c xác ñ nh ñư ng truy n. Th hai, là vi c phân tích, tính toán ñ ch n ra ñư ng truy n kh d ng (cũng có th là ñư ng truy n t i ưu) d a trên các thông tin tr ng thái trên. Đư ng truy n kh d ng là ñư ng truy n tho mãn m i yêu c u c a thông tin c n truy n (như t c ñ , băng thông) và ñi u ki n c a m ng (như kh năng c a ñư ng truy n). Còn ñư ng truy n t i ưu (theo m t tiêu chu n nào ñó) là ñư ng truy n t t nh t trong nh ng ñư ng truy n kh d ng. 1.2.2. Phân lo i ñ nh tuy n m ng 1.2.2.1. Đ nh tuy n tĩnh Đ nh tuy n tĩnh là d ng ñ nh tuy n mà các thông tin v ñư ng ñi ph i do ngư i qu n tr m ng nh p cho router. Khi c u trúc m ng có b t kỳ thay ñ i nào thì chính ngư i qu n tr m ng ph i xoá ho c thêm các thông tin v ñư ng ñi cho router. Các ñư ng ñi này là c ñ nh nên trong h th ng m ng l n vi c b o trì b ng ñ nh tuy n cho
  8. 6 router t n r t nhi u th i gian. Đ nh tuy n tĩnh là cách ñ nh tuy n không linh ho t, không có kh năng t thích nghi khi các ñi u ki n truy n thông thay ñ i nên thư ng phù h p v i h th ng m ng nh ho c tuy n ñơn ít có bi n ñ i v thông tin ñ nh tuy n. 1.2.2.2. Đ nh tuy n ñ ng Đ nh tuy n ñ ng là d ng ñ nh tuy n mà các ñư ng ñi ñư c t ñ ng c p nh t b i router, vi c l a ch n tuy n ñư ng d a trên thông tin tr ng thái hi n th i c a m ng. Thông tin tr ng thái có th ño ho c d ñoán và tuy n ñư ng có th thay ñ i khi topo m ng ho c lưu lư ng m ng thay ñ i. Thông tin ñ nh tuy n ñư c c p nh t t ñ ng vào trong các b ng ñ nh tuy n c a các node m ng tr c tuy n, và ñáp ng tính th i gian th c nh m tránh t c ngh n cũng như t i ưu hi u năng m ng. Đ nh tuy n ñ ng có th thích ng v i vi c thay ñ i ki n trúc m ng và lưu lư ng truy n thông, phù h p ñ i v i m ng l n, thư ng bi n ñ i trong quá trình ho t ñ ng. Chính vì ñ nh tuy n tĩnh ñòi h i ngư i qu n tr m ng ph i c u hình m i thông tin v ñư ng ñi cho router nên nó không có ñư c tính linh ho t như ñ nh tuy n ñ ng. Trong nh ng h th ng m ng l n, ñ nh tuy n tĩnh thư ng ñư c s d ng k t h p v i giao th c ñ nh tuy n ñ ng cho m t s m c ñích ñ c bi t. 1.2.3. Các giao th c ñ nh tuy n m ng 1.2.3.1. Đ nh tuy n theo ñư ng ñi ng n nh t Đ ch n m t tuy n ñư ng ñi gi a hai b ñ nh tuy n, thu t toán ch c n tìm ra ñư ng ñi ng n nh t gi a chúng trên ñ th . Khái ni m ñư ng ñi ng n nh t ñây có m t s v n ñ c n ph i làm rõ. M t cách ñ ño ñ dài ñư ng ñi là s lư ng các nút mà nó ñi qua (còn ñư c g i là s bư c nh y). Bên c nh các ñ ño s
  9. 7 bư c nh y và kho ng cách ñ a lý, m t s ñ ño khác cũng có th ñư c s d ng. Ví d , m i cung có th ñư c gán nhãn tương ng v i ñ tr trung bình c a các gói tin do ph i x p hàng ñ i trư c khi ñư c truy n ñi. V i nhãn ñư c gán ki u này thì ñư ng d n ng n nh t chính là ñư ng truy n nhanh nh t thay vì là ñư ng ít bư c nh y nh t hay ñưòng ng n nh t xét v kho ng cách v t lý. Trong trư ng h p t ng quát, các nhãn trên m i cung ñư c tính như m t hàm theo kho ng cách, băng thông, lưu lư ng trung bình, chi phí truy n tin, th i gian ch trung bình, ñ tr ,… và nh ng y u t khác. B ng cách thay ñ i hàm tr ng s , thu t toán s tính l i ñư c ñư ng ñi “ng n nh t” tùy theo s lư ng các y u t ñư c ch n. Cho ñ n nay, ñã có khá nhi u gi i thu t ñư c ñưa ra nh m gi i thuy t vi c tính toán ñư ng ñi ng n nh t trên ñ th , nhưng gi i thu t Dijkstra (1959) v n ñư c xem là hi u qu nh t và ñư c s d ng ph bi n trong các nghi th c ñ nh tuy n theo ñư ng d n ng n nh t hi n nay. 1.2.3.2. Đ nh tuy n ng p l t (Flooding) 1.2.3.3. Đ nh tuy n theo vectơ kho ng cách Hai gi i thu t ñ ng thông d ng nh t hi n nay là ñ nh tuy n theo vectơ kho ng cách và ñ nh tuy n theo tình tr ng k t n i. Gi i thu t ñ nh tuy n theo vectơ kho ng cách ho t ñ ng d a vào vi c duy trì m t hàng (ñư c g i là m t vectơ) bên trong m i b ñ nh tuy n cho bi t kho ng cách ñư c bi t t t nh t t i m i nút ñích và c ng nào s ñư c s d ng ñ ñi ñ n ñó, hàng này ñư c c p nh t thư ng xuyên nh vi c trao ñ i thông tin v i các b ñ nh tuy n k c n.
  10. 8 1.2.3.4. Đ nh tuy n theo tình tr ng k t n i 1.2.3.5. Đ nh tuy n phân c p 1.2.3.6. Đ nh tuy n qu ng bá (broadcast) 1.2.3.7. Ð nh tuy n theo nhóm (multicast) 1.2.3.8. Đ nh tuy n cho m ng có các tr m di ñ ng 1.2.3.9. Đ nh tuy n cho m ng di ñ ng h n t p (Ad Hoc) 1.2.3.10. Tìm ki m các nút trong m ng ñi m n i ñi m (Peer-to- Peer) 1.3. K T LU N CU I CHƯƠNG Đ m t m ng máy tính có th t n t i theo th i gian thì ñòi h i ph i có các thao tác v n hành thích h p. Có r t nhi u các y u t khác nhau nh hư ng ñ n su t quá trình ho t ñ ng c a m ng, ñôi khi trong b n thân nh ng y u t này l i ch a ñ ng mâu thu n l n nhau. Vì v y s không th có m t gi i pháp chung ñem l i hi u qu t i ưu cho t t c các mô hình m ng, mà ngư c l i, nhà qu n tr c n ph i xem xét k lư ng t ng hoàn c nh c th ñ xác ñ nh ñư c nh ng y u t nào c n ph i ñư c ưu tiên trư c, nh ng y u t nào có th dung hòa ñư c l n nhau, ñ t ñó ñưa ra quy t ñ nh sáng su t trong vi c l a ch n phương án thích h p cho h th ng m ng c a mình.
  11. 9 CHƯƠNG 2 BÀI TOÁN Ư C LƯ NG NHU C U TRUY N THÔNG 2.1. PHÁT BI U BÀI TOÁN 2.1.1. Vai trò và m c tiêu ñ t ra c a bài toán Nhu c u truy n thông gi a các c p nút ngu n - ñích trên m ng thư ng ñư c bi u di n dư i d ng ma tr n g i là ma tr n nhu c u truy n thông, cùng v i sơ ñ c u trúc m ng và nghi th c ñ nh tuy n, chúng làm nên nh ng y u t cơ b n cho vi c giám sát, phân tích và t i ưu hóa quá trình truy n d li u trên m ng. Hơn n a, vi c thu th p nhu c u truy n thông trong m t kho ng th i gian dài s r t h u ích cho vi c thi t k m ng, l p k ho ch phát tri n m r ng m ng và t ñó ñưa ra ñư c các chi n lư c kinh doanh thích h p. Thông thư ng v i nh ng m ng nh , lưu lư ng truy n không cao, thì các ma tr n này có th ñư c thu th p m t cách tr c ti p thông qua ch c năng lưu v t (log) c a các b ñ nh tuy n. Tuy nhiên, cơ ch này s không còn kh thi ñ i v i các m ng tr c l n, ñó lưu lư ng truy n r t cao, b x lý và b nh trong các thi t b ñ nh tuy n h u như ph i t p trung h t cho vi c luân chuy n các gói tin, n u b t ch ñ lưu v t ñ thu th p thông tin nh m xây d ng ma tr n nhu c u truy n thông thì chúng s tr nên trì tr không th ch p nh n ñư c. Ngư c l i, thông tin v lưu lư ng truy n - ñây chúng ta g i là t i tr ng - trên t ng c ng (interface) c a các thi t b ñ nh tuy n thì h u như luôn có s n và có th ñư c thu th p m t cách d dàng thông qua nghi th c qu n tr m ng ñơn gi n (SNMP).
  12. 10 Đ n ñây, chúng ta ñã có th th y rõ vai trò không th thi u c a ma tr n nhu c u truy n thông, tuy nhiên vi c xác ñ nh chính xác chúng là ñi u h u như không th th c hi n ñư c, vì v y ñ tài s s d ng m t phương pháp nh m ư c lư ng ma tr n nhu c u truy n thông d a vào thông tin t i tr ng trên t ng k t n i, sơ ñ c u trúc m ng và nghi th c truy n thông ñang s d ng. 2.1.2. Mô hình hóa bài toán 2.2. CÁC PHƯƠNG PHÁP Ư C LƯ NG NHU C U TRUY N THÔNG 2.2.1. Phương pháp suy di n d a vào xác su t Có b n y u t làm ñ u vào cho các phương pháp d a vào lý thuy t xác su t: nh ng gi ñ nh v xác su t phân b c a nhu c u truy n thông s quy t ñ nh chi n lư c ñ ti n hành các bư c k ti p và ñó cũng chính là y u t ñ phân bi t s khác nhau gi a các phương pháp. Y u t ñ u vào th hai chính là ma tr n nhu c u truy n thông trư c ñó, ñư c dùng làm kh i ñi m cho thu t toán. Tham s k ti p là tr ng s c a các k t n i ñư c s ñ ng ñ tính ñư ng ñi ng n nh t nh m xây d ng nên ma tr n ñ nh tuy n A. Tham s cu i cùng là t i tr ng c a các k t n i ñư c thu th p tr c ti p t các thi t b ñ nh tuy n thông qua nghi th c SNMP dùng ñ áp ñ t các ràng bu c trên ma tr n nhu c u truy n thông s ư c lư ng. 2.2.2. Phương pháp quy ho ch tuy n tính (Linear Programming) 2.2.3. Phương pháp suy di n Tomography Phương pháp tomography ñã ñư c áp d ng vào bài toán ư c lư ng nhu c u truy n thông, ñây ta ño ñư c t ng lưu lư ng thông
  13. 11 tin truy n trên m i k t n i m ng b ng nghi th c SNMP và bi t ñư c c u trúc bên trong c a m ng thông qua chính sách ñ nh tuy n, v n ñ c a chúng ta là ph i tính ngư c l i ñư c nhu c u truy n thông gi a t ng c p k t n i ñó. 2.2.4. Phương pháp suy di n d a vào mô hình tr ng l c (Gravity) M t trong nh ng phương pháp ư c lư ng ma tr n nhu c u truy n thông ñơn gi n nh t là d a vào mô hình l c h p d n. Theo lu t h p d n Newton thì l c hút gi a hai v t th t l thu n v i tích kh i lư ng c a hai v t th chia cho bình phương kho ng cách gi a chúng. 2.3. THU T TOÁN TOMO-GRAVITY 2.3.1. Gi i thi u thu t toán Như ñã ñ c p trên, trong c hai phương pháp ư c lư ng nhu c u truy n thông d a vào mô hình gravity và tomography ñ u có nh ng ưu và khuy t ñi m riêng c a nó, nhưng nhìn chung c hai phương pháp ñ u không cho k t qu t t như mong ñ i. Vì v y ñây chúng ta s nêu ra m t gi i pháp k t h p ưu ñi m c a c hai phương pháp trên và ñ t tên là TomoGravity, gi i pháp này t n d ng ñư c c nguyên lý h p d n thông tin gi a các nút và nh ng ràng bu c v t i tr ng c a các k t n i trên mô hình tomography. 2.3.2. Sơ ñ thu t toán 2.3.3. Chi ti t thu t toán Bư c 1: Gi i bài toán ư c lư ng nhu c u truy n thông theo mô hình tr ng l c c i ti n
  14. 12 Bư c 2: Tìm trong s nh ng l i gi i thu c không gian vectơ b ràng bu c b i các ñi u ki n thu th p ñư c qua phương pháp tomography m t l i gi i g n nh t so v i l i gi i thu ñư c bư c th nh t 2.4. CÁC GI I THU T TÌM ĐƯ NG ĐI T I ƯU Đư ng ñi t i ưu t A ñ n B là ñư ng ñi “ng n nh t” trong s các ñư ng ñi có th . Tuy nhiên khái ni m “ng n nh t” có th ñư c hi u theo nhi u ý nghĩa khác nhau tùy thu c vào ñơn v dùng ñ ño chi u dài ñư ng ñi. Đ i v i các router, các ñ i lư ng sau có th ñư c s d ng ñ ño ñ dài ñư ng ñi: S lư ng các router trung gian ph i ñi qua (HOP) Đ trì hoãn trung bình c a các gói tín Cư c phí truy n tin M i gi i thu t ch n ñư ng trư c tiên ph i ch n cho mình ñơn v ño chi u dài ñư ng ñi. Đ xác ñ nh ñư c ñư ng ñi t i ưu, các gi i thu t ch n ñư ng s d ng phương pháp ñ th ñ tính toán. Trư c tiên, nó mô hình hóa tình tr ng m ng thành m t ñ th có các ñ c ñi m như sau: Nút là các router. C nh n i li n 2 nút là ñư ng truy n n i hai router. Trên m i c nh có giá ñó là chi u dài ñư ng ñi gi a 2 router thông qua ñư ng truy n n i hai router . Chi u dài ñư ng ñi t nút A ñ n nút B là t ng t t c các giá c a các c nh n m trên ñư ng ñi. N u không có ñư ng ñi gi a 2 router thì xem như giá là vô cùng. Trên ñ th này s th c hi n vi c tính toán tìm ñư ng ñi ng n nh t.
  15. 13 2.4.1. Gi i thu t tìm ñư ng ñi ng n nh t Dijkstra M c ñích là ñ tìm ñư ng ñi ng n nh t t m t nút cho trư c trên ñ th ñ n các nút còn l i trên m ng. 2.4.2. Gi i thu t ch n ñư ng t i ưu Ford-Fulkerson M c ñích c a gi i thu t này là ñ tìm ñư ng ñi ng n nh t t t t c các nút ñ n m t nút ñích cho trư c trên m ng. 2.4.3. Gi i pháp v ch ñư ng Vector kho ng cách (Distance Vector) Ý tư ng c a Distance Vector như sau: m i nút thi t l p m t m ng m t chi u (vector) ch a kho ng cách (chi phí) t nó ñ n t t c các nút còn l i và sau ñó phát vector này ñ n t t c các nút láng gi ng c a nó. Gi thi t ñ u tiên trong Distance Vector là: m i nút ph i bi t ñư c chi phí c a các ñư ng n i t nó ñ n t t c các nút láng gi ng có ñư ng n i k t tr c ti p v i nó. M t n i k t b ñ t (down) s ñư c gán cho chi phí có giá tr vô cùng. 2.5. K T LU N CU I CHƯƠNG Bài toán ư c lư ng nhu c u truy n thông có ng d ng r t l n không ch cho vi c t i ưu hóa quá trình ñ nh tuy n mà còn ph c v cho vi c duy trì và nâng c p m ng nh m luôn ñ m b o ñư c ch t lư ng d ch v trư c yêu c u tài nguyên m ng ngày càng gia tăng. V lý thuy t, bài toán có th ñư c gi i m t cách ñơn gi n b ng vi c lưu l i v t c a các lu ng d li u khi ñi qua t t c các b ñ nh tuy n, tuy nhiên trong ñi u ki n công ngh như hi n nay, gi i pháp này không th th c hi n ñư c n u không mu n các thi t b ñ nh tuy n b trì tr . Vì v y gi i pháp kh thi nh t v n là ư c lư ng nhu c u truy n thông d a vào vi c thu th p m t s thông tin khác v i chi phí ch p nh n ñư c.
  16. 14 CHƯƠNG 3 T I ƯU HÓA QUÁ TRÌNH Đ NH TUY N M NG B NG GI I THU T DI TRUY N Trong ph n này, ñ tài s t p trung trình bày gi i pháp t i ưu hóa quá trình ñ nh tuy n áp d ng cho k thu t truy n thông trên m ng IP, d a vào nghi th c ñ nh tuy n hư ng ñích (destination - based routing protocol) nói chung và nghi th c ñ nh tuy n ưu tiên ñư ng d n ng n nh t (Open Shortest Path First - OSPF) nói riêng. Ngoài ra, ñ tài cũng gi i thi u các khái ni m khác nhau trong vi c t i ưu hóa quá trình ñ nh tuy n và ng d ng c a chúng trong vi c tri n khai cho k thu t truy n thông. V n ñ c n quan tâm ñ c bi t là k thu t ñ nh tuy n d a vào nhi u ñ ño - c th là ñ ño m c tr (delay) và băng thông (bandwidth) - ñ có th ñưa ra ñư ng d n ng n nh t t i m i nút trên m ng. M t gi i thu t m i d a trên gi i thu t di truy n (genetic algorithm) s ñư c trình bày cho phép tính toán t p t i ưu các tr ng s c a nh ng k t n i, k t h p v i các nghi th c truy n thông d a trên ñ ño ñơn cũng như kép. Cu i cùng là ph n trình bày nh ng ưu ñi m c a nghi th c d a trên ñ ño kép so vói ñ ño ñơn. 3.1. T NG QUAN BÀI TOÁN T I ƯU HÓA QUÁ TRÌNH Đ NH TUY N M NG T i ưu hóa quá trình ñ nh tuy n là m t phương pháp r t quan tr ng trong k thu t truy n thông trên Internet, ñư c áp d ng cho các lu ng thông tin (ví d như quy t ñ nh h p hay tách các lu ng thông tin vào/ra gi a các nút nh t ñ nh) sau nh ng kho ng th i gian c th
  17. 15 cho trư c, thư ng t i thi u là vài gi ñ ng h . Đ i v i nh ng nơi c n gia tăng thêm lưu lư ng truy n thông ho c nh ng bi n ñ i lưu lư ng t m th i gây ra t c ngh n ñư ng truy n m t cách c c b , t i ưu hóa quá trình ñ nh tuy n có th gi i quy t, ho c ít nh t cũng gi m b t ñư c nh ng v n ñ ti m tàng nh hư ng ñ n hi u su t m ng. Ý tư ng cơ b n là ñi u ch nh l trình c a nh ng lu ng t i hi n th i và do ñó nâng cao tài nguyên m ng hi n có, d n t i vi c ch t lư ng d ch v (QoS - Quality of Service) ñư c c i thi n. 3.1.1. Phân bi t ñ nh tuy n hư ng ñích v i ñ nh tuy n hư ng ngu n hay l trình. Hai khái ni m ñ nh tuy n khác nhau cơ b n hi n ñang t n t i, chúng nh hư ng m nh m ñ n các phương th c t i ưu hóa cũng như k t qu ñ t ñư c, ñó là: ñ nh tuy n hư ng ñích và ñ nh tuy n hư ng ngu n hay l trình. Các nghi th c ñ nh tuy n truy n th ng ñ u thu c lĩnh v c ñ nh tuy n hư ng ñích như OSPF (Open Shortest Path First), EIGRP (Enhanced Interior Gateway Routing Protocol), hay IS-IS (Intermediate System-to-Intermediate System) do chúng s ch ra bư c k ti p d a trên thông tin ñích ñ n. 3.1.2. Phân bi t gi a ñ nh tuy n ñơn ñ ño và ña ñ ño V i nghi th c ñ nh tuy n hư ng ñích, các b ñ nh tuy n s xác ñ nh c ng ñi ra (outgoing-interface) d a trên nh ng giá tr ñ ño mà có th lư ng hóa b ng kho ng cách t i nút ñích. Thông thư ng nh t, các ñ ño ñơn s ñư c gán vào m i k t n i và thu t toán tìm ñư ng ñi ng n nh t ñư c dùng ñ xác ñ nh ñư ng d n thích h p t m t nút t i các nút khác trên m ng, g i là ñ nh tuy n ñơn ñ ño. Trong khi các ñ ño k t n i thư ng có m t ý nghĩa v t lý nh t ñ nh ch ng h n như là ñ tr ho c chi phí, chúng cũng có th ñư c dùng
  18. 16 theo cách thông thư ng thu n túy ch ñ t i ưu hóa vi c ñ nh tuy n. B ng cách thi t l p các ñ ño phù h p m t cách gián ti p chúng ta có th t i ưu hóa ñư c phương th c ñ nh tuy n. Ngoài nh ng nghi th c v i ñơn ñ ño, cũng ñã có các phương th c ñ nh tuy n cho phép s d ng nhi u hơn m t ñ ño khi tính toán chi u dài c a các ñư ng d n t i m i nút ñích, g i là ñ nh tuy n ña ñ ño. Vi c t i ưu hóa quá trình ñ nh tuy n d a trên các nghi th c v i ñ ño kép có th cho k t qu th c thi t t hơn so v i ñ ño ñơn. B i vì ñ ño th hai có th ñư c s d ng m t cách linh ho t cho phép s n sinh ra nhi u mô hình ñ nh tuy n phong phú. M t khác, ta luôn luôn có th s d ng nghi th c ñ nh tuy n v i ñ ño kép ñ sinh ra m t mô hình ñ nh tuy n v i ñ ño ñơn. 3.1.3. Nhi u ñư ng d n v i chi phí b ng nhau (Equal-Cost Multi-Path ECMP) M t ñ c tính khác có th có c a các nghi th c ñ nh tuy n gây nh hư ng r t l n ñ n quá trình t i ưu hóa là vi c chia s t i tr ng. Trong các nghi th c ñ nh tuy n hư ng ñích, kh năng này thư ng ñư c tri n khai dư i hình th c c a khái ni m “nhi u ñư ng d n v i chi phí b ng nhau” (ECMP). 3.1.4. Nh ng l p t i ưu hóa quá trình ñ nh tuy n D a trên các khái ni m ñã ñư c trình bày trong ph n trên, nhi u lo i gi i pháp ñ nh tuy n trên m ng IP có th ñư c tri n khai. Các nghi th c ñ nh tuy n hư ng ngu n hay l trình (như MPLS) ch c ch n s ñem l i nh ng ti m năng to l n trong vi c t i ưu hóa quá trình ñ nh tuy n. Gi s r ng không có b t c h n ch nào liên quan ñ n quá trình ñ nh tuy n trên toàn b m ng, chúng ta có th tìm
  19. 17 ra m t gi i pháp t i ưu toàn c c b ng cách áp d ng quy ho ch tuy n tính (LP-linear programming) ho c áp d ng heuristic thích h p. Tuy nhiên, ñây chúng ta ch ch tr ng ñ n các nghi th c ñ nh tuy n hư ng ñích, do ñó ch c n tính ñư c ch n dư i c a v n ñ t i ưu hóa quá trình ñ nh tuy n b ng quy ho ch tuy n tính. Lo i gi i pháp t i ưu hóa quá trình ñ nh tuy n hư ng ñích l i ti p t c ñư c chia ra thành mô hình v i ñ ño ñơn (ñi n hình là OSPF) và ñ ño kép (ñi n hình là EIGRP), m i lo i có m t phiên b n k t h p v i vi c chia s t i tr ng (ECMP) và không chia s . H u h t các tài li u v lo i t i ưu hóa quá trình ñ nh tuy n như th này ñ u xem OSPF như là nghi th c n n t ng bên dư i. Tuy nhiên, không th áp d ng quy ho ch tuy n tính cho các m ng v i kích c thu c lo i t trung bình tr lên ñư c, khi ñó c n ph i k t h p thêm heuristic. 3.2. NGHI TH C Đ NH TUY N M ƯU TIÊN ĐƯ NG D N NG N NH T (OSPF) 3.2.1. Vài nét v quá trình hình thành và phát tri n 3.2.2. Sơ lư c nguyên t c ho t ñ ng 3.3. NG D NG GI I THU T DI TRUY N CHO NGHI TH C TRUY N THÔNG OSPF 3.3.1. T ng quan v gi i thu t di truy n 3.3.1.1. Khái ni m gi i thu t di truy n Gi i thu t di truy n là k thu t chung giúp gi i quy t v n ñ , bài toán b ng cách mô ph ng s ti n hóa c a con ngư i hay c a sinh v t nói chung (d a trên thuy t ti n hóa muôn loài c a Darwin) trong ñi u ki n qui ñ nh s n c a môi trư ng, tìm ki m d a trên cơ ch ch n l c và di truy n t nhiên. Thu t gi i này s d ng các nguyên lý di truy n v s thích nghi và s s ng các cá th thích nghi nh t trong
  20. 18 t nhiên. GA là m t thu t gi i và m c tiêu c a GA không nh m ñưa ra l i gi i chính xác t i ưu mà là ñưa ra l i gi i tương ñ i t i ưu. T p h p t t c các l i gi i trong không gian tìm ki m ñư c g i là ki u hình. Các ki u hình này khi mã hoá g i là ki u gen. Toán t di truy n s ñư c th c thi trên ñ i tư ng này. M t ánh x t ki u hình sang ki u gen g i là quá trình mã hoá. M i cá th trong ki u gen có nhi u nhi m s c th . Trong m i nhi m s c th có ch a nhi u gen. M i ñ c trưng di truy n c th ñư c quy ñ nh b i giá tr và v trí c a gen trong nhi m s c th . Đ thích nghi là thư c ño kh năng s ng sót và phát tri n c a cá th trong môi trư ng. Toán t xác ñ nh cá th trong th h hi n t i ñư c gi l i trong th h k ti p ñư c g i là ch n l c. Toán t k t h p ng u nhiên hai cá th ñư c ch n g i là lai ghép. Toán t thay ñ i ng u nhiên c u trúc cá th , t c làm thay ñ i giá tr c a gen g i là ñ t bi n. Thu t toán di truy n g m có b n quy lu t cơ b n là lai ghép, ñ t bi n, sinh s n và ch n l c t nhiên. C u trúc thu t gi i di truy n t ng quát: B tñ u t =0; Kh i t o P(t) Tính ñ thích nghi cho các cá th thu c P(t); Khi (ñi u ki n d ng chưa th a) l p t = t + 1; Ch n l c P(t); Lai P(t); Đ t bi n P(t); H tl p K t thúc
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
8=>2