Cơ sở mạng thông tin - Cơ sở mạng thông tin điện tử - viễn thông

Nội dung text: Cơ sở mạng thông tin - Cơ sở mạng thông tin điện tử - viễn thông

1. 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
2. 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
3. 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 Alignment Signal PDF Probability Density Function pdf probability distribution function TDMA Time Division Multiple Access 2
4. 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 Time Division Multiplexing gian Bộ phát, khối phát Transmitter 3
5. 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
6. 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
7. 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 (rate- based 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
8. 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
9. 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
10. 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
11. 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
12. 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. 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. 5
13. 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 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: 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, 6
14. 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 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 7
15. Để 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:  pi ( t ) 1, t 0 (2-5) i Tức là chuẩn hóa các pi(t), t≥0, thành các tính chất phân bố rời rạc theo thời gian. Ta có thể tính giới hạn khi Δt →0 và có hệ phương trình vi phân: dp0 () t p0( t )  p 1 ( t ), N 0 dt (2-6) dp t)( N (  )p ( t )  p ( t )  p ( t ), N 0 dt NNN 1 1 Để giải ta phảo cho điều kiện ban đầu. 8
16. Giả sử rằng hệ thống hàng đợi bắt đầu tại thời điểm t=0 với N khách hàng ở trong hệ thống, điều kiện ban đầu được viết như sau: pi(0)=0, với i≠N pN(0)=1, với i=N (2-7) Sử dụng điều kiện ban đầu phù hợp hệ thống có thể được giải để được giải pháp thời gian ngắn (transient solution), một giải pháp phức tạp thậm chí cho các hệ đơn giản nhất. Bây giờ ta xét giải pháp trạng thái ổn định (equilibrium solution), t→∞. Khi đó ta có: dp t)( 0 0,N 0 dt (2-8) dp() t N 0,N 0 dt Vì vậy, p0(t)=p0, với N=0 pN(t)=pN, với N>0 (2-9) Định nghĩa ρ=λ /µ với ngụ ý rằng hệ thống hàng đợi ổn định với ρ 0 (2-10) Gỉa sử tuân theo điều kiện phân bố chuẩn, ta có: i pi = ρ (1-ρ ), i=0,1, (2-11) với giải pháp trạng thái ổn định cho phân bố trạng thái với ρ <1. giải pháp trạng thái ổn định không phụ thuộc điều kiện phân bố ban đầu. Tuy nhiên, nó cần điều kiện rằng tốc độ đến nhỏ hơn tốc độ phục vụ. Các tham số hiệu năng trung bình Số lượng trung bình của khách hàng trong hệ thống Nhắc lại rằng phân bố của trạng thái ổn định cho số lượng khách hàng trong hệ thống khi t→∞. Ví vậy, có thể suy ra số khách hàng trung bình trong hệ thống từ phân bố trạng thái ổn định của hệ thống như sau: i E[ N ]  ipi  i (1 ) (2-12) i 0i 0 1 Kết quả trên không áp dụng cho số trung bình khách hàng trong hệ thống tại một khoảng thời gian ngắn t (arbitrary time t). 9
17. Số lượng trung bình của khách hàng trong hàng đợi Chú ý rằng số lượng khách hàng trong hàng đợi thì bằng với số lượng khách hàng trong hệ thống trừ đi 1. Sử dụng cùng các giả thiết ta có: 2 E[ NQ ]  ( i 1) p i  ipi  pi (1 p0 ) i 1i 1i 1 1 1 1 (2-13) Chú ý rằng tổng bắt đầu từ i=1, do sự kiện khách hàng đợi chỉ đúng khi có nhiều hơn 0 khách hàng trong hệ thống. Chú ý rằng (i-1)!, do đang tìm số lượng khách hàng trung bình trong hàng đợi. Thời gian trung bình trong hệ thống Thời gian này có thể được phân chia thành hai thành phần : Thời gian đợi Thời gian phục vụ Tính toán các tham số hiệu năng này đòi hỏi những giả thiết thêm dựa trên đặc tính của hệ thống hàng đợi : Quy tắc phục vụ khách hàng : Giả sử quy tắc “ first-come, first served” là khách hàng được phục vụ theo thứ tự như khi đến hệ thống Phân bố trạng thái ổn định pk, k=0,1, , cũng giống như phân bố xác suất của số lượng khách hàng trong hệ thống. Thời gian phục vụ dư trung bình của khách hàng sẽ dùng để phục vụ khi tiến trình đến xảy ra với tốc độ 1/µ, cũng giống như vậy. Vì vậy được gọi là đặc tính không nhớ. Sử dụng các giả thiết cho thời gian trung bình trong hệ thống của khách hàng : k 1 k 1 1 EW  pk  pk  pk (2-14) k 0k 0 k 0  (1 ) Thời gian trung bình trong hàng đợi (thời gian đợi để được phục vụ) Với các giả thiết trên ta có: k EWQ   pk (2-15) k 0  (1 ) Chú ý rằng thời gian trung bình trong hàng đợi bằng với thời gian trung bình hệ thống trừ đi thời gian phục vụ: 1 1 1 EWEW    (2-16) Q  (1 )  (1 ) Có thể có khả năng rằng khách hàng phải chờ để được phục vụ 10
18. Sử dụng phân bố trạng thái ổn định pk, k=0,1, ta chú ý rằng lượng khách hàng đến luôn phải đợi để được phục vụ nếu số lượng khách hàng lớn hơn 0 trong hệ thống. Vì vậy, Pwait=1-p0=ρ (2-17) Sử dụng server Ý nghĩa vật lý của tham số hiệu năng là nó đưa ra khoảng thời gian khi server bận. vì vậy, Pbusy=1-p0=ρ (2-18) Các cách tiếp cận đã trình bày được sử dụng để phân tích bất kỳ một hệ thống hàng đợi đều phải có các giả thiết sau: Tiến trình đến là tiến trình poisson, có nghĩa là khoảng thời gian đến được phân bố theo hàm mũ. Tiến trình đến với tốc độ đến thay đổi. Hệ thống có một hoặc nhiều server Thời gian phục vụ có dạng phân bố hàm mũ Tiến trình đến là độc lập với các tiến trình phục vụ và ngược lại Có vô hạn các vị trí đợi hữu hạn trong hệ thống Tất cả các giả thiết tạo thành lớp đơn giản nhất của hệ thống hàng đợi. 2.2. Nhắc lại các khái niệm thống kê cơ bản 2.2.1. Tiến trình điểm Các tiến trình đến là một tiến trình điểm ngẫu nhiên, với tiến trình này chúng ta có khả năng phân biệt hai sự kiện với nhau. Các thông tin về sự đến riêng lẻ (như thời gian phục vụ, số khách hàng đến) không cần biết, do vậy thông tin chỉ có thể dùng để quyết định xem một sự đến có thuộc quá trình hay không. Mô tả tiến trình Chúng ta xem xét qui luật của tiến trình điểm thông thường, nghĩa là loại trừ các tình huống đến kép. Xét số lần cuộc gọi đến với cuộc gọi thứ i tại thời điểm Ti : 0 = T0 < T1 < T2 < < < Ti < Ti+1< (2-19) Lần quan sát thứ nhất tại T0 = 0. 11
19. Số các cuộc gọi trong nửa khoảng thời gian mở [0, t] là Nt, ở đây Nt là một biến ngẫu nhiên với các tham số thời gian liên tục và thời gian rời rạc, khi t tăng thì Nt không bao giờ giảm. Khoảng thời gian giữa hai lần đến là: Xi = Ti - Ti-1 (2-20) Khoảng thời gian này gọi là khoảng thời gian giữa hai lần đến. Sự phân bố của tiến trình này gọi là sự phân bố khoảng đến. Tương ứng với hai biến ngẫu nhiên Nt và Xi, hai tiến trình này có thể được mô tả theo hai cách: Cách biểu diễn số Nt : khoảng thời gian t giữ không đổi, và ta xét biến ngẫu nhiên Nt cho số cuộc gọi trong khoảng thời gian t. Cách biểu diễn khoảng ti : số các cuộc gọi đến là hằng số (n), và ta xét biến ngẫu nhiên ti là khoảng thời gian diễn ra n cuộc gọi. Mối quan hệ căn bản giữa hai cách biểu diễn thể hiện đơn giản như sau: n Nt 0 và với mỗi k 0 . Xác suất mà k cuộc gọi đến trong khoảng thời gian [t1, t1+t2] là độc lập với t1, nghĩa là với mọi t, k ta có: p ()() Nt1 t 2 N t 1 k p N t 1 t 2 t N t 1 t k (2-22) 12
20. Đây là một trong nhiều định nghĩa về tính dừng của tiến trình điểm các cuộc gọi đến. Tính độc lập (Independence) Tính chất này thể hiện là: tương lai của tiến trình chỉ phụ thuộc vào trạng thái hiện tại. Định nghĩa: xác suất có k sự kiện (với k nguyên và lớn hơn hoặc bằng 0) trong khoảng [t1, t1+t2] là độc lập với các sự kiện trước thời điểm t1 : pNN (t2 t 1 ) kNNnpNN | t 1 t 0  ( t 2 t 1 ) k (2-23) Nếu điều này đúng với mọi t thì tiến trình này là tiến trình Markov: trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, nhưng độc lập với việc nó đã có được như thế nào. Đây chính là tính chất không nhớ. Nếu tính chất này chỉ xảy ra tại các thời điểm nào đó (ví dụ thời điểm đến), thì những điểm này được gọi là các điểm cân bằng hay các điểm tái tạo. Khi đó tiến trình có nhớ giới hạn, và ta cần lưu lại điểm tái tạo gần nhất. Tính đều đặn (Regularity) Như đã nói ta loại trừ các tiến trình của nhiều cuộc gọi vào một thời điểm, vậy ta có định nghĩa sau: Định nghĩa: một tiến trình điểm được gọi là đều đặn nếu xác suất xảy ra với nhiều hơn một sự kiện ở cùng một thời điểm bằng không: p ( Nt t N t ) 2 o ( t ), khi : t 0, o ( t ) 0 (2-24) 2.2.2. Tiến trình Poisson Tiến trình Poisson là tiến trình điểm quan trọng nhất bởi vì vai trò của nó cũng quan trọng như vai trò của phân bố chuẩn trong phân bố thống kê. Tất cả những tiến trình điểm ứng dụng khác đều là dạng tổng quát hoá hay dạng sửa đổi của tiến trình Poisson. Tiến trình Poisson mô tả rất nhiều tiến trình trong đời sống thực tế, do nó có tính ngẫu nhiên nhất. Đặc tính của tiến trình Poisson : Những đặc tính cơ bản của tiến trình Poisson là: Tính dừng Tính độc lập tại mọi thời điểm Tính đều đặn 13
21. Hai tính chất sau là tính chất cơ bản, từ đó tiến trình Poisson có cường độ phụ thuộc thời gian.Từ các tính chất trên người ta có thể đưa ra các tính chất khác đủ để biểu diễn tiến trình Poisson, đó là: Biểu diễn số: là số các sự kiện đến trong một khoảng thời gian với độ dài cố định được phân bố theo tiến trình Poisson. Biểu diễn khoảng thời gian: là các khoảng thời gian Xi giữa các sự kiện liên tiếp nhau được phân bố theo hàm mũ. Tiến trình đến Poisson sử dụng trong lưu lượng viễn thông của mạng chuyển mạch gói và mạng máy tính. Thêm vào đó tiến trình Poisson đã được sử dụng để mô tả các tiến trình nhiễu và để nghiên cứu hiện tượng các hố điện tử xuất hiện trong chất bán dẫn, và trong các ứng dụng khác Ba vấn đề cơ bản được sử dụng để định nghĩa tiến trình đến Poisson. Xét một khoảng thời gian nhỏ t (với t 0 ), như Hình 2-7. t t t t t Hình 2-7 Khoảng thời gian sử dụng để định nghĩa tiến trình Đó là: Xác suất của một tiến trình đến trong khoảng thời gian t được định nghĩa là  t o( t) , với  t 1 và  là hằng số tỷ lệ lý thuyết. Xác suất không có tiến trình đến nào trong khoảng thời gian t là 1  t o( t) Tiến trình đến không có nhớ: một tiến trình đến trong khoảng thời gian t là độc lập với các tiến trình trước đó và các tiến trình trong tương lai. Nếu lấy một chu kỳ T, tìm xác suất p(k) của k tiến trình đến trong thời gian T được cho bởi:  T k e  T p() k với k = 0, 1, 2, 3 (2-25) k ! Nó được gọi là phân bố Poisson. Đây là một phân bố chuẩn  p( k ) 1 và k 0 giá trị kỳ vọng là : E()() k  kp k  T (2-26) k 0 2 2 2 Phương sai :  k E()() k E k hay: 2 k E() k  T (2-27) 14
22. E() k Tham số   là hằng số tỷ lệ, được xem là tham số tốc độ:  T Phương trình (2-25) mô tả tốc độ đến trung bình của tiến trình Poisson. Bình thường giá trị trung bình E(k) tiến tới không tương đương với  T lớn: k /E ( k ) 1/  . T với nghĩa là  T lớn, phân bố có quan hệ chặt chẽ với giá trị trung bình  T. Do đó nếu một thông số (ngẫu nhiên) số các tiến trình đến n trong khoảng thời gian T lớn (‘lớn’ theo nghĩa  T >>1, hoặc T >> 1/ ), n/T có thể đánh giá  . Cũng chú ý là p(0) e T . Khi  T tăng với phân bố đỉnh E (k) =  T, xác suất không có tiến trình đến nào trong khoảng thời gian T tiến đến không với e mũ T. 2.3. Định luật Little Xem xét một hệ thống hàng đợi, khách hàng đến là một tiến trình ngẫu nhiên. Các khách hàng đến hệ thống ở các thời điểm ngẫu nhiên và chờ được phục vụ thì khách hàng sẽ rời khỏi hệ thống. 2.3.1. Công thức Little Chúng ta có ký hiệu như sau: N(t) = Số cuộc gọi đến hệ thống tại thời điểm t. t = Số cuộc gọi đi đến hệ thống trong khoảng thời gian từ (0,t). t = Số cuộc gọi rời khỏi hệ thống trong khoảng thời gian từ (0,t). Ti = Thời gian của cuộc gọi thứ i trong hệ thống (thời gian phục vụ). Như vậy: Nt - Số lượng cuộc gọi trung bình đến hệ thống trong (0,t) là : 1 t Nt N t dt t 0  - Mật độ cuộc gọi trong khoảng (0,t) là :  t t t t Tt - Thời gian trung bình của cuội gọi trong hệ thống là : 1 t TTt i 1 i t Giả sử các giới hạn sau đây tồn tại : NNTT lim ; lim  ; lim t t t t t t Có công thức sau: N T (2-28) 15
23. Công thức trên có tên gọi là Định lý Little Số cuộc gọi trung bình trong hệ thống bằng tích mật độ cuộc gọi với thời gian chiếm kênh trung bình. 2.3.2. Chứng minh công thức Little Chứng minh công thức Little bằng phương pháp hình học theo như minh họa dưới đây. Hình 2-8 Xét trong khoảng (0,t) : t Diện tích phần gạch chéo: S N dt ()() t  t t t   0 t Mặt khác diện tích này cũng bằng : S= 1.Ti i 1 t T t t  i 1 t Như vậy N t)( dt = Ti N dt t i 1  o t 0 i 1 t t t tức là : NTt  t t (*) Nếu giới hạn sau đây tồn tại : NNTT lim ; lim  ; lim ( ) t t t t t t 16
24. Từ (*) và ( ) N T Công thức được chứng minh 2.4. Các mô hình hàng đợi 2.4.1. Ký hiệu Kendall Bất kỳ hệ thống xếp hàng nào cũng được mô tả bởi : Tiến trình đến Nếu các khách hàng đến vào các thời điểm t1, t2 tj thì các biến số ngẫu nhiên Pj=tj-tj-1 được gọi là các thời điểm giữa các lần đến. Các thời điểm này thường được giả thiết là các biến số ngẫu nhiên độc lập và được phân bố đồng nhất IID (Independent and Identycally distributed). Các tiến trình đến thông dụng nhất là : M: Tiến trình mũ (là tiến trình Markov hay tiến trình không nhớ) Er: Tiến trình Erlang bậc r Hr: Tiến trình siêu số mũ bậc r D: Tiến trình tất định (deterministic) G: Tiến trình chung Tiến trình phục vụ Thời gian mà mỗi công việc tiêu tốn cần thiết tại server gọi là thời gian phục vụ. Các thời gian phục vụ thường giả thiết là các biến số ngẫu nhiên IID. Các tiến trình phục vụ thông dụng nhất cũng giống như thời gian đến. Số lượng các bộ server: Số lượng các server phục vụ cho hàng đợi Dung lượng hệ thống Kích thước bộ nhớ đệm cực đại Qui mô mật độ Số lượng các công việc đến tại hàng đợi. Qui mô mật độ luôn là hữu hạn trong các hệ thống thực. Tuy nhiên phân tích hệ thống với qui mô mật độ lớn sẽ dễ dàng hơn nếu giả thiết rằng qui mô mật độ là vô hạn. Qui tắc phục vụ Thứ tự mà theo đó các công việc trong hàng xếp được phục vụ. Các qui tắc phổ biến nhất là đến trước phục vụ trước FCFS (First Come First Served), đến sau phục vụ trước LCFS (Last Come First Served), theo vòng tròn RR (Round Robin), thời gian xử lý ngắn nhất phục vụ trước SPT (Shortest Procesing Time First) và thời gian xử lý ngắn nhất được đề cử SRPT (Shortest Remaining Processing Time First) 17
25. Ký hiệu Kendall A/S/m/B/K/SD được sử dụng rộng rãi để mô tả hệ thống xếp hàng A: Phân bố thời gian giữa các lần đến S: Phân bố thời gian phục vụ m: Số lượng server B:Kích thước bộ đệm K: Quy mô mật độ SD: Quy tắc phục vụ Ví dụ hàng đợi M/D/1: M có nghĩa tiến trình đến là tiến trình Markov không nhớ (với thời gian giữa các lần đến theo hàm mũ); D thời gian phục vụ luôn như nhau (tất định); 1 có một server duy nhất phục vụ. Phần B/K/SD của ký hiệu bị loại trừ để cho thấy rằng dung lượng của hệ thống và qui mô mật độ là vô hạn và qui tắc phục vụ là FCFS. 2.4.2. Quá trình Sinh-Tử (Birth-Death) Trạng thái của hệ thống được biểu diễn bằng số các khách hàng n trong một hệ thống. Khi có một khách hàng mới đến thì trạng thái của hệ thống sẽ thay đổi sang n+1, khi có một khách hàng ra đi thì trạng thái hệ thống sẽ thay đổi sang n-1, ta có lược đồ chuyển tiếp trạng thái là quá trình sinh tử. λ0 λ1 λ2 λi-2 λi-1 λi 0 1 2 i-1 i i+1 µ µ2 µ3 µi-1 µi µi+1 1 Hình 2-9. Chuỗi Markov của một quá trình sinh-tử n : Tốc độ của lần đến n n : Tốc độ của lần đi Pn: Xác suất ổn định trạng thái n của quá trình sinh – tử tại trạng thái n 0  1 n 1 Pn = .P0 (2-29) 1  2  n P0 - xác suất ở trạng thái 0, Pn - xác suất ở trạng thái n 18
26. 2.4.3. Hàng đợi M/M/1 Lược đồ trạng thái λ λ λ λ λ λ 0 1 2 i-1 i i+1 µ µ µ µ µ µ Hình 2-10 Chuỗi Markov của hàng đợi M/M/1 Tất cả các tốc độ đến đều là  ,   : Tốc độ của lần đến  : Tốc độ của lần đi  n n Pn=( ) P0 = P0 (2-30)  Pn: Xác suất ổn định trạng thái n P0: Xác suất ổn định trạng thái 0  : Mật độ lưu lượng =  Trong trường hợp này số kênh phục vụ bằng 1, chỉ có 1 server Các công thức tính toán: Xác suất có n khách hàng trong hệ thống n Pn= (1- ) ; n=1,2, (2-31) P0= (1- ) (2-32) Số lượng trung bình các khách hàng trong hệ thống L=E(n)= (2-33) 1 Phương sai:  2 = (2-34) n (1 ) 2 Tham số thời gian Thời gian trung bình của 1 khách hàng trong hệ thống: W 1 W = L = = (2-35)  (1 )   19
27. Thời gian phục vụ trung bình cho một khách hàng : W S W = 1 = (2-36) S   Thời gian trung bình của khách hàng trong hàng đợi 2 W = W- W = - = (2-37) q S (1 )  (1 ) Chiều dài hàng đợi Số lượng trung bình các khách hàng trong hệ thống L= (2-38) 1 Số lượng trung bình các job trong server: L S L S = 1P(n>=1) =1- P(n=0) =1-(1- ) = (2-39) Số lượng trung bình của các công việc trong hàng đợi L q 2 L = L- L = = (2-40) q S 1 1 Ví dụ: Cho Switch nhận các bản tin đến tốc độ 240bản tin/phút. Độ dài bản tin có phân bố hàm mũ với chiều dài trung bình là 100 ký tự. Tốc độ truyền bản tin đi khỏi hệ thống là 500 ký tự/giây. Tính các tham số sau : Thời gian trung bình của bản một tin trong hệ thống Số bản tin trung bình trong hệ thống Tính chiều dài hàng đợi và thời gian đợi trung bình Bài giải: Xét hệ thống M/M/1: 240 Tốc độ đến  4 bản tin/giây 60 500 Tốc độ phục vụ  5 100  4 Mật độ lưu lượng 8.0  5 Số bản tin trong hệ thống 8.0 L=E(n)= 4 bản tin 1 1 0.8 20
28. Thờigian trung bình của bản tin trong hệ thống L 4 W= 1 (s)  4 Chiều dài hàng đợi L q 2 8,0.8,0 L = 2,3 bản tin q 1 1 0,8 Thời gian đợi trung bình W q 2 L 2,3 W = q 8,0 (s) q (1 )  4 2.4.4. Hàng đợi M/M/1/K λ λ λ λ λ 0 1 2 k-1 k µ µ µ µ µ Hình 2-11 Với số khách hàng là k  n Pn = ( ) .P0 ; 0<=n<=k (2-41)  2k 1 Pn = (1 )(1 ) (2-42) (k 1) k 1 L = (2-43) 1 1 k 1 Xác suất khách hàng đến hệ thống bị từ chối là P K Tốc độ thực tế đến hệ thống '  = (1-P K ) (2-44) Mật độ lưu lượng ' ' (1 P ) (2-45)  K 21
29. 2.4.5. Hàng đợi M/M/C λ λ λ λ λ λ 0 1 2 c-1 c 2µ 3µ (c-1)µ cµ cµ µ Hình 2-12 1  Pn= ()n Po ; 0 c (2-47) CC! n c  c 1 1 ()c c Po= [()c n ] 1 (2-48) n 0 n! c!(1 ) Xác suất xuất hiện hàng đợi Po() c c Pq = (công thức Erlang) (2-49) c!(1 ) Độ dài hàng đợi: Lq = Pq. (2-50) 1 Thời gian đợi: Lq Wq = (2-51)  2.5. Lý thuyết lưu lượng 2.5.1. Khái niệm về lưu lượng và đơn vị Erlang Định nghĩa Trong lý thuyết lưu lượng viễn thông chúng ta thường sử dụng thuật ngữ lưu lượng để biểu thị cường độ lưu lượng, tức là lưu lượng trong một đơn vị thời gian. Thuật ngữ về lưu lượng có nguồn gốc từ tiếng ý và có nghĩa là “độ bận rộn”. Theo (ITU-T,1993) định nghĩa như sau: 22
30. Cường độ lưu lượng: Mật độ lưu lượng tức thời trong một nhóm tài nguyên dùng chung là số tài nguyên bận tại thời điểm đó. Nhóm tài nguyên dùng chung có thể là một nhóm phục vụ như đường trung kế. Tiến hành thống kê mật độ lưu lượng hiện tại có thể tính toán cho một chu kỳ T, ta có cường độ lưu lượng trung bình là: 1 T YT() n() t dt (2-52) T 0 Với n(t) là số thiết bị sử dụng tại thời điểm t Lưu lượng mang Ac = Y = A’ được gọi là lưu lượng được thực hiện bởi một nhóm phục vụ trong khoảng thời gian T (hình 3.1). Trong thực tế, thuật ngữ cường độ lưu lượng thường có nghĩa là cường độ lưu lượng trung bình. Hình 2-13 Lưu lượng mang (mật độ)( bằng số thiết bị bận) là một hàm thời gian (đường cong C). Lưu lượng trung bình trong khoảng thời gian T (đường cong D) Đơn vị của cường độ lưu lượng là Erlang (kí hiệu là Erl), đây là đơn vị không có thứ nguyên. (Ra đời 1946 để ghi nhớ công ơn của nhà toán học người Đan mạch A.K Erlang (1878-1929), người đã tìm ra lý thuyết lưu lượng điện thoại). 23
31. Khối lượng lưu lượng: là tổng lưu lượng mang trong chu kỳ T và được đo bằng đơn vị Erlang - giờ (Eh) (theo như tiêu chuẩn ISO những đơn vị tiêu chuẩn có thể là Erlang giây, nhưng thông thường đơn vị Erlang giờ thường sử dụng nhiều hơn). Lưu lượng mang không thể vượt quá số lượng của đường dây. Một đường dây chỉ có thể mang nhiều nhất một Erlang. Doanh thu của các nhà khai thác tỷ lệ với lưu lượng mang của mạng viễn thông. Đối với điện thoại cố định thường thì có Ac =0,010,04 Erl Đối với cơ quan : 0,04 0,06 Erl Tổng đài cơ quan: 0,6 Erl Điện thoại trả tiền : 0,7 Erl Lưu lượng phát sinh A Lưu lượng phát sinh là lưu lượng được mang nếu không có cuộc gọi nào bị từ chối do thiếu tài nguyên, ví dụ như với số kênh không bị giới hạn. Lưu lượng phát sinh là một giá trị lý thuyết không đo lường được chỉ có thể ước lượng thông qua lưu lượng mang. Ta gọi mật độ cuộc gọi là , là số cuộc gọi trung bình đến trong một đơn vị thời gian và gọi s là thời gian phục vụ trung bình. Khi đó lưu lượng phát sinh là: A .s (2-53) Từ phương trình này ta thấy rằng đơn vị lưu lượng không có thứ nguyên. Định nghĩa này phù hợp với định nghĩa trên với điều kiện kênh phục vụ không bị giới hạn. Nếu sử dụng cho một hệ thống với năng lực giới hạn ta có sự xác định phụ thuộc vào hệ thống. Ngoài ra có thể được tính: A =/ ( : tốc độ phục vụ) Lưu lượng tổn thất Ar Lưu lượng tổn thất là độ chênh lệch giữa lưu lượng phát sinh và lưu lượng mang. Giá trị này của hệ thống giảm khi năng lực của hệ thống tăng. Ar = A – Ac (2-54) Lưu lượng phát sinh là một tham số sử dụng trong tính toán lý thuyết định cỡ. Tuy nhiên, chỉ có lưu lượng mang thường phụ thuộc vào hệ thống thực mới là tham số đo lường được trong thực tế. 24
32. Trong hệ thống truyền dẫn số ta không nói về thời gian phục vụ mà chỉ nói về các tốc độ truyền dẫn. Một cuộc giao dịch có thể là quá trình truyền s đơn vị (như bits hay bytes). Năng lực hệ thống là , nghĩa là tốc độ báo hiệu số liệu, được tính bằng đơn vị trên giây (ví dụ bít/s). Như vậy thời gian phục vụ cho một giao dịch như thế tức là thời gian truyền sẽ là s/ đơn vị thời gian (ví dụ như giây-s); nghĩa là phụ thuộc vào . Nếu trung bình có  cuộc giao dịch đến trong một đơn vị thời gian, thì độ sử dụng hệ thống sẽ là: .s  (2-55) Với: 1  0 . 2.5.2. Hệ thống tổn thất (Loss System) và công thức Erlang B Công thức Erlang B Công thức Erlang được mô tả bằng ba thành phần: cấu trúc, chiến lược và lưu lượng: Cấu trúc: Ta xem xét một hệ thống có n kênh đồng nhất hoạt động song song và được gọi là nhóm đồng nhất (các server, kênh trung kế, khe slot). Chiến lược: Một cuộc gọi tới hệ thống được chấp nhận nếu còn ít nhất một kênh rỗi (mọi cuộc gọi chỉ cần một kênh rỗi). Nếu tất cả các kênh đều bận thì cuộc gọi sẽ bị huỷ bỏ và nó sẽ bị loại bỏ mà không gây một ảnh hưởng nào sau đó (cuộc gọi bị loại bỏ có thể được chấp nhận trên một tuyến khác). Chiến lược này được gọi là mô hình Loss (tổn thất) Erlang hay mô hình LCC (Lost Calls Cleared). Lưu lượng: Giả sử rằng trong khoảng thời gian dịch vụ được phân bố theo hàm mũ (số mũ  ), và tiến trình sử dụng là tiến trình Poisson với tốc độ  . Loại lưu lượng này được gọi là PCT -I (Pure Chance Traffic Type I). Tiến trình lưu lượng này sẽ trở thành tiến trình Mackov đơn giản xử lý bằng toán học. Công thức Erlang B biểu thị mối quan hệ giữa lưu lượng xuất hiện, lượng thiết bị, và xác suất tổn hao như một hàm số được sử dụng rộng rãi như là lý thuyết tiêu chuẩn cho việc lập kế hoạch trong hệ thống viễn thông, vì vậy công thức Erlang B chứa đựng những tiêu chuẩn sau: Các cuộc gọi xuất hiện một cách ngẫu nhiên: 25
33. Xác suất xảy ra sự cố cuộc gọi là luôn cố định bất chấp thời gian (xác suất cố định xảy ra sự cố của cuộc gọi). Xác suất xảy ra sự cố của cuộc gọi không bị ảnh hưởng bởi các cuộc gọi trước (không còn sót lại những đặc điểm của cuộc gọi trước). Trong thời gian rất ngắn, không có cuộc gọi nào xuất hiện hoặc chỉ có một cuộc gọi xuất hiện (các cuộc gọi rải rác). Dạng tổn hao trong khi vận hành khi tất cả các mạch đều bận: Trong dạng tổn hao vận hành này, cuộc gọi không thể liên lạc được khi tất cả các mạch đều bận. Trong trường hợp đó tín hiệu được gửi ra ngoài và dù đường ra trở nên thông suốt sau khi tín hiệu bận được gửi ra thì cuộc gọi vẫn không được kết nối. Nhóm mạch ra là nhóm trung kế có khả năng sử dụng hết. Thời gian chiếm dụng của các cuộc gọi gần đúng với phân bố hàm mũ. Các mạch vào thì vô hạn, còn các mạch ra thì hữu hạn. Xác suất tổn hao cuộc gọi trong công thức Erlang B được trình bày trong công thức sau: An An n! n! En(A)= E ,1 n (A) = P(n) = = (2-56) AA2 n n Ai 1 A  !2 n! i 0 i! Với A -Lưu lượng phát sinh (A=.s) n - Số kênh Việc tính toán công thức trên không phù hợp cả khi cả An và n! tăng quá nhanh, khi đó máy tính sẽ bị tràn số do vậy người ta thường áp dụng một số kết quả tính toán và đưa ra công thức sau: AEA.()x 1 EAx () với E0 (A) = 1 (2-57) x A.() Ex 1 A Từ quan điểm toán ứng dụng, hàm tuyến tính có độ ổn định cao nhất ta có: x IA( ) 1 IA ( ) với I0 (A) = 1 (2-58) xA x 1 Ở đây In (A) = 1/ En (A) (2-59) Công thức này hoàn toàn chính xác, thậm chí với các giá trị (n.A) lớn vẫn không xuất hiện lỗi. Đây là công thức cơ bản cho rất nhiều bảng số của công thức Erlang B 26
34. Ví dụ : Cho tốc độ gọi đến  bằng một cuộc gọi trên 1 phút, thời gian trung bình của 1 cuộc gọi là 3 phút, số kênh phục vụ bằng 4. Tính xác suất tổn thất P theo 2 công thức trên. Cách 1: Lưu lượng phát sinh A= .t 1.3 3 Erl 34 P(n)= !4 0,206 323 33 4 1 3 2 !3 !4 Ý nghĩa : có 1/5 các cuộc gọi tới số thuê bao bị tổn thất (bị bận) Cách 2: AEA.()3 E 4 ()A 4 AEA .3 ( ) E 0 (A ) 1 AEA.()0 3 3 E 1 ()A 1 AEA .0 ( ) 1 3 4 3 .3 AEA.() 9 E ()A 1 4 2 2 AEA . ( ) 3 17 1 2 3. 4 9 .3 AEA.() 27 E ()A 2 17 3 3 AEA . ( ) 9 78 2 3 3. 17 9 .3 AEA.() 81 E ()A 3 17 0.2061 4 4 AEA . ( ) 9 393 3 4 3. 17 Các đặc tính lưu lượng của công thức Erlang B Biết được xác suất trạng thái ta có thể biết được các số đo hiệu năng. Độ nghẽn theo thời gian: là xác suất mà tất cả các trung kế bị chiếm tại một thời điểm bất kỳ bằng với phần thời gian tất cả các trung kế bị chiếm trên tổng thời gian (3.13) Độ nghẽn theo cuộc gọi: xác suất mà một cuộc gọi bất kỳ bị mất bằng tỷ lệ số cuộc gọi bị chặn trên tổng các cuộc gọi. AY Độ nghẽn lưu lượng: C EA() A n 27
35. Ta có E = B = C, bởi vì cường độ cuộc gọi độc lập với trạng thái, đây chính là tính chất PASTA (Poisson Arrival See Time Average), nó phù hợp với tất cả các hệ thống tuân theo tiến trình Poisson. Trong tất cả các trường hợp khác, ít nhất có ba tham số đo tắc nghẽn là khác nhau. Ví dụ : Cho thời gian xem xét T là 1h ,lưu lượng phát sinh A là 1 Erl, số kênh là n=3, thời gian phục vụ trung bình cho một cuộc gọi là 3 phút. Tính số lượng cuộc gọi bị nghẽn trong khoảng thời gian T, tính lưu lượng tổn thất, lưu lượng mang? Bài giải : Số cuộc gọi tổn thất : N loss = B.N=P(n).N A 1 N=T. T. .60 20 cuộc gọi S 3 A 1  cuộc gọi/phút S 3 A n 13 !n !3 1 B=P(n)= 2 n Ai 1 13 16  1 1 i 0 !i !2 !3 1 N = .20 1.25 cuộc gọi loss 16 Ý nghĩa : Trong 20 cuộc gọi dến có 1.25 cuộc gọi bị nghẽn không được phục vụ. Lưu lượng tổn thất : 1 1 Ar= A.C = 1. (Erl) 16 16 Lưu lượng mang Ac = Y= A(1-P(n)) = 1.(1- 1 )= 15/16 (Erl) 16 2.5.3. Hệ thống trễ (Delay) và công thức Erlang C Xét lưu lượng với tiến trình poisson (Không gới hạn về tài nguyên). Phân bố thời gian phục vụ là PCT-1. Hệ thống hàng đợi này có tên là hệ thống trễ Erlang.Trong hệ thống này thì lưu lượng mang sẽ bằng lưu lượng phát sinh và không có khách hàng nào bị nghẽn. 28
36. Công thức Erlang C Gọi w là biến ngẫu nhiên của thời gian đợi thì ta có xác xuất để biến w 0 là: An n . n! n A E ,2 n (A) = P(w>0) = (A<n) (2-60) AA2n 1 A n n 1 A . !2 (n 1)!n ! n A Cho biết xác xuất cuộc gọi đến hệ thống thì nó phải bị xếp vào hàng đợi (do số kênh giới hạn). Xác xuất để 1 khách hàng đợi phục vụ ngay : Sn E2,n(A) (2-61) Công thức hồi quy: 1 = 1 - 1 (2-62) EA,2 n () EA,1 n () EA1,n 1() I ,2 n (A) = I ,1 n (A) - I1,n 1 (A) (2-63) 1 I ,2 n (A) = (2-64) En,2 (A) Lưu lượng phát sinh lưu lượng mang: A=Y (Chỉ áp dụng cho mô hình trễ). Ví dụ : Cho hệ thống trễ tốc độ các cuộc gọi đến  =20 cuộc/giờ, thời gian chiếm kênh của cuộc gọi là 6 phút .Tính lưu lượng mang, lưu lượng phát sinh. Xác suất cuộc gọi bất kỳ phải vào hàng đợi, xác suất cuộc gọi đi được phục vụ ngay, cho n=3. (Tính theo hai cách) Bài giải: Lưu lượng mang = lưu lượng phát sinh; A=Y 20 A=.S .6 2 Erl 60 Cách 1: Xác suất cuộc gọi vào hàng đợi 2 3 . !3 3 2 E ,2 n()A = 4/9 323 3 3 1 3 . !2 !3 3 2 Xác suất cuộc gọi được phục vụ: 29
37. 4 5 Sn = 1- E (A ) 1 ,2 n 9 9 Cách 2: 1 1 1 EEAEA2,3 1,3() 1,2 () E 0,1 (A ) 1 2.EA0,1 ( ) 2 1 E 1,1 ()A 1 2.EA0,1 ( ) 1 2 3 2 .2 2.EA ( ) 4 2 E ()A 1,1 3 2,1 2 2.EA ( ) 2 10 5 1,1 2 2. 3 2 .2 AEA.() 4 E ()A 2,1 5 3,1 3 AEA . ( ) 2 19 2,1 3 2. 5 1 1 1 19 5 9 . EAEAEA2,3() 1,3() 1,2 () 4 2 4 4 E ()A 3,2 9 2.6. Hệ thống hàng đợi có ưu tiên Các khách hàng sau khi đến hệ thống có thể phải đứng vào hàng đợi, do đó cần có các qui tắc nhất định để đảm bảo khách hàng được phục vụ một cách nhanh nhất. Tuy nhiên kích thước của hàng đợi không phải là một giá trị vô hạn, chính nguyên nhân này là nguồn gốc của các thông số khác liên quan đến hàng đợi và tổ chức hàng đợi. Hàng đợi là một quan điểm toán học về tình huống trong thế giới thực, nó đưa ra các phân tích có khả năng đánh giá hiệu suất lưu lượng của khách hàng (như các cuộc gọi, các tế bào ATM, hay các mạng LAN) khi đi qua hàng đợi. Có ít nhất 7 tham số thường sử dụng trong hệ thống đó là: Kết cấu các mức ưu tiên (các lớp) của khách hàng đến, nếu có hơn một mức ưu tiên trong hàng đợi (ví dụ trong cửa hàng thì nam giới và phụ nữ là hai lớp) do đó thời gian phục vụ trong các mức ưu tiên là khác nhau. Với mỗi mức ưu tiên khách hàng có phân bố tiến trình đến riêng. Với mỗi mức ưu tiên, kích thước hay số khách hàng tạo ra lưu lượng. 30
38. Phân bố thời gian phục vụ của Server hàng đợi (hành động của Server). Trong nhiều mạng truyền thông thường gọi là phân bố chiều dài. Các qui tắc của hàng đợi. Chiều dài tối đa của hàng đợi (phụ thuộc vào kích thước của Buffer). Phản ứng của khách hàng khi bị trễ, tắc nghẽn, 2.6.1. Qui tắc và tổ chức hàng đợi Một cách để các phần tử mạng xử lý các dòng lưu lượng đến là sử dụng các thuật toán xếp hàng để sắp xếp các loại lưu lượng. Khách hàng đang đợi trong hàng đợi để được phục vụ có thể được lựa chọn theo nhiều cách, đầu tiên chúng ta quan tâm đến 3 loại qui tắc sau: FCFS (First Come First Served ) nó thường được gọi là hàng đợi công bằng hay hàng đợi gọi và qui tắc này thường xuất hiện trong cuộc sống hàng ngày của chúng ta. Nó được xem như là FIFO, chú ý là FIFO chỉ sử dụng trong hàng đợi không sử dụng cho toàn hệ thống. LCFS ( Last Come First sever) đó là chu trình ngăn xếp, như việc xếp hàng trên giá của cửa hàng.v.v qui tắc này cũng xem như LIFO ( Last In First Out) SIRO (Sevice In Random Order) tất cả các khách hàng đang đợi trong hàng đợi có xác suất để được chọn phục vụ như nhau. Nó còn được gọi là RANDOM hay RS (Random Selection). Hai qui tắc đầu tiên chỉ sử dụng trong lần đến mà được xét, trong khi qui tắc thứ 3 không được xem như tiêu chuẩn và không yêu cầu nhớ. (Ngược với hai qui tắc đầu). Như ba trường hợp đề cập ở trên tổng thời gian đợi cho tất cả các khách hàng là như nhau. Qui tắc của hàng đợi chỉ quyết định làm sao để xác định tổng thời gian đợi của khách hàng. Trong chương trình điều khiển hệ thống hàng đợi có thể có nhiều qui tắc phức tạp. Trong lý thuyết hàng đợi chúng ta giả thiết là tổng lưu lượng phát sinh là độc lập với qui tắc của hàng đợi. Với hệ thống máy tính chúng ta thường cố gắng giảm tổng thời gian đợi, nó có thể thực hiện khi sử dụng thời gian phục vụ như là tiêu chuẩn: SJF (Shortest Job First): Việc đầu tiên ngắn nhất. SJN (Shortest Job Next): Việc tiếp theo ngắn nhất. SPF (Shortest Processing Time First): Thời gian xử lý đầu tiên ngắn nhất. Qui tắc này được giả thiết như là chúng ta biết thời gian phục vụ trong sự phát triển, qui tắc hàng đợi này tiểu hình hoá tổng thời gian đợi cho tất cả các khách hàng. 31
39. Như nói ở trên qui tắc ảnh hưởng tới thời gian đến hoặc thời gian phục vụ. Một sự thoả hiệp giữa các qui định có được bởi: RR (Round Robin): một khách hàng được phục vụ cho trong một khoảng thời gian cố định (Time slice). Nếu dịch vụ không hoàn thành trong khoảng thời gian này, thì khách hàng trở lại hàng đợi là FCFS. PS (Processor Sharing): tất cả khách hàng chia sẻ dung lượng dịch vụ bằng nhau. FB (Foreground-Background): qui tắc này cố gắng thực hiện SJF mà không biết đến thời gian phục vụ sau này. Server sẽ cung cấp dịch vụ để khách hàng có thời gian phục vụ ít nhất. Khi tất cả các khách hàng có được thời gian phục vụ giống nhau, FB được xác định như là PS. Qui tắc cuối cùng là qui tắc động do qui tắc hàng đợi phụ thuộc vào lượng thời gian sử dụng trong hàng đợi. Từ các qui tắc trên những thuật toán xếp hàng hay dùng là: Xếp hàng vào trước ra trước (FIFO Queuing). Xếp hàng theo mức ưu tiên (PQ - Priority Queuing). Xếp hàng tuỳ biến (CQ - Custom Queuing). Xếp hàng theo công bằng trọng số (WFQ - Weighted Fair Queuing). Xếp hàng vào trước ra trước (FIFO Queuing) Trong dạng đơn giản nhất, thuật toán vào trước ra trước liên quan đến việc lưu trữ gói thông tin khi mạng bị tắc nghẽn và rồi chuyển tiếp các gói đi theo thứ tự mà chúng đến khi mạng không còn bị tắc nữa. FIFO trong một vài trường hợp là thuật toán mặc định vì tính đơn giản và không cần phải có sự thiết đặt cấu hình nhưng nó có một vài thiếu sót. Thiếu sót quan trọng nhất là FIFO không đưa ra sự quyết định nào về tính ưu tiên của các gói cũng như là không có sự bảo vệ mạng nào chống lại những ứng dụng (nguồn phát gói) có lỗi. Một nguồn phát gói lỗi phát quá ra một lưu lượng lớn đột ngột có thể là tăng độ trễ của các lưu lượng của các ứng dụng thời gian thực vốn nhạy cảm về thời gian. FIFO là thuật toán cần thiết cho việc điều khiển lưu lượng mạng trong giai đoạn ban đầu nhưng với những mạng thông minh hiện nay đòi hỏi phải có những thuật toán phức tạp hơn, đáp ứng được những yêu cầu khắt khe hơn. Xếp hàng theo mức ưu tiên (PQ - Priority Queuing) Thuật toán PQ đảm bảo rằng những lưu lượng quan trọng sẽ có được sự xử lý nhanh hơn. Thuật toán được thiết kế để đưa ra tính ưu tiên nghiêm ngặt đối với những dòng lưu lượng quan trọng. PQ có thể thực hiện ưu tiên căn cứ vào giao thức, giao diện truyền tới, kích thước gói, địa chỉ nguồn hoặc điạ chỉ 32
40. đích Trong thuật toán, các gói được đặt vào 1 trong các hàng đợi có mức ưu tiên khác nhau dựa trên các mức độ ưu tiên được gán (Ví dụ như bốn mức ưu tiên là High, Medium, Normal, và Low) và các gói trong hàng đợi có mức ưu tiên cao sẽ được xử lý để truyền đi trước. PQ được cấu hình dựa vào các số liệu thống kê về tình hình hoạt động của mạng và không tự động thích nghi khi điều kiện của mạng thay đổi. (Hình 2.14) Hình 2-14 Thuật toán xếp hàng theo mức ưu tiên Xếp hàng tuỳ biến (Custom Queuing) CQ được tạo ra để cho phép các ứng dụng khác nhau cùng chia sẻ mạng với các yêu cầu tối thiểu về băng thông và độ trễ. Trong những môi trường này, băng thông phải được chia một cách tỉ lệ cho những ứng dụng và người sử dụng. CQ xử lý lưu lượng bằng cách gán cho mỗi loại gói thông tin trong mạng một số lượng cụ thể không gian hàng đợi và phục vụ các hàng đợi đó theo thuật toán round -robin (round-robin fashion). Cũng giống như PQ, CQ không tự thích ứng được khi điều kiện của mạng thay đổi. (hình 2.15) Hình 2-15 Xếp hàng cân bằng trọng số Xếp hàng công bằng trọng số (WFQ - Weighted Fair Queuing) Trong trường hợp muốn có một mạng cung cấp được thời gian đáp ứng không đổi trong những điều kiện lưu lượng trên mạng thay đổi thì giải pháp là thuật toán WFQ. Thuật toán WFQ tương tự như CQ nhưng các giá trị sử dụng băng thông gán cho các loại gói không được gán một các cố định bởi 33
41. người sử dụng mà được hệ thống tự động điều chỉnh thông qua hệ thống báo hiệu Qos. WFQ được thiết kế để giảm thiểu việc thiết đặt cấu hình hàng đợi và tự động thích ứng với sự thay đổi điều kiện lưu lượng của mạng. Thuật toán này phù hợp với hầu hết các ứng dụng chạy trên những đường truyền không quá 2Mbps. 2.6.2. Độ ưu tiên của khách hàng trong hàng đợi ưu tiên Khách hàng được chia thành p lớp ưu tiên. Khách hàng ở lớp ưu tiên k có độ ưu tiên cao hơn so với khách hàng ở lớp ưu tiên k+1. Hàng đợi ưu tiên lại đựoc chia thành các nhóm sau: Không ưu tiên phục vụ trước (Non-preemptive hay là HOL - Head of the Line): Khách hàng đến với mức độ ưu tiên cao hơn so với khách hàng đang được phục vụ thì vẫn phải chờ cho đến khi server phục vụ xong khác hàng này (và phục vụ xong tất cả các khách hàng khác có mức độ ưu tiên cao hơn nó). Ưu tiên phục vụ trước (preemptive): Việc phục vụ khách hàng có quyền ưu tiên thấp sẽ bị ngừng lại khi có một khách hàng mà quyền ưu tiên của nó cao hơn đến hệ thống. Ưu tiên phục vụ trước lại có thể chia thành các nhóm nhỏ sau: Phục hồi ưu tiên (preemptive resume), khi mà sự phục vụ được tiếp tục từ thời điểm mà nó bị ngắt quãng trước đó. Ưu tiên không lấy mẫu lại (preemptive without resampling), khi mà sự phục vụ bắt đầu lại từ đầu với khoảng thời gian phục vụ không đổi. Ưu tiên lấy mẫu lại (preemptive with resampling), khi mà sự phục vụ bắt đầu lại với khoảng thời gian phục vụ mới. 2.6.3. Duy trì qui tắc hàng đợi, luật Kleinrock Giả thiết thời gian phục vụ của khách hàng là độc lập với qui tắc của hàng đợi. Do dung lượng của Server là hạn chế và độc lập (chiều dài hàng đợi) và sau một thời gian Server đạt đến ngưỡng và tốc độ phục vụ bị giảm. Chúng ta giới thiệu hai hàm thường áp dụng rộng rãi trong lý thuyết hàng đợi: Hàm tải U (t) Là hàm phụ thuộc thời gian, nó phục vụ khách hàng đã đến tại thời điểm t, hàm U(t) độc lập với qui tắc của hàng đợi. Giá trị trung bình của hàm tải là U(t) = E{U(t)}. 34
42. Thời gian đợi ảo W (t) Là thời gian đợi của khách hàng khi anh ta đến tại thời điểm t, thời gian đợi ảo phụ thuộc vào qui tắc hàng đợi, giá trị trung bình là W=E{W(t)}. Nếu qui tắc hàng đợi là FCFS thì U(t)=W(t), trong tiến trình Poisson thì thời gian đợi ảo sẽ bằng thời gian đợi thực tế. Định lý: Luật Kleinrock: AV. AW. =const  i i 1 A (V là thời gian phục vụ trung bình ở thời điểm bất kỳ) Thời gian đợi trung bình cho tất cả các loại khách hàng (lớp) bị tác động bởi lưu lượng tải của lớp đang xét là độc lập với qui tắc của hàng đợi. 2.6.4. Một số hàng đợi đơn server Hình 2-16 Một số loại hàng đợi đơn server thường gặp 2.6.5. Kết luận Lý thuyết hàng đợi đã được nghiên cứu ngay từ trong mạng chuyển mạch kênh, tuy nhiên việc áp dụng trong mạng chuyển mạch kênh còn hạn chế, 35
43. sau đó đã được nghiên cứu sâu rộng trong mạng chuyển mạch gói với việc đóng gói dữ liệu. Các tín hiệu thoại truyền thống được số hoá, đóng gói và chuyển tải trong mạng gói như là một phần cơ sở của mạng dữ liệu. Tiến trình điểm là tiến trình quan trọng nó cho phép phân biệt các khách hàng đến (các sự kiện) và nó là một tiến trình ngẫu nhiên với các tính chất như: tính độc lập, tính đều đặn tại mọi thời điểm và tính dừng. Tiến trình Poisson là một tiến trình điểm và là tiến trình quan trọng nhất. Các tiến trình khác chỉ là rút gọn hay phát triển của tiến trình Poisson. Tiến trình Poisson là tiến trình mô tả nhiều tiến trình trong đời sống thực tế nên nó là tiến trình ngẫu nhiên nhất do vậy nó đóng vai trò như là một tiến trình chuẩn trong phân bố thống kê. Các khách hàng đến (gói hay cuộc gọi) một Server nó có thể được phục vụ ngay hoặc phải mất một khoảng thời gian chờ nào đó cho đến khi Server rỗi và thực hiện tiếp nhận xử lý. Các qui tắc phục vụ các khách hàng đợi được phục vụ được thiết lập cho các Server qua đó các khách hàng lần lượt được phục vụ theo mức ưu tiên của mình do vậy các khách hàng có độ ưu tiên khác nhau thì có thời gian chờ khác nhau. Các thông số này được quyết định bởi thuật toán xếp hàng của hàng đợi và cũng từ đó ảnh hưởng tới QoS của các loại dịch vụ cung cấp trên mạng. Các thông số của hàng đợi được xác định thông qua lý thuyết xác suất thống kê, định lý Little, qui tắc duy trì hàng đợi Kleinrock và quan trọng hơn cả là các tiến trình đi - đến của khách hàng là các tiến trình Poisson với phân bố hàm mũ cùng với thuật toán xếp hàng của nó. Xác định các thông số hàng đợi như: chiều dài hàng đợi ở các thời điểm bất kỳ hoặc ngay cả khi có khách hàng, qua đó đưa ra các phương án điều khiển lưu lượng trên mạng cho phù hợp nhằm giảm thiểu các sự cố trên mạng đánh giá được hiệu suất sử dụng tài nguyên đồng thời xác định được cấp QoS mà có thể cung cấp trên mạng, đó là cơ sở cho việc thiết kế các mạng hệ thống viễn thông sau này. 2.7. Bài tập (Pending) 36
44. Chương 3 MẠNG HÀNG ĐỢI 3.1. Mạng nối tiếp 37
45. Chương 4 ĐỊNH TUYẾN IN MẠNG MÁY TÍNH 4.1. Yêu cầu về định tuyến trong mạng thông tin 4.1.1. Vai trò của định tuyến trong mạng thông tin 4.1.2. Các khái niệm trong lý thuyết graph Phần này giới thiệu các thuật ngữ và các khái niệm cơ bản nhằm mô tả các mạng, graph, và các thuộc tính của nó. Lý thuyết graph là một môn học xuất hiện từ lâu, nhưng lý thuyết này có một số thuật ngữ được chấp nhận khác nhau dùng cho các khái niệm cơ bản. Vì thế có thể sử dụng một số thuật ngữ khác nhau để lập mô hình graph cho mạng. Các thuật ngữ được trình bày dưới đây này là các thuật ngữ đã được công nhận và được sử dụng thường xuyên chương này. Một graph G, được định nghiã bởi tập hợp các đỉnh V và tập hợp các cạnh E. Các đỉnh thường được gọi là các nút và chúng biểu diễn vị trí (ví dụ một điểm chứa lưu lượng hoặc một khu vực chứa thiết bị truyền thông). Các cạnh được gọi là các liên kết và chúng biểu diễn phương tiện truyền thông. Graph có thể được biểu diễn như sau: G=(V, E) Hình 4.1 là một ví dụ của một graph. Hình 4.1. Một graph đơn giản Mặc dù theo lý thuyết, V có thể là tập hợp rỗng hoặc không xác định, nhưng thông thường V là tập hợp xác định khác rỗng, nghĩa là có thể biểu diễn V={vi | i=1,2, N} Trong đó N là số lượng nút. Tương tự E được biểu diễn: E={ei | i=1,2, M} 38
46. Một liên kết, ej, tương ứng một kết nối giữa một cặp nút. Có thể biểu diễn một liên kết ej giữa nút i và k bởi ej=(vi,vk) hoặc bởi ej=(i,k) Một liên kết gọi là đi tới một nút nếu nút đó là một trong hai điểm cuối của liên kết. Nút i và k gọi là kề nhau nếu tồn tại một liên kết (i, k) giữa chúng. Những nút như vậy được xem là các nút láng giềng. Bậc của nút là số lượng liên kết đi tới nút hay là số lượng nút láng giềng. Hai khái niệm trên là tương đương nhau trong các graph thông thường. Tuy nhiên với các graph có nhiều hơn một liên kết giữa cùng một cặp nút, thì hai khái niệm trên là không tương đương. Trong trường hợp đó, bậc của một nút được định nghĩa là số lượng liên kết đi tới nút đó. Một liên kết có thể có hai hướng. Khi đó thứ tự của các nút là không có ý nghiă. Ngược lại thứ tự các nút có ý nghĩa. Trong trường hợp thứ tự các nút có ý nghĩa, một liên kết có thể được xem như là một cung và được định nghĩa aj=[vi,vk] hoặc đơn giản hơn aj=[i,k] k được gọi là cận kề hướng ra đối với i nếu một cung [i,k] tồn tại và bậc hướng ra của i là số lượng các cung như vậy. Khái niệm cận kề hướng vào và bậc cận kề hướng vào cũng được định nghĩa tương tự. Một graph gọi là một mạng nếu các liên kết và các nút có mặt trong liên kết có các thuộc tính (chẳng hạn như độ dài, dung lượng, loại ). Các mạng được sử dụng để mô hình các vấn đề cần quan tâm trong truyền thông, các thuộc tính riêng biệt của nút và liên kết thì liên quan đến các vấn đề cụ thể trong truyền thông. Sự khác nhau giữa các liên kết và các cung là rất quan trọng cả về việc lập mô hình cho mạng lẫn quá trình hoạt động bên trong của các thuật toán, vì vậy sự khác nhau cần phải luôn được phân biệt rõ ràng. Về mặt hình học các liên kết là các đường thẳng kết nối các cặp nút còn các cung là các đường thẳng có mũi tên ở một đầu, biểu diễn chiều của cung. Một graph có các liên kết gọi là graph vô hướng, tuy nhiên một graph có các cung gọi là graph hữu hướng. Một graph hữu hướng có thể có cả các liên kết vô hướng. Thông thường , các graph được giả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa. 39
47. Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết giữa cùng một cặp nút (điều này tương ứng với việc có nhiều kênh thông tin giữa hai chuyển mạch). Những liên kết như vậy được gọi là các liên kết song song. Một graph có liên kết song song gọi là một multigraph. Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những liên kết đó được gọi là các self loop. Chúng ít khi xuất hiện và thường xuất hiện do việc xem hai nút như là một nút trong quá trình lập mô hình graph cho một mạng hoặc phát sinh trong quá trình thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ một graph có các liên kết song song và các self loop. Một graph không có các liên kết song song hoặc các self loop gọi là một graph đơn giản. Việc biểu diễn và vận dụng các graph đơn giản là tương đối dễ dàng, vì vậy giả thiết rằng các graph được xem xét là các graph đơn giản. Nếu có sự khác biệt với giả thiết này, chúng sẽ được chỉ ra. 4.2. Các mô hình định tuyến quảng bá (broadcast routing) 4.2.1. Lan tràn gói (flooding) Một dạng mạnh hơn của định tuyến riêng biệt đó là lan tràn gói. Trong phương thức này, mỗi gói đi đến router sẽ được gửi đi trên tất cả các đường ra trừ đường mà nó đi đến. Phương thức lan tràn gói này hiển nhiên là tạo ra rất nhiều gói sao chép (duplicate). Trên thực tế, số gói này là không xác định trừ khi thực hiện một số biện pháp để hạn chế quá trình này. Một trong những biện pháp đó là sử dụng bộ đếm bước nhảy trong phần tiêu đề của mỗi gói. Giá trị này sẽ bị giảm đi một tại mỗi bước nhảy. Gói sẽ bị loại bỏ khi bộ đếm đạt giá trị không. Về mặt lý tưởng, bộ đếm bước nhảy sẽ có giá trị ban đầu tương ứng với độ dài từ nguồn đến đích. Nếu như người gửi không biết độ dài của đường đi, nó có thể đặt giá trị ban đầu của bộ đếm cho trường hợp xấu nhất. Khi đó giá trị ban đầu đó sẽ được đặt bằng đường kính của mạng con. Một kỹ thuật khác để ngăn sự lan tràn gói là thêm số thứ tự vào tiêu đề các gói. Mỗi router sẽ cần có một danh sach theo nút nguồn để chỉ ra những số thứ tự từ nguồn đó đã được xem xét. Để tránh danh sách phát triển không giới hạn, mỗi danh sách sẽ tăng lên bởi số đếm k để chỉ ra rằng tất cả các số thứ tự đến k đã được xem. Khi một gói đi tới, rất dễ dàng có thể kiểm tra được gói là bản sao hay không. Nếu đúng gói là bản sao thì gói này sẽ bị loại bỏ. Lan tràn gói có ưu điểm là lan tràn gói luôn luôn chọn đường ngắn nhất. Có được ưu điểm này là do về phương diện lý thuyết nó chọn tất cả các đường có thể do đó nó sẽ chọn được đường ngắn nhất. Tuy nhiên nhược điểm của nó là số lượng gói gửi trong mạng quá nhiều. 40
48. Sử dụng lan tràn gói trong hầu hết các ứng dụng là không thực tế. Tuy vậy lan tràn gói có thể sử dụng trong những ứng dụng sau. Trong ứng dụng quân sự, mạng sử dụng phương thức lan tràn gói để giữ cho mạng luôn luôn hoạt động tốt khi đối mặt với quân địch. Trong những ứng dụng cơ sở dữ liệu phân bố, đôi khi cần thiết phải cập nhật tất cả cơ sở dữ liệu. Trong trường hợp đó sử dụng lan tràn gói là cần thiết. Ví dụ sự dụng lan tràn gói để gửi cập nhật bản định tuyến bởi vì cập nhật không dựa trên độ chính xác của bảng định tuyến. Phương pháp lan tràn gói có thể được dùng như là đơn vị để so sánh phương thức định tuyến khác. Lan tràn gói luôn luôn chọn đường ngắn nhất. Điều đó dẫn đến không có giải thuật nào có thể tìm được độ trễ ngắn hơn. Một biến đổi của phương pháp lan tràn gói là lan tràn gói có chọn lọc. Trong giải thuật này, router chỉ gửi gói đi ra trên các đường mà đi theo hướng đích. Điều đó có nghĩa là không gửi gói đến những đường mà rõ rang nằm trên hướng sai. 4.2.2. Định tuyến bước ngẫu nhiên (random walk) Trong phương pháp định tuyến này, router sẽ chuyển gói đi đến trên một đường đầu ra được chọn một cách ngẫu nhiên. Mục tiêu của phương pháp này là các gói lang thang trong mạng cuối cùng cũng đến đích. Với phương pháp này giúp cho quá trình cân bằng tải giữa các đường. Cũng giống như phương pháp định tuyến lan tràn gói, phương pháp này luôn đảm bảo là gói cuối cùng sẽ đến đích. So với phương pháp trước thì sự nhân rộng gói trong mạng sẽ ít hơn. Nhược điểm của phương pháp này là đường từ nguồn đến đích có thể dài hơn đường ngắn nhất. Do đó trễ đường truyền sẽ dài hơn sẽ trễ ngắn nhất thực sự tồn tại trong mạng. 4.2.3. Định tuyến khoai tây nóng (hot potato) Định tuyến riêng biệt là loại định tuyến mà router quyết định tuyến đi chỉ dựa vào thông tin bản thân nó lượm lặt được. Đây là một thuật toán tương thích riêng biệt (isolated adaptive algorithm). Khi một gói đến một nút, router sẽ cố gắng chuyển gói đó đi càng nhanh càng tốt bằng cách cho nó vào hàng chờ đầu ra ngắn nhất. Nói cách khác, khi có gói đi đến router sẽ tính toán số gói được nằm chờ để truyền tren mỗi đường đầu ra. Sau đó nó sẽ gán gói mới vào cuối hàng chờ ngắn nhất mà không quan tâm đến đường đó sẽ đi đâu. Hình 4-1 biễu diễn các hàng chờ đầu ra bên trong một router tại một thời điểm nào đó. Có ba hàng chờ đầu ra tương ứng với 03 đường ra. Các gói đang xếp hàng trên mỗi đường để chờ được truyền đi. Trong ví dụ ở đây, hàng chờ đến F là hàng chờ ngắn nhất với 41
49. chỉ có một gói nằm trên hàng chờ này. Giảu thuật khoai tây nóng do đó sẽ đặt gói mới đến vào hàng chờ này. Hình 4-1. Hàng chờ bên trong router Có thể biến đổi ý tưởng này một chút bằng cách kết hợp định tuyến tĩnh với giải thuật khoai tây nóng. Khi gói đi đến, router sẽ tính đến cả những trọng số tĩnh của đường dây và độ dài hàng chờ. Một khả năng là sử dụng lựa chọn tĩnh tốt nhất trừ khi độ dài hàng chờ lớn hơn một ngưỡng nào đó. Một khả năng khác là sử dụng độ dài hàng chờ ngắn nhất trừ trọng số tĩnh của nó là quá thấp. Còn một cách khác là sắp xếp các đường theo trọng số tĩnh của nó và sau đó lại sắp xếp theo độ dài hàng chờ của nó. Sau đó sẽ chọn đường có tổng vị trí sắp xếp là nhỏ nhất. Dù giải thuật nào được chọn đi chăng nữa cũng có đặc tính là khi ít tải thì đường có trọng số cao nhất sẽ được chọn, nhưng sẽ làm cho hàng chờ cho đường này tăng lên. Sau đó một số lưu lượng sẽ được chuyển sang đường ít tải hơn. 4.2.4. Định tuyến nguồn (source routing) và mô hình cây (spanning tree) Chúng ta sẽ xét một số thuật toán cơ bản dùng cho việc tìm kiếm các cây được sử dụng để thiết kế và phân tích mạng. Một cây là một graph không có các vòng; bất kỳ một cặp nút nào cũng chỉ có duy nhất một đường đi. ở đây chủ yếu xem xét các graph vô hướng, những graph đó có các liên kết được sử dụng cả hai chiều trong quá trình tạo ra các đường đi. Vì một số lý do, các cây rất hữu dụng và được sử dụng như là graph cơ bản cho các thuật toán và các kỹ thuật phân tích và thiết kế mạng. Thứ nhất, các cây là mạng tối thiểu; cung cấp một sự kết nối mà không một liên kết nào là không cần thiết. Thứ hai, do việc chỉ cung cấp duy nhất một đường đi giữa một cặp nút bất kỳ, các cây giải quyết các vần đề về định tuyến (nghĩa là quyết định việc chuyển lưu lượng giữa hai nút). Điều đó làm đơn giản mạng và dạng của nó. Tuy nhiên, vì các cây liên thông tối thiểu nên cũng đơn giản và có độ tin cậy tối thiểu. Đó là nguyên nhân tại sao các mạng thực tế thường có tính liên thông cao hơn. Chính vì vậy, việc thiết kế một mạng thường bắt đầu bằng một cây. 42
50. 4.2.5. Duyệt cây Cho trước một cây nào đó, chúng ta có thể đi tới mọi nút của nó. Quá trình đó gọi là một quá trình duyệt cây. Trong quá trình thực hiện, các cạnh trong cây được duyệt hai lần, mỗi lần theo một hướng khác nhau. Có nhiều cách duyệt khác nhau. Đầu tiên, chỉ ra một nút của cây làm nút gốc. Việc duyệt được thực hiện xoay quanh nút đó. Có một số điều kiện để lựa chọn nút gốc này (chẳng hạn nút gốc là một khu vực máy tính trung tâm). Ngoài ra, nút gốc có thể được chọn một cách ngẫu nhiên. Giả sử nút A trong hình 4.1 là nút gốc của cây. Từ A chúng ta có thể lần lượt đi tới các nút kề cận của nó như là B, C hoặc D. Sau đó, lại đi theo các nút kề cận của chúng (B, C và D) là E, F, G và H. Tiếp tục đi tới lần lượt các nút kề cận khác bên cạnh các nút này. Khi đó, việc duyệt này sẽ kết thúc khi tới các nút I, J, K và L. Quá trình này được gọi là tìm kiếm theo chiều rộng. Trong quá trình tìm kiếm theo chiều rộng một đặc điểm cần chú ý là những nút gần nút gốc nhất sẽ được tới trước. Việc tìm kiếm sẽ thực hiện theo mọi hướng cùng lúc. Điều đó đôi khi có ích và được thực hiện dễ dàng. Một thuật toán nhằm đi tới mọi nút của cây thì được gọi là thuật toán duyệt cây. Thuật toán sau đây, Bfstree, thực hiện một quá trình tìm kiếm theo chiều rộng. (Chúng ta quy ước rằng, các tên hàm có ký tự đầu tiên là ký tự hoa để phân biệt chúng với các tên biến). Bfstree sẽ sử dụng một danh sách kề cận n_adj_list, danh sách này liệt kê tất cả các nút kề cận của mỗi nút thuộc cây. Để đơn giản hơn, giả sử rằng cây này là một cây hữu hướng hướng ra nhìn từ gốc và do đó n_adj_list sẽ chỉ bao gồm các nút kề cận với một nút nào đó mà các nút kề cận đó xa gốc hơn so với nút đang xét. 43
51. Hình 4-2. Duyệt cây void <-BfsTree ( n, root, n_adj_list ): dcl n_adj_list [n, list ] scan_queue [queue ] InitializeQueue (scan_queue ) Enqueue( root, scan_queue ) while (NotEmpty(scan_queue)) node <- Dequeue (scan_queue) Visit(node ) for each (neighbor , n_adj_list [node ]) Enqueue(neighbor, scan_queue) Visit là một thủ tục trong đó thực hiện một số quá trình nào đó đối với mỗi nút (chẳng hạn như in lên màn hình các thông tin của mỗi nút .v.v). Thuật toán này được thực hiện cùng một hàng đợi. Hàng đợi là một FIFO; trong đó các phần tử được thêm vào từ phía sau hàng đợi và chuyển ra từ phía trước. Các thủ tục InitializeQueue, Enqueue, Dequeue, NotEmpty làm việc trên các hàng đợi. InitializeQueue thiết lập một hàng đợi rỗng. Enqueue, Dequeue là các thủ tục để thêm một phần tử vào cuối hàng đợi và chuyển một phần tử ra từ đầu hàng đợi. Hàm NotEmpty trả về TRUE hoặc FALSE tuỳ thuộc vào hàng đợi có rỗng hay không. 44
52. n_adj_list là một chuỗi mà mỗi phần tử của chuỗi là một danh sách. n_adj_list[n] là một danh sách các nút kề cận nút n. Như đã nói ở chương trước, for_each(element, list), là một cấu trúc điều khiển thực hiện vòng lặp đối với tất cả các phần tử của list và thực hiện các mã ở bên trong vòng lặp, trong vòng lặp đó các phần tử của list lần lượt được sử dụng. Thủ tục trên hoạt động với giả thiết là n_adj_list đã được thiết lập trước khi thủ tục BfsTree được gọi. Tương tự, ta có thể định nghĩa một quá trình tìm kiếm theo chiều sâu. Quá trình này cũng bắt đầu từ nút gốc. Quá trình duyệt tiếp tục thực hiện nút láng giềng chưa được duyệt của nút vừa mới được duyệt. Ta cũng giả sử rằng cây bao gồm các liên kết có hướng đi ra xa nút gốc. Ví dụ 4.1: Trở lại với graph trong hình 4.1, ta có thể tới nút B từ nút A. Sau đó, ta tới nút E, kề cận với nút B-nút được duyệt gần thời điểm hiện tại nhất. Nút E này không có nút kề cận chưa duyệt nào, do vậy ta phải quay trở lại nút B để đi sang nút F. Ta tiếp tục đi tới các nút I, J, K (cùng với việc quay lại nút I), và nút L. Sau đó ta quay trở về nút A, tiếp tục tới các nút còn lại là C, D, G và H. Do vậy, toàn bộ quá trình duyệt là: A, B, E, F, I, J, K, L, C, D, G, H Nhớ rằng thứ tự của quá trình duyệt là không duy nhất. Trong quá trình duyệt trên ta chọn các nút kề cận để xâm nhập theo thứ tự từ trái qua phải. Nếu chọn theo thứ tự khác, quá trình duyệt là: A, B, F, I, J, K, L, E, D, H, G, C Trật tự thực tế của quá trình duyệt phụ thuộc vào từng thuật toán cụ thể. Điều này cũng đúng với một quá trình tìm kiếm theo chiều rộng. Kiểm tra thuật toán BfsTree, trật tự này là một hàm của trật tự các nút cận kề trong n_adj_list. Thuật toán DfsTree sau sẽ thực hiện một quá trình tìm kiếm theo chiều sâu. void <- DfsTree(n, root, n_adj_list): dcl n_adj_list [n, list] Visit(root) for each(neighbor, n_adj_list[node]) DfsTree(n, neighbor, n_adj-list) Quá trình tìm kiếm này sẽ được thực hiện với sự trợ giúp của một ngăn xếp theo kiểu LIFO, nghĩa là phần tử được thêm vào và chuyển ra từ đỉnh ngăn xếp. Trong trường hợp này, chúng ta thường gọi đệ quy DfsTree, thực 45
53. tế chúng ta đã sử dụng ngăn xếp hệ thống, nghĩa là sử dụng loại ngăn xếp mà hệ thống sử dụng để lưu giữ các lời gọi hàm và đối số. Cả hai loại duyệt trình bày ở trên đều là quá trình duyệt thuận (nghĩa là các quá trình này duyệt một nút rồi sau đó duyệt tới nút tiếp theo của nút đó). Quá trình duyệt ngược đôi khi cũng rất cần thiết, trong quá trình duyệt ngược một nút được duyệt sau khi đã duyệt nút tiếp của nút đó. Dĩ nhiên, cũng có thể thành lập một danh sách thuận và sau đó đảo ngược danh sách đó. Cũng có thể thay thế trật tự tìm kiếm một cách trực tiếp như thủ tục sau: void <- PostorderDfsTree(n, root, n_adj_list): dcl n_adj_list [n, list] for each(neighbor, n_adj_list[node]) PostorderDfsTree(n, neighbor, n_adj_list) Visit (root) Các thành phần liên thông trong các graph vô hướng Ta có thể áp dụng khái niệm duyệt các nút vào một graph vô hướng, đơn giản chỉ bằng cách theo dõi các nút đã được duyệt và sau đó không duyệt các nút đó nữa. Có thể duyệt một graph vô hướng như sau: void <- Dfs(n, root, n_adj_list): dcl n_adj_list [n, list] visited [n] void <- DfsLoop (node) if (not(visited [node]) visited [node]<-TRUE visit [node] for each(neighbor, n_adj_list[node]) DfsLoop (neighbor) visited <-FALSE DfsLoop (root) Chú ý rằng câu lệnh Visited <-FALSE khởi tạo toàn bộ các phần tử mảng được duyệt bằng FALSE. Cũng cần chú ý rằng thủ tục DfsLoop được định nghĩa bên trong thủ tục Dfs nên 46
54. DfsLoop có thể truy cập tới visited và n_adj_list (Lưu ý rằng cách dễ nhất để đọc các giả mã cho các hàm có dạng hàm Dfs ở trên là trước tiên hãy đọc thân của hàm chính rồi quay trở lại đọc thân của các hàm nhúng như hàm DfsLoop). Chú ý rằng trong quá trình duyệt chúng ta đã ngầm kiểm tra tất cả các cạnh trong graph, một lần cho mỗi đầu cuối của mỗi cạnh. Cụ thể, với mỗi cạnh (i, j) của graph thì j là một phần tử của n_adj_list[i] và i là một thành phần trong n_adj_list[j]. Thực tế, có thể đưa chính các cạnh đó vào các danh sách kề cận của nó và sau đó tìm nút ở điểm cuối khác của cạnh đó bằng hàm: node <- OtherEnd(node1, edge) Hàm này sẽ trả về một điểm cuối của edge khác với node1. Điều đó làm phức tạp quá trình thực hiện đôi chút. Có thể dễ dàng thấy rằng độ phức tạp của các thuật toán duyệt cây này bằng O(E), với E là số lượng cạnh trong graph. Bây giờ chúng ta có thể tìm được các thành phần liên thông của một graph vô hướng bằng cách duyệt mỗi thành phần. Chúng ta sẽ đánh dấu mỗi nút bằng một chỉ số thành phần khi chúng ta tiến hành. Các biến n_component sẽ theo dõi bất kỳ thành phần nào mà chúng ta đi tới void <- LabelComponent (n, n_adj_list): dcl n_component_number [n], n_adj_list[n,list] void <- Visit [node] n_component_number [node]<- ncomponents n_component_number<-0 ncomponent<-0 for each(node, node_set) if (n_component_number [node]=0) ncomponent +=1 Dfs (node, n_adj_list) Chúng ta định nghiã một hàm Visit để thiết lập một chỉ số thành phần các nút được duyệt. Hàm này nằm bên trong thủ tục LabelComponent và chỉ có thể được gọi từ trong thủ tục đó. Mặt khác, Dfs còn được định nghĩa ở bên ngoài, vì thế nó có thể được gọi từ bất kỳ đâu. Trong khi thực hiện quá trình duyệt theo chiều rộng và chiều sâu một graph vô hướng, những cạnh nối một nút với một nút láng giềng chưa duyệt trước khi duyệt nút đó tạo ra một cây, nếu graph là không liên thông thì tạo ra một rừng. 47
55. Hình 4-3. Các thành phần Hình 4-3 biểu diễn một graph có 4 thành phần. Giả sử vòng trên tập các nút đi theo tuần tự alphabet, các thành phần được đánh số theo trật tự các nút có chữ cái "thấp nhât" và chỉ số thành phần được biểu diễn ở bên cạnh nút. Với mỗi thành phần, thuật toán trên sẽ gọi Dfs để kiểm tra thành phần đó. Trong đó, thuật toán cũng kiểm tra các cạnh, mỗi cạnh một lần. Vì thế, độ phức tạp của nó có bậc bằng bậc của tổng số các nút cộng với số các cạnh trong tất cả các thành phần (nghĩa là độ phức tạp của thuật toán bằng O(N+E)). Cây bắc cầu tối thiểu (Minimum Spanning Tree) Có thể sử dụng Dfs để tìm một cây bắc cầu nếu có một cây bắc cầu tồn tại. Cây tìm được thường là cây vô hướng. Việc tìm cây "tốt nhất" thường rất quan trọng . Chính vì vậy, chúng ta có thể gắn một "độ dài" cho mỗi cạnh trong graph và đặt ra yêu cầu tìm một cây có độ dài tối thiểu. Thực tế, "độ dài" có thể là khoảng cách, giá, hoặc là một đại lượng đánh giá độ trễ hoặc độ tin cậy. Một cây có tổng giá là tối thiểu được gọi là cây bắc cầu tối thiểu. Nói chung, nếu graph là một graph không liên thông, chúng ta có thể tìm được một rừng bắc cầu tối thiểu. Một rừng bắc cầu tối thiểu là một tập hợp các cạnh nối đến graph một cách tối đa có tổng độ dài là tối thiểu. Bài toán này có thể được xem như là việc lựa chọn một graph con của graph gốc chứa tất cả các nút của graph gốc và các cạnh được lựa chọn. Đầu tiên, tạo một graph có n nút, n thành phần và không có cạnh nào cả. Mỗi lần, chúng ta chọn một cạnh để thêm vào graph này hai thành phần liên thông trước đó chưa được kết nối được liên kết lại với nhau tạo ra một thành phần liên thông mới (chứ không chọn các cạnh thêm vào một thành phần liên thông trước đó và tạo ra một vòng). Vì vậy, tại bất kỳ giai đoạn nào của thuật toán, quan hệ: n=c+e 48
56. luôn được duy trì, ở đây n là số lượng nút trong graph, e là số cạnh được lựa chọn tính cho tới thời điểm xét và c là số lượng thành phần trong graph tính cho tới thời điểm xét. Ở cuối thuật toán, e bằng n trừ đi số thành phần trong graph gốc; nếu graph gốc là liên thông, chúng ta sẽ tìm được một cây có (n-1) cạnh. Như đã giải thích ở trên, Dfs sẽ tìm ra một rừng bắc cầu. Tuy nhiên, chúng ta thường không tìm được cây bắc cầu có tổng độ dài tối thiểu. Thuật toán "háu ăn" Một cách tiếp cận khả dĩ để tìm một cây có tổng độ dài tối thiểu là, ở mỗi giai đoạn của thuật toán, lựa chọn cạnh ngắn nhất có thể. Thuật toán đó gọi là thuật toán "háu ăn". Thuật toán này có tính chất "thiển cận" nghĩa là không lường trước được các kết quả cuối cùng do các quyết định mà chúng đưa ra ở mỗi bước gây ra. Thay vào đó, chúng chỉ đưa ra cách chọn tốt nhất cho mỗi quá trình lựa chọn. Nói chung, thuật toán "háu ăn" không tìm được lời giải tối ưu cho một bài toán. Thực tế thuật toán thậm chí còn không tìm được một lời giải khả thi ngay cả khi lời giải đó tồn tại. Tuy nhiên chúng hiệu quả và dễ thực hiện. Chính vì vậy chúng được sử dụng rộng rãi. Các thuật toán này cũng thường tạo cơ sở cho các thuật toán có tính hiệu quả và phức tạp hơn. Vì thế, câu hỏi đầu tiên đặt ra khi xem xét việc ứng dụng một thuật toán để giải quyết một bài toán là liệu bài toán ấy có hay không cấu trúc nào đó đảm bảo cho thuật toán hoạt động tốt. Hy vọng rằng thuật toán ít ra cũng đảm bảo được một lời giải khả thi nếu lời giải đó tồn tại. Khi đó, nó sẽ đảm bảo tính tối ưu và đảm bảo yêu cầu nào đó về thời gian thực hiện. Bài toán tìm các cây bắc cầu tối thiểu thực sự có một cấu trúc mạnh cho phép thuật toán "háu ăn" đảm bảo cả tính tối ưu cũng như đảm bảo độ phức tạp tính toán ở mức độ vừa phải. Dạng chung của thuật toán "háu ăn" là: Bắt đầu bằng một lời giải rỗng s. Trong khi vẫn còn có các phần tử cần xét, Tìm e, phần tử "tốt nhất" vẫn chưa xét Nếu việc thêm e vào s là khả thi thì e được thêm vào s, nếu việc thêm đó không khả thi thì loại bỏ e. Các yêu cầu các khả năng sau: So sánh giá trị của các phần tử để xác định phần tử nào là "tốt nhất" Kiểm tra tính khả thi của một tập các phần tử 49
57. Khái niệm "tốt nhất" liên quan đến mục đích của bài toán. Nếu mục đích là tối thiểu, "tốt nhất" nghĩa là bé nhất. Ngược lại, "tốt nhất" nghĩa là lớn nhất. Thường thường, mỗi giá trị gắn liền với một phần tử, và giá trị gắn liền với một tập đơn giản chỉ là tổng các giá trị đi cùng của các phần tử trong tập đó. Đó là trường hợp cho bài toán cây bắc cầu tối thiểu được xét trong phần này. Tuy nhiên, đó không phải là trường hợp chung. Chẳng hạn, thay cho việc tối thiểu tổng độ dài của tất cả các cạnh trong một cây, mục đích của bài toán là tối thiểu hoá độ dài các cạnh dài nhất trong cây. Trong trường hợp đó, giá trị của một cạnh là độ dài của cạnh đó và giá trị của một tập sẽ là độ dài của cạnh dài nhất nằm trong tập. Muốn tìm được cạnh "tốt nhất" để bổ sung, hãy đánh giá các cạnh theo độ ảnh hưởng về giá trị của nó tới giá trị của tập. Giả sử V(S) là giá trị của tập S và v(e,S) là giá trị của một phần tử e thì v(e,S) có quan hệ với tập S bởi công thức v(e,S)= V(S  e) - V(S) Trong trường hợp tối thiểu độ dài của cạnh dài nhất trong một cây. v(e,S) bằng 0 đối với bất kỳ cạnh nào không dài hơn cạnh dài nhất đã được chọn. Ngược lại, nó sẽ bằng hiệu độ dài giữa cạnh với cạnh dài nhất đã được chọn, khi hiệu đó lớn hơn 0. Trong trường hợp chung, giá trị của tập có thể thay đổi một cách ngẫu nhiên khi các phần tử được bổ sung vào nó. Chúng ta có thể gán giá trị 1 cho các tập có số lượng phần tử là chẵn và 2 cho các tập có số lượng phần tử là lẻ. Điều đó làm cho các giá trị của các phần tử chỉ là một trong hai giá trị +1 và -1. Trong trường hợp này, thuật toán "háu ăn" không được sử dụng. Bây giờ giả sử rằng "trọng lượng" của một tập biến đổi theo một cách hợp lý hơn thì khi đó, sẽ có một cơ sở hợp lý hơn cho việc chỉ ra phần tử "tốt nhất". Một điều quan trọng cần chú ý đó là, khi tập lớn lên, giá trị của phần tử mà trước đó không được xem xét có thể thay đổi do các phần tử thêm vào tập đó. Khi điều này xảy ra, thuật toán "háu ăn" có thể mắc lỗi trong các lựa chọn của nó và sẽ ảnh hưởng tới chất lượng của lời giải mà chúng ta nhận được. Tương tự, trong hầu hết các trường hợp, tính khả thi có thể bị ảnh hưởng một cách ngẫu nhiên do sự bổ sung phần tử. Chính vì vậy, trong các bài toán mà những tập có số lượng phần tử chẵn có thể được xem là khả thi và những tập có số phần tử là lẻ có thể được xem là không khả thi thì thuật toán "háu ăn" hoặc bất kỳ thuật toán nào có bổ sung các phần tử, mỗi lần một phần tử, sẽ không hoạt động. Vì vậy chúng ta sẽ giả thiết các tính chất sau, những tính chất này luôn được duy trì trong mọi trường hợp xem xét: Tính chất 1: 50
58. Bất kỳ một tập con nào của một tập khả thi thì cũng khả thi, đặc biệt tập rỗng cũng là một tập khả thi. Ngoài ra giả thiết rằng độ phức tạp của thuật toán để tính toán giá trị của một tập và kiểm tra sự khả thi của chúng là vừa phải, đặc biệt, khi độ phức tạp này là một đa thức của số nút và cạnh trong graph. list<-Greedy (properties) dcl properties [list, list] candidate_set[list] solution[list] void<-GreedyLoop ( *candidate_set, *solution) dcl test_set[list],solution[list], candidate_set[list] element <- SelectBestElement(candidate_set) test_set <-Append(element,solution) if(Test(test_set)) solution<-test_set candidate_set<-Delete(element,candidate_set) if(not(Empty(candidate_set))) Greedy_loop(*candidate_set, *solution) candidate_set<-ElementsOf(properties) solution<- if(!(Empty(element_set))) GreedyLoop(*candidate_set, *solution) return(solution) Bây giờ ta đã có thể xem xét sâu hơn các câu lệnh của thuật toán "háu ăn". Các câu lệnh của thuật toán hơi khó hiểu vì chúng dựa trên định nghĩa của hai hàm, Test và SelestBestElement (là hàm kiểm tra tính khả thi và đánh giá các tập). Chúng ta cũng giả sử rằng có một cấu trúc properties, là một danh sách của các danh sách chứa tất cả các thông tin cần thiết để kiểm tra và đánh giá tất cả các tập. Một danh sách của các danh sách đơn giản chỉ là một danh sách liên kết, mà mỗi thành viên của nó là một danh sách. Thậm chí cấu trúc đó có thể được lồng vào nhau sâu hơn, nghĩa là có các danh sách nằm bên trong các danh sách nằm bên trong các danh sách. Cấu trúc như vậy tương đối phổ biến và có thể được sử dụng để biểu diễn hầu hết các kiểu thông tin. Có thể lưu giữ độ dài, loại liên kết, dung lượng, hoặc địa chỉ. Bản thân các mục thông tin này có thể là một cấu trúc phức tạp; nghĩa là cấu trúc đó có thể 51
59. lưu giữ giá và các dung lượng của một vài loại kênh khác nhau cho mỗi liên kết. Trên thực tế, điều đó rất có ích cho việc duy trì các cấu trúc dữ liệu trợ giúp để cho phép thuật toán thực hiện hiệu quả hơn. Bài toán về cây bắc cầu tối thiểu là một ví dụ. Tuy nhiên, để rõ ràng, giả sử rằng tất cả quá trình tính toán được thực hiện trên một cấu trúc properties sẵn có (đã được khởi tạo).  được sử dụng để biểu diễn tập rỗng. Append và Delete là các hàm bổ sung và chuyển đi một phần tử khỏi một danh sách. ElementsOf chỉ đơn giản để chỉ ra các phần tử của một danh sách; vì vậy, ban đầu tất cả các phần tử trong properties là các ứng cử. Có rất nhiều cách thực hiện các quá trình này. properties có thể là một dãy và các hàm Append, Delete và ElementsOf có thể hoạt động với các danh sách chỉ số (danh sách mà các phần tử là các chỉ số mạng). Trong thực tế cách thực hiện được chọn là cách làm sao cho việc thực hiện các hàm Test và SelectBestElement là tốt nhất. Đoạn giả mã trên giả thiết rằng thuật toán "háu ăn" sẽ dừng lại khi không còn phần tử nào để xem xét. Trong thực tế, có nhiều nguyên nhân để thuật toán dừng lại. Một trong những nguyên nhân là khi kết quả xấu đi khi các phần tử được tiếp tục thêm vào. Điều nay xảy ra khi tất cả các phần tử còn lại đều mang giá trị âm trong khi chúng ta đang cố tìm cho một giá trị tối đa. Một nguyên nhân khác là khi biết rằng không còn phần tử nào ở trong tập ứng cử có khả năng kết hợp với các phần tử vừa được chọn tạo ra một lời giải khả thi. Điều này xảy ra khi một cây bắc cầu toàn bộ các nút đã được tìm thấy. Giả sử rằng thuật toán dừng lại khi điều đó là hợp lý, còn nếu không, các phần tử không liên quan sẽ bị loại ra khỏi lời giải. Giả thiết rằng, các lời giải cho một bài toán thoả mãn tính chất 1 và giá trị của tập đơn giản chỉ là tổng các giá trị của các phần tử trong tập. Ngoài ra, giả thiết thêm rằng tính chất sau được thoả mãn: Tính chất 2: Nếu hai tập Sp và Sp+1 lần lượt có p và p+1 phần tử là các lời giải và tồn tại một phần tử e thuộc tập Sp+1 nhưng không thuộc tập Sp thì Sp{e} là một lời giải. Chúng ta thấy rằng, các cạnh của các rừng thoả mãn tính chất 2, nghĩa là nếu có hai rừng, một có p cạnh và rừng kia có p+1 thì luôn tìm được một cạnh thuộc tập lớn hơn mà việc thêm cạnh đó vào tập nhỏ hơn không tạo ra một chu trình. Một tập các lời giải thoả mãn các tính chất trên gọi là một matroid. Định lý sau đây là rất quan trọng (chúng ta chỉ thừa nhận chứ không chứng minh). Định lý 4.1 52
60. Thuật toán “háu ăn” đảm bảo đảm một lời giải tối ưu cho một bài toán khi và chỉ khi các lời giải đó tạo ra một matroid. Có thể thấy rằng, tính chất 1 và tính chất 2 là điều kiện cần và đủ để đảm bảo tính tối ưu của thuật toán “háu ăn” . Nếu có một lời giải cho một bài toán nào đó mà nó thoả mãn hai tính chất 1 và 2 thì cách đơn giản nhất là dùng thuật toán “háu ăn” để giải quyết nó. Điều đó đúng với một cây bắc cầu. Sau đây là một định lý không kém phần quan trọng. Định lý 4.2 Nếu các lời giải khả thi cho một bài toán nào đó tạo ra một matroid thì tất cả các tập khả thi tối đa có số lượng phần tử như nhau. Trong đó, một tập khả thi tối đa là một tập mà khi thêm các phần tử vào thì tính khả thi của nó không được bảo toàn; Nó không nhất thiết phải có số lượng phần tử tối đa cũng như không nhất thiết phải có trọng lượng lớn nhất. Định lý đảo của định lý trên cũng có thể đúng nghiã là nếu tính chất 1 được thoả mãn và mọi tập khả thi tối đa có cùng số lượng phần tử, thì tính chất 2 được thoả mãn. Định lý 4.2 cho phép chúng ta chuyển đổi một bài toán tối thiểu P thành một bài toán tối đa P' bằng cách thay đổi các giá trị của các phần tử. Giả thiết rằng tất cả v(xj) trong P có giá trị âm. Lời giải tối ưu cho bài toán P có số lượng phần tử tối đa là m thì chúng ta có thể tạo ra một bài toán tối đa P' từ P bằng cách thiết lập các giá trị của các phần tử trong P' thành -v(xj). Tất cả các phần tử đều có giá trị dương và P' có một lời giải tối ưu chứa m phần tử. Thực ra, thứ tự của các lời giải tối đa phải được đảo lại: lời giải có giá trị tối đa trong P' cũng là lời giải có giá trị tối thiểu trong P. Giả sử lúc nay ta cần tìm một lời giải có giá trị tối thiểu, tuân theo điều kiện là có số lượng tối đa các phần tử. Sẽ tính cả các phần tử có giá trị dương. Có thể giải quyết bài toán P như là một bài toán tối đa P' bằng cách thiết lập các giá trị của các phần tử thành B-v(xj) với B có giá trị lớn hơn giá trị lớn nhất của xj. Khi đó các giá trị trong P' đều dương và P' là một lời giải tối ưu có m phần tử. Thứ tự của tất cả các tập khả thi tối đa đã bị đảo ngược: một tập có giá trị là V trong P thì có giá trị là mB-V trong lời giải P'. Một giá trị tối đa trong P' thì có giá trị tối thiểu trong P. Quy tắc này cũng đúng với các cây bắc cầu thoả mãn tính chất 1 và tính chất 2 và có thể tìm một cây bắc cầu tối thiểu bằng cách sử dụng một thuật toán “háu ăn”. 53
61. Thuật toán Kruskal Thuật toán Kruskal là một thuật toán “háu ăn” được sử dụng để tìm một cây bắc cầu tối thiểu. Tính đúng đắn của thuật toán dựa trên các định lý sau: Định lý 4.3 Các rừng thì thoả mãn tính chất 1 và 2. Như chúng ta đã biết, một rừng là một tập hợp các cạnh mà tập hợp đó không chứa các chu trình. Rõ ràng là bất kỳ một tập con các cạnh nào của một rừng (thậm chí cả tập rỗng) cũng là một rừng, vì vậy tính chất 1 được thoả mãn. Để thấy rằng tính chất 2 cũng thoả mãn, xét một graph được biểu diễn trong hình 4.4. Hình 4.3. Giả sử có một rừng F1 có p cạnh. Rừng {2,4} là một ví dụ với p=2, và nó được biểu diễn bằng nét đứt trong hình 4.4. Khi đó xét một rừng khác F2 có p+1 cạnh. Có hai trường hợp được xét. Trường hợp 1: F2 đi tới một nút n, nhưng F1 không đi tới nút đó. Một ví dụ của trường hợp này là rừng {1, 4, 6}, rừng này đi tới E còn F1 thì không. Trong trường hợp này, có thể tạo ra rừng {2, 4, 6} bằng cách thêm cạnh 6 vào rừng {2,4}. Trường hợp 2: F2 chỉ đi tới các nút mà F1 đi tới. Một ví dụ của trường hợp này là rừng {1. 4. 5}. Xét S, một tập các nút mà F1 đi tới. Cho rằng có k nút trong tập S. Vì F1 là một rừng nên mỗi cạnh trong F1 giảm số lượng thành phần trong S đi một, do đó tổng số lượng thành phần là k-p. Tương tự, F2 tạo ra k-(p+1) thành phần từ S (số lượng thành phần vừa nói bé hơn với số lượng thành phần của F1). Vì vậy, một cạnh tồn tại trong F2 mà các điểm 54
62. cuối của nó nằm ở các thành phần khác nhau trong F1 thì có thể thêm cạnh đó vào F1 mà không tạo ra một chu trình. Cạnh 3 là một cạnh có tính chất đó trong ví dụ này (cạnh 1 và 5 cũng là những cạnh như vậy). Vì thế, chúng ta thấy rằng nếu tính chất 1 và 2 được thoả mãn thì một thuật toán “háu ăn” có thể tìm được một lời giải tối ưu cho cả bài toán cây bắc cầu tối thiểu lẫn bài toán cây bắc cầu tối đa. Chú ý rằng một cây bắc cầu là một rừng có số cạnh tối đa N-1 cạnh với N là số nút trong mạng. Sau đây chúng ta sẽ xét bài toán tối thiểu. Thuật toán Kruskal thực hiện việc sắp xếp các cạnh với cạnh đầu tiên là cạnh ngắn nhất và tiếp theo chọn tất cả các cạnh mà những cạnh này không cùng với các cạnh được lựa chọn trước đó tạo ra các chu trình. Chính vì thế, việc thực hiện thuật toán đơn giản là: list <- kruskal_l( n, m, lengths ) dcl length[m], permutation[m], solution[list] permution <- VectorSort( n , lengths ) solution <-  for each ( edge , permutation ) if ( Test(edge , solution ) ) solution <- Append ( edge , solution ) return( solution ) VectorSort có đầu vào là một vector có độ dài là n và kết quả trả về là thứ tự sắp xếp các số nguyên từ 1 tới n. Sự sắp xếp đó giữ cho giá trị tương ứng trong vector theo thứ tự tăng dần. Ví dụ 4.2: Giả sử rằng n= 5 và giá trị của một vector là 31, 19, 42, 66, 27 VectorSort sẽ trả về thứ tự sắp xếp như sau: 2, 5, 1, 3, 4 Test nhận một danh sách các cạnh và trả về giá trị TRUE nếu các cạnh đó không chứa một chu trình. Vì Test được gọi cho mỗi nút, sự hiệu quả của toàn bộ thuật toán tuỳ thuộc vào tính hiệu quả của việc thực hiện Test. Nếu mỗi khi các cạnh được thêm vào cây, chúng ta theo dõi được các nút của cạnh thuộc các thành phần nào thì Test trở nên đơn giản; đó đơn giản chỉ là việc kiểm tra xem các nút cuối của các cạnh đang được xét có ở cùng một 55
63. thành phần không. Nếu cùng, cạnh sẽ tạo ra một chu trình. Ngược lại, cạnh đó không tạo nên chu trình. Tiếp đó là xem xét việc duy trì cấu trúc thành phần. Có một số cách tiếp cận. Một trong các cách đó là ở mỗi nút duy trì một con trỏ đến một nút khác trong cùng một thành phần và có một nút ở mỗi thành phần gọi là nút gốc của thành phần thì trỏ vào chính nó. Vì thế lúc đầu, bản thân mỗi nút là một thành phần và nó trỏ vào chính nó. Khi một cạnh được thêm vào giữa hai nút i và j, trỏ i tới j. Sau đó, khi một cạnh được thêm vào giữa một nút i trong một thành phần có nút gốc là k và một nút j trong một thành phần có nút gốc là l thì trỏ k tới l. Vì vậy, chúng ta có thể kiểm tra một cạnh bằng cách dựa vào các con trỏ từ các nút cuối của nó và xem rằng chúng có dẫn đến cùng một nơi hay không. Chuỗi các con trỏ càng ngắn, việc kiểm tra càng dễ dàng. Nhằm giữ cho các chuỗi các con trỏ đó ngắn, Tarjan gợi ý nên làm gọn các chuỗi khi chúng được duyệt trong quá trình kiểm tra. Cụ thể, ông gợi ý một hàm FindComponent được tạo ra như sau: index <- FindComponent(node , *next) dcl next[] p=next[node] q=next[p] while ( p!=q ) next[node]= q node = q p=next[node] q=next[p] return (p) FindComponent trả về nút gốc của thành phần chứa node. Hàm này cũng điều chỉnh next , nút hướng về nút gốc chứa nút đó. Đặc biệt, hàm này điều chỉnh next hướng tới điểm ở tầng cao hơn. Tarjan chỉ ra rằng, bằng cách đó, thà làm gọn đường đi tới nút gốc một các hoàn toàn còn hơn là không làm gọn một chút nào cả và toàn bộ kết quả trong việc tìm kiếm và cập nhật next chỉ lớn hơn so với O(n+m) một chút với n là số lượng nút và m là số lượng cạnh được kiểm tra. Ví dụ 4.3: 56
64. Hình 4-4. Phép tính Minimum Spanning Tree ( MST) Xét một mạng được biểu diễn trong hình 4.4. các dấu * trong hình được giải thích dưới đây. Đầu tiên, sắp xếp các cạnh và sau đó lần lượt xem xét từng cạnh, bắt đầu từ cạnh nhỏ nhất. Vì thế, chúng ta xem (A, C) là cạnh đầu tiên. Gọi FindComponent cho nút A ta thấy cả p lẫn q đều là A nên FindComponent trả về A như là nút gốc của thành phần chứa nút A. Tương tự, FindComponent trả về C như là nút gốc của thành phần chứa nút C. Vì thế, chúng ta mang A và C vào cây và thiết lập next[A] bằng C. Sau đó, xét (B, D). Hàm cũng thực hiện tương tự và B, D được thêm vào cây, next[B] bằng D. Chúng ta xét (C, E), chấp nhận nó và thiết lập next[C] bằng E. Bây giờ, xét (A, E). Trong FindComponent, p là C còn q là E. Vì thế chúng ta chạy vào vòng lặp while , thiết lập next[A] bằng E và rút ngắn đường đi từ A tới E với E là nút gốc của thành phần chứa chúng. Node, p và q được thiết lập thành E và FindComponent trả về E như là nút gốc của thành phần chứa nút A. FindComponent cũng trả về E như là nút gốc của thành phần chứa E. Vì thế, cả hai điểm cuối của (A, E) là cùng một thành phần nên (A, E) bị loại bỏ. Tiếp đến, xét (A, B). Trong quá trình gọi FindComponent đối với nút A, chúng ta thấy rằng p=q=E và next không thay đổi. Tương tự, quá trình gọi FindComponent đối với nút B ta được p=q=D. Vì thế, chúng ta thiết lập next[E] bằng D. Chú ý rằng, chúng ta không thiết lập next[A] bằng B, mà lại thiết lập next đối với nút gốc của thành phần của A bằng với nút gốc của thành phần của B. Cuối cùng, (C, D) được kiểm tra và bị loại bỏ. Trong hình 4.4 những cạnh trong cây bắc cầu được phân biệt bởi một dấu * ở ngay bên cạnh các cạnh đó. Nội dung các next được chỉ ra bằng các cung (các cạnh hữu hướng) có mũi tên. Chẳng hạn, next[B] bằng D được chỉ ra bằng một mũi tên từ B tới D. Chú ý rằng, các cung được định nghĩa bởi next tạo ra một cây, nhưng nói chung cây đó không phải là một cây bắc cầu tối thiểu. Thực vậy, với trường hợp có một cung (E, D), ngay cả khi các cung đó không cần thiết phải là một phần graph. Vì vậy, bản thân next chỉ định nghĩa 57
65. cấu trúc thành phần khi tiến hành thực hiện thuật toán. Chúng ta tạo một danh sách hiện các cạnh được chọn dành cho việc bao gộp trong cây. Giá của cây được định nghĩa bởi next tương đối bằng phẳng, nghiã là các đường đi tới các nút gốc của các thành phần là ngắn khiến FindComponent hoạt động hiệu quả. Hiển nhiên, sự phức tạp của thuật toán Kruskal được quyết định bởi việc sắp xếp các cạnh, sự sắp xếp đó có độ phức tạp là O(m log m). Nếu có thể tìm được cây bắc cầu trước khi phải kiểm tra tất cả các cạnh thì chúng ta có thể cải tiến quá trình đó bằng cách thực hiện sắp xếp phân đoạn. Cụ thể, chúng ta có thể lưu giữ các cạnh trong một khối (heap) và sau đó lấy ra, kiểm tra mỗi cạnh cho đến khi một cây được tạo ra. Chúng ta dễ dàng biết được quá trình đó dừng vào lúc nào; chỉ đơn giản là theo dõi số lượng cạnh đă được xét và dừng lại khi đã có n-1 cạnh được chấp nhận. Chúng ta giả sử rằng, các quá trình quản lý khối (heap) như thiết lập, bổ xung và lấy dữ liệu ra là đơn giản. Điều quan trọng cần chú ý ở đây là độ phức tạp của việc thiết lập một khối (heap) có m phần tử là O(m), độ phức tạp của việc tìm phần tử bé nhất là O(1) và độ phức tạp của việc khôi phục một khối (heap) sau khi bổ xung, xoá, hoặc thay đổi một giá trị là O(logm). Chính vì vậy, nếu chúng ta xét k cạnh để tìm cây bắc cầu, độ phức tạp trong việc duy trì một khối (heap) bằng O(m+klogm), độ phức tạp này bé hơn O(mlogm) nếu k có bậc bé hơn bậc của m. k tối thiểu bằng O(n) nên nếu graph là khá mỏng thì việc sử dụng khối (heap) sẽ không có lợi. Nếu graph là dày đặc thì việc lưu trữ đó có thể được xem xét. Đây là phiên bản cuối cùng của thuật toán Kruskal, thuật toán này tận dụng các hiệu ứng nói trên. list <- Kruskal_l( n, m, lengths ) dcl length[m], ends[m,2], next[n], solution[list], l_heap[heap] for each ( node , n ) next[node]<-node l_heap <-HeapSet(m, lengths) #_accept <-0 solution <-  while ( (#_accept < n-1) and !(HeapEmpty(l_heap)) edge <- HeapPop(*l_heap) c1=FindComponent(ends[edge,1], *next) c2=FindComponent(ends[edge,2], *next) if (c1 !=c2 ) next[c2] <- c1 solution <- Append ( edge , solution ) #_accept=#_accept+1 return( solution ) 58
66. HeapSet tạo ra một khối (heap) dựa vào các giá trị cho trước và trả về chính khối (heap) đó. HeapPop trả về chỉ số của giá trị ở đỉnh của khối (heap) chứ không phải bản thân giá trị đó. Điều này có lợi hơn việc trả về một giá trị vì từ chỉ số luôn biết được giá trị có chỉ số đó chứ từ giá trị không thể biết được chỉ số của giá trị đó. Cũng cần chú ý rằng HeapPop làm khối (heap) thay đổi. HeapEmpty trả về giá trị TRUE nếu khối (heap) rỗng. Mảng ends chứa các điểm cuối của các cạnh. Thuật toán Prim Thuật toán này có những ưu điểm riêng biệt, đặc biệt là khi mạng dày đặc, trong việc xem xét một bài toán tìm kiếm các cây bắc cầu tối thiểu (MST). Hơn nữa các thuật toán phức tạp hơn được xây dựng dựa vào các thuật toán MST này; và một số các thuật toán này hoạt động tốt hơn với các cấu trúc dữ liệu được sử dụng cho thuật toán sau đây, thuật toán này được phát biểu bởi Prim. Tóm lại, các thuật toán này phù hợp với các quá trình thực hiện song song bởi vì các quá trình đó được thực hiện bằng các toán tử vector. Thuật toán Prim có thể được miêu tả như sau: Bắt đầu với một nút thuộc cây còn tất cả các nút khác không thuộc cây (ở ngoài cây). Trong khi còn có các nút không thuộc cây Tìm nút không thuộc cây gần nhất so với cây Đưa nút đó vào cây và ghi lại cạnh nối nút đó với cây Thuật toán Prim dựa trên những định lý sau đây: Định lý 4.4. Một cây là một MST nếu và chỉ nếu cây đó chứa cạnh ngắn nhất trong mọi cutset chia các nút thành hai thành phần. Để thực hiện thuật toán Prim, cần phải theo dõi khoảng cách từ mỗi nút không thuộc cây tới cây và cập nhật khoảng cách đó mỗi khi có một nút được thêm vào cây. Việc đó được thực hiện dễ dàng; đơn giản chỉ là duy trì một dãy d_tree có các thông tin về khoảng cách đã nói ở trên. Quá trình đó tuân theo: 59
67. array[n] dist{i,j])) d_tree[j]<- dist[i,j] pred[j]<-i d_tree <- INFINITY pred <- -1 in_tree <- FALSE d_tree(root)<-0 #_in_tree <-0 while (#_in_tree < n) i <- FindMin() in_tree[i]<- TRUE Scan(i) #_in_tree =#_in_tree + 1 return (pred) FindMin trả về một nút không thuộc cây và gần cây nhất. Scan cập nhật khoảng cách tới cây đối với các nút không thuộc cây. Có thể thấy rằng độ phức tạp của thuật toán này là O(n2); cả hai hàm FindMin và Scan có độ phức tạp là O(n) và mỗi hàm được thực hiện n lần. So sánh với thuật toán Kruskal ta thấy rằng độ phức tạp của thuật toán Prim tăng nhanh hơn so với độ phức tạp của thuật toán Kruskal nếu m, số lượng các cạnh, bằng O(n2),còn nếu m có cùng bậc với n thì độ phức tạp của thuật toán Kruskal tăng nhanh hơn. Có thể tăng tốc thuật toán Prim trong trường hợp graph là một graph mỏng bằng cách chỉ quan tâm đến các nút láng giềng của nút i vừa được thêm vào cây. Nếu sẵn có các thông tin kề liền, vòng lặp for trong Scan có thể trở thành. 60
68. for each (j , n_adj_list[i] ) Độ phức tạp của Scan trở thành O(d) với d là bậc của nút i. Chính vì thế độ phức tạp tổng cộng của Scan giảm từ O(n2) xuống O(m). Thiết lập một tập kề liền cho toàn bộ một graph là một phép toán có độ phức tạp bằng O(m): index[nn,list] <- SetAdj(n ,m, ends) dcl ends[m,2], n_adj_list[n,list] for node = 1 to n n_adj_list[node] <-  for edge = 1 to m Append(edge, n_adj_list[end[edge,1]]) Append(edge, n_adj_list[end[edge,2]]) Có thể tăng tốc FindMin nếu ta thiết lập một khối (heap) chứa các giá trị trong d_tree. Vì thế, chúng ta có thể lấy ra giá trị thấp nhất và độ phức tạp tổng cộng của quá trình lấy ra là O(nlogn). Vấn đề ở chỗ là chúng ta phải điều chỉnh khối (heap) khi một giá trị trong d_tree thay đổi. Quá trình điều chỉnh đó có độ phức tạp là O(mlogn) trong trường hợp xấu nhất vì có khả năng mỗi cạnh sẽ có một lần cập nhật và mỗi lần cập nhật đòi hỏi một phép toán có độ phức tạp là O(logn). Do đó, độ phức tap của toàn bộ thuật toán Prim là O(mlogn). Qua thí nghiệm có thể thấy rằng hai thuật toán Prim và Kruskal có tốc độ như nhau, nhưng nói chung, thuật toán Prim thích hợp hơn với các mạng dày còn thuật toán Kruskal thích hợp hơn đối với các mạng mỏng. Tuy vậy, những thuật toán này chỉ là một phần của các thủ tục lớn và phức tạp hơn, đó là những thủ tục hoạt động hiệu quả với một trong những thuật toán này. Hình 4.2. Graph có liên kết song song và self loop 61
69. Bảng 4.1 N in D A C E B út it. 0 0(-) 0(-) 0(-) 0(-) 0(- A ) 1 10( 10( 10( 10( 10( B 00 A) A) A) A) A) 1 2( 2(A 2(A 2( 2( C 00 A) ) ) A) A) 1 100 11( 11( 5(B 5( D 00 (-) A) A) ) B) 1 7( 6(C 6(C 6(C 6( E 00 A) ) ) ) C) Ví dụ 4.4: Trở lại hình 4.4, giả sử rằng các cạnh không được biểu diễn có độ dài bằng 100. Thuật toán Kruskal sẽ chọn (A, C), (B, D), (C, E), và loại (A, E) bởi vì nó tạo ra một chu trình với các cạnh đã được chọn là (A, C) và (C, E), chọn (A, B) sau đó dừng lại vì một cây bắc cầu hoàn toàn đã được tìm thấy. Thuật toán Prim bắt đầu từ nút A, nút A sẽ được thêm vào cây. Tiếp theo là các nút C, E, B và D. Bảng 4.1 tổng kết các quá trình thực hiện của thuật toán Prim, biểu diễn d_tree và pred khi thuật toán thực hiện. Cuối thuật toán, pred[B] là A, tương ứng với (A, B) là một phần của cây. Tương tự, pred chỉ ra (A, C), (B, D) và (C, E) là các phần của cây. Vì vậy, thuật toán Prim sẽ lựa chọn được cây giống với cây mà thuật toán Kruskal nhưng thứ tự các liên kết được lựa chọn là khác nhau. Một đường đi trong một mạng là một chuỗi liên tiếp các liên kết bắt đầu từ một nút s nào đó và kết thúc tại một nút t nào đó. Những đường đi như vậy được gọi là một đường đi s, t. Chú ý rằng thứ tự các liên kết trong đường đi là có ý nghĩa. Một đường đi có thể là hữu hướng hoặc vô hướng tuỳ thuộc vào việc các thành phần của nó là các liên kết hay là các cung. Người ta gọi một đường đi là đường đi đơn giản nếu không có nút nào xuất hiện quá hai lần trong đường đi đó. Chú ý rằng một đường đi đơn giản trong một graph đơn giản có thể được biểu diễn bằng chuỗi liên tiếp các nút mà đường đi đó chứa vì chuỗi các nút đó biểu diễn duy nhất một chuỗi các liên kết . Nếu s trùng với t thì đường đi đó gọi là một chu trình, và nếu một nút trung gian xuất hiện không quá một lần thì chu trình đó được gọi là chu 62