Nội dung

CƠ SỞ MẠNG THÔNG TIN ĐIỆN TỬ - VIỄN THÔNG Khoa Điện tử Viễn Thông Trường Đại học Bách khoa Hà nội Các từ viết tắt FAS Frame Alignment Signal IEEE Institute of Electronics and Electrical Engineering ITU International Telecommunication Union MFAS Multi-Frame Signal PDF Alignment Probability Density Function pdf probability function TDMA Time Access 2 Division distribution Multiple Bảngđối chiếu thuật ngữAnh -Việt Tiếng Việt Tiếng Anh Băng tần thông dải Band Pass Băng tần cơ sở Baseband Trạm gốc Base Station Kênh Channel Va đập Collision Cuộc nối Connection Mã hoá điều khiển lỗi Error Control Coding Mật độ phổ năng lượng Energy Spectral Density Khung Frame Đáp ứng tần số Frequency Response Giao thoa giữa các ký tự Intersymbol Interference Đa khung Multi-frame Đa truy nhập Multiple Access Bộ ghép kênh, bộ hợp kênh Multiplexer Hiệu ứng xa - gần Near – Far Effect Kết nối, liên kết Link Đầu thu, phần thu Sender Đầu thu, phần thu, đích Sink Mã hoá nguồn Source Coding Ghép kênh phân chia theo thời gian Bộ phát, khối phát Time Division Multiplexing Transmitter 3 Mục lục Các từ viết tắt_____________________________________________ 2 Bảng đối chiếu thuật ngữ Anh - Việt __________________________ 3 Mục lục _________________________________________________ 4 Mục lục hình vẽ __________________________________________ 6 Mục lục bảng biểu_________________________________________ 6 Chương 1 Giới thiệu _________________ Error! Bookmark not defined. 1.1. Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống _______________________________________________ 1 1.2. Các khái niệm cơ bản trong hệ thống thong tin ______________ 1 1.3. Các bước và phương pháp đánh giá một mạng thông tin ______ 1 1.3.1. Đo đạc, thu tập kế quả thống kê __________________________ 1 1.3.2. Mô hình hóa toán học __________________________________ 1 1.3.3. Mô phỏng ___________________________________________ 1 1.4. Các công cụ phục vụ cho việc đánh giá chất lượng hoạt động của mạng _____________________________________________________ 1 Chương 2 Hàng đợi – Các hệ thống thời gian liên tụcError! Bookmark not defined. 2.1. Giới thiệu lý thuyết hàng đợi ____________________________ 2 2.1.1. Hàng đợi và đặc điểm __________________________________ 2 2.1.2. Các tham số hiệu năng trung bình _________________________ 6 2.2. Nhắc lại các khái niệm thống kê cơ bản ___________________ 11 2.2.1. Tiến trình điểm ______________________________________ 11 2.2.2. Tiến trình Poisson ____________________________________ 13 2.3. Định luật Little ______________________________________ 15 2.3.1. Công thức Little _____________________________________ 15 2.3.2. Chứng minh công thức Little ___________________________ 16 2.4. Các mô hình hàng đợi _________________________________ 17 2.4.1. Ký hiệu Kendall _____________________________________ 17 2.4.2. Quá trình Sinh-Tử (Birth-Death)_________________________ 18 2.4.3. Hàng đợi M/M/1_____________________________________ 19 2.4.4. Hàng đợi M/M/1/K ___________________________________ 21 2.4.5. Hàng đợi M/M/C ____________________________________ 22 2.5. Lý thuyết lưu lượng ___________________________________ 22 2.5.1. Khái niệm về lưu lượng và đơn vị Erlang __________________ 22 4 2.5.2. Hệ thống tổn thất (Loss System) và công thức Erlang B _______ 25 2.5.3. Hệ thống trễ (Delay) và công thức Erlang C ________________ 28 2.6. Hệ thống hàng đợi có ưu tiên ___________________________ 30 2.6.1. Qui tắc và tổ chức hàng đợi ____________________________ 31 2.6.2. Độ ưu tiên của khách hàng trong hàng đợi ưu tiên ___________ 34 2.6.3. Duy trì qui tắc hàng đợi, luật Kleinrock ___________________ 34 2.6.4. Một số hàng đợi đơn server ____________________________ 35 2.6.5. Kết luận ___________________________________________ 35 2.7. Bài tập (Pending) _____________________________________ 36 Chương 3 Mạng hàng đợi_____________ Error! Bookmark not defined. 3.1. Mạng nối tiếp ________________________________________ 37 Chương 4 Định tuyến trong mạng thông tinError! Bookmark not defined. 4.1. Yêu cầu về định tuyến trong mạng thông tin _______________ 38 4.1.1. Vai trò của định tuyến trong mạng thông tin ________________ 38 4.1.2. Các khái niệm trong lý thuyết graph ______________________ 38 4.2. Các mô hình định tuyến quảng bá (broadcast routing)_______ 40 4.2.1. Lan tràn gói (flooding) ________________________________ 40 4.2.2. Định tuyến bước ngẫu nhiên (random walk) ________________ 41 4.2.3. Định tuyến khoai tây nóng (hot potato) ____________________ 41 4.2.4. Định tuyến nguồn (source routing) và mô hình cây (spanning tree) _________________________________________________________ 42 4.2.5. Duyệt cây __________________________________________ 43 4.3. Các mô hình định tuyến thông dụng _____________________ 65 4.3.1. Định tuyến ngắn nhất (Shortest path Routing)_______________ 65 4.4. Bài tập (Pending) _____________________________________ 90 Chương 5 Điều khiển luồng và chống tắc nghẽnError! Bookmark not defined. 5.1. Tổng quan __________________________________________ 91 5.1.1. Mở đầu ____________________________________________ 91 5.1.2. Khái niệm điều khiển luồng ____________________________ 95 5.1.3. Khái niệm chống tắc nghẽn_____________________________ 95 5.1.4. Nhiệm vụ chủ yếu của điều khiển luồng và chống tắc nghẽn____ 95 5.1.5. Phân loại điều khiển luồng và tránh tắc nghẽn_______________ 97 5.2. Tính công bằng ______________________________________ 97 5.2.1. Định nghĩa _________________________________________ 97 5.2.2. Tính công bằng về mặt băng truyền ______________________ 97 5.2.3. Tính công bằng về mặt bộ đệm __________________________ 98 5.2.4. Cơ chế phát lại ARQ _________________________________ 99 5.2.5. Stop-and-Wait ARQ _________________________________ 101 5 5.2.6. Go-back-N ARQ ___________________________________ 107 5.2.7. Selective repeat ARQ ________________________________ 113 5.3. Điều khiển luồng và tránh tắc nghẽn theo phương pháp cửa sổ115 5.3.1. Điều khiển luồng theo cửa sổ (Window Flow Control) _______ 116 5.3.2. Điều khiển tắc nghẽn sử dụng cửa sổ thích ứng (adaptive window) ________________________________________________________ 121 5.4. Điều khiển luồng và chống tắc nghẽn dựa trên băng thông (ratebased flow control) ________________________________________ 127 5.4.1. Khái niệm_________________________________________ 127 5.4.2. Điều khiển băng thông theo thuật toán gáo rò (leaky bucket) __ 128 5.4.3. Thuật toán GPS (pending) ____________________________ 133 5.5. Bài tập (Pending) ____________________________________ 133 Chương 6 Kỹ thuật mô phỏng __________ Error! Bookmark not defined. 6.1. Giới thiệu __________________________________________ 134 6.2. Mô phỏng dựa trên các sự kiện rời rạc và các công cụ ______ 134 6.2.1. Phương pháp mô phỏng dựa trên sự kiện rời rạc ____________ 134 6.2.2. Các công cụ mô phỏng thông dụng dựa trên sự kiện rời rạc ___ 137 6.3. Công cụ mô phỏng mạng NS2__________________________ 139 6.3.1. Cấu trúc __________________________________________ 139 6.3.2. Các tiện ích trong NS hỗ trợ cho mô phỏng mạng [Pending]___ 141 6.3.3. Thí dụ (Pending)____________________________________ 141 6.4. Kết luận (Pending)___________________________________ 141 6.5. Bài tập (Pending) ____________________________________ 141 Tài liệu tham khảo ______________________________________ 142 Phụ lục 1 ______________________________________________ 143 Mục lục hình vẽ Hình 1-1 Đường truyền, kết nối và cuộc nối Error! Bookmark not defined. Hình 1-2 Ghép kênh và đa truy nhậpError! Bookmark not defined. Mục lục bảng biểu Bảng 1-1. Độ rộng băng tần của một số tín hiệu cơ bản ............................................ Error! Bookmark not defined. 6 Chương 1 GIỚI THIỆU 1.1. Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống 1.2. Các khái niệm cơ bản trong hệ thống thông tin 1.3. Các bước và phương pháp đánh giá một mạng thông tin 1.3.1. Đo đạc, thu tập kế quả thống kê 1.3.2. Mô hình hóa toán học 1.3.3. Mô phỏng 1.4. Các công cụ phục vụ cho việc đánh giá chất lượng hoạt động của mạng Chương 2 HÀNG ĐỢI-HT TG LIÊN TỤC 2.1. Giới thiệu lý thuyết hàng đợi 2.1.1. Hàng đợi và đặc điểm Trong bất cứ một hệ thống nào thì khách hàng đi đến các điểm cung cấp dịch vụ và rời khỏi hệ thống khi dịch vụ đã được cung cấp. Ví dụ: Các hệ thống điện thoại: khi số lượng lớn khách hàng quay số để kết nối đến một trong những đường ra hữu hạn của tổng đài. Trong mạng máy tính: khi mà gói tin được chuyển từ nguồn tới đích và đi qua một số lượng các nút trung gian. Hệ thống hàng đợi xuất hiện tại mỗi nút ở quá trình lưu tạm thông tin tại bộ đệm. Hệ thống máy tính: khi các công việc tính toán và tuyến làm việc của hệ thống yêu cầu dịch vụ từ bộ xử lý trung tâm và từ các nguồn khác. Những tình huống này được diễn tả bằng hình vẽ sau: Hình 2-1 Mô hình chung của hệ thống hàng đợi Người ta mô tả tiến trình đến và tiến trình phục vụ như thế nào? Hệ thống có bao nhiêu server? Có bao nhiêu vị trí đợi trong hàng đợi? Có bất kỳ quy tắc nội bộ đặc biệt nào không (yêu cầu dịch vụ, mức độ ưu tiên, hệ thống còn rỗi không)? Đặc điểm của hệ thống hàng đợi Miêu tả của tiến trình đến (phân bố khoảng thời gian đến) Miêu tả của tiến trình phục vụ (phân bố thời gian phục vụ) Số lượng server Số lượng các vị trí đợi Các quy tắc hàng đợi đặc biệt: 2 Quy tắc phục vụ (FCFS, LCFS, RANDOM) Thời gian rỗi (phân bố thời gian rỗi, khi mà thời gian rỗi bắt đầu ) Mức độ ưu tiên Những luật khác Với một mạng cụ thể của hàng đợi gồm có các thông tin sau: Sự kết hợp giữa các hàng đợi Chiến lược định tuyến: Xác định (Deterministic) Dựa vào một lớp Thống kê Xử lý nghẽn mạng (khi bộ đệm tại đích bị đầy) Số lượng khách hàng bị suy giảm Hàng đợi gốc bị nghẽn Tái định tuyến Chúng ta sẽ xem xét ví dụ về các mạng hàng đợi đơn giản khác Hình 2-2: Ví dụ về mạng hàng đợi mở 3 Hình 2-3 Ví dụ về mạng hàng đợi đóng Phân tích hệ thống hàng đợi hoặc mạng hàng đợi bao gồm: Phân tích giải tích Quá trình mô phỏng Cả hai phương pháp trên Kết quả giải tích đạt được: Yêu cầu ít tính toán Đưa ra kết quả chính xác (không xảy ra lỗi xác suất) Những kết quả thu được (các thông số dịch vụ) được chia thành hai nhóm lớn: Dành cho người sử dụng Dành cho các nhà cung cấp phục vụ Thông số quan trọng cho người sử dụng: Trễ hàng đợi Tổng trễ (bao gồm trễ hàng đợi và trễ phục vụ ) Số lượng khách hàng trong hàng đợi Số lượng khách hàng trong hệ thống (gồm khách hàng chờ và khách hàng đang được phục vụ ) Xác suất nghẽn mạng (khi kích thước bộ đệm hữu hạn) Xác suất chờ để phục vụ Thông số quan trọng cho các nhà cung cấp dịch vụ: Khả năng sử dụng server Khả năng sử dụng bộ đệm 4