Cơ sở mạng thơng tin ng c om Giáo trình dành cho sinh viên đại học ngành Điện tử - Viễn thông co Chủ biên: Nguyễn Hữu Thanh Khoa Điện tử Viễn Thông cu u du o ng th an Trường Đại học Bách khoa Hà nội CuuDuongThanCong.com https://fb.com/tailieudientucntt .c om ng co an th ng du o u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt Các từ viết tắt Đầy đủ Viết tắt Cumulative distribution function CDF First in first out FIFO Last in first out LIFO First-come-first-server FCFS LCFS Probability density function c om Last-come-first-serve pdf PDF cu u du o ng th an co ng Probability distribution function CuuDuongThanCong.com https://fb.com/tailieudientucntt Bảng đối chiếu thuật ngữ Anh - Việt Tiếng Anh Tiếng Việt Arrival process Tiến trình tới Biominal distribution Phân bố nhị thức Birth – Death Process Tiến trình sinh tử Analysis Phân tích Base station Trạm gốc Tiến trình nhị thức Derparture process Tiến trình Expectation Kỳ vọng Evaluation c om Binomial process Đánh giá Phân bố mũ Vào trước phục vụ trước Formal description Mô tả hình thức co First in first out / First-come-first-serve ng Exponential distribution Hàm tần suất Inter-arrival time Thời gian hai kiện tới (?) Load Tải an Frequency function Phân bố chuẩn/phân bố Gauss th Gaussian distribution Model du o Modeling Performance Probability density function u Probability Random event cu Probability distribution function Random experiment Vào sau phục vụ trước ng Last in first out / Last-come-first-serve Random variable Mơ hình Mơ hình hóa Đặc tính/chất lượng hoạt động Xác suất Hàm mật độ xác suất Hàm phân phối xác suất Phép thử ngẫu nhiên Sự kiện ngẫu nhiên Biến ngẫu nhiên Scale parameter Tham số tỷ lệ Server Trạm phục vụ/Server Shape parameter Tham số hình dạng Service process Tiến trình phục vụ Simulation Mơ CuuDuongThanCong.com https://fb.com/tailieudientucntt Standard deviation Độ lệch chuẩn Steady state Trạng thái ổn định Traffic intensity Mật độ lưu lượng Stochastic process Tiến trình ngẫu nhiên Transformation Biến đổi Uniform distribution Phân bố Validation Kiểm định tính xác Utilization Hiệu suất kênh Phương sai cu u du o ng th an co ng c om Variance CuuDuongThanCong.com https://fb.com/tailieudientucntt Mục lục Các từ viết tắt Bảng đối chiếu thuật ngữ Anh - Việt Mục lục _6 Mục lục hình vẽ Mục lục bảng biểu _10 Chương Giới thiệu _1 c om 1.1 Mục đích việc mơ hình hóa đánh giá đặc tính hoạt động hệ thống _ 1.2 Các tham số, tiêu chuẩn phương pháp đánh giá hệ thống thông tin _ 1.2.1 Các tham số đánh giá đặc tính hoạt động hệ thống thơng tin _ 1.2.2 Các tiêu chuẩn đánh giá 1.2.3 Các phương pháp đánh giá _ Chương Các tiến trình ngẫu nhiên ng 2.1 Xác suất kiện _ 2.1.1 Phép thử kiện ngẫu nhiên 2.1.2 Xác suất co 2.2 Biến ngẫu nhiên hàm xác suất _ an 2.2.1 Biến ngẫu nhiên 2.2.2 Hàm mật độ phân phối xác suất 10 2.2.3 Hàm tần suất phân phối xác suất biến ngẫu nhiên rời rạc 12 2.2.4 Các tham số đặc trưng biến ngẫu nhiên 13 2.3 Các mơ hình phân bố xác suất _ 16 du o ng th 2.3.1 Phân bố Bernoulli (Bernoulli distribution) _ 2.3.2 Phân bố nhị thức (binomial distribution) 2.3.3 Phân bố chuẩn (Gaussian distribution) _ 2.3.4 Phân bố mũ (exponential distribution) 2.3.5 Phân bố Poisson (Poinsson distribution) 2.3.6 Phân bố Gamma (Gamma distribution) _ 2.3.7 Mối liên hệ phân bố mũ phân bố Gamma _ 16 17 19 20 20 21 22 2.4 Tiến trình ngẫu nhiên (stochastic process) 23 2.4.1 Khái niệm định nghĩa 23 2.4.2 Phân loại 24 2.5 Các đặc tính thơng kê tiến trình ngẫu nhiên _ 25 cu u 2.5.1 Các hàm quan hệ xác suất _ 25 2.5.2 Các trung bình thống kê _ 26 2.5.3 Tính dừng _ 27 2.6 Các tiến trình ngẫu nhiên thường gặp _ 30 2.6.1 Tiến trình đếm 30 2.6.2 Tiến trình Poisson _ 31 2.7 Kết luận _ 31 Chương Hệ thống hàng đợi _32 3.1 Giới thiệu 32 3.2 Mô hình hàng đợi – Ký hiệu Kendall 32 3.2.1 Mơ hình hàng đợi đơn 32 3.2.2 Ký hiệu Kendall 33 3.2.3 Các tham số quan trọng để đánh giá đặc tính hệ thống hàng đợi _ 35 CuuDuongThanCong.com https://fb.com/tailieudientucntt 3.3 Hệ thống hàng đợi trạng thái ổn định – Định lý Little _ 36 3.3.1 Hệ thống hàng đợi ổn định 36 3.3.2 Định lý Little _ 38 3.3.3 Một số đặc tính khác hệ thống đóng, hoạt động trạng thái ổn định 40 3.4 Hàng đợi M/M/1/1 _ 41 3.5 Hàng đợi M/M/1/ _ 44 3.5.1 Xác suất có n yêu cầu hệ thống 44 3.5.2 Tính tốn tham số hiệu 46 3.6 Tiến trình sinh – tử (Birth – Death Process) _ 49 3.7 Hàng đợi M/M/1/K 49 3.7.1 Xác suất có n yêu cầu hệ thống 50 3.7.2 Tính tốn tham số hiệu 50 3.8 Hàng đợi M/M/c/ _ 54 c om 3.8.1 Xác suất có n yêu cầu hệ thống 55 Chương Mạng hàng đợi _56 4.1 Mạng nối tiếp _ 56 Chương Định tuyến mạng thông tin _57 5.1 Yêu cầu định tuyến mạng thông tin 57 ng 5.1.1 Vai trò định tuyến mạng thông tin _ 57 5.1.2 Các khái niệm lý thuyết graph _ 57 co 5.2 Các mơ hình định tuyến quảng bá (broadcast routing) 59 an 5.2.1 Lan tràn gói (flooding) _ 5.2.2 Định tuyến bước ngẫu nhiên (random walk) _ 5.2.3 Định tuyến khoai tây nóng (hot potato) _ 5.2.4 Định tuyến nguồn (source routing) mơ hình (spanning tree) _ 5.2.5 Duyệt _ 59 60 60 61 61 th 5.3 Các mơ hình định tuyến thơng dụng _ 82 5.3.1 Định tuyến ngắn (Shortest path Routing) 82 ng 5.4 Bài tập (Pending) _ 105 Chương Điều khiển luồng chống tắc nghẽn 106 6.1 Tổng quan 106 106 109 110 110 111 6.2.1 Định nghĩa 6.2.2 Tính cơng mặt băng truyền _ 6.2.3 Tính cơng mặt đệm 6.2.4 Cơ chế phát lại ARQ 6.2.5 Stop-and-Wait ARQ 6.2.6 Go-back-N ARQ _ 6.2.7 Selective repeat ARQ _ 112 112 112 114 115 121 128 du o 6.1.1 Mở đầu 6.1.2 Khái niệm điều khiển luồng _ 6.1.3 Khái niệm chống tắc nghẽn _ 6.1.4 Nhiệm vụ chủ yếu điều khiển luồng chống tắc nghẽn _ 6.1.5 Phân loại điều khiển luồng tránh tắc nghẽn _ cu u 6.2 Tính cơng 112 6.3 Điều khiển luồng tránh tắc nghẽn theo phương pháp cửa sổ 130 6.3.1 Điều khiển luồng theo cửa sổ (Window Flow Control) 131 6.3.2 Điều khiển tắc nghẽn sử dụng cửa sổ thích ứng (adaptive window) 136 6.4 Điều khiển luồng chống tắc nghẽn dựa băng thông (rate-based flow control) _ 142 6.4.1 Khái niệm 142 6.4.2 Điều khiển băng thơng theo thuật tốn gáo rò (leaky bucket) _ 143 6.4.3 Thuật toán GPS (pending) 147 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6.5 Bài tập (Pending) _ 148 Chương Kỹ thuật mô _149 7.1 Giới thiệu _ 149 7.2 Mô dựa kiện rời rạc công cụ _ 149 7.2.1 Phương pháp mô dựa kiện rời rạc _ 149 7.2.2 Các công cụ mô thông dụng dựa kiện rời rạc 152 7.3 Công cụ mô mạng NS2 _ 153 7.3.1 Cấu trúc 153 7.3.2 Các tiện ích NS hỗ trợ cho mô mạng [Pending] _ 155 7.3.3 Thí dụ (Pending) _ 155 7.4 Kết luận (Pending) 155 7.5 Bài tập (Pending) _ 156 c om Tài liệu tham khảo 157 cu u du o ng th an co ng Phụ lục 158 CuuDuongThanCong.com https://fb.com/tailieudientucntt Mục lục hình vẽ Hình 1-1 Các bước mơ hình hóa đánh giá đặc tính hệ thống Hình 2-1 Hàm mật độ xác suất 10 Hình 2-2.Hàm phân phối xác suất 11 Hình 2-3: Kết Thí dụ 2-5 13 Hình 3-1 Hệ thống hàng đợi với N trạm phục vụ, hàng đợi có độ lớn K 33 c om Hình 3-2 Round robin 34 Hình 3-3 Mạng đóng 36 Hình 3-4 Quan hệ số yêu cầu tới số yêu cầu phục vụ 39 ng Hình 3-5.Hệ thống hàng đợi quan sát với hai ranh giới khác nhau: (a) Hàng đợi trạm phục vụ; (b) Hàng đợi 41 Hình 3-7 Khoảng thời gian xét 42 Hình 3-8 Hàng đợi M/M/1/ 44 co Hình 3-6 Hàng đợi M/M/1/1 42 an Hình 3-9 Cân xác suất trạng thái i Tiến trìnhsinh – tử49 th Hình 3-10 Hệ thống M/M/1/K 49 ng Hình 3-11 Hệ thống hàng đợi M/M/1/K 50 Hình 3-12 Hệ thống M/M/1/K quan điểm hệ thống đóng 53 du o Hình 3-13 Hàng đợi M/M/c/ 54 Hình 5-1 Hàng chờ bên router 61 Hình 5-2 Duyệt 62 cu u Hình 5-3 Các thành phần 66 Hình 5-4 Phép tính Minimum Spanning Tree ( MST) 74 CuuDuongThanCong.com https://fb.com/tailieudientucntt Mục lục bảng biểu Bảng 2-1 Điểm tương ứng với kết tung xúc xắc cu u du o ng th an co ng c om Bảng 2-2: Kết Thí dụ 2-5 13 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt ... cho chặng Trong trường hợp truyền thông tin cự ly không xa (với đa phần chế truyền tin, trừ thông tin vệ tinh) kích thước cửa sổ thường (do số nút mạng thông tin phải qua 1, trễ truyền sóng khơng... lượng gói tin vào mạng thông qua việc cấp phát số lượng hạn chế thẻ Mỗi gói tin muốn vào mạng cần phải nhận thẻ nút mà gói tin vào trả lại thẻ nút mà gói tin khỏi mạng Như vậy, tổng số gói tin tồn... băng thơng Cơ chế kiểm sốt băng thông đảm bảo lượng thông tin người dùng đưa vào mạng khơng vượt q mức nhằm tránh tắc nghẽn mạng Trong số trường hợp cụ thể, thông tin người dùng đưa vào mạng vượt