Đã đăng vào thg 10 29, 7:00 SA 8 phút đọc

113

Random access protocols in computer network - Điều khiển truy nhập ngẫu nhiên trong mạng máy tính (phần 1)

I. Mở đầu

Thế giới đang dần chuyển mình theo xu hướng kỹ thuật số, nhu cầu kết nối và chia sẻ tài nguyên giữa các thiết bị ngày càng tăng. Một môi trường mạng luôn có nhiều người dùng cạnh tranh với nhau để truy nhập băng thông, dẫn đến sự xung đột và tắc nghẽn dữ liệu, ảnh hưởng tới hiệu suất tổng thể của mạng. Do đó, việc đảm bảo sự hiệu quả, công bằng trong quá trình truyền dữ liệu đã trở thành một yêu cầu cơ bản và thiết yếu.

"Điều khiển truy nhập ngẫu nhiên" (Random access protocols) là một giải pháp được thiết kế để giải quyết những thách thức đó bằng cách phân phối tài nguyên mạng một cách linh hoạt và quy tắc. Phương pháp giúp giảm thiểu xung đột và tắc nghẽn bằng cách quản lý cách thức, thời điểm các thiết bị truy nhập vào mạng, đồng thời tăng cường khả năng mở rộng và độ tin cậy của mạng bằng cách đảm bảo rằng mọi yêu cầu truy nhập đều được xử lý theo cách công bằng, hiệu quả.

Trong bài viết này, chúng ta xem xét các phương thức điều khiển truy nhập ngẫu nhiên sau:

Aloha
CSMA (Carrier Sense Multiple Access)

II. Aloha

Aloha là một phương thức truy nhập mạng không dây nguyên thủy và có ảnh hưởng lớn, được phát triển lần đầu tại Đại học Hawaii vào năm $1970$ . Sử dụng kênh radio UHF để kết nối tài nguyên máy tính trên các đảo Oahu, Maui và Hawaii, AlohaNet đã mở ra một kỷ nguyên mới cho việc truyền thông không dây. Đến năm $1973$ , ALOHA đã được thử nghiệm thành công trong mạng PacNet - một mạng vệ tinh thử nghiệm ở Thái Bình Dương có sự tham gia của NASA, và tại các trường đại học khác như University of Alaska, Tohoku University ở Nhật Bản, và University of Sydney ở Úc. Về sau, kỹ thuật này đã được tiến hóa bởi Dr. Robert Metcalfe vào năm $1973$ để trở thành nền tảng cho mạng ALOHA dựa trên cáp của Xerox, tiền thân của Ethernet do 3COM phát triển.

ALOHA tồn tại chủ yếu trong hai phiên bản: Pure Aloha và Slotted Aloha.

1. Đụng độ (va chạm) trong Aloha

Trong hệ thống Aloha, va chạm xảy ra khi hai nút (hoặc hơn) cùng gửi thông tin trong cùng một frame thời gian. Giả sử có một mạng Aloha với ba nút: nút A, nút B và nút C. Cả ba nút này đều muốn gửi thông tin qua một kênh truyền chung. Nếu nút A bắt đầu gửi một gói tin tại thời điểm $t_0$ và nút B cũng quyết định gửi một gói tin cùng lúc đó, tín hiệu từ hai nút sẽ va chạm.

Kết quả dẫn tới cả hai gói tin đều bị hỏng và không thể đến được đích. Do cả hai nút không thể biết được liệu gói tin của mình có bị va chạm hay không cho đến khi chúng nhận được (hoặc không nhận được) xác nhận từ nút đích.

Do Aloha không có cơ chế để kiểm tra liệu kênh truyền có đang bận hay không trước khi gửi dữ liệu, nên khả năng xảy ra va chạm là khá cao, đặc biệt khi có nhiều nút trong mạng và mức độ truy cập mạng cao.

2. Pure Aloha

Pure Aloha là phiên bản ban đầu, một thiết bị có thể gửi dữ liệu bất cứ khi nào nó muốn, không cần đồng bộ với các thiết bị khác. Khi một gói tin được gửi đi, nếu nó không gặp va chạm, gói tin được coi là đã gửi thành công. Nếu xảy ra va chạm, thiết bị sẽ chờ đợi một khoảng thời gian ngẫu nhiên trước khi thử gửi lại.

Công thức tính hiệu suất tối đa của Pure Aloha là:

