HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- MAI TUẤN CƯỜNG ĐỊNH TUYẾN NAN TRONG MẠNG CHUYỂN MẠCH BURST QUANG Chuyên ngành: Kỹ thuật điện tử Mã số: 60.52.70 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – NĂM 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: PGS.TS BÙI TRUNG HIẾU Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 LỜI NÓI ĐẦU Công nghệ viễn thông trong những năm gần đây đã và đang có những bước phát triển rất mạnh mẽ để đáp ứng nhu cầu sử dụng ngày càng phong phú của người dùng, đặc biệt là sự bùng nổ lưu lượng trong mạng Internet và mạng di động. Với đặc tính truyền dẫn ưu việt, băng thông gần như vô hạn, giá thành rẻ, công nghệ truyền dẫn quang nổi lên như là một công nghệ đầy tiềm năng cho mạng Internet thế hệ sau. Hầu hết mạng lưới truyền dẫn trên thế thới cũng như ở Việt Nam hiện này đều đã được cáp quang hóa. Tuy nhiên, việc sử dụng công nghệ chuyển mạch kênh như hiện tại cho mạng truyền dẫn quang WDM bộc lộ nhược điểm về lãng phí băng thông. Do vậy, gần đây chuyển mạch Burst quang đang nhận được nhiều sự quan tâm, với rất nhiều nghiên cứu về khả năng áp dụng nó vào trong thực tế. Một vấn đề quan trọng trong chuyển mạch Burst quang đó là giải quyết tranh chấp tài nguyên giữa các Burst quang. Với yêu cầu truyền tải một lưu lượng lớn các Burst với cơ sở hạ tầng phần cứng ở mức tối thiểu nhất thì phải có các giải pháp giải quyết tranh chấp xung đột tài nguyên rất hiệu quả. Đã có rất nhiều các giải pháp giải quyết tranh chấp được nghiên cứu và đưa ra trên thế giới. Trên cơ sở đó, luận văn này sẽ đưa ra và trình bày một giải pháp giải quyết tranh chấp tài nguyên cho mạng chuyển mạch Burst quang đó là “ Thuật toán định tuyến NAN (Next Available Neighbour)”. Nội dung luận văn bao gồm 3 chương. Chương 1: Tổng quan về chuyển mạch Burst quang. Chương này sẽ giới thiệu những kiến thức cơ bản về chuyển mạch Burst quang. Chương 2: Các cơ chế chống xung đột Burst quang. Chương này sẽ giới thiệu các cơ chế giải quyết xung đột Burst quang đã được nghiên cứu và đề xuất. Chương 3: Thuật toán định tuyến NAN trong chuyển mạch Burst quang. Chương này sẽ đưa ra và trình bày về cơ chế sử dụng thuật toán định tuyến NAN để giải quyết xung đột trong mạng chuyển mạch Burst quang. 2 Chương 1: TỔNG QUAN VỀ CHUYỂN MẠCH BURST QUANG Chương này sẽ giới thiệu tổng quan mạng truyền dẫn quang, sự phát triển bùng nổ của cáp quang trong viễn thông từ những tuyến truyền dẫn đơn lẻ thành một mạng truyền dẫn quang và đang hướng tới một mạng toàn quang. Trong chương này cũng giới thiệu về ba công nghệ chuyển mạch quang là chuyển mạch gói quang, chuyển mạch kênh quang và sau đó đi sâu vào các đặc điểm, kiến trúc mạng của chuyển mạch Burst quang. 1.1 Sự phát triển của mạng truyền dẫn quang Như chúng ta đều biết công nghệ viễn thông đang thay đổi rất nhanh chóng nhằm đáp ứng nhu cầu ngày càng cao của con người. Với băng thông gần như vô hạn, nguyên liệu chế tạo rẻ, đặc tính truyền dẫn vượt trội, cáp quang đã nhanh chóng được sử dụng rộng khắp trên toàn thế giới không chỉ ở mạng đường trục, mạng lõi mà cả mạng truy nhập. Như vậy, nhu cầu về một hệ thống chuyển mạch quang để nâng cao tốc độ và dung lượng chuyển mạch và hướng đến một mạng toàn quang là tất yếu nhằm đáp ứng nhu cầu về băng thông ngày càng cao hiện nay. 1.2. Các công nghệ chuyển mạch quang Cũng như chuyển mạch điện, chuyển mạch quang cũng có nhiều phương thức, công nghệ khác nhau, trong phần này sẽ giới thiệu ba công nghệ chuyển mạch quang đã và đang được nghiên cứu. 1.2.1.Chuyển mạch kênh quang Trong chuyển mạch kênh quang [2], một kênh quang sẽ được thiết lập giữa một nút nguồn và một nút đích trước khi quá trình truyền dữ liệu bắt đầu và sẽ được duy trì đến khi quá trình truyền dữ liệu kết thúc. 1.2.2.Chuyển mạch gói quang Trong chuyển mạch gói quang [2], thông tin được đóng thành các gói quang và mỗi gói sẽ được gắn một tiều đề (header) chứa thông tin điều khiển. Các gói quang sẽ được định tuyến và chuyển mạch trong miền toàn quang mà không cần phải chuyển sang miền điện tại các nút trung gian. Việc truyền gói tin trong mạng sẽ không cần phải thực hiện thiết lập trước kênh truyền mà gói tin sẽ được gửi ngay vào trong mạng. 3 Khi tới nút trung gian, header của gói tin được tách ra khỏi phần dữ liệu và được xử lý để quyết định cổng đầu ra. 1.2.3.Chuyển mạch Burst quang 1.2.3.1.Giới thiệu chuyển mạch Burst Chuyển mạch Burst quang (Optical Burst Switching: OBS) được thiết kế nhằm kết hợp những ưu điểm của chuyển mạch kênh và chuyển mạch gói. OBS không cần đến bộ đệm quang ở các nút trung gian, trong khi cực tiểu thời gian thiết lập và cực đại hiệu quả sử dụng băng thông kết nối. Hình 1.3: Quá trình báo hiệu và truyền Burst trong mạng chuyển mạch Burst quang 1.2.3.2 Kiến trúc mạng chuyển mạch Burst Mạng chuyển mạch Burst quang bao gồm các nút chuyển mạch Burst quang được liên kết với nhau thông qua các liên kết bằng sợi quang. Các nút trong mạng chuyển mạch Burst quang được chia làm hai loại chính là nút biên và nút lõi. Nút biên có chức năng tách/lập Burst, tạo bản tin điều khiển, định tuyến, gán bước sóng, và báo hiệu. Nút lõi có chức năng chuyển mạch các Burst dữ liệu từ cổng đầu vào tới cổng đầu ra mong muốn dựa trên thông tin từ bản tin điều khiển mà nút biên gửi tới. Ngoài ra nút lõi còn có chức năng giải quyết tranh chấp tài nguyên giữa các Burst nếu nó xảy ra. 4 Hình 1.4: Mạng chuyển mạch Burst quang 1.2.3.3 Thiết lập và tách Burst Quá trình lập Burst được minh họa trong hình 1.7. Đây là quá trình xử lý việc đóng gói từ các gói tin đầu vào thành từng Burst dữ liệu tại các nút biên trong mạng chuyển mạch Burst quang. Hình 1.7: Quá trình lập Burst Hiện tại có hai phương pháp chủ yếu được sử dụng để lập Burst đó là dựa vào thời gian ( Timer Base) và dựa vào mức ngưỡng (Threshold Base) như được mô tả ở hình 1.8 và 1.9. 5 Hình 1.8: Lập Burst dựa trên Timer Base Hình 1.9: Lập Burst dựa trên mức ngưỡng Ngược lại với lập Burst là quá trình tách Burst. Đây là quá trình cũng được thực hiện tại các nút biên đích, tại đây Burst được chuyển sang miền điện và lưu trong các bộ đệm trước khi được tách ra thành các gói tin IP ( ATM, SONET..) như ban đầu khi nó được đưa vào mạng OBS. Việc tách Burst cần có các thông tin ở quá trình lập Burst ban đầu để đảm bảo các gói tin được tách ra chính xác như lúc được ghép ở đầu vào. Quá trình tách Burst được minh họa ở Hình 1.10. Gói tin điều khiển Nút biên đích IP (ATM hoặc Ethernet) 1 2 3 Kênh điều khiển IP (ATM hoặc Ethernet) Burst 1 Burst 2 Burst 3 Kênh dữ liệu Hình 1.10: Quá trình tách Burst 1.3 Báo hiệu trong chuyển mạch Burst quang 1.3.1.Tổng quát về báo hiệu trong chuyển mạch Burst Hệ thống báo hiệu đóng vai trò vô cùng quan trọng trong các mạng viễn thông nói chung cũng như mạng OBS nói riêng. Nó thực hiện chức năng chuyển thông tin 6 liên quan đến thiết lập, giám sát và giải phóng cuộc gọi từ điểm này đến điểm khác hay từ nút mạng này đến nút mạng khác. 1.3.2.Một số loại giao thức báo hiệu điển hình trong chuyển mạch Burst Trong phần này sẽ giới thiệu bốn giao thức báo hiệu cơ bản trong mạng chuyển mạch Burst . 1.3.2.1.Giao thức báo hiệu Tell and Go (TAG) 1.3.2.2. Giao thức báo hiệu Tell-and-Wait (TAW) 1.3.2.3.Giao thức báo hiệu Just-In-Time (JIT). 1.3.2.4.Giao thức báo hiệu Just Enough Time (JET). 1.4.Kết luận chương Chương này đã giới thiệu một cách cơ bản và so sánh một số tính chất nổi bật của ba công nghệ chuyển mạch quang là chuyển mạch kênh, gói và Burst. Sau đó là phần đi sâu vào trình bày các đặc điểm của chuyển mạch Burst, kiến trúc mạng và nút của mạng OBS để người đọc có những kiến thức cơ bản về OBS. Phần cuối của chương trình bày khá chi tiết về các loại báo hiệu trong OBS để làm tiền đề cho chương 2 khi đi sâu vào phân tích các giải pháp giải quyết xung đột Burst quang. 7 Chương 2: CÁC GIẢI PHÁP CHỐNG XUNG ĐỘT BURST QUANG Để giải quyết xung đột Burst, có 4 phương pháp cơ bản thường được thực hiện, đó là: đệm bằng bộ trễ quang, chuyển đổi bước sóng, phân đoạn Burst và định tuyến lệch hướng. 2.1.Giải pháp sử dụng bộ đệm quang Một phương pháp đơn giản nhất để giải quyết sự xung đột tài nguyên nói chung trong viễn thông là sử dụng bộ đệm. Với phương thức này, tín hiệu quang sẽ được cho chạy qua một đoạn sợi quang có chiều dài xác định để làm trễ tín hiệu trong một khoảng thời gian xác định. 2.2.Giải pháp chuyển đổi bước sóng Trong WDM, nhiều bước sóng được ghép cùng lúc trên một liên kết kết nối hai chuyển mạch quang. Nhiều bước sóng có thể giảm tối thiểu số lượng xung đột. Giả sử rằng có hai burst đều đi đến một đích và ra ở cùng ngõ ra tại cùng thời điểm. Khi đó nếu có hai bước sóng khác nhau ở cùng trên cổng đầu ra đó thì hai burst vẫn có thể truyền đi tiếp đến nút đích. 2.3.Giải pháp phân mảnh Burst Một cách tiếp cận khác khi giải quyết tranh chấp tài nguyên trong mạng chuyển mạch Burst đó là phân nhỏ Burst thành từng mảnh khi có tranh chấp và chỉ loại bỏ các mảnh chồng lấn khi xung đột [3]. Như vậy độ phức tạp của mạng sẽ tăng lên nhưng đổi lại việc mất dữ liệu khi xung đột xảy ra sẽ được giảm bớt do thay vì phải hủy cả Burst thì giờ chỉ phải hủy một vài mảnh nhỏ của Burst có chống lấn với nhau. 2.4.Giải pháp định tuyến lệch hướng Trong định tuyến lệch hướng, xung đột Burst được giải quyết bằng cách định tuyến Burst dữ liệu sang một cổng đầu ra khác mà nó vẫn có thể đi đến được đích. Quá trình thực hiện định tuyến lệch hướng được mô tả qua các bước sau: Bước 1: Nút nguồn truyền đi một gói điều khiển. Bước 2: Nút trung gian xử lí gói điều khiển và cố gắng đăng ký trước một kênh đầu ra phù hợp cho burst theo thông tin trong bản tin điều khiển. Bước 3: Nút nguồn truyền đi burst sau một khoảng thời gian lệch (offset). 8 Bước 4: Nếu tại nút trung gian đăng ký được kênh đầu ra phù hợp cho Burst tức là mạng không bị nghẽn (đối với Burst đang được đăng ký) thì khi Burst đến nó sẽ chuyển Burst sang khối thực hiện lập lịch để gán Burst lên kênh đầu ra và đi đến đích. Nếu không đăng ký được thì chuyển sang bước 5. Bước 5: Nút trung gian không đăng ký được kênh đầu ra theo yêu cầu của Burst đến nên nó sẽ chuyển Burst sang xử lý định tuyến lệch hướng. Đầu tiên nó sẽ kiểm tra Burst sắp đến đã phải áp dụng định tuyến lệch hướng quá số lần qui định Ndmax chưa. Nếu đúng thì Burst đó sẽ bị hủy, nếu không chuyển bước 6. Bước 6: Nút trung gian căn cứ vào thông tin địa chỉ đích của Burst để tìm tuyến đường lệch hướng mới phù hợp. Nếu tìm được nó sẽ chuyển Burst sang tuyến mới vừa tìm được, nếu không nó sẽ hủy Burst. Hình 2.5: Lưu đồ định tuyến lệch hướng 9 2.5. Định tuyến lệch hướng kết hợp với phân mảnh Burst. Để nâng cao hiệu quả giải quyết xung đột Burst chúng ta có thể kết hợp hai giải pháp định tuyến lệch hướng và phân mảnh Burst [3]. Khi đó thay vì hủy một hay nhiều mảnh của Burst bị xung đột, ta sẽ dịnh tuyến các mảnh đó sang một tuyến khác mà có thể định tuyến tiếp tục nó đến đích. Việc kết hợp giữa phân mảnh Burst và định tuyến lệch hướng làm tăng khả năng Burst đến được đích do đó làm tăng hiệu suất của mạng. 2.6.Kết luận chương Các giải pháp giải quyết xung đột tài nguyên trong mạng chuyển mạch Burst quang có ảnh hưởng lớn đến chất lượng của mạng. Việc áp dụng các giải pháp khác nhau với mức độ khác nhau có thể giúp đơn vị cung cấp dịch vụ đưa ra được các loại dịch vụ với chất lượng dịch vụ khác nhau (QoS). Chương này đã giới thiệu năm giải pháp cơ bản đã được nghiên cứu và đề xuất để giải quyết xung đột Burst làm tiền đề cho việc đề xuất một giải pháp mới được giới thiệu ở chương 3. 10 Chương 3: THUẬT TOÁN ĐỊNH TUYẾN NAN (Next Available Neighbour) Trong chương này sẽ giới thiệu một thuật toán định tuyến khá mới là NAN (Next Available Neighbour) được đề xuất sử dụng trong mạng chuyển mạch Burst để giải quyết xung đột Burst quang. 3.1.Định tuyến NAN (Next Available Neighbour) Trong trường hợp xảy ra quá tải, việc tranh chấp tài nguyên dẫn đến mất Burst là không tránh khỏi, nhưng vấn đề là làm sao để Burst không bị hủy mà sẽ được chèn lại vào mạng ngay sau khi tài nguyên mạng được giải phóng. Từ ý tưởng trên một thuật toán định tuyến mới được đề xuất để xử lý việc xung đột Burst khi tài nguyên mạng bị quá tải. Theo đó khi xung đột Burst xảy ra tại một nút trung gian nào đó, thay vì hủy Burst nó sẽ gửi Burst đến một nút khác gần đích nhất có thể để tiếp tục đi đến đích và nếu không có nút nào phù hợp Burst sẽ được lưu và chèn lại vào mạng sau khi tài nguyên được giải phóng [7]. Thuật toán này là một giải pháp bổ sung cho các giải pháp giải quyết xung đột tài nguyên của Burst và được gọi là định tuyến NAN ( Next Available Neighbour Routing). Thuật toán định tuyến NAN được đề xuất để giải quyết xung đột trong mạng chuyển mạch Burst quang nhưng nó cũng có thể được ứng dụng trong nhiều loại mạng khác nhau như IP/MPLS, OPS. Đối với mạng OBS, định tuyến NAN hoạt động như sau: Khi một nút lõi của mạng OBS nhận được một bản tin điều khiển (CP) yêu cầu đặt trước tài nguyên cho một Burst sắp đến, nếu không tìm được tài nguyên phù hợp theo yêu cầu thì thay vì gửi bản tin từ chối (NACK) trở lại nút nguồn nó sẽ tìm các nút khác bên cạnh có tài nguyên phù hợp và tạo một bản tin NAN-CP để gửi đến nút đó nhờ tiếp nhận Burst. Nút bên cạnh có tài nguyên phù hợp này được gọi là nút NAN. Khi Burst được truyền đến nút lõi nó sẽ định tuyến Burst sang nút NAN. Do có tài nguyên phù hợp nhất và đã được báo trước qua bản tin điều khiển NAN-CP nên nút NAN sẽ tiếp nhận Burst đến và tiếp tục định tuyến Burst đó đến đích. Trong trường hợp xấu nhất là nút NAN đó cũng xảy ra xung đột thì nó cũng sẽ không hủy Burst mà chuyển đổi O/E, lưu nó trong bộ đệm và sẽ chèn lại Burst vào mạng ngay sau khi tài nguyên được giải phóng. 11 Cũng tương tự như trong định tuyến lệch đường ( Deflection routing), trong định tuyến NAN cũng phải sử dụng một bộ đếm hoặc một phương pháp nào đó để tính được thời gian mà Burst đã được đưa vào quá trình định tuyến NAN. Khi tính được thông tin này của Burst ta sẽ tránh được việc Burst sẽ bị chèn đi chèn lại liên tục vào trong mạng mà vẫn không đến được đích hoặc Burst sẽ bị lặp vòng trong mạng bằng cách tính toán và đặt ra một ngưỡng thời gian Burst được thực hiện định tuyến NAN, nếu quá thời gian này mà vẫn chưa đến được đích thì nó sẽ bị hủy. Trong thuật toán định tuyến NAN thì việc quan trọng nhất là tìm được nút bên cạnh có tài nguyên phù hợp nhất để tiếp tục định tuyến Burst đến đích. Để đảm bảo nút bên cạnh là tối ưu nhất sẽ phải dựa trên việc kết hợp một số giá trị như : nút có vị trí gần nút đích nhất, nút có băng thông rộng nhất đến nút đích, nút có thời gian bận ít nhất .v.v. Thực hiện kết hợp các thông tin trên sẽ làm tăng độ phức tạp của mạng lên đáng kể do sẽ phải thêm các modul xử lý, rồi tăng thời gian trễ của gói tin nhưng bù lại xác suất mất Burst sẽ giảm đáng kể. Trong một số trường hợp cụ thể việc lựa chọn nút bên cạnh có thể được thực hiện theo một quá trình ngẫu nhiên để giảm thiểu sự phức tạp của hệ thống. Hình 3.1 : Định tuyến NAN trong mạng OBS Hình 3.1 mô tả quá trình định tuyến NAN trong mạng OBS, khi nút 2 và nút 3 định tuyến một Burst tới nút 6 tại cùng một thời điểm nhưng lại cùng sử dụng đường link từ nút 5 đến nút 6. Như vậy nếu bình thường không áp dụng các giải pháp giải 12 quyết tranh chấp thì nút 5 sẽ hủy một Burst và chỉ cho 1 Burst định tuyến qua nút 5 đến nút 6. Nhưng khi sử dụng định tuyến NAN để giải quyết tranh chấp thì quá trình sẽ diễn ra như sau: Khi nút 5 nhận được yêu cầu thiết lập cấu hình chuyển mạch tại cùng một thời điểm cho Burst 2 và Burst 3 cùng đến nút 6 qua đường link 5-6, nó sẽ thực hiện cấu hình trường chuyển mạch để cho 1 Burst (ở đây là Burst 2) chuyển đến nút 6, đồng thời nó cũng sẽ lập một bản tin NAN CP để gửi đến nút 4 là nút bên cạnh gần nhất có tài nguyên phù hợp để định tuyến Burst 3 qua nút 4 đến nút 6. Tuy nhiên nếu nút 4 cũng xảy ra tranh chấp khi Burst 3 truyền đến thì nó sẽ lưu Burst 3 vào bộ đệm và sẽ chèn lại vào mạng ngay sau khi tài nguyên được giải phóng. Trong trường hợp ở trên, nút 4 đóng vai trò là nút NAN nhưng không mang tính chất cố định, mà bất cứ nút nào trong mạng OBS cũng có thể là nút NAN nếu tại một thời điểm nào đó nó có tài nguyên phù hợp và nhận được yêu cầu định tuyến “hộ” cho các nút bên cạnh đang bị xung đột tài nguyên. Do đó trong một trường hợp khác, khi nút 4 xảy ra tranh chấp tài nguyên nó cũng có thể gửi một bản tin NAN CP sang nút 5 để nhờ định tuyến “hộ” và lúc này nút 5 lại đóng vai trò một nút NAN. Khi thực hiện định tuyến NAN, Burst sẽ bị trễ đi một khoảng thời gian do phải đi vòng sang đường khác và có thể phải lưu trong bộ đệm điện. Tuy nhiên nếu so với trễ của việc phải truyền lại Burst từ đầu thì nó vẫn nhỏ hơn nhiều. Sau đây ta sẽ xét thời gian trễ của cả hai trường hợp khi không sử dụng và khi sử dụng định tuyến NAN. Trường hợp thứ nhất, giả sử trong mạng OBS có một Burst sau khi đã truyền qua k nút trung gian đến một nút trung gian tiếp theo thì xảy ra xung đột tài nguyên và nó bị hủy. Nút trung gian thực hiện hủy Burst sẽ gửi bản tin NACK quay trở lại nút biên đầu vào để yêu cầu phát lại Burst. Sau khi nhận được bản tin NACK từ nút trung gian, nút biên sẽ xử lý và lập bản tin điều khiển mới và chuyển đổi E/O Burst lưu trong bộ đệm điện để truyền lại vào mạng sau khi truyền bản tin điều khiển. Giả sử sau khi truyền lại thì Burst trên đến được đích, khi đó tổng thời gian trễ của cả quá trình từ lúc Burst bị hủy đến lúc Burst được truyền lại và đến được đích sẽ là: TD1 = TNACK + hTCP + TE/O + TS-D Trong đó: 13 TD1 : Là thời gian trễ của Burst từ lúc bị hủy đến lúc truyền lại và đến được đích TNACK : Thời gian truyền bản tin NACK qua k nút về nút nguồn TNACK = kTCP + TNAN-S kTCP: Thời gian xử lý bản tin NACK tại k nút TNAN-S: Thời gian truyền bản tin NACK trên đường truyền qua k nút h.TCP : Thời gian lệch (offset time) khi truyền lại Burst TE/O : Thời gian chuyển Burst từ miền điện sang miền quang TS-D : Thời gian truyền lại Burst từ nút nguồn đến nút đích Như vậy ta có: TD1 = (h + k)TCP + TNAN-S + TE/O + TS-D Trong trường hợp thứ hai, tại nút trung gian xảy ra xung đột tài nguyên áp dụng phương pháp định tuyến NAN để giải quyết tranh chấp thì nó sẽ định tuyến Burst xung đột sang một nút bên cạnh để tiếp tục định tuyến nó đến đích. Giả sử trong trường hợp xấu nhất nút bên cạnh cũng bận nó sẽ lưu Burst vào bộ đệm rồi chèn lại vào mạng ngay sau đó để định tuyến nó đến đích khi tài nguyên đã giải phóng. Khi đó tổng thời gian trễ của Burst khi đến đích sẽ là: TD2 = nTNAN + TO/E/O + TNAN-D Trong đó: TD2: Là thời gian trễ từ lúc được định tuyến NAN đến lúc đến được đích nTNAN : Thời gian xử lý bản tin điều khiển qua n nút từ nút NAN đến nút đích TO/E/O : Thời gian trễ chuyển đổi qua bộ đệm điện. TNAN-D : Thời gian truyền Burst từ nút NAN đến nút đích. Ta thấy rằng với TCP ≈ TNAN ≈ TO/E trong khi đó h+k > n, TS-D > TNAN-D thì TD2 < TD1 , còn trong trường hợp nút NAN gần đích thì h+k >> n và TS-D + TNAN-S >> TNAN-D thì TD2 << TD1 tức là ở trường hợp nào thì trễ gây ra do việc định tuyến NAN cũng nhỏ hơn so với việc truyền lại Burst từ nút nguồn. Tuy nhiên đây không phải là 14 mục tiêu chính của định tuyến NAN mà mục đích quan trọng nhất của nó là giải quyết xung đột tài nguyên trong mang OBS một cách triệt để và hiệu quả. Chúng ta có thể dễ dàng nhận thấy rằng so với định tuyến lệch đường (Deflection routing) thì định tuyến NAN là sự tiếp nối và giải quyết triệt để vấn đề mà định tuyến lệch hướng không giải quyết được. Đổi lại chúng ta phải bổ sung bộ nhớ cho các nút chuyển mạch Burst và nâng cao khả năng xử lý của các nút mạng. Một vấn đề nữa cần lưu ý trong việc thực hiện định tuyến NAN là thời gian lệch Offset times. Do thời điểm Burst được truyền vào mạng chưa dự tính được sẽ có xung đột tài nguyên ở đâu và khi nào nên thời gian offset times chỉ được dự tính vừa đủ để đi đến đích mà không tính những lúc mà có thể có xung đột xảy ra và Burst sẽ phải định tuyến theo hướng khác. Nếu không chỉnh lại được thời gian này thì đến thời điểm nào đó khi bản tin điều khiển đến một nút nhưng chưa kịp xử lý xong và trường chuyển mạch cũng chưa sẵn sàng để truyền Burst mà Burst đã được truyền tới. Trong trường hợp này Burst sẽ bị hủy vì chưa kịp cấu hình đầu ra cho Burst. Trong định tuyến lệch hướng để xử lý thời gian lệch offset times không đủ thì sẽ phải bổ sung bộ trễ quang (FDL) tại các nút mạng, nếu các Burst được định tuyến lệch hướng thì sẽ phải được định tuyến chạy qua các bộ trễ quang để bù thời gian trễ do đi theo hướng khác xa hơn. Tuy nhiên trong định tuyến NAN, do đã có các bộ đệm điện tại mỗi nút nên khi cần bù thời gian trễ này các Burst sẽ được lưu vào trong bộ đệm điện. Qua việc trình bày về định tuyến NAN ở trên ta có thể thấy một số ưu điểm của định tuyến NAN trong mạng OBS như sau: - Giải quyết được triệt để hơn vấn đề xung đột tài nguyên trong mạng OBS - Do các Burst có thể được lưu tại các nút trung gian rồi được truyền tiếp đến đích nên việc truyền Burst từ nguồn tới đích có thể chia thành một vài chặng nhỏ hơn và việc tìm đường cho từng chặng nhỏ cũng dễ dàng hơn, dẫn đến tỷ lệ mất Burst giảm đáng kể. - Burst có thể được lưu đệm tại các nút một thời gian cũng làm cho việc điều tiết lưu lượng mạng và xử lý tranh chấp tài nguyên của các nút được chủ động và mềm dẻo hơn. 15 3.2. Xây dựng lưu đồ giải thuật cho định tuyến NAN 3.2.1.Quá trình truyền Burst qua mạng sử dụng định tuyến NAN để tránh xung đột. Trong mạng OBS khi một nút nguồn muốn gửi đi một Burst trước tiên nó phải gửi một bản tin điều khiển để đăng ký trước tài nguyên. Trong bản tin điều khiển sẽ chứa các thông tin cần thiết cho việc đăng ký bước sóng cho Burst như: Địa chỉ nút đích, bước sóng truyền, độ dài Burst, tốc độ truyền Burst. Tại nút trung gian, khi nhận được bản tin điều khiển từ nút nguồn gửi tới nó sẽ tiến hành đọc thông tin trong bản tin điều khiển và xem có thể đáp ứng yêu cầu truyền Burst sắp đến không. Để làm được việc này, nút trung gian sẽ áp dụng các giải thuật lập lịch để gán Burst vào một kênh dữ liệu liên kết đầu ra phù hợp. Dựa vào thông tin được cung cấp trong bản tin điều khiển, bộ lập lịch kênh biết được thời gian đến và thời gian kết thúc của Burst. Cùng với đó, bộ lập lịch luôn được cập nhật thông tin về thời điểm chưa lập lịch khả dụng muộn nhất (LAUT), các khoảng trễ (gap) và các khoảng trống (Void) trên mỗi kênh dữ liệu đầu ra. Căn cứ vào các thông số này và các giải thuật lập lịch được áp dụng nút trung gian sẽ biết được có bước sóng nào phù hợp với Burst sắp được truyền tới hay không. Các giải thuật lập lịch được áp dụng phải đáp ứng được yêu cầu lập lịch được càng nhiều Burst càng tốt trên cùng một kênh bước sóng đầu ra nhằm tối ưu hóa lưu lượng và giảm tổn thất Burst. Nếu không tìm được tài nguyên bước sóng phù hợp cho Burst, tức là không thực hiện được việc lập lịch thì mạng ở trạng thái bị xung đột tài nguyên hay bị nghẽn, lúc này nút trung gian sẽ chuyển Burst sang khối xử lý định tuyến NAN. A. Khối lập lịch kênh, tìm kênh bước sóng đầu ra phù hợp cho Burst. Để thực hiện các giải thuật về lập lịch Burst, khối xử lý cần phải có các thông số sau: Chiều dài burst: Lb BR: Tốc độ bít Trên tuyến đầu vào có F sợi quang được ký hiệu là f, khi đó f = 1,2,3…F. Trên mỗi sợi quang đều có W bước sóng giống nhau (λo, λ1, λ2…. λ W-1). Burst cần được lập lịch được truyền trên bước sóng λi và có thời điểm đến là t. 16 LAUTi là thời điểm chưa lập lịch khả dụng muộn nhất của kênh bước sóng thứ i trên mỗi sợi quang F trong khoảng thời gian xử lý . Si,j và Ei,j là các thời điểm bắt đầu và kết thúc của burst dữ liệu đã được lập lịch thứ j trên kênh bước sóng thứ i, cho các giải thuật điền khoảng trống. Gapi: là sự sai khác về thời gian giữa t và LAUTi đối với các thuật toán không điền khoảng trống và là sự sai khác về thời gian giữa t và Ei,j của burst được lập lịch trước đó với các thuật toán điền khoảng trống. Nếu t = Ei,j hoặc t= LAUTi, thì Gapi = 0 tức là ở thời điểm đó kênh truyền bận đối với Burst cần lập lịch tại thời điểm t. Thông tin về khoảng trễ “gap” là hữu ích để lựa chọn một kênh bước sóng thích hợp trong trường hợp có nhiều hơn một kênh rỗi. * Giải thuật FFUC Đây là giải thuật thuộc loại không điền khoảng trống. Thuật toán FFUC lưu giữ thời điểm chưa lập lịch muộn nhất (LAUT) của tất cả các kênh bước sóng trên tất cả các sợi quang f đầu ra. Khi nhận được bản tin điều khiển yêu cầu lập lịch cho Burst được gửi đến trên kênh bước sóng λi, giải thuật FFUC sẽ tìm kiếm tất cả các sợi quang f theo thứ tự và chọn kênh bước sóng λi khả dụng đầu tiên để lập lịch cho Burst [3]. Hình 3.2: Giải thuật FFUC và LAUC 17 * Giải thuật LAUC Thuật toán LAUC về cơ bản thực hiện tương tự như thuật toán FFUC, nó cũng duy trì giá trị của LAUT trên tất cả các kênh bước sóng nhưng trong quá trình tìm kiếm kênh bước sóng thích hợp thay vì sắp xếp burst dữ liệu trên kênh bước sóng thích hợp đầu tiên tìm được, giải thuật này lựa chọn kênh có LAUT gần với thời điểm đến của burst dữ liệu nhất. Giải thuật LAUC cũng được mô tả trên hình 3.2. Trên các sợi quang f1 và f2 đều có kênh bước sóng phù hợp vì thời điểm Burst đến nằm sau các LAUT của bước sóng λi trên hai sợi quang này. Nếu như thuật toán FFUC được sử dụng thì kênh sợi quang f1 được lựa chọn. Tuy nhiên, với thuật toán LAUC còn quan tâm đến khoảng thời gian giữa t và LAUT của mỗi kênh bước sóng, nó sẽ chọn kênh nào có khoảng thời gian này nhỏ nhất; điều này làm tăng hiệu quả sử dụng kênh truyền so với FFUC [3]. Chúng ta thấy rằng Gap 1 > Gap 2 do đó burst sẽ được sắp xếp trên kênh f2. Giải thuật cho LAUC được mô tả như sau: Bước 1: Khởi tạo kênh f = 1, gapmin = 100s, Cn = 0 (Cn là biến số lưu chỉ số của sợi quang f được chọn để lập lịch cho Burst đến thứ n); Bước 2: Cho f chạy từ 1 đến F để tìm giá trị LAUTi của bước sóng λi lần lượt trên các sợi quang đầu ra, bắt đầu từ sợi quang f=0 . Tại kênh bước sóng λi của mỗi sợi quang f tiến hành kiểm tra giá trị LAUTi so với thời điểm đến t của Burst cần được lập lịch. Nếu LAUTi < t, tức gapi = t - LAUTi >0 chuyển sang bước 3. Nếu không lặp lại quá trình với sợi quang f +1 cho đến khi f = F+1 thì chuyển bước 4. Bước 3: So sánh gapi với gapmin. Nếu gapmin > gapi, thì gán gapmin = gapi , gán Cn = f và quay lại bước 2 để tìm tiếp kênh khác. Ngược lại thì giữ nguyên các thông số khác và quay lại bước 2 với f = f +1. Bước 4: Khi f = F+1 quá trình tìm kiếm kết thúc, kiểm tra chỉ số Cn. Nếu Cn =0 tức không tìm thấy kênh bước sóng λi nào trên tất cả các sợi quang f phù hợp cho Burst sắp đến và khi đó sẽ chuyển Burst sang khối xử lý định tuyến NAN. Nếu Cn = f , tức đã tìm được kênh λi trên sợi quang f = Cn có tài nguyên phù hợp để lập lịch cho Burst và đây là kênh có gap nhỏ nhất. 18 f=1 Cn = 0 LAUC Gapmin = 100 s Đúng f = F+1 ? Sai Sai f = f +1 Gap i > 0 ? Đúng Sai f = f +1 Gapmin > Gap i ? Đúng Ghi chú: Gap i = t - LAUT i f = f +1 Cn = f Gapmin = Gap i Đúng Chuyển Burst Cn = 0 ? sang định tuyến NAN sai λi thuộc sợi quang f = Cn là kênh được chọn để lập lịch cho Burst Hình 3.3: Lưu đồ giải thuật cho LAUC * Giải thuật FFUC-VF Đây là giải thuật thuộc loại điền khoảng trống, thay vì lưu giữ giá trị LAUT bộ lập lịch sẽ lưu thời điểm bắt đầu Sij và kết thúc Eij của mỗi Burst đã được lập lịch trên mọi kênh bước sóng của các sợi quang đầu ra. Khi có bản tin điều khiển đến yêu cầu lập lịch cho Burst được truyền đến trên kênh bước sóng λi, giải thuật FFUC-VF sẽ căn cứ vào các giá trị Sij, Eij của các Burst đã được lập lịch của kênh bước sóng λi trên tất cả các sợi quang đầu ra và giá trị bắt đầu SB, kết thúc EB của Burst cần lập lịch để tìm