III. Polling - Hỏi vòng

Polling, hay hỏi vòng, là một trong ba loại giao thức truy cập kiểm soát chính, được thiết kế để quản lý việc truy cập mạng trong một môi trường có nhiều thiết bị cần giao tiếp. Trong mô hình polling bao gồm hai loại thiết bị:

• Một thiết bị trung tâm, thường được gọi là máy chủ hoặc trạm điều khiển (controller).
• Các thiết bị còn lại gọi là trạm phụ, thực hiện truyền dữ liệu.

Polling hoạt động dựa trên một quy trình tuần tự để tránh xung đột.

1. Nguyên lý hoạt động

Hoạt động của Polling được so sánh giống như quy trình điểm danh của giáo viên trên lớp học:

• Giáo viên - trạm điều khiển bắt đầu "điểm danh" (quy trình) bằng cách gửi một tín hiệu "poll" đến trạm đầu tiên trong "danh sách học sinh".
• Trạm nhận được tín hiệu sẽ thực hiện gửi truyền dữ liệu nếu có. Trong trường hợp không có dữ liệu truyền, thực hiện báo lại bằng cách gửi thông điệp "poll reject" (NAK).
• Tiếp tục thao tác trên đối với trạm tiếp theo trong danh sách.
• Quy trình lặp lại cho tới trạm cuối cùng (tất cả trạm đều được hỏi).

Chúng ta xem xét một ví dụ cụ thể qua hình ảnh sau:

Trạm chính Primary thực hiện hỏi trạm A bằng cách gửi tín hiệu "Poll". Trạm A phản hổi bằng tín hiệu "NAK" thể hiện việc không truyền dữ liệu. Trạm chính tiếp tục gửi tín hiệu "Poll" tới trạm B, trạm B gửi lại dữ liệu "DATA", trạm chính báo hiệu dữ liệu nhận thành công bằng cách gửi lại gói tin "ACK" cho trạm B.

2. Hiệu suất

Gọi $T_t$ là tổng thời gian cần thiết để truyền dữ liệu, $T_{poll}$ là tổng thời gian dành để polling tất cả các thiết bị. Hiệu suất (Efficiency) của giao thức Polling được tính bằng công thức:

$$E=\frac{T_t}{T_{poll}+T_t}$$

Tuy nhiên, công thức trên được thành lập dựa trên giả định luôn có dữ liệu để truyền sau khi polling. Trong các tình huống thực tế, nếu trạm được polling không có dữ liệu để truyền, thời gian từ sau khi polling cho đến khi polling trạm tiếp theo (có thể được coi là thời gian lãng phí) cũng cần được xem xét.

Chúng ta có thể "điều chỉnh" lại công thức tính hiệu suất trên một chút, khi xét đến cả khả năng không có dữ liệu được truyền sau một số lần polling. Với $N$ là số lượng thiết bị có dữ liệu để truyền, $T_{idle}$ là thời gian khi kênh truyền thông không hoạt động, bao gồm thời gian sau khi polling một trạm không có dữ liệu để truyền và trước khi polling trạm tiếp theo. Công thức tính hiệu suất trở thành:

$$E=\frac{N\times T_t}{N\times (T_{poll}+T_t) + T_{idle}}$$

3. Ưu, nhược điểm

Ưu điểm

• Thời gian truy cập và tốc độ dữ liệu trên kênh là cố định và có thể dự đoán được: giúp cho việc lập kế hoạch và quản lý tài nguyên mạng trở nên dễ dàng hơn.
• Hiệu quả tối đa: Trong mô hình lý tưởng, không có sự lãng phí thời gian do va chạm hay đợi chờ, do đó hiệu suất của hệ thống có thể đạt tối đa.
• Băng thông tối đa: Khả năng sử dụng tối đa băng thông do không có sự lãng phí trong việc chờ đợi hoặc va chạm.
• Không có slot nào bị lãng phí trong quá trình polling: Mỗi lượt polling đều có mục đích và được sử dụng hiệu quả.
• Có sự phân bổ ưu tiên: Một số trạm phụ có thể được gán ưu tiên để đảm bảo truy cập nhanh hơn, điều này quan trọng đối với các ứng dụng cần phản ứng nhanh.

