Tài liệu Định tuyến ràng buộc và thực hiện định tuyến ràng buộc trong MPLS – TE

khiển lưu lượng được áp dụng trên IP hoặc ATM, phụ thuộc vào MỞ ĐẦU giao thức được sử dụng giữa các router biên trong mạng. Trên Ngày nay, với sự phát triển nhanh chóng của khoa học kỹ thế giới hiện nay đã khá quen thuộc với công nghệ điều khiển lưu thuật đặc biệt là công nghệ thông tin và viễn thông đã trở thành lượng trên MPLS, song nhìn chung người ta vẫn còn sử dụng TE một động lực quan trọng trong sự phát triển kinh tế thế giới. trên IP và ATM. Vậy tại sao cần thiết phải áp dụng và triển khai TE trên MPLS? Đó có phải là một tất yếu trong sự phát triển hiện Chuyển mạch nhãn đa giao thức (MPLS) là công nghệ đề nay? xuất cho mạng lõi, nên yêu cầu đối với các cơ chế định tuyến trong MPLS cần phải đảm bảo tốc độ tính toán nhanh nhất và đạt Chương II: ĐỊNH TUYẾN RÀNG BUỘC QoS. Chương hiệu năng tổng thể với cho nhiều luồng lưu lượng khác nhau. Hơn này nghiên cứu về định tuyến dựa trên QoS, các khái niệm QoS và nữa, cải thiện hiệu năng định tuyến luôn là một bài toán được nền tảng của nó. Thứ hai, chúng ta xem xét các khái niệm định quan tâm hàng đầu trong mạng. tuyến dựa trên QoS. Sau đó, so sánh một số dạng thuật toán định tuyến dựa trên QoS, và tìm hiểu ưu và nhược điểm của từng loại. Muốn làm được điều đó phải có các giao thức định tuyến trong mạng MPLS – TE. Để tiếp cận các phương pháp định tuyến Chương III: THỰC HIỆN ĐỊNH TUYẾN RÀNG BUỘC ràng buộc đang triển khai trong môi trường mạng viễn thông hiện TRONG MPLS – TE. Trong chương này chúng ta nghiên cứu ba nay, tôi lựa chọn luận văn “ Định tuyến ràng buộc và thực hiện phương pháp định tuyến ràng buộc trong MPLS – TE đó là: định định tuyến ràng buộc trong MPLS – TE”. tuyến đảm bảo băng thông, định tuyến đa đường và định tuyến mờ. Chúng ta nêu ra sự tồn tại của một số thuật toán hiện tại trên Nội dung tìm hiểu của luận văn chia thành 3 chương: cơ sở đó để xây dựng những phương pháp định tuyến mới để đảm Chương I: KỸ THUẬT LƯU LƯỢNG TRONG MPLS. bảo các yêu cầu mức chất lượng dịch vụ. Mỗi một phương pháp Điều khiển lưu lượng (traffic engineering) là quá trình chuyển định tuyến có thuật toán định tuyến và cách xây dựng riêng. hướng lưu lượng trên mạng xương sống để sử dụng hiệu quả băng CHƯƠNG I: KỸ THUẬT LƯU LƯỢNG TRONG MPLS thông hữu dụng giữa các router. Trước khi có MPLS TE, điều  Động lực phát triển MPLS - TE 1 Kỹ thuật lưu lượng trên IP hầu hết được triển khai bằng cách xác định giá nối thông khi nhiều đường đi cùng tồn tại giữa hai điểm trên mạng. Hơn nữa, định tuyến tĩnh cũng cho phép bẻ hướng lưu lượng theo một đường đi định trước. Hình 1.1 mô tả một mạng IP cơ bản với hai khách hàng A và B kết nối với cùng một nhà cung cấp dịch vụ. Mạng điều khiển lưu lượng MPLS  Thiết đường chuyển mạch nhãn sử dụng MPLS – TE Như đã xem xét ở trên việc tính toán đường đi sử kỹ thuật lưu lượng phải trải qua hai giai đoạn chính: tính toán đường dẫn dựa trên các yêu cầu cho trước và sau đó là chuyển gói tin đi dọc theo đường dẫn đó. Tuy nhiên trước khi tìm hiểu quá trình thiết lập một đường chuyển mạch nhãn chúng ta sẽ làm rõ một khái Mạng IP truyền thống niệm quan trọng trong MPLS – TE đó là độ ưu tiên. Độ ưu tiên là thông số quan trọng nhất trong thiết lập đường dẫn chuyển mạch nhãn. Thông tin quảng bá về tài nguyên sẵn có, độ ưu tiên được thực hiện bởi các IGP như OSPF, IS-IS...Khi đã có được thông tin về tài nguyên mạng, các nút mạng sẽ tính toán đường đi bằng thuật toán CSPF. CSPF là một giải thuật dùng để chọn ra đường đi tối ưu nhất với một thuộc tính ràng buộc. Cuối cùng, việc báo hiệu và thiết lập đường hầm do giao thức RSVP thực hiện. 2  Quảng bá tình trạng của LSP như các đường liên kết  Sử dụng đường dẫn kỹ thuật lưu lượng Cách đơn giản nhất để điều khiển một luồng thông tin đi thông thường.  Bảo vệ và khôi phục vào một đường dẫn mong muốn là thông qua định tuyến tĩnh. Tuy nhiên trong một mạng lớn gồm nhiều thành phần thì việc quan sát Có nhiều phương pháp bảo vệ tương ứng với loại sự cố toàn cục để đưa ra một kết luận là một điều khó khăn. xảy ra trong mạng và mô hình mạng đang sử dụng. Ví dụ như Ví dụ như trong một mạng gồm các bộ định tuyến muốn trong mạng SDH/SONET có mô hình mạng vòng ta có thể sử chạy định tuyến IP với nhau. Vì một lý do nào đó mà hai trong số dụng các phương pháp các bộ định tuyến này phải được nối WAN với nhau, mạng WAN SONET/BLSR, FDDI, RPR... bảo vệ như SONET/UPSR, này sử dụng MPLS. Khi mô hình định tuyến IP hoạt động, điều Với MPLS cũng tương tự như vậy, có nhiều cách để bảo chúng ta muốn là đưa kết nối bằng MPLS này vào mô hình định vệ và khôi phục đường truyền dữ liệu khi có sự cố. Nhưng do tuyến IP giữa các bộ định tuyến. Có nghĩa là các LSP trong MPLS MPLS là mô hình mạng hybrid được thiết kế để hoạt động trên phải có các đặc tính tương tự như kết nối thông thường. nền IP. Hoạt động của MPLS gắn chặt với các giao thức định Để thực hiện được điều trên cần phải có một giao thức tuyến nên trong luận văn này chỉ đề cập tới vấn đề khôi phục giúp cho các LER trong MPLS có thể thực hiện trao đổi thông tin trong MPLS dựa trên lớp mạng. định tuyến với nhau. Lưu ý là thông tin định tuyến này là giữa các - Bảo vệ toàn cục và bảo vệ cục bộ. bộ định tuyến ngoài mạng MPLS, các bộ định tuyến trong MPLS - Tái định tuyến và chuyển mạch bảo vệ. thực hiện một quá trình định tuyến riêng biệt. - Mô hình MAKAM(Bảo vệ toàn cục). BGP hiện nay là giao thức định tuyến duy nhất thỏa mãn - Mô hình Haskin. những yêu cầu trên. BGP là giao thức đặc thù được sử dụng trong - Mô hình Hundessa. MPLS – VPNs. - Mô hình Simple Dynamic, - Mô hình Shortest Dynamic. Các bộ định tuyến sử dụng IGP (ngoài mạng MPLS) có  Kết luận chương những đặc tính sau:  Sử dụng LSP để tính SPF. 3 Trong chương này chúng ta đã xem xét kỹ thuật lưu lượng “một luồng gói tin từ nguồn tới đích (unicast hoặc multicast) với trong MPLS – TE. Các động lực để phát triển MPLS – TE. Các một chất lượng liên quan đến dịch vụ QoS”. Nói cách khác, QoS quá trình để thiết lập kênh truyền dẫn trong MPLS – TE. Sau đó là một cấp độ đo lường của dịch vụ giao cho người dùng mạng, có sử dụng đường truyền dẫn MPLS – TE để điều khiển một luồng thể được đặc trưng bởi xác suất mất gói, băng thông hiện có, trễ thông tin đi vào mạng. đầu cuối…QoS có thể cung cấp một số thỏa thuận của nhà cung CHƯƠNG II: ĐỊNH TUYẾN DỰA T RÊN RÀNG BUỘC cấp dịch vụ mạng (mức dịch vụ hiệp định, hoặc SLA) giữa người QoS. sử dụng mạng và cung cấp dịch vụ.  Giới thiệu  Định tuyến dựa trên QoS Internet ngày nay chỉ có thể cung cấp dịch vụ "nỗ lực tối Định tuyến dựa trên QoS được định nghĩa là: “một cơ chế đa", có nghĩa là nó sẽ cố gắng hết sức mình để chuyển tiếp lưu định tuyến, theo đó các đường dẫn cho luồng được xác định dựa lượng người dùng, nhưng có thể cung cấp không đảm bảo về tỷ lệ trên một số kiến thức sẵn có về nguồn tài nguyên mạng cũng như thất thoát gói tin, băng thông, độ trễ, sự chậm trễ jitter…Ví dụ, yêu cầu QoS của luồng dữ liệu” hay “một giao thức định tuyến các gói tin có thể bị bỏ bừa bãi trong trường hợp tắc nghẽn. Trong động đã mở rộng các tiêu chí lựa chọn đường để bao gồm các khi các loại dịch vụ này hoạt động tốt đối với một số ứng dụng thông số QoS như liên kết có sẵn, băng thông và đường dẫn sử truyền thống (như FTP và email), đó là điều không thể chấp nhận dụng đầu cuối đến đầu cuối, nút tiêu thụ tài nguyên, sự chậm trễ, cho các ứng dụng mới, thời gian thực, đa phương tiện các ứng độ trễ, và jitter gây ra”. dụng như điện thoại Internet, hội nghị truyền hình, hình ảnh theo cách khác, các ứng dụng mới yêu cầu truyền dẫn tốt hơn dịch vụ 8M 8M yêu cầu, đòi hỏi cao băng thông, độ trễ thấp, và trễ jitter thấp. Nói "nỗ lực tối đa". Vì vậy, việc nghiên cứu chất lượng của dịch vụ QoS là rất quan trọng. QoS là “một tập hợp các yêu cầu dịch vụ để được đáp ứng bởi các mạng trong khi vận chuyển một luồng”. Ở đây luồng là Ví dụ định tuyến dựa trên QoS 4  Định tuyến liên miền dự kiến sẽ được càng đơn giản càng Các vấn đề chính của định tuyến dựa trên QoS - Số liệu và tính toán đường đi. tốt, ổn định và khả năng mở rộng được nhiều nhất. Do đó không - Kiến thức quảng bá, bảo trì thể định tuyến dựa trên thông tin trạng thái mạng. Thay vào đó, - Mở rộng quy mô của tập hợp phân cấp. thông tin QoS sẽ thay đổi giữa các miền khác nhau với quan hệ - Mô hình thông tin trạng thái không chính xác. tĩnh. - Kiểm xoát hành chính.  Thuật toán định tuyến dựa trên QoS. - Tích hợp định tuyến dựa trên QoS định tuyến nỗ  lực tối đa.  Định tuyến dựa trên QoS nội miền và liên miền. Yêu cầu đối với các thuật toán định tuyến dựa trên QoS - Hiệu quả và khả năng mở rộng mạng lớn. - Không phức tạp hơn các thuật toán định tuyến hiện nay.  Phù hợp với kiến trúc Internet hiện tại. Các dạng của thuật toán định tuyến dựa trên QoS Về cơ bản, thuật toán định tuyến dựa trên QoS có thể chia thành ba loại định tuyến “hop – by – hop”, định tuyến dựa trên mã nguồn, định tuyến phân cấp. Định tuyến nội miền và định tuyến liên miền Đối với định tuyến dựa trên QoS nội miền, nó được thiết kế để phối hợp nhiều thuật toán khác nhau trong một miền. Người quản trị mạng có thể tự do sử dụng bất cứ định tuyến dựa trên QoS bên trong các miền, đó là độc lập của định tuyến dựa trên QoS được sử dụng trong các miền khác. 5 Cấu trúc định tuyến phân cấp Maximize  Định tuyến dựa trên QoS và các kỹ thuật liên quan.  Định tuyến dựa trên QoS và kỹ thuật lưu lượng.  Định tuyến dựa trên QoS và điều khiển tải.  Định tuyến dựa trên QoS và dành trước tài nguyên.  Định tuyến dựa trên QoS và Diffserv.  sd ( s ,d )P ( a ,b ) Ý tưởng: Ý tưởng của thuật toán là các đường đi sẽ không ảnh hưởng quá nhiều để thỏa mãn yêu cầu tương lai. Thuật toán phát triển dựa trên khái niệm “liên kết tới hạn”. “Liên kết tới hạn” được chỉ định bởi thuật toán, và là các kết nối với các thuộc tính  Kết luận chương mà một LSP được định tuyến qua các kết nối này giá trị luồng lớn Để cung cấp QoS đảm bảo trên Internet, định tuyến dựa nhất của một hoặc nhiều đôi đầu vào và đầu ra giảm đi. Nếu “liên trên QoS là một thành phần quan trọng. Chương này giới thiệu các kết tới hạn” có tải nặng thì mạng không có khả năng thỏa mãn cho khái niệm về QoS và định tuyến dựa trên QoS, kiểm tra các thuật tương lai. toán dựa trên QoS khác nhau và quan hệ của nó với một số kỹ Các ý tưởng chính : thuật QoS khác. CHƯƠNG III: THỰC HIỆN ĐỊNH TUYẾN RÀNG BUỘC TRONG MPLS – TE  Thuật toán định tuyến với điểm giao tối thiểu MIRA. Chúng ta biết rằng để đảm bảo yêu cầu cài đặt LSP, giá trị maxflow càng nhỏ sau khi mọi cặp nguồn-đích chọn được tuyến đường thì khả năng của mạng đáp ứng cho yêu cầu của tương lai Liên kết tới hạn càng lớn. Vấn đề này có thể được mô tả bởi công thức toán học: Các đường giao tối thiểu: chúng ta có thể nghĩ đường giao Đặt sdθ là maxflow của cặp nguồn-đích (s,d) được tính toán sau tối thiểu là đường đi tối đa của tối thiểu luồng cực đại của mọi cặp khi thỏa mãn yêu cầu thiết lập LSP, bài toán đặt ra là cực đại tổng đầu vào-đầu ra. sdθ của mọi cặp nguồn-đích. Mục tiêu tối ưu là:  Định tuyến ràng buộc đa đường.  6 Định tuyến đa đường. Giảm đến mức tối thiểu  Được biết đến đó là vấn đề giảm đến mức tối thiểu việc sử dụng các liên kết tới hạn có thể được giải quyết bằng công thức Đối tượng luồng mạng đa luồng của định tuyến tối ưu đa đường, dẫn đến 1, k  K , i  s k , l  1 X ijkl   j :( i , j )E 0, k  K , i  s k , l  1  chia đôi luồng lưu lượng thành hai đường giữa các cặp nguồn và đích. Định tuyến đa đường cung cấp băng thông tăng lên, các tài  nguyên mạng sử dụng hiệu quả hơn so với trường hợp thuật toán X klji X ijkl  0, l  Lk Định tuyến ràng buộc đa đường. Lk Vấn đề chia luồng lưu lượng: bao gồm tìm ra các tuyến  X kl ij  1, k  K , i  t k l 1 j:( j ,i )E đường mang một phần hoặc tất cả lưu lượng giữa một nút đầu vào Lk và một nút đầu ra để giảm thiểu tới mức tối đa sử dụng các đường  d k X ijkl  cij , (i, j )  E l 1 kK kết nối. 0  X ijkl  1,0   Xây dựng LP của chia lưu lượng được trình bày như sau: X k ij X - j:( i , j )E X k ij j:( i , j )E  = 0, k  K , i  s k , t k - X k ji k Phương pháp tiến cận Bước 1: Tiền xử lý Khi một vài yêu cầu đường chuyển mạch nhãn có thể đồng = 1, k  K , i  s k j:( i , j )E j:( i , j )E d k ji j:( i , j )E  X ijk - thời phục vụ, chúng ta sẽ phân loại theo sự ưu tiên đã cho hoặc  X kji = -1, k  K , i  t k chính sách quản lý giống như tối đa yêu cầu lưu lượng. Đối với j:( i , j )E mỗi yêu cầu lưu lượng, các nút hoặc các đường liên kết trên lý X ijk  cij , (i, j )  E , 0  X ijk  1,0   thuyết được loại trừ và bị xóa. kK  j:( i , j )E k  K , i  s k , t k ,1  l  Lk định tuyến đơn đường ngắn nhất  X ijk ( l 1)   j :( i , j )E Vấn đề chia lưu lượng với ràng buộc số bước nhảy tối đa Bước 2: Biến đổi lược đồ ràng buộc số bước nhảy Xây dựng công thức LP cho vấn đề chia đôi luồng lưu lượng với ràng buộc số bước nhảy được mô tả như dưới đây: 7 Với mạng đã cho, G=(N,E) được biến đổi tới lược đồ ràng Bước 4: Tính toán tỉ lệ chia tải buộc có số bước nhảy ( Lk  LSP ( k )  H ), G’=(N’,E’). Ở đây N’ và E’ được biến đổi như sau: N 0  s k  N k   j | (i, j )  E , i  N k 1  N '  U 0k  Lk N k E1  ( s k , i| (s k , i)  E Ek  (i, j ) | i  N k 1 , j  N k  E '  U 1 k  Lk E k Phương pháp Tìm kiếm ràng buộc đa đường và các tỉ lệ chia tải  Thiết lập  để sử dụng liên kết cực đại trong mạng;  d k là nhu cầu lưu lượng yêu cầu từ s k đến t k ;  Chuyển đổi G đến lược đồ ràng buộc Lk bước nhảy là (a) G: Biểu đồ phân phối tài nguyên G’; (b) G’: Biểu đồ ràng buộc số bước nhảy  Tham số liên kết = Yêu cầu lưu lượng được gán(Mbps)/khả năng Tìm kiếm tập đường ngắn nhất M (hoặc rộng nhất) từ s k tới d k , P  pi , i  1,2,...M ; liên kết(Mbps)  Hình 3.3: Ví dụ chuyển đổi cấu trúc mạng Thiết lập  M để sự sử dụng liên kết tối đa trong P; If (  M   ) Bước 3: Tìm kiếm đa đường M 8 Đối tượng 3: Giảm đến mức tối thiểu số bước nhảy. Đối While ( d k  0 và P không rỗng)  Thiết lập p là đường có bước nhảy nhỏ nhất trong P; tượng này là cần thiết bởi vì đường này tốt hơn một chút so với  Gán d k cho đường p đến khí  M nhỏ hơn  ; hai đối tượng trên nhưng một số lượng lớn bước nhảy có khả năng  Xóa p trong P;  Cập nhật d k và  M ; tạo ra nhiều nhiễu với các yêu cầu tuyến khác trong một số kết nối. Quy tắc R1: Nếu đường tới nút y qua nút x có băng thông Endwhile sử dụng thấp trong liên kết cổ chai và đường tới nút y qua nút Endif x có băng thông sử dụng thấp trên các liên kết cổ chai khác và While ( d k  0 )  đường từ y qua x có số bước nhảy thấp thì nút y có thể truy cập. Chia d k còn lại tới các đường M theo tỉ lệ hiệu suất sử dụng liên kết sẵn có. Endwhile  Định tuyến ràng buộc mờ Chúng ta định nghĩa ba đối tượng tài nguyên có hướng cho cân bằng tải trọng: Đối tượng 1: Tăng tối đa băng thông đường, ví dụ tăng tối THUẬT TOÁN FRA(G, R, C, ingress, egress, b ) đa băng thông trong liên kết cổ chai với băng thông dư ít nhất KÝ HIỆU trong tuyến. G  G ( N , L) = Đầu vào lược đồ. R = Tập băng thông dư rt Đối tượng 2: Tăng tối đa băng thông trong các liên kết C = Tập đường kết nối có thể sử dụng ci khác bằng liên kết cổ chai. Khi có nhiều hơn một đường với băng thông liên kết cổ chai giống nhau, sau đó đường với băng thông ingress = Nút đầu vào dư cao hơn trong các liên kết là đường tốt nhất. Egress = Nút đầu ra b = Yêu cầu băng thông Path y = Tập các nút trong tuyến từ đầu vào tới nút y 9 Begin: Cấu trúc của thuật toán định tuyến mờ FRA 1. Xóa tất cả các kết nối mà không thỏa mãn ràng buộc băng  Kết luận chương thông “ b ” từ G. Trong chương này chúng ta đã tìm hiểu một vài phương 2. Chạy thuật toán Dijkstra để tính toán H min cho mỗi nút. pháp định tuyến ràng buộc trong MPLS. Chúng ta đề cập đến ba r 3. P   , Path y   y , mingress  1 , và mtr  0 i  đầu thuật toán định tuyến là: thuật toán định tuyến với điểm giao tối vào. thiểu MIRA, thuật toán định tuyến ràng buộc đa đường và thuật Loop: toán định tuyến mờ. Các thuật toán chúng ta đã đề cập đều có 4. Tìm kiếm x  P mà m xr là lớn nhất x  P . những phương pháp thực hiện riêng với từng tham số của mạng 5. P  PU x. Nếu P bao gồm egress thì thoát khỏi vòng nhằm đảm bảo băng thông, độ trễ, jitter... của mạng MPLS – TE. lặp; Mỗi phương pháp có những ưu và nhược điểm riêng, tuỳ theo Loop: từng cấu trúc mạng mà áp dụng các phương pháp định tuyến phù 6. y  P có một kết nối xy Update hợp để đảm bảo định tuyến được tối ưu nhất. KẾT LUẬN VÀ KIẾN NGHỊ 1 test y   . min( p xy , l xy , hxy )  (1   ). ( p xy  l xy  hxy ) 3 Kỹ thuật định tuyến đảm bảo chất lượng dịch vụ QoS If test y  m then Path y  Path xU x r y trong mạng đa dịch vụ luôn là một vấn đề cần quan tâm của các m ry  max( m ry , test y ) nhà khai thác và cung cấp dịch vụ mạng. Đã có rất nhiều nghiên End If cứu được tiến hành và sẽ còn tiếp tục trong tương lai. Thông qua End Loop bài luận văn tốt nghiệp, học viên mong muốn cung cấp thong tin cho người đọc một cách nhìn về kỹ thuật định tuyến QoS trong End Loop mạng MPLS, qua các tìm hiểu về các thuật toán hiện đang sử 7. Return Pathegress dụng trong mạng MPLS và các hướng tiếp cận gần đây nhằm 8. End FRA nâng cao hiệu năng thuật toán định tuyến. 10 Qua nội dung trình bày trong luận văn có thể rút ra một số những thiếu sót kính mong các thầy cô đóng góp y kiến bổ sung kết quả sau: - để em có thể tiếp tục hoàn thiện nghiên cứu và mở rộng đề tài này Hiểu được kỹ thuật lưu lượng trong chuyển mạch nhãn đa một cách hiệu quả. gia thức, các động lực phát triển MPLS – TE. Các quá Em xin chân thành cảm ơn! trình thiết lập kênh truyền dẫn sử dụng MPLS – TE cũng như sử dụng đường truyền dẫn kỹ thuật lưu lượng và quá trình bảo vệ, khôi phục đường truyền dẫn. - Tìm hiểu các phương pháp định tuyến dựa trên QoS, các khái niệm và thông số trong QoS. Để thực hiện định tuyến dựa trên QoS luận văn nêu lên một số phương pháp định tuyến và so sánh ưu nhược điểm của các thuật toán với nhau. - Luận văn đưa ra một số thuật toán định tuyến ràng buộc trong MPLS – TE đó là: Định tuyến với điểm giao tối thiểu MIRA, định tuyến ràng buộc đa đường và định tuyến ràng buộc mờ. Mỗi thuật toán có phương pháp tiếp cận để đánh giá hiệu năng sử dụng trong kỹ thuật định tuyến mạng MPLS riêng để đảm bảo định tuyến được tối ưu nhất. Trên đây là một số kết quả đạt được của luận văn và trong thời gian tới luận văn sẽ sử dụng một số phương pháp để mô phỏng các thuật toán định tuyến ràng buộc trong MPLS. Do sự hiểu biết của học viên còn hạn chế nên không thể tránh khỏi 11