Bài tập tính khối lượng bit bang go back n năm 2024

Cân thằng bằng đã từng rất phổ biến trong xã hội loài người, vì tính đơn giản của nó. Cấu tạo của cân gồm hai đĩa A, B được đặt ở hai đầu của một đòn bẩy. Có n quả cân, quả thứ i có khối lượng mi. Để cân một vật, người ta đặt nó vào đĩa A, sau đó thêm một vài quả cân vào các đĩa sao cho cân thăng bằng. Lúc này, cân nặng của vật là tổng khối lượng các quả cân trên đĩa B trừ đi tổng khối lượng các quả cân trên đĩa A, vì cân chỉ thăng bằng khi tổng khối lượng trên đĩa A bằng tổng khối lượng trên đĩa B.

Tuần trước, con chim vừa chở người em đi lấy vàng về, người em tiến hành cân lại số vàng mình nhận được. Để thuận tiện, anh ấy sẽ để nguyên túi vàng và cân một lần thay vì phải tách số vàng ra. Sau khi cân, anh ấy biết chính xác rằng túi vàng nặng M. Sau đó, vì tò mò và đam mê thuật toán, anh ấy thắc mắc là liệu có bao nhiêu cách cân khác nhau? Cụ thể hơn, bạn được cho một vật có khối lượng M, bạn đặt nó vào đĩa A sau đó thêm một số quả cân vào các đĩa sao cho cân thăng bằng. Cần đếm số cách khác nhau để thêm các quả cân như trên. Hai cách được coi là khác nhau nếu tồn tại i, 1 ≤ i ≤ n, sao cho hoặc là trong cách này thì sử dụng quả cân thứ i còn trong cách kia thì không, hoặc là cả hai cách đều sử dụng quả cân thứ i nhưng đặt vào hai đĩa khác nhau.

Uploaded by

Lê Thị Cẩm Nhung

100% found this document useful (3 votes)

4K views

45 pages

Original Title

qttb

Copyright

© © All Rights Reserved

Available Formats

DOCX, PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

100% found this document useful (3 votes)

4K views45 pages

QTTB

Uploaded by

Lê Thị Cẩm Nhung

Jump to Page

You are on page 1of 45

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

Chúng ta đã được tìm hiểu về các phương pháp phát hiện lỗi như parity check, checksum, ... giúp kiểm tra các gói tin bị lỗi trong quá trình truyền. Sau khi phát hiện lỗi, cần có thêm cơ chế báo nhận, phát lại, còn được gọi chung là ARQ (Automatic Repeat reQuest). Hai kỹ thuật phát hiện lỗi và báo nhận, phát lại kết hợp với nhau tạo thành cơ chế kiểm soát lỗi đóng vai trò quan trọng trong việc đảm bảo tính toàn vẹn và độ tin cậy của dữ liệu truyền qua mạng.

Trong môi trường truyền thông, lỗi có thể xảy ra do nhiều nguyên nhân như nhiễu, suy giảm tín hiệu, hoặc va chạm dữ liệu. ARQ giúp giảm thiểu tác động của những vấn đề này bằng cách đảm bảo rằng mọi gói tin đều được nhận một cách chính xác trước khi tiếp tục quá trình truyền. Không chỉ cải thiện độ tin cậy và chất lượng của dịch vụ truyền thông mạng, ARQ còn góp phần tăng cường hiệu suất tổng thể bằng cách giảm thiểu cần thiết phải truyền lại dữ liệu, qua đó tiết kiệm được băng thông và giảm độ trễ.

ARQ là một phương pháp kiểm soát lỗi trong truyền thông dữ liệu, trong đó bên nhận phản hồi lại với bên gửi thông qua việc gửi các tín hiệu báo nhận (acknowledgements - ACKs) hoặc thông báo lỗi (negative acknowledgements - NACs/NACKs). Dựa trên phản hồi này, bên gửi quyết định có cần thiết phải gửi lại gói tin bị lỗi hoặc mất mát hay không. Có nhiều biến thể của ARQ như Stop and wait ARQ, Go back N ARQ, Selective reject ARQ. Trong khuôn khổ tầng liên kết dữ liệu chúng ta sẽ tìm hiểu kỹ thuật Stop and wait ARQ, hai kỹ thuật khác thuộc về tầng giao vận.

II. Stop and wait ARQ

1. Định nghĩa Stop and wait ARQ

Kỹ thuật kiểm soát lỗi Stop and wait ARQ yêu cầu bên gửi (sender) và bên nhận (receiver) tuân thủ quy tắc như sau:

