Chuyên đề Những vấn đề cơ bản về chuyển mạch BURST quang

ra tương ứng. Tại các node lõi sẽ chỉ có trách nhiệm chuyển tiếp gói tin đi nhờ xử lý các thông tin báo hiệu và lập lịch. Tại node biên đầu ra sẽ burst sẽ được giải tổ hợp và phân phối đến địa chỉ.Trong mạng OBS xử dụng các giao thức định tuyến OSPF và GMPLS. Có thể thấy tuyến đã được lựa chọn tại node biên, các node đích chỉ việc chuyển tiếp. Nếu đi thêm về các giao thức trên thì chuyên đề sẽ quá dài và không tập trung vào đặc điểm riêng chính của OBS nên nhóm sẽ không trình bày cụ thể về các giao thức định tuyến trên. Mục tiếp theo sẽ đề cập đến quá trình tổ hợp burst là một trong những đặc điểm nổi bật của OBS. 2.2 Tổ hợp burst Tổ hợp burst là tiến trình tập hợp và đóng các gói ở router nút biên đầu vào từ các lớp cao hơn thành các burst để truyền tải vào mạng OBS. Khi các gói tin đi đến từ lớp cao hơn, chúng được lưu đệm trong các bộ nhớ đệm điện và được phân loại theo địa chỉ và loại dịch vụ. Việc tổ hợp burst sẽ quyết định khi nào tạo ra một burst và gửi burst đó vào mạng OBS. Hai phương pháp tổ hợp burst phổ biến nhất là tổ hợp burst dựa trên bộ định thời và tổ hợp burst dựa trên mức ngưỡng. 2.2.1 Tổ hợp burst dựa trên bộ định thời Như đã trình bày trong phần 2.1.1, các router biên có cấu tạo gồm có bộ định tuyến, các bộ tổ hợp burst và các bộ lập lịch kênh. Khi các gói tin đến router biên, bộ định tuyến sẽ căn cứ vào địa chỉ đích của các gói tin để chuyển các gói tin này đến bộ tổ hợp burst thích hợp. Các gói tin này sẽ được lưu đệm tạm thời trong các hàng đợi khác nhau nằm trong bộ tổ hợp burst. Trong phương pháp tổ hợp burst dựa trên bộ định thời, mỗi bộ tổ hợp burt sẽ tham chiếu thời gian của một bộ định thời cục bộ nằm trên một hàng đợi để quyết định việc tổ hợp các gói tin thành các burst. Thời điểm bộ định thời bắt đầu đếm thời gian có thể là ngay sau khi một burst trước đó được lập lịch để truyền đi hoặc ngay sau khi gói tin đầu tiên đến hàng đợi sau khi hàng đợi trống. Sau một khoảng thời gian T được cấu hình từ trước, các gói tin trong hàng đợi đó sẽ được tổ hợp thành một burst và lập lịch để truyền đi. Phương pháp tổ hợp burst này sẽ tạo ra các burst có chiều dài ngẫu nhiên. Lưu lượng vào mạng thay đổi phần lớn sẽ quyết định chiều dài của burst. Lưu lượng vào mạng lớn, burst sẽ có kích thước lớn, lưu lượng vào mạng nhỏ, burst sẽ có kích thước nhỏ. Tuy nhiên, thời gian của bộ định thời cũng là một nhân tố quyết định kích thước các burst. Hình 2.5: Tổ hợp burst dựa trên bộ định thời 2.2.2 Tổ hợp burst dựa trên mức ngưỡng Trong phương pháp tổ hợp burst dựa trên mức ngưỡng, số lượng các burst bị giới hạn hay chiều dài của các burst là bằng nhau. Cụ thể là khi khi kích thước của các gói tin trong hàng đợi đạt đến một giá trị ngưỡng L, các gói tin được tổ hợp thành burst và lập lịch để truyền đi. Phương pháp tổ hợp burst này không đảm bảo về thời gian trễ tổ hợp burst. Hình 2.6: Tổ hợp burst dựa trên mức ngưỡng Một vấn đề đặt ra cho việc tổ hợp burst là làm sao tìm ra giá trị của bộ định thời và kích thước ngưỡng để tối thiểu hóa xác suất mất gói trong mạng OBS. Nếu như mức ngưỡng quá thấp dẫn đến kích thước burst nhỏ, số lượng burst truyền trong mạng sẽ nhiều dẫn đến xác suất xảy ra xung đột ở các router lõi cao, nhưng số lượng gói trung bình bị mất do xung đột lại nhỏ. Tuy nhiên, số lượng burst nhiều sẽ làm tăng áp lực lên mặt bằng điều khiển do phải xử lý nhiều các gói tin điều khiển của mỗi burst dữ liệu. Nếu thời gian cấu hình cho mỗi nút chuyển mạch không được bỏ qua, các burst ngắn sẽ khiến cho việc sử dụng tài nguyên một cách kém hiệu quả do phải mất nhiều thời gian chuyển mạch. Ngược lại, khi mức ngưỡng lớn dẫn đến kích thước burt lớn, số lượng burst vào mạng sẽ nhỏ, do đó xác suất xảy ra xung đột sẽ nhỏ nhưng số lượng gói trung bình bị mất do xung đột sẽ lớn. Vì thế, cần có một sự cân bằng giữa số lượng xung đột và số lượng gói mất trung bình tại mỗi lần xung đột. Do đó, hoạt động của mạng OBS sẽ được cải thiện khi các gói đến được tổ hợp thành burst với một kích thước tối ưu. Tương tự, phương pháp tổ hợp burst dựa trên bộ định thời cũng cần giá trị tối ưu về mặt thời gian. Việc lựa chọn phương pháp tổ hợp burst tùy thuộc vào loại lưu lượng được truyền đi. Phương pháp tổ hợp burst dựa trên bộ định thời thích hợp với các lưu lượng bị giới hạn về mặt thời gian như các dịch vụ thời gian thực như thoại, truyền tải video vì thời gian trễ tổ hợp burst bị giới hạn. Nếu không có giới hạn về độ trễ, phương pháp tổ hợp burst dựa trên mức ngưỡng phù hợp cho các dịch vụ không yêu cầu thời gian thực như truyền số liệu, và cho phép điều khiển được số lượng gói bị mất trong mỗi lần xung đột. Việc sử dụng cả hai loại phương pháp dựa trên bộ định thời và dựa trên mức ngưỡng là lựa chọn tốt nhất và việc tổ hợp burst sẽ linh hoạt hơn là chỉ dùng một trong hai phương pháp kể trên. Bằng cách tính toán giá trị mức ngưỡng tối ưu và sử dụng giá trị của bộ định thời dựa trên độ trễ gói cho phép, ta có thể chắc rằng số lượng mất gói là nhỏ nhất trong khi vẫn đảm bảo độ trễ cho phép. Sau khi một burst được tạo ra sử dụng các phương pháp được nói ở trên, burt được lưu đệm trong hàng đợi trong một khoảng thời gian trước khi truyền đi sao cho gói tin điều khiển của burst đó có đủ thời gian để dự trữ tài nguyên. Trong thời gian này, các gói tin khác có thể tiếp tục đến router nút biên. Việc thêm các gói tin này vào burst là không chấp nhận được vì tài nguyên cho burst lúc đầu được dự trữ căn cứ vào chiều dài của burst có trong gói tin điều khiển. Để các gói tin này cho các burst ở đằng sau có khả năng tăng trễ trung bình trong trường hợp lưu lượng lớn. Trong [4], theo Yang Chen, Chunming Quiao và Xiang Yu, một cách để giảm thiểu trễ là thực hiện dự đoán chiều dài burst: Gói tin điều khiển sẽ mang thông tin về chiều dài burst là L + f(t) thay vì là L với L là chiều dài chính xác của burst khi gói tin điều khiển được gửi đi, f(t) là chiều dài dự đoán của các gói tin đi đến trong khoảng thời gian offset và được tính toán dựa trên tốc độ trung bình của lưu lượng tới. Giả sử chiều dài thực sự của các gói tin đi đến là l(t). Nếu f(t) > l(t), chiều dài của burst khi truyền vào nút lõi là L + l(t), tài nguyên dự trữ cho burst sẽ bị lãng phí. Nếu f(t) < l(t), chiều dài của burst khi truyền vào nút lõi là L + f(t). Một phần gói tin có chiều dài l(t) – f(t) sẽ được ghép vào để truyền trên các burst phía sau. Nếu f(t) = l(t) là trường hợp lý tưởng nhất khi đó việc dự trữ tài nguyên cho burst sẽ là tối ưu và không tăng trễ. 2.3 Các cơ chế báo hiệu Khi burst được truyền vào mạng lõi OBS, một cơ chế báo hiệu phải được thực hiện nhằm mục đích phân bổ tài nguyên và cấu hình trường chuyển mạch cho từng burst tại mỗi nút thông qua các gói tin tiêu đề burst BHP hay gói tin điều khiển. OBS sử dụng báo hiệu ngoài băng: Gói tin BHP được truyền trên một bước sóng khác với burst dữ liệu. Tuy nhiên, BHP được truyền trên cùng một đường đi từ nguồn tới đích như burst dữ liệu để thông báo cho các nút chuyển mạch dự trữ tài nguyên và cấu hình trường chuyển mạch cho burst dữ liệu tương ứng. Dưới đây ta xét bốn cơ chế báo hiệu cơ bản trong OBS là Just – Enough – Time, Just – In – Time, Tell – And – Go và Tell – And – Wait. Trong đó ba cơ chế báo hiệu đầu là ba cơ chế báo hiệu một chiều: Nút nguồn gửi gói tin điều khiển để dự trữ tài nguyên và thực hiện truyền burst dữ liệu mà không cần đợi nút đích thông báo việc dự trữ tài nguyên từ nguồn tới đích có thành công hay không. Cơ chế báo hiệu Tell – And – Wait là cơ chế báo hiệu hai chiều: nút nguồn sẽ chỉ truyền burst dữ liệu khi được xác nhận kênh truyền đã được thiết lập hoàn toàn từ nguồn tới đích. 2.3.1 Cơ chế báo hiệu Just – Enough – Time (JET) Trong phương thức JET, có một độ trễ giữa việc truyền dẫn gói tiêu đề burst và burst dữ liệu. Độ trễ này lớn hơn tổng thời gian xử lý gói điều khiển dọc theo tuyến. Mục đích là sao cho khi burst đến mỗi nút chuyển mạch trung gian thì gói tiêu đề burst đã được xử lý xong và một kênh trên cổng đầu ra đã được chỉ định. Do đó không cần đường dây trễ quang để làm trễ burst dữ liệu ở mỗi nút. Đây là một đặc tính quan trọng của JET vì đường dây trễ quang tốn kém và có nhiều hạn chế (ví dụ như chỉ cho độ trễ cố định, chiều dài lớn). Cơ chế báo hiệu Just – Enough – Time được mô tả trên hình 2.7, node nguồn đầu tiên gửi một gói tiêu đề bust (Burst Header Packet – BHP) trên một kênh điều khiển tới node đích. BHP được xử lý tại mỗi node tiếp theo với yêu cầu thiết lập đường dữ liệu toàn quang cho burst dữ liệu tương ứng. Nếu quá trình dự trữ tài nguyên thành công, chuyển mạch sẽ được cấu hình cho burst dữ liệu đi qua. Trong lúc đó, burst sẽ đợi tại nguồn trong miền điện. Sau một khoảng thời gian offsetime xác định trước, burst được gửi trong miền quang trên bước sóng được chọn. Hình 2.7: Cơ chế báo hiệu Just – Enough – Time Offset time được tính toán cơ bản dựa trên số nút chuyển mạch trung gian từ nguồn tới đích và thời gian chuyển mạch của node đích. Offset time được tính là [1]: OT = h.δ + ST Ở đây: h là số nút chuyển mạch trung gian giữa nguồn và đích. δ là thời gian xử lý tiêu đề burst trên một nút trung gian. ST là thời gian cấu hình lại chuyển mạch ở nút đích. Gói tiêu đề burst chứa thông tin về offset time và chiều dài burst. Và khi qua một nút trung gian thì giá trị offset time sẽ phải được cập nhật lại vì giá trị offset time sẽ giảm đi một lượng đúng bằng thời gian xử lý gói tin tiêu đề burst. Khi quá trình dự trữ tài nguyên thành công, kênh bước sóng tại một nút sẽ chỉ được ấn định hoàn toàn cho burst khi bit đầu tiên của burst dữ liệu truyền tới nút. Tức là trong khoảng thời gian offset time, kênh không bị chiếm hay rỗi cho dù đã đăng ký tài nguyên thành công. Kênh có thể gán cho burst dữ liệu khác miễn sao cho việc truyền các burst dữ liệu không bị chồng lên nhau. Kiểu dự trữ tài nguyên của JET gọi là dự trữ tài nguyên trễ (Delayed Reservation). Sau khi truyền xong burst dữ liệu kênh bước sóng sẽ tự động được giải phóng mà không cần phải có bản tin giải phóng kênh được gửi từ nguồn tới đích. Vì thế một đặc điểm khác của JET là giải phóng tài nguyên không rõ ràng (Implicit Release). Nếu tại nút trung gian nào đó, quá trình dự trữ không thành công, burst sẽ bị loại bỏ. Một vấn đề nảy sinh trong việc tính toán giá trị offset cho JET là phải xác định được số nút chuyển mạch trung gian giữa nguồn và đích. Trong mạng OBS, thông tin về số lượng các nút chuyển mạch trung gian trên một đường đi từ nguồn tới đích thông thường là không sẵn có. Thậm chí khi những thông tin này bằng cách nào đó được biết thì do ảnh hưởng của lộ trình thay đổi, nó cũng không đảm bảo tính hợp lệ khi sử dụng [5]. Như vậy, cần một giá trị offset time mà không phụ thuộc vào đường truyền sử dụng và không yêu cầu trao đổi thông tin giữa các node mạng với nhau. Hiện nay với những tiến bộ trong chế tạo phần cứng cho các giao thức truyền thông, trễ xử lý tại các node trung gian là rất ngắn trong hầu hết các chức năng chung của giao thức báo hiệu. Trong trường hợp này, các dây trễ quang có thể được sử dụng một cách hợp lý tại các node trung gian làm trễ mỗi burst đầu vào một lượng thời gian cân bằng với trễ xử lý tiêu đề. Ta có thể bỏ qua các trễ này trong tính toán. Sơ đồ mới này được gọi là giao thức chỉ có trễ đích (Only Destination Delay – ODD) và giá trị trong biểu thức là [5]: OT = δ + ST δ,ST là các giá trị trễ tại đích. *Dự trữ trễ (DR) trong việc sử dụng hiệu quả băng thông: Dự trữ trễ sẽ đem lại hiệu quả cao trong việc sử dụng băng thông. Hình 2.8 minh hoạ tại sao dự trữ trễ tạo nên sử dụng hiệu quả băng thông. Giả sử xét tại node X, một gói điều khiển tới và thực hiện dành trước tài nguyên tại thời điểm t1' và thời điểm bít đầu tiên của burst thứ nhất đến là t1, với t1> t1' .Ta có khoảng thời gian offset time của burst thứ nhất là: offset time = t1 - t1'. Cũng giả sử có một gói điều khiển khác (gói điều khiển thứ 2) đến node đang xét thời điểm t2', tương tự t2 là thời điểm bít đầu tiên của burst thứ 2 đến. Ta có thời gian trễ của burst này là: offset = t2 - t2'. Hình 2.8: Lợi ích của DR Để xác định thời điểm đến của Burst thứ nhất (t1) , khi thời gian xử lý gói điều khiển có thể thay đổi từ node này đến node khác, trong gói điều khiển sẽ cho biết giá trị thời gian trễ được sử dụng tại node kế tiếp. Giá trị này có thể được cập nhật dựa trên thời gian xử lý gói điều khiển tại node hiện tại. Trong chuyển mạch burst quang dựa trên giao thức JET , việc xác định thời điểm đến của burst t1 là rất quan trọng. Trong giao thức JET độ rộng băng được đăng ký tới thời điểm t1 +l1, l1 là khoảng thời gian tồn tại của burst thứ 1 , thay vì đến vô hạn. Điều này sẽ làm tăng hiệu quả sử dụng băng thông và giảm xác suất loại bỏ burst . Như hình ở trên, trong cả hai trường hợp, chúng ta sử dụng giao thức JET và dự trữ trễ thì burst thứ 2 đến vẫn được phục vụ nếu t1' < t2' < t2+l2 < t1 (trường hợp 1) hay t1' < t2' < t1+l1 < t2 (trường hợp 2). DR luôn sử dụng thời gian trễ. Để tăng hiệu quả sử dụng thời gian trễ trong JET và giảm độ trễ khi phải truyền lại burst, gói điều khiển sẽ được truyền đi tại thời điểm sớm nhất có thể được bằng cách ước lượng độ dài burst. Nếu độ dài burst lớn hơn độ dài ước lượng thì một gói điều khiển khác sẽ được gửi đi để xoá độ rộng băng đã đăng ký. Nếu độ dài burst nhỏ hơn độ dài ước lượng thì phần dữ liệu còn lại được gửi đi như một hay nhiều burst bổ sung. 2.3.2 Cơ chế báo hiệu Just – In – Time (JIT) Cơ chế báo hiệu Just-In-Time (JIT) tương tự như cơ chế báo hiệu JET, nhưng cơ chế này sử dụng phương thức dự trữ tài nguyên tức thời (Immediate Reservation) và giải phóng tài nguyên rõ ràng (Explicit Release). Giữa burst dữ liệu và gói tiêu đề burst có khoảng thời gian offset time do đó JIT không yêu cầu phải sử dụng đường dây trễ quang tại các nút chuyển mạch trung gian. Hình 2.9: Cơ chế báo hiệu Just – In – Time Khi gói tiêu đề burst được gửi đi để dự trữ tài nguyên, tại một nút chuyển mạch trung gian, một bước sóng khả dụng sẽ được ấn định cho burst dữ liệu ngay sau khi gói tiêu đề burst được xử lý. Bước sóng này sẽ dành riêng cho burst dữ liệu cho đến khi có một bản tin giải phóng được gửi đi từ node nguồn để giải phóng kết nối. Gói tiêu đề burst không cần phải mang thông tin về thời điểm đến của burst dữ liệu và độ dài của burst [3]. Nếu quá trình dự trữ tài nguyên thất bại, burst dữ liệu sẽ bị loại bỏ. Hình 2.10: So sánh cơ chế báo hiệu JET (trên) và JIT (dưới) Hình 2.10, so sánh cơ chế báo hiệu JET và JIT. Trong cơ chế báo hiệu JET sử dụng phương thức dự trữ tài nguyên trễ (Delayed Reservation), nghĩa là bước sóng khả dụng chỉ được ấn định khi burst dữ liệu “0” tới được nút nên trong khoảng thời gian offset time có thể truyền burst dữ liệu “1” trên cùng một bước sóng mà không xảy ra tranh chấp. Khi burst dữ liệu “0” kết thúc truyền, kênh truyền sẽ được giải phóng ngay vì vậy burst dữ liệu “2” có thể được gửi vào mạng OBS ngay khi burst “0” kết thúc. Trong cơ chế báo hiệu JIT, do sử dụng phương thức dự trữ tài nguyên tức thì nên trong khoảng thời gian offset time, burst dữ liệu “1” không thể truyền qua mạng OBS trên cùng bước sóng với burst dữ liệu “0”. Và khi burst dữ liệu “0” truyền kết thúc thì bản tin giải phóng sẽ được gửi đi từ node nguồn để giải phóng kênh, trong thời gian giải phóng kênh thì burst dữ liệu “2” không thể truyền qua mạng OBS được. Như vậy cơ chế báo hiệu Just – In – Time sử dụng băng thông không hiệu quả như Just – Enough – Time. Trong [4], Jing Teng và George N. Roukas đã tiến hành mô phỏng và kết quả cho thấy cơ chế báo hiệu JIT cho tỷ lệ mất burst cao hơn cơ chế báo hiệu JET. 2.3.3 Cơ chế báo hiệu Tell – And – Go (TAG) Đây là cơ chế báo hiệu dự trữ tài nguyên tức thì và giải phóng tài nguyên rõ ràng. Trong TAG, gói điều khiển được truyền dẫn trên một kênh điều khiển được theo sau bởi một burst, trên một kênh dữ liệu với độ lệch bằng không hoặc không đáng kể. Burst được đệm bằng cách sử dụng đường dây trễ quang (Fiber Delay Line – FDL) trong khi gói tin điều khiển được xử lý tại mỗi node trung gian. Đặc điểm này của Tell – And – Go giống với chuyển mạch gói quang. Nếu việc chiếm dụng bước sóng thành công thì burst được truyền dẫn dọc theo kênh đã chiếm trái lại burst sẽ bị loại bỏ và một bản tin phủ định báo nhận (NAK – Negative Acknowledgment) được gửi trở lại nguồn. Node nguồn sẽ gửi một gói điều khiển sau khi truyền dẫn burst để giải phóng tài nguyên bị chiếm dọc theo tuyến [2]. Nhược điểm cơ bản của phương pháp này là giới hạn về mặt công nghệ của đường dây trễ quang FDL. FDL có thể làm trễ burst trong một khoảng thời gian cố định và không thể thích nghi với kích thước burst dữ liệu thay đổi. Cũng như cơ chế báo hiệu Just – In – Time, TAG không tận dụng tài nguyên hiệu quả do sử dụng dự trữ tức thì và giải phóng tài nguyên rõ ràng. Khi chưa có bản tin Release, kênh sẽ không được giải phóng và trong khoảng thời gian giải phóng kênh, kênh sẽ không được gán cho bất cứ burst nào khác. Hình 2.11: Cơ chế báo hiệu Tell-And-Go 2.3.4 Cơ chế báo hiệu Tell – And – Wait (TAW) Cơ chế báo hiệu Tell – And – Wait được mô tả trên hình 2.12. Trong phương thức TAW, node nguồn sẽ gửi một gói điều khiển để dự trữ tài nguyên cho burst dữ liệu dọc theo tuyến. Sau đó nút nguồn sẽ đợi một bản tin xác nhận ACK từ node đích thông báo việc dự trữ tài nguyên đã thành công. Burst dữ liệu sẽ được gửi đi từ node nguồn trên tuyến đường đã chọn. Và sau khi burst được truyền đến đích sẽ có một bản tin giải phóng kết nối được gửi đi để giải phóng tài nguyên từ nguồn tới đích. Nếu quá trình dự trữ tài nguyên là không thành công tại một nút OBS trung gian nào đó đến nút đích thì ngay lập tức sẽ có một bản tin thông báo không thành công được gửi về từ nút đó để giải phóng tài nguyên đã được thiết lập trên tuyến từ nút nguồn đến nút đó và burst sẽ không được phát đi. Nút nguồn sẽ phải gửi lại gói điều khiển để dự trữ tài nguyên từ nguồn tới đích một lần nữa. Nếu chúng ta so sánh TAW và các cơ chế báo hiệu một chiều thì nhược điểm của TAW là thời gian cần thiết cho thiết lập kênh; tuy nhiên ưu điểm của TAW là tỷ lệ mất dữ liệu là rất thấp. Do đó, TAW phù hợp cho lưu lượng yêu cầu tin cậy về tỉ lệ mất burst và các burst có kích thước tương đối lớn so với thời gian thiết lập kênh truyền từ nguồn tới đích. Hình 2.12: Cơ chế báo hiệu Tell – And – Wait 2.4 Các thuật toán sắp xếp kênh Khi một gói tin tiêu đề burst tới nút lõi, khối điểu khiển chuyển mạch SCU xử lý gói tin này và một thuật toán sắp xếp kênh hay lập lịch kênh được thực hiện để gán burst dữ liệu cho một kênh bước sóng thích hợp ở đầu ra. Khối lập lịch kênh lấy thời điểm burst đến và chiều dài burst từ gói tin điều khiển. Thuật toán có thể cần phải duy trì thời điểm kênh truyền rỗi gần nhất LAUT (Latest Available Unscheduled Time) hay còn gọi là horizon, các tham số “void” và “gap” trên mọi kênh dữ liệu đầu ra. Theo lý thuyết, LAUT của một kênh dữ liệu là thời điểm gần nhất một kênh dữ liệu có thể sử dụng cho một burst dữ liệu chưa được lập lịch hay có thể hiểu là thời điểm kết thúc của một burst đã được lập lịch trong một số trường hợp. “Gap” là khoảng thời gian được tính giữa thời điểm đến của một burst chưa được lập lịch và thời điểm kết thúc của một burst đã được lập lịch trước đó. “Void” là khoảng thời gian giữa hai burst dữ liệu được lập lịch trên một kênh dữ liệu mà trong thời gian đó không có burst dữ liệu nào khác được lập lịch. Những thông tin sau được sử dụng bởi khối lập lịch cho hầu hết các thuật toán lập lịch kênh: Lb là chiều dài burst. t là thời điểm đến của burst chưa được lập lịch W là số lượng kênh dữ liệu tối đa ở ngõ ra. Nb là số lượng tối đa các burst dữ liệu được lập lịch. Di kênh dữ liệu thứ i ở ngõ ra. LAUTi là LAUT của kênh dữ liệu thứ i, i = 0,2…, W-1, cho các thuật toán không lấp khoảng trống. 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 dữ liệu thứ i, cho các thuật toán lấp khoảng trống. Gapi: Nếu kênh truyền có thể sử dụng, khoảng trống “gap” 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 lấp 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 không lấp khoảng trống. Nếu kênh truyền bận, thì Gapi = 0. Thông tin về khoảng trống “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. Những thuật toán lập lịch kênh nói chung có thể phân thành hai loại: các thuật toán không thực hiện lấp khoảng trống và thực hiện lấp khoảng trống. Các thuật toán về cơ bản khác nhau dựa trên loại và số lượng thông tin trạng thái tại một nút về các kênh truyền. Đối với các thuật toán không lấp khoảng trống, tham số LAUTi trên tất cả các kênh truyền Di được duy trì bởi bộ lập lịch kênh. Đối với các thuật toán lấp đầy khoảng trống, thời gian bắt đầu và kết thúc của mỗi một burst dữ liệu được duy trì tại mỗi nút trên tất cả các kênh. Trong phần dưới đây, chúng ta xem xét các thuật toán không lấp khoảng trống FFUC, LAUC và lấp khoảng trống FFUC-VF, LAUC-VF, Min-EV. 2.4.1 Kênh rỗi phù hợp đầu tiên (FFUC) Thuật toán FFUC lưu trữ giá trị của LAUT (hay còn gọi là horizon) trên tất cả các kênh dữ liệu. Khi burst dữ liệu đi đến, thuật toán FFUC sẽ tìm kiếm trên tất cả kênh truyền theo một thứ tự cố định và sắp xếp một kênh thích hợp tìm thấy đầu tiên cho burst đang đến này. Một kênh truyền được xem là thích hợp đối với thuật toán FFUC khi giá trị LAUT của nó nằm trước thời điểm burst chưa được lập lịch đi đến. Giải thuật FFUC có thể được giải thích như trên hình 2.13. Có thể mô tả như sau: FFUC thực hiện dựa trên các giá trị LAUT0, LAUT1, LAUT2, LAUT3 của kênh dữ liệu D0, D1, D2, D3. Thời điểm t là thời điểm burst đến. Ta thấy cả LAUT1 và LAUT2 đều thỏa mãn còn LAUT0 và LAUT3 không thỏa mãn. Nếu các kênh dữ liệu được sắp đặt dựa trên chỉ số của kênh (D0, D1, D2, D3), burst dữ liệu đi đến sẽ được sắp xếp trên kênh D1 vì theo thứ tự kênh D1 nằm trước kênh D2. Ưu điểm của thuật toán này là đơn giản và tốc độ nhanh. Nhược điểm của thuật toán này là tỷ lệ mất burst cao và tận dụng tài nguyên không hiệu quả. Hình 2.13: Thuật toán FFUC và LAUC 2.4.2 Kênh rỗi với LAUT gần nhấ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 dữ liệu nhưng trong quá trình tìm kiếm kênh dữ liệu thích hợp thay vì sắp xếp burst dữ liệu trên kênh 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 2.13. Các kênh dữ liệu D1 và D2 là thích hợp vì vì thời điểm burst đi đến nằm sau các LAUT của hai kênh này. Nếu như thuật toán FFUC được sử dụng thì kênh D1 đượ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, 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. Chúng ta thấy rằng Gap1 > Gap2 do đó burst sẽ được sắp xếp trên kênh D2. 2.4.3 Kênh rỗi phù hợp đầu tiên – thực hiện lấp khoảng trống (FFUC-VF) Điểm khác biệt của các thuật toán lấp khoảng trống nói chung là không lưu trữ giá trị LAUT mà lưu thời điểm bắt đầu S và kết thúc E của mỗi burst đã được lập lịch trên mọi kênh dữ liệu. Ưu điểm của thuật toán này là tận dụng khoảng trống giữa hai burst dữ liệu được sắp xếp làm tăng hiệu suất sử dụng kênh truyền. FFUC-VF cũng giống như FFUC, nó lựa chọn kênh truyền theo thứ tự. Kênh truyền đầu tiên với một khoảng cách “void” thích hợp được lựa chọn. Hình 2.14: Thuật toán FFUC-VF và LAUC-VF Thuật toán FFUC-VF được mô tả trên hình 2.14. Dựa trên Si,j và Ei,j, tất cả các kênh dữ liệu D0, D1, D2, D3 có khả năng đáp ứng cho burst dữ liệu đến chưa được lập lịch. Nếu các kênh này được sắp đặt theo chỉ số của từng kênh, burst dữ liệu mới đến sẽ được lập lịch ở ngõ ra D0 vì nó thỏa mãn các điều kiện sau: là kênh có số thứ tự đầu tiên có E0,0 nằm trước E0,a, khoảng trống “void” của kênh này lớn hơn chiều dài của burst mới đến chưa được lập lịch. 2.4.4 Kênh rỗi với LAUT gần nhất - thực hiện lấp khoảng trống (LAUC-VF) Giải thuật LAUC-VF cũng lưu những thời điểm bắt đầu S và kết thúc E cho mỗi burst dữ liệu đã được lập lịch trên tất cả các kênh dữ liệu. Ưu điểm của giải thuật này là tận dụng được khoảng trống giữa hai burst dữ liệu đã được sắp xếp. Kênh truyền với khoảng trống mà khoảng cách nhỏ nhất sẽ được chọn. Để thiết lập LAUC – VF, khối điều khiển chuyển mạch phải lưu lại thông tin sử dụng của tất cả các kênh dữ liệu. Điều này làm cho LAUC – VF phức tạp hơn so với FFUC và LAUC. Nhưng tận dụng tài nguyên hiệu quả hơn 2 loại trên. 2.4.5 Khoảng trống kết thúc tối thiểu (Min-EV) Một dạng khác của LAUC – VF là Minimum End Void (MinEV). MinEV sẽ xét sự khác nhau giữa thời điểm bắt đầu của burst dữ liệu đã lập lịch và thời điểm kết thúc của burst dữ liệu đến mới trên kênh. MinEV chọn một kênh có giá trị trước nó nhỏ nhất. Vì vậy giải thuật này cần lưu thông tin của các kênh dữ liệu trước 2.5 Phân giải tranh chấp 2.5.1 Bộ đệm quang Cần sử dụng bộ đệm khi có nhiều hơ