Cơ sở mạng thông tin

Khoa Điện tử Viễn Thông

Trường Đại học Bách khoa Hà nội

Cơ sởmạng thông tin

Giáo trình dành cho sinh viên đại học

ngành Điện tử - Viễn thông

2

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 Time Division Multiplexing

Bộ phát, khối phát Transmitter

3

Mục lục

Các từ viết tắt_________________________________________________ Error! Bookmark not defined.

Bảng đối chiếu thuật ngữ Anh - Việt_____________________________________________________2

Mục lục ___________________________________________________________________________3

Mục lục hình vẽ_____________________________________________________________________5

Mục lục bảng biểu___________________________________________________________________6

Chương 1 Giới thiệu _________________________________________________________________1

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ục _______________________________________2

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 __________________________________________________________________ 5

2.2. Nhắc lại các khái niệm thống kê cơ bản _____________________________________________________ 10

2.2.1. Tiến trình điểm _______________________________________________________________________________ 10

2.2.2. Tiến trình Poisson _____________________________________________________________________________ 12

2.3. Định luật Little _________________________________________________________________________ 14

2.3.1. Công thức Little_______________________________________________________________________________ 14

2.3.2. Chứng minh công thức Little_____________________________________________________________________ 14

2.4. Các mô hình hàng đợi ___________________________________________________________________ 15

2.4.1. Ký hiệu Kendall ______________________________________________________________________________ 15

2.4.2. Quá trình Sinh-Tử (Birth-Death) __________________________________________________________________ 17

2.4.3. Hàng đợi M/M/1 ______________________________________________________________________________ 17

2.4.4. Hàng đợi M/M/1/K ____________________________________________________________________________ 19

2.4.5. Hàng đợi M/M/C______________________________________________________________________________ 20

2.5. Lý thuyết lưu lượng _____________________________________________________________________ 21

2.5.1. Khái niệm về lưu lượng và đơn vị Erlang ___________________________________________________________ 21

2.5.2. Hệ thống tổn thất (Loss System) và công thức Erlang B________________________________________________ 23

2.5.3. Hệ thống trễ (Delay) và công thức Erlang C _________________________________________________________ 26

2.6. Hệ thống hàng đợi có ưu tiên______________________________________________________________ 28

2.6.1. Qui tắc và tổ chức hàng đợi ______________________________________________________________________ 29

2.6.2. Độ ưu tiên của khách hàng trong hàng đợi ưu tiên_____________________________________________________ 31

2.6.3. Duy trì qui tắc hàng đợi, luật Kleinrock_____________________________________________________________ 32

2.6.4. Một số hàng đợi đơn server ______________________________________________________________________ 33

2.6.5. Kết luận_____________________________________________________________________________________ 33

2.7. Bài tập (Pending) _______________________________________________________________________ 34

Chương 3 Mạng hàng đợi ____________________________________________________________35

3.1. Mạng nối tiếp __________________________________________________________________________ 35

4

Chương 4 Định tuyến trong mạng thông tin ______________________________________________36

4.1. Yêu cầu về định tuyến trong mạng thông tin_________________________________________________ 36

4.1.1. Vai trò của định tuyến trong mạng thông tin _________________________________________________________ 36

4.1.2. Các khái niệm trong lý thuyết graph _______________________________________________________________ 36

4.2. Các mô hình định tuyến quảng bá (broadcast routing) ________________________________________ 38

4.2.1. Lan tràn gói (flooding)__________________________________________________________________________ 38

4.2.2. Định tuyến bước ngẫu nhiên (random walk) _________________________________________________________ 39

4.2.3. Định tuyến khoai tây nóng (hot potato) _____________________________________________________________ 39

4.2.4. Định tuyến nguồn (source routing) và mô hình cây (spanning tree)________________________________________ 40

4.2.5. Duyệt cây ___________________________________________________________________________________ 40

4.3. Các mô hình định tuyến thông dụng________________________________________________________ 59

4.3.1. Định tuyến ngắn nhất (Shortest path Routing)________________________________________________________ 59

4.4. Bài tập (Pending) _______________________________________________________________________ 80

Chương 5 Điều khiển luồng và chống tắc nghẽn __________________________________________81

5.1. Tổng quan_____________________________________________________________________________ 81

5.1.1. Mở đầu _____________________________________________________________________________________ 81

5.1.2. Khái niệm điều khiển luồng______________________________________________________________________ 84

5.1.3. Khái niệm chống tắc nghẽn ______________________________________________________________________ 85

5.1.4. Nhiệm vụ chủ yếu của điều khiển luồng và chống tắc nghẽn ____________________________________________ 85

