batnapmoto_aloanhha95
New Member
Tải Thuật toán đường đi ngắn nhất và rộng nhất SWP
MỤC LỤC
I. Đảm bảo chất lượng dịch vụ định tuyến
1.1. Giới thiệu:
1.2 Kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở
1.3 Các mục tiêu của đảm bảo chất lượng dịch vụ định tuyến
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ụ.
1.4.1 Dịch vụ phân biệt và đảm bảo chất lượng dịch vụ định tuyến
1.4.2 MPLS và đảm bảo chất lượng dịch vụ định tuyến
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.
1.4.4 Đảm bảo chất lượng dịch vụ định tuyến với điều khiển tải
II.Thuật toán định tuyến
2.1 Lời giới thiệu
2.2 Ghi chú
2.3 Số đo:
2.4 Các vấn đề về định tuyến:
2.4.1 Các vấn đề định tuyến số đo đơn
2.4.2 các vấn đề định tuyến với một số số đo
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:
2.6.1 Các thuật toán lựa chọn đường dẫn cơ bản :
2.6.2 Tóm tắt những thuật toán với ràng buộc băng thông:
2.7 Ràng buộc trễ đầu cuối
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
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 hay í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 đ...
Download miễn phí Thuật toán đường đi ngắn nhất và rộng nhất SWP
MỤC LỤC
I. Đảm bảo chất lượng dịch vụ định tuyến
1.1. Giới thiệu:
1.2 Kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở
1.3 Các mục tiêu của đảm bảo chất lượng dịch vụ định tuyến
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ụ.
1.4.1 Dịch vụ phân biệt và đảm bảo chất lượng dịch vụ định tuyến
1.4.2 MPLS và đảm bảo chất lượng dịch vụ định tuyến
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.
1.4.4 Đảm bảo chất lượng dịch vụ định tuyến với điều khiển tải
II.Thuật toán định tuyến
2.1 Lời giới thiệu
2.2 Ghi chú
2.3 Số đo:
2.4 Các vấn đề về định tuyến:
2.4.1 Các vấn đề định tuyến số đo đơn
2.4.2 các vấn đề định tuyến với một số số đo
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:
2.6.1 Các thuật toán lựa chọn đường dẫn cơ bản :
2.6.2 Tóm tắt những thuật toán với ràng buộc băng thông:
2.7 Ràng buộc trễ đầu cuối
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
I. Đảm bảo chất lượng dịch vụ định tuyến1.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 hay í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 đ...