$S = G \times e^{-2G}$

Với $S$ là hiệu suất của hệ thống (tỉ lệ frame thành công trên tổng số frame được gửi) và $G$ là số lượng frame gửi trung bình trong một khoảng thời gian của frame.

Quan sát đồ thị hàm số $f(x)=x\times e^{-2x}$ nhận thấy điểm cực đại của hàm số đạt tại $x=0.5$ , khi đó $f(x)\approx 18.4$ (Bạn đọc có thể tự chứng minh điều này).

Điều đó nghĩa là giao thức Pure Aloha có thông lượng cực đại đạt khoảng $18.4\%$ , hay xác suất truyền thành công đạt $18.4\%$ . Đây không phải một hiệu suất tốt vì ít nhất $81.6\%$ tổng băng thông đã bị bỏ phí do xung đột dữ liệu!

3. Slotted Aloha

Slotted Aloha là một cải tiến của Pure Aloha. Thời gian được chia thành các slot cố định và mỗi thiết bị chỉ được phép gửi dữ liệu vào đầu của mỗi slot. Hiệu suất của Slotted Aloha có thể được tính bằng công thức:

$S = G \times e^{-G}$

Với $S$ và $G$ có cùng ý nghĩa như trên.

Slotted Aloha giúp giảm khả năng xảy ra va chạm và nâng cao hiệu suất lên gần gấp đôi so với Pure Aloha.

III. CSMA (Carrier Sense Multiple Access)

CSMA là một phương thức kiểm soát truy cập mạng phổ biến, đặc biệt trong các mạng LAN không dây. Mục đích của CSMA là để tối ưu hóa việc sử dụng kênh truyền thông và giảm thiểu va chạm dữ liệu trên mạng. CSMA cải thiện hiệu suất so với các phương thức truy cập ngẫu nhiên không có cảm nhận môi trường, như Aloha, bằng cách yêu cầu mỗi thiết bị cảm nhận kênh truyền trước khi gửi dữ liệu. Bằng cách sử dụng cảm biến sóng mang (Carrier) để quyết định xem kênh truyền có bận rộn hay không trước khi gửi dữ liệu, nên phương pháp còn được gọi là "Đa truy nhập sử dụng sóng mang". CSMA tuân theo nguyên tắc "nghe trước khi nói" (Listen before talk), tức là một thiết bị phải "nghe" hoặc cảm nhận kênh truyền để xác định xem kênh có đang được sử dụng bởi một thiết bị khác hay không. Nếu kênh truyền đang bận, thiết bị sẽ đợi; ngược lại, nó sẽ tiến hành gửi dữ liệu.

CSMA có một số biến thể, trong đó hai phiên bản phổ biến nhất là:

CSMA/CD (CSMA Collision Detection)
CSMA/CA (CSMA Collision Avoidance)

1. Sóng mang (Carrier)

Sóng mang có tần số cao (năng lượng lớn) và được sử dụng để truyền tín hiệu thông tin đi xa, cả trong môi trường có dây và không dây. Tần số của sóng mang thường cao hơn nhiều so với tần số của tín hiệu thông tin để đảm bảo có thể phủ sóng xa hơn và vượt qua được các rào cản vật lý.

Sóng mang là một giao động tuần hoàn không mang thông tin, nó chỉ đóng vai trò là phương tiện để "mang" tín hiệu thông tin từ nguồn đến đích thông qua quá trình điều chế.

2. Đụng độ (va chạm) trong CSMA

Va chạm trong CSMA xảy ra khi hai hoặc nhiều nút cùng một lúc cố gắng gửi thông tin qua một kênh truyền chung. Giả sử chúng ta có một kênh truyền với $4$ nút A, B, C và D. Khi nút A bắt đầu gửi một tín hiệu điện tử tại thời điểm $t_0$ , tín hiệu này sẽ lan truyền qua kênh và mất một khoảng thời gian nhất định để đến các nút khác. Nếu nút B cũng bắt đầu gửi một tín hiệu tại một thời điểm gần $t_0$ (có thể trước khi nó nhận được tín hiệu từ A) thì tín hiệu từ A và B có thể va chạm trên kênh truyền. Điều này là do sự trễ lan truyền – thời gian cần thiết để một tín hiệu đi từ nguồn đến đích.

Tài liệu tham khảo

Computer Network