Trong phần trước, mình đã giới thiệu về tầng liên kết và các kĩ thuật phát hiện và sữa lỗi của frame. Trong phần này mình sẽ nói về các giao thức để quản lý đa truy cập(Giao thức phân hoạch kênh, Giao thức truy cập ngẫu nhiên).

III. Multiple Access Links và Protocol

Có 2 loại liên kết: Broadcast và Point-to-Point.

• Liên kết Point-to-Point thường được dùng trong các kết nối bằng Ethernet giữa hai node. Có nhiều giao thức giành cho liên kết Point-to-Point tiêu biểu là Point-to-Point Protocol (PPP) và high-level data link control(HDLC).
• Liên kết Broadcast, có thể được dùng cho mạng có dây(Ethernet hoặc cáp đồng trục) hoặc không dây(Mạng LAN không dây Wifi, 4G/5G, vệ tinh). Thuật ngữ broadcast được sử dụng ở đây vì khi bất kỳ node nào truyền một frame, kênh sẽ “rải” frame đó đến tất cả node khác một bản sao của frame.

Vấn đề được đặt ra ở đây là cách phối hợp quyền truy cập của nhiều node gửi và nhận vào 1 kênh broadcast có thể xảy ra chồng lấn(multiple access problem). Như nhiều thiết bị phát sóng cùng một tần số có thể làm mất dữ liệu, hay gần gũi hơn là ví dụ về đám đông nói chuyện với nhau càng nhiều người nói thì sẽ càng khó nghe hơn.
Để giải quyết vấn đề trên thì mạng máy tính có các giao thức đa truy cập, bằng cách đó các node có thể điều chỉnh để không gây ra chồng lấn lên nhau. Bao gồm ba loại: giao thức phân hoạch kênh, giao thức truy cập ngẫu nhiên và giao thức truy cập luân phiên.

Một giao thức đa truy cập lý tưởng cho một kênh phát sóng có tỷ lệ R bps nên có các đặc điểm mong muốn sau:

1. Khi chỉ một node có dữ liệu để gửi, node đó có băng thông là R bps.
2. Khi có M node gửi dữ liệu, mỗi node trong số các node này có băng thông là R/M bps. Điều này không nhất thiết có nghĩa là mỗi node trong số M node luôn có tỷ lệ tức thời là R/M, mà thay vào đó, mỗi node nên có tỷ lệ truyền trung bình là R/M trong một time slot phù hợp.
3. Giao thức là phi tập trung; tức là, không có node chính đại diện cho một điểm lỗi duy nhất của mạng.
4. Giao thức đơn giản, để việc triển khai không tốn kém.

1. Giao thức phân hoạch kênh

Có 2 loại giao thức phân hoạch kênh: time-division multiplexing (TDM) and frequency-division multiplexing (FDM) là hai kỹ thuật có thể được sử dụng để phân chia băng thông của kênh broadcast giữa tất cả các node cùng chia sẽ kênh đó.

1.1 Time-division multiplexing (TDM)

• Thời gian sẽ được phân chia thành các frame thời gian cố định, mỗi frame thời gian sẽ được chia thành các slot thời gian. Khi một kết nối được thiết lập, sẽ giành riêng một slot thời gian trong mỗi frame cho kết nối này.
• Mỗi node trong N node được giành riêng một slot, mỗi khi một node có một gói tin để gửi, nó sẽ truyền các bit của gói tin trong slot thời gian được chỉ định của nó trong frame TDM theo kiểu xoay vòng.
• TDM loại bỏ các va chạm và hoàn toàn công bằng: Mỗi node nhận được tỷ lệ truyền riêng là R/N bps trong mỗi frame thời gian.
• Tuy nhiên, nó có hai nhược điểm lớn. Nhược điểm thứ nhất, một node bị giới hạn ở tỷ lệ trung bình là R/N bps ngay cả khi nó là node duy nhất có gói tin để gửi. Nhược điểm thứ hai là một node luôn phải chờ đến lượt của nó trong chuỗi để truyền lại một lần nữa, ngay cả khi nó là node duy nhất có frame để gửi.

