Download miễn phí Đề tài Định tuyến và gán bước sóng trong mạng quang WDM
Công nghệ truyền dẫn WDM đó đi vào giai đoạn ứng dụng và thương mại hoá theo xu hướng ngày càng hoàn thiện của công nghệ. Trong lĩnh vực thông tin quang, vấn đề quan trọng là lợi dụng được mạng quang hiện có và tương lai sẽ xây dựng để tạo thành mạng WDM tốc độ cao, dung lượng lớn đa dịch vụ. Trong khi thực hiện mạng vấn đề then chốt quyết định hiệu suất sử dụng tài nguyên mạng là quy hoạch hợp lý tài nguyên bước sóng và nó liên quan trực tiếp tới vấn đề định tuyến và gán bước sóng trong mạng.
Vấn đề tìm các tuyến và gán bước sóng cho luồng quang được gọi là bài toán định tuyến và gán bước sóng (RWA- Routing and Wavelength Assignment). Các yêu cầu kết nối có hai dạng: dạng tĩnh và dạng động.
Kỹ thuật WDM trong các mạng quang đó được phát triển nhanh chóng, nó đó đáp ứng các yêu cầu về băng tần của người sử dụng mạng. Trong mạng định tuyến các nút truy nhập thông tin với nhau qua các kênh toàn quang, các kênh này được xem như các luồng quang.
Để 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:
bộ chuyển đổi bước sóng và số lượng luồng nhánh trên mỗi cạnh từ nguồn đến đích cần sử dụng bộ chuyển đổi bước sóng.Giải pháp tổng thể
Chuyển đồ thị nhằm mục đích định tuyến.
Xác định đường đi ngắn nhất.
Chuyển đồ thị nhằm mục đích gán bước sóng.
Thực hiện giải pháp gán bước sóng.
Sau đây là một số bước thực hiện cụ thể:
Thực hiện định tuyến nguồn đến đích
Chuyển mạng gốc thành đồ thị bổ trợ, bằng cách dùng hai nút giả ngẫu nhiên S và D kết nối trực tiếp với hai nút nguồn đích trong mạng gốc với chi phí kết nối là 0. Sau đó thực hiện chuyển đổi tuyến trong mạng gốc thành đỉnh và cạnh trong đồ thị bổ trợ. S và D đóng vai trũ như các nút trung gian, không tham gia quá trình chuyển đổi này.
Hình 2.2 (a) Đồ thị mạng gốc trong giải pháp WCA
Hình 2.2 (b) Đồ thị bổ trợ trong giải pháp WCA
Trong mạng WDM, đường quang động có thể khụng thiết lập qua một nút (node) có gán bước sóng đầu vào đầu ra cho phép, khi tại đầu đó không có bộ chuyển đổi bước sóng phù hợp với các bước sóng vào ra còn có thể sử dụng. Do đó khi thiết lập hàm tính toán tham số tải trọng của cạnh trên đồ thị bổ trợ, cần dựa vào tham số trạng thái của đường tuyến như số bước sóng đầu vào đầu ra cho phép, số lượng cũng như giải chuyển đổi cũng như dải chuyển đổi của các bộ chuyển đổi bước sóng tại nút.
Tải trọng của một cạnh trên đồ thị bổ trợ được xác định bằng xác suất của các luồng nhánh cho phép đi qua cạnh đó.
Giải thuật tỡm đường Dijkstra được áp dụng để tỡm đường đi ngắn nhất trong đồ thị bổ trợ (tải trọng của luồng nhánh là thấp nhất), tương ứng với đường đi từ nguồn đến đích trong mạng gốc. Trong đồ thị bổ trợ này, không quan tâm đến các kênh trên một tuyến giữa hai nút, mà chỉ quan tâm đến tải trọng của chúng.
Gán bước sóng
Các đường đi tối ưu được áp đặt trong biểu đồ bổ trợ để tạo ra đồ thị bổ trợ của bước sóng tiếp theo trong giải pháp tổng thể. Tại thời điểm này chỉ quan tâm đến các luồng nhánh tối ưu tìm được theo giải pháp trên và xét đồ thị bổ trợ trờn tập các luồng nhánh này.
Các thuật toán được áp dụng
- Thuật toán FFWF(First Fit Wavelength First) _ thuật toán gán bước sóng theo thứ tự bước sóng.
Node nguồn sẽ thực hiện và gán bước sóng chưa dùng đầu tiên nó tìm thấy trên đường đi tối ưu từ nguồn tới đích xác định theo giải thuật định tuyến. Khi việc gán bước sóng thực hiện trên một tuyến, yêu cầu kết nối sẽ được gửi tới một node kế cận, và quá trình tiếp tục. Tại node thuật toán luồng ưu tiên sử dụng bộ chuyển đổi bước sóng nếu cho phép. Bản tin từ chối yêu cầu trả về trong hai trường hợp, hay không thể gán được trên toàn bộ tuyến, hay cho phép một bước sóng trên đường quang động được xác định.
- Thuật toán LEC (Least Converter First ) – chuyển đổi bước sóng
Giải thuật LEC được coi vấn đề gán bước sóng như vấn đề định tuyến và giải thuật Dijkstra để tìm giải pháp. Lý do đưa ra là số bộ chuyển đổi bước sóng tại node có thể rất nhỏ số bước sóng cho phép sử dụng tại node đó, nú có thể đưa tham số này vào để xem xét trong vấn đề gán bước sóng. Một biểu đồ bổ trợ cũng được lập ra tương tự, nhưng trong giải thuật này, chỉ quan tâm đường đi tối ưu tìm được trong giải thuật định truyến. Tải trọng LEC xác định theo cách tương tự, tức là một kênh có tải trọng hữu hạn nếu nó chưa sử dụng, và nó có tải trọng là vô hạn nếu nó đang sử dụng. Tải trọng của một cạnh chuyển đổi bằng g và lớn hơn tổng của bất kỳ đường nào chưa dùng mà có bộ chuyển đổi bước sóng tại node đạt bằng 0. LEC sẽ thiết lập một đường quang cho một yêu cầu kết nối với tối thiểu hóa các bộ chuyển đổi được sử dụng. Nếu không có đương quang nào được thiêt lập yêu cầu kết nối bị từ chối.
- Thuật toán LCC (Least Converter Cost First)
LCC tương tự như LEC nhưng hàm tải trọng xây dựng không tuyến tính. Nó đặt ra giả thiết rằng việc sử dụng các bộ chuyển đổi bước sóng tại các node có hiệu suất sử dụng chuyển đổi bước sóng cao sẽ phải trả với chi phí cao.
2.2 Topo vật lý
Đặc điểm của topo vật lý đóng vai trũ chủ yếu là hoạt động kết nối sợi ở thiết bị đầu cuối là hiệu suất chủ yếu của mạng. Chúng ảnh hưởng nhiều đến chất lượng tín hiệu quang, hiệu suất quang, lưu lượng đưa vào lớn nhất và khả năng tồn tại của mạng.
Biểu đồ đường kính D đưa ra khoảng cách giữa hai node mạng (bước nhảy quang). Bởi vỡ đường dẫn quang càng dài thỡ chất lượng tín hiệu càng xấu, mạng sẽ nghẽn. Như vậy topo tốt có thể thực hiện với độ dày đặc, trong hướng này sẽ cú bậc cao (số của node), và đường kính nhỏ. Giới hạn lớn nhất của biểu đồ Moore đưa ra NMoore (∆, D) độ ∆ lớn của một biểu đồ và đường kính D.
NMoore(∆,D) = 1+∆ (∆-1)i = , ∆ >2 (2.1)
Biểu đồ này đạt được giới hạn đó nhận biết qua biểu đồ Moore. Cú một số vụ hạn của đường kớnh 1 của biểu đồ Moore. Ngoài ra biểu đồ Moore của độ 2 và tồn tại của mọi đường kính . Tuy nhiên biểu đồ Moore đường kính nhỏ đạt tới điểm rất hiếm tăng thêm.Với D=2 chỉ có 1 biểu đồ Moore của độ 3. Biểu đồ Moore của đường kính 2 và 3 không thể tồn tại một vài độ khác được loại trừ ra một cách hợp lý ∆ =57
Hình 2.3 Biểu đồ 38 đỉnh
Mục đích của topo vật lý là phác họa biểu diễn ước lượng nú là bản tin xóa bỏ tuỳ ý với công việc về topo này với độ đối xứng cao.
2.3 Định tuyến và gán bước sóng tĩnh
Trong phần này mô tả bài toán thiết lập luồng quang tĩnh SLE. Trong bài toán SLE, các yêu cầu luồng quang được biết trước và việc định tuyến và gán bước sóng thực hiện ngoại tuyến (off-line). Đối tượng của hàm mục tiêu là tối thiểu số bước sóng cần thiết để thiết lập một tập các bước sóng nào đó cho một cấu hình vật lý đưa ra. Bài toán thay thế bài toán tối thiểu số bước sóng trong mạng là bài toán với mục tiêu là cực đại số các kết nối có thể được thiết lập (tối thiểu tắc nghẽn) cho một số các bước sóng và các yêu cầu kết nối đưa ra.
Với bài toán SLE với điều kiện ràng buộc bước sóng liên tục có thể được áp dụng như quy hoạch tuyến tính nguyên (ILP– Integer Linear Program) trong đó hàm mục tiêu là tối thiểu lưu lượng trên mỗi liên kết, lần lượt nó tương ứng với tối thiểu số các luồng quang qua từng liên kết riêng biệt. Bây giờ xây dựng bài toán SLE.
Đặt lsdw biểu diễn lưu lượng (số các yêu cầu kết nối) từ nguồn s đến đích d trên bất kỳ bước sóng w nào. Ta giả sử rằng hai hay nhiều hơn các luồng quang có thể được thiết lập giữa cặp cùng nguồn- đích nếu cần, nhưng mỗi chúng phải dùng một bước sóng riêng biệt; do đó lsdw £ 1.
Đặt biểu diễn lưu lượng (số các yêu cầu kết nối) từ nguồn s đến đích d trờn liên kết ij và bước súng w. khi một bước sóng trên một liên kết có thể được gán chỉ cho một tuyến.
Dựa vào cấu hình mạng vật lý, một tập các luồng quang và ma ...