• Bên gửi mỗi lần chỉ gửi một gói tin, và chỉ gửi tiếp gói tin khác khi nhận được ACK của gói đã gửi trước đó. Trong trường hợp timeout mà chưa nhận được ACK thì gửi lại gói đã gửi.
• Bên nhận bắt buộc gửi lại ACK báo nhận cho bên gửi khi nhận gói tin hợp lệ (tốt).

2. Nguyên tắc hoạt động

Nguyên tắc hoạt động của Stop and wait ARQ dựa trên một quy trình truyền thông hai chiều giữa bên gửi và bên nhận. Dưới đây là các bước cơ bản trong quy trình này:

• Gửi dữ liệu: Bên gửi thực hiện gửi một gói dữ liệu và dừng lại, chờ phản hồi từ bên nhận.
• Chờ phản hồi: Sau khi nhận được gói tin, bên nhận kiểm tra tính toàn vẹn thông qua các phương pháp như checksum. Nếu dữ liệu được xác nhận là không có lỗi, bên nhận gửi một ACK về cho bên gửi. Ngược lại, nếu phát hiện lỗi, bên nhận có thể gửi một NAK/NACK, hoặc không gửi phản hồi nào cả, tùy thuộc vào thiết kế cụ thể của hệ thống.
• Nhận phản hồi và xử lý: Bên gửi sau khi nhận được ACK, sẽ tiến hành gửi gói tin tiếp theo. Nếu nhận được NACK hoặc không nhận được phản hồi trong một khoảng thời gian nhất định (timeout), bên gửi sẽ gửi lại gói dữ liệu trước đó.
• Lặp lại quy trình: Quy trình này lặp lại cho đến khi tất cả dữ liệu được truyền thành công.

Bên nhận sau khi nhận gói tin thực hiện công việc kiểm soát luồng dữ liệu:

• Flow control (kiểm soát luồng): cơ chế ngăn chặn bên gửi gửi quá nhiều dữ liệu mà bên nhận không thể xử lý kịp thời. Nó đảm bảo rằng bên gửi chỉ gửi lượng dữ liệu mà bên nhận có thể xử lý, tránh làm tràn bộ đệm của bên nhận và gây mất mát dữ liệu. Trong mô hình Stop and wait ARQ, kiểm soát luồng thực hiện thông qua việc bên gửi chờ đợi một ACK cho mỗi gói tin trước khi gửi gói tiếp theo.
• After Consumption (sau tiêu thụ): chỉ việc bên nhận chỉ gửi một tín hiệu ACK sau khi nó đã xử lý (tiêu thụ) gói tin dữ liệu nhận được. Điều này đảm bảo rằng bên nhận đã đủ không gian và tài nguyên để tiếp nhận và xử lý gói tin dữ liệu mới trước khi báo hiệu cho bên gửi rằng họ đã sẵn sàng nhận thêm dữ liệu.

III. Các trường hợp lỗi và xử lý

1. Các trường hợp lỗi

Trong kỹ thuật Stop and wait ARQ, có ba trường hợp lỗi chính có thể xảy ra:

2. Xử lý lỗi

2.1. Xử lý Lost Data (Dữ liệu bị mất)

Khi dữ liệu bị mất, Timer được sử dụng để xác định khoảng thời gian chờ phản hồi từ bên nhận. Nếu không nhận được ACK trong khoảng thời gian đã định (khi Timer hết hạn), bên gửi sẽ giả định rằng dữ liệu đã bị mất và sẽ tự động gửi lại dữ liệu đó. Việc sử dụng số thứ tự (Sequence Number) cho dữ liệu giúp bên gửi nhận biết đó là dữ liệu mới hay là dữ liệu được gửi lại.

2.2. Xử lý Lost ACK (ACK bị mất)

Tương tự như trường hợp mất dữ liệu, khi ACK bị mất, Timer sẽ hết hạn và kích hoạt để bên gửi gửi lại dữ liệu. Tuy nhiên, để phòng tránh việc gửi lại dữ liệu không cần thiết (nếu dữ liệu ban đầu thực sự đã đến được bên nhận), Sequence Number cho ACK cũng quan trọng, giúp bên gửi nhận biết được phản hồi cho dữ liệu cụ thể nào.

2.3. Xử lý Delayed ACK (ACK bị trễ)

Trong trường hợp ACK bị trễ, có thể xảy ra tình huống bên gửi đã gửi lại dữ liệu do nghĩ rằng nó đã bị mất. Để ngăn chặn việc này, việc sử dụng số thứ tự cho cả dữ liệu và ACK là rất quan trọng, giúp đảm bảo rằng mỗi bản sao của dữ liệu có thể được phân biệt và giúp bên nhận xác định xem gói dữ liệu đã được xử lý trước đó hay chưa. Nếu nhận được dữ liệu trùng lặp, bên nhận sẽ bỏ qua và không xử lý nó.

IV. Ưu, nhược điểm của Stop and wait ARQ

1. Ưu điểm

• Đơn giản và dễ triển khai: Do cơ chế hoạt động đơn giản, việc triển khai Stop and wait ARQ không đòi hỏi phần cứng phức tạp hay thuật toán lập trình phức tạp.
• Độ tin cậy cao: Kỹ thuật này đảm bảo rằng mỗi gói tin đều được xác nhận trước khi gửi gói tiếp theo, giúp đảm bảo rằng không có gói tin nào bị mất mà không được phát hiện.
• Phù hợp với các kênh truyền có băng thông thấp: Kỹ thuật này hoạt động tốt trên các kênh truyền mà việc truyền dữ liệu không thường xuyên và băng thông là một hạn chế.
• Khả năng kiểm soát luồng: Kỹ thuật này cung cấp khả năng kiểm soát luồng một cách tự nhiên vì người gửi không thể gửi gói tin tiếp theo cho đến khi nhận được ACK cho gói tin hiện tại.

2. Nhược điểm

• Hiệu suất thấp: Kỹ thuật này có hiệu suất kém trên các kênh truyền có băng thông cao hoặc độ trễ truyền lớn vì phải chờ đợi ACK cho mỗi gói tin trước khi gửi gói tiếp theo.
• Sử dụng kém hiệu quả băng thông: Vì người gửi phải chờ ACK sau mỗi gói tin, phần lớn thời gian kênh truyền không được sử dụng.
• Tăng độ trễ tổng thể: Việc phải chờ đợi xác nhận cho mỗi gói tin gửi đi có thể làm tăng độ trễ tổng thể trong truyền thông.

V. Minh họa kỹ thuật Stop and wait ARQ

Chúng ta sẽ thực hiện minh họa kỹ thuật Stop and wait ARQ bằng chương trình Python, có thể tạo một ví dụ đơn giản với hai hàm: sender() cho người gửi (sender) và receiver() cho người nhận (receiver).

import time
import threading
# Biến toàn cục để mô phỏng việc gửi và nhận dữ liệu qua mạng
network_buffer = None
ack_received = threading.Event()
def sender(data_packets):
    global network_buffer
    for sequence_number, packet in enumerate(data_packets):
        while True:
            print(f"Sender: Gửi gói tin {sequence_number}")
            network_buffer = (sequence_number, packet)  # Gửi gói tin
            ack_received.clear()  # Reset event cho ACK
            ack_received.wait(timeout=2)  # Đợi ACK với timeout
            if ack_received.is_set():
                print(f"Sender: Nhận được ACK cho gói tin {sequence_number}")
                break
            else:
                print(f"Sender: Không nhận được ACK, gửi lại gói tin {sequence_number}")
    print("Sender: Hoàn thành việc gửi tất cả gói tin.")
def receiver():
    global network_buffer
    while True:
        if network_buffer:
            sequence_number, packet = network_buffer
            print(f"Receiver: Nhận được gói tin {sequence_number}")
            time.sleep(1)  # Mô phỏng việc xử lý gói tin
            print(f"Receiver: Gửi ACK cho gói tin {sequence_number}")
            ack_received.set()  # Gửi ACK
            network_buffer = None  # Xóa buffer
# Tạo và khởi chạy các luồng
data_to_send = ['packet1', 'packet2', 'packet3']
receiver_thread = threading.Thread(target=receiver)
sender_thread = threading.Thread(target=sender, args=(data_to_send,))
receiver_thread.start()
sender_thread.start()
sender_thread.join()
receiver_thread.join()

Chương trình mô phỏng một kênh truyền thông đơn giản qua việc sử dụng một biến network_buffer để truyền dữ liệu từ sender đến receiver. Sự kiện ack_received được sử dụng để đợi và thông báo ACK từ receiver đến sender. Mỗi gói tin được gửi kèm với một số thứ tự.

Trong ví dụ này, chúng ta giả định rằng không có lỗi truyền thông và mạng là đáng tin cậy để tập trung vào cơ chế ARQ. Khuyến khích bạn đọc tiếp tục xây dựng các trường hợp lỗi minh họa cho các lỗi trong quá trình truyền được đề cập phía trên.