Tìm kiếm nhanh và chính xác hơn với google tùy chỉnh

Thứ Sáu, 16 tháng 3, 2012

Kỹ thuật cửa sổ trượt (Sliding Window)

Một kỹ thuật điều khiển luồng , tốt hơn kỹ thuật dừng và đợi .

a. Hoạt động
Bên phát được phát tối đa w khung trước khi nhận báo nhận(w:kích thước cửa sổ)
Mỗi khi phát 1 khung w giảm đi 1 đơn vị,mỗi khi nhận 1 báo nhận,w lại tăng lên 1 đơn vị,khi w=0 thì không được phép phát tiếp

Do bên phát được phát đồng thời w khung nên cần có 1 trường đánh số thứ tự các khung tin

Giả sử cần k bit đánh số thứ tự các khung tin thì 1<= w <= 2^k - 1



Vd: Dùng 3 bit đánh số thứ tự các khung tin => w<8, chọn w=7, máy thu phải có bộ nhớ đệm để lưu trữ và xử lý tương ứng.


ở ví dụ này bên phát được phép truyền tối đa 3 frame tiếp theo. Lúc đầu bên máy phát sẽ truyền đi 3 frame và chờ phản hồi, nếu có ACK (như trên hình là RR3 tức là đã sẵn sàng nhận frame 3 trở đi) thì bên phát sẽ gửi tiếp, tuy nhiên cùng với thời gian gửi thì bên thu cũng gửi lại RR để báo bên phát còn có thể truyền bao nhiêu frame nữa. Nếu như bên thu bị sao đó hoặc "chán" không muốn nhận thêm thì chỉ đơn giản không gửi nữa , bên phát sẽ chỉ phát được đến mức tối đa 7 frame từ thông báo cuối cùng thôi hoặc nếu gửi chậm chậm thì bên phát sau khi truyền thả phanh đến hét bộ đệm bên thu thì khi nào nhận được thông báo mới bắt đầu truyền tiếp.


b.Hiệu suất
Hiệu suất của kỹ thuật sliding window được tính như sau
+n = 1 nếu w>=2a+1
+n = w / (1+2a) nếu w<2a+1


Vẫn ví dụ gửi thư như ở bài kỹ thuật dừng và đợi :
Giờ không gửi một bức thư nữa, người miền nam bảo cứ gửi thư đi, hòm thư nhà tao chứa được 10 bức chẳng hạn. Thời gian thì vẫn mất 2 ngày để nhận thư, còn thời gian để viết xong thư coi như là 1 ngày 1 bức đi (15 phút 1 bức thì không thể viết suốt ngày đêm được, lâu rồi cũng chán).
Đầu tiên phải viết 1 bức hỏi xem bên kia thế nào, có muốn nhận thư không, nhận được bao nhiêu, quá trình khởi động mất 5 ngày ( mất 2 ngày để thư đến đích, 1 ngày để bên kia viết và 2 ngày để thư đáp trả lại).
Bên nhận thư báo lại là cứ viết thoải mái đi, hoặc không thấy hồi âm thì thôi khỏi gửi. Nếu nhận thông báo ok, từ đây người viết ngày nào cũng viết cũng gửi. Khi đó người viết đã viết đến bức thứ 6 thì nhận được thông tin là đã ok thư thứ nhất(tức là có thể truyền đến thư thứ 11) thì mới đầy hòm thư, hôm sau người viết viết thư thứ 7 thì lại thông báo có thể truyền đến thư 12 ... cứ thế, không mất công đợi , hiệu suất 100% nếu bên nhận gửi cũng nhanh bằng hoặc hơn bên gửi, nếu bên kia xử lý chậm đọc chậm thì hòm thư cứ đầy dần, người gửi thấy 10 bức không thấy hồi âm thì sẽ dừng lại, đến khi bên kia gửi xác nhận thì mới gửi tiếp nên không bị đầy, "bục" hòm thư.
Phương thức này hiệu suất cao, maximum 100% (tất nhiên nếu không tính giai đoạn khởi động chờ xem bên kia có phản hồi không hay lại nhầm địa chỉ đi đâu), tốt hơn dừng và đợi nhiều, nhưng cần bộ đệm.

Ở trên mình giải thích trong trường hợp có thể song công (vừa truyền vừa nhận), nếu chỉ có truyền hoặc nhận (không đồng thời được) thì cũng chỉ giống như truyền stop and wait vì gửi tối đa n frame với ghép n frame thành 1 frame để truyền (trong stop and wait) thì cũng như nhau thôi, có điều nếu lỗi thì cái này không phải truyền lại toàn bộ frame như stop and wait.

2 nhận xét:

minh nói...

hay quá, nhưng bạn giải thích rõ hơn cho mình cái sơ đồ được ko? tại sao giai đoạn 1 là gửi đi 3 frame mà giai đoạn 2 lại là 4 frame

Unknown nói...

Gửi nhiêu thì tùy theo tốc độ bên gửi thế nào, vấn đề là khi bộ đệm chưa đầy thì xác nhận gửi tín hiệu ok đã quay trở lại để đảm bảo có thể truyền liên tục được.

Bạn đọc kỹ đoạn phía dưới cái hình thì sẽ rõ thôi.

:) , :D , :)) , =)) , :( , :(( , x-( , :-/ , :|

Đăng nhận xét

Twitter Delicious Facebook Digg Stumbleupon Favorites More

 
Design by NewWpThemes | Blogger Theme by Lasantha - Premium Blogger Themes | New Blogger Themes