NGUYÊN CỨU VÀ ỨNG DỤNG CHƯƠNG TRÌNH LẬP LỊCH TRONG MẠNG IP CHƯƠNG 3_2

Từ kết quả (3. 10) và (3. 11) có thể dễ dàng thấy rằng WFQ và GPS cung cấp hầu hết tính đúng đắn của một gói Parekh đã cung cấp rằng WFQ không thể sụp đổ sau GPS ở khía cạnh các dịch vụ cung cấp bởi một gói có kích thước lớn nhất
Nội dung trích xuất từ tài liệu:
NGUYÊN CỨU VÀ ỨNG DỤNG CHƯƠNG TRÌNH LẬP LỊCH TRONG MẠNG IP CHƯƠNG 3_2Đồ án tốt nghiệp Chương 3: Scheduling ĐỒ ÁN HỆ THỐNG MẠNG Đề tài: NGUYÊN CỨU VÀ ỨNG DỤNG CHƯƠNG TRÌNH LẬP LỊCH TRONG MẠNG IP CHƯƠNG 3 SCHEDULING 3. 2. 2. 11 WF2Q Hàng đợi hợp lý theo trọng số trong trườnghợp xấu nhất Từ kết quả (3. 10) và (3. 11) có thể dễ dàng thấy rằng WFQ và GPS cungcấp hầu hết tính đúng đắn của một gói Parekh đã cung cấp rằng WFQ không thểsụp đổ sau GPS ở khía cạnh các dịch vụ cung cấp bởi một gói có kích thước lớnnhất . Xét hình 3. 14, ở đó 11 phiên được phân thành các liên kết giống nhau.Trục ngang là thời gian, trục dọc là đường đi đơn giản của mỗi phiên. Đ ể đơngiản, giả sử tất cả các gói cùng có kích cỡ là 1 và tốc độ là 1. Đ ặt tốc độ bảo đảmcủa phiên 1 là 0. 5 và tốc độ của 10 phiên còn lại là 0. 05Đồ án tốt nghiệp Chương 3: Scheduling Hình 3. 14 Ví dụ Phiên 1 gửi 11 gói lặp lại bắt đầu từ thời gian là 0, trong khi mỗi phiên của10 phiên khác chỉ gửi 1 gói cũng tại thời gian là 0. Nếu dịch vụ là GPS nó sẽ giữ2 đơn vị thời gian cho gói của phiên 1 và 20 đơn vị thời gian cho các gói của cácphiên còn lại. Còn nếu server là WFQ, tại thời gian 0, tất cả 11 phiên có các góigửi đi sẽ đ ược xử lý. Khi gói p 1, 1(gói đầu tiên của phiên 1) kết thúc tại thời gian2, trong khi tất cả các gói khác sẽ kết thúc ở thời gian 20 trong hệ thống GPS.WFQ sẽ phục vụ gói p1, 1 trước, vì thế 10 gói trong phiên 1 sẽ có thời gian xử lýnhỏ hơn các gói từ các phiên khác. Tức là 10 gói trong phiên 1 sẽ được phục vụlặp lại trước khi các gói trong phiên khác được truyền đi. Định nghĩa 3. 5 : Một dịch vụ s đ ược gọi là hợp lý nhất cho phiên i nếu tạithời gian τ trễ của gói đến tại τ được giới hạn bởi Qis( )/ri+c is đó là : D si, kĐồ án tốt nghiệp Chương 3: Scheduling Trong đó ri là giới hạn băng thông nhỏ nhất của phiên i, Qis(  ) là kíchthước của hàng đợi của phiên i tại thời gian ai, k khi gói thứ k của phiên i đến, cislà hằng số C’i=rici’/r (3. 18) C’=max{cis} (3. 19) Định l ý 3. 1: Cho một hệ thống WF2Q và một hệ thống GPS tương ứng,th ì các thuộc tính sẽ giữ cho mỗi i, k, τ là: DWFQi, k–di, kGPS  Lmax/r (3. 20) Wi, kWFS(0, 0)-WiWFQ  Lmax (3. 21) WiW2FQ(0, 0)-WiGPS  (1–ri/r)Li (3. 23) 3. 2. 2. 12 WF2Q+ WF2Q cung cấp giới hạn trễ chặt và nhỏ nhất WFI của tất cả các thuật toánPFQ, nó có thời gian phức tạp giống như trường hợp xấu nhất, O(N), như WFOvì chúng cần cả hai để tính toán thời gian ảo hay hệ thống thời gian ảo V(t) bằngdấu hiệu hệ thống GPS lỏng. WF2Q+ và SPFQ cho thấy có các đặc tính tương tựnhư WF2Q nhưng chúng thực hiện đơn giản hơn bằng việc đưa ra hàm thời gianảo của hệ thống như sau:  V(t+  )=max V (t   ), min ( S i (t ))i   (t) (3. 23) trong đó β(t) là tập hợp các phiên tạm thời trong hệ thống tại thời gian t,và Si(t) là thời gian bắt đầu ảo của phiên tạm thời của gói tin HOL. Gọi W(t, t+τ)là tổng số lượng các dịch vụ được cung cấp bởi các server hoặc số bit đã đượctruyền dẫn trong khoảng thời gian (t, t+τ). Trong trường hợp đặc biệt của mộtserver tốc độ không đổi, τ = W(t, t+τ)/r, trong đó r là khả năng kết nối. Thời gianphức tạp được giảm tới O (log N), các thuộc tính này được vận hành cho việctìm kiếm giá trị thời gian bắt đầu nhỏ nhất trong số các phiên N. Gần giống vớiGPS, thuật toán PQF, như WF2Q+ và SPFQ duy trì một hệ thống hàm thời gianĐồ án tốt nghiệp Chương 3: Schedulingảo V(t), hàm thời gian bắt đầu ảo Si(t) và hàm thời gian kết thúc ảo (hoặc temthời gian) Fi(t) cho mỗi hàng đ ợi i. Si(t) và Fi(t) được cập nhật khi các gói HOLđến mỗi hàng đ ợi. Một gói thực sự khởi hành khi các bit cuối của nó được gửi rangoài khi một gói đến xuất hiện trong hai trường hợp sau : Trường hợp 1, mộthàng đợi trước rỗng ngay lập tức có một gói HOL đến ; trường hợp 2 gói tiếptheo của gói HOL trong một hàng đợi không rỗng ngay lập tức trở thành góiHOL khi nó xuất phát. Hiển nhiên, trong trường hợp 2 gói xuất phát và gói đếntại cùng một thời điểm, vì thế: Si(t) = max{V(t), Fi(t -)} ; đối với gói đến trong trường hợp 1(3. 24) Si ...