Bài giảng MạngViễn thông (33BB)

1Bài giảng Mạng Viễn thông (33BB) Trần Xuân Nam Khoa Vô tuyến Điện tử Học viện Ky ̃ thuật Quân sự 2Bài 5 Các Giao thức Điều khiển Truy nhập Môi trường và ̀ Mạng Cục bộ̣ Phần I: Điều khiển Truy nhập Môi trường Phần II: Mạng Cục bô ̣ 3Phân loại Mạng  Có 2 loại cơ bản ‰ Mạng Chuyển mạch 9 Nối các người sử dụng bằng đường dây, ghép kênh va ̀ chuyển mạch 9 Chuyển gói từ nguồn tới đích, yêu cầu bảng định tuyến 9 Đối với mạng lớn thi ̀ việc đánh địa chỉ cần có cấu trúc để dễ tìm ra người phát va ̀ nhận 9 Ví du ̣: Mạng Internet ‰ Mạng Quảng ba ́ 9 Không cần bảng định tuyến do thông tin được đưa đến tất cả người dùng đồng thời. 9 Đánh địa chỉ đơn giản 9 Cần có giao thức điều khiển truy nhập môi trường 9 Ví du ̣: Mạng LAN 4Bài 5 Các Giao thức Điều khiển Truy nhập Môi trường Kỹ thuật Đa truy nhập Truy nhập Ngẫu nhiên Định trình (Scheduling) Phân Kênh (Channelization) Phẩm chất Trễ (Delay Performance) 5Chương 6 Các Giao thức Điều khiển Truy nhập Môi trường và ̀ Mạng Cục bộ̣ Kỹ thuật Đa Truy nhập 6Kỹ ̃ thuật Đa truy nhập Hình ve ̃ mô ta ̉ một trường hợp điển hình với M người dùng chia sẻ chung một môi trường truyền dẫn Môi trường truyền dẫn là môi trường quảng ba ́ nên khi một trạm phát thi ̀ tất cả các trạm khác đều thu được Khi hai hay nhiều trạm truyền đồng thời xảy ra hiện tượng va chạm ÖVấn đê ̀: Chia sẻ môi trường như thê ́ nào? 1 2 3 4 5M Môi trường đa truy nhập chia sẻ chung 7Các Giải pháp Chia sẻ Môi trường Các ky ̃ thuật Chia sẻ Môi trường ̃ i i Phân kênh Tĩnhĩ Điều khiển Truy nhập Môi trường Động i i i t Định trìnhị trì Truy nhập ngẫu nhiên r i MAC schemes  Polling  Token ring WLANs  Aloha  Ethernet 8Kỹ ̃ thuật Phân kênh (Channelization)  Cho phép chia sẻ môi trường tĩnh  Không có va chạm  Phân chia môi trường thành các kênh riêng biệt rồi gán cho từng người dùngÆ có tên gọi là phân kênh  Thích hợp cho các ứng dụng truyền tín hiệu liên tục (steady stream) Å sử dụng hiệu quả kênh truyền riêng 9Kênh Vệ tinh uplink fin downlink fout Thông tin Vệ ̣ tinh 10 Di động tế ́ bào uplink f1 ; downlink f2 uplink f3 ; downlink f4 11 Kỹ ̃ thuật Điều khiển Truy nhập Môi trường  Chia sẻ động môi trường trên cơ sở packets.  Thích hợp với các trường hợp dữ liệu phát theo cụm “bursty”  Chức năng của MAC là giảm thiểu va chạm đê ̉ thu được hiệu suất sử dụng môi trường hợp lý  Có hai loại MAC: ‰ Định trình (scheduling) ‰ Truy nhập ngẫu nhiên (random access) 12 Inbound line Outbound line Host computer Stations Định trình: Polling 1 2 3 M Poll 1 Data from 1 Poll 2 Data from 2 Data to M 13 Ring networks Định trình: Trao Token token Trạm giữ token được phát lên mạch vòng tokenData to M 14 Multitapped Bus Truy nhập Ngẫu nhiên Phát khi sẵn sàng Crash!! Nhiều máy cùng phát đồng thời; cần có chính sách phát lại thích hợp 15 Chê ́ đô ̣ AdHoc: trạm-tới-trạm Chê ́ đô ̣ cấu trúc: Trạm tới Trạm gốc (base station) Truy nhập ngẫu nhiên & polling Wireless LAN 16 Lựa chọn MACs  Các ứng dụng ‰ Kiểu lưu lượng? 9 Liên tục (steady) 9 Hay “cụm” (bursty) 9 Yêu cầu vê ̀ thời gian thực, jitter thấp?  Qui mô ‰ Chuyển được bao nhiêu lưu lượng? ‰ Hô ̃ trợ được bao nhiêu người dùng?  Đô ̣ tin cậy, chi phí? 17 Đánh giá ́ phẩm chất MACs  Môi trường chia sẻ là phương tiện duy nhất cho các trạm liên lạc với nhau  Bất kỳ sự phối hợp nào giữa các trạm đều thông qua môi trường  Một phần của tài nguyên môi trường bị dùng vào việc truyền tải phối hợp giữa các trạm  Đánh gia ́ hiệu suất/phẩm chất thông qua Tích Trê ̃ -Băng tần  Ví du ̣ hai trạm đơn giản ‰ Trạm có frame cần phát lắng nghe môi trường và thực hiện phát nếu môi trường rỗi ‰ Trạm giám sát môi trường để phát hiện va chạm ‰ Nếu có va chạm, trạm phát trước được phát lại 18 Hai trạm chia sẻ môi trường chung Ví dụ ̣ về ̀ MAC Hai trạm A phát vào thời điểm t = 0 Khoảng cách d meters tprop = d /v seconds A B A B B không phát trước thời điểm t = tprop & A chiếm kênh Case 1 B phát trước thời điểm t = tprop và phát hiện có va chạm ngay sau đo ́ A B A B A phát hiện va chạm tại thời điểm t = 2 tprop Case 2 19 Hiệu suất của Ví dụ ̣ Hai Trạm Mỗi lần truyền 1 frame cần khoảng thời gian yên lặng 2tprop ‰ Trạm B cần giữ yên lặng tprop trước và sau khi Trạm A phát ‰ Tốc độ R bit/s ‰ Sô ́ bit trong 1 frame L bits/frame max 1 1 2 1 2 / 1 2prop prop L L t R t R L a η = = =+ + + / propta L R =Tích Trễ-Băng tần chuẩn hóa Trê ̃ truyền sóng Thời gian truyền 1 frame Hiệu suất Thông lượng tối đa 1 bits/second / 2 1 2eff prop L R R L R t a = =+ + 20 Hiệu suất MAC điển hình Giao thức CSMA-CD (Ethernet): Mạng Token-ring a΄= đô ̣ trê ̃ của vòng (bits)/đô ̣ dài trung bình của khung Ví du ̣ Hai trạm: CSMA 1 1 6.44a η = + token 1 1 a η = ′+ 2tram 1 1 2a η = + Ö Khi a«1, η≈100% Ö Khi a →1, η giảm 21 Các Tích Trễ-Băng thông Điển hình  Các đường truyền dài hoặc có băng thông rộng có a lớn  Đô ̣ dài Ethernet frame max: 1500 bytes = 12.000 bits  TCP có max segment: 65.000bytes=520.000bit Æ Mạng quảng bá thích hợp với mạng LAN hoặc các mạng có tích trễ- băng thông nho Mạng Toàn cầu (GAN)3.33 x 10083.33 x 10073.33 x 1006100000 km Mạng Vùng rộng (WAN) 3.33 x 10063.33 x 10053.33 x 10041000 km Mạng Đô thị (MAN)3.33 x 10043.33 x 10033.33 x 100210 km Mạng Cục bô ̣ (LAN)3.33 x 10033.33 x 10023.33 x 1001100 m Mạng Desk area network 3.33 x 1003.33 x 10-013.33 x 10-021 m Kiểu Mạng1 Gbps100 Mbps10 MbpsKhoảng cách 22 Phẩm chất MAC Trê ̃ truyền Khung (Frame Transfer Delay): T ‰ Từ khi bit đầu tiên của khung đến MAC nguồn ‰ Tới khi bit cuối của khung được phân phối đến MAC đích Thông lượng (Throughput) ‰ Tốc độ truyền thực tế qua môi trường chia sẻ ‰ Đo bằng số frames/sec hay bits/sec Các tham sô ́ Tốc độ truyền: R bits/sec Đô ̣ dài môṭ frame: L bits/frame Thời gian truyền 1 frame: X=L/R seconds/frame Tốc độ tới trung bình: λ frames/second Thông lượng max (@ 100% hiệu suất): R/L fr/sec Tải: ρ = λX =λ(L/R) 23Tải T r ê ̃ t r u y ề n E[T]/X ρ ρmax 1 1 Trễ ̃ truyền chuẩn hóa vs. Tải E[T] = trê ̃ truyền khung trung bình X = thời gian truyền khung trung bình  Ở tốc đô ̣ tới thấp, chỉ là thời gian truyền frame  Ở các tốc độ tới cao, thời gian đợi truy nhập kênh dài hơn  Hiệu suất max thường nho ̉ hơn 100% 24 Sự ̣ phụ ̣ thuộc vào tải a=tpropR/L T r a n s f e r D e l a y Load E[T]/X ρρmax 1 1 ρ′max aa′ a′ > a  Khi a nho ̉ chi phí điều phối truy nhập thấp, ρmax≅1, khi a lớn, chi phí điều phối nhiều, hiệu suất giảm  Ηình dáng chính xác phu ̣ thuộc vào môi trường va ̀ MAC cụ thê ̉, số trạm, mẫu khung đến va ̀ phân bô ́ đô ̣ dài khung 25 Chương 6 Các Giao thức Điều khiển Truy nhập Môi trường và ̀ Mạng Cục bộ̣ Truy nhập Ngẫu nhiên 26 ALOHA  Tuyến vô tuyến truyền dữ liệu giữa campus chính & các campus xa của Đại học Hawaii  Giải pháp đơn giản nhất: just do it! ‰ Một trạm phát khi nó có dữ liệu đê ̉ phát ‰ Nếu có nhiều frames được truyền, chúng gây nhiễu lẫn nhau (va chạm) va ̀ bị mất ‰ Nếu ACK không nhận được trong khoảng thời gian timeout, thi ̀ mỗi trạm chọn một thời gian lùi ngẫu nhiên ‰ Trạm phát lại frame sau thời gian “lùi”  Tại sao lại phải chọn thời gian lùi ngẫu nhiên? 27 Nguyên lý ́ sơ đồ ̀ ALOHA  Truyền lần đầu không định trình  Kết quả truyền biết được (ACK) sau 2tprop  Sau 2tprop nếu không nhận được ACK, sử dụng thuật toán lùi đê ̉ chọn thời gian phát ngẫu nhiên (B)  Hoạt động của ALOHA có thể rơi vào 2 tình huống ‰ Phát lần đầu thành công, thỉnh thoảng xảy ra va chạm sau đó ‰ Snowball effect: xảy ra một loạt va chạmÆ nhiều trạm đợiÆ nguy cơ tăng số va chạm t t0t0-X t0+X t0+X+2tprop t0+X+2tprop + B Khoảng thời gian nguy hiểm Time-out Khoảng thời gian B Truyền lần đầu Phát lại 28 Mô hình ALOHA Định nghĩa và gia ̉ thiết ‰ Thời gian truyền khung X=L/R cố định ‰ S: thông lượng (số lần truyền frame thành công trung bình trong khoảng X giây) ‰ G: tổng tải tải (số lần thử truyền trung bình trong khoảng X giây.) ‰ Psuccess : xác suất truyền một khung thành công successS GP= XX frame transmission Prior interval  Một lần truyền bất ky ̀ bắt đầu trong khoảng thời gian nguy hiểm dẫn đến va chạm  Lần truyền đầu tiên thành công nếu không có khung nào tới trong khoảng 2X giây 29 Phương pháp phân tích Abramson Bài toán: Tính xác suất truyền thành công lần đầu tiên? Giả thiết của Abramson: Quá trình đến tổng hợp do khung mới và khung phát lại có phân bô ́ Poisson với số́ lần tới trung bình trong X giây là G Phân bô ́ Poinsson: xác suất k lần tới trong khoảng thời gian t với λ là tốc độ tới ( ) [ ( ) ] ! k ttP A t k e k λλ −= = 30 Phương pháp phân tích Abramson  Do t=2X, λ=G/X Xác suất truyền lần đầu thành công ( 2 ) 2 ( 2 ) [ arrivals in 2X] ! (2 ) ! G X kG XX k G X P k e k G e k − − = = 0 2 2 [0 arrivals in 2X] (2 ) 0! success G G P P G e e− − = = = 31 Thông lượng của ALOHA 2G successS GP Ge −= = 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0 0 . 0 0 7 8 1 2 5 0 . 0 1 5 6 2 5 0 . 0 3 1 2 5 0 . 0 6 2 5 0 . 1 2 5 0 . 2 5 0 . 5 1 2 4 G S  Thông lượng max Smax= 1/2e (18.4%)  Hoạt động kiểu 2 phương thức: G nho, S≈G G lớn, S↓0  Va chạm có thê ̉ tăng nhanh va ̀ kéo thông lượng vê ̀ không (2e)-1 = 0.184 Thông lượng của ALOHA Sô ́ khung đến ít Snowball effect 32 Trễ ̃ trung bình của ALOHA  Thời gian truyền gói đầu là và các gói tiếp theo là với B là thời gian lùi trung bình  Thời gian truyền gói trung bình là ( )2ALOHA[ ]/ 1 1 (1 / ) [packet]GE T X a e a B X= + + − + + propX t+ 2 propt X B+ + ( )2ALOHA[ ] 1 ( 2 ) [sec]Gprop propE T X t e X t B= + + − + + Sô ́ lần thử không thành công để truyền 1 gói Với là tích trễ-băng tần chuẩn hóa / prop propt ta L R X = = 33 Tóm tắt ALOHA  Ưu điểm: đơn giản Nhược điểm: hiệu suất thấp do xác suất va chạm lớn Æ Cải thiện bằng Slotted ALOHA 34 ALOHA phân khe Các gói có đô ̣ dài không đổi va ̀ bằng 1 khe thời gian Thời gian được phân khe thành các khe X giây Các trạm đồng bô ̣ theo thời gian của khung Các trạm phát khung ở ngay phần đầu của khe sau khi có khung tới Khoảng thời gian “lùi” bằng bội sô ́ của các khe t (k+1)XkX t0 +X+2tprop+ B Vulnerable period Time-out Thời gian backoff B t0 +X+2tprop Chỉ có các frames tới trước X giây va chạm 35 Xác suất truyền thành công của S-ALOHA ( )( ) ( )[ arrivals in X] ! ! G X kG k XX GX GP k e e k k − −= = 0( ) [0 arrivals in ] 0! G G success G P P X e e− −= = = Thông lượng của S-ALOHA G successS GP Ge −= = ( )S-ALOHA[ ]/ 1 1 (1 / ) [packet]GE T X a e a B X= + + − + + Thời gian truyền trung bình của S-ALOHA 36 Thông lượng của S-ALOHA 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0 . 0 1 5 6 3 0 . 0 3 1 2 5 0 . 0 6 2 5 0 . 1 2 5 0 . 2 5 0 . 5 1 2 4 8 Ge-G Ge-2G G S 0.184 0.368  Smax = (1/e)=0.386  Có 2 chê ́ đô ̣ làm việc giống như ALOHA 37 Ví dụ ̣ ALOHA vs S-ALOHA  Hê ̣ thống vô tuyến truyền yêu cầu thiết lập cuộc gọi qua kênh vô tuyến 9600bps, chiều dài gói là 120bits, thời gian time-out 20ms, thời gian chờ phân bô ́ đều trong khoảng 1~7 gói. So sánh average delay của ALOHA và S-ALOHA khi tải là 40% của SALOHA-max Tốc độ truyền gói 9600bps 1 packet/120 bits=80 packets/s× ALOHA max 80 0,184 15 packet/sS − = × ≈ S-ALOHA max 80 0,384 30 packet/sS − = × ≈ 40% tải SALOHA-max = 15x0.4= 6packet/s Æ G=6/80 Bỏ qua trê ̃ truyền sóng ( )12/80ALOHA[ ]/ 1 1 (1 0.5(1 7) / ) 1.81 [packet]ET X e X X= + − + + = ( )6/80S-ALOHA[ ]/ 1 1 (1 0.5(1 7) / ) 1.39 [packet]ET X e X X= + − + + = 38 Tóm tắt S-ALOHA  Có hiệu suất cao hơn so với ALOHA  Có thời gian trê ̃ thấp hơn ALOHA  Hiệu suất tối đa=38.4% Æ vẫn còn thấp do lãng phí băng tần vào điều khiển va chạm gói Ö Cải thiện bằng CSMA 39 Ý tưởng CSMA  Nâng cao hiệu suất bằng cách giảm việc truyền các gói có nguy cơ gây va chạm  Cảm nhận đường truyền xem có sóng mang (có trạm đang phát) không? 40 Đa truy nhập Cảm nhận Sóng mang (CSMA) A Station A begins transmission at t = 0 A Station A captures channel at t = tprop  Trạm cảm nhận (dò) kênh trước khi bắt đầu truyền ‰ Nếu thấy kênh bận, hoặc là đợi hoặc là định trình lùi (tùy chọn) ‰ Nếu rỗi, bắt đầu truyền ‰ Thời gian nguy hiểm giảm xuống tprop (do hê ̣ quả chiếm kênh) ‰ Khi có va chạm, diễn ra trong toàn bộ thời gian truyền khung ‰ If tprop > X (hoặc a>1), không có tăng ích so với ALOHA hoặc S-ALOHA 41 Dựa theo hành động khi kênh bận, có 3 loại CSMA ‰ 1-persistent CSMA (most greedy) 9 Truyền ngay sau khi kênh rỗi 9 Độ trễ thấp, hiệu quả thấp ‰ Non-persistent CSMA (least greedy) 9 Đợi một khoảng thời gian lùi, sau đó dò kênh lại 9 Trê ̃ lớn, hiệu suất cao ‰ p-persistent CSMA (adjustable greedy) 9 Đợi đến khi kênh rỗi, truyền với xác suất p; hoặc đợi thêm một khe thời gian nhỏ va ̀ dò kênh lại với xác suất 1-p 9 Cân bằng giữa hiệu suất va ̀ trê ̃ Các phương pháp CSMA Sensing 42 0 0.1 0.2 0.3 0.4 0.5 0.6 0 . 0 2 0 . 0 3 0 . 0 6 0 . 1 3 0 . 2 5 0 . 5 1 2 4 8 1 6 3 2 6 4 0.53 0.45 0.16 S G a = 0.01 a =0.1 a = 1 Thông lượng 1-Persistent CSMA  Tốt hơn Aloha & S- Aloha với a nhỏ  Tồi hơn Aloha với a > 1 43 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0 . 0 2 0 . 0 3 0 . 0 6 0 . 1 3 0 . 2 5 0 . 5 1 2 4 8 1 6 3 2 6 4 0.81 0.51 0.14 S G a = 0.01 Thông lượng Non-Persistent CSMA a = 0.1 a = 1  Thông lượng tối đa cao hơn 1- persistent CSMA với a nho ̉  Tồi hơn Aloha với a > 1 44 CSMA với Phát hiện Va chạm (CSMA/CD) Giám sát đường truyền đê ̉ phát hiện va chạm & và ngừng truyền ‰ Các trạm có gói truyền, cần dò sóng mang trước ‰ Sau khi bắt đầu truyền, các trạm tiếp tục dò kênh đê ̉ phát hiện va chạm ‰ Nếu có va chạm, tất cả các trạm liên quan dùng phát, định trình lại thời gian lùi ngẫu nhiên, và thử lại ở thời gian định trình tiếp theo. Ở CSMA va chạm gây nên lãng phí X giây truyền hết một khung CSMA-CD giảm lãng phí xuống còn thời gian phát hiện va chạm va ̀ ngừng truyền 45 Thời gian phản ứng CSMA/CD Mất 2 tprop đê ̉ biết kênh đa ̃ được chiếm hay chưa? A begins to transmit at t = 0 A B B begins to transmit at t = tprop- δ; B detects collision at t = tprop A B A B A detects collision at t= 2 tprop- δ 46 Mô hình CSMA-CD Gia ̉ thiết 1-persistent CSMA-CD ‰ Va chạm có thê ̉ phát hiện va ̀ giải quyết trong 2tprop ‰ Khoảng thời gian cạnh tranh được chia thành các khe có độ dài 2tprop để đảm bảo các trạm đều phát hiện được va chạm ‰ Giả sử có n trạm đang cạnh tranh chiếm đường truyền, và mỗi trạm có thê ̉ truyền với xác suất p trong mỗi khe thời gian cạnh tranh ‰ Sau khi kết thúc khoảng thời gian cạnh tranh (một trạm đa ̃ chiếm được kênh), mất thêm X giây để truyền một gói Busy Contention Busy(a) Time Idle Contention Busy 47 Giải quyết Cạnh tranh  Bài toán: Mất bao nhiêu lâu để giải quyết xong vấn đề cạnh tranh?  Cạnh tranh được giải quyết khi có duy nhất một trạm truyền trong một khe thời gian. Do có n trường hợp 1 trạm phát trong khi các trạm khác không phát nên 1(1 )nsuccessP np p −= −  Đê ̉ tìm xác suất p cho Psuccess lớn nhất, lấy đạo hàm theo p chúng ta tìm được gia ́ trị lớn nhất tại p=1/n ( ) ( )1 1max 1 1 1 11 1n nsuccessP n n n n e− −= − = − →  Trung bình, sau 1/Pmax = e = 2.718 khe thời gian thi ̀ giải quyết xong cạnh tranh Chu ky Canh tranh TB 2 [sec]propt e= 48 CSMA/CD Throughput Hê ̣ thống đạt được thông lượng tối đa khi quá trình cạnh tranh va ̀ truyền gói liên tiếp nhau ( ) ( ) LRdeaeettX X propprop /121 1 121 1 2max νρ ++=++=++= Time Busy Contention Busy Contention Busy Contention Busy  với: R bits/sec, L bits/frame, X=L/R seconds/frame a = tprop/X ν meters/sec (tốc đô ̣ ánh sáng) d meters là đường kính của hê ̣ thống 2e+1 = 6.44 49 Ứng dụng của CSMA-CD: Ethernet Chuẩn Ethernet LAN đầu tiên sử dụng CSMA-CD ‰ Dò sóng mang 1-persistent ‰ R = 10 Mbps ‰ tprop = 51.2 microseconds 9 512 bits = 64 byte slot 9 Cho phép truyền xa 2.5 km + 4 repeaters ‰ Truncated Binary Exponential Backoff 9 Sau va chạm thứ n, chọn lùi từ {0, 1,, 2k – 1}, với k=min(n, 10) 50 Thông lượng của MAC truy nhập Ngẫu nhiên 0 0.2 0.4 0.6 0.8 1 0.01 0.1 1 ALOHA Slotted ALOHA 1-P CSMA Non-P CSMA CSMA/CD a ρmax  Với a nho ̉: CSMA-CD có thông lượng tốt nhất  Với a lớn: Aloha & S-Aloha có thông lượng tốt hơn  ALOHA và S-ALOHA thay đổi theo a do hoạt động của chúng không phu ̣ thuộc vào thời gian phản ứng 51 Do kênh và ̀ Truyền Ưu tiên  Một số ứng dụng yêu cầu đáp ứng nhanh hơn các ứng dung khác, ví du ̣: các bản tin ACK  Đặt quyền ưu tiên khác nhau ‰ Lưu lượng ưu tiên cao dò kênh ở thời gian τ1 ‰ Lưu lượng ưu tiên thâp dò kênh ở thời gian τ2>τ1 ‰ Lưu lượng ưu tiên cao chiểm kênh trước Cơ cấu ưu tiên này được sử dụng ở IEEE 802.11 W-LAN 52 Định trình Chapter 6 Medium Access Control Protocols and Local Area Networks 53 Định trình dùng cho MAC  Định trình truyền khung đê ̉ tránh va chạm trong môi trường chia sẻ 9 Hiệu suất sử dụng kênh hiệu quả hơn 9 Trê ̃ ít biến động hơn 9 Tạo công bằng đều giữa các trạm 8 Tăng đô ̣ phức tạp vê ̀ tính toán va ̀ thu ̉ tục  Hai phương pháp chính ‰ Đặt chô ̃ ‰ Thăm dò 54 Hệ ̣ thống đặt chỗ̃  Các hê ̣ thống tập trung: Một trạm trung tâm nhận yêu cầu từ các trạm và thực hiện cấp quyền phát  Hệ thống phân tán: các trạm thực hiện một thuật toán phân quyền để xác định trình tự truyền Central Controller 55 Hệ ̣ thống Đặt chỗ̃ Time Chu ky ̀ n Khoảng t/g đặt chỗ Truyền khung r d d d r d d d Chu ky ̀ (n + 1) r = 1 2 3 M  Quá trình phát được tổ chức theo các chu kỳ  Chu ky ̀: khoảng thời gian đặt chỗ + Thời gian truyền khung  Khoảng thời gian đặt chỗ có một khe nho ̉ cho từng trạm yêu cầu đặt chô ̃ đê ̉ truyền khung 56 Tùy chọn của Hệ ̣ thống Đặt chỗ̃  Hê ̣ thống Tập trung hay Phân tán ‰ Hê ̣ thống tập trung: Một trạm trung tâm lắng nghe thông tin đặt chô ̃, quyết định trình tự truyền, trao quyền ‰ Hê ̣ thống Phân tán: Mỗi trạm xác định khe phát của nó từ thông tin đặt chô ̃  Đặt chô ̃ Đơn khung hay Đa Khung ‰ Đặt chô ̃ một khung: chỉ có thê ̉ đặt chô ̃ 1 khung trong chu ky ̀ đặt chô ̃ ‰ Đặt chô ̃ đa khung: có thê ̉ đặt chô ̃ hơn một khung 57 t r 3 5 r 3 5 r 3 5 8 r 3 5 8 r 3 (a) t r 3 5 r 3 5 r 3 5 8 r 3 5 8 r 3 8(b) Ví dụ̣  Ban đầu trạm 3 & 5 đặt chô ̃ va ̀ truyền  Trạm 8 có khung truyền và đặt chô ̃ đê truyền  Chu ky ̀ truyền bao gồm cả các khung từ trạm 8 58 Hiệu suất của Hệ ̣ thống Đặt chô ̃̃ Gia ̉ thiết đô ̣ dài của minislot (slot đặt chô ̃) = vX Sơ đô ̀ đặt chô ̃ đơn khung ‰ Nếu trễ truyền sóng có thê ̉ bo ̉ qua, truyền 1 khung đơn cần (1+v)X seconds ‰ Đường truyền tải đầy khi tất cả các trạm đều truyền và hiệu suất tối đa đạt được là:  Sơ đô ̀ đặt chỗ k-frame ‰ Nếu có thể đặt chỗ truyền k frame và nếu có M trạm, thi ̀ có Mk frames có thê ̉ truyền trong khoảng thời gian XM(k+v) seconds ‰ Hiệu suất tối đa: max 1 1 MX Mv MX v ρ = =+ + max 1 1 MkX vMv MkX k ρ = =+ + 59 Hệ ̣ thống Đặt chỗ ̃ Truy nhập Ngẫu nhiên  Khi sô ́ trạm truyền ít không hiệu quả ‰ Do gán tĩnh cho mỗi trạm một khe thời gian đặt chô ̃ nho ̉  Sơ đô ̀ đặt chô ̃ S-ALOHA ‰ Các trạm sử dụng S-Aloha đê ̉ đặt chô ̃ ‰ Trung bình, mỗi lần đặt chô ̃ thành công mất ít nhất e khe minislot ‰ Thời gian hiệu dụng yêu cầu đê ̉ đặt chô ̃ là 2.71vX X X(1+ev) 1 1 + 2.71v ρmax = = 60 Ví dụ̣: GPRS General Packet Radio Service ‰ Dùng truyền dữ liệu trong GSM ‰ Các thiết bị GPRS, ví du ̣ ĐTDĐ hay laptop đê ̉ gửi dữ