Kĩ thuật lưu lượng IP/WDM, chương 9

Khi thiết kế mô hình thì các mục tiêu hiệu năng được lựa chọn là khác nhau. Các mục tiêu này là nhân tố quyết định và có hai kiểu mục tiêu cơ bản. Một kiểu là hướng ứng dụng, nghĩa là nó thường liên quan tới tỉ lệ QoS ở mức ứng dụng ví dụ như trễ từ đầu cuối tới đầu cuối. Kiểu còn lại là hướng mạng, nghĩa là nó thường có liên quan tới các mức tận dụng tài nguyên mạng, ví dụ như thông lượng tổng. Thông tin đầu vào của thiết kế mô hình...
Nội dung trích xuất từ tài liệu:
Kĩ thuật lưu lượng IP/WDM, chương 9 Chương 9: Thiết kế mô hình Khi thiết kế mô hình thì các mục tiêu hiệu năng được lựa chọn là khác nhau. Các mục tiêu này là nhân tố quyết định và có hai kiểu mục tiêu cơ bản. Một kiểu là hướng ứng dụng, nghĩa là nó thường liên quan tới tỉ lệ QoS ở mức ứng dụng ví dụ như trễ từ đầu cuối tới đầu cuối. Kiểu còn lại là hướng mạng, nghĩa là nó thường có liên quan tới các mức tận dụng tài nguyên mạng, ví dụ như thông lượng tổng. Thông tin đầu vào của thiết kế mô hình là ma trận nhu cầu lưu lượng. Với một mạng IP gồm N bộ định tuyến, ma trận lưu lượng là một ma trận T có kích thước N x N, trong đó phần tử T(i,j) là dòng lưu lượng tổng (đo dưới dạng b/s) từ bộ định tuyến i tới bộ định tuyến j. Các giá trị của các phần tử có thể được xác định nhờ các kĩ thuật dự đoán nhất định dựa trên các kết quả đo hiện tại. Phần dự đoán xu hướng lưu lượng sẽ được xem xét riêng, còn phần này sẽ tập trung đề cập tới các vấn đề thiết kế mô hình. Do vậy, có thể định nghĩa ma trận nhu cầu lưu lượng, T(i,j), bằng với các phép đo độ lớn lưu lượng giữa bộ định tuyến i và bộ định tuyến j trong một cửa sổ thời gian điều khiển được. Thuật toán thiết kế mô hình có thể rút ra từ các công cụ phần mềm dự đoán cho nhu cầu băng thông dòng lưu lượng IP. Các điều kiện khởi tạo có mối quan hệ mật thiết với thuật toán và mục tiêu tối ưu hoá. Thuật toán thiết kế mô hình chấp nhận hai kiểu khởi tạo. Kiểu đầu tiên là các thông số cảm ứng từ mạng, ví dụ như tình trạng tải tuyến nối là điều kiện cho thích ứng tự động. Kiểu thứ hai là các quyết định quản trị từ bên ngoài mạng, ví dụ như sử dụng thuật toán thiết kế mô hình nhờ giám sát dự đoán. 3.1.3 Một số thuật toán dựa trên kinh nghiệm Thiết kế mô hình có thể sử dụng các thuật toán dựa trên kinh nghiệm. Một thuận lợi của việc sử dụng các kinh nghiệm trong một thuật toán tối ưu có đòi hỏi khắt khe trong việc thiết kế mô hình ảo chính là sự mềm dẻo. Trong khi thiết kế một thuật toán dựa trên kinh nghiệm, ta có thể tập trung vào một số mặt khác nhau mà vẫn giảm được chi phí tính toán. Thuật toán thiết kế mô hình đường đi ngắn nhất dựa trên kết quả điều tra Tồn tại ba thuật toán kiểu này: thuật toán thiết kế mô hình dựa trên kinh nghiệm (HTDA), thuật toán thiết kế mô hình logic trễ tối thiểu (MLDA) và thuật toán thiết kế mô hình logic không phụ thuộc lưu lượng (TILDA). HTDA cố gắng tạo ra các đường đi ngắn nhất giữa các cặp node theo trật tự nhu cầu lưu lượng giảm dần. Khi đã có cấp của node mạng, một đường đi ngắn nhất sẽ được tạo ra để đáp ứng nhu cầu lưu lượng tối đa chưa được mang. Quá trình này sẽ tiếp tục cho tới khi không còn tài nguyên mạng nữa. Nếu tất cả nhu cầu lưu lượng đã được ấn định, phần còn lại của tài nguyên mạng sẽ được lựa chọn ngẫu nhiên để hình thành các đường đi ngắn nhất cho tới khi các tài nguyên đã cạn kiệt. Ý tưởng cho thuật toán này xuất phát từ việc nên định tuyến lưu lượng lớn trên một kết nối đơn hop. MLDA thiết lập các đường đi ngắn nhất giữa cặp node liền kề và sau đó HTDA được dùng để ấn định các tài nguyên còn lại tuỳ theo các điều kiện ràng buộc. Ở đây MLDA là một mở rộng của HTDA trong trường hợp cấp mạng logic là cao hơn cấp mạng vật lí. TILDA không quan tâm tới nhu cầu lưu lượng mà tập trung vào việc tối thiểu hoá số lượng bước sóng cần sử dụng. TILDA trước tiên sẽ xây dựng các đường đi ngắn nhất đơn hop và sau đó là các đường đi hai hop. Thuật toán này sẽ tiếp tục thiết lập các đường đi ngắn nhất cho tới khi các điều kiện ràng buộc được đáp ứng. Một thuật toán khác cũng đã được đề xuất gồm hai thuật toán nhỏ hơn: lược đồ tối đa hoá lưu lượng đơn hop dựa trên LP (OHTMS) và lược đồ ghép thông qua loại bỏ tuyến nối (LEMS). OHTMS tương tự như HTDA ở điểm nó cố gắng tối đa hoá tổng lưu lượng đơn hop trong khi vẫn duy trì khả năng kết nối của mô hình ảo. LEMS trước tiên sẽ cố gắng tạo một mô hình ảo hoàn toàn kết nối (lược đồ chia đôi). Trong đó mỗi phần sẽ chứa tất cả các node trong mô hình vật lí. Khối lượng của các biên được đặt theo nhu cầu lưu lượng. Khối lượng nhỏ nhất phù hợp cho việc ghép sẽ được xác định cho các biên này. Các biên đã được ghép sẽ bị xoá khỏi lược đồ và lưu lượng được đẩy sang mô hình mới cập nhật để thực hiện tính toán lại. Khối lượng các biên được cập nhật và đối với các biên đã bị xoá sẽ được tìm kiếm và loại bỏ theo cùng phương thức. Quá trình này sẽ tiếp tục cho tới khi đạt được điều kiện giới hạn ràng buộc. Một số thuật toán (dựa trên kinh nghiệm) thiết kế mô hình cây mở rộng Về mặt lí thuyết, thuật toán hướng ‘tối ưu hoá lưu lượng đơn hop’ đã được chứng minh là cho hiệu năng tốt hơn. Tồn tại một số thuật toán theo xu hướng này. Các phương pháp này khác nhau ở sự ấn định tài nguyên dư thừa sau khi kết nối mô hình ảo ban đầu đã được cung cấp. Các thuật toán này có một số định nghĩa sau:  Mô hình đường đi ngắn nhất tại mức IP được biểu thị bởi trong đó N là tập các bộ định tuyến và L là tập các kết nối IP, n  N và l  L . Trong N thì ni biểu diễn nhận dạng của bộ định tuyến. Một tuyến nối IP luôn luôn là song hướng do đó hai đường đi ngắn nhất đơn hướng trong tầng WDM hình thành một tuyến nối ảo tại tầng IP. Trong L thì lij là nhận dạng tuyến và lij-c biểu diễn băng thông của tuyến. Trong các thảo luận dưới đây thì không có sự khác nhau giữa lij và lji, do đó lij-c = lji-c = max(lij-c, lji-c).  Véc tơ cấp độ node, D, có n phần tử. Mỗi phần tử, 1 d i , i  N , là cấp của node i. Rõ ràng là l   d i cho bất 2 i cứ mô hình IP nào.  Ma trận nhu cầu lưu lượng được biểu thị bởi T. T là một ma trận n x n mà các phần tử của nó, T i, j   0, i, j  N , là độ lớn dòng lưu lượng trong một đơn vị thời gian từ bộ định tuyến i ...