Nhược điểm

• Mất nhiều thời gian hơn: Do cần phải chờ đợi lượt được poll, quy trình có thể mất nhiều thời gian hơn so với các phương thức truy cập khác.
• Phân bổ không công bằng: Mặc dù mỗi trạm đều có cơ hội ngang nhau trong mỗi vòng polling, nhưng điều này có thể tạo ra sự thiên vị nếu một số trạm phụ không cần gửi dữ liệu thường xuyên.
• Có thể một số trạm sẽ hết dữ liệu để gửi: Khi đó, việc polling trạm đó trở nên không cần thiết và gây lãng phí thời gian.
• Tăng thời gian chuyển đổi dẫn đến giảm tốc độ dữ liệu của kênh dưới tải nhẹ: Khi tải mạng thấp, thời gian chờ để được poll có thể làm giảm hiệu suất truyền dữ liệu tổng thể của kênh.

4. Bài tập

Đề bài

Trong một mạng Polling với $10$ trạm và một máy chủ. Máy chủ mất $0.5ms$ để poll mỗi trạm, trạm truyền dữ liệu cần $3ms$.

a) Không có độ trễ truyền tin giữa các trạm. Hãy tính tổng thời gian cần thiết để tất cả các trạm gửi dữ liệu của họ một lần. b) Biết rằng trong mạng có $2$ trạm không có dữ liệu để gửi trong lần poll đầu tiên. Và có một độ trễ truyền tin giữa các trạm là $0.1ms$. Hãy tính tổng thời gian cần thiết thực hiện chu kỳ Polling đầu tiên.

Hướng dẫn

a) Mỗi trạm mất $3ms$ để gửi dữ liệu và máy chủ mất $0.5ms$ để poll mỗi trạm. Vì vậy, tổng thời gian cần thiết cho mỗi trạm là $3ms$ (truyền dữ liệu) + $0.5ms$ (polling) = $3.5ms$. Với $10$ trạm, tổng thời gian cần thiết sẽ là $3.5ms \times 10 = 35ms$

b) $2$ trạm không có dữ liệu để truyền, mỗi trạm mất tổng thời gian: $0.5ms$ (polling). $8$ trạm có thực hiện truyền dữ liệu, mỗi trạm mất tổng thời gian: $0.5ms$ (polling) + $3ms$ (truyền dữ liệu) = $3.5ms$.

Lưu ý rằng do trạm cuối cùng không cần độ trễ sau khi gửi, nên tổng độ trễ giữa các trạm là $9 \times 0.1ms = 0.9ms$

Tổng thời gian chu kỳ đầu tiên mất:

$$2\times 0.5 + 8\times 3.5 + 0.9 = 29.9ms$$

IV. Token passing - Truyền thẻ bài

Token passing, hay truyền thẻ bài, là một giao thức truy cập mạng dựa trên việc chuyển một "token" - một đơn vị bit đặc biệt hoặc mẩu dữ liệu đặc biệt - giữa các thiết bị trong một mạng. Mỗi thiết bị chỉ có thể gửi dữ liệu khi nó nắm giữ token, đảm bảo rằng chỉ có một thiết bị có thể truyền dữ liệu tại một thời điểm nhất định, ngăn chặn xung đột dữ liệu và va chạm. Giao thức này được sử dụng trong các mạng LAN (Local Area Network) vòng tròn và bus.

1. Nguyên lý hoạt động

• Đối với mạng vòng Token ring, token được chuyền từ mỗi trạm tới trạm lân cận (theo một chiều). Đối với Token bus, token được truyền theo một thứ tự xác định trước.
• Mỗi trạm đang nắm giữ token thực hiện truyền dữ liệu trước khi chuyển token sang cho trạm khác, nếu không có dữ liệu cần truyền, token được chuyển luôn cho trạm khác.

Hình ảnh trên cho thấy token được chuyển lần lượt theo vòng (thuận chiều kim đồng hồ) từ trạm $1$ tới trạm $4$, lặp lại liên tục.

2. Hiệu suất

Hiệu suất trong giao thức token passing chịu ảnh hưởng bởi các yếu tố độ trễ (delay) và thông lượng (throughput).

