Giao thức ALOHA
Pure ALOHA
Năm 1971, đại học Hawaii bắt đầu nghiên cứu và sử dụng hệ thộng ALOHA của họ Hệ thống vô cùng đơn giản bao gồm những bước sau:
Chế độ truyền Người dùng truyền bất cứ lúc nào họ muốn, mã có khả năng phát hiện lỗi.
Chế độ lắng nghe Sau một gói tin truyền, bên phát sẽ nhận được một tín hiệu (ACK) từ người nhận nếu gói tin được truyền thành công
Sự truyền dữ liệu từ nhiều người dùng có thể bị chồng chéo, dẫn đến lỗi tiếp nhận tại phía thu, được gọi là va chạm gói tin Khi xảy ra va chạm, các lỗi sẽ được phát hiện và nguồn phát sẽ nhận được tín hiệu NAK để thông báo về sự cố này.
Chế độ truyền lại cho biết rằng khi tín hiệu NAK được nhận, gói tin sẽ được gửi lại Tuy nhiên, nếu người sử dụng thực hiện việc truyền lại ngay lập tức, khả năng xảy ra va chạm vẫn có thể xảy ra Do đó, nguồn phát sẽ thực hiện việc truyền lại sau một khoảng thời gian ngẫu nhiên để giảm thiểu tình trạng này.
Chế độ timeout là cơ chế quan trọng trong quá trình truyền dữ liệu, trong đó nếu nguồn phát không nhận được tín hiệu ACK hoặc NAK trong một khoảng thời gian xác định, nó sẽ tự động truyền lại gói tin.
Hệ thống pure ALOHA sử dụng các gói tin có độ dài đồng nhất Khi hai gói tin cố gắng truyền tải cùng lúc, va chạm sẽ xảy ra Nếu bit đầu tiên của gói tin mới chồng lên bit cuối của gói tin cũ, cả hai gói tin sẽ bị hủy và cần phải truyền lại sau.
Giao thức pure ALOHA hoạt động dựa trên giả thiết rằng lưu lượng đến từ một số lượng hữu hạn người dùng, tuân theo quá trình Poisson với tốc độ trung bình λ gói/s Mỗi gói tin được truyền trong thời gian cố định T giây, và một truyền dẫn thành công xảy ra khi không có truyền dẫn khác trong khoảng thời gian (t - T, t + T) Tốc độ tải yêu cầu trong thời gian gửi một gói tin, ký hiệu là G, bao gồm cả các gói tin cần truyền lại và các gói tin mới đến trong khoảng thời gian này Thông lượng kênh S được tính theo công thức cụ thể.
Hình 1.2: Chi tiết quá trình truyền trong giao thức pure ALOHA
Thông lượng tối đa của giao thức này là S = 1/(2e) khoảng 18% Khi tốc độ tải yêu cầu G nhỏ, thông lượng gần bằng với tốc độ tải yêu cầu.
G lớn thì thông lượng tiến tới 0.
Mặc dù kết quả hiện tại chưa đáp ứng được nhu cầu sử dụng của người dùng, nhưng đây là bước khởi đầu quan trọng cho các cải tiến trong các giao thức tiếp theo.
Slotted ALOHA
Sau khi giao thức ALOHA ra đời, Roberts (1972) đã giới thiệu một phương pháp mới giúp tăng gấp đôi hiệu suất so với hệ thống pure ALOHA Ông đề xuất chia thời gian thành các slot bằng nhau, tương ứng với thời gian truyền một khung Theo đó, một trạm muốn truyền khung phải chờ đến đầu slot thời gian tiếp theo để thực hiện việc truyền.
Hình 1.3: Cơ chế quá trình truyền trong giao thức Slotted ALOHA ( Computer
Khoảng thời gian yêu cầu để tránh va chạm trong giao thức slotted ALOHA là T, thay vì 2T như trong giao thức ALOHA, dẫn đến hiệu năng đỉnh của slotted ALOHA tăng gấp đôi Thông lượng S được xác định qua số gói tin truyền thành công trong thời gian truyền dẫn một gói tin.
Giao thức slotted ALOHA đạt được thông lượng tối đa khi G = 1 và S = 0.37 (1/e), như thể hiện trong hình 4 So với giao thức pure ALOHA, slotted ALOHA cho thông lượng cao gấp đôi, nhưng yêu cầu phải có sự đồng bộ về thời gian.
Hình 1.4: Hiệu suất 2 cơ chế pure ALOHA và slotted ALOHA (Computer
Reservation-ALOHA
Một cải tiến quan trọng đã được áp dụng cho các hệ thống ALOHA với sự xuất hiện của reservation-ALOHA (R-ALOHA) Hệ thống R-ALOHA hoạt động trên hai chế độ chính: chế độ không dự trữ (unreservation) và chế độ dự trữ (reservation), mỗi chế độ có những đặc điểm riêng biệt.
Một khung thời gian được thiết lập và phân chia thành một số khe dự trữ
Nguồn phát sử dụng các khe dự trữ này để dự trữ các gói tin
Sau khi yêu cầu, nguồn phát lắng nghe cho một bản tin và một khe chỉ định
Khung thời gian được chia thành M+1 khe bất cứ khi nào một hàng đợi được thiết lập
M khe đầu tiên dùng để truyền bản tin
Khe cuối cùng được chia thành các khe nhỏ hơn để sử dụng cho việc dự trữ hoặc yêu cầu
Nguồn phát gửi gói tin chỉ khi nó là một phần chỉ định của M khe
Trong ví dụ R-ALOHA, thời gian được chia thành các khe ngắn cho việc đặt chỗ mà không có reservations Khi các reservations được thực hiện, hệ thống được cấu hình với M = 5 bản tin tiếp theo và V = 6 khe thời gian Điều này cho thấy một yêu cầu và sự thừa nhận trong tiến trình Các trạm tìm kiếm để dành ba khe thời gian, với các reservations đóng vai trò dẫn đường cho việc định vị gói dữ liệu đầu tiên.
Hình 1.5: Ví dụ về reservation ALOHA ( M=5 slots, V=6 subslots )
Giao thức đa truy nhập cảm nhận sóng mang CSMA
Giao thức đa truy nhập càm nhận sóng mang Non-persistent CSMA và 1-
Trong giao thức NP-CSMA, khi một nút phát hiện kênh bận, nó sẽ ngừng cảm nhận kênh và thay thế cơ chế lập lịch truyền dẫn bằng thời gian ngẫu nhiên trong tương lai Hoạt động của NP-CSMA được chia thành các chu kỳ thời gian liên tiếp, mỗi chu kỳ bao gồm khoảng thời gian bận và khoảng thời gian rỗi Các khoảng thời gian này phản ánh các sự kiện trong chu kỳ, với t là khoảng thời gian trễ truyền cực đại và T là thời gian truyền dẫn một gói tin, dẫn đến kênh bận trong khoảng thời gian (T+t).
Trong cơ chế truy nhập kênh giao thức non-persistent CSMA, thông lượng kênh S được định nghĩa là tỷ số giữa thời gian hiệu dụng truyền gói tin và tổng thời gian bận và rỗi của kênh Tỷ số a được xác định bằng khoảng thời gian truyền lan so với khoảng thời gian truyền gói, với a = t / T Công thức tính thông lượng kênh S được sử dụng để phân tích hiệu suất của hệ thống.
Để giảm thiểu thời gian rỗi của kênh, các nút có thể khởi tạo truy cập truyền dẫn ngay khi phương tiện được xác định là rỗi Nếu kênh đang bận, các nút sẽ thực hiện quá trình đếm ngẫu nhiên một khoảng thời gian để xác định thời điểm cho lần truy cập tiếp theo.
1 khi kênh cảm nhận rỗi thể hiện nguyên tắc làm việc của cơ chế 1-CSMA
Hình 2.2 minh họa cơ chế truy nhập kênh giao thức 1-persistent CSMA Thông lượng S trong trường hợp không phân khe được tính bằng công thức (điền số), trong khi trường hợp phân khe được biểu diễn bằng công thức dưới đây.
Giao thức đa truy nhập cảm nhận sóng mang p-persistent CSMA
2.2 Giao thức đa truy nhập cảm nhận sóng mang p-persistent CSMA
Giao thức 1-CSMA là một trường hợp đặc biệt của giao thức p-persistent CSMA Trong giao thức p-CSMA, khi cảm nhận được kênh rỗi, nút phát sẽ truyền dẫn với xác suất p nhỏ hơn 1 Nếu kênh đang bận, các nút phát sẽ tiếp tục theo dõi cho đến khi kênh trở lại trạng thái rỗi và thực hiện truyền lại với xác suất p.
Giao thức p-persistent CSMA được mô hình hóa bằng chuỗi Markov thông qua các trạng thái nút, với hành vi của một nút trong điều kiện bão hòa lưu lượng được thể hiện qua chuỗi Markov 3 trạng thái Hình 2.3 minh họa cơ chế truy nhập kênh của giao thức này.
Hình 2.4: Các trạng thái nút trong mô hình Markov
Trong chuỗi Markov, có ba trạng thái chính: Trạng thái Chờ (Wait - w) khi nút i trì hoãn truyền dẫn hoặc đang trong quá trình backoff; Trạng thái Thành công (Success - s) khi nút i hoàn tất truyền dẫn thành công tới đích với bản tin xác nhận ACK; và Trạng thái Thất bại (Failure - f) khi nút i khởi tạo nhưng không thể hoàn thành truyền dẫn.
Hình 2.5: Hiệu suất của các giao thức ALOHA và CSMA (Computer Network-
CSMA với phát hiện va chạm
Giao thức CSMA persistent và nonpersistent đã cải tiến đáng kể so với giao thức ALOHA bằng cách đảm bảo rằng không có trạm nào bắt đầu truyền khi kênh truyền đang bận Tuy nhiên, nếu hai trạm cùng cảm nhận kênh truyền trống và bắt đầu truyền đồng thời, tín hiệu sẽ xảy ra va chạm Một cải tiến quan trọng khác là khả năng giúp trạm nhanh chóng phát hiện va chạm và dừng truyền, từ đó tiết kiệm thời gian và băng thông.
Phương pháp này áp dụng cho topo tuyến tính, với tất cả các trạm mạng kết nối trực tiếp vào bus Mỗi trạm có khả năng truy cập ngẫu nhiên vào bus chung (đa truy nhập), điều này có thể gây ra xung đột khi nhiều trạm truyền dữ liệu đồng thời Dữ liệu được truyền theo một khuôn dạng cố định, bao gồm vùng thông tin điều khiển chứa địa chỉ trạm đích.
Hình 3.1: Topo dạng tuyến tính, các máy được nối vào bus chung
Phương pháp CSMA/CD là một cải tiến của CSMA (LBT - Nghe trước khi nói), hoạt động như một cuộc hội thảo qua điện thoại Mỗi người tham gia phải chờ cho đến khi mọi người khác ngừng nói trước khi bắt đầu cuộc hội thoại Khi đường dây đã yên tĩnh, cá nhân có thể nói chuyện Nếu hai người bắt đầu nói cùng lúc, họ sẽ phải ngừng lại và thử lại sau.
Giao thức CSMA/CD (Carrier Sense Multiple Access with Collision Detection) là nền tảng của mạng LAN Ethernet cổ điển, cho phép phát hiện va chạm trong quá trình truyền dữ liệu Quá trình này yêu cầu phần cứng của trạm phải lắng nghe kênh truyền trong khi đang gửi thông tin.
Giao thức CSMA/CD, tương tự như các giao thức mạng LAN khác, hoạt động theo mô hình 3.1 Khi một máy tính muốn gửi gói tin, nó sẽ lắng nghe tín hiệu Carrier trên đường truyền Nếu không có tín hiệu, máy sẽ tiến hành truyền gói tin Sau khi gửi xong, máy tiếp tục lắng nghe để phát hiện xung đột Nếu không có xung đột, gói tin sẽ được truyền hoàn tất Ngược lại, nếu phát hiện xung đột, máy sẽ phát đi một gói tin broadcast để thông báo cho các máy khác ngừng gửi tin, nhằm tránh làm nhiễu đường truyền và sẽ gửi lại gói tin.
Một thiết bị có gói tin cần truyền sẽ lắng nghe đường truyền cho đến khi nào đường truyền không còn bị chiếm.
Khi đường truyền không còn bị chiếm, nguồn phát bắt đầu gửi gói tin.
Nguồn phát cũng bắt đầu lắng nghe để đảm bảo rằng không có xung đột xảy ra.
In the event of a collision, all workstations that have transmitted a frame will send out a jam signal to ensure that every workstation is aware of the collision.
Sau khi tín hiệu nghẽn được xử lý, mỗi nguồn phát của các gói tin xung đột sẽ khởi động một bộ định thời và chờ một khoảng thời gian ngẫu nhiên gọi là thời gian back-off t_bo để cố gắng truyền lại Thời gian này nằm trong khoảng 0 ≤ t_bo < 2^k, với k là số lần truyền lại Nếu k vượt quá 15, quá trình truyền sẽ dừng lại Các máy không gặp phải xung đột sẽ không phải chờ đợi.
Sau khi các thời gian định thời là hết, máy gửi có thể bắt đầu một lần nữa từ bước đầu tiên.
Hình 3.2: Các bước thực hiện giao thức CSMA/CD
Mô hình CSMA/CD bao gồm ba trạng thái chính: quá trình truyền dữ liệu, quá trình va chạm giữa các tín hiệu, và trạng thái rỗi khi không có trạm nào đang thực hiện việc truyền.
Hình 3.3: Mô hình giao thức CSMA/CD (Computer network-Tanenbaum)
Thuật toán va chạm được xem xét kỹ lưỡng, trong đó giả định rằng hai trạm bắt đầu truyền dữ liệu tại thời điểm t0 Thời gian tối thiểu để phát hiện va chạm là khoảng thời gian mà tín hiệu truyền từ một trạm đến trạm khác.
Xem xét trường hợp xấu nhất, thời gian truyền tín hiệu giữa hai trạm xa nhất là t Tại thời điểm t0, một trạm bắt đầu truyền tín hiệu Ngay trước khi tín hiệu đến đích, tại thời điểm t0 + t - ε, một trạm khác cũng bắt đầu truyền, dẫn đến xung đột ngay lập tức Xung đột này sẽ dừng lại, nhưng tín hiệu không trở lại trạm gốc cho đến khi thời gian đạt 2t.
Nói cách khác, trong trường hợp xấu nhất, trạm không chắc chắn rằng nó chiếm kênh cho đến khi nó truyền được 2t không phát hiện va chạm.
Kết nối CSMA/CD hoạt động như một hệ thống ALOHA phân khe với độ rộng khe là 2t, trong đó t = 5ms cho 1 km cáp đồng trục Sự khác biệt chính giữa CSMA/CD và ALOHA phân khe là chỉ có một trạm truyền được phép hoạt động trong mỗi khe thời gian, trong khi các trạm khác phải chờ Sự khác biệt này trở nên quan trọng khi thời gian truyền của một gói tin lớn hơn nhiều so với thời gian cần thiết để truyền tải.
Việc phát hiện xung đột đã nâng cao độ tin cậy trong việc truyền dẫn thông tin qua cáp Khi một máy trạm truyền thông tin, dòng điện trên cáp sẽ xuất hiện, với dòng điện trong máy trạm lớn gấp đôi dòng đo được trên đường cáp do cáp truyền theo hai hướng IEEE đã phát triển phương pháp phát hiện ngưỡng để nhận diện xung đột Nếu chỉ có một máy trạm truy cập, điện áp trên đường truyền sẽ đạt giá trị tối đa xác định Khi có thêm máy thứ hai tham gia, điện áp đo được sẽ tăng lên, và bộ phát hiện xung đột sẽ nhận biết sự thay đổi này để thông báo trạng thái đường truyền bận Để bộ phát hiện xung đột hoạt động chính xác, giá trị ngưỡng tối thiểu phải lớn hơn điện áp tối đa khi chỉ có một máy trạm đang truyền thông tin.
IEEE đã cung cấp một số liệu quan trọng về cáp đồng trục, trong đó bộ phát hiện va chạm cần có ngưỡng từ -1448 mV đến -1590 mV Trong thực tế, điện áp một chiều trên cáp trong quá trình truyền không có xung đột đạt giá trị tối đa là -1293 mV, chênh lệch 55 mV so với ngưỡng -1448 mV Giá trị này được dự trữ để gửi xung kết thúc tín hiệu và đáp ứng xung của bộ lọc trong phần còn lại của gói tin, chiếm khoảng 12% cho đáp ứng xung của bộ lọc.
Nếu cần lắp đặt một bộ lọc có giá trị đáp ứng xung lớn, ngưỡng thấp nhất(1448mV) được thay thế bằng giá trị 1293mV (1+ đáp ứng xung).
Trong quá trình thực hiện bài tập lớn, chúng em đã học hỏi được nhiều bài học bổ ích, không chỉ về kiến thức cơ sở mạng máy tính mà còn về tinh thần làm việc nhóm, thảo luận và phân tích Những kinh nghiệm này sẽ giúp chúng em hoàn thiện kỹ năng của mình Cuối cùng, em xin chân thành cảm ơn thầy đã giúp đỡ tận tình.
1 “ Slide mạng máy tính” Đại học Bách Khoa Hà Nội- Nguyễn Hữu Thanh
3 Head First Networking – Al Anderson