1.2 frequency-division multiplexing (FDM)

• FDM phân chia băng thông R bps của kênh truyền thành nhiều dải tần số khác nhau (mỗi tần số có R/N bps) và gán mỗi tần số cho một node trong N node. Bề rộng của dải tần số là băng thông.
• FDM có cả lợi ích và nhược điểm của TDM. Nó tránh các va chạm và phân chia băng thông công bằng giữa các node N. Tuy nhiên, FDM cũng chia sẻ một nhược điểm chính với TDM—một node bị giới hạn ở băng thông R/N, ngay cả khi nó là node duy nhất có gói tin để gửi.

1.3 Code division multiple access (CDMA)

- Trong khi TDM và FDM gán các time slot và tần số cho các node, CDMA gán một mã khác nhau cho mỗi node. Mỗi node sau đó sử dụng mã của nó để mã hóa các bit dữ liệu mà nó gửi.
- Nếu các mã được chọn cẩn thận, các mạng CDMA có đặc tính tuyệt vời là các node khác nhau có thể truyền cùng một lúc và vẫn cho phép các bộ nhận của chúng nhận chính xác các bit dữ liệu mã hóa của bên gửi (với điều kiện bên nhận biết mã của bên gửi) mặc dù có sự truyền nhiễu từ các node khác.
- Được sử dụng trong quân sự và điện thoại di động.

2. Giao thức truy cập ngẫu nhiên

- Trong các giao thức truy cập ngẫu nhiên, một node truyền luôn truyền với tốc độ đầy đủ của kênh, cụ thể là R bps. Khi xảy ra va chạm, mỗi node tham gia vào va chạm sẽ liên tục truyền lại frame của nó cho đến khi frame của nó được truyền thành công mà không xảy ra va chạm.
- Tuy nhiên, khi một node gặp va chạm, nó không nhất thiết phải truyền lại frame ngay lập tức. Thay vào đó, nó chờ một time slot ngẫu nhiên trước khi truyền lại frame. Mỗi node tham gia vào va chạm chọn các time slot ngẫu nhiên độc lập. Vì các time slot ngẫu nhiên được chọn độc lập, có thể một trong các node sẽ chọn một time slot nhỏ hơn đáng kể so với các time slot của các node va chạm khác và do đó có thể truyền frame của nó vào kênh mà không gặp va chạm.
- Có 2 giao thức được sử dụng rộng rải là: Slotted ALOHA và CSMA.

2.1 Slotted ALOHA

Giả định:

• Tất cả các frame có kích thước chính xác là L bit.
• Thời gian được chia thành các time slot có kích thước L/R giây (thời gian để truyền một frame).
• Các node bắt đầu truyền frame tại đầu các time slot.
• Các node được đồng bộ hóa sao cho mỗi node biết khi nào các time slot bắt đầu.
• Nếu hai hoặc nhiều frame xảy ra va chạm trong một time slot, thì tất cả các node sẽ phát hiện sự kiện va chạm trước khi time slot kết thúc.
• Gọi p là một xác suất, tức là một số giữa 0 và 1. Hoạt động của Slotted ALOHA tại mỗi node:
• Khi node có một frame dữ liệu mới để gửi, nó chờ đến đầu time slot tiếp theo và truyền toàn bộ frame trong time slot đó.
• Nếu không có va chạm, node đã truyền thành công frame của nó và do đó không cần phải xem xét việc truyền lại frame. (Node có thể chuẩn bị một frame mới để truyền, nếu có).
• Nếu có va chạm, node phát hiện va chạm trước khi time slot kết thúc. Node truyền lại frame của nó trong mỗi time slot tiếp theo với xác suất p cho đến khi frame được truyền thành công mà không có va chạm.

