Lặp Lại Có Lựa Chọn (Selective

các khung 4 và 5 bị loại khi chúng đến. Thiết bị phát gửi lại cả ba khung (3, 4 và 5) do từ xác nhận trước đó, và quá trình tiếp tục. Máy thu đã loại các khung 4 và 5 (cùng các khung tiếp theo) cho đến khi nhận tốt được khung 3.

Mất khung dữ liệu:

Giao thức cửa sổ trượt đòi hỏi các khung dữ liệu phải được chuyển đi tuần tự. Nếu một trong số các khung này bị nhiễu và bị thất lạc trong khi truyền, thì khung đến sau sẽ bị máy thu loại. Máy thu kiểm tra số nhận dạng của mỗi khung, phát hiện ra là một số khung đã bị bỏ qua, và gửi về tín hiệu NAK cho khung thất lạc đầu tiên. Khung NAK không chỉ ra là khung đã bị thất lạc hay hỏng, chỉ thông báo yêu cầu gửi lại. Thiết bị phát sẽ phát lại khung do NAK yêu cầu, cùng các khung đã được chuyển đi sau khung vừa thất lạc.

Sender Receiver

Data 0

Data

Có thể bạn quan tâm!

Xem toàn bộ 210 trang tài liệu này.

Data

Lost

Data 3

Discarded

NAK 2

Data 4

Discarded

Time

Hình 5.24. Hoạt động của Go back N khi mất khung dữ liệu

Trong hình trên, dữ liệu 0 và 1 thu được nhưng dữ liệu 2 thì bị mất. Khung kế tiếp sẽ đến máy thu là khung 3. Máy thu đang chờ khung 2 nên khung 3 bị xem là lỗi, bị loại và gửi về thông báo NAK 2, cho biết các khung 0 và 1 đã được chấp nhận nhưng khung 2 thì bị sai (bị thất lạc trong trường hợp này). Trong ví dụ trên, do máy phát đã phát dữ liệu 4 trước khi nhận được NAK 2, dữ liệu 4 đến đích nhưng bị loại. Một khi máy phát nhận được tín hiệu NAK 2, thì chuyển tất cả các khung còn bị kẹt lại (2, 3 và 4).

Mất ACK:

Máy phát không mong nhận được các khung ACK sau mỗi dữ liệu đã gửi. Vì vậy nên không thể dùng các chuỗi số của ACK để nhận dạng các khung ACK hay NAK bị thất lạc, mà phải dùng một timer. Thiết bị phát có thể gửi bất kỳ khung nào

trong lúc mà cửa sổ còn cho phép trước khi chờ tín hiệu chấp nhận. Một khi giới hạn thời gian này đã hết hay máy phát không còn khung để gửi thì máy phát phải chờ. Nếu một tín hiệu ACK (đặc biệt nếu là NAK) do máy thu gửi đi bị thất lạc, thì máy phát phải chờ mãi. Để tránh tình trạng này, phải phát phải trang bị một bộ timer nhằm bắt đầu đếm khi dung lượng cửa sổ đã đầy. Khi không nhận được tín hiệu xác nhận sau một thời gian hạn định, máy phát gửi lại mỗi khung đã được phát từ lần nhận được ACK gần nhất.

Data

Lost

ACK 3

Sender

Time out

Time Time

Hình 5.25. Hoạt động của Go back N khi mất ACK

Hình trên cho thấy trường hợp khi máy phát đã gửi đi tất cả các khung và chờ tín hiệu xác nhận đã bị mất trên đường truyền. Máy phát chờ trong một thời gian xác định, rồi gửi lại các khung NAK. Máy thu nhận ra được là lần truyền mới này là lần lặp lại của lần trước, gửi tiếp đi tín hiệu ACK, và loại bỏ thông tin thừa.

5.4.2.2. Lặp lại có lựa chọn (Selective - repeat ARQ)

Trong giao thức này, chỉ phải truyền lại các khung bị hỏng hay thất lạc. Nếu một khung bị hỏng trong khi truyền thì tín hiệu NAK được gửi về và khung này được gửi riêng. Bộ thu phải có khả năng chọn lọc các khung và chèn vào đúng chỗ trong chuỗi khung. Để thực hiện được việc này, hệ thống Selective - repeat ARQ có điểm khác so với Go - back - N ARQ như sau:

- Thiết bị thu phải có trình tự chọn lọc cho phép sắp xếp lại các khung nhận được. Thiết bị thu cũng cần lưu trữ được các khung đã nhận được từ sau khi gửi về NAK cho đến khi khung hỏng này được thay thế.

- Thiết bị phát phải có cơ chế tìm kiếm nhằm cho phép tìm và chọn lọc các khung được yêu cầu truyền lại.

- Bộ nhớ đệm tại phần thu sẽ lưu trữ tất cả các khung đã nhận được trước đó cho đến khi tất cả các khung truyền lại được chọn lọc và các khung trùng lặp được nhận ra và loại bỏ.

- Nhằm tăng tính chọn lọc, các số ACK, cũng như số NAK cũng được ghi cho các khung đã nhận được (hay thất lạc) thay vì là các khung mong muốn nhận

- Tính phức tạp này đòi hỏi kích thước của cửa sổ phải bé hơn so với trường hợp Go - back -N để cho phép hệ thống hoạt động hiệu quả hơn. Kích thước cửa sổ nên

được chọn bé hơn hay bằng hợp Go - back - N.

Các trường hợp hỏng:

Lỗi khung dữ liệu

(n 1) / 2 , trong đó

(n 1)

là kích thước cửa sổ của trường

Hình 5.26 minh họa tình huống trong đó khung dữ liệu nhận được bị lỗi. Theo đó, khung 0 và 1 được nhận nhưng không được xác nhận. Dữ liệu 2 đến và bị phát hiện là có lỗi, đến có tín hiệu NAK về. Tương tự khung NAK trong phương pháp sửa lỗi go-back-n, một NAK ở đây chứa thông tin của phần xác nhận dữ liệu nhận và chỉ thị sai số ở khung hiện tại. Trong hình thì NAK-2 cho máy phát biết rằng dữ liệu 0 và 1 đã được chấp nhận, nhưng phải gửi lại dữ liệu 2. Khác với trường hợp máy thu của hệ thống sử dụng Go - back - N ARQ, trường hợp này máy thu truyền lại có chọn lọc nên bắt đầu chấp nhận các khung mới trong khi chờ đợi các lỗi phải sửa. Tuy nhiên, do ACK cho biết về các cuộc nhận thành công không chỉ trong khung đang có mà còn có giá trị cho tất cả các khung đã nhận được trước đó, các khung nhận được sau khi khung lỗi chưa được xác nhận, cho đến khi các khung lỗi được gửi lại. Trong hình thì máy thu chấp nhận dữ liệu 3, 4 và 5 trong khi chờ bản copy của dữ liệu 2. Khi dữ liệu 2 mới tới, tín hiệu ACK 5 được gửi trả về, xác nhận về tín hiệu 2 mới, và các khung gốc 3, 4 và

5. Máy thu cần có phương thức chọn lựa trong các chuỗi khung được truyền lại và theo dòi xem khung hỏng còn thiếu để có thể xác nhận.

Sender Receiver

` `

Data 0

Data 1

NAK 2

Data 2

Errors in Frame 2

Resent

Data 3

Data 4

Data 5

Time

Hình 5.26. Hoạt động của Selective - Repeat ARQ khi lỗi khung dữ liệu

Mất khung dữ liệu:

Tuy các khung có thể được nhận, nhưng không có nghĩa là được xác nhận. Nếu khung bị thất lạc thì khung kế tiếp sẽ không được nhận vào chuỗi. Khi máy thu cố sắp xếp lại các khung hiện có, thì sẽ phát hiện ra thiếu sót này và gửi đi tín hiệu NAK. Đương nhiên là máy thu chỉ có thể nhận ra thiếu sót này nếu có các khung tiếp tục đến. Nếu khung thất lạc là khung truyền cuối cùng thì máy thu không làm gì và máy phát sẽ xem sự im lặng này chính là NAK.

Mất ACK:

Các khung ACK và NAK thất lạc được Selective - Reject ARQ xử lý tương tự như trong trường hợp Go - back - N ARQ. Khi thiết bị phát đạt đủ dung lượng của cửa sổ hay khi chấm dứt truyền, thì thiết lập bộ timer. Nếu không có tín hiệu xác nhận trong khoảng thời gian qui định, thiết bị phát gửi lại tất cả các khung chưa được xác nhận. Trong hầu hết trường hợp, máy thu sẽ nhận ra các bản trùng lắp và loại bỏ chúng.

Hiệu suất Continuous RQ

Trong phần thảo luận giao thức Idle RQ, chúng ta đã thấy hiệu suất sử dụng liên kết là một hàm theo thời gian truyền một khung dữ liệu và thời gian lan truyền của liên kết. Tuy nhiên, trong các liên kết với tprop lớn hơn tf thì hiệu suất sử dụng liên kết cũng bị chi phối bởi cửa sổ truyền.

Đối với giao thức Continuous RQ, hiệu suất truyền có mối liên hệ với cửa sổ truyền K như sau:

h0  1

nếu

K  1 2a

(5.15)

h0 

Kt f

t f  2tprop

K

1 2a

nếu

K  1 2a

(5.16)

So sánh giữa phương pháp Go – back – N và Selective – repeat ARQ

Mặc dù chỉ truyền lại các khung bị hỏng hay thất lạc nên có vẻ hiệu quả hơn so với việc chuyển lại tất cả các khung bị hỏng, nhưng do cơ chế chọn lọc và lưu trữ mà máy thu phải có, cùng với cơ chế chọn lọc phức tạp nên phương pháp Selective - repeat có chi phí đắt hơn và ít được dùng. Tức là, tuy có hiệu quả hơn nhưng thực tế thì phương pháp Go – back – N được dùng nhiều hơn do dễ thiết lập.

Nhận xét: Giao thức Stop – and – Wait ARQ có thể coi là một trường hợp đặc biệt của giao thức cửa sổ trượt trong đó kích thước cửa sổ được chọn là 1.

Ví dụ 5.11:

Truyền 1500 bit thông tin theo giao thức HDLC, sử dụng giao thức Selective – repeat ARQ. Xác định hiệu suất sử dụng đường truyền trong các trường hợp sau nếu tốc độ lan truyền là 2.108 m/s và độ lỗi bit của các liên kết thấp không đáng kể:

a) Một liên kết dài 2km có tốc độ 2Mbps và cửa sổ truyền K= 3.

