NGHIÊN CỨU CÁC GIẢI THUẬT XẾP LỊCH ĐỂ TỐI ƯU HÓA VIỆC TRUYỀN SỐ LIỆU TRONG MẠNG OBS - 7

S(i, j) , E(i, j) : Thời điểm bắt đầu và kết thúc của mỗi burst thứ j đã được sắp xếp trênkênh thứ i.Gapi : Nếu kênh rỗi, gap là sự chênh lệch giữa thời gian đến của burst và các thôngsố LAUTi đối với trường hợp không sử dụng void filling, và thông số E(i, j) đối với trường hợp có void filling. Thông số Gap là cơ sở để thuật toán quyết định nên sử dụng kênh nào khi có hơn 1 kênh rỗi. Trong trường hợp kênh không rỗi, hệ số gap bằng 0. 4.3 Các...
Nội dung trích xuất từ tài liệu:
NGHIÊN CỨU CÁC GIẢI THUẬT XẾP LỊCH ĐỂ TỐI ƯU HÓA VIỆC TRUYỀN SỐ LIỆU TRONG MẠNG OBS - 7S(i, j) , E(i, j) : Thời điểm bắt đầu và kết thúc của mỗi burst thứ j đã được sắp xếp trênkênh thứ i.Gapi : Nếu kênh rỗi, gap là sự chênh lệch giữa thời gian đến của burst và các thôngsố LAUTi đối với trường hợp không sử dụng void filling, và thông số E(i, j) đối vớitrường hợp có void filling. Thông số Gap là cơ sở để thuật toán quyết định nên sửdụng kênh nào khi có hơn 1 kênh rỗi. Trong trường hợp kênh không rỗi, hệ số gapbằng 0.4.3 Các giải thuật xếp lịch cơ bản4.3.1 Các thuật toán không sử dụng void-filling4.3.1.1 Thuật toán FFUC Giải thuật FFUC (First Fit Unschedule Channel) không sử dụng void fillingcó thể được trình bày cơ bản như sau: Khi một burst dữ liệu đến một nút. Nút đó sẽ Gapi tub - LAUTi , nếu thông số này lớn hơn 0 thì kênh đó sẽso sánh thông số =thích hợp để cấp cho burst đó. Trong trường hợp có nhiều hơn 1 kênh thích hợp,thuật toán sẽ chọn kênh có hệ số i thấp nhất. Hình 4.1: Mô hình giải thuật FFUC không sử dụng void filling. Trong ví dụ trên, ta thấy khi burst dữ liệu đến nút lõi thì có 2 kênh khôngthỏa mãn yêu cầu của thuật toán là kênh 0 và kênh 3 do hệ số LAUT lớn, trong khiđó kênh 1 và kênh 2 là 2 kênh thỏa điều kiện của thuật toán. Trong trường hợp này,thuật toán sẽ chọn lựa kênh 1 (1 TH =i Drop N burst Sắp xếp i++ burst update end Hình 4.2: Lưu đồ giải thuật FFUC4.3.1.2 Giải thuật LAUC Giải thuật LAUC (Latest Available Unschedule Channel) không sử dụngvoid filling có thể được trình bày cơ bản như sau: Khi một burst dữ liệu đến một Gapi tub - LAUTi , nếu thông số này lớn hơn 0nút. Nút đó sẽ so sánh thông số =thì kênh đó sẽ thích hợp để cấp cho burst đó. Trong trường hợp có nhiều hơn 1 kênhthích hợp, thuật toán sẽ chọn kênh có hệ số gap nhỏ nhất. LAUT Hình 4.3: Mô hình giải thuật LAUC không sử dụng void filling.Trong trường hợp trên, cũng chỉ có 2 kênh thỏa mãn yêu cầu của thuật toán, nhưngthuật toán sẽ chọn kênh thứ 2 do có hệ số gap nhỏ hơn kênh thứ 1. b egin i = ncc N N Y fdl ≤ Có i i≤ Làm trễ channel max n Y Y Y N N Tìm channel Sắp xếp burst Drop burst i ++ update end Hình 4.4: Lưu đồ giải thuật LAUC4.3.2 Giải thuật có sử dụng void fillingGiải thuật FFUC và LAUC có mức sử dụng tài nguyên thấp do nó không quan tâmđến các khoảng trống do đó người ta đưa ra một thuật toán khác sửa đổi từ giải thuậtFFUC và LAUC ban đầu gọi là FFUC có sử dụng void filling (FFUC-VF) và giảithuật LAUC có sử dụng void filling (LAUC-VF). Trong các thuật toán có sử dụngvoid filling, khoảng trống giữa các burst và khoảng trống tính từ thời điểm sử dụngsau cùng của kênh dữ liệu hay thời gian kết thúc cuối cùng của burst cuối cùngđược sắp xếp trên kênh dữ liệu đến vô cùng được tận dụng để sắp xếp các burst.4.3.2.1 Giải thuật FFUC_VF Các giải thuật sử dụng void filling thì bộ channel scheduling sẽ phải ghinhận thông số bắt đầu và kết thúc của từng burst dữ liệu trên kênh truyền. Khi mộtburst dữ liệu đến, nếu thời điểm bắt đầu burst dữ liệu lớn hơn thời điểm kết thúc củaburst trước đó và thời điểm kết thúc của burst dữ liệu nhỏ hơn thời điểm bắt đầu củaburst liền sau nó (nếu sau nó không còn burst nào khác thì thời gian bắt đầu đó xemnhư là ∞) thì kênh truyền đó được chọn làm ngõ ra cho burst d ữ liệu. Tương tự nh ưtrên, FFUC sẽ chọn kênh có hệ số i nhỏ nhất làm kênh ngõ ra. Hình 4.5 Mô hình giải thuật FFUC có sử dụng void filling. Trong trường hợp trên thì cả 4 kênh đều thỏa mãn điều kiện của thuật toán,nhưng thuật toán FFUC sẽ chọn kênh đầu tiên (kênh 0) làm kênh ngõ ra cho burstdữ liệu.4.3.2.2 Thuật toán LAUC_VF Cũng tương tự như thuật toán FFUC_VF, thuật toán LAUC có sử dụ ...