Mạng máy tính - Chương 4: Lớp liên kết dữ liệu

Chương 4 – lớp Liên Kết Dữ LiệuKhoa Khoa Học Máy TínhTrường Cao Đẳng Công Nghệ Thông Tin Hữu Nghị Việt HànChương 4. Lớp liên kết dữ liệuVấn đề nghiên cứu:nguyên tắc tổ chức lớp liên kết dữ liệu với các thuật toán để đạt được độ tin cậy và hiệu quả truyền tin giữa 2 máy trạm liền kề. giao thức, phương pháp dò tìm và xử lý lỗi của lớp này.4.1 Vai trò, chức năngLớp liên kết dữ liệu có các chức năng chính sau:Cung cấp dịch vụ cho lớp MạngKhắc phục lỗi đường truyềnĐiều khiển luồng dữ liệu để tránh trường hợp tràn dữ liệu Để thực hiện được các nhiệm vụ này, lớp liên kết dữ liệu nhận các gói dữ liệu từ Lớp Mạng và định dạng thành các khung dữ liệu để truyền đi. Mỗi khung gồm phần mào đầu, tải tin và phần đuôi khung 4.1.1 Cung cấp dịch vụ cho lớp mạngLớp liên kết dữ liệu có khả năng cung cấp nhiều dịch vụ khác nhau cho lớp mạng. Các dịch vụ này khác nhau trong các hệ thống khác nhau. Có 3 dịch vụ cơ bản như sau:Dịch vụ truyền tin phi kết nối - không phúc đáp.Dịch vụ truyền tin phi kết nối - có phúc đáp.Dịch vụ truyền tin có kết nối – có phúc đáp 4.1.1 Cung cấp dịch vụ cho lớp mạngDịch vụ truyền tin phi kết nối - không phúc đáp gửi các khung dữ liệu độc lập không cần xác nhận không cần thiết lập kênh logic trước khi truyền dữ liệu và giải phóng kênh truyền sau khi kết thúc.Nếu khung dữ liệu nào bị mất do tạp âm đường truyền thì lớp liên kết dữ liệu cũng không cần dò tìm và khôi phục lại.  Loại dịch vụ này sử dụng ở môi trường truyền dẫn có tỷ lệ lỗi thấp hoặc đối với các dữ liệu thời gian thực như truyền thanh, yêu cầu đáp ứng về thời gian nhiều hơn là chất lượng dữ liệu. 4.1.1 Cung cấp dịch vụ cho lớp mạngDịch vụ truyền tin phi kết nối - có phúc đápcó độ tin cậy cao hơn. không sử dung kênh logic để truyền dữ liệu nhưng mỗi khung dữ liệu truyền đi sẽ được xác nhận đầu phát có thể biết được khung dữ liệu đã đến đúng đích nhận hay chưa. Nếu khung dữ liệu chưa đến trong một khoảng thời gian nhất định thì nó sẽ được gửi lại. Dịch vụ này thường được dùng trong các kênh dữ liệu có độ tin cậy thấp như các hệ thống không dây. 4.1.1 Cung cấp dịch vụ cho lớp mạngdịch vụ truyền tin có kết nối. Phức tạp nhấtthiết lập kết nối được yêu cầu trước khi truyền dữ liệu. Mỗi khung dữ liệu trên kênh truyền được gán số thứ tự và lớp liên kết dữ liệu đảm bảo rằng khung dữ liệu này đã được nhận ở đầu thu.Ngoài ra, lớp liên kết dữ liệu còn đảm bảo rằng khung dữ liệu này chỉ nhận một lần và theo đúng thứ tự.4.1.2 Tạo khung dữ liệuKhung dữ liệuLớp liên kết dữ liệu làm việc dựa vào khả năng chuyển tải của lớp Vật lý. Các bít thông tin truyền đi hoặc nhận về đều được nhóm lại thành những đơn vị logic gọi là khung (frame). Trong khung dữ liệu, ngoài các bit thông tin, còn chứa các trường địa chỉ, trường điều khiển, trường nhận biết, trường kiểm soát lỗi 4.1.2 Tạo khung dữ liệuCác phương pháp tạo khung dữ liệu Quá trình truyền thông tại lớp LKDLtách luồng bit thành các khung dữ liệu tính toán giá trị kiểm tra tổng (checksum) của mỗi khungKhi khung dữ liệu đến đích nhận, giá trị checksum này sẽ được tính toán lại và so sánh với giá trị checksum nhận được của đầu phát để xác định khung dữ liệu này có bị lỗi trong quá trình truyền hay không4.1.2 Tạo khung dữ liệuViệc tách luồng bit thành các khung dữ liệu được thực hiện bởi một trong số các phương pháp sau:Đếm số ký tự.Dùng cờ hiệu (flags) kết hợp với byte nhồi.Dùng cờ hiệu bắt đầu và kết thúc, kết hợp với bit nhồi.Dựa vào kỹ thuật mã hóa của lớp vật lý.4.1.2 Tạo khung dữ liệuPhương pháp đếm số ký tự sử dụng một trường trong phần mào đầu (header) để xác định số ký tự trong một khung. Khi lớp liên kết dữ liệu ở đầu nhận xác định được thông tin này thì nó sẽ biết được có bao nhiêu ký tự trong một khung và vị trí cuối cùng của khung. Nhược điểm: giá trị của trường đếm số ký tự có thể sai lệch do lỗi đường truyền 4.1.2 Tạo khung dữ liệuPhương pháp thứ 2, phương pháp sử dụng cờ hiệu kết hợp với byte nhồi, byte cờ hiệu (flag byte) để phân biệt điểm bắt đầu và kết thúc một khung dữ liệu byte cờ hiệu giúp xác định vị trí kết thúc của khung dữ liệu hiện tại trong trường hợp mất đồng bộ.xác định vị trí kết thúc một khung dữ liệu và bắt đầu một khung mới bằng hai byte cờ hiệu liên tiếpkỹ thuật nhồi byte (byte stuffing) hoặc nhồi ký tự (character stuffing). Hiện tượng trùng lắp byte cờ hiệu  giải quyết bằng cờ byte escape (ESC) được chèn trước cờ hiệu giả. 4.1.2 Tạo khung dữ liệuCơ chế giải quyết cờ “giả” bằng byte stuffingPhương phát này được dùng trong giao thức PPP Nhược điểm là sử dụng các từ mã cố định 8 bit4.1.2 Tạo khung dữ liệuPhương pháp chia khung không cố định: Cờ hiệu là 01111110 Nếu đầu phát có dữ liệu 111111  1111101Đầu thu nhận được dữ liệu 1111101  1111114.1.2 Tạo khung dữ liệuPhương pháp thứ tư, phương tách khung dựa vào kỹ thuật mã hóa của lớp vật lý chỉ được áp dụng đối với các mạng sử dụng thêm các bit khi mã hóa dữ liệu. Ví dụ, một số mạng LAN mã hóa 1 bit dữ liệu bằng 2 bit vật lý, thông thường bit 1 được đại diện bằng cặp trạng thái (cặp bit) là cao - thấp và bit 0 được đại diện bằng cặp trạng thái là thấp – cao. Như vậy, người ta dùng cặp trạng thái cao – cao và thấp – thấp không dùng cho việc biễu diển dữ liệu để phân biệt ranh giới giữa các khung dữ liệu. 4.1.2 Tạo khung dữ liệuTóm lại, đối với việc tạo khung dữ liệu ở nhiều giao thức người ta sử dụng kết hợp phương pháp đếm số ký tự kết hợp với các phương pháp còn lại nhằm đảm bảo độ an toàn cho dữ liệu. Tại đầu thu, người ta dùng giá trị của trường đếm số ký tự để xác định vị trí kết thúc của khung dữ liệu, nếu cờ hiệu xuất hiện đúng vị trí và giá trị kiểm tra tổng (checksum) đúng thì khung dữ liệu được chấp nhận. Ngược lại, hệ thống sẽ tìm kiếm vị trí bắt đầu của khung tiếp theo dựa vào cờ hiệu 4.1.3 Kiểm soát lỗiMục đích: tất cả các khung dữ liệu đã truyền đến được lớp mạng của đầu thu dữ liệu theo đúng trật tự Phương pháp: Sử dụng các thông điệp từ đầu thu để báo cho đầu phát thông điệp đã được gửi thành công hay chưaThông báo Possitive Acknowledgement – ACK: Thông điệp gửi thành côngThông báo Negative Acknowledgement – NAK: Thông điệp gửi không thành côngGiải quyết sự cố liên quan đến chờ ACK/NAK từ phía đầu thu quá lâu, dẫn đến quá hạn (timed – out) hay nhận/ gửi một gói tin nhiều lần: Kết hợp bộ định thời nơi phát cho mỗi gói tin và đánh số thứ tự cho mỗi gói tin.4.1.4 Điều khiển luồngMục đích: Giải quyết tình trạng mất đồng bộ trong truyền thông giữa phía đầu phát và đầu thu.Phương pháp xử lý:điều khiển luồng sử dụng hồi tiếp (feedback-based flow control), đầu thu sẽ gửi thông tin phản hồi về cho đầu phát để báo cho đầu phát biết có nên tiếp tục phát dữ liệu nữa hay không hoặc nó sẽ báo cho đầu phát biết rằng quá trình nhận dữ liệu đang diễn như thế nào  Phương pháp phổ biến: trong giao thức chứa các các luật được định nghĩa sẵn qui định thời điểm mà đầu phát dữ liệu sẽ phát khung dữ liệu tiếp theo điều khiển luồng dựa vào tốc độ dữ liệu (rate-based flow control), trong phương pháp này giao thức sẽ có một cơ chế để hạn chế tốc độ phát dữ liệu ở đầu phát mà không cần thông tin phản hồi từ đầu thu 4.2 Phương pháp dò tìm và sửa lỗiCác loại lỗi:Lỗi đơn: Lỗi chỉ một bit, một đơn vị dữ liệu  dễ xảy ra, dễ phát hiện và sửa chữaLỗi chùm: Lỗi trên nhiều bit, nhiều đơn vị dữ liệu  khó xảy ra, khó phát hiện và sửa chữa.Biện pháp khắc phục lỗi:Kiểm soát lỗi hướng tới:bổ sung thêm các thông tin vào mỗi khối dữ liệu cho phép đầu thu xác định được thông tin nhận được có bị lỗi hay không và chỉ ra vị trí của lỗi đó Kiểm soát lỗi quay lui: chỉ thêm vào các trường thông tin cho phép đầu thu nhận biết khung dữ liệu nào bị lỗi và yêu cầu phát lại khung dữ liệu đó mà không chỉ ra vị trí lỗi 4.2 Phương pháp dò tìm và sửa lỗiKhung dữ liệu: m bit chứa bản tin và r bit chứa thông tin kiểm tra, do đó chiều dài của khung dữ liệu là n = m + r.m bit thông tin  2m bản tin có nghĩan bit dữ liệu  2n bản tin dữ liệuKhoảng cách Hamming: Số bit khác nhau giữa hai từ mã. Từ 2n tổ hợp dữ liệu chúng ta tạo ra danh mục các từ mã được sử dụng cho truyền thôngVí dụ hai từ mã sau đây: 10001001 và 10110001 có khoảng cách mã Hamming là 3.4.2 Phương pháp dò tìm và sửa lỗiTính chất dò tìm lỗi và sửa lỗi của một mã phụ thuộc vào khoảng cách Hamming của mã đó.Để dò được d lỗi  cần mã có khoảng cách Hamming là d+1Để sửa được d lỗi  cần mã có khoảng cách 2d+1Ví dụ n=10, chúng ta có tất cả 210 các giá trị. Chọn các từ mã sau đây để làm mã truyền thông: 0000000000; 0000011111; 1111100000; 1111111111.  Khoảng cách Hamming là 5  mã này dò được 4 lỗi  mã này sửa được 2 lỗi4.2 Phương pháp dò tìm và sửa lỗiNếu đầu phát gửi đi từ mã 0000011111 đến đầu thu kiểm tra kết quả là 0000011100 (sai 2 bit) thì từ mã 0000011111 có thể sửa sai được vì khoảng cách Hamming của nó đến từ mã gốc gần nhất 0000011111  0000011100 là 2 có thể phát hiện được.Trong trường hợp đầu thu nhận được 0000011000 thì không thể sửa sai được vì khoảng cách Hamming của nó đến các từ mã gốc là không thể phát hiện được0000011000 0000011111=30000011000 0000000000=24.2.1 Phương pháp dò lỗi Parity CheckDựa vào từ mã quy ước giữa đầu phát và đầu thu là chẵn/ lẻ, đầu phát sẽ chèn thêm 1 bit kiểm tra chẵn/ lẻ tương ứng. Bit này là 0 hoặc 1 để đạt được từ mã có giá trị chẵn/ lẻ đã quy ước.Ví dụ hệ thống quy ước sử dụng từ mã chẵn.Nếu dữ liệu là 01100010 chèn thêm bit 1  011000101: từ mã chẵnNếu dữ liệu là 01101010 chèn thêm bit 0  011010100: từ mã chẵn.Phía đầu thu sẽ căn cứ vào từ mã thu được, kiểm tra nó:Nếu chẵn: Dữ liệu đúng hoặc bị lỗi với khoảng cách Hamming là bội số của 2Nếu lẻ: Dữ liệu chắc chắn sai.Nếu đúng, đầu thu loại đi bit kiểm tra và lấy dữ liệu cuối4.2.2 Phương pháp kiểm dư vòng (CRC- Cyclic Redundancy Check) Đặc điểm:Đây là một phương pháp dùng để dò lỗi, không có tác dụng sửa lỗi, thường được sử dụng phổ biến khi môi trường truyền dẫn có chất lượng cao, ít lỗi như cáp đồng, cáp quang.Phương pháp này khai thác đặc trưng của các số nhị phân khi dùng phép toán modulo-2 để tính toán ra giá trị checksum. Giả sử M(x) là một số m bit cần truyền, G(x) là đa thức sinh có bậc r (phần tử chia) 4.2.2 Phương pháp kiểm dư vòng (CRC- Cyclic Redundancy Check)Các bước tiến hànhBước 1: Thêm r bit 0 vào cuối chuỗi bit cần truyền. Xâu ghép có (m+r) bit, tương ứng với đa thức xr M(x).Bước 2: Chia modulo-2 chuỗi bit tương ứng với xr M(x) cho chuỗi bit tương ứng với G(x).Bước 3: Lấy số bị chia trong bước 2 trừ (modulo-2) cho số dư.Kết quả chuỗi bit được truyền đi sẽ là chuỗi gốc ghép với checksum tính được ở trên1101011011 và đa thức sinh G(x) = x4 + x +1, ta tính toán được giá trị checksum và chuỗi bit truyền đi như sau 4.2.2 Phương pháp kiểm dư vòng (CRC- Cyclic Redundancy Check)Dữ liệu gửi 1101011011Đa thức sinh 10011  bậc 4 cần chèn 4 bit 0 vào dữ liệuChuỗi sau khi được chèn: 11010110110000Lấy phép chia của 11010110110000 cho đa thức sinh 10011 kết quả số dư là 1110Chuỗi được truyền đi là: 110101101111103 đa thức sinh được sử dụng phổ biến:CRC-12= x12+x11+x3+x2+x+1CRC-16= x16+x15+x2+1CRC-CCITT= x16+x12+ x5+14.3 Điểu khiển luồng bằng cửa sổ trượtYêu cầu thực tế: Truyền dữ liệu đồng thời ở cả hai phía đầu cuối, cần có:Một kênh dành cho dữ liệuMột kênh dành cho điều khiểnLãng phí băng thông dành cho kênh điều khiểnKhắc phục:Sử dụng cùng kênh truyền cho dữ liệu cả hai hướngKhung dữ liệu được trộn với khung phúc đáp trên một hướng truyền, và phân biệt với nhau qua loại khung dữ liệu4.3 Điểu khiển luồng bằng cửa sổ trượtCơ chế piggybacking: Khi nhận một khung dữ liệu, thay vì phản hồi tức thì, máy thu đợi nhận một gói tin từ lớp mạng của nó, đính kèm trường ACK vào gói tin đó trong tiêu đề khung để gửi cho máy phát. Kết quả là phúc đáp được gửi đi mà không cần tốn băng thông đường truyền.Tiết kiệm băng thông nhiều hơn so với sử dụng một khung phúc đáp riêng rẽ.Vấn đề đặt ra là máy thu phải đợi bao lâu trước khi nó gửi phúc đáp cho máy phát? Nếu quá lâu máy phát sẽ tự động gửi lại gói tin ban đầuGiải quyết: sử dụng bộ định thời để xác định thời điểm trễ hạn bắt buộc phải phúc đáp, nếu máy thu không có gói tin muốn truyền dữ liệu cho máy phát.4.3 Điểu khiển luồng bằng cửa sổ trượtKỹ thuật cửa sổ trượt: là một chuỗi các khung dữ liệu liền kề nhau được phát đi mà chưa có phúc đáp. Khi nhận xong các khung dữ liệu trong một cửa sổ, đầu thu sẽ dịch chuyển hay “trượt” cửa sổ này lên một đơn vị để nhận tiếp các khung dữ liệu trong cửa sổ tiếp theo vì vậy người ta gọi kỹ thuật này là kỹ thuật cửa sổ trượt. Cả đầu phát và đầu thu đều sử dụng cửa sổ trượt khi truyền dữ liệu, cửa sổ trượt ở đầu phát gọi là cửa sổ truyền (Sending Window) và cửa sổ trượt ở đầu thu gọi là cửa sổ thu (Receiving Window).4.3 Điểu khiển luồng bằng cửa sổ trượtTrong trường hợp tổng quát, hai cửa sổ này không nhất thiết phải có cùng chung giá trị cạnh trên và cạnh dưới trong cùng một thời điểm cũng như không nhất thiết phải có cùng chung kích thước.Các số thứ tự trong cửa sổ truyền cho biết số khung đã được gửi đi song chưa có phúc đáp.Do các khung này có thể bị thất lạc hoặc bị hư hỏng trong quá trình truyền nên chúng phải được lưu vào trong bộ nhớ của đầu phát để khi cần có thể truyền lặp lại 4.3 Điểu khiển luồng bằng cửa sổ trượt4.3 Điểu khiển luồng bằng cửa sổ trượtNhư vậy, nếu kích thước lớn nhất của cửa sổ là n thì nó phải có ít nhất n vùng đệm để lưu n khung chưa có phúc đáp. Còn ở bên thu, với kích thước cửa sổ là hữu hạn nên khi số lượng khung đến vượt quá giá trị của cửa sổ thì cách đơn giản nhất và cũng thông dụng nhất là hủy các khung này và bắt buộc đầu phát truyền lặp lại. Khung đến có số thứ tự trùng với cạnh dưới của cửa sổ thu sẽ được chấp nhận, dữ liệu của nó (gói) được chuyển lên lớp mạng và phúc đáp được tạo ra, đồng thời cửa sổ dịch lên một đơn vị. Cửa sổ thu, khác với cửa sổ phát, luôn luôn không đổi về giá trị. Trong quá trình này, đầu thu luôn phải nhớ rằng nó phải nhận các khung theo đúng thứ tự mà đầu phát truyền lên kênh.4.3.2 Thủ tục cửa sổ trượt (Sliding Window) có kích thước một bit Giả thiết rằng đầu phát luôn có khung dữ liệu để truyền, nói cách khác là lớp điều khiển dữ liệu luôn có sẵn các gói dữ liệu do lớp mạng cung cấp để thực hiện phép truyền liên tục. Chiến lược truyền lặp ARQ được kết hợp với cửa sổ để điều khiển số lượng khung lưu thông trên đường truyền giữa A và B. Mô hình ARQ đơn giản nhất là ARQ dừng - đợi, có nghĩa là sau khi đầu phát đã truyền đi một khung dữ liệu, nó dừng lại và đợi phúc đáp của bên thu. Nhận được phúc đáp nó mới gửi tiếp khung tiếp theo. Như vậy, ta thấy ngay, thực tế đây cũng chính là mô hình cửa sổ trượt với kích thước cửa sổ bằng 1.4.3 Điểu khiển luồng bằng cửa sổ trượtBan đầuSau khi gói thứ nhất được gửiSau khi nhận gói thứ nhấtSau khi phúc đáp thứ nhất trở lại4.3 Điểu khiển luồng bằng cửa sổ trượtTrao đổi bản tin với cửa sổ 1 bit như sau:Máy A ở tầng 2 nhận gói dữ liệu từ tầng 3, tạo bản tin gửi đi. Khi bản tin này đến tầng 2 máy B, nó sẽ tự kiểm tra xem có bị lặp lại không. Nếu đúng là bản tin đang mong đợi thì nó được chuyển lên tầng 3 và cửa sổ dịch đi một nấc. Vùng ACK chứa số bản tin cuối đã được nhận không lỗi. Nếu số này trùng với số bản tin vừa gửi, đầu phát sẽ lấy gói dữ liệu tiếp theo từ lớp mạng. Nếu số không đúng nó phải gửi lại bản tin cũ.Với thuật toán dùng cửa sổ có kích thước bằng 1, phần lớn thời gian sau khi đã truyền xong một khung A và B phải đợi phản hồi ngược lại mới có thể truyền tiếp được khung khác nên hiệu quả phép truyền không thể cao được. Để sử dụng kênh truyền hiệu quả hơn cần có các thuật toán khác với kích thước cửa sổ lớn hơn.4.3 Điểu khiển luồng bằng cửa sổ trượtNhư giới thiệu ở trên, khi thiết lập việc truyền tin giữa hai đầu cuối ta phải quan tâm tới trễ truyền dẫn của các gói trên đường truyền để sử dụng kênh một cách có hiệu qủa. Giả thiết dung lượng kênh là b bit/s, kích thước của khung là 1 bit và trễ truyền dẫn theo vòng kín (từ đầu phát đến đầu thu và ngược lại) là R giây với R/2 giây cho mỗi chiều. Trong thuật toán sử dụng ARQ dừng và đợi, thời gian đường dây bận là 1/b và thời gian rỗi là R, hiệu dụng của đường dây là 1/(1+bR). 4.3 Điểu khiển luồng bằng cửa sổ trượtNếu 1< bR thì độ hiệu dụng không vượt quá 50%, mà trễ truyền dẫn bao giờ cũng có, nên ta có thể dùng thuật toán có kích thước cửa sổ truyền lớn hơn 1. Hay còn gọi là kỹ thuật tạo đường ống (Pipelining). Các khung pipelining khi được truyền lên kênh không tin cậy có thể làm nảy sinh một số vấn đề cần giải quyết. Nếu một khung nằm giữa luồng trên tuyến bị hỏng hoặc mất thì khi khung hỏng này đến, đầu thu sẽ hủy nó và gửi NAK cho bên phát, nhưng các gói đến tiếp sau đó thì phải làm gì với chúng, trong khi mô hình của chúng ta yêu cầu lớp liên kết dữ liệu thu phải đưa các khung lên lớp mạng theo thứ tự.4.3 Điểu khiển luồng bằng cửa sổ trượtTa có hai cách giải quyết vấn đề lỗi khi sử dụng pipeline:Cách thứ nhất, gọi là ARQ phát lại gói N, đầu thu hủy toàn bộ các gói đứng sau khung bị hỏng bằng cách không phúc đáp. Nó tương ứng với trường hợp cửa sổ thu bằng 1. Cuối cùng thì bên phát, sau khoảng thời gian Timeout, sẽ gửi lại cho đầu thu tất cả những gói dữ liệu chưa được xác nhận bắt đầu từ gói dữ liệu hỏng thứ N. Cách thứ hai, gọi là ARQ phát lại có chọn lọc, cho phép đầu thu lưu toàn bộ các khung đến nguyên vẹn đến sau khung hỏng trong bộ đệm của mình. Khi đầu phát nhận thấy có sự cố, nó chỉ truyền lặp lại khung hỏng mà thôi, còn đầu thu nếu nhận được khung này lần thứ hai không có lỗi thì lớp liên kết dữ liệu của nó chỉ việc xếp đặt lại các khung theo thứ tự và gửi các khung tương ứng lên cho lớp mạng 4.3 Điểu khiển luồng bằng cửa sổ trượtKỹ thuật yêu câu phát lại tự động từ gói dữ liệu hỏng thứ NKỹ thuật yêu cầu phát lại tự động có chọn lọc 4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói N Hai phương pháp này cho thấy sự tương phản giữa hiệu suất sử dụng băng thông và dung lượng của bộ đệm lớp liên kết dữ liệu. Tùy theo khả năng và mức độ yêu cầu để sử dụng phương pháp này hay phương pháp khác.Ngoài ra, do các phương pháp kể trên cho phép gửi nhiều gói trong phạm vi của cửa sổ nên cũng cần nhiều bộ đếm thời gian để xác định Timeout cho từng gói. Thông số này thường được mô phỏng trong chương trình phần mềm có sử dụng đồng hồ phần cứng để tạo các ngắt theo chu kỳ 4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói NPhương pháp ARQ phát lại gói dữ liệu hỏng thứ N tỏ ra rất hữu hiệu khi tỉ lệ lỗi thấp hoặc đường truyền có chất lượng tốt, còn khi đường truyền có chất lượng xấu thì nó làm lãng phí rất nhiều băng thông vì các khung đến sau khung hỏng sẽ bị hủy và truyền lặp lại, khi đó người ta nên dùng phương pháp có sử dụng ARQ phát lại có chọn lọc.Trong phương pháp này, cửa sổ truyền bắt đầu từ kích thước bằng 0 tăng dần đến MaxSeq, còn cửa sổ thu luôn giữ giá trị bằng MaxSeq không đổi. Đầu thu có bộ đệm lưu từng số thứ tự nằm trong giới hạn cửa sổ của nó, ứng với mỗi bộ đệm này là 1 bit đến cho biết là bộ đệm đang trống hay đã bị chiếm. Khi một khung mới đến, số thứ tự của nó được kiểm tra xem nó có nằm trong phạm vi cửa sổ hay không, nếu đúng là khung này không trùng với khung nào khác đến trước thì nó được chấp nhận và lưu vào đệm. Sau khi đã nhận hết tất cả các khung trong phạm vi cửa sổ của mình, lớp liên kết dữ liệu sẽ gửi các gói cho lớp mạng theo đúng thứ tự truyền đi của chúng.4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói NTuy vậy, việc nhận các khung không theo thứ tự cũng làm nảy sinh một vấn đề cần phải giải quyết: Thí dụ, MaxSeq =7, đầu phát gửi các gói từ 0 đến 7 lên kênh, đầu thu nhận được đầy đủ và không có lỗi, nó phúc đáp lại cho đầu phát và dịch cửa sổ của mình đi một đơn vị để nhận các khung mới, bắt đầu từ khung số 0. Song trên đường trở lại bên phát, sự cố xảy ra, ví dụ dưới dạng sét đánh vào đường dây thoại, làm mất toàn bộ các ACK mà đầu thu gửi. Đầu phát sau khoảng Timeout sẽ truyền lặp lại các khung kể trên, nếu là số thứ tự của chúng lại nằm trong phạm vi cửa sổ thu thì toàn bộ số khung này được chấp nhận. Như vậy là đầu thu nhận hai lần cùng một thông tin. Nguyên nhân của việc này là cửa sổ mới cho phép các số thứ tự trùng với cửa sổ trước đó. Để tránh trường hợp kể trên, người ta chỉ cho phép cửa sổ có kích thước lớn nhất là bằng nửa tổng số thứ tự các khung mà thôi, tức là bằng (MaxSeq+1)/2.4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói NVí dụ, nếu ta dùng 4 bit để đánh số thứ tự thì có thể truyền các khung có số thứ tự từ 0 đến 15, nhưng chỉ có nhiều nhất là 8 khung cùng được truyền lên kênh.Áp dụng cho ví dụ trên, ta thấy đầu thu có thể phát hiện ngay được đâu là khung truyền lặp (từ 0 đến 7) và đâu là khung mới (từ 8 đến 15). Trong khi đó số đệm thu vẫn giữ nguyên (bằng 8). Khi một khung i tới, nó được đặt trong đệm số i mod 8, mặc dù khung i và khung i+8 sử dụng chung một đệm, song thực tế chúng không bao giờ cùng được nằm trong cùng một cửa sổ.4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói NTrong thuật toán sử dụng ARQ lùi lại gói N, ta giả thiết đầu thu cũng có thông tin cần phải trao đổi với đầu phát, nên các phúc đáp không được gửi ngay mà đợi một thời gian để dùng kỹ thuật piggyback. Nhưng nếu đầu thu không có nhu cầu này thì trong thuật toán dùng ARQ phát lại có chọn lọc, ta dùng thêm thủ tục tính thời gian mà đầu thu có thể đợi lớp mạng của mình gửi gói xuống, nếu không có thì nó sẽ tự động tạo ra khung phúc đáp riêng cho khung dữ liệu đã đến để không làm gián đọan họat động chung. Một cải tiến nữa trong thuật toán này là việc sử dụng phúc đáp NAK khi đầu thu nhận được khung có lỗi, giúp cho đầu phát có thể truyền lặp lại nhanh hơn so với việc đợi Timeout. Để tránh không gửi nhiều NAK cho cùng một khung có lỗi ta sử dụng cờ NoNak.4.3.4 Đánh giá hiệu quả ARQ phát lại có chọn lọc và ARQ phát lại gói NTóm lại, việc xảy ra lỗi trong quá trình truyền dữ liệu trong mạng máy tính là điều không thể tránh khỏi, nó làm giảm tốc độ truyền dữ liệu, thậm chí trong một số trường hợp nó gây tắc nghẽn đường truyền làm mất dữ liệu do đó việc điều chỉnh tốc độ truyền phù hợp là rất cần thiết. Các mạng máy tính hiện nay đều sử dụng những phương pháp kiểm soát lỗi và điều khiển luồng như đã khảo sát và đánh giá ở trên, giúp cho việc truyền tin ngày một nhanh hơn và đáng tin cậy hơn.4.4 Các giao thức liên kết dữ liệu4.4.1 Giao thức HDLC (High – Level Data Link Control): Giao thức hướng bit được sử dụng bởi nhiều ứng dụng trong nhiều thập kỉ4.4.2 Giao thức PPP (Point to Point Protocol): Giao thức được sử dụng để kết nối với Internet.4.4.1 Giao thức HDLCGiao thức định hướng bit là giao thức được dùng phổ biến hiện nay, tất cả các loại dữ liệu có thể được truyền dưới dạng bit nghĩa là phải được giải mã thành các bit trước khi truyền. Tất cả những giao thức định hướng bit đều bắt nguồn từ giao thức HDLC.Giao thức HDLC là chuẩn quốc tế được ISO đề nghị, dùng cho tất cả liên kết dữ liệu kiểu điểm-nối-điểm và đa điểm, hỗ trợ đường truyền song công. Tiền thân của HDLC là giao thức SDLC (điều khiển liên kết dữ liệu đồng bộ) của IBM và giao thức điều khiển truyền dữ liệu cấp cao ADCCP (Advanced Data Communication Control Procedure) của ANSI.4.4.1 Giao thức HDLCa. Khuôn dạng bản tinĐịnh dạngTrong đó:Flag: Để nhận biết gói dữ liệu dùng cờ bắt đầu và kết thúc :01111110Address: địa chỉ người nhận.Control: phần điều khiển. 88/168/16O - N16/328 Flag AddressControlInformationFCSFlag4.4.1 Giao thức HDLCGiao thức HDLC dùng cho cả dữ liệu và thông báo điều khiển thực hiện theo khuôn dạng khung chuẩn. Có 3 loại khung được dùng trong HDLC I (Information) khung thông tin : Mang thông tin thật hoặc số liệu. Các khung I có thể được dùng để mang thông tin ACK liên quan đến luồng khung I trong hướng ngược lại khi liên kết đang được hoạt động trong ABM và ARM.S (Supervisor) khung giám sát: Được dùng để điều khiển luồng và điều khiển lỗi và do đó chứa số thứ tự gửi và nhận, có hiệu lực điều hành sự nối.N (Unnumbered) khung không đánh số: Được dùng cho những chức năng như thiết lập liên kết và xóa kết nối.4.4.1 Giao thức HDLCCấu tạo các loại khung trong HDLC thông qua trường điều khiển – Controla. Khung thông tin – Informationb. Khung giám sát – Supervisorc. Khung không đánh số - UnNumbered4.4.1 Giao thức HDLCBit P/F được thay thế cho Poll/ Final.P: máy tính bên kia được yêu cầu gửi dữ liệu, tất cả các frame được gửi đi có giá trị là PF: Frame cuối cùng được đánh là F, và không được gửi đi.Các frame giám sát được phân biệt bởi trường typeType = 0  acknowledgement frame (Receive Ready): đợi frame kế tiếpType = 1  negative acknowledgement frame (Reject): truyền lỗi, cần truyền lại từ frame trong trường NextType = 2  Receive Not Ready: Báo ngưng gửi gói tin vì lỗi tạm thời của bên thuType = 3  Selective Reject: yêu cầu gửi lại frame xác định4.4.1 Giao thức HDLCHoạt động của HDLC: Trao đổi I-Frame, S-Frame và U-Frame giữa 2 bên3 giai đoạnKhởi tạoTrao đổi dữ liệuNgắt kết nối4.4.1 Giao thức HDLCGiai đoạn 1: Khởi tạoGửi U-frame khởi tạo 1 trong 6 chế độSNRM / SNRMESARM / SARMESABM / SABMEChế độ truyền và số bit đánh chỉ số frameNếu đồng ý kết nối gửi lại U-frame UA (unnumbered acknowledged) Nếu không đồng ý kết nối gửi lại U-frame DM (disconnected mode)4.4.1 Giao thức HDLCTrao đổi dữ liệu: Sau khi đã kết nối, Cả hai bên đều có thể gửi I-frame (chỉ số tuần tự bắt đầu từ 0)Các S-frame có thể được dùng để điều khiển dòng và điều khiển lỗi RR : ACKRNR : bên nhận bận, sau đóphải phát RR để tiếp tục nhận dữ liệuREJ: NACK (go-back-N)SREJ: NACK (selective repeat)Ngắt kết nối: Một trong hai bên ngắt kết nối bằng cách gửi U-frame DISC (disconnect) Bên kia phải chấp nhận ngắt kết nối, gửi lạiU-frame UA(unnumbered acknowledgment) Các khung quá độ có thể bị mất (việc phục hồi phải do các lớp trên)4.4.1 Giao thức HDLCSơ đồ hoạt động của HDLCTáchĐợi UAĐợi UANốiPhát SABMNhận UANhận UAPhát DISCTrao đổi số liệu4.4.1 Giao thức HDLCVí dụ về quá trình hoạt động4.4.1 Giao thức HDLCb. Hoạt động của giao thứcCơ chế vận hành của HDLC xoay quanh hai chức năng cơ bản là quản lý liên kết và truyền dữ liệu (bao gồm điều khiển luồng và điều khiển lỗi):Quản lý liên kết: Trước khi truyền một thông tin bất kỳ giữa hai trạm kết nối bằng liên kết điểm - điểm (point to point), một kết nối logic được thiết lập giữa hai bộ phận truyền thông tin 4.4.1 Giao thức HDLCTruyền dữ liệuHai vấn đề quan trọng nhất trong giai đọan truyền dữ liệu là kiểm soát lỗi và điều khiển luồng. Kiểm soát lỗi trong HDLC sử dụng thủ tục phát lại từ khung thứ N (go back N) hoặc phát lại có chọn lọc (selective repeat), điều khiển luồng dựa trên cơ chế cửa sổ trượt 4.4.2 Giao thức PPPGiao thức PPP cung cấp một phương thức để truyền các gói dữ liệu đa giao thức trên đường liên kết điểm-nối-điểm, và nó hỗ trợ bởi các giao thức sau : Giao thức điều khiển lớp liên kết DLLP (Data link Layer Protocol). Giao thức điều khiển liên kếtLCP (Link Control Protocol): giao thức điều khiển liên kết, điều khiển cởi gói thông suốt bản tin.Giao thức điều khiển mạng NCP (Network Control Protocol): cung cấp thông tin về cấu hình và điều khiển ở lớp mạng như việc gán và quản lý địa chỉ IP, nén hay không nén phần header của TCP/IP và gói dữ liệu IP. 4.4.2 Giao thức PPPNgoài ra, PPP còn có những ưu điểm sau:Dịch vụ thiết lập kết nối động để giảm chi phí truyền dữ liệu trong thời gian tạm ngưng.Hỗ trợ các đường kết nối tốc độ cao.Giao thức PPP hoạt động ở chế độ truyền 2 chiều đồng thời và được tích hợp trong các phần mềm mạng hỗ trợ cho phần lớn các trạm làm việc, các bộ định tuyến (router), các cầu nối dữ liệu (bridge).4.4.2 Giao thức PPPFlag: 01111110, xác định giới hạn khung.Address: Trường địa chỉ (loại địa chỉ quảng bá).Control: Trường điều khiển.Protocol: Trường giao thức, thường có kích thước là 2 byte dùng để xác định kiểu gói dữ liệu trong trường thông tin. Các giá trị của trường này được thể hiện ở bảng 4-1FCS: dùng để kiểm tra lỗi trong khung, sử dụng phương pháp kiểm tra độ dư vòng CRC.4.4.2 Giao thức PPPProtocolKiểuÝ nghĩa0021C0218021IP dataLCP dataNCP dataGói IP DatagramGói giao thức điều khiển liên kết (LCP)Gói giao thức điều khiển mạng (NCP)4.4.2.2 Phương thức hoạt độngĐể thiết lập kết nối dạng điểm-nối-điểm, mỗi trạm của liên kết PPP đầu tiên phải gửi các gói LCP để thiết lập cấu hình và kiểm tra tầng datalink. Sau đó, các trạm mới có thể gửi những yêu cầu cụ thể. Tiếp theo, các trạm gửi gói NCP cho phép chọn lựa và cấu hình các giao thức lớp mạng (IP, IPX, Appletalk). Khi giao thức ở lớp mạng đã được xác định, các ứng dụng thực sự của người dùng sẽ được giao thức PPP bắt đầu trao đổi ở dạng gói dữ liệu lớp mạng. Kết nối sẽ được duy trì cho đến khi LCP, NCP gửi các gói yêu cầu kết thúc kết nối.