b) Một liên kết dài 20km có tốc độ 300Mbps và cửa sổ truyền K= 8.

c) Một liên kết vệ tinh dài 20 000km có tốc độ 2Mbps và cửa sổ truyền K= 128.

Giải:

Một liên kết dài 2km có tốc độ 2Mbps và cửa sổ truyền K= 3 Thời gian cần truyền 1 frame tf là:

tf = số bit trong frame/ tốc độ bit (bps)

=1500/2. 106 = 750. 10-6s

t prop

S = 2.103 /2.108 = 10-5 s

a = 10-5/750. 10-6=1,33.10-4

K=3>1+2a do đó

h0 =1

b) Một liên kết dài 20km có tốc độ 300Mbps và cửa sổ truyền K= 8.

t prop

S =20. 103 /2.108 = 10-4 s

tf = số bit trong frame/ tốc độ bit (bps)

=1500/300. 106 = 5. 10-6s a = 10-4/5. 10-6=20

K=8 nhỏ hơn 1+2a nên U=K/(1+2a)=8/(1+2*20)=0,2

c) Một liên kết vệ tinh dài 20 000km có tốc độ 2Mbps và cửa sổ truyền K= 128.

t prop

S =20. 106 /2.108 = 0,1 s

tf = số bit trong frame/ tốc độ bit (bps)

