Luận văn:Nâng cấp chất lượng dịch vụ (QoS) trong mạng 3G trên nền MPLS

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

Thêm vào BST

Báo xấu

67
lượt xem 9
download

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

Ngày nay, cùng với sự phát triển nhanh chóng của khoa học kỹ thuật, Công nghệ thông tin và Viễn thông đã góp phần quan trọng vào sự phát triển kinh tế thế giới. Các tổ chức, doanh nghiệp có nhiều chi nhánh, các công ty đa quốc gia trong quá trình hoạt động luôn phải trao đổi thông tin với khách hàng, đối tác, nhân viên của họ. Chính vì vậy đòi hỏi phải luôn nắm bắt được thông tin mới nhất, chính xác nhất, đồng thời phải đảm bảo độ tin cậy cao giữa các chi nhánh của mình...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nâng cấp chất lượng dịch vụ (QoS) trong mạng 3G trên nền MPLS

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG TRƯƠNG SƠN HÒA NÂNG C P CH T LƯ NG D CH V ( QoS) TRONG M NG 3G TRÊN N N MPLS Chuyên ngành: K Thu t Đi n t Mã s : 60.52.70 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: TS. Lương H ng Khanh Ph n bi n 1: TS. Nguy n Lê Hùng Ph n bi n 2: PGS.TS. Nguy n H u Thanh Lu n văn ñã ñư c b o v trư c 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 26-27 tháng 06 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 M Đ U 1. Lý do ch n ñ tài: M ng thông tin di ñ ng phát tri n m nh m trong nh ng năm qua v i kh năng cung c p ña d ng các lo i hình d ch v . Cùng v i d ch v tho i, nhu c u d ch v d li u ngày càng tăng cao chi m m t t tr ng ñáng k trong t ng doanh thu c a nhà khai thác m ng. Xu hư ng này ñòi h i m ng di ñ ng ph i phát tri n theo m t c u trúc m i tiên ti n hơn có kh năng th a mãn cao nh t các yêu c u ch t lư ng d ch v cung c p cho ngư i s d ng, ñ m b o t t nh t tính trung th c, t c ñ x lý và ch t lư ng. Trư c nh ng yêu c u trên, ñ tài: “Nâng c p ch t lư ng d ch v (QoS) trong m ng 3G trên n n MPLS” ñưa ra m t s gi i pháp c th nh m nâng c p ch t lư ng d ch v trong m ng thông tin di ñ ng th h th 3 (3G) b ng cách s d ng ñ nh tuy n QoS ng d ng trong công ngh chuy n m ch nhãn ña giao th c (MPLS). 2. M c ñích nghiên c u: Nghiên c u m ng di ñ ng th h m i 3G, t ñó ñưa ra các hư ng gi i quy t nh m nâng c p ch t lư ng d ch v cung c p cho ngư i s d ng trên cơ s ng d ng công ngh chuy n m ch nhãn ña giao th c MPLS. 3. Đ i tư ng và ph m vi nghiên c u: 3.1. Đ i tư ng nghiên c u: - Nghiên c u m ng thông tin di ñ ng 3G. - Nghiên c u công ngh chuy n m ch nhãn ña giao th c (MPLS), chú tr ng các k thu t ñ nh tuy n QoS. Trên cơ s ñó, áp d ng công ngh này vào m ng di ñ ng th h m i 3G. - Đi sâu nghiên c u các thu t toán ñ nh tuy n QoS trong m ng MPLS, ñ c bi t quan tâm ñ n thu t toán ñ nh tuy n cu c g i o (Virtual Flow Deviation _VFD) 3.2. Ph m vi nghiên c u: - Nghiên c u lý thuy t v m ng 3G và công ngh chuy n m ch nhãn ña giao th c MPLS. - Tìm hi u ki n trúc c a m t h th ng di ñ ng 3G, các thành ph n và giao th c giao ti p. - Tìm hi u khuôn d ng nhãn các gói tin, các giao th c và thu t toán ñ nh tuy n trong m ng MPLS. - Nghiên c u lý thuy t v c u trúc m ng thông tin di ñ ng 3G s d ng MPLS. - Phân tích, ñánh giá các thu t toán ñ nh tuy n QoS trên máy tính b ng ngôn ng l p trình Delphi. 4. Phương pháp nghiên c u: Nghiên c u lý thuy t, k t h p s d ng ph n m m mô ph ng Delphi nh m tính toán, phân tích ñánh giá k t qu thu ñư c t các phương pháp ñ nh tuy n QoS ñư c ch n. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài: Đ xu t gi i pháp cho nhà khai thác m ng nâng c p kh năng c a h th ng, ñáp ng yêu c u ch t lư ng d ch v . 6. C u trúc c a lu n văn: g m 4 chương, - Chương 1: T ng quan v m ng 3G và MPLS - Chương 2: ng d ng MPLS trong m ng 3G - Chương 3: Đ nh tuy n QoS trong m ng MPLS - Chương 4: Mô ph ng thu t toán
4 CHƯƠNG 1 T NG QUAN 1.1. T ng quan m ng thông tin di ñ ng 3G. H th ng thông tin di ñ ng 3G ra ñ i v i m c tiêu là hình thành m t h th ng di ñ ng trên toàn th gi i, nh m vào các d ch v băng r ng như internet t c ñ cao, truy n hình, hình nh … ch t lư ng cao tương ñương m ng h u tuy n. Trong ph n này, tôi trình bày các v n ñ sau: - Gi i thi u: Gi i thi u l ch s phát tri n c a m ng thông tin di ñ ng - Các công ngh ñ xu t cho h th ng m ng 3G: Có m t vài công ngh ñ xu t ñư c phân nhóm d a trên các k thu t cơ b n c a nó như: WCDMA, TDMA c i ti n, hybrid CDMA/TDMA và OFDM. + WCDMA:Băng thông c a m t h th ng WCDMA là 5MHz ho c l n hơn và 5MHz cũng là ñ r ng băng thông t i thi u c a t t c các chu n 3G WCDMA +TDMA c i ti n: Khi TDMA c i ti n ñư c ñ xu t, yêu c u ñ t ra là h th ng m i ph i tương thích v i h th ng GSM 2.5G hi n t i cùng v i các c i ti n (GPRS, HSCSD, EDGE). Đây không th ñư c g i là 3G, nhưng vi c ñưa ra nó s giúp ti n g n hơn ñ n h th ng 3G, ít nh t là trong nh ng năm ñ u tri n khai 3G + Hybrid CDMA/TDMA: M i khung TDMA ñư c chia làm 8 khe (slot) th i gian, trong m i khe th i gian s th c hi n ghép kênh s d ng k thu t CDMA. C u trúc c a khung này tương thích v i GSM. UTRAN TDD mode th c t cũng là m t h th ng hybrid CDMA/TDMA. M t khung ñư c chia làm 15 khe th i gian, và trong m i khe th i gian này g m các kênh ghép s d ng k thu t CDMA + OFDM: OFDM là k thu t ñưa ra d a trên nguyên lý ñi u ch ña sóng mang, ñi u này có nghĩa là chúng ta s chia m t dòng d li u c n chuy n t i thành m t vài dòng bit d li u (các kênh ph ). Nh ng dòng bit ph này sau ñó s ñư c ñi u ch s d ng các mã tr c giao nhau, cho phép ph t n s các sóng mang ph s r t g n nhau (ho c ch ng nhau m t ph n) mà không nh hư ng ñ n nhau. +IMT-2000: IMT-2000 là “tiêu chu n công ngh ” c a t t c h th ng 3G. Ban ñ u, nó là m c tiêu c a ITU (International Telecommunication Union) ñ có ñư c m t tiêu chu n 3G duy nh t ñư c s d ng trên toàn c u, tuy nhiên yêu c u ph i th a mãn c hai m c ñích k thu t và chính tr thì ñã không thành hi n th c. Các k thu t IMT-DS và IMT-TC ñang ñư c phát tri n b i 3GPP, IMT-MC l i ñư c ch n phát tri n b i 3GPP2. Sau này IMT-TC ñư c chia làm hai chu n: TDD và TD-SCDMA - 3GPP: là t ch c nh m phát tri n các tiêu chu n k thu t cho h th ng 3G d a trên giao ti p sóng vô tuy n UTRA và lõi m ng GSM c i ti n. H th ng UTRA có hai mode: FDD và TDD. Mode FDD, ñư ng uplink và downlink s d ng các d i t n s tách bi t nhau. Mode TDD khác so v i mode FDD ch nó s d ng cùng m t t n s sóng mang c hai ñư ng uplink và downlink. + mode FDD, ñư ng uplink và downlink s d ng các d i t n s tách bi t nhau. Các sóng mang có ñ r ng băng t n là 5MHz. M i sóng mang l i ñư c chia thành các khung 10-ms, m i khung ch a 15 khe th i gian. T c ñ chip c a UTRAN là 3.84Mcps.
5 + mode TDD: 15 khe th i gian c a m t khung có th ñư c phân b ñ ng cho ñư ng uplink và downlink, vì th dung lư ng kênh c a các ñư ng này có th khác nhau. T c ñ chip c a m t mode TDD thông thư ng là 3.84Mcps. Ngoài ra còn có phiên b n TDD băng thông h p là TD-SCDMA. Đ r ng băng thông sóng mang 1.6MHz, t c ñ chip là 1.28Mcps - 3GPP2: là t ch c phát tri n h th ng CDMA2000 d a trên công ngh WCDMA. CDMA2000 có t c ñ chip không c ñ nh, có th thay ñ i theo b i s c a 1.2288 Mcps (t i ña là 12) cho t c ñ chip t i ña là 14.7456 Mcps. Băng t n ñư c c p phép (5 MHz) s ñư c chia thành m t s băng t n sóng mang h p (1.25 MHz). H th ng CDMA2000 truy n th ng s chia băng t n thành 3 sóng mang (3x mode). - Các giai ño n phát tri n h th ng lên 3G. Hình 1.6. Các giai ño n phát tri n lên 3G. 1.2. T ng quan công ngh chuy n m ch nhãn MPLS. M ng MPLS là s k th a và k t h p c a ñ nh tuy n thông minh trong m ng IP và chuy n m ch t c ñ cao trong m ng ATM, có c ñ nh tuy n l p 3 (IP) và chuy n m ch l p 2 (VPI/VCI c a ATM). MPLS là cơ ch chuy n m ch nhãn do Cisco phát tri n và ñư c IETF chu n hóa, h tr kh năng chuy n m ch, ñ nh tuy n lu ng thông tin m t cách hi u qu . ñây, tôi s tìm hi u các v n ñ sau: - Gi i thi u: MPLS ra ñ i v i ý tư ng dùng nhãn ñ chuy n m ch. Nó ñã gi i quy t và kh c ph c nh ng h n ch mà các m ng trư c ñây v n còn t n t i như: T c ñ , băng thông không h u ích, tr ... - Các khái ni m trong MPLS: ñây, tôi s tìm hi u các khái ni m v nhãn, Ngăn x p nhãn, B ñ nh tuy n chuy n ti p nhãn LSR, L p chuy n ti p tương ñương FEC, B ng chuy n ti p chuy n m ch nhãn, Đư ng chuy n m ch nhãn LSP, Cơ s thông tin nhãn, Gói tin gán nhãn, Phân ph i và n ñ nh nhãn. - Thi t b LSR: là b ñ nh tuy n chuy n m ch nhãn, nó th c hi n ch c năng chuy n ti p gói thông tin trong ph m vi m ng MPLS b ng th t c phân ph i nhãn. - Ho t ñ ng c a MPLS: MPLS cung c p chuy n m ch ñ nh hư ng liên k t. Trong ñó, dòng d li u s liên h v i nhãn. Các gói s ñư c chuy n ti p d a trên nhãn c a chúng. Chi u dài c a nhãn ng n và xác ñ nh. Các router trao ñ i nhãn v i nhau và các thông tin liên quan. - Các giao th c cơ b n trong MPLS: Các giao th c này bao g m:
6 + Đi u khi n gán nhãn ñ c l p và theo yêu c u + Phát hi n và ch ng vòng l p + Giao th c phân ph i nhãn LPD + Giao th c MPLS-BGP 1.3. K t lu n.
7 CHƯƠNG 2 NG D NG MPLS TRONG M NG 3G 2.1. Gi i thi u chung Ngày nay, nhi u nhà khai thác m ng GSM ho c CDMA nâng c p các m ng 2G hi n t i cung c p các d ch v t c ñ cao s d ng EDGE, GPRS, 1xRTT, EV-DO, ho c các công ngh WLAN như Wi-Fi. Nh ng d ch v này yêu c u các thi t b , các d ng truy n d n khác nhau, th i gian tri n khai lâu và t n kém. Trong quá trình phát tri n t 2G sang 2.5G và 3G, k thu t ATM là gi i pháp cho vi c tích h p tho i, d li u và video. Tuy nhiên gi i pháp này l i không t i ưu cho vi c tăng t c ñ trong các m ng di ñ ng trong khi các m ng 2G TDM v n ñang ñư c duy trì. Chuy n ñ i các m ng 2G và 3G sang m ng chuy n m ch gói IP/MPLS s là gi i pháp ñ gi m giá thành và s d ng l i các thi t b TDM ñã ñ u tư. Ki n trúc m ng 2G TDM: D li u tho i s ñư c chuy n t các tr m thu/phát BTS (Base Transceiver Station) t i biên m ng RAN, qua ph n lõi RAN (BSC) ñ n MSC và c ng GMSC, cu i cùng chuy n vào m ng chuy n m ch công c ng PSTN. Ki n trúc m ng 3G: ph n m ng RAN s mang các tín hi u tho i 2G s d ng k thu t TDM và tín hi u tho i theo chu n 3G s d ng k thu t ATM. Mô hình này s d ng thêm m t c ng MGW th c hi n ch c năng chuy n ñ i tín hi u tho i trên ATM (voice-over-ATM) sang TDM và m t vài tín hi u báo hi u. Các tín hi u sau MGW ñư c chuy n ñ n MSC ti p t c x lí. Các tr m RNC là phiên b n 3G c a BSC th c hi n ch c năng ñ nh tuy n các cu c g i và ñi u ch nh băng thông. M ng di ñ ng là 3G th h th 4 phân tách ch c năng ph n k t n i gi a các MGW thành ph n ñi u khi n và ph n d li u. Ph n ñi u khi n d a trên n n IP và báo hi u s 7 (SS7) th c hi n qua các máy ch MSC. Ph n d li u có th qu n lí các lu ng TDM, ATM, ho c IP. V i c u hình m ng này, tho i 3G không còn ñư c x lí t i MSC n a, do ñó cho phép lo i b hoàn toàn các MSC truy n th ng có chi phí v n hành cao sang s d ng VoIP. Chu n 3G th h th năm và cao hơn s d ng k thu t IP/MPLS cho ph n k t n i gi a BTS/Node B ñ n BSC/RNC (RAN edge), cu i cùng IP/MPLS tr thành công ngh truy n d li u chính trong ki n trúc RAN. 2.2. Các thành ph n chính c a m ng truy n d n vô tuy n: Hình 2.7: M ng thông tin di ñ ng ph n vô tuy n M ng truy n d n vô tuy n có th ñư c chia thành 3 ph n chính: m ng truy c p, m ng ñ nh tuy n, và m ng chuy n t i (Hình 2.7), k t n i theo hai d ng chính: m t là k t n i ñi m-ñi m gi a thi t b truy n tin n i
8 ñ n các vùng riêng, và gi a thi t b truy n tin n i ñ n các vùng trung tâm ñ truy n t i Abis, Iub và S1. M t d ng k t n i ñi m-ñi m khác gi a các thi t b truy n tin/giao ti p n i ñ n hai eNB ñ truy n t i X2. Đ ng h h th ng và ñ ng b th i gian là các y u t quan tr ng quy t ñ nh vi c ch n l a công ngh /nhà cung c p m ng truy n d n di ñ ng, ñ c bi t là v i chu n LTE b i vì công ngh này không ch ñòi h i ñ ng b t n s ñ ng h chính xác, mà còn c n ñ ng b c v th i gian. 2.3. Truy n d n IP trong m ng 3G d a trên n n MPLS. 2.3.1. Gi i thi u: M ng di ñ ng không dây th h th ba cung c p m t lo t các d ch v ña phương ti n ñ truy n tho i, d li u, hình nh, video. Đ cung c p ñư c các d ch v này, yêu c u các m ng ph i h tr ña d ng nhi u l p lưu lư ng truy n d li u và các yêu c u v QoS như t c ñ d li u, t l bit l i, ñ tr , … Các gi i pháp truy n d a trên n n IP ñang g p m t s khó khăn ñ ñáp ng các yêu c u m ng vô tuy n 3G, các yêu c u ñ i v i tr , trư t thông tin, t l m t gói trong quá trình truy n d li u. Các gi i pháp truy n tin trên n n IP c n ñư c nâng c p nh m ñáp ng các yêu c u v QoS. Hi u su t truy n tin trong gi i pháp IP cũng là m t v n ñ r t quan tr ng. Do RTP/UDP/IP header có kích thư c l n (kho ng 60 byte) so v i kích thư c c a ATM (5 byte) nên quá trình truy n thông tin mào ñ u d ch v tho i c a nó s cao hơn so v i ATM. 2.3.2. MPLS trong RAN: Nh m ñ m b o tính hi u qu trong vi c ñi u khi n các ñư ng d n LSPs, m i LSP s ñư c gán m t ho c nhi u các thu c tính nh m h tr trong vi c xem xét, tính toán các ñư ng ñi c a gói tin. Các thu c tính này có th s d ng v i ñ nh tuy n CBR (Constrained-based routing) ñ tính toán ñư ng ñi cho các LSPs. V i CBR offline, máy ch tính toán ñư ng ñi cho LSPs ñ nh kỳ (ví d như hàng gi ho c hàng ngày,..). Các LSPs sau ñó ñư c c u hình ñ ñi theo nh ng ñư ng truy n ñã ñư c tính toán xác ñ nh. Các CBR online ñư c s d ng ñ tính toán l i các tuy n ñ ng nh m thích nghi các thay ñ i băng thông c a các LSP và các l i ñư ng truy n. IETF ñ xu t hai d ng LSP là E-LSP và L-LSP ñ h tr DiffServ trong MPLS. 2.3.2.1. E-LSP: E-LSP ñơn ch có th h tr cho t i ña 8 l p QoS, trong ñó ch h tr hai l p QoS trong mi n ATM. 2.3.2.2. L-LSP: L-LSP ñư c s d ng khi c n h tr cho hơn 8 l p QoS (ho c nhi u hơn hai l p QoS ñ i v i ATM). 2.3.3. Mô hình truy n d n d a trên MPLS: 2.3.3.1. T ng quan v truy n d n MPLS: Cách b trí (layout) và c u trúc liên k t (topology) c a m ng truy n d n vô tuy n cho phép xây d ng nhi u mô hình khác nhau c a các d ch v truy n d n d a trên n n IP. T t c các mô hình này có th ñư c mô t b i m t mô hình chung mà t i ñó BS và RNC ñư c k t n i v i nhau thông qua m t m ng IP. Khi truy n d n IP ñư c xây d ng d a trên k thu t MPLS, các router ñ u là các router chuy n m ch nhãn và m ng truy n d n IP tương thích v i MPLS. Mô hình ñ xu t là mô hình m ng truy n d n UTRAN s d ng chuy n m ch nhãn trong m ng h tr MPLS. Mô hình này khác v i mô hình m ng truy n d n UTRAN s d ng chuy n m ch gói IP thông thư ng. Mô hình này g m hai ph n: - Ph n th nh t t p trung vào vi c thi t l p và qu n lý các LSP.
9 - Ph n th hai xây d ng phương th c g i các gói tin thông qua các LSP. Vi c truy n d li u t RNC ñ n BS (downlink) và t BS ñ n RNC (uplink) ñư c th c hi n b i các LSP riêng bi t. Các m ng truy n d n downlink và uplink có th ñư c xem như hai m ng o riêng bi t, cung c p các lu ng d li u có lưu lư ng b t ñ i x ng cho hai hư ng m t cách linh ho t. Có hai cách xây d ng ñ cung c p d ch v QoS khác nhau trong m ng truy n d n vô tuy n 3G-RAN trên n n MPLS (Hình 2.11): + Cách 1: S d ng m t LSP ñ k t n i m i BS ñ n RNC. Các l p lưu lư ng d li u c a m t BS ñư c mang trong m t LSP. + Cách 2: S d ng nhi u LSP ñ k t n i BS ñ n RNC. M i LSP mang m t l p lưu lư ng. Hình 2.11. Các LSP trong RAN 2.3.3.2. Mô hình giao th c: Các lu ng d li u c a ph n d li u và giao th c ng d ng ph n ñi u khi n c a l p m ng vô tuy n ñ u ñư c chuy n ñi b i các LSP ph n d li u c a l p m ng truy n d n. Hình 2.12. Mô hình l p giao th c c a m ng RAN trên n n MPLS 2.3.3.3. LSP ñơn cho m i BS: M t LSP ñơn ñư c thi t l p ñ k t n i m i BS ñ n RNC. Lu ng thông tin t ng h p c a m t BS, bao g m t t c các l p, ñư c chuy n ñi trong m t LSP. Gi i pháp này có th ñư c th c hi n theo mô hình E-LSP. 2.3.3.4. Đa LSP cho m i BS: Các LSP ñư c thi t l p ñ k t n i m i BS ñ n RNC. M i LSP mang m t l p lu ng d li u. Gi i pháp này có th ñư c th c hi n theo mô hình L-LSP.
10 2.3.4. D phòng ngu n tài nguyên m ng. Trong m ng 3G-RAN trên n n MPLS, d phòng tài nguyên m ng có th th c hi n theo hai m c: d phòng băng thông LSP và d phòng m c m ng truy n d n. Các tuy n cho LSP ñư c tính toán s d ng CBR v i các ràng bu c băng thông. 2.4. ng d ng MPLS trong lõi m ng UMTS 3G. 2.4.1. Gi i thi u. Đ truy n gói d li u, yêu c u ph i có ph n m r ng GTP, UDP, và ph n mào ñ u IP (40 byte). V i các gói d li u nh , d li u mào ñ u c n truy n ñi s r t l n. Đ kh c ph c ñư c nh ng h n ch trên, ñ xu t tích h p k thu t MPLS vào m ng lõi 3G UMTS. Chúng ta s s d ng m t kênh MPLS (MPLS tunnel) như m t cơ ch chuy n t i s d ng các nhãn MPLS hai m c ñ thay th kênh GTP. ng d ng k thu t MPLS cũng giúp kh năng cân b ng t i t t hơn, cung c p d ch v linh ho t hơn, h tr QoS t t hơn. 2.4.2. Các gi i pháp c i thi n kh năng làm vi c c a m ng IP: Đ c i thi n kh năng làm vi c c a m ng IP, 3GPP ñưa ra k thu t GTP chu n (standard GTP) và K thu t GTP c i ti n (Enhanced-GTP) ñư c ñưa ra ñ c i thi n hi u su t truy n d n. 2.4.2.1. GTP chu n: 3GPP ñ nh nghĩa kênh GTP như là l p v n chuy n gi a RNC và GGSN. Đ i v i RNC-SGSN GTP-U tunnel và SGSN-GGSN GTP-U tunnel như (hình 2.13), yêu c u ph i truy n d li u mào ñ u g m m t GTP-U header (12 bytes), m t UDP header (8 bytes), và m t IP header (20 bytes). T ng c ng 40 bytes d li u mào ñ u ñư c ñính kèm vào. V i nh ng gói tin ng n, ch ng h n như d li u VoIP, hi u su t c a phương pháp truy n này r t th p. Hình 2.13: Cơ ch truy n kênh GTP 2.4.2.2. GTP c i ti n: Mô hình GTP c i ti n kh c ph c ñư c h n ch yêu c u quá nhi u d li u mào ñ u c a mô hình GTP chu n. Tuy nhiên, m c ñ c i thi n kh năng làm vi c không nhi u, b i vì nó v n c n m t mào ñ u IP m r ng 20 bytes. 2.4.2.3. Gi i pháp kh c ph c: Cơ ch truy n kênh MPLS (MPLS-tunnel) v i các nhãn MPLS hai m c (8 bytes) ñư c s d ng ñ thay th cơ ch truy n tin theo kênh GTP (GTP-tunnel). + Giao th c ph n ñi u khi n: Đ h tr giao th c này, các thi t b RNC, SGSN, và GGSN ph i h tr MPLS. Đ h tr nh ng node này, chúng ta s ph i thêm vào m t s ngăn x p giao th c ph n ñi u khi n. Hình 2.14 trình bày cách thêm các ngăn x p giao th c này vào m ng lõi.
11 Hình 2.14: Các ngăn x p giao th c ph n ñi u khi n v i các ngăn x p thêm vào B. Th t c kích ho t n i dung PDP s a ñ i (modified PDP): Sau khi RNC, SGSN, và GGSN trao ñ i thông tin ñ nh tuy n v i các router trung gian (intermediate router), chúng t o ra 3 kênh MPLS m t chi u (one-directional MPLS tunnel) tương ng. Cu i cùng, SGSN ph i ghi nh n ñư c băng thông kh d ng cho m i kênh MPLS ñ ñ y nhanh quá trình kích ho t n i dung PDP. Th t c kích ho t di n ra như hình 2.15 C. Giao th c ph n khách hàng (user plane): Sau khi m t thi t b c a khách hàng UE (User Equipment) k t n i vào m ng và th t c kích ho t n i dung PDP ñã ñư c ti n hành, các gói tin có th ñư c truy n t UE ñ n PDN (Packet Data Network), thông qua RNC, SGSN, và GGSN.Giao th c ph n khách hàng t i ch ñ s d ng MPLS như hình 2.16. D. Cơ ch h tr QoS: Cơ ch h tr QoS (QoS supporting mechanism) c a kênh MPLS như hình 2.17. Khi m t gói PDP ñưa ñ n RNC ho c GGSN, quá trình phân lo i gói s ñư c th c hi n và xác ñ nh kênh MPLS tương ng. Các gói tin ñã g n nhãn s ñư c chuy n ñi qua m t nhãn ngoài (outer-label) thay vì s d ng mào ñ u IP (IP header). T i RNC, SGSN, và GGSN, các gói g n nhãn ñư c phân lo i qua nhãn n i (inner-label) thay vì s d ng mào ñ u GTP. Quá trình truy n tin theo cách này s không c n ñ n mào ñ u GTP, UDP. Vì th chúng ta có th s d ng các nhãn hai m c kích thư c 8 bytes ñ thay th cho các mào ñ u IP/UDP/GTP truy n th ng (40 bytes) mà v n duy trì ñư c cùng m t ch c năng, giúp gi m ñư c quá trình truy n các mào ñ u nâng cao hi u qu truy n d n. Hình 2.16: Giao th c ph n khách hàng trong ch ñ s d ng MPLS
12 Hình 2.17: Cơ ch h tr QoS kênh MPLS 2.4.2.4. Đánh giá: Ki n trúc m ng trên n n MPLS không ch gi m dung lư ng mào ñ u ph i truy n t i lõi m ng UMTS 3G, mà còn c i thi n hi u su t truy n tin, cân b ng t i, d ch v cung c p và ch t lư ng d ch v . Ngoài ra, nó còn ñ y nhanh t c ñ th c hi n các th t c th c hi n m t phiên PDP, khi mà công vi c ñi u hành m ng v n th c hi n t i SGSN. A. Hi u su t truy n d n. Hi u su t truy n d n Et (transmission efficiency) trong các m ng lõi 3G (3G PS-Domain core network) ñư c tính như sau: Packet − Length (2.1) Et = x100% ( Packet − Length + Tunneling − Overhead ) B. Cân b ng t i: V i kênh GTP, các gói tin c n ñư c ñ nh tuy n chuy n ñi trên các ñư ng ng n nh t, ho c chi phí truy n tin nh nh t s khi n không ñ ngu n tài nguyên c n thi t cho quá trình truy n gói tin (ñ r ng băng thông ñư ng truy n, không gian b ñ m d li u ra, phân lo i và ki m tra mào ñ u gói tin, …), gây ngh n t i m t s ñi m nút trong khi các ñư ng truy n ho c node khác v n r i. Ngư c l i, k thu t truy n d n d a trên n n MPLS s d ng kênh MPLS cho ñ cân b ng t i t t hơn. 2.5. Gi i pháp nâng c p m ng d a trên thi t b TN700 series: UTStarcom TN700 là th h m i nh t h tr truy n qua Ethernet. V i tính năng h tr MPLS-TP, các s n ph m series TN700 không ch h tr truy n qua Ethernet mà còn h tr các lu ng d li u thư ng dùng như ATM, TDM. TN700 h tr phương th c truy n t i ña giao th c cho phép phát tri n m ng thông tin di ñ ng d a trên n n k thu t chuy n m ch gói. Thi t b TN700 s d ng công ngh MPLS-TP cho phép các nhà cung c p ñư ng truy n gi m ñáng k chi phí v n hành b i vì thi t b tiêu th năng lư ng th p hơn, nh g n hơn, s d ng l i ñư c ngu n nhân l c và kinh nghi m v n hành hi n có. V i TN700, nhà cung c p ñư ng truy n có ñư c gi i pháp chuy n ñ i m ng ñi m-ñi m hoàn ch nh trong khi v n duy trì k t n i ñ n các m ng lõi IP/MPLS và TDM/SDH/vi ba. TN700 ñáp ng ñư c các yêu c u
13 ñ ng b m ng nghiêm ng t cũng như ñ chính xác r t cao c a h th ng 3G/4G, không c n s d ng tín hi u GPS ho c ngu n ñ ng h trung tâm giúp gi m chi phí v n hành. 2.5.1. M ng truy n d n di ñ ng chu n LTE: TN700 h tr m ng di ñ ng chu n LTE s d ng L2 trên n n VPLS và VPWS. M ng truy n d n có th ñư c xây d ng s d ng TN703 cho ch c năng truy c p, TN705 cho ch c năng ñ nh tuy n và TN725 cho ch c năng chuy n t i. M ng này h tr c k t n i S1 (t eNodeB ñ n aWG) và X2 (t eNodeB ñ n eNodeB). Đ tăng kh năng h th ng, các chuy n m ch ñ nh tuy n ñư c k t n i theo c u trúc liên k t d ng m t lư i. TN700 s d ng công ngh MPLS-TP. Theo thi t k , MPLS-TP không ph thu c vào l p IP (ho c ñ a ch ) cho vi c chuy n gói ho c OAM. Thi t l p d ch v VPWS và VPLS không yêu c u thông tin ñ a ch IP. Chi ti t k thu t này giúp ñơn gi n hóa qui ho ch m ng. V i chu n LTE, Lu ng thông tin S1 I/F s ñ m nh n hơn 95% lưu lư ng m ng (X2 ñ m nh n chưa ñ n 5%). Công ngh truy n d n như MPLS-TP là gi i pháp t i ưu ñ xây d ng m ng truy n d n di ñ ng theo chu n LTE. 2.5.2. H tr multicast: TN700 s d ng k t h p H-VPLS và IGMP proxy ñ th c hi n ch c năng multicast. TN700 th c hi n vai trò c a m ng H-VPLS, trong ñó l p chuy n t i (distribution layer) th c hi n ch c năng N-PE, còn l p ñ nh tuy n/truy c p th c hi n ch c năng U-PE. 2.5.3. Đ ng b ñ ng h m ng: Các k thu t truy n tin theo phương th c chuy n gói như 3G, HSPA, và LTE yêu c u ñ chính xác cao c a ñ ng h m ng. TN700 s d ng m t s k thu t ñ ñ m b o tính chính xác và ñ ng b này. V i TN700, nhà khai thác m ng di ñ ng có th l a ch n s d ng ñ ng h TDM truy n th ng, n u gói ñư c chuy n qua m ng truy n d n SDH (s d ng byte SSM/S1). V i m ng truy n d n 10GE/Ge ñ ng b m ng có th s d ng ñ ng b Ethernet (Sync Ethernet). V i nh ng ng d ng trên m ng, yêu c u thông tin v th i gian (th i gian th c) ph i th t chính xác. Tuy nhiên, ñ ng b Ethernet l i không th chuy n ñư c thông tin “th i gian th c” này. Đ chuy n t i thông tin này, TN700 s d ng phương th c th i gian trên gói tin ToP (Time over packet) – IEEE 1588v2. 2.5.4. Kh năng làm vi c cùng m ng IP/MPLS: TN700 ñư c thi t k d a trên k thu t MPLS-TP, tuy nhiên ph n d li u c a MPLS-TP l i v n d a trên k thu t MPLS. TN700 cung c p kh năng tương thích hoàn toàn v i m ng lõi IP/MPLS hi n t i. TN700 ñư c s d ng t i m i m ng chuy n t i, và s k t n i gi a các m ng này ñư c th c hi n qua m ng lõi IP/MPLS. Ho c chúng ta có th k t n i t m ng chuy n t i ñ n m ng lõi h th ng thông qua cùng m t lõi m ng IP/MPLS. 2.6. Các c u hình tham kh o cho m ng di ñ ng: 2.6.1.Các c u trúc liên k t c a RAN: RAN có các c u trúc liên k t t p trung và k t h p. Các c u trúc liên k t này ph i ñư c h tr b i các h t ng m ng MPLS. Ki n trúc m ng RAN t p trung có d ng c u trúc hình sao cho phép giao ti p t BS ñ n tr m ñi u khi n và ngư c l i. Ki n trúc m ng RAN k t h p có d ng: - C u trúc hình sao cho giao ti p t BS ñ n aGW và ngư c l i. - C u trúc any-to-any cho giao ti p gi a các BS.
14 2.6.2. C u hình tham kh o cho m ng di ñ ng t p trung: C u hình MPLS thay ñ i tùy theo d ng TNL (Transport network layer) chuy n trên m ng qua giao ti p Abis/Iub. Có b n d ng TNL (TDM TNL, ATM TNL, HDLC TNL và IP TNL) tùy thu c vào th h c a m ng di ñ ng, giao ti p ho c các TNL ñư c s d ng gi a BS (BTS ho c NodeB) và tr m ñi u khi n (BSC ho c RNC). B ng 2.7: Các m ng RAN và TNL tương ng. M ng Chu n giao ti p TNL GSM/GPRS/EDGE TDM (2G/2.5G) UMTS R3, R99/R4 ATM R99/R5, R6, R7 ATM IP CDMA 1xRTT IS-2000 HDLC ho c TDM CDMA 1x EV-DO IS-856 IP Hình 2.28: C u hình tham kh o cho các m ng di ñ ng t p trung v i các c u hình MPLS cho TNL Hình 2.28 cho th y các c u hình TNL khác nhau s d ng công ngh MPLS trong các m ng truy c p/ñ nh tuy n. Đ h tr m i lo i TNL, m ng MPLS có th m r ng t RNC ñ n các node khác trong ph n truy c p/ñ nh tuy n, như các c u hình (a) ñ n (f). 2.6.2.1. Các lo i TNL cho MPLS trong m ng di ñ ng t p trung: - D ng 1: TDM TNL xác ñ nh l p TDM ñ c trưng trong 2G TNL. TDM TNL qu n lí thi t b RAN n i ñ n qua giao ti p T1/E1. - D ng 2: ATM TNL xác ñ nh l p ATM ñ c trưng trong R3/R4 3G TNL. ATM TNL qu n lí thi t b RAN n i ñ n qua giao ti p I.432.3 E1 ho c STM-1. - D ng 3: IP TNL xác ñ nh l p IP (như trong R5/R6/R7 3G). Nó ñ m b o thông tin c a các thi t b t i ph n m ng RAN s d ng các gói IP. Ch c năng MPLS PE có th truy n lu ng d li u IP s d ng gi i pháp truy n IPoEthoMPLS (ví d như L2VPN), ho c IPoMPLS (như L3VPN). - D ng 4: HDLC TNL xác ñ nh l p HDLC ñ c trưng trong CDMA 1x-RTT TNL.
15 2.6.2.2. Các c u hình s d ng MPLS trong m ng di ñ ng t p trung: T t c các phương th c d a trên n n MPLS th c hi n t i CSG ñòi h i ph i có cơ ch tương thích t i MASG nh m có ñư c m t giao ti p gi a tr m g c (BS) và RC. Các ch c năng MPLS s d ng linh ho t cho các d ng TNL khác nhau. Có nhi u c u hình s d ng MPLS khác nhau tùy thu c vào v trí áp d ng các ch c năng MPLS cũng như m cñ ng d ng k thu t MPLS trong m ng truy n d n di ñ ng. Các c u hình (a) ñ n (f) hình 2.28 cho th y các c u hình MPLS v i ñư ng truy n o ñơn tuy n SS PW (Single Segment Pseudowire) (như c u hình (a) ñ n (d)) ho c ñư ng truy n o ña tuy n MS PW (Multi-Segment Pseudowire) (như c u hình (e) ñ n (f)) t i m ng truy c p và m ng ñ nh tuy n. V i m i c u hình MPLS, m t mô hình chung d a trên L2VPN có th ñư c s d ng gi a b t kỳ các router MPLS. L2VPN có th d a trên VPWS ho c VPLS trong m ng ñ nh tuy n, ho c t i AN. Mô hình chung này tách bi t c a các ph n ñi u khi n . V i các c u hình (e) và (f) các ñư ng truy n o (PW) gi a các thi t b trong m ng truy c p ñư c xây d ng b ng cách n i tr c ti p v i nhau (không có thi t b nào khác n i gi a hai thi t b c n thi t l p PW) gi a CSG và EN (c u hình e) ho c CSG và AN (c u hình f), và ñư c chuy n qua m t l p v t lý có băng thông b h n ch . ng v i m i c u hình MPLS , yêu c u ph i b sung m t s ngăn x p giao th c t i các node m ng truy c p/ñ nh tuy n tương ng ñ chuy n TNL. IP TNL s truy n qua giao th c l p 2 sau ñó qua l p 1. Ph n này trình bày v các ngăn x p giao th c (protocol stack) t i các node m ng truy c p/ñ nh tuy n ñ chuy n t i TNL cho m i c u hình MPLS ñã trình bày. 2.6.3. C u hình tham kh o cho m ng di ñ ng k t h p: IP TNL là d ng TNL ñư c s d ng riêng trong các m ng di ñ ng k t h p (LTE, di ñ ng WiMAX, HSPA+ flat, và UMB). Có hai gi i pháp có th ñư c s d ng ñ truy n IP TNL trong các m ng truy c p/ñ nh tuy n/m ng lõi: L2VPN MPLS và L3VPN MPLS. 2.6.3.1. L2VPN MPLS: Hình 2.37 mô t c u hình tham kh o m ng di ñ ng k t h p s d ng L2VPN MPLS, ñ chuy n t i IP TNL qua giao ti p gi a BS và aGW, và giao ti p gi a các BS. Hình 2.37: C u hình tham kh o cho các m ng di ñ ng k t h p v i L2VPN MPLS
16 2.6.3.2. L3VPN MPLS: Hình 2.38: C u hình tham kh o cho các m ng di ñ ng k t h p v i L3VPN MPLS truy n trong các m ng truy c p (tùy ch n) / ñ nh tuy n / m ng lõi. Hình 2.38 mô t c u hình tham kh o cho m ng di ñ ng k t h p s d ng L3VPN MPLS, ñ chuy n t i IP TNL qua giao ti p gi a BS và aGW, và giao ti p gi a các BS. K t n i gi a CSG và L3VPN trong m ng truy c p có th ñư c th c hi n b ng m t k thu t l p 2 truy n th ng, ho c ch n l a gi a VPWS hay VPLS. 2.7. Nh ng yêu c u chung cho m ng truy n d n di ñ ng MPLS. 2.7.1. Nh ng yêu c u v k thu t lu ng và QoS: Nh ng yêu c u v QoS ñ t ñư c nh s d ng các k thu t lu ng và ñ nh tuy n, trong khi v n tránh ñư c quá t i trong m ng MPLS. 2.7.2. T i ưu hóa ña ñư ng (multi-path): M ng truy c p ph i h tr kh năng ña ñư ng ñ t i ưu hóa băng thông chuy n tín hi u nh n t CSG (có th là m t giao ti p SHDSL và m t giao ti p ADSL2+) ho c n u CSG ñư c n i ñ n hai m ng truy c p khác nhau (như m t giao ti p ADSL2+ và m t giao ti p MW). 2.8. K t lu n: Trong chương 2 chúng ta ñã tìm hi u ki n trúc cơ b n c a m t m ng 3G ng d ng trên n n MPLS t i ph n vô tuy n, lõi m ng, và các giao th c ñi u khi n. Vi c c i ti n nâng c p m ng 3G s d ng ñ nh tuy n IP truy n th ng sang ñ nh tuy n MPLS không nh t thi t ph i th c hi n c i ti n ñ ng b t i t t c các thành ph n trong m ng IP. Đ th c hi n nâng c p m ng 3G hi n t i sang s d ng ñ nh tuy n MPLS, c n có nhi u nghiên c u ñánh giá th c tr ng chi ti t ñ l p d án ñ u tư thích h p.Vi c c i ti n nâng c p m ng 3G hi n t i ñ c i thi n chât lư ng d ch v c n ph i có gi i pháp ñ ng b c ph n c ng và ph n m m.
17 CHƯƠNG 3 Đ NH TUY N QoS TRONG M NG MPLS 3.1. M ñ u: Vi c tìm ki m m t ñư ng d n trong m ng nh m h tr truy n thông tin k t n i m i ñ m b o các thông s ch t lư ng như: băng thông, ñ tr truy n d n là nhi m v c a k thu t ñ nh tuy n QoS. K thu t này ñư c ñưa ra nh m h tr cho m ng IP d a trên k thu t chuy n nhãn ñi như MPLS hay GMPLS. 3.2. Gi i thi u chung: Trong nh ng năm g n ñây, Internet ñã có bư c phát tri n r t n tư ng. Nh ng m ng t c ñ cao ñư c s d ng nh m h tr m t lo t các ng d ng ña phương ti n th i gian th c. Tuy nhiên, ki n trúc c a m ng Internet hi n nay ch h tr d ch v “best effort”. Nó không ñáp ng ñư c cho các m ng tích h p d ch v ñư c thi t k ñ mang các lo i thông tin khác nhau. Đ có ñư c s ñ m b o trong ho t ñ ng ñ u cu i – ñ u cu i (ñ m b o các v n ñ như tr , trư t, t c ñ …), c n thi t ph i có m t vài k thu t t i ưu tài nguyên trong m ng. G n ñây ñã có nh ng n l c quan tr ng nh m nâng c p ki n trúc ñ nh tuy n và các giao th c ñ nh tuy n IP. Công vi c này ñư c th c hi n b ng cách cung c p thêm cho chúng nh ng ch c năng m i ñư c h tr b i MPLS. M c ñích c a thu t toán ñ nh tuy n QoS là: • Th a mãn nh ng yêu c u v ch t lư ng d ch v cho m i k t n i ñư c ch p nh n. • Đ t ñư c hi u qu trong vi c t n d ng tài nguyên. 3.3. Đ nh tuy n QoS: Khái ni m QoS liên quan ñ n vi c cân b ng ho t ñ ng gi a ngư i cung c p d ch v internet và các ng d ng khác. Các thông s b t bu c c a QoS trên m t liên k t ñơn ñó là: • Đ m b o lư ng băng thông t i thi u. • Đ tr cũng như ñ trư t l n nh t còn ch p nh n ñư c. • T l m t thông tin l n nh t còn ch p nh n ñư c. M c ñích chính c a ñ nh tuy n QoS là xác ñ nh m t ñư ng d n có th ñ m b o ñư c nh ng yêu c u b t bu c trên. 3.3.1. Thu t toán Min-Hop (MHA): Thu t toán Min-Hop ñ nh tuy n m t k t n i d c theo ñư ng d n ti n ñ n node ñích b ng cách s d ng m t s ít nh t các liên k t kh thi. Quá trình này th c hi n d a trên cơ s thu t toán Dijkstra. Tuy nhiên, vi c s d ng MHA có th d n ñ n khó khăn trong truy c p khi x y ra ngh n m ch vì s x y ra quá t i trên m t vài liên k t có t n d ng tài nguyên. 3.3.2. Thu t toán WSP: WSP ñư c ñưa ra nh m c i thi n thu t toán MHA v i m c ñích cân b ng t i trên m ng. Trên th c t , WSP ch n m t ñư ng d n kh thi v i lư ng Hop nh nh t và n u có nhi u ñư ng d n như v y thì ñư ng d n v i lư ng dư th a băng thông l n nh t s ñư c s d ng. Thu t toán này không khuy n khích s d ng cho nh ng liên k t có lư ng t i l n trong m ng. Tuy nhiên, WSP v n còn t n t i m t vài h n ch như MHA do vi c ch n nh ng ñư ng d n trong s nh ng ñư ng d n ng n nh t kh thi ñư c s d ng s b o hòa trư c khi chuy n sang ñư ng d n kh thi m i.
18 3.3.3. Thu t toán MIRA: Thu t toán MIRA xác ñ nh m t b ng tư ng thu t tư ng minh v v trí các router vào và ra. M c ñích c a thu t toán này là ñ nh tuy n cho m t k t n i vào ñi qua m t ñư ng d n có ít s can thi p c a nh ng yêu c u có th có trong tương lai nh t. Khi m t cu c g i m i c n ñư c ñ nh tuy n gi a m t c p ngu n và ñích (Si,Ti), MIRA s xác ñ nh ch s thi t l p LST c a các liên k t t i h n cho t t c các c p ngu n và ñích (Sj,Tj). Tr ng s w c a m i liên k t l s ñư c thi t l p theo bi u th c sau: (3.2) w(1) = ∑ ( ST ):l∈L α ST 3.3.4. Thu t toán VFD: Thu t toán này ñư c ñ ra nh m gi i quy t nh ng gi i h n c a các thu t toán trư c b ng cách khai thác t t c các thông tin có th dùng ñư c mà chưa ñư c s d ng các thu t toán trư c ho c th m chí chưa ñư c xem xét b i các thu t toán trư c. Đ mô t tình tr ng c a m ng t t hơn và d ñoán tình tr ng c a m ng trong tương lai, chúng ta có th ñưa ra thông tin v topo m ng t i các node vào và ra (s d ng thu t toán MIRA). S li u th ng kê d li u s ñư c xác ñ nh b ng cách ño t i ñi vào m ng t i m i node ngu n. Thông tin này ñóng vai trò quan tr ng trong vi c quy t ñ nh tuy n các yêu c u ñ n như th nào nh m tránh ngh n m ch. B ng cách khai thác thông tin lưu lư ng thu ñư c, chúng ta có th d ñoán ñư c có bao nhiêu k t n i m i s ñư c t o ra t i m i c p S-T trong tương lai. Các cu c g i này ñư c ñưa vào m ng, chúng s tham gia cùng v i cu c g i hi n th i ñang ñư c ñ nh tuy n và các cu c g i này ñư c xem như là ñang trong giai ño n x lí ñ nh tuy n. Đ bi t ñư c b ng tư ng thu t v lưu lư ng d li u trong tương lai ñư c ñưa vào m ng, VFD th c hi n ñ nh tuy n không ch là các cu c g i th c mà còn ñ nh tuy n m t s xác ñ nh các cu c g i o. Tính chính xác c a vi c xác ñ nh s li u th ng kê là r t quan tr ng khi th c thi thu t toán VFD. Tuy nhiên ngay c khi s li u th ng kê lưu lư ng không ñ t ñ xác ñ nh cao, thì chúng cũng gi m t lư ng thông tin nhi u hơn so v i thông tin topo m ng v v trí c a node ngu n và ñích ñư c khai thác b i thu t toán MIRA. T t c các thông tin v topo m ng và s li u ư c tính cho t i ñư c s d ng ñ xác ñ nh ñư ng d n s s d ng tài nguyên m ng m t cách t t nh t và t i thi u hóa s lư ng cu c g i b c m. M t ñư ng d n như v y s ho t ñ ng trong VFD dư i thu t toán FD. Thu t toán này cho phép chúng ta xác ñ nh ñư c tuy n t i ưu nh t cho t t c các d li u vào m ng thông qua nh ng c p S-T khác nhau. 3.3.4.1. Cu c g i o (Virtual call): M i cu c g i ñư c ñưa vào m ng dù th t hay o ñ u ñư c ñ c trưng b i ba thông s sau: (S,T,d). Trong ñó S,T là node ngu n, ñích và d là băng thông yêu c u. Vi c xác ñ nh 3 thông s này cho m i cu c g i o c n r t chính xác vì chúng s ph i ph n ánh lưu lư ng ñ ng ñ t vào m ng càng chính xác càng t t. Hơn th n a, chúng ta c n xác ñ nh c n phát ra bao nhiêu cu c g i o, yêu c u c p ngu n/ñích và băng thông c a các cu c g i như th nào. Đ x lí v n ñ này, chúng ta có th d dàng xác ñ nh và phân b cho m i c p S-T hai thông s sau: • Lưu lư ng trung bình (αSi,Ti) t i c p S-T th i: là s k t n i trung bình ñi vào thông qua node Si trong kho ng th i gian ñi vào m ng ∆t.
19 • Kh năng phân b băng thông yêu c u t i m i c p S-T: là t s gi a s cu c g i nd có băng thông yêu c u d v i t ng s cu c g i N. N u xem t ng s t i trung bình ñi vào m ng là Λ, ta có: Λ= ∑ Si −Ti λ Si ,Ti (3.3) T ñó, chúng ta s xác ñ nh ñư c xác su t PSi,Ti nh n m t cu c g i gi a c p node S-T như sau: A ni PSi,Ti = ∑ n! (3.4) Xác su t có m t yêu c u v i băng thông d node th i là Pdi s ñư c ư c tính như sau: nd Pdi = (3.5) N Các thông s (Si,Ti,di) s xác ñ nh hoàn toàn nh ng cu c g i o. Các thông s này ñư c xác ñ nh m t cách ng u nhiên tùy thu c vào PSi,Ti ñư c cho trên. Các cu c g i o s ñư c ñ nh tuy n cùng v i các cu c g i th c. Vi c xác ñ nh các cu c g i th c tương t như các cu c g i o và chúng ñư c ñ c trưng b i các thông s (SR,TR,dR). Thu t toán VFD s ch c ch n t i ưu hóa lu ng d li u. Đ xác ñ nh thông s Nv c a cu c g i o, chúng ta s xét hai ti n trình như sau: • Đ u tiên xác ñ nh b n tư ng thu t v s thay ñ i c a t ng lư ng t i trong m ng và ư c tính s cu c g i trung bình N ñư c ñ nh tuy n trong m ng trong kho ng th i gian Ts. Khi có m t yêu c u m i ñ n, Nv = [N - NA] thì cu c g i o xu t hi n. Trong ñó, NA là s cu c g i Active. Chú ý, n u NA> N thì không t n t i b t c cu c g i o nào. • Ti p theo, d a vào s cu c g i Active l n nh t ñư c ñinh tuy n trong m ng, Nmax, s cu c g i o s ñư c xác ñ nh b i công th c: Nv = (Nmax - NA) (3.6) 3.3.4.2. Lưu ñ thu t toán VFD: Ho t ñ ng c a thu t toán VFD ñư c mô t lưu ñ (hình 3.1). Khi có m t yêu c u g i m i, b x lí s thi t l p s hi u Nv cho nh ng cu c g i o là Active. Cu c g i th c và o sau ñó s ñư c ñưa vào m ng. Phương th c ñ nh tuy n lưu lư ng thông tin m i s làm vi c theo hai bư c: • Bư c 1: Xác ñ nh m t lưu lư ng kh thi ban ñ u. Các cu c g i s ñư c ñ nh tuy n t ng cu c m t b t ñ u là cu c g i th c. M t cu c g i s ñư c xem là Active n u tìm th y m t ñư ng d n là kh thi và s là Non-Active n u không tìm th y m t ñư ng d n kh thi. Bư c này s ñư c l p ñi l p l i cho ñ n khi t t c các cu c g i ñ u ñư c xem xét. Công vi c này s d ng l i n u cu c g i th c không ñư c ñ nh tuy n. • Bư c 2: T i ưu hóa t t c các cu c g i Active b ng thu t toán FD.
20 Sau ñó, bư c m t ñư c s d ng l p l i cho t t c các cu c g i là Non-Active. N u có ít nh t m t cu c g i Non-Active ñư c khai báo là Active, bư c hai s ñư c th c hi n. Công vi c này s ñư c l p ñi l p l i cho ñ n khi không có cu c g i nào là Active hay bư c m t không nh n ñư c b t kỳ cu c g i nào là Active. K t qu sau cùng, cu c g i th c ñã ñư c ñ nh tuy n trên m t ñư ng d n t i ưu. Cu c g i th c Nh p s cu c g i o T i ñư c ñưa vào m ng. T t c các cu c g i là NON ACTIVE Tìm ñư ng d n ng n nh t Bư c 1 cho m i cu c g i Cu c g i là No END ACTIVE ? Yes T i ưu hóa lu ng Bư c 2 cho các cu c g i Yes Cu c g i là No NON ACTIVE ? END Hình 3.1. Lưu ñ thu t toán VFD Dòng d li u kh thi mô t bư c m t xác ñ nh b i thu t toán Dijsktra ñư c ñưa vào m ng là nơi có tr ng s c a k t n i ph n nh ñư c s t n d ng kênh th c. Cho m i liên k t, m t tr ng s wij ñư c xác ñ nh như sau: 1 wij = (4.6) C ij − F ij Tr ng s này s ñư c gán và c p nh t thư ng xuyên t i m i quá trình l p. Đo n chương trình sau mô t thu t toán VFD. Trong ñó, m t c s ñư c ñưa vào b ng mô t k t n i nh m xác ñ nh tính Active hay Non-Active c a liên k t. For( ∀ connection(Sk,Tk,flagk)) Flagk=NON ACTIVE End for