5.1.5. Phân loại điều khiển luồng và tránh tắc nghẽn________________________________________________________ 86

5.2. Tính công bằng_________________________________________________________________________ 86

5.2.1. Định nghĩa___________________________________________________________________________________ 86

5.2.2. Tính công bằng về mặt băng truyền________________________________________________________________ 87

5.2.3. Tính công bằng về mặt bộ đệm ___________________________________________________________________ 87

5.2.4. Cơ chế phát lại ARQ___________________________________________________________________________ 88

5.2.5. Stop-and-Wait ARQ ___________________________________________________________________________ 90

5.2.6. Go-back-N ARQ______________________________________________________________________________ 95

5.2.7. Selective repeat ARQ _________________________________________________________________________ 101

5.3. Điều khiển luồng và tránh tắc nghẽn theo phương pháp cửa sổ_________________________________ 103

5.3.1. Điều khiển luồng theo cửa sổ (Window Flow Control)________________________________________________ 103

5.3.2. Điều khiển tắc nghẽn sử dụng cửa sổ thích ứng (adaptive window) ______________________________________ 109

5.4. Điều khiển luồng và chống tắc nghẽn dựa trên băng thông (rate-based flow control) _______________ 114

5.4.1. Khái niệm __________________________________________________________________________________ 114

5.4.2. Điều khiển băng thông theo thuật toán gáo rò (leaky bucket) ___________________________________________ 115

5.4.3. Thuật toán GPS (pending)______________________________________________________________________ 119

5.5. Bài tập (Pending) ______________________________________________________________________ 119

Chương 6 Kỹ thuật mô phỏng ________________________________________________________120

6.1. Giới thiệu_____________________________________________________________________________ 120

6.2. Mô phỏng dựa trên các sự kiện rời rạc và các công cụ ________________________________________ 120

6.2.1. Phương pháp mô phỏng dựa trên sự kiện rời rạc _____________________________________________________ 120

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 ____________________________________________ 123

6.3. Công cụ mô phỏng mạng NS2____________________________________________________________ 124

6.3.1. Cấu trúc____________________________________________________________________________________ 124

6.3.2. Các tiện ích trong NS hỗ trợ cho mô phỏng mạng [Pending]____________________________________________ 126

6.3.3. Thí dụ (Pending) _____________________________________________________________________________ 126

6.4. Kết luận (Pending) _____________________________________________________________________ 126

6.5. Bài tập (Pending) ______________________________________________________________________ 126

Tài liệu tham khảo_________________________________________________________________127

Phụ lục 1 ________________________________________________________________________128

5

Mục lục hình vẽ

Hình 1-1 Đường truyền, kết nối và cuộc nối <Caption>Error! Bookmark not defined.

Hình 1-2 Ghép kênh và đa truy nhập....Error! Bookmark not defined.

6

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 <Caption>Error! Bookmark not defined.

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 thong 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

2

Chương 2 Hàng đợi – Các hệ

thống thời gian 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:

3

 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

S

S

S

S M

Hình 2-2: Ví dụ về mạng hàng đợi mở

Hình 2-3 Ví dụ về mạng hàng đợi đóng

4

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

 Lợi ích thu được (thông số dịch vụ và các xem xét về kinh tế)

 Lợi ích bị mất (thông số dịch vụ và các xem xét về kinh tế)

Đáp ứng nhu cầu của người sử dụng

 Chất lượng dịch vụ (QoS):

 Tổn thất (PDF, mean)

 Trễ (PDF, mean)

 Jitter (PDF, mean)

Đưa ra các thông số trên để thu được:

 Hàm phân bố xác suất

 Các giá trị trung bình

 Đo được các thời điểm cực đại, cực tiểu

Các hàm phân bố xác suất chứa đựng đầy đủ các thông tin liên quan đến các

thông số quan tâm. Tuy nhiên, việc thiết lập được các hàm này là khó thực

hiện.

5

Phân tích hệ thống hàng đợi được chia thành:

 Phân tích ở thời gian ngắn (dựa trên một thời điểm nhất định)

 Phân tích trong một khoảng thời gian (trạng thái ổn định) – (dựa trên tham

số vô hạn)

Cấu trúc logic của phân tích hệ thống hàng đợi

 Đo được nhiều thông số thống kê: mean-mean, moments, transform, pdf

 Phân tích thời gian ngắn sử dụng cho các trừong hợp đơn giản- sử dụng

các phương pháp mô phỏng hay xấp xỉ

 Việc phân tích chính xác không thể cho áp dụng cho quá trình ổn định- sử

dụng các phương pháp xấp xỉ, nếu không thì dùng các phương pháp mô