Độ trễ là thước đo khoảng thời gian từ khi một gói tin sẵn sàng cho đến khi nó được giao. Với $N$ là số lượng các trạm, $T_p$ là độ trễ truyền và $T_t$ là độ trễ truyền tải, ký hiệu $a$ là tỉ lệ $\frac{T_p}{T_t}$. Chúng ta có thời gian trung bình (độ trễ) cần thiết để gửi token đến trạm tiếp theo là:

$$\frac{a}{N}$$

Thông lượng là thước đo lượng truy cập thành công, được tính bằng công thức:

$$S = \begin{cases} \frac{1}{1+\frac{a}{N}} & \text{khi } a<1 \\ \frac{1}{a(1+\frac{1}{N})} & \text{khi } a>1 \end{cases}$$

3. Ưu, nhược điểm

Ưu điểm

• Ứng dụng mở rộng: Giao thức này hiện có thể được áp dụng với các loại cáp và router khác nhau, bao gồm cả tính năng gỡ lỗi tích hợp như rơle bảo vệ và cấu hình tự động lại.
• Hiệu suất tốt dưới tải cao: Token passing cung cấp thông lượng tốt khi mạng chịu tải lớn, do cơ chế quản lý quyền truy cập mạng một cách hợp lý và tránh va chạm dữ liệu.

Nhược điểm

• Chi phí cao: Việc triển khai giao thức Token passing thường đắt đỏ hơn so với các tiêu chuẩn phổ biến khác do chi phí cho các thành phần topologi mạng và thiết bị phần cứng.
• Thành phần phần cứng đắt tiền: Các phần tử phần cứng của mạng Token Ring thường có giá cao hơn so với những mạng dựa trên các giao thức khác.
• Tính độc quyền cao: Các thiết bị Token Ring thường được thiết kế để hoạt động tốt với sản phẩm từ một nhà sản xuất cụ thể, điều này hạn chế khả năng lựa chọn của người dùng và tạo nên một hệ thống có tính độc quyền cao.

4. Bài tập

Đề bài

Một mạng Token Ring với $8$ trạm, mỗi trạm cần $2ms$ để gửi dữ liệu và thời gian để token di chuyển từ một trạm đến trạm tiếp theo là $0.2ms$.

a) Hãy tính tổng thời gian cần thiết để mỗi trạm gửi dữ liệu của họ một lần. b) Biết rằng có $1$ trạm đầu tiên không có dữ liệu để gửi, và có độ trễ là $0.05ms$ cho mỗi trạm khi truyền token. Hãy tính tổng thời gian cần thiết để các trạm còn lại gửi dữ liệu của họ một lần.

Hướng dẫn

a) Mỗi trạm cần $2ms$ để gửi dữ liệu. Token di chuyển từ một trạm đến trạm tiếp theo mất $0.2ms$.

Token phải di chuyển qua tất cả các trạm, nhưng không cần di chuyển sau trạm cuối cùng, tổng thời gian di chuyển token là $0.2ms \times 7 = 1.4ms$

Tổng thời gian cần thiết để mỗi trạm gửi dữ liệu của họ một lần:

$$2ms \times 8 + 1.4 = 17.4ms$$

b) Token phải di chuyển qua tất cả các trạm, nhưng không cần di chuyển sau trạm cuối cùng, tổng thời gian di chuyển token là $(0.2ms + 0.05ms (độ trễ)) \times 7 = 1.75ms$

Chỉ có $7$ trạm cần truyền dữ liệu, mất $2ms \times 7 = 14ms$.

Tổng thời gian cần thiết để mỗi trạm gửi dữ liệu của họ một lần:

$14ms + 1.75ms = 15.75ms$

Các tài liệu tham khảo

• https://www.geeksforgeeks.org/controlled-access-protocols-in-computer-network/
• https://csc-knu.github.io/sys-prog/books/Andrew%20S.%20Tanenbaum%20-%20Computer%20Networks.pdf
• https://www.ucg.ac.me/skladiste/blog_44233/objava_64433/fajlovi/Computer%20Networking%20_%20A%20Top%20Down%20Approach,%207th,%20converted.pdf