Tiểu luận Tổng quan về mạng quang

cấp các dịch vụ theo phương thức không có liên kết, cung cấp các chương trình ứng dụng thâm nhập trực tiếp đến các dịch vụ lưu chuyển các gói datagram trên mạng. Tầng ứng dụng (Application): Tầng ứng dụng bao gồm tất cả các tiến trình dùng các giao thức của tầng vận chuyển để truyền dữ liệu. Các dịch vụ ở trong lớp này đa số được đề cập đén trong các dịch vụ ứng dụng trực tiếp trên Internet như: Email, FTP, WWW… Hình 2.4: Mô hình TCP/IP 2.3.3 Công nghệ kết hợp mạng số IP và mạng quang WDM Ngày nay lưu lượng thông tin truyền qua Internet tăng rất nhanh, đã thúc đẩy mặt bằng truyền dẫn phải phát triển theo hướng có băng thông ngày càng cao. Điều này đặt ra các vấn đề cần giải quyết như: xây dựng mạng băng thông rộng như thế nào? Chọn công nghệ gì để xây dựng mạng băng rộng đó? Có thể xem xét vấn đề này từ góc độ kết cấu thứ tự các lớp mạng [4]. Do TCP/IP đã trở thành tiêu chuẩn thực sự, hiện nay phần lớn đều dùng IP, như vậy vấn đề thảo luận tập trung vào lớp mạng, lớp đường kết nối số và lớp vật lý. Hiện nay, người ta có cách nhìn tương đối giống nhau với lớp vật lý là dùng sợi quang làm phương tiện vật lý. Vì sợi quang có chất lượng cao, băng thông rộng lớn và giá thành hạ, đã ngày càng trở thành vật liệu xây dựng mạng, nhất là mạng đường trục. Vì vậy nó được chọn làm phương tiện truyền dẫn hàng đầu. Trên lớp mạng, dùng giao thức IP đã trở thành xu hướng chung. Hiện nay cho dù là số liệu truyền thống hay tín hiệu âm thoại và thị tần đều có thể được quy vào gói số liệu IP, sau đó truyền dẫn số liệu bằng khuôn dạng IP. Hiện nay có mấy phương pháp chủ yếu sau: một là giữa IP và hệ thống phân cấp kỹ thuật số đồng bộ (SDH) dùng công nghệ ATM, tức công nghệ IP qua ATM. Hai là loại bỏ công nghệ ATM, cũng tức là công nghệ gói dữ liệu qua SDH (Packet over SDH). IP qua WDM tức là truyền dẫn trực tiếp gói số liệu IP trên kênh quang, hiện nay đây là công nghệ mới nhất. Dùng công nghệ IP qua WDM có thể giảm sự trùng lặp chức năng giữa các lớp mạng, giảm bộ phận trung gian thừa giữa các lớp SDH/SONET, ATM, và lớp IP, giảm thao tác thiết bị, giảm phí bảo dưỡng và quản lý. Đồng thời do tiết kiệm được lớp ATM trung gian và thiết bị SDH/SONET cho nên gói số liệu trực tiếp vận hành trên sợi quang có hiệu suất truyền dẫn cao nhất, chi phí ngoài thấp nhất, đồng thời đơn giản hoá việc quản lý mạng, có thể phối hợp với đặc tính lưu lượng không đối xứng của IP, tận dụng băng tần, giảm giá thành khai thác. Từ đó giảm một cách gián tiếp chi phí cho thuê bao để có được dịch vụ thông tin đa phương tiện. Ngoài ra, trong IP qua WDM, mỗi kênh tín hiệu không còn là kênh tín hiệu SDH ghép kênh thời gian, mà là kênh tín hiệu độc chiếm ghép kênh bước sóng, tốc độ trên 1 Gbit/s, nâng cao thêm một bước tốc độ truyền dẫn của mạng. Loại mạng IP băng rộng này có thể có đầu dây FR và ATM, lúc này vận hành FR và ATM trên mạng IP, tức FR qua IP hay ATM qua IP. 2.3.4 Mô hình phân lớp của mạng quang Internet Hình 2.5 là mô hình phân lớp của mạng quang Internet, công nghệ IP qua WDM [7]. Hình 2.5: Mô hình phân lớp IP qua WDM Trong đó lớp phối hợp có thể diễn tả như ở Hình 2.6 Hình 2.6: Mô hình lớp phối hợp Có nhiều phương pháp đóng gói để truyền dữ liệu giữa lớp IP và lớp WDM được đưa ra. Cách tiếp cận cơ bản là phân tích liên tiếp, bắt đầu từ IP qua ATM qua SDH qua WDM cho đến IP qua Gbe qua WDM, và bây giờ là IP qua 10GbE qua WDM. IP qua ATM qua SDH qua WDM: Trong phương pháp này, các gói IP được chia thành những gói ATM và được phân phối cho các kết nối ảo bởi thẻ dòng SDH/ATM trong bộ định tuyến IP. Sau đó các khối ATM được đóng gói thành khung SDH mà nó có thể được gửi đến bộ chuyển mạch ATM hoặc gửi trực tiếp đến hệ thống nhận phát tín hiệu WDM. IP qua ATM qua WDM: Trong phương pháp này, các gói ATM được vận chuyển trực tiếp đến một kênh WDM. Phương pháp này cũng giống như phương pháp trên nhưng các khối ATM không được đóng gói thành khung SDH. Thay vào đó chúng được gửi trực tiếp đến bộ trung chuyển vật lý bằng cách sử dụng một lớp vật lý khối cơ sở ATM. Lớp vật lý khối cơ sở là một công nghệ khá mới cho truyền tải ATM mà nó được phát triển một cách cụ thể cho giao thức ATM. Công nghệ này không thể hỗ trợ cho bất kỳ giao thức nào khác cạnh tranh với giao thức ATM. IP qua SDH; Gói tin qua SONET: Ta có thể sử dụng khung định dạng SDH để làm vỏ cho gói IP để truyền qua WDM bằng cách sử dụng một hệ thống tiếp sóng (bộ điều khiển bước sóng). Ta cũng có thể truyền IP dưới dạng khung SDH qua mạng truyền tải SDH cùng với một lưu lượng khác mà sau đó có thể sử dụng các liên kết WDM. IP qua SDL qua WDM: Liên kết dữ liệu đơn giản (SDL) là một phương thức đóng khung được Lucent Technologies, Inc. đưa ra và có thể thay thế đóng khung điều khiển dữ liệu ở tầng cao (HDLC) cho việc tạo vỏ cho gói trong giao thức PPP. So với khung HDLC, khung SDL không phân chia dãy cờ. Thay vào đó, khung SDL được bắt đầu với trường độ dài gói. Điều đó có lợi cho các bit tốc độ cao, ở đó sự đồng bộ của dãy cờ là khó khăn. Định dạng SDL có thể được chèn vào một gói SDH để truyền qua WDM. Định dạng SDL cũng có thể được mã hóa trực tiếp thành sóng mang quang. IP qua GbE qua WDM: Chuẩn GbE mới có thể được sử dụng để mở rộng dung lượng cao của mạng LAN thành mạng MAN và thậm chí có thể thành mạng WAN, sử dụng các thẻ đường dây gigabit trên các bộ định tuyến IP, mà nó có thể rẻ hơn thẻ đường dây SDH 5 lần với cùng dung lượng. Vì lý do đó, GbE có thể được ưa chuộng trong việc truyền tải IP qua mạng WDM dạng vòng trong đô thị. Hơn nữa, cổng 10-Gbps Ethernet thích hợp để được chuẩn hóa trong tương lai không xa. Mặc dù có nhiều phương pháp truyền các gói dữ liệu giữa lớp IP và lớp WDM nhưng xu hướng phát triển cuối cùng của sự giao tiếp giữa lớp IP và lớp WDM là gói IP được vận chuyển trực tiếp đến lớp quang mà không qua lớp trung gian nào. 2.4 Thiết kế mạng WDM 2.4.1 Sự phân cấp của mạng quang WDM Nếu trong mạng quang WDM ứng dụng bộ biến đổi bước sóng, thì kết cấu của mạng quang WDM có thể phân cấp cũng có thể không phân cấp. Nếu không dùng bộ biến đổi bước sóng thì kết cấu mạng quang WDM là không phân cấp [3]. Kết cấu của mạng quang phạm vi rộng thường có 3 cấp: Cấp 0: là mạng LAN sợi quang. Mạng LAN cấp 0 thường có đường kính mạng nhỏ, độ trễ truyền dẫn nhỏ, độ lưu loát phải cao. Do đó thường sử dụng topo hình sao. Các trạm trong mạng có thể dùng bước sóng đơn nhất hoặc dùng nhiều bước sóng, giữa các trạm dùng giao thức điều khiển phương tiện để giải quyết vấn đề dùng tài nguyên. Cấp 1: là mạng MAN sợi quang, có cự ly từ vài chục đến vài trăm km. Mạng là sự liên kết nhiều mạng con cấp 0 với nhau. Trong mạng ở cấp này, yêu cầu tốc độ tương đối cao, phần nhiều dùng topo hình vòng. Cấp 2: là mạng WAN hoặc mạng đường trục trong phạm vi toàn quốc, cự ly thường là vài trăm đến vài nghìn km. Mạng ở cấp này có đường kính mạng lớn, độ trẽ truyền dẫn lớn và thường dùng topo hình lưới. Trong đó các cấp mạng khác nhau có các nhóm bước sóng khác nhau, mạng cùng cấp nhưng không giao nhau có thể dùng cùng một nhóm bước sóng. 2.4.2 Mạng cục bộ WDM (WDM LAN Network) Một mạng cục bộ WDM điển hình bao gồm một số các điểm nút được nối với nhau bằng các sợi quang hai chiều qua các bộ trung chuyển mạng vật lý hoặc được nối trực tiếp với nhau [5]. Bộ trung chuyển mạng: Thiết bị kết nối đơn giản nhất và phổ biến nhất của mạng cục bộ WDM là bộ phối ghép hình sao không nguồn, cung cấp cho bộ trung chuyển quảng bá (Hình 2.7). Khả năng quảng bá của bộ phối ghép hình sao kết hợp với nhiều kênh WDM cho phép một băng thông rộng của các giao thức truy cập môi trường truyền thông có thể có. Ngoài ra, vì bộ phối ghép hình sao là một thiết bị không nguồn nên nó thực sự công bằng đối với các nút mạng. Điểm hạn chế của bộ trung chuyển mạng không nguồn là các nút mạng có thể yêu cầu thêm điều khiển xử lý và có thể yêu cầu thêm phần cứng trong trong sắp xếp định tuyến và lập biểu truyền thông. Khả năng quảng bá của bộ phối ghép hình sao cũng ngăn cản việc dùng lại các bước sóng để tạo nhiều kết nối đồng thời. Nút mạng: Một điều quan trọng khác cần nói đến trong thiết kế một mạng quang WDM là kết cấu tại mỗi điểm nút. Mỗi điểm nút trong mạng bao gồm một trạm công tác kết nối với bộ trung chuyển mạng qua sợi quang và nút có thể truy cập đến bất kỳ kênh bước sóng khả dụng nào trên mỗi sợi quang. Trong thiết kế giao diện mạng cho mỗi nút, cần phải lựa chọn số lượng máy thu và máy phát, cũng như phải chọn loại máy thu và máy phát (cố định điều khiển hay có thể điều khiển được) để đặt tại mỗi điểm nút. Những quyết định đó thường phụ thuộc giao thức, mức độ truy cập, yêu cầu kết nối trong mạng và giá cả. Một giao thức mạng quang WDM có thể là giao thức đơn bước nhảy (nghĩa là hai nút trực tiếp giao tiếp với nhau mà không cần qua một nút trung gian nào) hoặc là giao thức đa bước nhảy (nghĩa là thông tin từ điểm nút nguồn đến điểm nút đích có thể được định tuyến qua một số điểm nút trung gian trong mạng). Thông thường, các mạng đa bước nhảy yêu cầu chỉnh sóng ít hơn các mạng đơn bước nhảy. Tối thiểu, mỗi điểm nút phải được trang bị ít nhất một máy phát và một máy thu. Khi cả máy phát và máy thu đều được cố định điều khiển cho một vài kênh bước sóng, và có nhiều hơn một kênh, sau đó một kiến trúc đa bước nhảy tĩnh phải được thiết lập qua bộ phối ghép không nguồn hình sao. Kiến trúc được tạo ra bằng cách thiết lập các kết nối giữa các cặp điểm nút trên các bước sóng đã được đưa ra. Một cách tiếp cận linh hoạt hơn là sử dụng một máy phát và/hoặc một máy thu điều hướng được. Tính điều hướng được cho phép mạng trở thành cấu hình động dựa trên các kiểu lưu lượng, và nó cũng cho phép thực thi giao thức đa bước nhảy. Việc thêm vào các máy phát và máy thu tại mỗi điểm nút có thể giúp cho việc tăng thêm khả năng kết nối của mạng và cũng có thể được sử dụng để giúp cho việc truyền theo tọa độ. Trong vài trường hợp, mạng có thể có một kênh điều khiển mà nó có thể được sử dụng cho xác định tọa độ tiền vận chuyển (xác định tọa độ tiền vận chuyển cho phép một điểm nút thông báo trước sự vận chuyển của nó mà điểm nút nhận có thể sẵn sàng tiếp nhận). Mỗi điểm nút có thể được trang bị thêm một máy phát và máy thu cố định có tần số cố định do kênh điều khiển điều chỉnh sóng. Hình 2.7: Mạng quang WDM cục bộ quảng bá và lựa chọn với bộ trung chuyển mạng là bộ phối ghép không nguồn hình sao Sóng gốc của các máy phát và máy thu điều hướng được có thể là nhân tố quan trọng trong việc chọn các thành phần tùy thuộc vào loại mạng đang thực thi. Một mạng đơn bước nhảy thường yêu cầu các thành phần điều hướng được để tạo các kết nối theo đòi hỏi và yêu cầu được sắp xếp để có được máy phát của điểm nút nguồn và máy thu của điểm nút đích trên cùng một kênh cho khoảng thời gian một chuyển giao thông tin. Trong trường hợp này, thời gian điều hướng của máy phát và máy thu có thể có một tác động hữu ích đến sự thực thi của mạng. Mặc khác, phần lớn mạng đa bước nhảy yêu cầu khả năng điều hướng chỉ cho các cấu hình hiếm khi xảy ra của mạng dựa trên việc thay đổi các mẫu lưu lượng. Theo cách đó, thời gian điều hướng của các thành phần trong mạng đa bước nhảy là không giới hạn như trong trường hợp của mạng đơn bước nhảy. Theo thời gian thì thuật ngữ đa bước nhảy sẽ trở nên chính xác vì các thiết bị điều hướng nhanh, điều này khó đạt được trong quá khứ. 2.4.3 Vấn đề mạng diện rộng WDM (WDM WAN Network) Các mạng diện rộng hiện tại được thiết kế như các mạng điện tử với các liên kết sợi quang [6]. Tuy nhiên, những mạng đó có thể không có đầy đủ ưu điểm của Dải thông được cung cấp bởi sợi cáp quang vì các thành phần chuyển mạch điện tử có thể không đủ khả năng để chuyển mạch một lượng lớn dữ liệu có thể được truyền đi trên các liên kết sợi quang. Điều đó dự báo trước thế hệ mạng quang tiếp theo sẽ sử dụng các bộ định tuyến và các yếu tố chuyển mạch quang để cho phép các kênh quang toàn quang được thiết lập từ một điểm nút nguồn đến một điểm nút đích. Hơn nữa, kỹ thuật WDM sẽ cho phép nhiều kênh quang chia sẻ một liên kết sợi quang. Thuật ngữ kênh quang WDM tương tự như một xa lộ nhiều làn đường mà nó được sử dụng để vượt qua các điểm dừng tại các con đường trong thành phố. Một thuật ngữ khác trong thiết kế mạng WAN là sử dụng lại bước sóng. Vì mỗi bước sóng có thể được sử dụng trên mỗi liên kết trong mạng nên các kênh quang không dùng chung bất kỳ liên kết nào có thể sử dụng cùng một bước sóng. Vấn đề thiết lập và định tuyến kênh quang qua các sợi quang và các bộ chuyển mạch vật lý trong mạng WAN WDM là một vấn đề tối ưu, trong đó toàn bộ việc thực thi mạng phải được cân đối với sự tiêu thụ các tài nguyên mạng. Trong việc thiết kế một mạng quang, điều quan trọng là nhận ra cái gì có thể và cái gì không thể được thiết lập bằng các thiết bị chuyển mạch. Các thiết bị nối chéo quang hiện thời có thể có khả năng chuyển mạch thông tin quang dựa trên các cổng vào hoặc các bước sóng, nhưng trong phạm vi một luồng dữ liệu quang chúng không thể hiệu quả như dữ liệu ghép kênh chia thời gian (TDM), nghĩa là gói dữ liệu thời gian cơ sở. Hơn nữa, trong bộ chuyển mạch quang được cấu hình lại, thời gian yêu cầu cấu hình lại bộ chuyển mạch thường lâu hơn khi so sánh với tốc độ đi qua bộ chuyển mạch. Vì vậy, các bộ chuyển mạch quang dường như thích hợp cho việc chuyển mạch luồng dữ liệu lớn hoặc thích hợp cho việc thiết lập các tuyến đường tĩnh ở mức độ nào đó trong mạng dựa trên các bước sóng hơn là cho việc chuyển mạch các gói đơn lẻ. Chương 3 ĐỊNH TUYẾN VÀ PHÂN PHỐI BƯỚC SÓNG 3.1 Bài toán phân phối và định tuyến bước sóng (Routing and Wavelength Assignment Problem). Topo vật lý của một mạng định tuyến bước sóng gồm các điểm nút, bộ định tuyến bước sóng và sợi quang kết nối chúng lại với nhau. Kênh quang được thiết lập giữa các nút đầu cuối đi qua topo vật lý này và tạo nên một topo logic. Mỗi kênh quang được phân phối cho một đường đi qua mạng và một bước sóng trên đường đi đó. Việc tìm ra đường đi qua mạng cho các kênh quang và phân phối bước sóng cho các kênh quang đó gọi là định tuyến và phân phối bước sóng (RWA). Trong khuôn khổ bài viết, việc xác định bài toán định tuyến và phân phối bước sóng là trong mô hình mạng quang WDM định tuyến bước sóng. Hầu hết sự chú ý là tập trung vào hoạt động của mạng là dưới ràng buộc tính liên tục bước sóng, các kênh quang được thiết lập đối với các yêu cầu kết nối giữa các cặp điểm, và một kênh quang đơn phải duy trì cùng một bước sóng trên tất cả các kết nối sợi quang mà nó đi qua và các kênh quang trên cùng một kết nối phải được sử dụng các bước sóng khác nhau. Để thiết lập một kênh quang, một tuyến đường phải được chọn và một bước sóng phải được phân phối cho kênh quang đó. Nếu không có bước sóng sẵn có cho kênh quang với tuyến đường được chọn, thì yêu cầu kết nối sẽ bị huỷ bỏ. [2] 3.2 Các kiểu bài toán RWA. Bài toán RWA có thể được chia thành 2 loại: RWA tĩnh (SLE) và RWA động (DLE). Nói chung RWA động là yêu cầu xem xét xây dựng kết nối quang đến là ngẫu nhiên, tức là khi có một yêu cầu kết nối; với RWA tĩnh là trước khi xét đến việc định tuyến và phân phối bước sóng thì đã biết sự kết nối quang muốn xây dựng [3]. 3.2.1 Định tuyến và phân phối bước sóng tĩnh (SLE) Trong RWA tĩnh, tất cả yêu cầu kênh quang giữa các cặp nút đầu cuối là được biết trước. Điều đó có nghĩa là, một yêu cầu đối với việc thiết lập một tập các kênh quang là được xác định đầu tiên. Các đường dẫn quang không bị giải phóng dù chúng chỉ được thiết lập một lần. Tiêu chuẩn xác định tốt nhất bài toán RWA là làm tối ưu số bước sóng (số bước sóng ít nhất) đối với một tôpô mạng, số sợi quang và tập các yêu cầu đường đi quang cho trước. Trong mạng này, số kênh quang giữa các cặp nút là cố định theo thời gian, nó chỉ thay đổi khi việc phân phối kênh quang diễn ra một cách chậm chạp làm thay đổi nhu cầu lưu lượng trung bình theo thời gian. Bài toán SLE có thể được chia thành hai bài toán con: Bài toán định tuyến: Được đưa về dạng bài toán chương trình tuyến tính nguyên (ILP) và giải bằng phương pháp xấp xỉ. Bài toán phân phối bước sóng (WA): Thuộc dạng bài toán tô màu đồ thị. Có hai giải thuật heuristics được sử dụng trong bài toán tô màu đồ thị là: Largest-First (LF) và Smallest-Last (SL). Cả hai bài toán trên đều thuộc dạng bài toán NP-hoàn chỉnh, có nghĩa là không tồn tại giải pháp với độ phức tạp đa thức. Để giải quyết lớp bài toán này, cần sử dụng những thuật toán gần tối ưu, như heuristic, … Hàm mục tiêu: Phân phối bước sóng cho các kênh quang sao cho số bước sóng được sử dụng là nhỏ nhất. 3.2.1.1. Bài toán chương trinh tuyến tính nguyên (ILP) Vấn đề đặt ra trong bài toán RWA tĩnh là chọn tuyến và phân phối bước sóng cho một nhóm cần xây dựng kênh quang với giả thiết là đã biết topo kết nối vật lý của mạng. Do hiện nay số lượng bước sóng có thể sử dụng thực tế là có hạn, do đó thông qua thiết kế tối ưu kết cấu lớp kênh quang, để giảm tối đa số lượng bước sóng là một đề tài nghiên cứu rất có ý nghĩa. Các nghiên cứu về vấn đề này thường sử dụng dạng bài toán ILP hoặc dựa vào phương pháp tiếp cận heuristic với yêu cầu cố gắng giảm tối đa số bước sóng được yêu cầu để thiết lập lớp kênh quang. Bài toán ILP là dạng NP đầy đủ và chỉ có thể được giải quyết trên các hệ thống nhỏ. Đối với các hệ thống lớn, phương pháp heuristic phải được sử dụng. Trong SLE, các yêu cầu kênh quang được xác định trước, và các thao tác định tuyến và phân phối bước sóng được thực hiện một cách độc lập. Mục tiêu điển hình là giảm tối đa số bước sóng cần thiết để thiết lập một tập các kênh quang nào đó với kết cấu tôpô vật lý cho trước. Một lựa chọn khác so với việc giảm tối đa số bước sóng trong mạng, bài toán đối ngẫu (daul) là làm cực đại hoá số kết nối (connection) có thể được thiết lập (cực tiểu hóa xác suất nghẽn) đối với số bước sóng và tập các yêu cầu kết nối cho trước. SLE với ràng buộc tính liên tục (thống nhất) của bước sóng, có thể được đưa về dạng bài toán chương trình tuyến tính nguyên (ILP) với hàm mục tiêu là cực tiểu hóa các luồng trên mỗi kết nối, tương ứng, cực tiểu hóa số kênh quang qua một liên kết cụ thể. Đặt lsdw biểu thị lưu lượng (số các yêu cầu kết nối) từ điểm nguồn s đến điểm đích d bất kỳ trên một bước sóng w. Ta giả thiết rằng có hai hay nhiều hơn các kênh quang có thể được thiết lập giữa cặp nguồn-đích, nhưng mỗi kênh phải duy trì một bước sóng khác nhau; vì thế, lsdw £ 1. Đặtbiểu thị lưu lượng (số yêu cầu kết nối) từ nguồn s đến đích d trên kết nối ij với bước sóng w. £ 1 do bước sóng trên một kết nối có thể được phân phối chỉ đến một kênh. Cho biết topo kết nối vật lý mạng, một tập các bước sóng, và ma trận lưu lượng l, trong đó lsd biểu thị số kết nối cần thiết giữa s và d, thì bài toán có thể được đưa về dạng sau: Minimize: Fmax (1) sao cho: trường hợp khác nếu nếuu đối với mỗi liên kết (i,j) trong E (2) (3) (4) (5) (6) Đây cũng là phương pháp được sử dụng để tìm được số bước sóng nhỏ nhất được yêu cầu đối với tập các yêu cầu kết nối cho trước bằng cách thực hiện tìm kiếm trên giá trị nhỏ nhất của số bước sóng trong mạng. Đối với số bước sóng cho trước, áp dụng bài toán ILP để thấy kết quả nếu một lời giải được tìm thấy. Ngược lại, nếu không tìm thấy lời giải, thì sẽ thử lại với một giá trị số bước sóng lớn hơn. Thủ tục này sẽ được lặp lại cho đến khi tìm thấy được giá trị số bước sóng nhỏ nhất. Phân tích ở trên chỉ rõ, trong trường hợp dịch vụ tĩnh, vấn đề mạng định tuyến và phân phối bước sóng lấy tối ưu bước sóng làm mục tiêu có thể quy thành vấn đề quy hoạch tuyến tính số học của luồng. Đây là một bài toán NP đầy đủ. Khi quy mô mạng tương đối nhỏ, thì có thể trực tiếp sử dụng thuật toán quy hoạch tuyến tính để tìm lời giải cho số bước sóng nhỏ nhất mà mạng cần. Theo nhu cầu mở rộng quy mô mạng, thời gian tính toán sẽ tăng theo số mũ, cho nên với mạng lớn tính toán tối ưu số bước sóng của mạng phải sử dụng một thuật toán gợi ý (heuristici). 3.2.1.2 Bài toán phân phối bước sóng tĩnh (Static Wavelength-Assignment) Việc phân phối các bước sóng đến các kênh quang khác nhau với yêu cầu làm tối ưu số bước sóng cần sử dụng dưới ràng buộc tính liên tục của bước sóng (wavelength-continuity) tương đương với bài toán tô màu (graph-coloring) trên đồ thị kênh, vì số lượng bước sóng cần thiết bằng số đỉnh sắc trong đồ thị kênh. Với giả thiết đã cho phương án định tuyến, như vậy có thể xác định đồ thị kênh của mạng như sau: - Xây dựng đồ thị kênh G(V,E) sao cho mỗi kênh quang trong hệ thống là một đỉnh điểm của đồ thị G. Các cạnh vô hướng giữa các đỉnh trong đồ thị G tương ứng các kênh quang giao nhau thuộc kết nối sợi quang vật lý. - Màu của các đỉnh trong đồ thị được xác định sao cho không có 2 đỉnh gần kề có màu giống nhau. 3.2.1.3 Thuật toán Heuristic Thuật toán heuristic được đua ra để phân phối kênh quang trong mạng định tuyến bước sóng. Mỗi cặp điểm nút được gán cho một kênh quang đơn qua mạng và thuật toán cố gắng cực tiểu số lượng yêu cầu kênh bước sóng trong các sợi quang để định tuyến lưu lượng này qua kiến trúc vật lý đã định trước. Trong thuật toán này, đầu tiên, những tuyến đường truyền dẫn ngắn nhất được xác định giữa cặp điểm nút và các tuyến đường này được gán cho các yêu cầu kênh quang. Bằng cách này, tổng lưu lượng vận chuyển và lưu lượng vẩn chuyển trung bình qua các tuyến đường bước sóng là nhỏ nhất. Vì thường tồn tại nhiều hơn một một đường truyền ngắn nhất giữa mỗi cặp điểm nút nên có thể cân bằng số lượng đường truyền trên tất cả các liên kết bằng cách chọn tuyến đường hợp lý từ các khả năng. Vì vậy, sự thay thế các đường truyền ngắn nhất luân phiên được tiến hành cho các kênh quang nếu số lượng kênh quang, liên kết được nạp nhiều nhất trong đường truyền luân phiên thấp hớn đường truyền trước đó. Khi không có sự thay thế nào có thể, định tuyến kênh quang được hoàn tất, và phân phối bước sóng cho các tuyến đường đó diễn ra. Phân phối bước sóng được tiến hành chẳng hạn theo cách các bước sóng được gán cho vài chỉ mục và kênh quang kênh quang với đường tuyền dài hơn được gán cho bước sóng chỉ mục nhỏ nhất khả dụng qua tuyến đường của nó trước các kênh quang khác. Nguyên nhân của cách giải quyết đường truyền dài hơn này là việc tìm ra một bước sóng tựdo cho nhiều liên kết là khó hơn. Một thuật toán heuristic khác là thuật toán định tuyến heuristic và phân phối bước sóng (HRWA), thuật toán này cực tiểu số lượng bước sóng được yêu cầu. Thuật toán bắt đầu với việc tìm đường truyền ngắn nhất cho mỗi cặp nút nguồn- đích và chọn tuyến đường ngắn nhất mà nó cực tiểu yêu cầu bước sóng. Sau đó, số lượng bước sóng được yêu cầu được giảm xuống bởi việc định tuyến lại một số kênh quang. Bước tiếp theo là lặp lại cho đến khi sự cải tiến không xa hơn là có thể. Những kết quả mô phỏng cho thấy rằng HRWA thực hiện tốt từ quan điểm thời gian tính toán và sự cực đại bước sóng dùng lại đến các giải pháp ILP. [4] Đối với định tuyến VWP và WP, hai thuật toán heuristic tương tự được đề ra (mà chúng sử dụng việc định tuyến lại để cựu tiểu một hàm mục tiêu). Trong những thuật toán này, mỗi liên kết bao gồm nhiều sợi quang và thuật toán cố gắn cực tiểu đường truyền quang qua kết nối co giãn hệ thống (nghĩa là tổng số lượng đầu sợi quang được yêu cầu trong mỗi điểm nút). Điều đó có nghĩa là mục tiêu là sự cực tiểu số lượng các sợi quang trung bình được quản lý tại các bộ định tuyến bước sóng. Trong một số mạng đó là được yêu cầu cho việc thấy rõ sự hoạt động (hoặc hiệu quả chi phí) của các bộ định tuyến bước sóng. Trong lược đồ VWP, kênh quang cài đặt ban đầu mà chúng được phân phối đều trong phạm vi mạng (nghĩa là mọi liên kết nên bằng số kênh quang). Sau đó, các liên kết sử dụng bước sóng không có hiệu quả nhất (nghĩa là có giá trị của số lượng kênh quang sử dụng liên kết mod số lượng bước sóng trong mỗi sợi quang lớn) được xác định. Tiếp đó, các kênh quang mà chúng sử dụng số cực đại các liên kết được định tuyến lại. Sự định tuyến lại này được thực hiện vài lần và kết thúc thuật toán. Ngay khi các tuyến đường được xác định, các yêu cầu sợi quang cho mỗi liên kết có thể được xác định bằng số kênh quang chia cho số bước sóng. Thuật toán định tuyến WP bắt đầu với thuật toán định VWP để xác định các tuyến đường cho các kênh quang. Sau đó, tất cả các kênh quang được chia cho số lớp nhỏ nhất chẳng hạn như bất kỳ hai kênh quang nào trong một số lớp một cách ngẫu nhiên và bước sóng được phân phối theo số lớp (nghĩa là bước sóng được phân phối = số lớp mod số bước sóng). Cuối cùng, tất cả các bước trên cho tập các tuyến đường ban đầu khác được thực hiện lặp lại vài lần và việc phân phối với giá trị hàm mục tiêu thấp nhất được lựa chọn như việc định tuyến kênh quang. Những mô phỏng cho thấy rằng lược đồ định tuyến WP chịu sự co giãn hệ thống nối chéo đường truyền quang lớn hơn lược đồ định tuyến VWP. Hơn nữa, sự khác biệt giữa lược đồ định tuyến WP và định tuyến VWP tăng lên như số bước sóng tăng lên. Đó là vì trong lược đồ WP, rất nhiều bước sóng còn lại không được xác định trên các liên kết chẳng hạn như số các bước sóng được ghép lại trong sự tăng lên sợi quang đơn. 3.2.2 Định tuyến và phân phối bước sóng động (DLE) Trong RWA động, các yêu cầu kênh quang giữa các điểm nút được đưa đến một cách ngẫu nhiên. Điều đó có nghĩa là yêu cầu kênh quang được thiết lập theo yêu cầu. Do đó vấn đề lấy tối ưu tài nguyên (như bước sóng) làm mục tiêu không phản ánh được yêu cầu thực tế, căn cứ vào đặc điểm dịch vụ động, phải chọn chỉ tiêu tính năng phục vụ làm mục tiêu tối ưu của vấn đề RWA động [2]. Hàm mục tiêu: Khi xây dựng kết nối (thiết lập kênh quang và phân phối các bước sóng), chọn phương án có tổn hao nhỏ nhất (khả năng huỷ bỏ yêu cầu nhỏ nhất), cũng có nghĩa là trong điều kiện tài nguyên mạng có hạn (số bước sóng xác định trước), có thể hỗ trợ xây dựng kết nối kênh quang đến mức tối đa (tức là số kết nối được thiết lập là lớn nhất), hoặc có thể giảm tối đa chi phí thiết lập mạng. Bài toán RWA dù thuộc dạng bài toán tĩnh hay động thì đều có thể giải quyết bằng cách chia nhỏ thành hai bài toán con để giải quyết một cách tách biệt: bài toán định tuyến (Routing) và bài toán phân phối bước sóng (Wavelength Assignment). Bài toán con định tuyến: Giải bài toán định tuyến là xác định một đường đi qua mạng từ điểm nút nguồn đến điểm nút đích cho mỗi kênh quang. Đối với bài toán RWA tĩnh, đường đi đó là thông thường là đường đi ngắn nhất. Với bài toán RWA động, ngoài việc xác định đường đi ngắn nhất, thì vấn đề trách tắc nghẽn hay làm giảm tối ưu xác xuất tắc nghẽn cũng phải được đặt lên hàng đầu. Bài toán con phân phối bước sóng: Bài toán phân phối bước sóng thực hiện việc phân phối bước sóng cho mỗi kênh quang sao cho hai kênh quang cùng đi qua một sợi quang trong mạng thì có bước sóng khác nhau và số bước sóng sử dụng là ít nhất. Các giải thuật heuristic với phân phối bước sóng: Random Assignment, First-Fit, Least-Used, Most-Used, Min-Product, Least-Loaded, Max-Sum, Relative Capacity Loss. 3.3 Các phương pháp tiếp cận để giải quyết bài toán RWA. Bài toán RWA bao gồm nhiều phần khác nhau, thường được giải quyết một cách tách biệt để làm đơn giản hóa bài toán. Về khía cạnh định tuyến (routing), có 3 phương pháp định tuyến cơ bản: fixed routing, fixed-alternate routing, và adaptive routing [2]. Fixed routing: Trong định tuyến được bố trí trước, chỉ có một lộ trình đi được cố định giữa mỗi cặp nguồn và đích. Khi có một yêu cầu kết nối, mạng sẽ cố gắng thiết lập một kênh quang theo lộ trình đã được đưa ra. Nếu không có bước sóng sẵn có trên mỗi liên kết trong lộ trình đó, thì kết nối sẽ bị huỷ bỏ. Fixed- alternate routing: Trong định tuyến fixed-alternate, mỗi node duy trì một bảng định tuyến chứa một danh sách có thứ tự của các đường đi đã được cố định đến mỗi node đích. Ví dụ, các tuyến đường có thể được sắp xếp dựa trên độ dài (path length), như bao gồm: first-shortest-path, second-shortest-path, third-shortest-path,… Lộ trình đi thực sự đối với một yêu cầu kết nối chỉ có thể được chọn từ tập các đường đi cố định đó và kênh quang tương ứng sẽ được thiết lập. Adaptive routing: Trong định tuyến adaptive, lộ trình đường đi được dựa trên bước sóng sẵn có hiện thời trên mỗi kết nối. Bất kỳ một lộ trình khả thi nào từ node nguồn đến node đích đều có thể thích hợp như là lộ trình thực tế đối với yêu cầu kết nối. Việc chọn một lộ trình phụ thuộc vào chính sách của mạng được sử dụng, như chọn đường đi có chí phí nhỏ nhất hay đường đi mà khả năng tắc nghẽn là ít nhất. Bài toán WA là một phần khác của bài toán RWA. Nói chung thì nó dễ giải quyết hơn vấn đề định tuyến, nhưng nó cũng phụ thuộc vào kết quả thực tế của cách giải quyết định tuyến. Tuy nhiên, nó thường có tác động trở lại đến các kết quả thực hiện của các giải thuật RWA khi nó được tính toán trọn vẹn. Chương 4 MINH HỌA BÀI TOÁN ĐỊNH TUYẾN VÀ PHÂN PHỐI BƯỚC SÓNG TĨNH Chương này minh họa bài toán RWA thông qua việc đưa ra một bài toán cụ thể và sử dụng một thuật toán đơn giản để giải bài toán trong trường hợp định tuyến và phân phối bước sóng tĩnh có ràng buộc tính liên tục của bước sóng. 4.1 Mô tả bài toán Cho mạng G = (V,E) như hình 4.1. Trong đó tập đỉnh V là tập các nút mạng, tập cạnh E là tập các kết nối giữa các nút mạng. I là tập các yêu cầu kết nối. V = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10} E = {(1,2), (1,5), (1,6), (2,3), (3,4), (4,8), (5,8), (6,7), (7,8), (7,10), (8,9)} I = {(1,7), (6,10), (5,7), (1,9), (3,7), (4,8), (9,7)} Hình 4.1: Các yêu cầu kết nối trong mạng quang WDM Bài toán đặt ra là tìm định tuyến tối ưu và số bước sóng nhỏ nhất dựa trên kíên trúc mạng và ma trận lưu lượng λ. Ma trận lưu lượng λ: 4.2 Lời giải bài toán minh họa 4.2.1 Lý thuyết cơ sở Bài toán tìm đường đi ngắn nhất: Cho đơn đồ thị liên thông, có trọng số G = (V, E). Tìm khoảng cách d(u0, v) từ u0 đến mọi đỉnh v của G và chỉ ra đường đi ngắn nhất từ u0 đến v. Ở đây ta sử dụng thuật toán Dijkstra do nhà toán học người Hà Lan E. Dijkstra đưa ra năm 1960. Phương pháp của thuật toán Dijkstra là: xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Trước tiên, ta có d(u0, u0) = 0. Trong các đỉnh v ¹ u0 kề với u0, tìm đỉnh có khoảng cách k1 đến u0 là nhỏ nhất. Giả sử đó là u1, ta có d(u0, u1) = k1 Trong các đỉnh v ¹ u0 và v ¹ u1 kề với u0 hoặc u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ nhất. Giả sử đó là u2. Ta có: d(u0, u2) = k2 Tiếp tục như vậy cho đến khi tìm được khoảng cách từ u0 đến mọi đỉnh của G. Giả sử có p đỉnh, ta có : 0 = d(u0, u0) < d(u0, u1) < d(u0, u2) < ... < d(u0, un) Thuật toán Dijkstra i := 0 S := V \ {u0} L(u0) := 0, L(v) := + ∞ , "v Î S Nếu p = 1 thì xuất d(u0, u0) và kết thúc Với mọi đỉnh v Î S kề với ui L(v) := min(L(v), L(ui) + m(ui, v)) Trong đó m(ui,v) là trọng số của đường đi từ ui đến v. Xác định k = min L(v) v Î S Nếu L(vj) = k thì xuất d(u0,uj) ui+1 := vj S := S \ {ui+1} i := i+1 Nếu i = p – 1 thì kết thúc. Nếu không thì quay lại bước 2. Bài toán tô màu đồ thị: Định nghĩa: Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh). Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. Một đồ thị có thể là phẳng ngay cả khi nó thường được vẽ với những cạnh cắt nhau, vì có thể vẽ nó bằng cách khác không có các cạnh cắt nhau. Tô màu bản đồ Mỗi bản đồ có thể coi là một đồ thị phẳng. Trong một bản đồ, ta coi hai miền có chung nhau một đường biên là hai miền kề nhau (hai miền chỉ có chung nhau một điểm biên không được coi là kề nhau). Một bản đồ thường được tô màu, sao cho hai miền kề nhau được tô hai màu khác nhau. Ta gọi một cách tô màu bản đồ như vậy là một cách tô màu đúng. Để đảm bảo chắc chắn hai miền kề nhau không bao giờ có màu trùng nhau, chúng ta tô mỗi miền bằng một màu khác nhau. Tuy nhiên việc làm đó nói chung là không hợp lý. Nếu bản đồ có nhiều miền thì sẽ rất khó phân biệt những màu gần giống nhau. Do vậy người ta chỉ dùng một số màu cần thiết để tô bản đồ. Một bài toán được đặt ra là: xác định số màu tối thiểu cần có để tô màu đúng một bản đồ. Tô màu đồ thị Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh; các cạnh nối hai đỉnh, nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Rõ ràng mọi bản đồ trên mặt phẳng đều có đồ thị đối ngẫu phẳng. Bài toán tô màu các miền của bản đồ là tương đương với bài toán tô màu các đỉnh của đồ thị đối ngẫu sao cho không có hai đỉnh liền kề nhau có cùng một màu, mà ta gọi là tô màu đúng các đỉnh của đồ thị. Số màu ít nhất cần dùng để tô màu đúng đồ thị G được gọi là sắc số của đồ thị G và ký hiệu là χ(G). Ví dụ: Hình 4.2: Đồ thị miền (a,b) Ta thấy rằng 4 đỉnh b, d, g, e đôi một kề nhau nên phải được tô bằng 4 màu khác nhau. Do đó χ(G) ≥ 4. Ngoài ra, có thể dùng 4 màu đánh số 1, 2, 3, 4 để tô màu G như hình 2.4b. Như vậy χ(G) = 4. 4.2.2 Thuật toán Greedy RWA Phần này giới thiệu một thuật toán đơn giản để đạt được một cấu hình của topo logic thích hợp trên topo vật lý của mạng dựa vào các yêu cầu kênh quang. Thuật toán 1 sử dụng phương pháp tìm đường đi ngắn nhất của Dijkstra để tìm ra đường đi ngắn nhất S từ điểm s đến điểm d [5]. Trong đó, hàm idx() được mô tả trong thuật toán được dùng để sắp xếp các đường đi theo một thứ tự nào đó. Chỉ tiêu chính để sắp xếp là số bước nhảy bổ sung, nghĩa là những đường đi sử dụng bổ sung các bước nhảy ở mức ưu tiên thấp hơn. Chỉ tiêu thứ hai là độ dài của đường đi, đường đi dài hơn được xếp trước đường đi ngắn hơn. Nếu hai đường đi có cùng hai chỉ tiêu trên thì thứ tự được xác định bởi điểm nút khác đầu tiên trên các đường đi: đường đi nào có số điểm nút nhỏ hơn được xếp trước. Tiêu chuẩn cuối cùng chỉ cần thiết để đảm bảo một trật tự rõ ràng. Thuật toán 1: S đường đi ngắn nhất Đặt L = f(si, di) là một danh sách các căp nút có yêu cầu thiết lập kênh quang. Tìm đường đi ngắn nhất cho mỗi cặp (si, di) Î L, và lưu bộ 3 (si, di, pi) vào danh sách X, trong đó pi là đường đi tương ứng. Đặt len(pi) là độ dài của đường đi pi (số bước nhảy) Đặt sp(pi) = sp(si,di) là độ dài của đường đi ngắn nhất có thể từ si đến di Đặt idx(pi) = (N + 1)[len(pi) – sp(pi)] – len(pi) + pi(j)(N + 1)-j Trong đó pi(j) là số nút của nút thứ j trong đường đi pi Sắp xếp danh sách X = {(si,di,pi)} tăng dần theo idx(pi) Return X Thuật toán 2: Greedy RWA Sử dụng thuật toán 1 để tìm đường đi ngắn nhất cho mỗi yêu cầu kênh quang. Xây dựng đồ thị phân phối bước sóng G. Trong đó mỗi đỉnh tương ứng với một kênh quang và hai kênh quang sử dụng chung một kết nối tương ứng với hai đỉnh kề nhau trong. Sử dụng thuật toán tô màu đồ thị để tô màu các điểm nút của G. Return: các đường đi và các bước sóng được chọn Thuật toán 2 giải bài toán RWA theo hai phần. Đầu tiên nó sử dụng thuật toán đường đi ngắn nhất đã được mô tả ở trên để thu được một tuyến đường cho mỗi yêu cầu kênh quang và sau đó phân phối kênh bước sóng cho chúng bằng cách sử dụng thuật toán tô màu đồ thị. 4.2.3 Kết quả đạt được Kết quả lý thuyết: Áp dụng thuật toán, từ tập các yêu cầu kênh quang I và mà trận lưu lượng l ta thu được đáp án cuối cùng bao gồm ma trận định tuyến F (hình 4.3) và tập các bước sóng được chọn. Từ kết quả đó ta tiến hành phân phối bước sóng cho các kênh quang sao cho không có hai kênh quang sử dụng một bước sóng trên cùng một liên kết sợi quang. Để phân phối bước sóng, ta tiến hành xây xựng đồ thị G = (V, E) như sau: Mỗi kênh quang tương ứng với một đỉnh trong đồ thị. Hai kênh quang sử dụng chung một liên kết sợi quang tương ứng với hai đỉnh kề nhau trong đồ thị G. Hình 4.3: Ma trận định tuyến Tiến hành tô màu đồ thị sao cho hai đỉnh kề nhau thì có màu khác nhau. Trong đồ thị topo mạng ở trên, ta có 7 kênh quang là (1,6,7), (6,7,10), (1,5,8,9), (3,4,8,7), (5,8,7), (4,8) và (9,8,7). Ta sẽ xây dựng 7 đỉnh trong đồ thị theo các kênh quang đó. Kênh quang (1,6,7) và (6,7,10) sử dụng chung một đường kết nối quang vật lý (6,7), vì vậy, có một cạnh nối giữa 2 đỉnh (1,6,7) và (6,7,10). Tương tự với các kênh quang còn lại và tiến hành tô màu cho đồ thị ta được kết quả như hình hình 4.4. Số màu nhỏ nhất cần thiết chính là số bước sóng cần sử dụng tương ứng trong bài toán phân phối bước sóng. Do đó, các màu khác nhau đại diện cho các bước sóng khác nhau, màu được sử dụng để tô màu cho một đỉnh tương ứng với bước sóng được phân phối cho một kênh quang. Hình 4.4: Đồ thị kênh quang Như vậy, ta có thể thu được kết quả là đồ thị cuối cùng như sau: Hình 4.5: Kết quả định tuyến và phân phối bước sóng Kết quả từ chương trình cài đặt: Khởi tạo chương trình được một form như hình 4.6: Hình 4.6: Khởi tạo chương trình Trong đó hai hộp lựa chọn Source node và Destination node chứa các nút mạng. Hộp lựa chọn ở phía dưới chứa các chức năng của chương trình: thêm nút (add nodes), xóa nút (remove nodes), di chuyển nút (move nodes), kết nối nút (connect nodes). Chức năng của các nút: Assign: Tiến hành định tuyến và phân phối bước sóng. Reset: Xóa mạng. Set: Thiết lập yêu cầu kênh quang. Reset Lightpath: Xóa các yêu cầu kênh quang đã thiết lập. Thiết lập mạng theo yêu cầu của bài toán đã được nêu ra bằng cách sử dụng chức năng add nodes để tạo các nút mạng và sủ dụng chức năng connect nodes để liên kết các nút mạng. Sau khi thiết lập ta được mạng như hình 4.7. Hình 4.7: Mạng sau khi được thiết lập Sau khi thực hiện chương trình cho kết quả như hình 4.7. Hình 4.7: Kết quả từ chương trình. Nhận xét: Từ kết quả chương trình ta thấy: Các tuyến đường định ra đúng theo ma trận định tuyến F đã được nêu ở trên. Số bước sóng sử dụng là 3 Chương 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 5.1 Kết luận Mạng quang giữ vị trí là phương tiện trung gian vận chuyển quan trọng nhất và làm bùng nổ sự phát triển mạng truyền thông trong vài năm tới. Những đặc tính truyền dẫn quang (dải thông lớn, ít lỗi, độ suy hao thấp), và các chức năng hoạt động mạng vận chuyển được cung cấp bởi SONET/SDH được phân phát chủ yếu cho các tiến bộ trong dung lượng, sự tin cậy, hiện quả. Sự ra đời của kỹ thuật WDM cũng đóng vai trò quan trọng trong việc đáp ứng nhu cầu dải thông ngày càng lớn trong những năm vừa qua. Kỹ thuật WDM thường là một giải pháp mang lại nhiều lợi nhuận để khai thác dung lượng hơn là các sự lựa chọn khác, chẳng hạn như cài đặt nhiều sợi quang song song hoặc thay thế hệ thống TDM hiện thời bằng các hệ thống cao tốc. Vì vậy các kết nối WDM điểm - điểm trở thành phổ biến trong những năm gần đây. Kỹ thuật WDM giới thiệu bước đầu tiên hướng về hoạt động mạng toàn quang. Nếu yêu cầu lưu lượng tiếp tục tăng lên, và sự triển khai WDM được tiếp tục thì các kênh quang sẽ tăng lên nhanh chóng trở thành phương tiện vận chuyển cơ bản. Trong tương lai không xa, ngày càng nhiều kênh bước sóng sẽ được ghép kênh trong một sợi quang đơn và tốc độ kênh sẽ tăng lên bằng tốc độ điện tử. Vì thế, các công tắc điện tử tại các đầu sợi quang được đòi hỏi để làm tăng sự phức tạp và giá trị. Điều đó thúc đẩy sự thay thế các công tắc điện tử bằng các công tắc quang. Trong các mạng tương lai, chuyển mạch sẽ được thực hiện tại lớp quang bằng cách sử dụng các thiết bị định tuyến bước sóng, và mạng sẽ được cung cấp từ điểm đến điểm các đường ống quang dung lượng lớn giữa các người sử dụng mạng. Điều đó tạo khả năng cho mạng vận chuyển quang dựa trên định tuyến bước sóng. Điều đó có nghĩa là trong các mạng thế hệ tiếp theo, các chức năng vận chuyển mạng mà chúng hiện đang được điều khiển bởi các lớp cao sẽ được điều khiển bởi lớp quang. Vì vậy, mạng vận chuyển quang dựa trên định tuyến bước sóng giới thiệu bước tiếp theo trong sự ước lượng của mạng vận chuyển. Mặt khác, vì giá thành cao nên mạng LAN và MAN toàn quang dựa trên mạng quảng bá và lựa chọn khó cạnh tranh được với các kỹ thuật khác như ATM, GbE,… Trong tương lai gần, chỉ một vài ứng dụng thực sự cần dung lượng lớn sẽ thích hợp với mạng quảng bá và lựa chọn. Tuy nhiên, vì các ứng dụng mới và/hoặc các dịch vụ mà chung yêu cầu dải thông rất lớn nổi bật lên, mạng toàn quang trong các mạng LAN và MAN sẽ một sự lựa chọn quang trọng. Trong khuôn khổ thực hiện đề tài, do thời gian có hạn chúng tôi nghiên cứu một cách tổng quan các vấn đề về mạng quang WDM như IP qua mạng WDM, các kiểu chuyển mạch, định tuyến và phân phối bước sóng… Trong chương 4, chúng tôi đưa ra một ví dụ minh họa cho bài toán RWA tĩnh và một thuật toán đơn giản để giải quyết bài toán. Mục tiêu của trọng tâm của lời giải tìm ra đường đi ngắn nhất cho mọi kênh quang qua mạng và cực tiểu hóa số bước sóng cần sử dụng trong mạng. 5.2 Hướng phát triển Trong quá trình nghiên cứu thực hiện đề tài, chúng tôi chỉ dừng lại ở mức độ nghiên cứu tổng quan về mạng quang WDM, chưa đi sâu vào các vấn đề cụ thể và còn nhiều vấn đề chưa giải quyết được. Đồng thời chúng tối cũng đã phát hiện một số vấn đề có thể phát triển thêm. Vì chúng tôi đưa ra một số vấn đề có thể thực hiện được trong tương lai: Tiếp tục nghiên cứu bài toán RWA tĩnh với các trường hợp và các ràng buộc khác nhau, như bài toán RWA có chuyển đổi bước sóng. Nghiên cứu tìm cách giải quyết bài toán RWA động. Tiếp tục nghiên cứu sâu hơn vào các vấn đề của mạng quang WDM như công nghệ IP qua mạng WDM, chuyển mạch kênh quang, chuyển mạch gói quang… PHỤ LỤC Ngôn ngữ lập trình java: Giới thiệu: Java là một ngôn ngữ lập trình đơn giản, hướng đối tượng, phân tán, thông dịch lẫn biên dịch, mạnh mẽ, bảo mật, cấu trúc độc lập, khả chuyển, hiệu quả cao và linh động. Ngôn ngữ lập trình java ra đời vào cuối năm 1990 với tên ban đầu là Oak, do James Gosling. Sau đó, vì có sự trùng tên nên Oak được đổi tên va java ra đời. Java nhanh chóng được đón nhận như một công cụ mạnh mẽ cho việc phát triển các ứng dụng Internet. Các trình duyệt Web lần lượt đưa ra sự hỗ trợ cho Java, mở đầu là Netscape Communications với Netscape Navigator Web 2.0 rồi Micrisoft với Internet Explorer 3.0. Ngôn ngữ lập trình java: Khai báo biến: Biến được dùng để chứa dữ liệu. Mỗi biến gắn liền với một kiểu dữ liệu. Khai báo: ; Ví dụ: int x; //Khai báo biền x là kiểu sồ nguyền boolean kt; //Khai báo biến kt là kiểu logic Kiểu dữ liệu: Java có hai loại kiểu dữ liệu: Kiểu dữ liệu cơ sở: Kiểu dữ liệu cơ sở là các khối dữ liệu đã được xác định trong ngôn ngữ, chúng không thể chia cắt hoặc định nghĩa từ các kiểu khác. Các kiểu dữ liệu cơ sở của Java: Kiểu số nguyên: byte (8 bits), short (16 bits), int (32 bits), long (64 bits) Kiểu dấu chấm động: float, double Kiểu ký tự: char Kiểu logic: boolean Kiểu dữ liệu tham chiếu: Kiểu dữ liệu tham chiếu là các kiểu dữ liệu đối tượng. Các kiểu dữ liệu này truy xuất thông qua địa chỉ tham chiếu của biến. Ví dụ: Date today; //Khai báo kiểu đối tượng ngày Object obj; //Khai bóa kiểu đối tượng tổng quát Mảng: Một mảng có thẻ được khai báo theo hai cách: Cách 1: [ ] Cách 2: [ ] Ví dụ: Khai báo một mảng số nguyên: int[] intarray; int intarray[]; Sau khi khai báo, ta phải cấp vùng nhớ cho mảng để có thể sử dụng mảng bằng cách dùng từ khóa new Ví dụ: int intarray[] = new int [100]; //Khai báo và cấp phát float floatarray[]; //Khai báo floatarray = new float [10]; //Cấp phát Cấu trúc điều khiển: Cấu trúc lựa chọn: Cấu trúc if…: if () ; Nếu thì sẽ được thực hiện, còn nếu sai thì sẽ bị bỏ qua. Cấu trúc if… else…: if () ; else ; Nếu thì sẽ được thực hiện, còn nếu sai thì sẽ được thực hiện. Cấu trúc switch: switch { case : ; break; case : ; break; … case : ; break; default: ; Nếu có giá trị bằng thì được thực hiện (1≤ i ≤ n). Nếu không thõa tất cả các giá trị đã liệt kê thì được thực hiện. Vòng lặp: Vòng lặp for: For (; ; ) ; Bắt đầu với giá trị khởi tạo của biến đếm, được thực hiện. Sau đó biến đếm thay đổi giá trị một lượng bằng bước nhảy. Nếu biến đếm thõa thì tiếp tục thực hiện . Còn không thõa thì kết thúc vòng lặp. Vòng lặp while while ; hoặc do{ } whlie ; được thực hiện lặp lại cho đến khi có giá trị false. Đối với cấu trúc while… thì được kiểm tra trước mỗi lần thực hiện . Còn đối với cấu trúc do…while thì được kiểm tra sau mỗi lần thực hiện . Lớp và đối tượng: Lớp là khuôn mẫu tạo đối tưọng. Lớp bao gồm các dữ liệu của đối tượng (các trường và thuộc tính) và các phương thức tác động lên các dữ liệu đó. Lớp có tính kế thừa. Một lớp con có thể kế thừa tất cả các trường và phương thức của lớp cha. Khai báo lớp: class { ; ; } Ví dụ: public class myClass{ public int field1; private float field2; protected int field3[ ]; public myClass(){ //Hàm khởi tạo field1 = 0; field2 = 0; field3 = new int [10]; } } Từ khóa: public: các trường và các phương thức public có thể được truy cập từ tất cả các đối tượng. private: các đối tượng khác không thể truy cập đến các trường và các phương thức private. protected: các trường và các phương thức protected của một lớp chỉ có thể được truy cập bởi chính nó và các lớp con kế thừa nó. Đối tượng là thể hiện của lớp. Để tạo một đối tượng của lớp ta dùng từ khóa new. Ví dụ: myObject = new myClass(); Khi đó ta có đối tượng myObject là thể hiện của lớp myClass. Biên dịch và chạy một chương trình java: Để có thể biên dịch và chạy chương trình Java, ta cần phải cài đặt hệ Java JDK 1.4.1. Ví dụ biên dịch một file java có tên HelloWorld.java ở trong thư mục c:\j2sdk1.4.0: C:\j2sdk1.4.0>javac HelloWorld.java Khi đó trình biên dịch sẽ dịch mã nguồn thành file .class. Để chạy file này ta làm như sau: C:\j2sdk1.4.0>java HelloWorld Cài đặt thuật toán Greedy RWA: Phần này giới thiệu chương trình minh họa thuật toán Greedy RWA: GreedyRWA.java: Mã nguồn thuật toán GreedyRWA: /* * GreedyRWA.java * Thuat toan GreedyRWA. */ import java.awt.*; import java.lang.Math; import java.util.Vector; /*****************************************************/ class GreedyRWA { static boolean DEBUG = false; BinaryMatrix cm; Vector routes; int colors; public GreedyRWA( BinaryMatrix lm ) { cm = lm; routes = null; colors = -1; } public int getNumberOfColors( ) { return colors; } public Vector getConfiguration( ) { return routes; } public boolean runRWA( BinaryMatrix rlp) { Vector allroutes = new Vector(); BinaryMatrix lm; int i,j; int best; for( i=0; i<rlp.np; i++) for(j=0; j<rlp.np; j++) { if(rlp.m[i][j]) { Routes ijroutes = new Routes( cm, i, j ); if ( ijroutes.status() == false ) { System.out.println( "Khong the ket noi do thi." ); return false; } allroutes.addElement( ijroutes ); } } int selection[] = new int[ allroutes.size() ]; int choices[] = new int[ allroutes.size() ]; boolean can_iterate = false; for ( i=0; i<allroutes.size(); i++ ) { selection[i] = 0; choices[i] = ((Routes)allroutes.elementAt(i)).routes.size(); if ( choices[i]>1 ) can_iterate = true; } lm = getWAMatrix( allroutes, selection ); NodeColoring col = new NodeColoring( lm ); best = col.num; if ( can_iterate ) { for ( int iter=0; iter<30; iter++ ) { int nr; int or; do i = (int)(allroutes.size() * Math.random()); while ( i>=allroutes.size() || choices[i]<2 ); do nr = (int)(choices[i] * Math.random()); while ( nr>=choices[i] || selection[i]==nr ); or = selection[i]; selection[i] = nr; lm = getWAMatrix( allroutes, selection ); col = new NodeColoring( lm ); if ( col.num > best ) selection[i] = or; else best = col.num; } } if ( DEBUG ) System.out.println( "Tot nhat:" + best + " mau." ); lm = getWAMatrix( allroutes, selection ); col = new NodeColoring( lm ); col.print(); Vector best_routes = new Vector(); for (i=0; i<allroutes.size(); i++ ) { Route r1 = ( (Routes)allroutes.elementAt(i) ).getRoute( selection[i] ); r1.color = col.color[i]; best_routes.addElement( r1 ); } colors = best; routes = best_routes; return true; } /****************************************************************/ boolean commonLink( Route a, Route b ) { for ( int i=0; i<a.d; i++ ) { for( int j=0; j<b.d; j++ ) { if ( a.node[i]==b.node[j] ) { if ( i>0 ) { if ( j>0 && a.node[i-1] == b.node[j-1] ) return true; if ( j+1<b.d && a.node[i-1] == b.node[j+1] ) return true; } if ( i+1<a.d ) { if ( j>0 && a.node[i+1] == b.node[j-1] ) return true; if ( j+1<b.d && a.node[i+1] == b.node[j+1] ) return true; } } } } return false; } BinaryMatrix getWAMatrix( Vector allroutes, int selection[] ) { int i,j; BinaryMatrix lm; Routes routes; Route r1,r2; lm = new BinaryMatrix( allroutes.size() ); for ( i=0; i<allroutes.size(); i++ ) { routes = (Routes)allroutes.elementAt(i); r1 = routes.getRoute( selection[i] ); for ( j=i+1; j<allroutes.size(); j++ ) { routes = (Routes)allroutes.elementAt(j); r2 = routes.getRoute( selection[j] ); if ( commonLink( r1, r2 ) ) { lm.m[i][j] = true; lm.m[j][i] = true; } } } return lm; } } Các file kèm theo: BinaryMatrix.java và BinaryMatrix.class: ColorConversion.java và ColorConversion.class: Config.class DrawControls.class DrawPanel.class Node.java và Node.class NodeColoring.java và NodeColoring.class Route.java và Route.class Routes.java và Routes.class WdmDemo.java, WdmDemo.class và WdmDemo.html TÀI LIỆU THAM KHẢO TÀI LIỆU TIẾNG VIỆT [1] Nguyễn Thúc Hải. Giáo trình mạng máy tính. [2] Đặng Thanh Chương, Bài toán RWA (Routing and wavelength assignment-định tuyến và tham chiếu giữa kết nối IP và bước sóng) trong optical DWDM network, Luận văn Cao học, năm 2004 [3] Học viện công nghệ bưu chính viễn thông. Mạng thông tin toàn quang. Nhà xuất bản Bưu điện, tháng 4- 2001 [4] Học viện công nghệ bưu chính viễn thông. Hệ thống ghép kênh theo bước sóng quang. Nhà xuất bản Bưu điện, tháng 5- 2001 TÀI LIỆU TIẾNG ANH [5] Biswanath Mulkherjee. Optical Communication Networks. Department of Computer Science University of California, Davis, June 1997 [6] Esa Hyytiä. Maximization of Single Hop Trafficwith Greedy Heuristics. Networking Laboratary, HUT, 20th December 2002 [7] Joan Serrat, Alex Galis. Deploying and Managing IP over WDM Networks. Artech House Boston – London, 2003 [8] Semih Bilgen, Altan Kocyigit. All - Optical Networking