=1500/2. 106 = 750. 10-6s a = 0,1/750. 10-6=133

K=128 nhỏ hơn 1+2a nên U=K/(1+2a)=128/(1+2*133)=0,48

5.5. Điều khiển liên kết dữ liệu mức độ cao HDLC

Giao thức HDLC là một giao thức chuẩn hoá quốc tế đã được định nghĩa bởi ISO để dùng cho cả liên kết điểm - nối - điểm và đa điểm. Nó hỗ trợ hoạt động ở chế độ trong suốt, song công hoàn toàn và ngày nay được dùng một cách rộng dãi trong các mạng đa điểm và trong các mạng máy tính. Ngoài tên gọi là HDLC nó còn có các tên gọi khác như: SDLC (Synchronous data link control) của IBM, ADCCP (Advanced data communications control procedure) là tên dùng bởi tổ chức ANSI.

5.5.1. Các đặc điểm cơ bản

Hệ thống dùng HDLC có thể được đặc trưng hóa bởi dạng trạm, cấu hình và chế độ đáp ứng.

a) Các dạng trạm

Trạm trong HDLC có ba dạng: sơ cấp, thứ cấp và kết hợp. Trạm sơ cấp gửi tín hiệu điều khiển, thứ cấp gửi tín hiệu đáp ứng. Trạm kết hợp gửi cả tín hiệu điều khiển và đáp ứng.

b) Cấu hình (Configuration)

Từ cấu hình nói lên quan hệ của các thiết bị phần cứng trong kết nối. Các trạm sơ cấp, thứ cấp và kết hợp có thể được cấu hình theo 3 cách: không cân bằng, đối xứng và cân bằng.

