Định tuyến và gán bước sóng trong mạng WDM

o và đầu ra, trường hợp nhiều cổng thì càng phức tạp hơn nhưng cũng tương tự. Khả năng chuyển đổi bước sóng hoàn toàn tức là có thể chuyển đổi một bước sóng ở ngõ vào thành một bước sóng bất kì ở ngõ ra. Khả năng chuyển đổi bước sóng giới hạn qui định rằng mỗi bước sóng đầu vào có thể được chuyển đổi thành một số bước sóng xác định trước ở ngõ ra. Trường hợp đặc biệt của chuyển bước sóng giới hạn là chuyển đổi bước sóng cố định khi mà một bước sóng đầu vào chỉ có thể chuyển đổi thành một bước sóng cố định ở đầu ra. Nếu mỗi bước sóng được “chuyển đổi ” thành chính nó thì chúng ta gọi không có sự chuyển đổi nào. Hình 2.16: Các khả năng chuyển đổi bước sóng 2.8. Kết luận chương. Qua chương này, ta đã thấy được động lực để thúc đẩy mạng WDM hiện nay. Những mạng này cung cấp các lightpath từ đầu cuối này đến đầu cuối kia qua các node mạng trung gian. Một lightpath gồm có một kênh thông tin quang, hoặc bước sóng, giữa hai node mạng mà được định tuyến qua những node trung gian. Các node mạng trung gian có thể chuyển mạch và chuyển đổi bước sóng. Vì vậy các mạng này được xem là các mạng định tuyến bước sóng. CHƯƠNG 3 ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG. 3.1. Giới thiệu chương Trong mạng quang định tuyến bước sóng, người sử dụng liên lạc với nhau qua các kênh thông tin quang được gọi là các lightpath. Lightpath là một đường đi của tín hiệu ánh sáng từ nguồn đến đích dưới dạng quang thông qua các kết nối trung gian. Một lightpath có thể kéo dài qua nhiều tuyến truyền dẫn để cung cấp một kết nối chuyển mạch mạch giữa hai node mà có thể chứa một luồng lưu lượng lớn giữa chúng. Khi các lightpath thực hiện việc mang thông tin từ một node nguồn đến một node đích nào đó thì nó cần được định tuyến và gán bước sóng. Định tuyến và gán bước sóng cho lightpath là vấn đề hết sức quan trọng và xảy ra thường xuyên trong mạng. Chương này sẽ nói rõ về việc định tuyến và gán bước sóng cho các lightpath, các thuật toán thực hiện định tuyến và các phương pháp gán bước sóng trong mạng WDM. 3.2. Giới thiệu về định tuyến và gán bước sóng (Routing and Wavelength Assignment - RWA). Khi một lightpath được chọn và xác định, mỗi lightpath cần được định tuyến và gán bước sóng cho nó. Từ đó đặt ra bài toán định tuyến và gán bước sóng. Định tuyến là vấn đề tìm đường giữa hai node bất kì trong mạng để thoả mãn một mục đích nào đó, thuật ngữ gọi là để tối ưu hàm mục tiêu (cost function). Vấn đề này rất quen thuộc và rất quan trọng trong mạng. Thông thường định tuyến trong IP sử dụng thuật toán tìm đường Dijkstra, với hàm mục tiêu là các metric quen thuộc như băng thông, độ trễ, chi phí tuyến, … Trong mạng quang, tìm đường được hiểu theo hai khía cạnh, đó là tìm đường vật lí mang được mẫu lưu lượng yêu cầu (Routing) và đưa ra bước sóng phù hợp để mang lưu lượng trên mỗi link dọc path (Wavelength Assignment) trong số các bước sóng cho phép (bởi mỗi path gồm một số fiber, mà trên mỗi fiber này, bạn có thể có W sub-chanels, cũng là W bưóc sóng và W lựa chọn cho yêu cầu kết nối hiện tại). Vấn đề này được viết tắt là RWA. Khi tìm được một path vật lí và đánh dấu bước sóng trên các link dọc theo path đó, thì chúng ta có một đường quang, còn gọi là lightpath (LP). Rắc rối đặt ra đối với bài toán RWA là nó đưa ra hai điều kiện sau: Điều kiện tính liên tục bước sóng: một lightpath phải sử dụng chung một bước sóng trên tất cả các link dọc theo đường đi của nó từ nguồn đến đích. Điều kiện này được minh hoạ như hình dưới bằng cách mỗi lightpath được thể hiện bằng một màu nhất định trong suốt đường đi. Hình 3.1: Điều kiện tính liên tục bước sóng Điều kiện tính riêng biệt về bước sóng: tất cả các lightpath sử dụng cùng một link (fiber) phải được gán các bước sóng riêng biệt. Điều kiện được minh hoạ như (hình 2.10) mà nó được thoả mãn khi hai lightpath cùng chia sẻ cùng một link được thể hiện bằng hai màu khác nhau (hai bước sóng khác nhau). Vấn đề xảy ra khi các bước sóng trên hai link kế cận khác nhau, lúc đó cần dùng đến bộ chuyển đổi bước sóng, là tài nguyên đắt đỏ của mạng. Các giải thuật luôn tìm cách giảm thiểu chi phí này. Bài toán RWA có thể đưa ra như sau: cho một số hữu hạn các lightpath được thiết lập trên mạng và một số giới hạn các bước sóng. Ta phải xác định đường đi cho mỗi lightpath và xác định số bước sóng nên được gán cho cho các lightpath này để đạt được số lightpath có thể thiết lập là lớn nhất. Mặc dù những lightpath có đường đi ngắn nhất có vẻ tối ưu hơn, nhưng đôi khi ta đành phải loại bỏ sự lựa chọn này để nhiều lightpath hơn có thể thiết lập. Vì thế các giải thuật thường cho phép nhiều đường đi thay phiên nhau đối với mỗi lightpath được thiết lập. Các đường đi ánh sáng (lightpath) mà không thể được thiết lập vì những ràng buộc về đường đi và bước sóng được gọi là nghẽn, do vậy vấn đề tối ưu mạng tương ứng hạn chế đến mức thấp nhất xác xuất tắc nghẽn này. Khi hai lightpath mà chúng có tuyến truyền dẫn trùng nhau thì chúng sẽ không được gán cùng một bước sóng. Thông thường một đường đi ánh sáng (lightpath) hoạt động với cùng một bước sóng trên những sợi quang mà nó đi qua. Trường hợp này ta nói rằng lightpath thoã mãn sự ràng buộc về tính liên tục bước sóng. Tuy nhiên nếu một nút chuyển mạch/định tuyến được trang bị với một bộ chuyển đổi bước sóng thì điều kiện ràng buộc về tính liên tục bước sóng không còn nữa, lightpath này có thể chuyển sang nhiều bước sóng khác nhau trên đường đi từ nguồn đến đích của nó. Mạng lõi được mô hình bằng Graph G(E,V) với E (edge) là tập các cạnh và V là tập các đỉnh (vertical). Với mỗi cặp node bất kì S-D trong mạng (và tương ứng trong Graph), tồn tại một tập các đường đi (path) vật lí có thể giữa chúng (mỗi path bao gồm một số fiber hay link, edge trung gian), kí hiệu: R. Tập các đường đi này có thể tìm theo một giải thuật tìm đường phổ biến như Dijkstra, Prim hay Mentor với một hàm mục tiêu tuỳ chọn. 3.3. Định tuyến bước sóng Trong một mạng không có bộ chuyển đổi bước sóng, các lightpath phải sử dụng cùng một bước sóng từ nguồn đến đích. Khi có nhu cầu cho cuộc gọi, bộ định tuyến bước sóng WR phải sử dụng giải thuật được thiết lập từ trước để chọn một cổng ra và bước sóng tương ứng. Sự lựa chọn bước sóng đóng vai trò quan trọng đối với toàn bộ xác suất tắc nghẽn. Vì vậy một WR phải tìm ra đường đi cho yêu cầu thiết lập lightpath và thực hiện gán bước sóng sao cho tối thiểu hoá xác suất tắc nghẽn. Chức năng này có tầm quan trọng trong việc thiết kế các mạng toàn quang. Bài toán RWA được chia làm hai loại như sau: RWA dành cho lưu lượng mạng cố định (static traffic): với loại này thì các yêu cầu về lightpath được biết trước, tất cả mọi đường đi và bước sóng gán cho các lightpath đã được thiết lập cố định từ trước ( ví dụ như yêu cầu truyền từ Router này đến Router là không đổi, tính theo đơn vị LP, xét trên toàn mạng ta có ma trận hằng N*N ). Khi có yêu cầu đi đến, một đường đi và bước sóng đã chỉ định từ trước đó được gán cho yêu cầu tương ứng đó. Vì vậy, qui trình định tuyến và gán bước sóng là cố định, không thay đổi theo thời gian. Với loại này, công việc thực hiện không phức tạp, nó đơn giản là gán một đường đi nào đó cho lightpath. Mục đích của phương pháp này là tăng cực đại toàn bộ dung lượng của mạng, tức là có thể thiết lập đồng thời số lightpath là lớn nhất. Đây là bài toán trong mạng không có sự chuyển đổi bước sóng. RWA dành cho lưu lượng mạng thay đổi (dynamic traffic): trong mạng quang định tuyến bước sóng, các yêu cầu về lightpath đi đến theo một qui trình riêng biệt và thời gian chiếm bởi các yêu cầu này cũng theo một qui luật riêng. Với dạng lưu lượng mạng thay đổi thì cần có một giải thuật động để định tuyến các lightpath qua những đường đi khác nhau dựa vào sự tắc nghẽn trên các tuyến truyền dẫn. Từ đó giải thuật cho bài toán RWA động được đưa ra, nó dựa vào trạng thái hiện thời của mạng để xác định đường đi cho mỗi yêu cầu thiết lập lightpath. Một kết nối bị nghẽn nếu không có đường đi nào có thể dùng để mang nó. Một trong những thách thức để giải quyết bài toán định tuyến và gán bước sóng với lưu lượng mạng thay đổi là phát triển các giải thuật và giao thức để thiết lập các lightpath, nhằm hạn chế đến mức thấp nhất xác suất tắc nghẽn trong mạng (tức là số yêu cầu kết nối sẽ bị từ chối/ tổng số yêu cầu), nâng cao hiệu suất sử dụng tài nguyên (cùng một lượng fiber, node, bộ chuyển đổi bước sóng,…có thể tạo ra nhiều lightpath nhất) và cải thiện hiệu năng tổng thể của mạng (hiệu năng = xác suất tắc nghẽn của mạng + độ phức tạp của giải thuật) . Một phương pháp đơn giản là dựa vào giải thuật tìm đường đi bị nghẽn ít nhất để thiết lập các lightpath động. Trong giải thuật này, một lightpath được thiết lập trên đường đi ít bị nghẽn nhất từ tập các lightpath khác nhau giữa cặp nguồn - đích. Bước sóng được cấp phát là bước sóng đầu tiên còn rỗi giữa những tuyến liên kết trong đường này. Bài toán RWA ( Routing and Wavelength Assignment) được chia làm hai phần: định tuyến và gán bước sóng. 3.4. Định tuyến (Routing) 3.4.1. Giới thiệu Định tuyến được coi là thành phần cốt yếu của kiến trúc mạng, thiết kế mạng và điều hành mạng của mọi mạng thông tin, là thành phần không thể thiếu trong mạng viễn thông. Các yếu tố thúc đẩy cho quá trình thay đổi và phát triển định tuyến mạng chủ yếu do nhu cầu cải thiện hiệu năng mạng, các dịch vụ mới đưa vào khai thác và sự thay đổi công nghệ mạng, và đây cũng là một trong những thách thức khi xây dựng và khai thác mạng. Hầu hết các mạng viễn thông truyền thống được xây dựng theo mô hình mạng phân cấp mô hình này cho phép sử dụng định tuyến tĩnh trên qui mô lớn. Trong khi định tuyến tĩnh vẫn còn tồn tại thì tính chất độc lập giữa người sử dụng và mạng vẫn ở mức cao; định tuyến tĩnh chủ yếu dựa trên mong muốn của người sử dụng nhiều hơn là tình trạng của mạng hiện thời. Mạng hiện đại hiện nay có xu hướng hội tụ các dịch vụ mạng, yêu cầu đặt ra từ phía người sử dụng là rất đa dạng và phức tạp. Các phương pháp định tuyến động được sử dụng nhằm nâng cao hiệu năng mạng của mạng mới này, tăng thêm tính chủ động, mềm dẻo đáp ứng tốt hơn yêu cầu người sử dụng dịch vụ. Định tuyến để chỉ sự lựa chọn đường đi trên một kết nối mạng để thực hiện việc gửi dữ liệu. Định tuyến chỉ ra hướng, sự dịch chuyển của các gói (dữ liệu) được đánh địa chỉ từ mạng nguồn đến đích thông qua các node trung gian; thiết bị chuyên dùng là bộ định tuyến (router). Tiến trình định tuyến thường chỉ hướng đi dựa vào bảng định tuyến, đó là bảng chứa các lộ trình tốt nhất đến các đích khác nhau trên mạng. Vì vậy việc xây dựng bảng đinh tuyến, được tổ chức trong bộ nhớ của router, trở nên vô cùng quan trọng cho việc định tuyến hiệu quả. Khi có nhu cầu cho cuộc gọi đến, bộ định tuyến xác định đường đi cho yêu cầu thiết lập lightpath. Như vậy bài toán định tuyến là xác định đường đi cho mỗi yêu cầu thiết lập lightpath. Mỗi đường đi là một chuỗi các tuyến truyền dẫn từ điểm nguồn đến điểm đích. Nhằm giảm sự phức tạp trong tính toán, đồng thời để bài toán đơn giản hơn, ta sẽ xét đường đi ngắn nhất giữa hai điểm đầu cuối này. Để thực hiện điều này, ta sử dụng một giải thuật tìm đường đi ngắn nhất dựa trên giải thuật Dijkstra. Để hiểu rõ về thuật toán dùng trong định tuyến, ta tìm hiểu về lí thuyết đồ thị. 3.4.2. Phân loại định tuyến Có nhiều cách phân loại định tuyến, có thể đưa ra một số loại định tuyến như sau: Dựa vào chức năng thích nghi với trạng thái hiện thời của mạng để phân loại thành: định tuyến tĩnh và định tuyến động Định tuyến tĩnh: với định tuyến tĩnh, đường dẫn được chọn trước cho mỗi cặp nguồn – đích của các node trong mạng. Các giải thuật định tuyến chi phí tối thiểu có thể được sử dụng. Kế hoạch định tuyến tĩnh được sử dụng hầu hết các mạng truyền thống, trong kế hoạch định tuyến này chủ yếu với mục đích làm giảm các hệ thống chuyển mạch phải đi qua với yêu cầu kết nối đường dài. Kĩ thuật định tuyến tĩnh bộc lộ một số nhược điểm như: quyết định định tuyến tĩnh không dựa trên sự đánh giá lưu lượng và topo mạng hiện thời. Các bộ định tuyến không phát hiện ra các bộ định tuyến mới, chúng chỉ có thể chuyển thông tin đến tới các các bộ định tuyến được chỉ định trước của nhà quản lí mạng. Định tuyến động: định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo mạng thay đổi hoặc lưu lượng mạng thay đổi. Định tuyến động thể hiện tính linh hoạt và dễ dàng mở rộng mạng. Dựa vào phạm vi định tuyến, ta phân loại thành: định tuyến trong và định tuyến ngoài. Định tuyến trong: định tuyến xảy ra bên trong một hệ thống độc lập (AS – Autonomous System), các giao thức thường dùng là RIP (Router Information Protocol), IGRP (Interior Gateway Routing Protocol), OSPF (Open Shortest Path First), EIGRP (Enhanced IGRP),… Định tuyến ngoài: định tuyến xảy ra giữa các hệ thống độc lập (AS), liên quan tới dịch vụ của nhà cung cấp mạng sử dụng giao thức định tuyến ngoài rộng và phức tạp. Giao thức thường dùng là BGP (Border Gateway Protocol). Hình 3.2: Định tuyến trong và định tuyến ngoài 3.4.3. Lí thuyết đồ thị Trong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của lí thuyết đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọi là đỉnh nối với nhau bởi các cạnh. Thông thường đồ thị thường được vẽ dưới dạng tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tuỳ theo ứng dụng mà một số cạnh có thể có hướng. Hình 3.3: Lí thuyết đồ thị Có 3 loại đồ thị: đồ thị có hướng, đồ thị vô hướng và đồ thị hỗn hợp. 3.4.3.1. Đồ thị vô hướng. Đồ thị vô hướng hoặc đồ thị G là một cặp có thứ tự (order pair) G=(V,E), trong đó: V là tập các đỉnh hoặc nút. E là tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là cạnh. Hai đỉnh thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó. Hình 3.4: Đồ thị vô hướng 3.4.3.2. Đồ thị có hướng. Hình 3.5: Đồ thị có hướng Đồ thị có hướng G là một cặp có thứ tự G=(V,A), trong đó: V là tập các nút hoặc đỉnh. A là tập các cạnh có thứ tự chứa các đỉnh, được gọi là các cạnh có hướng hoặc cung. Một cạnh e=(x,y) được coi là có hướng từ x đến y, x được gọi là điểm đầu/gốc và y được coi là điểm cuối/ngọn của cạnh. Từ đó ta phân loại ra: đồ thị đơn và đa đồ thị. Đồ thị đơn: là đồ thị mà giữa hai đỉnh chỉ có tối đa một cạnh. Đa đồ thị: là đồ thị mà giữa hai đỉnh có thể có nhiều hơn một cạnh. Đa đồ thị có hướng là một đồ thị có hướng mà trong đó nếu x và y là hai đỉnh thì đồ thị được phép có cả hai cung (x,y) và (y,x). Đồ thị đơn có hướng là một đồ thị có hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị chỉ được phép có tối đa một trong hai cung (x,y) và (y,x). 3.4.3.3. Đồ thị hỗn hợp Đồ thị hỗn hợp G là bộ ba có thứ tự G=(V,E,A) với V,E,A được định nghĩa như trên. 3.4.3.4. Ví dụ Hình 3.6: Ví dụ Với hình trên, ta có các giá trị sau: - V={1,2,3,4,5,6} - E={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}} Đôi khi thông tin nối từ đỉnh 1 đến đỉnh 2 được kí hiệu là 1~2. Bài toán định tuyến gán bước sóng có liên hệ chặt chẽ với bài toán tô màu cho các nút trong đồ thị. Bài toán của chúng ta là tô màu cho các nút thuộc G sao cho hai node kế cận nhau phải mang màu khác nhau thể hiện mỗi trạng thái của node. 3.4.4. Các thuật toán cơ bản trong định tuyến Các mạng chuyển mạch gói và internet dựa trên quyết định định tuyến của nó từ các tiêu chí tối thiểu. Ở đây ta xét đến chi phí tuyến được sử dụng như tham số ngõ vào của thuật toán định tuyến chi phí tối thiểu mà có thể phát biểu đơn giản như sau: Cho một mạng gồm các node được nối bởi các tuyến song công, trong đó, mỗi tuyến có một chi phí được gán cho mỗi hướng, định nghĩa chi phí của đường dẫn giữa hai node là tổng chi phí của các tuyến hợp thành đường dẫn. Với mỗi cặp node, tìm đường dẫn với chi phí tối thiểu. Hầu hết các thuật toán chi phí tối thiểu đang sử dụng trong các mạng chuyển mạch gói và internet là Dijkstra hoặc Bellman-Ford. Ta sẽ xét hai thuật toán này dưới đây. 3.4.4.1. Thuật toán trạng thái liên kết LSA Trong thuật toán trạng thái liên kết, các node mạng quảng bá giá trị liên kết của nó với các node xung quanh tới các node khác. Sau khi quảng bá, tất cả các node đều biết rõ topo mạng và thuật toán sử dụng để tính toán con đường ngắn nhất tới node đích là thuật toán Dijkstra. Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán tìm đường đi ngắn nhất trong một đồ thị có hướng không có cạnh mang trọng số âm. 3.4.4.1.1. Bài toán Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị. Ví dụ: chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường hay có thể là chi phí (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi. Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C. 3.4.4.1.2. Thuật toán Thuật toán Dijkstra có thể mô tả như sau: Ta quản lý một tập hợp động S. Ban đầu S={s}. Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v. Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa. Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung vào tập S. Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán, chúng ta phải dùng đến tính chất này. 3.4.4.1.3. Chứng minh Ý tưởng được chứng minh như sau: Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v. Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v. Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy. Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh. 3.4.4.1.4. Các bước thực hiện Thuật toán Dijkstra dùng trong giao thức định tuyến 0SPF đi qua các bước sau: 1. Bộ định tuyến xây dựng đồ thị của mạng và xác định các node nguồn – đích, ví dụ như V1 và V2. Sau đó nó xây dựng một ma trận, được gọi là ma trận liền kề. Ma trận này thể hiện trọng số của các cạnh, ví dụ như [i,j] là trọng số của cạnh nối Vi với Vj. Nếu không có kết nối trực tiếp giữa Vi và Vj, trọng số này được xác định là vô cùng. 2. Bộ định tuyến xây dựng bảng trạng thái cho tất cả các node trong mạng. Bảng này gồm các phần: Chiều dài: thể hiện độ lớn của trọng số từ nguồn đến node đó. Nhãn của node: thể hiện trạng thái của node, mỗi một node có thể có một trong hai trạng thái là cố định hay tạm thời. 3. Bộ định tuyến gán thông số ban đầu của bảng trạng thái cho tất cả các node và thiết lập chiều dài của chúng là vô cùng và nhãn của chúng là tạm thời. 4. Bộ định tuyến thiết lập một T-node. Ví dụ như V1 là node nguồn T-node, bộ định tuyến sẽ chuyển nhãn của V1 sang cố định. Khi một nhãn chuyển sang cố định, nó sẽ không thay đổi nữa. 5. Bộ định tuyến sẽ cập nhật bảng thái trạng thái của tất cả các node tạm thời mà các node này liên kết với node nguồn T-node. 6. Bộ định tuyến nhìn vào các node tạm thời và chọn một node duy nhất mà node này có trọng số đến V1 là nhỏ nhất. Node này sau đó trở thànđ node đích T-node. 7. Nếu node này không phải là V2 thì bộ định tuyến trở lại bước 5. 8. Nếu node này là V2 thì bộ định tuyến tách node trước đó của nó khỏi bảng trạng thái và cứ thực hiện điều này cho đến khi đến node V1. Một lượt các node chỉ ra tuyến tối ưu nhất từ V1 đến V2. 3.4.4.1.5. Ví dụ về thuật toán Dijkstra Dưới đây ta sẽ tìm đường ngắn nhất giữa A và E. Bước 1: Theo hình sau, node A làm node nguồn T-node, nhãn của nó chuyển sang cố định và được đánh dấu bằng Bước 2: Trong bước này, ta sẽ thấy được bảng trạng thái của các node nối trực tiếp với node A là cặp node (B,C). Đường từ A đến B là ngắn nhất (có trọng số nhỏ nhất), do đó nó được chọn làm T-node và sau đó nhãn của nó chuyển sang cố định. Bước 3: giống như bước 2, dựa trên bảng trạng thái của các node kết nối trực tiếp với node B là cặp node (D,E).Tương tự như thế, node D kết nối với node B là đường ngắn nhất (mang trọng số 2 nên nhỏ hơn trọng số của cạnh BE), do đó node D được làm T-node, và sau đó nhãn của nó chuyển sang cố định. Bước 4: trong bước này chúng ta không có node tạm thời nào, vì thế ta chỉ có thể chọn T-node tiếp theo. Node E được chọn vào đồ thị, cạnh DE có trọng số nhỏ nhất. Bước 5: Node E là node đích nên chúng ta kết thúc quá trình định tuyến này. 3.4.4.2. Thuật toán định tuyến vectơ khoảng cách DVA Là một thuật toán định tuyến tương thích nhằm tính toán con đường ngắn nhất giữa các cặp node trong mạng, được biết đến như là thuật toán Bellman-Ford. Các node mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích, node kế tiếp, và con đuờng ngắn nhất tới đích. Mỗi node trong mạng có bảng định tuyến cho thấy đường tốt nhất đến mọi đích và mỗi node chỉ gởi bảng định tuyến của nó đến các node láng giềng. Vấn đề tồn tại của thuật toán DV là nó thực hiện đếm đến vô cùng khi có một kết nối bị hỏng. Vấn đề này có thể thấy rõ ở ví dụ sau: Hình 3.8: Ví dụ của thuật toán DVA Với hình 3.8 cho thấy có duy nhất một tuyến giữa node A đến những node khác. Giả sử trọng số trên mỗi cạnh đều bằng 1, mỗi node (Router) đều chứa bảng định tuyến. Bây giờ, nếu ta cắt kết nối giữa A và B thì node B sẽ hiệu chỉnh lại bảng định tuyến của nó. Sau khoảng thời gian, các node trao đổi thông tin bảng định tuyến và B nhận bảng định tuyến của C. Khi C không biết gì xảy ra với kết nối giữa kết nối giữa A và B, nó sẽ cho rằng có một tuyến kết nối với trọng số là 2 (1 cho kết nối C-B và 1 cho kết nối B-A), nó không biết rằng kết nối A-B đã bị cắt. B nhận bảng định tuyến này và nghĩ rằng có một tuyến khác giữa C và A, vì thế nó sửa lại bảng định tuyến và thay đổi giá trị trọng số của kết nối B-A về 3 (1 cho kết nối B-C, 2 cho kết C-A). Một lần nữa các node thay đổi bảng định tuyến của nó. Khi C nhận bảng định tuyến của B, nó thấy rằng bảng B thay đổi trọng số của tuyến B-A từ 1 thành 3, vì thế nó cập nhật bảng định tuyến và thay đổi trọng số của tuyến C-A thành 4 (1 cho kết nối C-B và 3 cho kết nối B-A). Quá trình này cứ xảy ra miết cho đến khi tất cả các node tìm ra trọng số của tuyến đến A là vô cùng. Thuật toán Bellman-Ford là một thuật toán tính các đường đi ngắn nhất trong một đồ thị có hướng có trọng số (trong đó một số cung có thể có trọng số âm).Thuật toán Dijksta đòi hỏi trọng số của các cung phải có giá trị không âm. Do đó thuật toán Bellman-Ford thường dùng khi có các cung với trọng số âm. 3.4.4.2.1. Thuật toán Giải thuật Bellman-Ford có thể phát biểu: Tìm các đường dẫn ngắn nhất từ node nguồn cho trước với ràng buộc chỉ chứa một tuyến, sau đó tìm đường dẫn ngắn nhất với ràng buộc chỉ chứa tối đa hai tuyến và cứ thế tiếp tục. Nếu đường dẫn trước đó là ngắn nhất thì để lại còn không thì cập nhật đường dẫn mới. Thuật toán được tiến hành qua các tầng được biểu diễn như sau: function BellmanFord (danh_sách _đỉnh, danh_sách_cung, nguồn) // hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh cung // hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh, sao cho các //giá trị đỉnh_liền_ trước sẽ lưu lại các đường đi ngắn nhất. // bước 1: khởi tạo đồ thị for each v in danh_sách_đỉnh: if v is nguồn then khoảng_cách (v) := 0 else khoảng_cách (v) := infinity đỉnh_liền_trước (v) := null // bước 2: kết nạp cạnh for i from 1 to size (danh_sách_đỉnh) : for each (u, v) in danh_sách_cung : if khoảng_cách (v) > khoảng_cách (u) + trọng_số (u, v) : khoảng_cách (v) := khoảng_cách (u) + trọng_số (u, v) đỉnh_liền_trước (v) := u // bước 3: kiểm tra chu trình âm for each (u, v) in danh_sách_cung : if khoảng_cách (v) > khoảng_cách (u) + trọng_số (u, v) : error “Đồ thị chứa chu trình có trọng số âm” 3.4.4.2.2.Chứng minh Tính đúng đắn của thuật toán có thể chứng minh bằng qui nạp. Thuật toán có thể phát biểu chính xác theo kiểu qui nạp như sau: Định lý: Sau i lần lặp vòng for: 1. Nếu Khoảng_cách(u) không có giá trị vô cùng lớn, thì nó bằng độ dài của một đường đi nào đó từ s tới u; 2. Nếu có một đường đi từ s tới u qua nhiều nhất i cung, thì Khoảng_cách (u) có giá trị không vượt quá độ dài của đường đi ngắn nhất từ s tới u qua tối đa i cung. Chứng minh: Trường hợp cơ bản: Xét i =0 và thời điểm trước khi vòng for được chạy lần đầu tiên. Khi đó, với đỉnh nguồn khoảng_cách (nguồn) := 0, điều này đúng. Đối với các đỉnh u khác, khoảng_cách (u) := infinity, điều này cũng đúng vì không có đường đi nào từ nguồn đến u qua 0 cung. Trường hợp quy nạp: Chứng minh câu 1: Xét thời điểm khi khoảng cách tới một đỉnh được cập nhật bởi công thức khoảng_cách (v) := khoảng_cách (u) + trọng_số (u,v). Theo giả thiết quy nạp, khoảng_cách (u) là độ dài của một đường đi nào đó từ nguồn tới u. Do đó, khoảng_cách (u) + trọng_số (u, v) là độ dài của đường đi từ nguồn tới u rồi tới v. Chứng minh câu 2: Xét đường đi ngắn nhất từ nguồn tới u qua tối đa i cung. Giả sử v là đỉnh liền ngay trước u trên đường đi này. Khi đó, phần đường đi từ nguồn tới v là đường đi ngắn nhất từ nguồn tới v qua tối đa i-1 cung. Theo giả thuyết quy nạp, khoảng_cách (v) sau i-1 vòng lặp không vượt quá độ dài đường đi này. Do đó, trọng_số (v, u) + khoảng_cách (v) có giá trị không vượt quá độ dài của đường đi từ s tới u. Trong lần lặp thứ i, khoảng_cách (u) được lấy giá trị nhỏ nhất của khoảng_cách (v) + trọng_số (v, u) với mọi v có thể. Do đó, sau i lần lặp, khoảng_cách (u) có giá trị không vượt quá độ dài đường đi ngắn nhất từ nguồn tới u qua tối đa i cung. Khi i bằng số đỉnh của đồ thị, mỗi đường đi tìm được sẽ là đường đi ngắn nhất toàn cục, trừ khi đồ thị có chu trình âm. Nếu tồn tại chu trình âm mà từ đỉnh nguồn có thể đi đến được thì sẽ không tồn tại đường đi nhỏ nhất (vì mỗi lần đi quanh chu trình âm là một lần giảm trọng số của đường). 3.4.5. Kết luận Cả hai thuật toán này đều hoạt động dưới điều kiện tĩnh của topo mạng và chi phí tuyến thì cả hai hội tụ về một nghiệm. Khi mạng có nhiều sự thay đổi thì thuật toán sẽ cố gắng bám theo sự thay đổi, tuy nhiên, nếu chi phí tuyến phụ thuộc vào lưu lượng, tức là nó lại phụ thuộc vào đường dẫn được chọn thì với đáp ứng làm cho mạng không ổn định. 3.5. Gán bước sóng Việc gán bước sóng là nhân tố chính ảnh hưởng đến xác suất tắc nghẽn và tính thực thi của mạng. Gán bước sóng thích hợp có thể làm giảm số bước sóng sử dụng hoặc không cần dùng đến bộ chuyển đổi bước sóng, nên ta có thể giảm được chi phí của mạng xuống rất nhiều. Gán bước sóng được chia làm hai loại cho lưu lượng mạng cố định và lưu lượng mạng thay đổi. Khi lưu lượng mạng cố định thì phép gán cố định, cùng một bước sóng được gán nếu( nếu có sẵn) cho mọi yêu cầu được tạo ra ở một nút, nếu không thì yêu cầu bị chặn. Khi lưu lượng mạng thay đổi, lúc có yêu cầu đến một nút mạng nào đó thì nút đó sẽ dùng một giải thuật để chọn một bước sóng riêng biệt còn rỗi ở nút đó và gán cho lightpath đó để định tuyến nó, nếu không thì yêu cầu không được giải quyết. Giải thuật cho phương pháp gán quản lí một danh sách các bước sóng được sử dụng, các bước sóng còn rỗi ở mỗi nút. Các phương pháp gán bước sóng được chia làm các loại như sau: Kiểu gán Random: khi có yêu cầu đến một nút, nút đó sẽ xác định những bước sóng còn hiệu lực ( tức là còn rỗi) và chọn ngẫu nhiên một trong những bước sóng đó để gán cho yêu cầu đó. Các bước sóng còn rỗi ở mỗi nút được xác định bằng cách loại bỏ bước sóng đã sử dụng ra khỏi danh sách bước sóng còn rỗi; khi cuộc gọi kết thúc, được loại ra khỏi danh sách bước sóng bị bận và được thêm vào trở lại danh sách bước sóng rỗi ban đầu. Phương pháp này không cần đòi hỏi những thông tin về toàn bộ trạng thái của mạng khi thực hiện gán bước sóng. Phép gán này phân phối lưu lượng một cách tuỳ ý, do vậy sự tận dụng bước sóng được cân bằng và tranh chấp bước sóng thấp nên xác suất tắc nghẽn cũng thấp hơn. Kiểu gán First - Fit: phép gán này sẽ tìm và gán những bước sóng theo một trình tự cố định. Tất cả các bước sóng được đánh số từ thấp đến cao và các bước sóng được chọn để gán cũng theo chỉ số từ thấp đến cao, tức là bước sóng đầu tiên được chọn là bước sóng có chỉ số nhỏ nhất trong số bước sóng rỗi và gán cho yêu cầu. Cũng tương tự như phương pháp gán Random, phép gán này không cần bất kì thông tin nào về thông tin trạng thái mạng. Hạn chế của phương pháp này là các bước sóng có chỉ số nhỏ hơn được dùng nhiều, trong khi những bước sóng có chỉ số lớn hầu như không được sử dụng. Hơn nữa sự gia tăng số bước sóng trong sợi cũng không mang lại hiệu quả nào bởi vì những bước sóng có chỉ số cao rất ít khi được dùng. Do đó sự tranh chấp đối với những bước sóng có chỉ số nhỏ tăng lên, làm xác suất tắc nghẽn cũng tăng lên. Phép gán này cho chi phí thấp hơn so với phép gán Random bởi vì nó không cần phải kiểm tra tất cả các bước sóng trong mỗi tuyến, vì thế nó được ưa chuộng hơn. Phép gán Least - used: Phép gán này chọn những bước sóng mà những bước sóng này ít được sử dụng nhất trong mạng. Mục đích của phép gán này là cân bằng tải trên tất cả những bước sóng. Phép gán này đòi hỏi thông tin trạng thái về mạng để tìm ra bước sóng ít được sử dụng nhất. Tuy nhiên phương pháp này phải tốn kém cho chi phí lưu trữ và tính toán. Phép gán Most - used: nó là phép gán chỉ là ngược với phép gán Least-used, nó tìm chọn những bước sóng được sử dụng nhiều nhất trong mạng. Phép gán này phải đòi hỏi những thông tin về trạng thái mạng để tìm ra bước sóng được sử dụng nhiều nhất. Nó cũng tốn những chi phí tương tự như trong phép gán Least- used, tuy nhiên nó thực hiện tốt hơn so với phép gán Least- used. Với các phép gán bước sóng kể trên, phương pháp Random và First - Fit là thực tế hơn vì dễ thực hiện. Không giống như hai phương pháp Least- used và Most- used đòi hỏi phải có các thông tin về mạng. Nó đơn giản chỉ dựa vào trạng thái nút lúc đó và chọn một bước sóng từ những bước sóng rỗi ở kết nối ngõ ra đó. Một cách tương đối, phương pháp ngẫu nhiên Random cho hiệu quả tốt hơn phương pháp First - Fit. Để thực hiện hai phương pháp gán Least - used và Most - used, mỗi nút cần trang bị thông tin toàn bộ mạng. Nên những phương pháp này phụ thuộc vào sự thông minh và hiểu biết chính xác của các nút. Vì trạng thái mạng thay đổi một cách nhanh chóng nên khó có thể biết được một cách chính xác thông tin mạng ở tất cả các thời điểm, do vậy ảnh hưởng đến việc gán bước sóng. Hơn nữa các nút trao đổi thông tin với nhau về mạng sau mỗi khoảng thời gian cố định và những thông tin này sẽ tiêu thụ một băng thông đáng kể, vì thế làm giảm băng thông sẵn có để truyền dữ liệu. 3.6. Sự thiết lập đường ảo (Virtual path) Một đường ảo được xem như một đường đi của ánh sáng từ nguồn đến đích. Khi có yêu cầu cuộc gọi được tạo ra ở nút, nút sử dụng giải thuật định tuyến và gán bước sóng để tìm ra một đường đi và một bước sóng cho cuộc gọi đó. Nút sẽ gán bước sóng đã được chọn cho cuộc gọi đó và định tuyến nó đến nút kế tiếp. Ở mỗi nút trung gian của đường đi, bước sóng của lightpath đi tới được kiểm tra xem có sẵn để được gán và từ đó để có thể đi tiếp hay không. Nếu bước sóng đó không có sẵn, và nếu nút có bộ chuyển đổi bước sóng, nó có thể chuyển sang bước sóng khác để định tuyến lightpath. Đường đi vừa thiết lập được gọi là đường ảo, được thiết lập sẵn trước khi bất kì dữ liệu nào được truyền qua. Một đường vật lí bao gồm tất cả các tuyến truyền dẫn (link) hình thành trên lộ trình từ nguồn đến đích, nhưng đường ảo có thể chứa các bước sóng giống hoặc khác nhau từ nguồn đến đích. Hai yêu cầu cho cuộc gọi có cùng chung điểm đầu cuối đích và nguồn có thể có cùng đường vật lí nhưng có các đường ảo khác nhau. Hình sau chỉ ra sự hành thành của một lightpath. Ở đây hai cuộc gọi được tạo ra từ nút 1 và đường ảo cho mỗi cuộc gọi tạo thành được vẽ ra. Đối với cuộc gọi thứ nhất, nút 1 gán bước sóng và gởi nó đến nút 2. Giả sử nút 2 có một bộ chuyển đổi bước sóng nhưng không có sẵn bước sóng , vì thế nó chuyển sang bước sóng và gửi đến nút 3. Nút 3 gán tiếp vì nó có sẵn và định tuyến lightpath đến nơi. Bằng cách này đường ảo thứ nhất được thiết lập. Nếu cuộc gọi thứ hai được tạo ra ở nút 1 ngay sau đó, thì một đường ảo thứ hai được tạo ra tương tự. Ta thấy rằng đường vật lí thì giống nhau nhưng các đường ảo thì khác nhau. Tổng số các đường ảo được thiết lập từ nguồn đến đích phụ thuộc vào số bước sóng sẵn có trên sợi. Số đường ảo được thiết lập thật sự phụ thuộc vào tốc độ cuộc gọi đi đến. Các bộ chuyển đổi bước sóng giúp thiết lập được nhiều đường ảo hơn. Hình 3.9: Sự thiết lập đường ảo 3.7. Phân loại mạng quang WDM 3.7.1. Mạng single- hop Trong mạng quang WDM single- hop, một khi luồng dữ liệu được phát đi dưới dạng ánh sáng sẽ đến được đích trực tiếp mà không cần phải chuyển sang dạng điện ở những node trung gian. Để truyền dẫn một gói, một trong những laser phát của nút gởi và một trong những bộ thu của node nhận phải được chỉnh đến cùng một bước sóng trong khoảng thời gian truyền dẫn gói. Trong các mạng chuyển mạch mạch, tốc độ điều chỉnh của các bộ thu phát thường yêu cầu thấp. Ngược lại trong các mạng chuyển mạch gói, các bộ thu phát ở các node cần được chỉnh đến các bước sóng khác nhau một cách nhanh chóng để gửi và nhận các gói tin khác tiếp theo. Bên cạnh vấn đề kĩ thuật của việc chuyển đổi bước sóng nhanh, một thách thức quan trọng khác nữa là phát triển các giao thức để phối hợp hiệu quả những kết nối ở các bước sóng khác nhau trong mạng. Để một hệ thống single- hop hoạt động hiệu quả, băng thông được cấp phát giữa các node đang tranh chấp phải được quản lí linh động. Các hệ thống này có thể phân thành hai loại: có phối hợp trước khi truyền dẫn và không yêu cầu phối hợp trước khi truyền dẫn. Các loại phối hợp dùng một kênh điều khiển đơn dùng chung giữa các node và sự truyền dữ liệu thật sự xảy ra thông qua một số các kênh dữ liệu. Các node rỗi cần giám sát kênh điều khiển. Trước khi phát hoặc thu gói dữ liệu, một gói chỉnh bộ phát hay bột thu của nó đến kênh dữ liệu thích hợp. Ngược lại trong hệ thống loại thứ hai, không có sự tồn tại của kênh điều khiển và các node phát hoặc thu từ các kênh được định trước. 3.7.2. Mạng Multi- hop Mạng multi- hop khắc phục được nhược điểm này bằng cách tránh sử dụng bộ thu phát điều chỉnh bước sóng. Mỗi node được trang bị một số các bộ thu phát quang được chỉnh cố định. Mỗi bộ phát trong mạng được chỉnh đến một bước sóng khác nhau. Kết nối trực tiếp single- hop giữa hai node chỉ có thể xảy ra khi nếu nút đến có một trong những bộ thu của nó được chỉnh đến một trong những bước sóng của node gởi. Sự kết nối giữa một cặp node bất kì trong mạng đạt được bằng cách định tuyến thông qua các node trung gian. Ở đó kênh thông tin quang được chuyển thành dạng điện, địa chỉ đến của gói được giải mã, sau đó gói được chuyển mạch điện và được phát lại trên bước sóng để đến node đích hoặc đến các node trung gian khác mà ở đó quá trình này được lặp lại. Vì vậy, một gói sẽ trải qua nhiều bước sóng thông qua một số node trung gian trước khi đến được node đích. 3.8. Giải thuật cho vấn đề định tuyến và gán bước sóng với lưu lượng mạng thay đổi DRWA Bạn có thể hình dung các vấn đề mà một giải pháp cho DRWA cần phải giải quyết, mục đích của nó là tối thiểu tắc nghẽn tại node mạng (tức là số yêu cầu kết nối sẽ bị refuse/tổng số yêu cầu), nâng cao hiệu suất sử dụng tài nguyên (cùng một lượng fiber, node, chuyển đổi bước sóng,...có thể tạo ra nhiều LP nhất) và cải thiện hiệu năng tổng thể của mạng (hiệu năng = xác suất tắc nghẽn + độ phức tạp của giải thuật). Giải thuật được trình bày như sau: Giả sử mỗi LP có tối đa H hop (link). Trên mỗi link (fiber) sử dụng W bước sóng (sub-channel). Tập các đường đi có thể giữa hai node bất kỳ là R*.  Trạng thái của mỗi bước sóng trên link (fiber) được mã hoá bằng hai bit b0b1. Khi có yêu cầu LP, node nguồn sẽ gởi bản tin cập nhật trạng thái dọc theo các path tiềm năng để tập hợp thông tin trạng thái đường truyền (bản tin có thể nhúng trong giao thức báo hiệu nào đó) Hai bit trạng thái như sau: b0b1= 00: bước sóng đang bận. b0b1= 01: có thể dùng liên tục không cần chuyển đổi bước sóng. b0b1= 10: muốn dùng phải chuyển đổi bước sóng b0b1= 11: có thể dùng cả hai cách Tại mỗi node trung gian thuộc LP, 2*W bít trạng thái bước sóng được ghi (tagged) vào sau bản tin này, và gửi đến đích. Nếu ở thời điểm đó node không thể thiết lập kênh (do hết bước sóng chẳng hạn), nó loại bỏ (discard) gói tin báo hiệu và gửi bản tin thông báo (notification) tới nguồn hoặc đích để xử lý. Tại đích, thông tin trong mỗi bản tin cập nhật trạng thái được đưa ra dạng ma trận: Toàn bộ hình ảnh về trạng thái tài nguyên đường truyền từ node 0 đến node H-1 được phản ánh trên ma trận này. Giải thuật đánh dấu bước sóng thực hiện dựa trên các ma trận (thành công) từ R* path tiềm năng của mỗi cặp node. Ký hiệu CS của bước sóng lamda(m) là bậc liên tục của bước sóng, tức là có thể dùng nó liên tục trong dãy liên tiếp các node nào đó dọc theo path. Giải thuật như sau:1. Tìm tập tất cả các tổ hợp CS của mỗi bước sóng, trên mỗi path, ký hiệu CSij2. Tìm tập các tổ hợp CS* thuộc {CSij} (i =1: W; j =1:R*) phủ kín LP với số phần tử tối thiểu (tức là ít đoạn CS nhất, điều này tương đương ít phải dùng bộ chuyển đổi bước sóng nhất) 3. Áp dụng hàm mục tiêu (trong giải thuật là tổng chi phí) cho mỗi tổ hợp CS tìm thấy trong bước 2 để chọn ra tổ hợp có tổng chi phí tối thiểu. 3.9. Kết luận chương Qua chương này, chúng ta đã tìm hiểu về phương pháp định tuyến và gán bước sóng trong mạng WDM, khi có yêu cầu thiết lập lightpath từ node nguồn đến node đích thì bộ định tuyến bước sóng có nhiệm vụ xác định đường đi và gán bước sóng cho lightpath đó. Trong mạng quang WDM, việc sử dụng thuật toán định tuyến bước sóng để đạt được tối ưu mạng là điều hết sức ý nghĩa. Thuật toán Dijkstra với việc định tuyến tìm đường ngắn nhất có nhiều ưu điểm trong mạng tập trung nên em sẽ sử dụng để mô phỏng việc định tuyến trong mạng quang. CHƯƠNG 4 THỰC HIỆN MÔ PHỎNG 4.1. Giới thiệu chương Định tuyến là công việc hết sức quan trọng trong mạng quang WDM, nó thực hiện tìm đường cho lightpath mang lưu lượng thông tin từ nguồn đến đích với mục đích tối ưu mạng. Trong chương này, dựa trên phần mềm Visual C++, em mô phỏng phần định tuyến cho các lightpath với hàm mục tiêu chúng ta có thể tuỳ chọn như chi phí, độ trễ, lượng lưu lượng… qua các tuyến từ nguồn đến đích. Thuật toán sử dụng để thực hiện định tuyến là thuật toán Dijkstra. Các trọng số trên các tuyến không chỉ là độ dài đường đi của tuyến mà tuỳ theo một tiêu chí nào đó của mạng như chi phí tuyến, độ trễ, băng thông, lưu lượng thông tin... Nếu lấy theo tiêu chí là chi phí thấp nhất thì trọng số trên các tuyến (cạnh) là chí phí của tuyến đó. 4.2. Giới thiệu về ngôn ngữ Visual C++ Visual C++ là ngôn ngữ lập trình dựa trên nền tảng cơ bản của C++, đó là lập trình hướng đối tượng. Nếu các bạn đã lập trình trên C++ thì việc xây dựng các ứng dụng trên Visual C++ rất thuận lợi. Khi thực hiện lập trình C/C++, để tạo các giao diện phức tạp, trình bày đẹp hoàn toàn không đơn giản. Nhưng đối với Visual C++ thì việc đó khá đơn giản. Bạn chỉ cần sử dụng các điều khiển hay xây dựng một menu đưa vào ứng dụng của mình mà các mã lệnh cần viết không quá dài dòng và phức tạp như trong C/C++. Trong chương trình mô phỏng của em có thể sử dụng bất kì ngôn ngữ lập trình nào. Em chọn ngôn ngữ Visual C++ do khả năng của nó tạo giao diện dễ dàng hơn C/C++. 4.3. Lưu đồ thuật toán Giả sử bộ định tuyến mô phỏng tìm đường đi với đường đi ngắn nhất qua các tuyến giữa node nguồn và node đích. Các trọng số trên các cạnh là độ dài của tuyến thông tin từ node này đến node kia. Bắt đầu Xác định node nguồn và đích như V1 và V2 Thiết lập V1 là T-node Thiết lập nhãn của T-node sang cố định, sau đó cập nhật bảng trạng thái các node lân cận. Xác định node tạm thời nối với V1 mà có trọng số nhỏ nhất và thiết lập thành T-node Dựa vào thông tin trong bảng trạng thái, làm như thế cho đến khi tới node V1, dãy các node đó là đường đi ngắn nhất Kết thúc NO YES T-node có phải là V2 không? Thuật toán sẽ thực hiện tìm đỉnh u trong tập hợp Q mà có giá trị d[u] nhỏ nhất. Đỉnh này được loại ra khỏi Q và được đưa vào tập S. Tập S chứa một bảng các đỉnh tạo thành một trong những đường đi ngắn nhất từ s đến node nguồn t nào đó. 1 function Dijkstra(G, w, s) 2 for each vertex v in V[G] 3 d[v] := infinity // Gán các giá trị ban đầu 4 previous[v] := undefined 5 d[s] := 0 // Khoảng cách từ s đến s bằng 0 6 S := empty set // Thiết lập S là tập hợp rỗng 7 Q := V[G] // Tập Q chứa tất cả các node của đồ thị 8 while Q is not an empty set 9 u := Extract_Min(Q) 10 S := S union {u} 11 for each edge (u,v) outgoing from u 12 if d[u] + w(u,v) < d[v] 13 d[v] := d[u] + w(u,v) 14 previous[v] := u 4.4. Kết quả mô phỏng Thuật toán Dijkstra tìm đường đi ngắn nhất từ node nguồn đến node đích được thực hiện như sau: 1.Click vào biểu tượng ”THEM NODE” để lấy node ra như sau: 2.Click vào biểu tượng “THEM CANH” để nối các cạnh lại với nhau. 3.Click vào biểu tượng “DUONG NGAN NHAT” thực hiện tìm đường ngắn nhất giữa hai cặp node bất kì. 4.Click “OK” để nhận được kết quả. 4.5. Kết luận chương. Ta thấy được thuật toán định tuyến Dijkstra được ứng dụng hiệu quả trong việc định tuyến các lightpath trong mạng WDM để tìm được đường đi tối ưu với các hàm mục tiêu (cost function) của mạng mà ta có thể áp đặt cho nó. Hàm mục tiêu này ta có thể theo tiêu chí nào đó của mạng như là chi phí tuyến, lượng lưu lượng, băng thông… Sự áp đặt này thực hiện bằng cách đặt trọng số trên các tuyến là giá trị của các hàm mục tiêu trên. Sau quá trình định tuyến đến các node mạng, các node mạng thực hiện gán bước sóng cho lightpath. Việc gán bước sóng phải thoả mãn điều kiện liên tục bước sóng nếu không node mạng đó phải sử dụng bộ chuyển đổi bước sóng. Đề tài “định tuyến và gán bước sóng trong mạng quang WDM” đã cho thấy được vai trò quan trọng của định tuyến và gán bước sóng trong mạng quang WDM, hiểu được một số giải thuật định tuyến và các phương pháp gán bước sóng cho các lightpath trong mạng quang. Đồng thời chương trình mô phỏng đã thể hiện quá trình định tuyến của các lightpath từ node nguồn đến node đích để được một đường đi tối ưu theo một hàm mục tiêu nào đó. Kết thúc quá trình nghiên cứu đề tài, em đưa ra một số nhận xét như sau: Chương trình mô phỏng thực hiện định tuyến với mục đích tìm đường đi tối ưu từ node nguồn đến node đích, đây là đường đi duy nhất. Tuy vậy, để tăng cường hiệu năng mạng thì không thể đơn thuần chọn duy nhất một tuyến tối ưu đó mà phải đánh giá được các tuyến còn lại để thực hiện phân tải, tránh tình trạng một tuyến hoạt động hết công suất trong khi đó có những tuyến khả thi còn rỗi. Sau khi thực hiện định tuyến cho lightpath, phải thực hiện gán bước sóng cho nó. Nếu toàn bộ node mạng không sử dụng bộ chuyển đổi bước sóng thì toàn bộ các tuyến trên đường đi từ nguốn đến đích chỉ được gán một bước sóng duy nhất. Tuy nhiên, tài nguyên số bước sóng trên mỗi node mạng có hạn, điều này làm xác suất tắc nghẽn rất cao khi một node mạng không cung cấp bước sóng đã ràng buộc từ trước. Vì thế, các mạng hiện nay luôn tìm cách thực hiện định tuyến và gán bước sóng sao cho đạt được tối ưu mạng là giảm xác suất tắc nghẽn. Ngày nay, người ta đang hướng tới mạng toàn quang mà mọi công việc xử lí đều thực hiện hoàn toàn trong miền quang. Mạng toàn quang hứa hẹn sẽ đem lại tốc độ cao, giá thành mạng sẽ được giảm xuống một cách đáng kể. Đồ án được hoàn thành trong thời gian hạn chế, đặt nền móng cho việc nghiên cứu và phát triển sau này, vì thế không thể tránh khỏi những thiếu sót. Hi vọng trong thời gian tới với kinh nghiệm thực tiễn, em sẽ cố gắng hoàn thiện hơn đề tài của mình. [1] Nguyễn Đức Nghĩa- Nguyễn Tô Thành, “Toán Rời Rạc”, Nhà xuất Bản Đại Học Quốc Gia Hà Nội_2004 [2] [3] Senior, John.M, “Optical fiber communications”, Library of Congress Cataloging in Publication Data. [4] George N. Rouskas, “Routing and Wavelength Assignment in Optical WDM Networks”, Department of Computer Science_2000. [5] Krishna M.Sivalingam, Suresh Subramaniam, “Optical WDM Networks- Principles and Practice”, Kluwer Academic Publishers_2000. [6] [7] “Hệ thống thông tin quang/Vô tuyến”, LG Information and Communication LTD (LGIC) [8] Nguyễn Duy Nhật Viễn, “Kĩ thuật chuyển mạch trong mạng diện rộng”, Đại học Bách Khoa Đà Nẵng [9] Regis J. BUD Bates, “Optical Switching and Networking Handbook”, McGraw-Hill Companies [10] ’s algorithm [11] [12] Jun Zheng, Hussien T. Mousftah, “Distributed lightpath control for wavelength-routed WDM network”, University of Ottawa [13] Jin seek Choi, Nada Golmie, Francois Lapeyrere, Frederic Mouveaux and David Su, “A functional Classification of Routing and Wavelength Assignment Shemes in DWDM networks: Static Case”, National Institute of Standards and Technology, Gaithersburg, MD, USA PHỤ LỤC Thực hiện thêm biến và thực hiện mã lệnh sau: void CAlgorithmsView::OnAddNode() { m_Dijkstra.StartAddNodes(); } void CAlgorithmsView::OnAddEdge() { m_Dijkstra.StartAddEdges(); } void CAlgorithmsView::OnShortestPath() { CShorthestPath dlg; if(dlg.DoModal()==IDOK) // { m_Dijkstra.ShortestPath(dlg.m_node1, dlg.m_node2); } } Thực hiện vẽ các node và các cạnh bằng mã như sau: class CGraph { public: long GetNrNodes(); CGraph(); virtual ~CGraph(); VTYPE_NODE m_nodes; // dãy các node VTYPE_EDGE m_edges; // dãy các cạnh VTYPE_NODE_P d; // array of longs that contain // the shortest path at every step VTYPE_NODE_P pi; // array of longs that contain // the predecessor of each node for the shortest path }; // // // // // // // // // // // // // // class CNode { public: CNode Copy(); double m_cost; // gia tri trong so long m_NodeNr; // so node POINT m_p; // diem do hoa cho node CNode(); virtual ~CNode(); }; // // // // // // // // // // // class CEdge { public: bool m_red; // ve duong di ngan nhat // (neu mot canh la mot phan cua duong di ngan nhat thi no duoc ve mau do) double m_cost; // trong so cua canh (lay gia tri ngau nhien tu 0-9) long m_secondNode; long m_firstNode; POINT m_secondPct; POINT m_firstPct; CEdge(); virtual ~CEdge(); }; // ve canh bat dau tu node dau den node cuoi Thuật toán Dijkstra: // The Dijkstra's algorithm STDMETHODIMP CDijkstra::ShortestPath(long node1, long node2) { ReleaseGraph(); InitializeSource(g, g.m_nodes[node1-1]); // Thiet lap S ve rong VTYPE_NODE S; // Dat cac node vao Q VTYPE_NODE Q; VTYPE_NODE::iterator kl; for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++) { CNode node = (*kl).Copy(); Q.push_back(node); } // Algorithm while(Q.size()) { CNode nod = ExtractMin(Q); // tach node tim duoc ra khoi tap Q // dua node nay vao tapS S.push_back(nod); VTYPE_NODE::iterator kl; for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++) { if(ExistEdge(nod, (*kl))) { bool gasit = false; VTYPE_NODE::iterator kll; for(kll=Q.begin(); kll<Q.end(); kll++) { if((*kll).m_NodeNr == (*kl).m_NodeNr) gasit = true; } if(gasit) Relax(nod, (*kl), GetEdgeVal(nod, (*kl))); } } } RefreshDone(node1, node2); return S_OK; } Lệnh thực hiện vẽ: // Draw HDC dc = ::GetDC(m_hWnd); HPEN pen=CreatePen(PS_SOLID,0,RGB(0,0,0)); HPEN penred=CreatePen(PS_SOLID,2,RGB(255,0,0)); HBRUSH brush=CreateSolidBrush(RGB(0,0,0)); HPEN oldpen; HPEN oldbrush; oldpen=(HPEN)SelectObject(dc,pen); RECT rc; ::GetClientRect(m_hWndCD, &rc); Rectangle(dc, rc.left, rc.top, rc.right, rc.bottom); HFONT OldFont = (HFONT)::SelectObject(dc, m_lmfont); long nr = 0; VTYPE_NODE::iterator kl; for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++) { char s[5]; ltoa((*kl).m_NodeNr, s, 10);; Ellipse(dc, (*kl).m_p.x-10, (*kl).m_p.y-10, (*kl).m_p.x+10, (*kl).m_p.y+10); if(nr<9) TextOut(dc, (*kl).m_p.x-5, (*kl).m_p.y-8, s, 1); else TextOut(dc, (*kl).m_p.x-8, (*kl).m_p.y-8, s, 2); nr++; } oldbrush=(HPEN)SelectObject(dc,brush); VTYPE_EDGE::iterator kll; for(kll=g.m_edges.begin(); kll<g.m_edges.end(); kll++) { HPEN temp; if((*kll).m_red) temp=(HPEN)SelectObject(dc,penred); MoveToEx(dc, (*kll).m_firstPct.x, (*kll).m_firstPct.y, NULL); LineTo(dc, (*kll).m_secondPct.x, (*kll).m_secondPct.y); Ellipse(dc, (*kll).m_secondPct.x-5, (*kll).m_secondPct.y-5, (*kll).m_secondPct.x+5, (*kll).m_secondPct.y+5); POINT po; po.x = ((*kll).m_firstPct.x+(*kll).m_secondPct.x)/2; po.y = ((*kll).m_firstPct.y+(*kll).m_secondPct.y)/2; char s[5]; ltoa((*kll).m_cost, s, 10); TextOut(dc, po.x, po.y, s, 1); if((*kll).m_red) SelectObject(dc,temp); } ::SelectObject(dc, OldFont); SelectObject(dc,oldpen); SelectObject(dc,oldbrush); DeleteObject(pen); DeleteObject(brush); ::ReleaseDC(m_hWnd, dc); } } void CDijkstra::ReleaseGraph() { g.d.clear(); g.pi.clear(); VTYPE_EDGE::iterator kll; for(kll=g.m_edges.begin(); kll<g.m_edges.end(); kll++) { (*kll).m_red = false; } Refresh(); }