- Slotted ALOHA có vẻ có nhiều ưu điểm. Không giống như phân hoạch kênh, slotted ALOHA cho phép một node truyền liên tục với tốc độ đầy đủ R, khi node đó là node duy nhất đang hoạt động. (Một node được gọi là đang hoạt động nếu nó có frame để gửi.)
- Slotted ALOHA cũng rất phân cấp, vì mỗi node phát hiện va chạm và tự quyết định khi nào sẽ truyền lại. (Tuy nhiên, slotted ALOHA yêu cầu các time slot phải được đồng bộ hóa ở các node)
- Slotted ALOHA cũng là một giao thức cực kỳ đơn giản.

Hiệu quả: tỷ lệ thành công dài hạn của các slot (khi có nhiều node và mỗi node có nhiều frame để gửi).
Giả định: Có N node, mỗi node có nhiều frame để gửi, và mỗi frame được truyền trong một slot với xác suất p.

Note: ALOHA bản đầu tiên có best pratice là 1/(2e) (~0.18) theo ALOHAnet - Wikipedia

2.2 CSMA

Carrier sense multiple access (CSMA), đây là giao thức rất đơn giản chỉ với một câu “Lắng nghe trước khi truyền”. Nếu kênh truyền rãnh thì truyền toàn bộ frame. Ngược lại, trì hoãn việc truyền.
Câu hỏi: nếu tất cả các node đều thực hiện lắng nghe kênh, thì tại sao lại xảy ra va chạm?

- Vào thời điểm t0, node B lắng nghe kênh là rãnh, vì không có node nào khác đang truyền dữ liệu. Do đó, node B bắt đầu truyền, với các bit của nó lan truyền theo cả hai hướng dọc theo môi trường phát sóng.
- Sự lan truyền xuống của các bit của B trong hình với thời gian tăng cho thấy rằng một slot khác không là cần thiết để các bit của B thực sự lan truyền (dù gần bằng tốc độ ánh sáng) dọc theo môi trường phát sóng. Vào thời điểm t1 (t1 > t0), node D có một frame để gửi.
- Mặc dù node B đang truyền dữ liệu vào thời điểm t1, các bit đang được truyền bởi B chưa đến D, và do đó D lắng nghe kênh là rãnh và bắt đầu truyền dữ liệu của nó.

2.3 CSMA/CD

- Xung đột được phát hiện trong thời gian ngắn. Nếu đang truyền gặp xung đột thì ngừng truyền, giảm lãng phí kênh. Xung đột dễ dàng được phát hiện với đường truyền có dây, khó phát hiện với đường truyền không dây.

Cách hoạt động:

• Bước 1: Network adapter nhận một datagram từ lớp mạng, chuẩn bị một frame của lớp liên kết, và đưa frame vào bộ đệm của network adapter.
• Bước 2: Nếu network adapter lắng nghe rằng kênh đang rảnh (tức là không có tín hiệu năng lượng vào network adapter từ kênh), nó bắt đầu truyền frame. Ngược lại, nếu network adapter lắng nghe rằng kênh đang bận, nó chờ cho đến khi không còn tín hiệu năng lượng và sau đó bắt đầu truyền frame.
• Bước 3: Trong khi truyền, network adapter theo dõi sự hiện diện của tín hiệu năng lượng từ các network adapter khác sử dụng kênh phát sóng.
• Bước 4: Nếu network adapter truyền toàn bộ frame mà không phát hiện tín hiệu năng lượng từ các network adapter khác, network adapter hoàn thành việc truyền frame. Ngược lại, nếu network adapter phát hiện tín hiệu năng lượng từ các network adapter khác trong khi truyền, nó hủy bỏ việc truyền (tức là, nó ngừng truyền frame).
• Bước 5: Sau khi hủy bỏ, network adapter chờ một time slot ngẫu nhiên và sau đó trở lại bước 2.

Độ hiệu quả