Các cấu hình này đều hỗ trợ cho phương thức truyền song công và bán song công.

Cấu hình không cân bằng(hay còn gọi là cấu hình master/slave) trong đó có một thiết bị là sơ cấp và các thiết bị khác là thứ cấp. Cấu hình không cân bằng còn được gọi là cấu hình điểm - điểm nếu chỉ có hai thiết bị, và thường là điểm - nhiều điểm trong đó một thiết bị sơ cấp điều khiển nhiều thiết bị thứ cấp.

Cấu hình đối xứng, trong đó mỗi trạm vật lý trên mạng gồm hai trạm luận lý, một là sơ cấp và một là thứ cấp. Các dây riêng biệt nối sơ cấp của một trạm vật lý đến thứ cấp của một trạm vật lý khác. Cấu hình đối xứng hoạt động tương tự như cấu hình không cân bằng trừ việc điều khiển mạng có thể được cả hai mạng thực hiện.

Cấu hình cân bằng, trong đó có một trạm dạng hỗn hợp, trong số các trạm cấu hình điểm - điểm. Các trạm được kết nối dùng một dây và được điều khiển từ các trạm khác.

Hình 5.27. Các cấu hình của các trạm sơ cấp, thứ cấp và kết hợp

HDLC không hỗ trợ chế độ cân bằng nhiều điểm. Điều này đưa ra nhu cầu cho việc thiết lập các giao thức truy cập môi trường cho mạng LAN.

c) Chế độ đáp ứng

Hoạt động của HDLC dựa trên quan hệ giữa hai thiết bị cần trao đổi thông tin: Chế độ này cho biết ai điều khiển mạng. Trao đổi trong cấu hình không cân bằng thường được thực hiện trong chế độ đáp ứng bình thường. Trao đổi trong cấu hình đối xứng hay cân bằng có thể được thiết lập ở các chế độ đặc biệt dùng các frame được thiết kế để mang lệnh điều khiển (sẽ thảo luận trong phần U-frame). HDLC hỗ trợ ba chế độ thông tin giữa các trạm:

Chế độ đáp ứng bình thường (normal response mode: NRM).

Chế độ đáp ứng không đồng bộ (asynchronous response mode: ARM). Chế độ cân bằng không đồng bộ (asynchronous balanced mode: ABM).

NRM: là chuẩn về quan hệ sơ cấp-thứ cấp. Trong chế độ này, thiết bị thứ cấp phải cho phép từ thiết bị sơ cấp thì mới có thể gửi tin. Khi đã có phép rồi thì thiết bị thứ cấp có có thể khởi tạo một đáp ứng truyền một hay nhiều frame dữ liệu.

ARM: thiết bị thứ cấp có thể khởi tạo việc truyền không cần sự cho phép của thiết bị sơ cấp khi nào kênh trống. Các trường hợp khác thì quan hệ master/slave vẫn được duy trì.

Mọi thông tin truyền từ thiết bị thứ cấp (hay từ một thiết bị thứ cấp khác trong đường truyền) vẫn phải dùng thiết bị sơ cấp làm relay để đi đến đích.

ABM: mọi thiết bị đều đồng quyền nên cần có các trạm hỗn hợp điểm nối điểm.

Các trạm hỗn hợp có thể gửi tin đến các trạm hỗn hợp khác mà không cần có phép.

■ Normal response mode (NRM)

■ Asynchronous response mode (ARM)

■ Asynchronous balanced mode (ABM)

5.5.2. Cấu trúc khung

Nhằm cung cấp hỗ trợ mềm dẻo cho tất cả các trường hợp về chế độ và cấu hình đã nói trên, HDLC định nghĩa 3 dạng frame: frame thông tin (I-frame: information frame), frame giám sát (S-frame: supervisory frame) và frame không đánh số (unnumbered frame U-frame).

Hình 5.28. Các khung trong HDLC

Trong chương 4, chúng ta đã nghiên cứu về cấu trúc cơ bản của khung HDLC. Phần này chúng ta tìm hiểu kỹ trường điều khiển trong khung HDLC.

Trường điều khiển là đoạn gồm một hay nhiều byte của frame được dùng để quản lý.

Đầu tiên, khảo sát trường hợp một byte, rồi sẽ phát triển thành trường hợp 2 byte, được gọi là chế độ mở rộng.

Tùy theo dạng frame mà trường điều khiển có thể khác nhau.

- Nếu bit đầu tiên của trường điều khiển là 0, thì đó là I-frame.