Giáo trình Truyền số liệu - Chương 2: Điều khiển liên kết - Vũ Mạnh Khánh

Nội dung text: Giáo trình Truyền số liệu - Chương 2: Điều khiển liên kết - Vũ Mạnh Khánh

1. Một số khái niệm Truyền Số Liệu  Đồng bộ frame (Frame synchronization): Dữ liệu được gửi trong các khối gọi là các frame. Điều Khiển Liên Kết Điểm bắt đầu và kết thúc của frame phải nhận biết được.  Điều khiển lưu lượng (Flow control): trạm phát Giảng viên: Ths. Vũ Mạnh Khánh không được gửi các frame với tốc độ nhanh hơn khả năng nhận của trạm thu.  Điều khiển khắc phục lỗi (Error control): các bit lỗi được phát sinh bởi hệ thống truyền dẫn có thể được khôi phục. Một số khái niệm I. Điều khiển dòng  Gán địa chỉ (Addressing): Trên một đường truyền nhiều  Điều khiển lưu lượng là cơ chế điều khiển điểm (như mạng LAN) thì cần thiết phải định danh các trạm trong quá trình truyền. nhằm đảm bảo thực thể truyền dữ liệu  Dữ liệu và việc điều khiển trên cùng liên kết (Control and không làm thực thể nhận bị tràn bộ nhớ data on same link): không cần phải có một đường truyền khác biệt cho việc điều khiển thông tin mà chỉ cần trạm thu đệm. phải có khả năng phân biệt việc điều khiển đó từ dòng dữ liệu nhận được.  Quản lý liên kết (Link management): việc khởi tạo, duy trì và kết thúc của quá trình trao đổi dữ liệu đòi hỏi sự sắp xếp và phối hợp giữa các trạm làm việc một cách thích hợp. 1
2. Stop and Wait Stop and Wait  Trạm nguồn truyền một frame  Sau khi trạm đích nhận được frame nó sẽ thông báo sẵn sàng nhận frame tiếp theo bằng việc gửi lại một tín hiệu báo nhận rằng đã nhận được frame  Trạm nguồn sẽ đợi cho đến khi nó nhận được tín hiệu báo nhận trước khi gửi frame tiếp theo. Stop and Wait Stop and Wait  Ưu điểm  Nhược điểm  Thủ tục này làm việc khá tốt với số ít các frame có kích cỡ lớn. Trong trường hợp khối dữ liệu lớn cần truyền  Với một thông điệp sử dụng nhiều frame thì thủ thì trạm nguồn sẽ chia khối dữ liệu thành các khối nhỏ tục của Stop-and-Wait có thể không đầy đủ. hơn và truyền bằng các frame.  Kích cỡ bộ nhớ đệm của trạm thu có thể được giới hạn Bản chất của vấn đề là chỉ 1 frame tại một thời  Quá trình truyền lâu hơn nên có thể phát sinh lỗi và cần phải điểm được truyền. truyền lại frame, tuy nhiên do các frame nhỏ nên lỗi có thể phát hiện sớm hơn và lượng dữ liệu truyền lại là nhỏ hơn.  Trường hợp mà độ dài của liên kết (là số lượng  Với môi trường chia sẻ (như mạng LAN), nó sẽ không cho phép một trạm chiếm giữ môi trường truyền với thời gian kéo bit lấp đầy trong liên kết) lớn hơn độ dài của dài, vì sẽ phát sinh thời gian trễ lâu cho việc gửi thông tin của các trạm khác. Tức cơ chế này sẽ ngăn chặn được việc một frame thì thật sự kết quả không có hiệu quả. trạm chiếm dụng đường truyền lâu. 2
3. Sliding-Window Flow Control Sliding-Window Flow Control  Hai trạm A và B được kết nối theo liên kết truyền song công. Trạm B cấp phát bộ nhớ đệm và nhận frame W, còn A gửi các frame W nhưng không cần đợi tín hiệu báo nhận (ACK).  Để theo dõi các frame vừa báo nhận, mỗi frame được gán nhãn với một số tuần tự.  B báo nhận frame bằng việc gửi một tín hiệu báo nhận chứa số tuần tự của frame sẽ nhận tiếp.  Cơ chế này cũng có thể dùng để báo nhận nhiều frame. Ví dụ: B nhận frame 2,3 và 4 nhưng không báo  Trong khi đó, A phải duy trì một danh sách số tuần tự các frame mà nó đã gửi, và B duy trì một danh sách các số tuần tự mà nó đã sẵn sàng nhận.  Mỗi danh sách này có thể truyền qua của sổ các frame. Thao tác trên được hiểu là có chế điều khiển lưu lượng cửa sổ trượt. Sliding-Window Flow Control Sliding-Window Flow Control  Ưu điểm  Điều khiển lưu lượng cửa sổ trượt có khả năng hữu ích hơn điều khiển lưu lượng Stop-and- Wait. Vì nó đã xử lý như một đường ống (pipeline) để có thể lấp đầy frame trên đường truyền. Điều này hoàn toàn tương phản với Stop-and-Wait là tại một thời điển chỉ có 1 frame được truyền trong ống trên đường truyền 3
4. II. Dò tìm lỗi II. Dò tìm lỗi  Quá trình truyền vẫn phát sinh lỗi bất chấp sự thiết kế của các hệ thống truyền dẫn, đó là sự thay đổi một hoặc nhiều bit của frame truyền. II. Dò tìm lỗi Kiểm tra chẵn lẻ( parity bit)  Các loại lỗi trong truyền thông  Thêm một bit chẵn lẻ vào phần cuối của  Lỗi đơn bit : Trong một đơn vị dữ liệu có một khối dữ liệu. bit bị hỏng  Giá trị của bit này được chọn lựa sao cho ký  Lỗi đa bit : Trong một đơn vị dữ liệu có hai hay tự có các bit 1 là số chẵn (even parity) hoặc nhiều bít bị hỏng các bit 1 là số lẻ (odd parity).  Lỗi bit chùm (đảo bit) : Trong một đơn vị dữ liệu có hai hay nhiều bit liên tiếp bị lỗi 4
5. Kiểm tra chẵn lẻ( parity bit) Kiểm tra chẵn lẻ kép  Vd  Dữ liệu: 0111010101  Thêm bit chẵn lẻ: 0111010101 0  Bit chẵn lẻ thêm vào đảm bảo số bit 1 là một số chẵn  Bên nhận kiểm tra  Nếu có số chẵn các bit 1 thì dịch là không có lỗi  Nếu là một số lẻ các bít thì có nghĩa là chắc chắn có một lỗi xảy ra. Một lỗi đơn ( hoặc một số lẻ của lỗi) có thể được dò tìm. Một số chẵn các lỗi không được dò tìm. Mã dư vòng (CRC - Cyclic Redundancy Check) Mã dư vòng (CRC - Cyclic Redundancy Check)  Bên phát :Lấy toàn bộ dữ liệu được truyền đem  Cách lấy số chia: Dùng một số đa thức sinh chia cho một số chia, phần dư của phép tính này chính là CRC, CRC được đưa vào cuối dữ liệu  Bên nhận: Lấy toàn bộ dữ liệu nhận được (CRC + DL) đem chia cho một số chia như là bên gửi, kết quả của phép chia này cho biết dữ liệu đúng hay sai  Không dư : Dữ liệu nhận đúng  Dư : Dữ liệu nhận sai 5
6. Mã dư vòng (CRC - Cyclic Redundancy Check) Mã dư vòng (CRC - Cyclic Redundancy Check)  Cách thực hiện phép chia Để chia dữ liệu cho một số ta thực hiện như sau: Nếu số chia có n bậc ta thêm vào bên phải dữ liệu n-1 số 0 và thực hiện phép chia nhị phân. Số dư thu được từ phép chia này là CRC sẽ thay thế vào n-1 số 0. Ví dụ : ta có dữ liệu là 100100 số chia là 1101-> n=4 Check Sum Check Sum  Nơi gửi:Người ta chia dữ liệu ra làm n đoạn và cộng những  Nơi nhận: nhận được L+ dữ liệu cũng thực đoạn ấy với nhau theo phương pháp số học bù 1 được tổng là T. Lấy nghịch đảo của T ta được một số L chính là check hiện cộng theo phương pháp số học bù 1 các sum. L được đưa vào cuối đơn vị dữ liệu và gửi đi đến nơi dữ liệu nhận được . Nếu tổng các bậc đều có nhận giá trị “1” thì giá trị không bị lỗi 6
7. Check Sum( ví dụ) Check Sum( ví dụ) III. Sửa lỗi Phương pháp Hamming  Việc phát hiện lỗi và sửa lỗi đều đòi hỏi phải đưa thêm vào các bit dư thừa, về nguyên tắc người ta đều có thể phát hiện và sửa những bit bị lỗi.  Việc sửa phải đòi hỏi phải biết được vị trí của bit lỗi  Việc sửa là đảo ngược giá trị của bit đó  Về nguyên tắc : tự động phát hiện lỗi và sửa lỗi. 7
8. Phương pháp Hamming Phương pháp Hamming Phương pháp Hamming Phương pháp Hamming 8
9. IV. Điều khiển lỗi Stop-and-Wait ARQ  Mất frame: vì một lý do nào đó mà frame  Phương pháp này dựa trên nguyên tắc chung của kỹ thuật điều khiển lưu lượng stop-and-wait. gửi đã không đến được đích  Trạm nguồn truyền 1 frame và chờ tín hiệu ACK.  Hỏng frame: nhận được frame đến nhưng có  Hai loại lỗi xuất hiện: một số bit bị lỗi  frame đến được đích nhưng bị hỏng, tức là trạm đích dùng kỹ thuật phát hiện lỗi thấy lỗi và huỷ frame  Để giải quyết vấn đề này, trạm nguồn sử dụng một đồng hồ, và nếu sau khoảng thời gian timeout không nhận được tín hiệu ACK thì frame đó được truyền lại Stop-and- Stop-and-Wait ARQ Wait ARQ  Tín hiệu ACK khi gửi lại bị hỏng, tức là trạm đích đã nhận đúng frame và báo tin hiệu ACK, nhưng tín hiệu ACK bị hỏng nên trạm nguồn không nhận ra (hoặc không đến được)  Trường hợp này trạm nguồn cũng dùng thời gian timeout để truyền lại frame. Giả sử frame truyền lại này cũng đến đích và không bị lỗi, khi đó trạm đích sẽ nhận được 2 frame giống nhau. Để giải quyết vấn đề này, các frame được luân phiên gán nhãn 0 và 1, và tín hiệu ACK tương ứng là ACK1 và ACK0. Ở đây, ACK0 sẽ báo nhận của frame 1 và có với ý nghĩa thông báo là đã sẵn sàng nhận tiếp (frame 0). 9
10. Go-Back-N ARQ Go-Back-N ARQ  Phương pháp này dựa trên kỹ thuật điều khiển lưu  Khi trạm đích phát hiện một frame lỗi, nó sẽ lượng cửa sổ trượt (sliding-window). báo tín hiệu NACK (REJ - reject) cho frame  Trạm nguồn có thể gửi hàng loạt các frame tuần tự đó và sẽ huỷ bỏ mọi frame đến sau cho đến được đánh số. (Số frame không được báo nhận khi frame lỗi được nhận đúng. còn lại sẽ được chỉ ra bởi kích cỡ cửa sổ.)  Còn trạm nguồn khi nhận được tín hiệu REJ  Trạm đích sẽ báo tín hiệu (tín hiệu RR - receive ready hoặc kèm ACK - piggybacked ACK) các nó sẽ truyền lại frame lỗi và tất cả các frame frame đến bình thường nếu không có lỗi nào xuất đã truyền sau frame lỗi. hiện. Go-Back-N ARQ Hỏng frame  Sau mỗi frame truyền, trạm nguồn khởi tạo  Ta có 2 trường hợp nhỏ:  Trong chu kỳ thời gian hợp lệ, A gửi tiếp frame i+1, B giá trị timeout cho frame đó. Giả sử trạm nhận được i+1 nhưng không đúng thứ tự (do hỏng i) và đích (B) nhận thành công frame i-1 và trạm gửi REJ. A phải truyền lại i và tất cả các frame sau đó.  A không gửi tiếp frame i+1, nên B không nhận được gì nguồn (A) gửi tiếp frame i, ta có thể có các thêm và cũng không gửi tín hiệu hoặc RR hoặc REJ. Khi A đạt giá trị timeout, nó sẽ truyền một frame RR trường hợp lỗi sau: gồm 1 bit (được hiểu như bit P - Poll) được thiết lập giá trị 1. Khi đó, B hiểu frame RR với bit P=1 như là một  Hỏng frame: B sẽ huỷ frame i, ta có 2 trường lệnh yêu cầu phải gửi thông báo tín hiệu RR cho biết hợp nhỏ: sẵng sàng nhận frame tiếp theo là frame i. Và khi A nhận được tín hiệu RR nó sẽ truyền lại frame i.  Hỏng tín hiệu RR: Có 2 trường hợp: 10
11. Go-Back Hỏng tín hiệu RR -N ARQ  B nhận đúng frame i và báo RR sẵn sàng nhận i+1, nhưng tín hiệu RR bị mất.  Tức là A chỉ nhận được tuần tự các tín hiệu RR của các frame 1,2, ,i-1,i và vẫn không nhận được i+1 cho đến khi đạt giá trị timeout của i.  Khi A đạt giá trị timeout nó sẽ truyền một frame RR đặc biệt như trường hợp trên, và thiết lập giá trị timeout của P- bit (P=1). Nếu tín hiệu trả lời RR này của B cũng thất bại thì khi A đạt giá trị timeout của P-bit nó sẽ phát lại lệnh RR. Và tất nhiên sau một số lần nhất định phát lại lệnh RR mà vẫn không nhận được tính hiệu báo nhận thì A sẽ khởi tạo lại thủ tục truyền từ đầu. Selective- Reject Selective-Reject ARQ ARQ  Tương tự Go back N nhưng khi cần truyền lại thì các frame cần truyền lại chỉ là các frame có báo nhận NACK (ta gọi là tín hiệu SREJ) hoặc quá thời gian timeout  Ưu điểm: Đẩy lại có chọn lọc thực hiện hiệu quả hơn Go-Back-N, bởi vì nó truyền lại các frame là ít nhất.  Nhược điểm:duy trì một bộ nhớ tạm đủ để lưu các frame đến cho đến khi frame lỗi nhận đúng và phải tạo vị trí logic để chèn frame lỗi vào đúng thứ tự. Và trạm truyền cũng phải duy trì nhiều logic phức tạp để có thể gửi các frame không theo tuần tự. Chí 11