Bài giảng Truyền số liệu 4

Chia sẻ: Nguyễn Phước Lộc | Ngày: | Loại File: PPT | Số trang:39

Thêm vào BST

Báo xấu

179
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dữ liệu chia thành nhiều ký tự, mỗi ký tự có từ 5-8 bít (giao thức hướng ký tự). Ký tự đầu tiên của một khung dữ liệu chứa số lượng ký tự của khung dữ liệu. Tại đích, căn cứ vào số đếm để xác địng ranh giới các khung Khi có 1 lỗi bất kỳ, mất đồng bộ, không có khả năng tái lập lại, kể cả khi phát hiện ra có lỗi. Dùng để hỗ trợ các phương pháp khác (phát hiện lỗi)....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Truyền số liệu 4

Chương 4: Điều khiển liên kết dữ liệu 1. Chia khung dữ liệu Kiểm soát luồng dữ liệu 2. Phát hiện và sửa lỗi 3. Kiểm soát lỗi 4. Giao thức HDLC 5. Các giao thức khác 6. Bài tập 7. 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 1
Điều khiển liên kết dữ liệu Chưa có vấn đề nào  Truyền tín hiệu trên liên kết vật lý được giải quyết ở tầng  Truyền dữ liệu trên liên kết vật lý vật lý Nội dung chương 4  Thiết lập liên kết dữ liệu Chia khung   Truyền dữ liệu Kiểm soát lỗi   Giải phóng liên kết dữ liệu  Vấn đề cần giải quyết Kiểm soát luồng dữ liệu  Chia dữ liệu thành khung  HDLC: Giao thức kiểm  Kiểm soát luồng dữ liệu  soát dữ liệu bậc cao Kiểm soát lỗi   Các giao thức khác Đánh địa chỉ  Gộp dữ liệu điều khiển và dữ  liệu trên cùng một liên kết  Quản lí liên kết 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 2
1. Chia khung Dữ liệu cần chia thành từng khối để  đảm bảo đồng bộ vật lý  Bổ sung các bít kiểm tra để phát hiện và sửa lỗi  Bổ sung các thông tin điều khiển Tầng vật lý truyền một chuỗi bít không có cấu trúc.  Có thể chia khung sử dụng các bít đặc biệt Tầng liên kết dữ liệu có thể chia khung sử dụng  Khoảng lặng giữa các khung dữ liệu Không đảm bảo đồng bộ, dễ bị ảnh hưởng bởi nhiễu  Số đếm ký tự  Ký tự đặc biệt  Chuỗi bít đặc biệt 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 3
Dùng số đếm ký tự  Dữ liệu chia thành nhiều ký tự, mỗi ký tự có từ 5-8 bít (giao thức hướng ký tự)  Ký tự đầu tiên của một khung dữ liệu chứa số lượng ký t ự của khung dữ liệu  Tại đích, căn cứ vào số đếm để xác địng ranh giới các khung  Khi có 1 lỗi bất kỳ, mất đồng bộ, không có khả năng tái lập lại, kể cả khi phát hiện ra có lỗi  Dùng để hỗ trợ các phương pháp khác (phát hiện lỗi) 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 4
Dùng ký tự đặc biệt  Dùng một ký tự đặc biệt FLAG để phân tách các khung dữ liệu  Nếu trong dữ liệu có ký tự FLAG, chèn một ký tự đặc biệt khác vào trước (ESC), trước khi tạo khung dữ liệu  Nếu trong dữ liệu có ký tự ESC, chèn tiếp một ký tự ESC  Tại đích: khi nhận khung dữ •Giới hạn trong một bảng chữ liệu, cái  Căn cứ vào FLAG đứng riêng để chia khung •Dùng trong PPP cho liên kết  Loại bỏ các ký tự chèn thêm quay số  ESC FLAG=FLAG  ESC ESC=ESC 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 5
Dùng chuỗi bít đặc biệt Dùng một chuỗi bít đặc biệt để phân chia các khung dữ liệu  Ví dụ 01111110 Khi có chuỗi 01111110 (a) Dữ liệu ban đầu. trong dữ liệu (b) Dữ liệu truyền đi.  Nếu có 5 bit 1 liền nhau, . (c) Dữ liệu tại đích chèn 1 bít 0 vào sau Tại đích  Tách khung  111110 được chuyển thành 11111 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 6
2. Kiểm soát luồng dữ liệu Đảm bảo trạm nguồn không làm quá tải trạm đích Trạm đích  lưu trữ các khung dữ liệu trong bộ nhớ đệm  Thực hiện một số thao tác trước khi chuyển dữ liệu lên t ầng trên  Bộ nhớ đệm có thể bị đầy, dẫn tới mất khung dữ liệu Chưa đặt vấn đề lỗi truyền tin  Các khung dữ liệu luôn luôn được truyền chính xác  Độ trễ truyền tin không xác định Giải pháp  Cơ chế dừng và chờ  Cơ chế cửa sổ trượt 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 7
Cơ chế dừng và chờ  Nguyên tắc  Nguồn gửi một khung dữ liệu  Đích nhận khung dữ liệu, xử lí, sau đó thông báo sẵn sàng nh ận các khung dữ liệu tiếp theo bằng một thông báo báo nhận (acknowledgement)  Nguồn chờ đến khi nhận được báo nhận mới truyền tiếp khung dữ liệu tiếp theo  Ưu điểm  Đơn giản, đặc biệt thích hợp với các khung dữ liệu lớn  Nhược điểm  Với các khung dữ liệu nhỏ, thời gian sử dụng đường truyền bị lãng phí  Không thể sử dụng các khung dữ liệu lớn một cách phổ biến  Bộ nhớ đệm có hạn  Khung dữ liệu dài khả năng lỗi lớn  Trong môi trường truyền tin chia sẻ, không cho phép trạm nào chiếm d ụng lâu đường truyền 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 8
Cơ chế cửa sổ trượt Cơ chế dừng và chờ: chỉ cho phép truyền một khung dữ liệu Cơ chế cửa sổ trượt cho phép truyền nhiều khung dữ liệu cùng một lúc Xét hai trạm A, B kết nối bằng một đường truyền song công  B có bộ nhớ đệm n khung dữ liệu  Như vậy A có thể gửi cùng một lúc n khung dữ liệu mà không cần báo nhận Báo nhận  Để ‘nhớ’ các khung dữ liệu đã báo nhận, cần đánh số các khung dữ liệu  B báo nhận một khung bằng cách báo số khung dữ liệu mà B đang chờ nhận, ngầm định đã nhận tất cả các khung trước đó  Một báo nhận có thể dùng cho nhiều khung dữ liệu 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 9
Cơ chế cửa sổ trượt Cửa sổ  A quản lý một danh sách các số thứ tự khung được quyền gửi đi (cửa sổ gửi)  B quản lý một danh sách các số thứ tự khung đang chờ nhận (cửa sổ nhận)  -> cơ chế cửa sổ trượt  Số thứ tự khung dữ liệu có độ dài giới hạn, do đó cần được lấy modulo. Vd 3 bít-> modulo 8  Cửa sổ bị giới hạn bởi giá trị lớn nhất của số thứ tự Ví dụ 3 bít, cửa sổ gửi = cửa sổ nhận=8 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 10
Cơ chế cửa sổ trượt  Hình trên  Tại nguồn  Cận dưới của cửa sổ tăng lên khi gửi một (nhiều) khung dữ liệu  Cận trên của cửa sổ tăng lên khi nhận một (nhiều) báo nhận  Tại đích  Cận dưới của cửa sổ tăng lên khi nhận một (nhiều) khung dữ liệu  Cận trên của cửa sổ tăng lên khi gửi một (nhiều) báo nhận  Hình dưới  A có thể gửi 7 khung dữ liệu cùng một lúc từ F0  A gửi F0,F1,F2, giảm cửa sổ xuống còn 4  B có thể nhận 7 khung  B nhận F0,F1,F2 giảm CS còn 4  B xử lí xong F0,F1,F2, RR 3, tăng CS  A gửi F3,4,5,- giảm CS còn 3  B nhận F3, xử lí, gửi RR 4 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 11
Cơ chế cửa sổ trượt Kiểm soát luồng dữ liệu  Khi trạm B không có khả năng nhận thêm khung dữ liệu, CS nhận tin=0, B gửi thông báo RNR 5 Receive Not Ready  Sau khi B xử lí một số các khung dữ liệu trong bộ nhớ đ ệm, CS>0, B gửi RR x Receive Ready, báo nhận và chờ nh ận Trong trường hợp truyền tin hai chiều  A và B cùng truyền tin  Khi B cần báo nhận và cần truyền số liệu. B gửi kèm báo nhận trong khung dữ liệu: Piggybacking  Nếu không, B gửi một khung báo nhận riêng  Sau khi gửi báo nhận, nếu B truyền khung dữ liệu, B v ẫn đặt số báo nhận trong khung dữ liệu Cơ chế cửa sổ trượt hiệu quả hơn nhiều so với dừng và chờ! 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 12
3. Phát hiện và sửa lỗi  Vì sao phải phát hiện và sửa lỗi  Xác suất lỗi của một bít tương đối nhỏ  (P1=10-6)  Xác suất một khung dữ liệu 1000 bit không lỗi  (1-P1)1000~0,999  Xác suất lỗi của một khung dữ liệu  Một khung dữ liệu m bít, sử dụng thêm r  1- (1-P1)1000=10-3 Quá lớn! bít  Làm thế nào?  Một từ dữ liệu m bít được mã hóa bằng  Bổ sung một số bít (dư thừa) một từ mã m+r bít để phát hiện lỗi  Hai loại mã  Tại đích tính lại các bít bổ sung Mã phát hiện lỗi: Mã Hamming   Nếu hai giá trị bằng nhau: Mã sửa lỗi  không có lỗi  Parity bit (bít chẵn lẻ)  Nếu không, có lỗi, căn cứ vào  CRC (Cyclic Redundancy Check) mã vòng kết quả để phát hiện lỗi 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 13
Khoảng cách Hamming  Định nghĩa: Số các bít khác nhau giữa hai từ  Có 2m+r từ mã để mã hóa 2m từ dữ liệu  Có một số từ mã không sử dụng: từ mã không hợp lệ  Nguyên tắc phát hiện lỗi: khi có lỗi xảy ra, từ mã thu được không hợp lệ  Ví dụ:  Thêm một bít chẵn lẻ vào sau dữ liệu  Có một tập từ mã với khoảng cách =2  Khi có 1 bit lỗi, có một từ mã không hợp lệ-> phát hiện có lỗi  Nguyên tắc sửa lỗi: khi có lỗi xảy ra, luôn luôn xác định đ ược từ mã hợp lệ gần nhất.  Ví dụ  Dùng 4 từ mã 0000000000, 0000011111,1111100000, 1111111111  Mã hóa từ dữ liệu 2 bít 00,01,10,11  Khoảng cách giữa các từ mã 5  Sửa được 2 lỗi: khi có 2 lỗi, từ mã hợp lệ tương ứng có khoảng cách gần nhất  Vd khi nhận chuỗi bít 0000000111, mã hợp lệ là 0000011111 (2 bít lỗi) 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 14
Mã hamming sửa một lỗi  Giới hạn lý thuyết  từ dữ liệu có m bit, mã hóa bằng m+r bit  Có 2m từ mã hợp lệ, mỗi từ mã có m+r bit  Khi có một bít lỗi, có khả năng tạo ra m+r từ mã không hợp lệ có khoảng cách đến từ mã hợp lệ là 1  Tập hợp của các từ mã không hợp lệ tạo ra bởi 2 từ mã hợp lệ khác nhau phải rời nhau  Do đó 2m(m+r+1)
Mã hamming sửa một lỗi-ví dụ  Từ mã 15 bít, bít 1,2,4,8 là Số TT Số TT 1 2 4 8 checkbit (xem bảng). Mã hóa 0001 0010 0100 1000 từ dữ liệu 11 bit 1 0001 X  Bất cứ bít nào bị sai, các 2 0010 x 3 0011 X X check bít tương ứng sẽ bị đảo 4 0100 X 5 0101 X X  Căn cứ vào đó, đích sẽ biết 6 0110 X X được bít nào bị đảo để sửa 7 0111 X X X lỗi 8 1000 X  Thuật toán sửa lỗi 9 1001 X X  Tổng=0 10 1010 X X  Kiểm tra lần lượt các checkbit 11 1011 X X X  Nếu checkbit bị đảo, cộng số 12 1100 X X thứ tự của checkbit đó vào 13 1101 X X X tổng 14 1110 X x X  Kết thúc kiểm tra, tổng=0: không có lỗi, nếu tổng0 là 15 1111 x X X X 10/07/11ố @Hà ự cốc Trung i2004. Chương 4: Điều khiển liên kết dữ liệu s thứ t Qu ủa bít lỗ 16
Mã hamming sửa một chuỗi lỗi liên tiếp  Thường các bit lỗi hay xảy ra liên tiếp  Mã hamming chỉ sửa được một lỗi  Để sửa k lỗi liên tục  truyền cùng một lúc k từ mã mã hóa bằng mã hamming  K từ mã này được xếp thành ma trận bit  Ma trận này được truyền theo từng cột.  Tại đích, ma trận được nhận, tái tạo lại các từ mã  Trường hợp xấu nhất, khi có k bít liên tiếp bị truyền lỗi, mỗi từ mã chỉ có đúng 1 bít Dùng kr checkbit cho km bit dữ lỗi liệu, sửa được một lỗi gồm tối đa  Bằng mã Hamming, sửa k bít liên tiếp được lỗi cho mỗi từ 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 17
Mã phát hiện lỗi Sửa lỗi đòi hỏi một số bít bổ sung Nếu tỷ lệ lỗi nhỏ, các bít bổ sung đó bị lãng phí Khi tỷ lệ lỗi nhỏ, giải pháp tốt hơn là truyền lại cả khung dữ liệu. Ví dụ: Tỷ suất lỗi 10-6  Truyền 1Mb bằng khung dữ liệu mã sửa lỗi hamming độ lớn 1000 bit Cần 10 checkbit bổ sung cho mỗi khung dữ liệu. Tổng cộng 10.000bit cho 1Mb  Nếu dùng 1 bít chẵn lẻ cho 1000 bít, khi truyền 1Mb có 1 l ỗi Tổng cộng dùng thêm 1x1000+1001=2001 bít Do đó khi tỷ suất lỗi nhỏ, sử dụng các mã phát hiện lỗi  Parity check (bít chẵn lẻ)  Mã vòng (Cyclic redundancy check-CRC) 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 18
Bít chẵn lẻ (Parity checkbit) Thêm một bít vào cuối khung dữ liệu.  Giá trị của bit đảm bảo số bít 1 trong khung dữ liệu luôn là số chẵn  Khi có một bít bị lỗi, tính chẵn lẻ bị thay đổi, phát hiện ra lỗi Nếu có một chuỗi bít liên tiếp bị lỗi, xác suất phát hiện ra lỗi là 0.5 Có thể dùng kỹ thuật ma trận giống như với mã hamming để phát hiện k lỗi liên tiếp  Khi truyền lại cần truyền cả k khối dữ liệu 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 19
Mã vòng Nguyên tắc: thêm r bít (FCS Frame Check Sequence) vào m bít dữ liệu  số nhị phân m+r bít chia hết cho một số nguyên xác định trước Khi nhận được khung dữ liệu, chia cho số nguyên trên. Nếu không còn dư tức là không có lỗi  Trong trường hợp có lỗi, giá trị của dữ liệu bị sai lệch m ột số E nào đó  Lỗi luôn được phát hiện, chỉ trừ khi E chia hết cho số nguyên trên (hiếm) Giải thuật  Mô tả bằng phép toán nhị phân  Mô tả bằng phép toán đa thức  Mô tả bằng mạch logíc số 10/07/11 @Hà Quốc Trung 2004. Chương 4: Điều khiển liên kết dữ liệu 20