Phần mềm xử lí lưu lượng IP/WDM

dụ như khi nào thì khởi động một thiết lập LSP? Xu hướng tối ưu hoá toàn cục cố gắng tích hợp thiết kế LSP và ấn định dòng nhưng lại gặp phải khó khăn vì độ phức tạp rất lớn. Xu hướng tối ưu hoá cục bộ chia các nhiệm vụ thành các giai đoạn khác nhau. Trong mỗi giai đoạn, phương pháp tối ưu hoá có thể được triển khai một cách độc lập nhau. CHƯƠNG III TÁI CẤU HÌNH TRONG KĨ THUẬT LƯU LƯỢNG IP/WDM 3.1 Tái cấu hình mô hình ảo đường đi ngắn nhất Trong các mạng WDM có khả năng tái cấu hình, liên kết IP được xây dựng trên các đường đi ngắn nhất WDM đa hop. Một lợi ích về mặt chi phí của mạng quang WDM là nó có thể hoạt động mà chỉ cần sự hỗ trợ tương đối nhỏ (đặc biệt là trong mạng đường trục). Điều này có nghĩa là nhiều kết nối IP khác nhau có thể chia sẻ cùng một tuyến nối vật lí chung và tuyến nối ảo IP sẽ được định tuyến qua các hop chuyển mạch WDM. Hình 3.1 mô tả mô hình ảo và định tuyến trong các mạng WDM tái cấu hình được. Có ba thành phần chính trong sơ đồ: Định tuyến lưu lượng Thiết lập cấu hình IP Định tuyến đường đi ngắn nhất Định tuyến lưu lượng chính là định tuyến gói tin truyền thống, ví dụ như OSPF. Thiết lập cấu hình IP sẽ được trình bày trong phần này. Trong khi đó định tuyến đường đi ngắn nhất cung cấp khả năng ánh xạ từ mô hình IP ảo sang mô hình WDM vật lí. Định tuyến đường đi ngắn nhất bao gồm hai mặt liên quan mật thiết với nhau: chọn đường đi trong sợi và gán bước sóng. Định tuyến đường đi ngắn nhất có thể được triển khai theo một trong hai cách sau: Định tuyến đường đi ngắn nhất tĩnh: phương pháp này tính toán trước và lưu trữ các đường đi định tuyến. Các đường dự phòng thay thế cho mỗi đường đi chính cũng có thể được tính toán và lưu trữ sẵn. Gán bước sóng được thực hiện ngay khi có yêu cầu kết nối đường đi ngắn nhất. Phương pháp này sử dụng các cơ chế gán bước sóng rất đơn giản. Gán bước sóng có thể thực hiện theo cơ chế ngẫu nhiên hoặc cơ chế chọn kênh sóng phù hợp đầu tiên. Định tuyến đường đi ngắn nhất thích ứng: phương pháp này sử dụng thuật toán SPF (chọn đường đi ngắn nhất đầu tiên) động để định tuyến. Thuật toán này đòi hỏi thông tin về trạng thái tuyến nối phải được phổ biến tới các node. Vì sự xuất hiện của các cơ sở dữ liệu trạng thái tuyến nối mang tính cục bộ nên gán bước sóng có thể trở nên phức tạp hơn. Một số cơ chế gán bước sóng là: chọn kênh bước sóng có tải ít nhất, được sử dụng nhiều nhất hay có tốc độ dữ liệu kết nối phù hợp nhất. Hình 3.1 Thiết kế và định tuyến mô hình ảo Thiết kế mô hình IP và định tuyến đường đi ngắn nhất là các chức năng mặt phẳng điều khiển trong khi đó định tuyến lưu lượng là thành phần duy nhất được sử dụng để chuyển tiếp gói tin cũng như định tuyến gói tin. Vì cả thiết kế mô hình ảo và định tuyến đường đi ngắn nhất là các chức năng mặt phẳng điều khiển nên hai thành phần này có thể được kết hợp hoặc kết nối rất gần nhau. Phương pháp kết nối gần nhau dùng cho giải pháp kĩ thuật lưu lượng IP/WDM chồng lấn trong khi phương pháp kia dùng cho giải pháp kĩ thuật lưu lượng IP/WDM tích hợp. Trong một ứng dụng kĩ thuật lưu lượng riêng rẽ thì định tuyến đường đi ngắn nhất dựa trên các điều kiện ràng buộc có thể bổ sung như là một công cụ đánh giá cho thuật toán thiết kế mô hình. Phương pháp này đảm bảo rằng mô hình được thiết kế có thể trở thành hiện thực trong tầng WDM với các dung lượng hiện có. Trong mạng IP/WDM chồng lấn, tầng chủ có thể do một nhà cung cấp dịch vụ truyền dẫn cung cấp. Họ cung cấp cho nhiều máy khách dịch vụ khác nhau, chẳng hạn như các khách hàng VPN. Với hình thức như thế thì một khách hàng tại tầng IP sẽ thuê các dịch vụ truyền dẫn từ mạng WDM. Trong hợp đồng dịch vụ, khách hàng sẽ chỉ rõ một tập các bộ định tuyến IP cố định kết nối trực tiếp với mạng WDM. Tầng WDM cung cấp các kết nối ngắn nhất giữa các bộ định tuyến đó. Tuy nhiên, không giống các kết nối đường dây thuê riêng trong các VPN hiện nay, sự sắp xếp của các kết nối ngắn nhất ảo ấy là không cố định. Trong khi số lượng các kết nối ngắn nhất ấy là cố định hoặc có giới hạn thì mỗi kết nối đường đi ngắn nhất có thể được gán lại để kết nối một cặp bộ định tuyến khác nhau, đáp ứng theo sự thay đổi động các kiểu yêu cầu lưu lượng khác nhau. Điều này đòi hỏi một thuật toán thiết kế mô hình ảo tại tầng IP. Ở đây, mô hình ảo là một sơ đồ chứa các node và các tuyến nối. Các node này là các bộ định tuyến trong khi các tuyến nối là các kết nối đường đi ngắn nhất WDM. Tiếp theo, đồ án sẽ trình bày về vấn đề này và sau đó chỉ ra một số giải pháp tại thời điểm hiện tại. Một số thuật toán dựa trên kinh nghiệm để tối ưu hoá thông lượng mạng và/hoặc khoảng cách hop cũng sẽ được giới thiệu. Các kết luận dựa trên kinh nghiệm này có thể được sử dụng để phát triển một thuật toán mới đáp ứng các mục tiêu khác nhau. 3.1.1 Mô hình ảo có quy tắc và bất quy tắc Mô hình có quy tắc tức là mô hình có các kết nối node theo một kiểu xác định rõ ràng trong khi mô hình bất quy tắc thường được xây dựng động để tối ưu hoá các ma trận hiệu năng nhất định. Mô hình có quy tắc được xây dựng và tồn tại dựa trên các nghiên cứu có tính hệ thống và các khái niệm được chấp nhận rộng rãi. Định tuyến và quản lí trong mô hình có quy tắc thường đơn giản nhưng bổ sung hoặc loại bỏ một node bất kì trong một mô hình có kiến trúc (trong khi vẫn duy trì mô hình đó) là rất khó khăn. Một số ví dụ của mô hình có quy tắc là: Ring Shuffle-Net Manhattan Street Network (MSN hay 2D Torus) GEMNet HyperCube deBruijn Graph Các mô hình có quy tắc trên thường có độ phức tạp định tuyến thấp và là đối xứng trong khi sự khác biệt của chúng nằm ở số lượng các bộ thu phát cần thiết, khả năng mở rộng và khả năng chấp nhận lỗi. Ví dụ như một mạng n–aray hypercube với N node cần (n-1)lognN bộ thu phát cho mỗi node và sẽ có khoảng cách hop trung bình là lognN và đường kính mạng là lognN. So với nó thì một MSN chỉ cần hai bộ thu phát cho một node nhưng cả khoảng cách hop trung bình và đường kính mạng đều bằng . Mô hình Shuffle-Net cũng có khoảng cách hop trung bình nhỏ hơn MSN vì với một bước sóng cho trước, nó có nhiều đường lựa chọn hơn từ node một đầu cuối tới một node đầu cuối bất kì khác. Tuy nhiên, nó cần nhiều bộ thu phát cho một node hơn. Cụ thể trong trường hợp này là n cho một node. Trong phần còn lại, các mô hình bất quy tắc sẽ được xem xét cụ thể vì chúng có thể được tối ưu hoá để hỗ trợ các kiểu lưu lượng đồng dạng và không đồng dạng nhất định. 3.1.2 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, và . 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ử, , là cấp của node i. Rõ ràng là cho bất 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ó, , là độ lớn dòng lưu lượng trong một đơn vị thời gian từ bộ định tuyến i tới bộ định tuyến j. Thông lượng X là một ma trận n x n mà các phần tử X(i,j) của nó là độ lớn lưu lượng (được đo bằng bit) được truyền dẫn từ bộ định tuyến i tới bộ định tuyến j trong một khoảng thời gian nhất định. Các thuật toán này sử dụng các kí hiệu sau: Ma trận nhu cầu lưu lượng dư thừa, biểu diễn bởi Tr và là một ma trận được xác định bởi Một vec tơ dòng F được xây dựng từ ma trận nhu cầu lưu lượng T theo hai bước: Lấy đối xứng T để có Ts trong đó phần tử của nó: Sắp xếp các Ts ở trên theo trật tự giảm dần thành một vec tơ để đạt được F. Vec tơ hop dòng, Fh, được xác định bởi: được sắp xếp theo trật tự giảm dần và H(i,j) là khoảng cách hop từ node i tới node j. Ma trận kết nối, G, là một ma trận n x n. Giá trị của các phần tử G(i,j) là 1 nếu tồn tại một kết nối giữa bộ định tuyến i và bộ định tuyến j và là 0 nếu ngược lại. Do tính chất đối xứng của mô hình ảo IP nên G là một ma trận đối xứng. Dựa trên các kí hiệu trên, các thuật toán trên đặc biệt quan tâm tới các thông số sau: Thông lượng bình thường hoá, Khoảng cách hop đã tính trọng số trung bình, phụ thuộc vào các điều kiện ràng buộc cấp node và Thiết kế thuật toán và các đánh giá hiệu năng sau đó đều nhằm nâng cao độ lợi thông lượng bình thường hoá (NTG-γ). Giá trị này được xác định như sau: và độ lợi khoảng cách hop đã tính trọng số trung bình (AWG-) được xác định theo biểu thức sau: trong đó hnew và là khoảng cách hop trung bình và thông lượng bình thường hoá hiện thời còn hold và là hai giá trị cho mô hình cũ hoặc một mô hình cố định. Các thuật toán dựa trên kinh nghiệm được đề xuất này sẽ thiết lập một mô hình đường đi ngắn nhất tuỳ theo cấp node mạng vật lí của mỗi node. Mô hình kết quả sẽ cho phép các đường song song giữa cùng một cặp node. Một kết nối đường đi ngắn nhất là song hướng. Các thuật toán sẽ bắt đầu với một lược đồ gồm n node rời nhau tương ứng với n bộ định tuyến. Các thuật toán này có giai đoạn đầu giống nhau. Giai đoạn này sẽ tạo ra một cây mở rộng (một cây chung mà không nhất thiết là cây nhị phân) sao cho cung cấp được tối thiểu hoá kết nối. Max [T(i,j)] được sử dụng như là kết quả của cây mở rộng. Tính kết nối lược đồ ban đầu là quy định của nhu cầu tải. Đối với mỗi F(i) tương ứng với Ts(p,q), một kết nối sẽ được gán giữa bộ định tuyến p và bộ định tuyến q nếu như không tồn tại đường nối nào giữa chúng. Không giống như các thuật toán ‘đơn hop tối ưu hoá lưu lượng’ truyền thống, các thuật toán được đề xuất ở đây sẽ không chỉ ấn định các kết nối còn lại một cách giản đơn nhờ sử dụng F. Thay vì thế, các thuật toán này sẽ đánh giá mô hình nguyên thuỷ nhờ sử dụng một môi trường dựa trên dòng được mô phỏng. Sự khác nhau của chúng là ở phương pháp ấn định các kết nối còn lại. Cho mạng gồm có n node, mô hình kết nối ban đầu bao giờ cũng có n-1 kết nối. Trong một mạng đang hoạt động thì làm cách nào để ấn định các tài nguyên còn lại là vấn đề rất quan trọng. Ba thuật toán dựa trên kinh nghiệm sẽ được trình bày dưới đây. Thuật toán dựa trên kinh nghiệm nhu cầu còn lại (RD) Thuật toán này gồm có các bước sau: Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa các node theo vec tơ dòng F tuỳ theo các điều kiện ràng buộc cấp node. Vì F được sắp xếp theo trật tự nhu cầu giảm dần nên cây kết nối ban đầu được xây dựng để chứa các dòng lưu lượng có nhu cầu lớn nhất của lân cận một hop. Có hai kết nối song song giữa cùng một cặp node. Mỗi kết nối này sử dụng băng thông tối đa đã được xác định trong ma trận L. Bước 2. Sử dụng nhu cầu lưu lượng đối với mô hình chưa hoàn thành. Hai phương pháp cho ấn định lưu lượng đã được xem xét. Một phương pháp là định tuyến tuyến nối ngắn nhất (SPF) và phương pháp kia triển khai SPF và một kĩ thuật lệch dòng chẳng hạn như ECMP (đa đường đồng chi phí) hay OMP (đa đường tối ưu hoá). Phương pháp ấn định lưu lượng trong thuật toán sẽ thể hiện chính sách định tuyến trong mạng đang hoạt động. Ví dụ như, một mạng IP truyền thống hỗ trợ SPF (ví dụ như tính toán định tuyến trong OSPF) một chính sách định tuyến tối ưu sẽ đòi hỏi cân bằng tải giữa các đường kế tiếp, ví dụ như OSPF-OMP. Bước 3. Vì có nhiều giao diện chưa được ấn định nên có khả năng là không phải tất cả các nhu cầu đều được hỗ trợ bởi mô hình chưa hoàn thành. Do đó, sẽ tạo ra một vec tơ dòng mới sử dụng ma trận nhu cầu dư thừa. Vec tơ dòng mới này được lưu trữ theo trật tự giảm dần của nhu cầu dư thừa. Bước 4. Tìm kiếm trong vec tơ dòng mới này để tìm ra một dòng mà một kết nối mới có thể được gán giữa các đầu cuối của nó. Chèn kết nối mới này vào mô hình và thiết lập kết nối với băng thông tối đa của nó theo F. Sau đó quay trở lại bước 2. Thuật toán sẽ dừng lại nếu không thể tìm ra một kết nối mới nào nữa. Bước 5. Nếu như số lượng các giao diện rỗi là không nhỏ hơn 2 thì ứng dụng thuật toán kinh nghiệm hội tụ được trình bày dưới đây. Vì sự đánh giá các mô hình trung gian dựa trên nhu cầu còn lại nên thuật toán này được đặt tên tương ứng là RD. Một biến thể của trạng thái này là xem xét tích của đếm hop và nhu cầu còn lại. Theo đó, thuật toán tương ứng được gọi là RDHP. RDHP có xu hướng ưa thích các dòng với các giá trị cao cho tích giữa nhu cầu còn lại và số đếm hop. Thuật toán dựa trên kinh nghiệm tích đếm hop và nhu cầu còn lại (RDHP) Có bốn bước trong thuật toán này: Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa các node theo vec tơ dòng F. Bước này giống bước 1 trong RD. Bước 2. Ứng dụng nhu cầu lưu lượng vào mô hình chưa hoàn thành. Bước này cũng giống với bước 2 trong RD. Bước 3. Tính toán khoảng cách hop giữa tất cả các cặp node dựa trên mô hình chưa hoàn thành. Bước 4. Tạo ra một vec tơ dòng mới nhờ sử dụng ma trận nhu cầu còn lại trong đó mỗi phần tử của nó có trọng số bằng với giá trị đếm hop của nó. Vec tơ dòng này được lưu trữ theo trật tự giảm dần của tích giữa nhu cầu còn lại và giá trị đếm hop. Tìm kiếm giữa các vec tơ hop-dòng này để tìm ra một dòng mà một kết nối mới có thể được gán giữa các đầu cuối của nó. Chèn kết nối mới này vào mô hình và thiết lập kết nối mới này với giá trị băng thông tối đa của nó theo F. Sau đó quay trở lại bước 2. Thuật toán sẽ dừng lại khi không tìm thấy kết nối mới nào nữa. Nếu số lượng các giao diện rỗi không nhỏ hơn 2 thì sử dụng thuật toán kinh nghiệm hội tụ được trình bày dưới đây. Một biến thể khác của trạng thái này là chỉ đơn giản xem xét tích giữa nhu cầu và số đếm hop. Đây rõ ràng là kết quả của mục tiêu tối ưu hoá toàn cục, nghĩa là tối thiểu hoá trọng số số đếm hop của mạng. Do vậy, nó được gọi là DHP. DHP giảm được nhu cầu tính toán xảy ra sau khi mỗi kết nối được bổ sung. Thuật toán dựa trên kinh nghiệm tích nhu cầu và số đếm hop (DHP) Thuật toán này gồm có các bước sau: Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa các node theo vec tơ dòng F. Bước này giống bước 1 trong RD. Bước 2. Tính toán/tính toán lại khoảng cách hop giữa tất cả các cặp node dựa trên mô hình chưa hoàn thành. Bước 3. Tạo một vec tơ dòng mới theo trật tự giảm dần nhờ sử dụng ma trận nhu cầu trong đó các phần tử của nó có trọng số bằng với giá trị đếm hop của nó. Bước 4. Tìm kiếm trong vec tơ hop dòng để tìm ra một dòng mà một kết nối mới có thể được gán giữa các đầu cuối của nó. Chèn kết nối mới này vào mô hình và thiết lập kết nối mới này với giá trị băng thông tối đa của nó theo F. Sau đó quay trở lại bước 2. Thuật toán sẽ dừng lại khi không tìm thấy kết nối mới nào nữa. Bước 5. Nếu số lượng các giao diện rỗi không nhỏ hơn 2 thì sử dụng thuật toán kinh nghiệm hội tụ được trình bày dưới đây. Các thuật toán được trình bày ở trên có thể dừng lại khi tất cả các giao diện đều sẵn sàng. Một ví dụ của tình huống như vậy là khi tất cả các giao diện chưa được ấn định cùng thuộc về một node. Điều này có thể xảy ra như là kết quả của sự nhầm lẫn giữa cấp node và nhu cầu lưu lượng. Vì các thuật toán cố gắng cung cấp cho các nhu cầu lớn các kết nối trực tiếp nên node có lưu lượng thấp hơn có thể kết thúc với nhiều giao diện rỗi nhưng phần còn lại của mạng là hoàn toàn bị chiếm. Một thuật toán cho hội tụ đã được cung cấp. Nó bao gồm các bước sau: Bước 1. Phát hiện node với nhiều giao diện IP mở (lớn hơn hoặc bằng 2). Bước 2. Ứng dụng nhu cầu lưu lượng cho mô hình hoàn thành một phần. Bước 3. Sắp xếp tất cả các kết nối dựa trên mức tận dụng theo trật tự giảm dần. Mức tận dụng kết nối được thiết lập cao hơn mức tận dụng tuyến nối của hai tuyến nối đã tạo nên kết nối. Bước 4. Chọn kết nối tải nhỏ nhất mà không phải là trường hợp node có các giao diện mở từ trong danh sách sắp xếp. Phá vỡ kết nối này và tạo ra hai kết nối mới giữa hai giao diện mở đang có. Hai giao diện vừa được mở mới này có được là nhờ việc phá vỡ kết nối có tải nhỏ nhất. Bước 5. Trở lại bước 2 nếu như số lượng các giao diện mở vẫn còn lớn hơn hoặc bằng 2. Trong một mạng đường trục IP, mỗi node thường có ít nhất vài giao diện. Điều này dẫn đến tổng số lượng kết nối, l, có thể cung cấp trong mạng là lớn hơn nhiều so với (n-1) kết nối trong lược đồ cây mở rộng ban đầu. Điều này có nghĩa là việc thiết lập (l-n+1) kết nối trong thực tế là một thủ tục rất quan trọng trong khi thiết kế mô hình. 3.1.4 Dịch chuyển mô hình ảo Trong mô hình IP chồng lấn mạng WDM có khả năng tái cấu hình, IP và WDM có thể truyền thông qua UNI quang hoặc WDM NC&M. UNI quang cho phép một lượng nhỏ thông tin về mạng vật lí (ví dụ như cấu hình và các kết nối mạng WDM) được chia sẻ với mạng khách. WDM NC&M thể hiện một hệ thống quản lí IP và WDM tách biệt hoàn toàn. Do vậy, giả thiết trong cấu hình mạng chồng lấn là ở chỗ mạng WDM có thể hỗ trợ mô hình ảo. Nếu một mô hình ảo không được hỗ trợ hoặc một đường đi ngắn nhất không được thiết lập do các điều kiện ràng buộc tại tầng WDM thì giải pháp dịch chuyển dự phòng cho mô hình gốc sẽ được dùng đến. Nghiên cứu gần đây chỉ ra rằng thắt cổ chai tài nguyên trong các mạng IP/WDM xảy ra tại các giao diện IP chứ không phải tại các giao diện WDM. Các giao diện IP thường đắt và hiếm hơn các giao diện WDM. Nói chung, có một số lượng giao diện WDM nhất định luôn sẵn sàng. Vì thế nếu một mô hình ảo không thể được hỗ trợ bởi một vật mang (nghĩa là nhà cung cấp máy chủ mạng) thì vật mang sẽ xem xét tới cập nhật dung lượng của nó hoặc là từ chối yêu cầu tài nguyên ngay lập tức. Vật mang có thể không thích chia sẻ thông tin mô hình với các máy khách. Các kinh nghiệm thiết lập mô hình và kinh nghiệm dịch chuyển được giới thiệu một cách riêng rẽ. Chúng có thể được coi là các công cụ riêng rẽ và chỉ được sử dụng khi cần thiết. Nhưng một giả thiết chung trong mô hình liên kết mạng chồng lấn IP/WDM có khả năng tái cấu hình là ở chỗ mô hình ảo có thể được hỗ trợ trong mạng WDM. Việc kiểm tra động các điều kiện ràng buộc vật lí mạng WDM trong tái cấu hình mô hình đòi hỏi một xu hướng IP/WDM tích hợp mạnh hơn nữa. Ví dụ như, trong mô hình mạng IP/WDM có khả năng tái cấu hình ngang hàng, thông tin về mô hình của mạng WDM sẽ được chia sẻ với mạng IP. Chính các mạng IP này làm cho các chiến thuật tái cấu hình IP/WDM tích hợp trở thành hiện thực. Một ví dụ đơn giản là kiểm tra độ mềm dẻo của mỗi đường đi ngắn nhất trong thuật toán thiết lập mô hình. Tuy nhiên, xu hướng này phụ thuộc quá nhiều vào độ chính xác và độ đồng bộ thông tin về mô hình tại một cơ sở dữ liệu của mỗi bộ định tuyến cục bộ. Trong môi trường phân tán và thời gian thực, thông tin cục bộ về mô hình có thể chưa được cập nhật và sự hội tụ mạng tương ứng (ví dụ như các thay đổi trạng thái tuyến nối) có thể mất một khoảng thời gian nào đó. Hơn thế, thông tin mạng WDM quảng bá tới mạng IP sẽ không mềm dẻo đứng từ góc độ điều khiển mạng. Mặc dù mô hình mạng IP/WDM có khả năng tái cấu hình ngang hàng đã được đề xuất nhưng lại không có bất cứ triển khai nào về mặt thương mại của một mô hình như vậy. Ngay cả khi các tài nguyên tầng WDM là đủ để hỗ trợ bất cứ một chuỗi dịch chuyển (một ví dụ yêu cầu nhiều nhất là có thể bổ sung tất cả các kết nối mới trước khi loại bỏ các kết nối không mong muốn), thì vẫn còn những khó khăn trong vấn đề dịch chuyển. Vì tái cấu hình WDM liên quan tới các bước sóng dung lượng lớn (lên tới OC-192), việc thay đổi ấn định tài nguyên trong phân mảnh thô sẽ ảnh hưởng rất lớn tới dòng lưu lượng đầu cuối người sử dụng. Nói chung quá trình dịch chuyển bao gồm nhiều chuỗi thiết lập và loại bỏ các đường đi ngắn nhất WDM riêng rẽ. Các dòng lưu lượng phải thích ứng theo các thay đổi của đường đi ngắn nhất sau mỗi bước dịch chuyển. Tuỳ thuộc vào cấu trúc mạng, sự liên quan có thể mở rộng ra phân bố định tuyến trong mạng và tới lượt nó lại ảnh hưởng tới nhiều dòng lưu lượng người sử dụng hơn. Vì tái cấu hình đường đi ngắn nhất WDM được coi như một thay đổi mô hình đường đi ngắn nhất tại tầng IP, giao thức định tuyến IP phải thích ứng với thay đổi này. Nghĩa là thay đổi về mô hình có thể gây ra các ‘hố đen’ và các vòng lặp chuyển tiếp trong bất cứ giao thức định tuyến IP nào đang tồn tại. Do đó, cần có các biện pháp bổ sung để loại bỏ các ảnh hưởng lên lưu lượng người sử dụng trong khi hội tụ giao thức định tuyến sau mỗi lần tái cấu hình. Các thuật toán tìm kiếm một lược đồ dịch chuyển tối ưu thường rất phức tạp vì nó liên q