Thuật toán đường đi ngắn nhất và rộng nhất SWP

I. Đảm bảo chất lượng dịch vụ định tuyến 1.1. Giới thiệu: OSPF và các giao thức định tuyến động khác luôn luôn đóng gói tin chuyển tiếp tới đường đi ngắn nhất. Nếu đường đi ngắn nhất không có đủ tài nguyên để đạt được các yêu cầu. Dịch vụ hợp nhất được hỗ trợ để dự trữ các tài nguyên cho lưu lượng, nhưng không thể tạo nguồn dự trữ nếu không có đủ tài nguyên dọc theo đường dẫn tới điểm khởi đầu. Dịch vụ phân biệt cũng được sử dụng với khả năng tốt nhất để cung cấp dịch vụ yêu cầu là chưa được xác định. Phần bị mất mát trên hệ thống mạng sẽ có một kỹ thuật có thể tìm thấy đường dẫn, nếu nó tồn tại, có được yêu cầu tài nguyên khả dụng. Trong trường hợp đó nó có thể được sử dụng kỹ thuật Dịch vụ phân biệt hay Dịch vụ hợp nhất một cách có hiệu quả. Đảm bảo chất lượng dịch vụ định tuyến là lược đồ định tuyến mà những sự cân nhắc về chất lượng của dịch vụ yêu cầu của một lưu lượng khi đưa ra các quyết định định tuyến. Tương phản với định tuyến tìm đường ngắn nhất truyền thống, cái chỉ xem xét việc tính bước truyền, Đảm bảo chất lượng dịch vụ định tuyến được thiết kế để tìm kiếm những đường đi khả thi mà đáp ứng được nhiều sức ép. Đảm bảo chất lượng dịch vụ định tuyến là một lược đồ định tuyến, dưới mỗi tài nguyên có giá trị trên mạng cũng như yêu cầu đảm bảo chất lượng dịch vụ định tuyến của các lưu lượng. “ Crawley et al. Phần này giới thiệu các khái niệm cơ bản về kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở. Sau đó các mục đích của đảm bảo chất lượng dịch vụ định tuyến sẽ được giới thiệu. Phần còn lại sẽ thảo luận về vị trí của đảm bảo chất lượng dịch vụ định tuyến trong mạng chất lượng dịch vụ các kỹ thuật có liên quan đến chất lượng dịch vụ khác. 1.2 Kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở Định tuyến đường đi ngắn nhất dẫn đường đến sự phân phối lưu lượng không đồng đều. Điều này có thể do sự tắc nghẽn ở một số đường đi của mạng ngay cả khi lưu lượng tải là không mạnh mẽ một cách đặc biệt. Trong khi lược đồ chất lượng dịch vụ cố gắng để cung cấp dịch vụ tốt hơn dưới sự tắc nghẽn cho các lưu lượng với các yêu cầu chất lượng dịch vụ, nó thậm chí còn đáng được mong muốn hơn để tránh các tình huống này. Kỹ thuật lưu lượng được xử lý có chuẩn bị làm sao để các lưu lượng chảy qua mạng, để tắc nghẽn do sự không đồng đều trong việc sử dụng mạng có thể tránh được. Ràng buộc cơ sở định tuyến tiến đến đảm bảo chất lượng dịch vụ định tuyến, Mặc dù các điều khoản đôi khi được sử dụng hầu như có thể đuợc thay thế cho nhau, định tuyến ràng buộc cơ sở chính xác là một điều khoản chung hơn, có thể kết hợp với đảm bảo chất lượng dịch vụ định tuyến và chính sách định tuyến. Nó kéo dài đến các lược đồ đảm bảo chất lượng dịch vụ định tuyến xét bởi thực tế, hơn nữa các yêu cầu chất lượng dịch vụ, các ràng buộc khác như chính sách mạng cũng như các ứng dụng của mạng chống lại các tình huống tải không đồng dều. 1.3 Các mục tiêu của đảm bảo chất lượng dịch vụ định tuyến Đảm bảo chất lượng dịch vụ định tuyến sử dụng thông tin về trạng thái mạng và tài nguyên có giá trị cũng như các yêu cầu chất lượng dịch vụ cả lưu lượng để ra các quyết định định tuyến. Các mục đích gồm 3 phần: Sự quyết định động của các đường đi khả thi. Mục đích này có nghĩa là tìm một đường đi khả thi cho dòng thông tin trong câu hỏi mà có thể cung cấp hoặc ít nhất là cơ hội tốt để cung cấp các yêu cầu chất lượng dịch vụ của dòng thông tin. Tối ưu tài nguyên sử dụng. Chất lượng dịch vụ cơ sở định tuyến có thể được sử dụng để giúp cho việc cân bằng tải của mạng bởi ứng dụng có hiệu quả của các tài nguyên, và do đó tăng tổng số thông lượng của mạng. Sự giảm hiệu năng uyển chuyển. Trong các tình huống quá tải đảm bảo chất lượng dịch vụ định tuyến có thể cung cấp thông lượng tốt hơn trong mạng hơn bất cứ lược đồ định tuyến trạng thái vô tình, và giảm hiệu năng uyển chuyển hơn nữa. 1.4 Vị trí của đảm bảo chất lượng dịch vụ định tuyến trong hệ thống mạng chất lượng dịch vụ. Phần này thảo luận về các mối quan hệ giữa đảm bảo chất lượng dịch vụ định tuyến và kỹ thuật có liên quan đến chất lượng dịch vụ. Vị trí có liên quan của các thành phần khác nhau trong khuôn khổ chất lượng dịch vụ được thể hiện trong bảng sau: Lớp ứng dụng Lớp giao vận Dịch vụ hợp nhất/RSVP , Dịch vụ phân biệt Lớp mạng Constraint Based Routing Lớp liên kết MPLS 1.4.1 Dịch vụ phân biệt và đảm bảo chất lượng dịch vụ định tuyến Thông thường, lược đồ Dịch vụ phân biệt được tách riêng một cách cố ý từ định tuyến IP, bởi vậy tất cả lưu lượng giữa một cặp nguồn – đích có đi theo cùng một đường cho dù nó thuộc về lớp dịch vụ nào đó, và Dịch vụ phân biệt tự nó không có tác dụng trong các quyết định chọn đường. Điều này có nghĩa là vùng Dịch vụ phân biệt dễ bị tắc nghẽn. Trường hợp sự tập hợp của lưu lượng tối ưu trong mạng lõi có thể là do sự tắc nghẽn. Điều này không phải là một vấn đề khi lưu lượng từ bộ định tuyến biên tập hợp lại ở nhân của bộ định tuyến, từ đó đường dẫn từ bộ định tuyến nhân này tới định tuyến nhân tiếp theo sẽ nhanh hơn là các đường dẫn từ bộ định tuyến lõi đến bộ định tuyến biên. Mặc dù vậy nếu lưu lượng giữa các nhân của bộ định tuyến trong cùng một bộ định tuyến lõi, đường dẫn mà bộ định tuyến dẫn lưu lượng tiến đến có thể không đủ nhanh. Vấn đề này không thể giải quyết được bởi Dịch vụ phân biệt. Đảm bảo chất lượng dịch vụ định tuyến có thể được sử dụng để tránh tình huống này. Trong một vùng Dịch vụ phân biệt đảm bảo chất lượng dịch vụ định tuyến được sử dụng để tìm kiếm các đường dẫn có thể cung cấp các luồng lưu lượng và chống lại sự tắc nghẽn. Một vấn đề khác có thể xảy ra nếu lưu lượng tối ưu không được định tuyến một cách tối ưu theo thứ tự ưu tiên cho lưu lượng, ưu tiên thấp khi khối lượng lớp chi phí cao. Đảm bảo chất lượng dịch vụ định tuyến có thể được sử dụng cho việc cân bằng tải vào khối Dịch vụ phân biệt, do vậy không chỉ lưu lượng tối ưu mà còn cả lưu lượng lớp thấp hơn có được dịch vụ tốt hơn. Các giải thuật định tuyến đặc biệt đã đề xuất để định tuyến lưu lượng ưu tiên cao trong một cách mà xem xét hiệu năng của các lớp lưu lượng khác. 1.4.2 MPLS và đảm bảo chất lượng dịch vụ định tuyến Từ khi MPLS được lược đồ chuyển tiếp và lược đồ đảm bảo chất lượng dịch vụ định tuyến, chúng có thể được sử dụng cùng nhau cho các vấn đề về kỹ thuật lưu lượng. Trong thực tế, MPLS có thể cung cấp thông tin chính xác hơn về lưu lượng tải hơn là định tuyến IP truyền thống, bởi vậy cho phép đảm bảo chất lượng dịch vụ định tuyến tính toán đường đi tốt hơn cho việc cài đặt các chyển mạch nhãn. Hơn thế nữa, nó dễ dàng được liên hệ để tích hợp một khung đảm bảo chất lượng dịch vụ định tuyến với MPLS. Định tuyến ràng buộc cơ sở giữa ba phạm vi vấn đề quan trọng nhất trong tối tài nguyên MPLS, cùng với phân chia khôi phục lưu lượng. Một thân lưu lượng MPLS là một tập hợp các dòng thuộc về cùng một lớp, ví dụ như tất cả các lưu lượng giữa lối vào đặc trưng và lối ra của bộ định tuyến. Lưu lượng liên kết là các đối tượng bảng chọn đường. Mục tiêu của định tuyến đảm bảo chất lượng dịch vụ trong mạng MPLS là định tuyến lưu lượng liên kết dọc theo mạng trong một đường đi thoả mãn ràng buộc đưa ra, và thiết lập một sự phân phối lưu lượng cân bằng tải. Nó cũng có khả năng để định tuyến các chuyển mạch nhãn để chống lại sự tắc nghẽn. Dựa trên thông tin về lưu lượng liên kết, cấu hình mạng và các tài nguyên, đảm bảo chất lượng dịch vụ định tuyến tính toán đường đi rõ ràng cho mỗi lưu lượng liên kết. Các đường rõ ràng ở đây là một sự chỉ rõ chuyển mạch nhãn, đường đi chuyển mạch nhãn, thoả mãn các yêu cầu của lưu lượng liên kết. Theo lộ trình định tuyến, MPLS xác lập việc sử dụng giao thức phân phối nhãn của đường đi chuyển mạch nhãn. Nó không tạo ra sự khác biệt nào so với MPLS cho dù các tuyến được tính toán với quy tắc tự động, cho phép băng thông có thể, nhưng các yêu cầu chất lượng dịch vụ của các dòng lưu lượng là không được xem xét. 1.4.3 Đảm bảo chất lượng dịch vụ định tuyến với sự dành riêng tài nguyên. Sự dành riêng tài nguyên và đảm bảo chất lượng dịch vụ định tuyến là các kỹ thuật độc lập nhưng bổ sung cho nhau. Đảm bảo chất lượng dịch vụ định tuyến có thể tìm thấy đường đi khả thi cho các dòng lưu lượng cần đến sự đảm bảo chất lượng dịch vụ nhưng không thể đảm bảo rằng đường đi sẽ khả thi trong thời gian còn lại của dòng lưu lượng. Phương thức dành riêng tài nguyên có thể được sử dụng để xác định tài nguyên yêu cầu theo đường đi đã chọn. RSVP (Resouce ReSerVation Protocol) Giao thức thường được đề nghị trong các tài liệu liên quan đến đảm bảo chất lượng dịch vụ định tuyến và dành riêng tài nguyên là giao thức lưu trữ tài nguyên. Nó được định hướng bộ nhận, có nghĩa là bộ nhận của dòng dữ liệu chịu trách nhiệm khởi tạo việc dành riêng tài nguyên. Khi nút nguồn khởi tạo một dòng, nó gửi một thông tin đường đi đến nút đích xác nhận các kí tự của dòng cho các tài nguyên được yêu cầu. Điểm trung gian theo thông tin đường đi đến giao thức định tuyến trong câu hỏi. Sau khi nhận thông tin đường đi PATH, điểm đích sẽ gửi lại một thông tin RESV để thực hiện việc dành riêng. Các điểm trung gian quyết định từng phần một cho dù chúng có thể thực hiện yêu cầu hay không. Nếu một trong các phần này thoát khỏi phần dành riêng, một thông báo lỗi sẽ được gửi tới bộ nhận. Nếu việc dành riêng thành công, băng thông cần thiết và không gian đệm sẽ được xác định. Sau khi kết nối và dành riêng được thiết lập nguồn gửi một cách định kỳ các thông tin đường đi để thiết lập hay cập nhật trạng thái, và bộ nhận định kỳ gửi thông tin RESV để thiết lập hay cập nhật trạng thái dự trữ. Không có thông tin cập nhật việc dành riêng sẽ kết thúc. Nó được gọi là trạng thái – mềm ( soft-state). Khi RSVP được sử dụng cùng với đảm bảo chất lượng dịch vụ định tuyến, các thông tin về đường đi được định tuyến sử dụng đảm bảo chất lượng dịch vụ định tuyến. Các thông tin RESV và dành riêng trên các tài nguyên sẽ không có tác dụng bởi giao thức định tuyến. Nhờ có sự tự nhiên động của tiêu chuẩn chọn đường đi chất lượng dịch vụ định tuyến có thể dễ dàng hơn trong định tuyến đường đi ngắn nhất. Điều này cho phép băng thông hoặc số đo khác có thể thay đổi nhanh hơn, để từ đó đường đi đang được chọn sẽ không còn là một với khả năng tốt nhất để thực hiện dòng lưu lượng. Mỗi sự thay đổi bất ngờ ít khi xảy ra trong định tuyến đường đi ngắn nhất, kể từ đó cấu hình mạng thường nhiều hơn hay ít hơn. Nếu đảm bảo chất lượng dịch vụ định tuyến truy vấn thêm tuyến mới, nó có thể điều khiển một tình hưống mới mà đường dẫn liên tục thay đổi và việc dành riêng lại được lặp lại cho đường dẫn mới. Để tránh những điều này giữa các đường đi, nó có thể xác nhận rằng đường đi hiện tại là không được thay đổi bởi một cái tốt hơn miễn là nó còn sử dụng được. Đường đi đó được coi là đã chốt (pinned) nếu nó được xác nhận trong phương thức giao thức lưu trữ tài nguyên mà đảm bảo chất lượng dịch vụ định tuyến không cần truy vấn thêm cái mới, còn nếu không đường đi được gọi là chưa chốt. Chốt đường đi sử dụng kỹ thuật giao thức lưu trữ tài nguyên trạng thái mềm, do đó một đường đi đã chốt được thực hiện một cách định kì. Khi một đường đi được chốt định kì thông tin đường đi được định tuyến theo đường đi đã chốt. Việc chốt đảm bảo cho bất cứ giao thức lưu trữ tài nguyên nào truy vấn đảm bảo chất lượng dịch vụ định tuyến cho cùng dòng lưu lưọng, nó quay trở lại đường đi đã chốt thay vì việc tính toán đảm bảo chất lượng dịch vụ định tuyến đường đi hiện tại tốt nhất. Các đường nhận chốt trong khi xử lý thông tin đường đi. Chúng không được chốt khi: Hết thời hạn gửi thông báo hay một PATHEAR được gửi. Tham số của thông tin đường đi bị thay đổi. Phát hiện thấy lỗi. 1.4.4 Đảm bảo chất lượng dịch vụ định tuyến với điều khiển tải Một trong những mục đích của đảm bảo chất lượng dịch vụ định tuyến là ứng dụng mạng tốt hơn. Điều này hơi mâu thuẫn với mục đích chính là tìm kiếm luân phiên đường đi để thực hiện các yêu cầu chất lượng dịch vụ của dòng lưu lượng. Khi lưu lượng lớn được tải với chỉ những đường dẫn có thể cung cấp sự đảm bảo chất lượng dịch vụ yêu cầu có thể lâu, đường đi ngắn nhất lưu lượng được định tuyến dọc theo đường đi luân phiên, một sự phân phối của dòng lưu lượng đến sự tắc nghẽn của mạng điều khiển đến có nhiều dòng lưu lượng hơn bị khoá trong tương lai. Điều này gợi đến việc sử dụng điều khiển tải cấp độ cao hơn để đảm bảo đường đi được chọn không được sử dụng nhiều của tài nguyên mạng mà tổng thông lượng giảm xuống. Cho mỗi đường dẫn đến phân số tuân theo đã được tính toán, khi có một sự cố gắng dành riêng: trong đó Bavaiable i là thông lượng cho phép trên đường dẫn i nơi mà tài nguyên được cố gắng để dự trữ, brequested là thông lượng yêu cầu của dòng và bcapacity i là tổng dung lượng của đường dẫn i. Việc dành riêng được xác định chỉ nếu phân số này, đưa ra băng thông cho phép trên đường dẫn nếu việc dành riêng được chấp nhận, là lớn hơn 1 dự trữ trước, hay băng thông dành riêng. Đường dẫn càng được sử dụng lâu hơn, thì băng thông dự trữ sẽ cao hơn. II.Thuật toán định tuyến 2.1 Lời giới thiệu Chương này thảo luận về chất lượng dịch vụ định tuyến và các thuật toán được sử dụng để giải quyết chúng. Các vấn đề định tuyến sử dụng một hoặc hai số đo, và sự phức tạp của chúng cũng sẽ được thảo luận. Chương này đưa ra các giải pháp cho các vấn đề đơn giản và hướng tiếp cận đối với các vấn đề phức tạp hơn. Các giải pháp này dựa vào thuật toán đường đi ngắn nhất, thuật toán Dijkstra và thuật toán Bellman-Ford. Phần 2.6 thảo luận về tình huống thông thường nhất, khi mà băng thông và bước nhảy là các số đo. Phần 2.7 giới thiệu một trường hợp đặc biệt: độ trễ ràng buộc đầu cuối. Nó có một số đo đơn là chức năng phức tạp của 1 số phần tử. 2.2 Ghi chú Mô hình mạng được biểu thị dưới dạng một đồ thị G(N,A), trong đó N(G) thể hiện cho các nút của đồ thị, A(G) thể hiện cho các cung biểu diễn đường liên kết trong mạng. n là số lượng nút, m là số lượng các liên kết trong mạng. Đường liên kết aЄA từ nút u đến nút v được kí hiệu bằng (u,v). Mỗi đường liên kết aЄA có tải trọng wi(a) cho tất cả các số đo i. w(u,v) là tải trọng tương đương với liên kết (u,v) trong đường đi P=(u1,u2,…,ui) và w(P) là tải trọng cho toàn bộ đường đi. 2.3 Số đo: Để có thể tìm ra đường đi khả thi mà thoả mãn được yêu cầu chất lượng của lưu lượng thì phải có một số số đo phù hợp nhằm đo được các yêu cầu. Các số đo phải được lựa chọn sao cho các yêu cầu có thể được biểu thị bằng một số đo, hoặc tổng hợp của nhiều số đo thích hợp. Khi các số đo định nghĩa được các dạng của chất lượng dịch vụ đảm bảo, thì mạng có thể được hỗ trợ. Nếu nó không thể được sắp xếp trong sự kết hợp của các số đo thì không yêu cầu nào được hỗ trợ. Các số đo thường được sử dụng trong định tuyến QoS và định tuyến ràng buộc được chia thành 3 loại, cũng được gọi là các quy tắc cấu tạo của số đo. Số đo bao gồm: Tính cộng: if w(P) = w(u1; u2) + w(u2; u3) + : : : + w(ul¡1; ul) Tính nhân: if w(P) = w(u1; u2) . w(u2; u3) ………….. w(ul¡1; ul) Tính lõm: if w(P) = min(w(u1, u2),w(u2, u3),......;w(ul¡1, ul)). Tính cộng bao gồm độ trễ, trễ pha, chi phí và số bước nhảy. Độ tin cậy [(1-tỉ lệ mất)], là tính nhân, trong khi đó, băng thông, đơn vị được sử dụng nhiều nhất là tính nhân. Tính cộng bằng cách thay thế các tải trọng liên kết wi và ràng buộc c. Bằng các thuật toán logwi và logC. 2.4 Các vấn đề về định tuyến: 2.4.1 Các vấn đề định tuyến số đo đơn Trong trường hợp đơn giản nhất, các yêu cầu QoS của lưu lượng được biểu thị tốt nhất bằng 1 trong các số đo (giới thiệu trong phần 2.3). Vấn đề hoặc là tối ưu hoặc là ràng buộc. Các số đo được chia thành ràng buộc tuyến và ràng buộc liên kết. Tính lõm là ràng buộc liên kết vì số đo cho 1 đường đi phụ thuộc giá trị đoạn nút cổ chai trên liên kết. Tính cộng và tính nhân là ràng buộc tuyến, vì số đo cho 1 đường đi phụ thuộc vào toàn bộ giá trị của đường đi. Có 4 vấn đề với số đo đơn. *) Vấn đề 1: (định tuyến tối ưu liên kết) Cho mạng G(N,A) và 1 tính nhân đơn w(a) cho mỗi đường liên kết aЄA. Tìm đường đi P từ nút nguồn s đến nút đích t sao cho w(P) là rộng nhất. Vấn đề định tuyến liên kết tối ưu có thể được giải quyết bằng thuật toán Dijkstras và thuật toán Bellman-Ford đã được sửa đổi. Thuật toán Dijkstras (xem phụ lục A) được chỉnh sửa bằng cách thay đổi các tiêu chuẩn về lựa chọn nút tiếp theo được thêm vào là nút M để sao cho nút đó liên kết có băng thông rộng nhất, còn trong thuật toán chuẩn của Dijstra’s nút tiếp theo được lựa chọn dựa vào hàm tích luỹ. Ví dụ tìm một đường đi với băng thông là liên kết tối ưu. Tính nhân của băng thông này vốn là một vấn đề liên kết tối ưu ở nút cổ chai. Vấn đề 2 (Định tuyến liên kết ràng buộc) cho mạng G(N,A) , một số đơn concave w(a) với mỗi đường liên kết aЄA và điều kiện ràng buộc C, tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho w(P)≥ C vấn đề định tuyến liên kết ràng buộc có thể được dưa về dạng định tuyến liên kết tối ưu bằng cách tìm ra đường dẫn tối ưu và kiểm tra xem ràng buộc nào đạt yêu cầu. Một cách khác là cắt bớt cấu trúc liên kết bằng cách xoá bỏ những liên kết có băng thông < C, và sau đó tìm ra đường đi ngắn nhất trên cấu trúc liên kết đã được cắt bớt đó. Từ đó định tuyến liên kết ràng buộc tìm ra được đường đi thoả mãn được yêu cầu chất lượng dịch vụ cho số đo liên kết ràng buộc. (không cần thiết phải tối ưu). Ví dụ là tìm ra đường đi có băng thông theo yêu cầu. Vấn đề 3 (định tuyến đường đi tối ưu) cho mạng G(N,A) và một tính cộng đơn w(a) với mỗi liên kết aЄA, tìm đường đi P từ điểm nguồn s tới điểm đích t sao cho w(P) nhỏ nhất. vấn đề định tuyến đường đi tối ưu có thể được giải quyết trực tiếp bằng thuật toán Dijstra hoặc thuật toán Bellman-Ford. Định tuyến đường đi tối ưu tìm ra đường đi tốt nhất cho một s ố đo đường đi ràng buộc. Một vấn đề điển hình có thề tìm được đường đi với số bước nhảy ít nhất, tổng chi phí thấp nhất hoặc độ trễ nhỏ nhất tất cả các giá trị đó là các số đo đường đi ràng buộc vì chúng là additive. Vấn đề 4 (định tuyến đường đi ràng buộc) cho mạng G(N,A) và một số đo additive đơn w(a) với mỗi liên aЄA, v à điều kiện ràng buộc C tìm đường đi P từ điểm nguồn s tới điểm đích t sao cho w(P)≤C Vấn đề định tuyến đường đi ràng buộc có thể được giải quyết trực tiếp bằng thuật toán Dijstra hoặc thuật toán bellman-Ford. Định tuyến đường đi ràng buộc tìm ra đường đi với độ trễ và chi phí thấp hơn mức yêu cầu. cả bốn vấn đề nêu trên đều là phức tạp đa thức. Xem phụ lục B. 2.4.2 các vấn đề định tuyến với một số số đo Thường thì một số tập hợp của nhiều số đo là cần thiết để mô tả các yêu cầu của dich vụ. Tuy nhiên một số tập hợp tính toán quá phức tạp nên chúng không thực dụng. Bất kỳ sự kết hợp nào của hai hoặc nhiều hơn số đo, hoặc là tính cộng hoặc là tính nhân, là NP-complete. Các tập hợp duy nhất cho phép tính toán đường đi với độ phức tạp đa thức là những tập hợp của số đo tính nhân như băng thông với các số đo khác, thông dụng nhất là độ trễ hoặc số bước nhảy. Đã có nhiều nỗ lực nhằm đơn giản vấn đề này. Wang và Crowcroft đã đề xuất ra một số đo hỗn hợp đơn là kết hợp của tất cả các số đo mong muốn. Họ kết luận rằng nó được sử dụng chỉ như là một chỉ báo, chứ không chứa đựng tất cả các thông tin cần thiết để quyết định đường đi nào có thể đáp ứng được các yêu cầu chất lượng dịch vụ QoS. Tuy nhiên trong một số trường hợp, băng thông có thể được sử dụng như một số đo đơn. Trong khi một kết nối có thể có nhiều yêu cầu về QoS thì những yêu cầu này chủ yếu chuyển thành các yêu cầu về băng thông. Guerin et al đề xuất ra một phương trình cho sự sắp xếp các ràng buộc trễ trong ràng buộc băng thông. Bảng 2.1 biểu diễn tổng hợp của 2 số đo từ 4 vấn đề đơn mô tả ở trên kết hợp 2 vấn đề tối ưu bị bỏ trống vì không hợp lí. Tất nhiên, vẫn kết hợp được 2 tối ưu, nhưng phải đưa các vấn đề phức hợp về dạng 2 số đo đơn. Tối ưu thứ 2 chỉ được sử dụng nếu có nhiều hơn một đường dẫn khả thi liên quan tới tối ưu thứ nhất. Phương pháp này được sử dụng trong các thuật toán như wsp và swp (xem phần 2.6) Bảng 2.1 Sự phức tạp của việc kết hợp các số đo -Sự cắt giảm: Một kĩ thuật quan trọng nhằm giải quyết các vấn đề phức hợp đó là cắt bớt mạng. Trường hợp các ràng buộc liên kết, giá trị của số đo trên tuyến luôn luôn bằng giá trị trên đường liên kết có giá trị thấp nhất. Do vậy, 1 liên kết mà không thoả mãn yêu cầu, (ví dụ như băng thông bất kì), là không khả thi. Những liên kết này bị xoá khỏi cấu trúc liên kết. Điều này giúp cho bất kì đường đi nào trên cấu trúc liên kết cũng thoả mãn được các yêu cầu của liên kết ràng buộc. -Các vấn đề định tuyến tổng hợp: + Vấn đề 5 (định tuyến liên kết tối ưu - liên kết ràng buộc). Cho mạng G(N,A), số đot ính nhân wi(a), i = 1,2; Với mỗi liên kết a thuộc A và điều kiện ràng buộc C1. Tìm đường đi từ điểm nguồn s đến điểm đích t sao cho w2(P) lớn nhất, trong khi w1(P)≥ C1 . Vấn đề này có thể đưa về dạng 1: vấn đề định tuyến liên kết tối ưu bằng cách cắt bớt mạng, xoá bỏ tất cả các liên kết mà ràng buộc w1(P) ≥C1 không được đáp ứng. Sự phức tạp của quá trình cắt bỏ cấu trúc liên kết tỉ lệ với m- số lượng các liên kết trong mạng, bởi vậy vấn đề liên kết ràng buộc, liên kết tối ưu là thuộc sự phức tạp đa thức. + Vấn đề 6 (định tuyến ràng buộc đa liên kết) Cho mạng G(N,A), số đo concave wi(a), i=1,2; Với mỗi liên kết a thuộc A và điều kiện ràng buộc Ci , i=1,2. Tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho wi(P)≥ C1 với tất cả các giá trị i. Cũng giống vấn đề 5 là đưa về dạng 1 bằng cách cắt bớt mạng, thì vấn đề 6 đưa về dạng 2: vấn đề định tuyến liên kết ràng buộc. + Vấn đề 7 (định tuyến liên kết ràng buộc, đường đi tối ưu) Cho mạng G(N,A), số đo wi(a), i=1,2, trong đó w1 là concave, với mỗi liên kết a thuộc A, và một điều kiện ràng buộc C1. Tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho w2(P) nhỏ nhất, w1(P)≥C1. Vấn đề định tuyến liên kết ràng buộc, đường đi tối ưu có thể được cắt bớt mạng đề đưa về dạng 3: vấn đề định tuyến đường đi tối ưu. + Vấn đề 8 (định tuyến liên kết ràng buộc, đường đi ràng buộc) Cho mạng G(N,A), số đo wi(a), i=1,2; trong đó w1 là concave, với mỗi liên kết a thuộc A , và các điều kiện ràng buộc Ci, i=1,2. Tìm đường dẫn P từ điểm nguồn s đến điểm đích t sao cho wi(P) ≥C1, w2(P)≤ C2. Vấn đề định tuyến liên kết ràng buộc, đường đi ràng buộc có thể đưa về dạng 4: vấn đề định tuyến đường đi ràng buộc, bằng cách cắt bớt mạng. 4 vấn đề phức hợp nêu trên đều có thể dễ dàng giải quyết bởi vì một trong các số đo là ràng buộc liên kết. Cắt bớt mạng bằng cách bỏ qua các liên kết có giá trị không thoả mãn điều kiện, đưa các vấn đề phức hợp về vấn đề số đo đơn. Như đã thấy trong bảng 2.1, bên cạnh 4 liên kết ràng buộc phức hợp, có 1 vấn đề phức hợp tổng có thể giải quyết được qua nhiều lần. + Vấn đề 9 (định tuyến liên kết tối ưu, đường đi ràng buộc) Cho mạng G(N,A), số đo wi(a); i=1,2 trong đó wi là tính nhân, với mỗi liên kết a thuộc A và 1 điều kiện ràng buộc C2, tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho w1(P) lớn nhất, w2(P)≤C2. Vấn đề này được giải quyết bằng cách sử dụng thuật toán đường đi ngắn nhất đã được chỉnh sửa. Trên mạng, có m liên kết, các liên kết này có một số giá trị là số đo liên kết tối ưu. Gọi k là biểu thị cho số lượng các gía trị khác nhau của số đo. Rõ ràng k≤m vì một số liên kết có thể có những giá trị xác định. Các giá trị này có thể được dùng như các giới hạn giả thấp hơn C11, C12, …, C1k sao cho các số đo liên kết ràng buộc được tối ưu. Điều này giúp đưa vấn đề 9 về dạng 8 như đã nêu ở trên. Bắt đầu từ giá trị lớn nhất C1k và cắt bớt mạng bằng cách xoá bỏ những liên kết a có w1(a) < C1k, đường đi P khả thi chính là đường đi đầu trên thoả mãn w2(P) ≤C2. Nếu số đo liên kết ràng bưộc w1 là băng thông, thì trước hết tất cả các liên kết, trừ những liên kết có băng thông rộng nhất C1k sẽ bị xoá bỏ. Nếu có thể tìm được một đường đi thoả mãn ràng buộc tuyến trên cấu trúc liên kết đã được cắt bỏ, thì đó là đường đi với băng thông lớn nhất. Còn nếu không tìm được đường đi đó, thì liên kết với băng thông C1k-1 sẽ được thêm vào cấu trúc liên kết, và việc tìm kiếm sẽ được lặp lại. Nếu vân không tìm được đường đi khả thi, các liên kết với băng thông C1k-2 sẽ lại tiếp tục được thêm vào cấu trúc liên kết. Việc này sẽ tiếp diễn cho đến khi tìm được 1 đường đi khả thi, vấn đề này phức tạp hơn các vấn đề từ 5 đến 8 nhưng vẫn có thể giải quyết được qua nhiều lần. Hai vấn đề phức tạp hơn còn tồn tại là MCP (vấn đề định tuyến ràng buộc đa tuyến) và MCOP(vấn đề định tuyến đường đi ràng buộc, đường đi tối ưu hay còn gọi là vấn đề tối ưu đa ràng buộc). Những số đo trong các vấn đề này không phải là concave, bởi vậy đây là những vấn đề NP-complete chúng không thể giải quyết qua nhiều lần, nếu sử dụng tập hợp các số đo này thì cần phải có những cách giải quyết khác. + Vấn đề 10 (Định tuyến ràng buộc đa thức) Cho mạng G(N,A), số đo additive wi, i=1,2, với mỗi đường liên kêt a thuộc A, và điều kiện ràng buộc Ci, i=1,2. Tìm đường dẫn P từ điểm nguồn s đến điểm đích t sao cho wi(P)≤ Ci với tất cả các giá trị i. Vấn đề định tuyến ràng buộc đa tuyến là NP - Complete. Vấn đề này được biết đến rất nhiều, nó chỉ ra rằng: vấn đề số đo patition và additive dùng để chứng minh NP-Complete bằng cách này hay cách khác, có thể đưa các vấn đề đa thức nêu trên về các vấn đề số đo đơn để dùng các thuật toán đường đi ngắn nhất để giải quyết chúng. Ví dụ có thể thực hiện việc này bằng cách cắt bỏ những liên kết có năng suất không hiệu quả để giải thích cho 1 ràng buộc liên kết. Ở đây, cả 2 số đo đều là ràng buộc tuyến nên việc cắt giảm đơn giản là không thể. Chính vì vậy vấn đề không thể giải quyết qua nhiều lần được. + Vấn đề 11 (định tuyến tuyến ràng buộc, tuyến tối ưu) Cho mạng G(N,A), số đo additive wi(a), i=1,2, với mỗi đường liên kết a thuộc A và 1 điều kiện ràng buộc C1 cho số đo w1, tìm đường đi từ điểm nguồn s đến điểm đích t, sao cho w2(P) nhỏ nhất, w1(P)≤ C1. Vấn đề này cũng là NP-Complete . Vấn đề MCOP (vấn đề tối ưu đa ràng buộc) thỉnh thoảng được dùng như dạng của định tuyến tuyến ràng buộc. Tuyến tối ưu, nhưng cũng có thể được hiểu như là vấn đề multi-contrained với chức năng chi phí, và có thể hoặc không là một trong các số đo tuyến ràng buộc. Lí do nêu trên là dựa vào giả thuyết: các số đo là độc lập với nhau. Tuy nhiên, điều này không cần thiết. Trong các mạng sử dụng các thuật toán rate-proportional scheduling, đặc biệt là WFQ-Scheduling, thì các vấn đề về độ trễ, dung pha có thể giải quyết qua nhiều lần bằng thuật toán Bellman-Ford. Nó dựa vào thực tế là trong một môi trường như vậy , bước nhảy chỉ là một thông số nếu như ràng buộc dung pha có thể đạt yêu cầu. Bởi vậy có thể giải quyết vấn đề này bằng cách giải quyết ràng buộc độ trễ, kiểm soát tính toán bước nhảy sao cho đảm bảo các yêu cầu về độ dung. Nếu tất cả các số đo cho phép nhận các giá trị nguyên trong giới hạn thì vấn đề cũng có thể được giải quyết qua nhiều lần. Ví dụ, bước nhảy vốn là một số đo có giá trị nguyên và được giới hạn bằng đường kính của đồ thị. 2.5 Các hướng tiếp cận từ nghiệm suy đôi với các vấn đề phức tạp NP-Complete: Như đã nói trong phần 2.4.2, sự phức tạp trong tính toán của các vấn đề MCP, MCOP, vấn đề 10,11 là NP-Complete. Để giải quyết các vấn đề này, thì cần tính gần đúng từ nghiệm suy nhiều lần. Các vấn đề được đưa về dạng đơn giản để giải quyết bằng thuật toán đường đi ngắn nhất. Hình 2.1: Vấn đề định tuyến ràng buộc đa tuyến. Vùng khả thi với mỗi i, wi(P)≤ Ci, được biểu thị bằng 1 hình chữ nhật góc dưới bên trái. Các chấm đen biểu thị các tuyến. Xem hình 2.1 mỗi đường đi P có một số giá trị cho mỗi số đo wi(P). Hình này mô phỏng tình huống với hai ràng buộc. Các tuyến là các chấm đen trong đồ thị theo giá trị của các số đo. Các phần tiếp theo xem lại một số phép tính gần đúng từ nghiệm suy nhiều lần. Các thuật toán cho các vấn đề MCOP, cũng như MCP dễ dàng được giải quyết chỉ bằng cách kiểm tra đường đi khả thi đối với các ràng buộc hay không. + Thuật toán Chen và Nahrstedt Chen Và Nahrstedt đã đề xuất 1 kĩ thuật để giải quyết vấn đề MCP. Tại đó giá trị số đo thứ 2 bị giới hạn bởi các giá trị nguyên, các vấn đề có thể giải quyết được qua nhiều lần. Thay tải trọng liên kết w2 bằng một hàm tải trọng mới (2.2) Dựa MCP (G,s,t, w1, w2, C1, C2) về dạng đơn giản hơn MCP (G, s, t, w1, w2’, C1, x) trong đó x là số nguyên xác định trước. Vấn đề 10 như sau: + Hướng nghiệm suy 1: Cho mạng G(N,A), số đo w1(a) và w2’(a) với liên kết a thuộc A, điều kiện ràng buộc C1 và x. Tìm đường đi P từ điểm nguồn s đến điểm đích t, sao cho w1(P)≤C và w2’(P)≤ x. Chen và Nahrstedt đã mở rộng thuật toán Dijkstra và Bellman-Ford để giải quyết vấn đề này. Mệnh đề 1: giải pháp cho vấn đề nghiệm suy gần đúng cũng là giải pháp cho vấn đề gốc Chứng minh: từ phương trình 2.2 Suy ra Đường đi P là giải pháp cho vấn đề đơn giản, phương trình W2’(P)≤x (2.3) phải được đảm bảo Có thể dễ thấy là P cũng là giải pháp cho vấn đề gốc Do đó w2(P) ≤ C2 Giải pháp cho vấn đề gốc là giải pháp cho vấn đề đơn giản. Vd: Nếu đường đi P có 3 bước nhẩy với tải trọng liên kết 4,5 và 6, nó là giải pháp cho vấn đề gốc khi C2=15. Chọn x=5, (2.1) sinh ra tải trọng mới là 2,2 và 2. Cộng lại chúng ta có tải trọng tuyến w’(P)=6 và w’(P)<=x không được đảm bảo. Nếu đường đi P, với chiều dài l(P) là giải pháp cho vấn đề gốc, thì 1 điều kiện hiệu quả cũng là giải pháp cho vấn đề đơn giản là Wi(P)≤(1-) (2.4) Điều này có nghĩa là đường đi cần phải vượt quá khả năng bằng 1 hệ số phụ thuộc vào chiều dài l(P) của nó và giá trị của x. Điều kiện 2.4 là hiệu quả nhưng không cần thiết. Trong ví dụ trên tải trọng là 6,6 và 3, tải trọng mới sẽ là 2,2 và 1. Điều kiện w’(P)<=x được đảm bảo, dù (2.4) không được thoả mãn. Cách nghiệm suy có thể áp dụng cho chỉ 1 số đo nếu không có giải pháp nào cho vấn đề đơn giản MCP (G, s, t, w1, w2’, C1, x), thì vấn đề MCP (G, s, t, w1’, w2, x2, C2) nên thử bằng cách khác. Còn nếu có giải pháp, thì cách nghiệm suy chính là 1 giải pháp. + Thuật toán Jaffe Jaffe đề xuất hàm chiều dài đường đi không thuộc đường thẳng f(P) = max{w1(P), C1} + max {w2(P), C2} (2.5) Trong đó, giá trị nhỏ nhất đảm bảo giải quyết vấn đề MCP bằng cách tìm ra tuyến khả thi nếu có. Tuy nhiên, nó không được giải quyết bằng thuật toán đường đi ngắn nhất, vì hàm chiều dài này không thuộc đường thẳng. Bởi vậy ông dùng 1 thuật toán tương tự sử dụng đường nối của các tải trọng: W(u,v) = d1.w1(u,v) + d2.w2(u,v) (2.6) Như vậy vấn đề trở thành: tải trọng hợp là 1 số đo và có thể giải quyết bằng thuật toán đường đi ngắn nhất. Sau đó giải pháp là kiểm tra với điều kiện ràng buộc. + Hướng nghiệm suy 2: Cho mạng G(N,A), số đo wi(a), i= 1, 2 với liên kết a thuộc A, điều kiện ràng buộc C1 và số nguyên dương di, i= 1, 2, tính hàm tải trọng mới w(u,v) = d1. w1(u,v) + d2. w2(u,v) và tìm ra đường đi P từ điểm nguồn s đến điểm đích t sao cho w(P) nhỏ nhất. Kiểm tra nếu đường đi P thoả mãn ràng buộc wi≤Ci. Hình 2.2: các đường thẳng tương đương trong thuật toán của Jaffe giải pháp khả thi có thể được tìm thấy với 1 giá trị cụ thể di. Hình 2.3 biểu diễn các đường cong của hàm tải trọng kết hợp thậm chí nếu có 1 giải pháp khả thi, thì thuật toán cũng có thể không tìm ra nó, là trường hợp bên phải.Nếu giải pháp mà thuật toán tìm ra không khả thi, thì ta có thể bằng cách thay đổi giá trị của di để tìm ra giải pháp khả thi. Nhưng vì các đường cong tương đương thuộc đường thẳng, nên có thể xuất hiện tình huống là có giải pháp khả thi nhưng không phải tìm được bằng bất cứ giá trị nào của di. Thuật toán Thuật toán này thay vì sử dụng đường nối tải trọng, thì sử dụng hàm non-lineat (làm cong các đường thẳng tương đương) để giải quyết vấn đề MCP Tải trọng đường được nối là: (2.7) Khi q -> ∞ phương trình (2.7) sẽ biến đổi thành (2.8) Phương trình này đảm bảo tất cả các điều kiện ràng buộc được thoả mãn nếu w(P)≤1. Hình 2.3 không có tuyến nhưng đường cong đang tồn tại tương tự. Giá trị q làm tăng thêm khả năng của thuật toán. Hình 2.3 biểu diễn tình huống tương tự như hình 2.2. Số đo đã tìm được chính xác đường khả thi. Vấn đề trong (2.6) đó là số đo đó không phải là tính cộng, do vậy mà khi tính toán tải trọng của đường đi. Kết quả là TAMCRA phải sử dụng thuật toán Dijkstra. Nó không dừng lại khi đã tìm ra đường đi khả thi đến đích, mà tiếp tục tìm ra k đường dẫn khác nữa. Sau đó với mỗi đường dẫn, tải trọng của đường đi được tính toán bằng phương trình (2.7). Trong TAMCRA, k được lựa chọn trước, trong khi đó, ở các phiên bản khác của thuật toán này đó là thuật toán SAMCRA, lại kiểm soát giá trị của k sáo cho tự thích nghi. Điều này có nghĩa TAMCRA là đa thức phức tạp, trong khi SAMCRA là một thuật toán chính xác và sự phức tạp của nó là số mũ. Sự lựa chọn k trong TAMCRA là sự thoả hiệp giữa việc thực thi và tính phức tạp. Còn SAMCRA đảm bảo tìm được một đường dẫn khả thi nếu như nó tồn tại. Để làm giảm sự phức tạp của các thuật toán, chỉ quan tâm đến đường dẫn không trội. Đường dẫn P là trội nếu wi(Q)<= wi(P) với tất cả các giá trị i, với 1 sự không cân bằng cho ít nhất 1 giá trị i. Điều này giúp giới hạn việc tìm kiếm trong không gian. + Hướng nghiệm suy 3 (TAMCRA) Cho mạng G (N,A), số đo wi(a), i=1,2 với mỗi đường liên kết a A, điều kiện rằng buộc ci,số nguyên dương di, i=1,2 và k.Tính toán hàm tải trong mới được xác định bằng pt 3,6 và tìm ra đường đi ngắn nhất từ điểm nguồn điểm & đến nguồn đích t.Với những đường đi đó, tính tải trọng đường đi,và lựa chọn đường đi P sao cho w(P) nhỏ nhất.Kiểm tra giải pháp đường đi P thoả mãn đk ràng buộc wi ≤ ci với mỗi I hay không. Thuật toán Iwata. Iwata đề xuất giải pháp trực tiếp đối với vấn đề MCP,thuật toán tìm ra đường đi ngắn nhất ,hoặc các tuyến phụ thuộc vào 1 số đo và sau đó kiểm tra ràng buộc có được đảm bảo không.Nếu không,nó tìm ra tuyến ngắn nhất với số đo khác và kiểm tra lại các điều kiện ràng buộc.Vấn đề là các tuyến khả thi không cần phải là ngắn nhất đối với bất kì số đo nào.Trong hình 2.4, tuyến khả thi là đường thứ 2 liên quan đến tải trọng 1. + Hướng nghiệm suy 4 (thuật toán IWATA) Cho mạng G(N,A), số đo Hình (2.4) Quy trình tìm kiếm của thuật toán Iwata wi(a), i=1,2 với mỗi liên kết a Є A, điều kiện ràng buộc Ci, i=1,2. Tìm đường đi P sao cho wi(P) nhỏ nhất với mỗi giá trị cụ thể i, hoặc một số đường đi nhẹ nhất với wi(OP). Kiểm tra đường đi P thoả mãn điều kiện ràng bưộc wi ≤ Ci với mỗi i không, nếu không thì tím i khác. - Thuật toán ngẫu nhiên: Thuật toán này được đề xuất bởi Korkmaz và Krun để giải quyết vấn đề MCP. Nó gồm 2 phần: kiểm tra bước đầu và kiểm tra ngẫu nhiên. Trong bước đầu, thuật toán tính toán các đường đi tối ưu từ điểm nguồn u đến điểm đích t với mỗi số đo wi, và với những số đo tổng hợp tuyến tính. Thông tin từ bước khởi đầu đó được sử dụng để tìm ra đường đi khả thi. Trong bước thứ 2, thuật toán sử dụng kiểm tra ngẫu nhiên breadth-first(BFS) Trong khi thuật toán BFS phát hiện tất cả các điểm, Thì thuật toán ngẫu nhiên sẽ chọn ngẫu nhiên các điểm, cho đến khi đạt đến đích. Thuật toán ngẫu nhiên còn sử dụng tính chất look-ahead, tức ra trước khi phát hiện 1 điểm, só sử dụng thông tin của bước khởi đầu để tìm kiếm xem có khả năng đạt đến điểm đích t thông qua điểm đó không. Nếu đường đi tối ưu từ điểm đó đến đích, ứng với những số đo khác nhau, mà không thoả mãn điều kiện ràng buộc thì tất nhiên sẽ không có đường đi đồng thời thoả mãn. Nếu không có cơ hội tốt để đạt tới t, thì điểm đó sẽ bị loại. Phương pháp này giúp giảm việc tìm kiếm trong không gian. + Hướng nghiệm suy 5(thuật toán ngẫu nhiên) Cho mạng G(N,A), số đo wi(a), i=1,2 với mỗi liên kết a Є A, điều kiện ràng buộc Ci và tải trọng di, i=1,2. Bước khởi đầu tính đường đi ngắn nhất từ điểm nguồn u đến điểm đích t, ứng với mỗi số đo wi, và số đo tổng hợp tuyến tính (2.5). Sử dụng kiểm tra ngẫu nhiên breadth-first tìm đường dẫn P từ điểm nguồn s đến điểm đích t sao cho wi(P) ≤ Ci với tất cả i. Để giảm việc tìm kiếm trong không gian, Khi tìm được 1 điểm thì dùng thông tin khởi đầu kiểm tra xem có thể tìm được đường đi khả thi thông qua điểm đó hay không. Nếu không có thì loại bỏ nó. H-MCOP Thuật toán này được đề xuất bởi Korkmaz và Krunz để giải quyết vấn đề MCOP. Nó trở về đường đi khả thi, cũng là làm nhỏ nhất hàm chi phí đã được lựa chọn, dựa vào chi phí 1 đường liên kết C(u,v) ứng với mỗi đường liên kết là một ràng buộc QoS wi(u,v) hoặc 1 số hàm chi phí tương tự. Trong bước đầu tiên, thuật toán tính tuyến khả dụng từ một điểm u đến điểm đích t ứng với số đo tổng hợp tuyến tính (2.5) thiết lập bước này trở lại tuyến khả thi với số đo tổng hợp tuyến tính. Sau đó, thuật toán sử dụng hàm chiều dài tuyến không thẳng của phương trình (2.6) để tính toán các đường đi từ điểm nguồn đến điểm s. Nó phát hiện ra mỗi điểm u dựa vào giá trị nhỏ nhất của hàm chiều dài tuyến không thẳng hàng. Với mỗi điểm u, thuật toán chọn ra đường đi ngắn nhất từ s đến t để xác định chiều dài từ điểm s đến t. Nếu các tuyến đi qua u mà khả thi, thuật toán sẽ lựa chọn điểm mà có đường dẫn có hàm chi phí cơ sở nhỏ nhất. Nếu không có tuyến khả dụng nào, thì thuật toán lựa chọn điểm có đường dẫn có số đo không tuyến tính nhỏ nhất, để đường dẫn này có thể trở thành khả thi. Sau đó, thuật toán tiếp tục từ điểm chọn u, tìm những điểm v tiếp theo bằng cách tương tự. Cuối cùng kết qủa nó trở về tuyến khả dụng. - Hướng nghiệm suy 6 (H-MCOP) Cho mạng G(N,A), số đo wi(a), i=1,2 và (a) với mỗi liên kết a Є A, điều kiện ràng buộc Ci, i=1,2 với số đo wi, bước đầu tìm đường dẫn ngắn nhất từ mỗi điểm u đến điểm đích t ứng với số đo tổng hợp tuyến tính. Sau đó từ điểm s tìm điểm từ s đến t qua u dựa vào tải trọng của đường dẫn P. Tải trọng này được tính bằng cách nối tải trọng không tuyến tính không tuyến tính w(s,u) với tải trọng tuyến tính w(u,t). Nếu một số đường dẫn tìm được là khả thi, chọn 1 đường làm cho tải trọng tổng hợp tuyến tính nhỏ nhất, nếu không thì chọn đường làm cho tải trọng không tuyến tính nhỏ nhất. Tiếp tục cho đến khi tìm được điểm đích t, tìm được đường dẫn P sao cho C(P) nhỏ nhất, wi(P)≤Ci với tất cả các giá trị của i. A* Prune Lui và Ramakrishnan đề xuất thuật toán A*Prune để giải quyết vấn đề MCOP. Thuật toán này tìm ra những tuyến ngắn nhất. Đây là thuật toán chính xác, nhưng sử dụng kỹ thuật tương tự như các thuật toán nghiệm suy. Nó dùng bước tính khởi đầu giống thuật toán ngẫu nhiên. Thuật toán tính những tuyến ngắn nhất ứng với mỗi số đo, từ mỗi điểm nguồn u đến điểm đích t cũng như từ điểm nguồn s đến tất cả các điểm u. Sau đó, nó thực hiện giống thuật toán Dijkstra, loại bỏ những điểm được lựa chọn bằng chiều dài đầu cuối dự tính trước của đường dẫn ứng với các số đo tổng hợp tuyến tính. Tất cả các điểm xung quanh được xem xét, nếu tạo thành đường vòng hoặc không thoả mãn điều kiện ràng buộc, sẽ bị cắt bỏ. Thuật toán sẽ tiếp tục cho đến khi tìm được các đường dẫn ngắn nhất (K), hoặc không thể tìm được thêm điểm nào nữa. Thuật toán luôn tìm được k đường dẫn ngắn nhất, hoặc tất cả các đường dẫn khả thi nếu nó ít hơn K. Nó dường như không chạy được trong Polynominal time, nhưng thực ra đây là 1 trường hợp 1 phiên bản khác của thuật toán có thể chạy được polynomial time, nhưng không cần thiết phải tìm ra 1 giải pháp khả thi . - Hướng nghiệm suy 7 (A* Prune). Cho mạng G(N,A), số đo wi(a), i= 1,2 với mỗi liên kết aЄA, điều kiện ràng buộc Ci, i=1,2, bước đầu tiên, tìm đường đi ngắn nhất từ mỗi điểm u đến điểm đích t và từ điểm nguồn s đến điểm đích u ứng với mỗi số đo và số đo tổng hợp tuyến tính (2.5). Sau đó từ điểm s tìm điểm từ s đến t qua u, dựa vào tải trọng của đường dẫn P. Tại mỗi bước, cắt bỏ tất cả những điểm không đi qua 1 đường dãn khả thi nào dụa vào thông tin ban đầu. Tiếp tục cho đến khi tìm được k đường dẫn ngắn nhất, hoặc đến khi không cần điểm nào 2.6 Ràng buộc băng thông Trong nhiều trường hợp băng thông là số đo quan trọng nhất, có khi chỉ sử dụng số đo. Thậm chí nếu có các yêu cầu về QoS mà liên quan đến các số đo khác, thì chúng thường được sắp xếp vào các yêu cầu về băng thông. Bởi vậy, nhiều sơ đồ định tuyến QoS chỉ quan tâm đến băng thông và tính bước nhảy. Bước nhảy là tính cộng nhưng băng thông là tính nhân, bởi vậy các vấn đề định tuyến này được xếp vào dạng là đinh tuyến tổng hợp polynomial time. Thuật toán này dựa vào sự lựa chọn giữa sự duy trì nguồn và sự cân bằng tải thông tin trên mạng. Đường dẫn khả thi tại điểm nút cổ chai của băng thông chưa chắc là lựa chọn tốt nhất, nếu như có một đường dẫn khác thoả mãn các yêu cầu và tiêu thụ thấp hơn các nguồn mạng. Sử dụng các tuyến đường đi xen kẽ quanh các liên kết nghẽn để cân bằng việc dùng mạng, nhưng lại tiêu thụ nhiều hơn nguồn vì đường đi ngắn nhát để duy trì nguồn mạng nhưng có thể dẫn đến nghẽn mạng. 2.6.1 Các thuật toán lựa chọn đường dẫn cơ bản : WSP Đường đi rộng nhất, ngắn nhất sẽ chọn ra đường đi có bước nhảy nhỏ nhất trong số những đường thoả mãn yêu cầu về băng thông nếu có nhiều đường có cùng bứơc nhảy, thì đường rộng nhất, tức là đường có băng thông tốt nhất, sẽ được lựa chọn. Về cơ bản là nó sẽ tìm ra tuyến khả thi ngắn nhất, bởi vậy đó là định tuyến tuyến tối ưu, liên kết ràng buộc (vấn đề 7) và có thể giải quyết qua nhiều bước. Tiêu chuẩn đường đi rộng nhất chỉ được sử dụng khi cần chọn ra trong những đường ngắn nhất nhưng có chiều dài bằng nhau. Thuật toán đảm bảo băng thông 1 (WSP). Cho mạng G(N,A), số đo wi(a), i=1,2 với liên kết aЄA, trong đó wi là băng thông, w2 là bước nhảy, băng thông nhỏ nhất yêu cầu C1, cắt bỏ bớt mạng bằng cách xoá bỏ tất cả những liên kết với w1<C1, tìm đường dẫn P từ điểm nguồn s đến điểm đích t sao cho bước nhảy w2(P) nhỏ nhất. Nếu có nhiều đường dẫn có cung bước nhảy, lựa chọn đường có băng thông w1(P) lớn nhất. Sau khi cắt bỏ bớt mạng, thì chọn đường dẫn trên tương tự như vấn đề 3 (Phần 2.4.1). Chỉ thực hiện bước thứ 2 nếu như có nhiều đường dẫn có bước nhảy nhỏ. Phương pháp này giúp bảo vệ nguồn mạng -SWP - Đường đi ngắn nhất, rộng nhất lựa chọn đường đi có băng thông lớn nhất có thể. Nếu có nhiều đường đi có băng thông rộng, thì chọn đường có bước nhảy nhỏ nhất. Cách này giúp cân bằng việc tải trên mạng. Thuật toán này áp dụng 2 thuật toán Dijkstra đầu tiên là tìm đường di rộng nhất (vấn đề 1). Gọi băng thông của đường đi rộng nhất là B. Sau khi cắt bỏ những liên kết có băng thông nhở hơn B, nó chạy thuật toán Dijkstra lần thứ 2 để tìm ra đường đi ngắn nhất trong số những đường đi rộng nhất (vấn đề 3) - Thuật toán đảm bảo băng thông 2 (SWP) Cho mạng G(N,A), số đo wi(a), i=1,2 với liên kết aЄA, trong đó w1 là băng thông, w2 là bước nhảy, băng thông nhỏ nhất C1, tìm đường dẫn Q từ điểm nguồn s đến điểm đích t sao cho w1 max. Gọi B=w1(Q) và cắt bớt mạng bằng cách xóa những liên kết có w1(a)<B. Sau đó tìm đường dẫn P từ điểm nguồn s đến điểm đích t sao cho bước nhảy w2(P) nhỏ nhất. SDP Đường dẫn có khoảng cách ngắn nhất, có lúc còn được gọi là thuật toán BSP(bandwidth-inversion shortest path), khoảng cách của 1 liên kết là nghịch đảo của băng thông trên 1 liên kết, và khoảng cách của đường đi là tổng khoảng cách tất cả các liên kết trên đường dẫn. đây là tổng hợp của 2 phương pháp trên. Khoảng cách được xác định để tìm ra những tuyến ngắn nhất khi tải trên mạng nhiều, và tìm ra những tuyến rộng nhất khi tải trung bình. Đường dẫn có khoảng cách ngắn nhất có thể được tìm bằng thuật toán đường đi ngắn nhất, dùng khoảng cách như 1 hàm chi phi. sdp được mở rộng thành dạng - Thuật toán đảm bảo băng thông 3(shortest- distance path) - Cho mạng G(N,A), số đo wi(a), i=1,2 với mỗi liên kết a , trong đó wi là băng thông, w2 là bước nhảy điều kiện băng thông nhỏ nhất C1. Cho và tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho nhỏ nhất + ebsp (enhanced band width-inversion shostest parth algorithm): Thuật toán đường đi ngắn nhất nghịch đảo băng thông nâng cao là một dạng nâng cao của thuật toán sdp, do Wang và Nhrstedt đề xuất nó thêm điều kiện cấm vào trong hàm tải trọng của sdp nhằm ngăn các đường dẫn không quá dài. Nó thực hiện bằng cách chặn những bước nhảy lớn - Thuật toán đảm bảo băng thông 4(ebsp) Cho mạng G(N,A), số đo wi(a), i= 1,2 với mỗi liên kết aЄA, trong đó w1 là băng thông và w2 là bước nhảy, điều kiện ràng buộc băng thông nhỏ nhất là C1, tìm đường đi P từ điểm nguồn s đến điểm đích t sao cho Trong đó các điều kiện a1,a2,...,ak là các điều kiện dọc theo đường dẫn P từ điểm nguồn s đến điểm đích t. Sao cho a1 là điều kiện ban đầu, ak là điều kiện cuối. - dap (dynamic alternative path): Dynamic-alternative path sử dụng thuật toán đường đi rộng nhất, ngắn nhất nhưng giới hạn bước nhảy là n+1, trong đó n là bước nhảy nhỏ nhất trong mạng chưa bị cắt giảm. Nếu không tìm thấy đường dẫn kả thi có bước nhảy nhỏ nhất, nó sẽ lựa chọn đường đi rộng nhất nếu không có đường đi khả thi, thì yêu cầu của lưu lượng cho 1 đường dẫn đảm bảo QoS sẽ bị từ chối. Thuật toán đảm bảo băng thông 5 (dynamic alternative path). Cho mạng G(N,A), số đo wi(a), i=1,2 với mỗi liên kết aЄA, trong đó w1 là băng thông, w2 là bước nhảy, điều kiện ràng buộc băng thông nhỏ nhất là C1, tìm đường dẫn Q từ điểm nguồn s đến điểm đích t sao bước nhảy nhỏ nhất là w2, gọi n=w2(Q). Cắt bớt mạng bằng cách xoá bỏ những liên kết có w1< C1. Tìm đường dẫn từ điểm nguồn s đến điểm đích t sao cho bước nhảy w2(P) nhỏ nhất trong khi w2(P)£n+1. Nếu có nhiều đường dẫn có cùng bước nhảy thì chọn ra 1 đường có băng thông w1(P) lớn nhất. 2.6.2 Tóm tắt những thuật toán với ràng buộc băng thông: Hình 2.5 biểu diễn mối quan hệ giữa các thuật toán. Thuật ngữ “shortest path algorithm” ở đây tức là thuật toán mà chỉ sử dụng bước nhảy như là 1 số đo. Nó tương đương với vấn đề 3, đường đi tối ưu, dù nó cho phép bất cứ một số đo nào, chứ không phải chỉ 1 số đo, mà trong đó tất cả các tải trọng liên kết là 1. Còn thay đổi tải trọng thành băng thông và tìm ra đường đi rộng nhất lại không tương đương giống vấn đề 1, liên kết tối ưu. Hình 2.5 Thuật toán băng thông ràng buộc kết hợp chúng dẫn đến 2 thuật toán: đường đi ngắn nhất, rộng nhất và đường đi rộng nhất- ngắn nhất. Số đo cơ sở được tối ưu trước, nếu như có nhiều đường đi cùng tối ưu như vậy thì số đo cấp III sẽ được sử dụng. Thuật toán dap thêm kiểm soát vào thuật toán wsp. Nó sẽ loại bỏ lưu lượng mà đường dẫn được lựa chọn có nhiều hơn 1 bước nhảy dài hơn đường đi ngắn nhất. Thuật toán khoảng cách ngắn nhất dùng thuật toán đường đi ngắn nhất cùng với các tải trọng liên kết là nghịch đảo của băng thông available. Thuật toán đường đi ngắn nhất tăng cường băng thông - nghịch đảo thêm vùng cấm nhằm chặn những đường dẫn dài. Trong sơ đồ, thuật toán càng cao thì càng nhấn mạnh vào giới hạn bước nhảy. 2.7 Ràng buộc trễ đầu cuối Định tuyến QoS đảm bảo băng thông rất được ưa chuộng trong nghiên cứu, nhưng đảm bảo độ trễ đầu cuối cũng là 1 phần quan trọng khác. Vấn đề là tính đường dẫn thoả mãn điều kiện ràng buộc đầu cuối D. Toán bộ trễ đầu cuối bao gồm: độ trễ lan truyền trên mỗi liên kết dọc theo đường dẫn, và độ trễ trên toàn tuyến. Dạng thứ nhất là 1 hàm tính cộng đặc thù, còn dạng thứ 2 lại phụ thuộc vào tỉ lệ kết nối. Nó cần thiết giống như băng thông, nó cũng là liên kết ràng buộc. Tuy nhiên vấn đề định tuyến không phải là bất cứ vấn đề tổng hợp nào, bởi vì giá trị nhỏ nhất (2.8) (phụ thuộc vào 2 ràng buộc tính cộng) là độ trễ lan truyền d(a), bước nhảy n, ràng buộc tuyến và tỉ lệ r. Bởi vậy nó không phải là vấn đề định tuyến nhiều ràng buộc, nhưng chúng ta chỉ có 1 hàm đối tượng. Bước nhảy có thể chỉ nhận giá trị nguyên và bị giới hạn dưới mức ít nhất tổng số liên kết trong mạng. Các giá trị r cũng có thể bị giới hạn giống trong vấn đề định tuyến 9. Vấn đề này có thể giải quyết bằng polynomial time. - Độ trễ đầu cuối là số đo . Giới hạn trên là D(P, r) = (2.9) Trong đó P là đường đi, r: tỉ lệ dự trữ, n(P) là bước nhảy của đường đi P, C là kích thước gói lớn nhất, d(a) là độ trễ lan truyền của liên kết aЄA, là giá trị biến thiên liên quan đến burst lớn nhất. Gọi D(P, r(P))= D(P) biểu hiện cho giá trị nhỏ nhất có thể của D(P,r) trong đó r(P) là tỉ lệ lớn nhất có thể trên đường đi bởi vậy: Trong đó r(a) liên quan đến tỉ lệ của liên kết a. - Thuật toán chính xác: Có m liên kết trên cấu trúc mạng, nhưng 1 số đường liên kết có tỉ lệ giống nhau nên số lượng các giá trị tỉ lệ khác nhau trên mạng k≤m. Gọi các tỉ lệ là rk. Bây giờ có k giá trị tỉ lệ khác nhau: r1<r2<…<rk. (giống vấn đề 9 phần 3.4.2). Cách tìm đường dẫn khả thi: với mỗi k sao cho 1≤k≤K. -Xoá tất cả các liên kết a có r(a)<rk - Dùng thuật toán Bellman-Ford H lần, dùng độ trễ lan truyền d(a) như 1 hàm chi phí, và dùng cách giải quyết vấn đề 3(vấn đề tuyến tối ưu) để xác định đường dẫn nào có độ trễ nhỏ nhất với tất cả các bước nhảy n,1≤n≤H. + Tính độ trễ của K.H đường dẫn để tìm: đường dẫn với độ trễ đảm bảo nhỏ nhất, hoặc đường dẫn khả thi với tỉ lệ dự trữ nhỏ nhất. Độ phức tạp của thuật toán là O(MHK). Nếu k gồm bằng M thì O(HM2) quá cao. bởi vậy các thuật toán về lượng là cần thiết để giảm bớt sự phức tạp của nó. -Thuật toán quantization (lượng) Ứng dụng với tỉ lệ và bước nhảy. Trong trường hợp với tỉ lệ, thì các tỉ lệ liên kết được nhóm lại thành các nhóm để nhóm tỉ lệ j thuộc r1(1+Є)j…r1. (1+Є)j+1. Sau đó với mỗi nhóm, thực hiện việc cắt giảm. Có thể áp dụng các thuật toán nêu trên, mức bảo đảm độ trễ của thuật toán là 1+ Єlần, nhiều hơn giá trị thấp nhất. Giá trị € là để lựa chọn giữa độ chính xác hay độ phức tạp của thuật toán. - Thuật toán chi phí nhỏ nhất: Wchi phí(r,P)=C(r,n(P), D(P,r)) (3.0) Có thể lựa chọn bằng cách cho các tiêu chuẩn của nó nhỏ nhất. Ví dụ hàm chi phí wchi phí=r làm cho tỉ lệ tiêu dùng nhỏ nhất, để cho wchi phí=n(P).r nhỏ nhất. Cách khác là dùng tiêu chuẩn cân bằng tải mạng. Thuật toán Miniman Rate (làm nhỏ nhất tỉ lệ quan hệ): làm nhỏ nhất tỉ lệ lớn nhất của bất cứ liên kết nào tỉ lệ available.