phỏng.

Tiếp theo chúng ta sẽ có các kết luận sau:

Kết luận chung: các giả thiết liên quan đến đặc tính và cấu trúc của hệ

thống hàng đợi đạt được kết quả chính xác ít nhất là cho các thông số

hiệu năng trung bình với điều kiện ổn định.

2.1.2. Các tham số hiệu năng trung bình

Ví dụ về hệ thống hàng đợi đơn giản

Hình 2-4 Hệ thống hàng đợi đơn giản

λ - tốc độ đến trung bình , thời gian đến trung bình -1/λ

µ - tốc độ phục vụ trung bình, thời gian phục vụ trung bình 1/µ

Với kích thước của bộ đệm là vô hạn, quy tắc phục vụ là FCFS (đến trước

phục vụ trước )

Xét khoảng thời gian Δt, và xét những sự kiện đến trong khoảng thời gian này:

6

Hình 2-5. Các sự kiện đến trong thời gian Δt

Sự kiện A: Có 1 sự kiện đến trong Δt

Sự kiện B: không có sự kiện đến trong Δt

Sự kiện C: Có nhiều hơn 1 sự kiện đến trong Δt

Giả sử rằng Δt →0. Như vậy ta sẽ có:

- Pr{A}= λ Δt

- Pr{B}= 1- λ Δt

- Giả thiết P{C}= 0,

với 1/λ là khoảng thời gian đến trung bình (thực tế được phân bố theo hàm mũ

của tiến trình đến Poisson).

Xét khoảng thời gian Δt và xét những sự kiện đi trong khoảng thời gian này

Hình 2-6: Các sự kiện đi trong thời gian Δt

Sự kiện A: Có 1 sự kiện đi trong Δt

Sự kiện B: không có sự kiện đi nào trong Δt

Sự kiện C: Có nhiều hơn 1 sự kiện đi trong Δt

Giả sử rằng Δt →0. Như vậy ta sẽ có:

Pr{A}= µΔt

Pr{B}= 1- µΔt

7

Giả thiết Pr{C}= 0, với 1/µ là thời gian phục vụ trung bình (thực tế được phân

bố theo hàm mũ.

D là sự kiện của 1 hoặc nhiều sự đến AND với sự kiện của 1 hoặc nhiều sự đi

trong khoảng Δt

Giả sử Pr{D}=0, (2-1)

Thực ra, nó chỉ ra rằng khi Δt nhỏ, sự kiện nhân (vừa đi vừa đến) là không xảy

ra.

Ngoài các giả thiết trên về đặc tính của tiến trình đến và tiến trình phục vụ, còn

có thêm các giả thiết sau:

 Tiến trình đến là tiến trình Poisson với tham số λ

 Khoảng thời gian đến phân bố theo hàm mũ với tham số 1/λ

 Thời gian phục vụ phân bố theo hàm mũ với tham số 1/µ

 Tiến trình đến là độc lập với tiến trình phục vụ và ngược lại

Để phân tích hệ thống hàng đợi cần hiểu khái niệm “Trạng thái hệ thống”. Có

thể định nghĩa thông qua biến thích hợp mô tả “ Sự phát triển theo thời gian”

của hệ thống hàng đợi. Để thuận tiện cho hệ thống hàng đợi biến được chọn sẽ

là số khách hàng trong hệ thống tại thời điểm t.

Trạng thái hệ thống tại t = N(t)= Số lượng khách hàng tại thời điểm t

(2-2)

Tức là :

pN(t)=Pr{N(t)=N} (2-3)

với

pN(t) là ký hiệu của trạng thái thứ N của hệ thống tại thời điểm t.

Pr{N(t)=N} là xác suất có N khách hàng trong hệ thống tại thời điểm t.

Có nghĩa là có N khách hàng trong hệ thống tại thời điểm t.

Sử dụng trạng thái đầu tiên tại t=0, nếu ta có thể tìm pN(t) thì có thể mô tả hệ

thống có quan hệ về mặt thời gian như thế nào?

Tiếp theo, cho thời gian Δt →0.

Xét các trạng thái có thể của hệ thống {0,1,…}(bằng đúng số lượng khách

hàng trong hệ thống) tại thời điểm t ta có thể tìm trạng thái của hệ thống tại

thời điểm t+Δt như sau:

p0(t+Δt )= p0(t)(1-λΔt)+p1(t)µΔt, N=0.

pN(t+Δt )= pN(t)(1-λ Δt-µΔt)+pN-1(t)λΔt+ pN+1(t)µΔt, N>0

(2-4)

ta luôn có điều kiện phân bố chuẩn: