Queueing System

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CƠ SỞ THÀNH PHỐ HỒ CHÍ MINH -----------oOo----------

BÁO CÁO NGHIÊN CỨU KHOA HỌC Tên đề tài: Tìm hiểu lý thuyết và mô phỏng trên phần mềm Ns2 các mô hình lý thuyết hàng đợi

Giáo viên hướng dẫn: Th.s NGUYỄN HUỲNH MINH TÂM Th.s LÊ HÀ THANH SVTH : Nguyễn Khánh Duy MSSV: 403170012 Lớp Đ03THA1 Trịnh Thị Trúc Chi MSSV: 403170007 Lớp Đ03THA1

Mục lục Chương 1 :Giới thiệu đề tài........................................................................................................................ 1 1.1. Đặt vấn đề ......................................................................................................................................... 1 1.2. Mục tiêu đề tài................................................................................................................................... 1 1.3. Giới hạn đề tài................................................................................................................................... 1 Chương 2 : Lý thuyết hàng đợi .................................................................................................................. 3 2.1. Lý thuyết tổng quát ........................................................................................................................... 3 2.1.1. Khái niệm traffic và đơn vị của traffic...................................................................................... 3 2.1.2. Poison Process........................................................................................................................... 4 2.2. Các mô hình hàng đợi ....................................................................................................................... 5 2.2.1. Giới thiệu: ................................................................................................................................. 5 2.2.2. Phân loại.................................................................................................................................... 6 2.2.3. Một số mô hình phổ biến .......................................................................................................... 6 2.2.4. Sơ đồ chuyển trạng thái ............................................................................................................ 8 2.2.5. Mô tả chi tiết các mô hình......................................................................................................... 9 Chương 3 :Xây dựng mô phỏng............................................................................................................... 23 3.1. Bộ mô phỏng NS2........................................................................................................................... 23 3.1.1. Giới thiệu ................................................................................................................................ 23 3.1.2. Kiến trúc NS2.......................................................................................................................... 23 3.2. Xây dựng mô phỏng cụ thể ............................................................................................................. 28 3.2.1. Hướng giải quyết: ................................................................................................................... 28 3.2.2. Xây dựng node SWITCH........................................................................................................ 28 3.2.3. Thiết kế lớp SWA ................................................................................................................... 31 3.2.4. Thiết kế hàng đợi cho switch .................................................................................................. 34 3.2.5. Cấu trúc lớp queue .................................................................................................................. 34 3.2.6. Tổ chức lớp random theo phân phối mũ – ExpRandom ......................................................... 34 3.2.7. Xây dựng lớp ExpTraffic ........................................................................................................ 35 3.2.8. Sơ đồ hoạt động mô phỏng ..................................................................................................... 36 Chương 4 : Kết quả mô phỏng và nhận xét ............................................................................................. 37 4.1. Đánh giá tool................................................................................................................................... 37 4.1.1. Mô hình M/M/n/n: .................................................................................................................. 37 4.1.2. Mô hình M/M/n/K – Erlang delay-loss................................................................................... 39 4.1.3. Mô hình Binomial: .................................................................................................................. 42 4.1.4. Mô hình Engset: ...................................................................................................................... 43 4.2. Những kết quả mở rộng .................................................................................................................. 44 4.2.1. Mô hình Engset mở rộng: ....................................................................................................... 44 4.2.2. Mô hình Palm’s Machine repair: ............................................................................................ 45 4.2.3. Mô hình Palm’s machine repair mở rộng: .............................................................................. 46 4.3. Bài toán ví dụ .................................................................................................................................. 47 Chương 5 : Kết luận................................................................................................................................. 50 Phụ lục A: Hướng dẫn cài đặt NS2 Phụ lục B: Cài đặt và thiết lập mô phỏng Phụ lục C: Code Tài liệu tham khảo

Trang i

Mục lục hình Hình 2-1: Carried traffic (= số lượng kênh bận) được xác định như một hàm n(t) theo thời gian. ....3 Hình 2-2: Sơ đồ chuyển trạng thái của hệ thống với ...........................................................................8 Hình 2-3: Mô hình mô phỏng hệ thống M/M/n/n ................................................................................9 Hình 2-4: Sơ đồ phát yêu cầu của customers.....................................................................................10 Hình 2-5: Sơ đồ hoạt động của hệ thống với 2 server........................................................................10 Hình 2-6: Sơ đồ chuyển trạng thái của mô hình M/M/n/n .................................................................10 Hình 2-7: Tương quan giữa Offered traffic (A) , xác suất blocking (En(A) = B) và số server .........12 Hình 2-8: Mô hình mô phỏng hệ thống M/M/n/K .............................................................................14 Hình 2-9: Mô hình hoạt động của hệ thống (M/M/2/4). ....................................................................15 Hình 2-10: Sơ đồ chuyển trạng thái của mô hình M/M/n/K ..............................................................15 Hình 2-11: Mô hình mô phỏng hệ thống M/M/N/N/N ......................................................................17 Hình 2-12: Biểu đồ phát yêu cầu của một customer bất kỳ. ..............................................................17 Hình 2-13: Sơ đồ chuyển trạng thái của mô hình M/M/N/N/N, ........................................................18 Hình 2-14: Mô hình mô phỏng hệ thống M/M/n/n/N ........................................................................19 Hình 2-15: Sơ đồ hoạt động tại customer ứng với mô hình M/M/n/n/N ...........................................19 Hình 2-16: Sơ đồ chuyển trạng thái mô hình M/M/n/n/N .................................................................19 Hình 2-17: Mô hình Palm’s Machine Repair.....................................................................................21 Hình 2-18: Sơ đồ hoạt động xét trên một terminal ............................................................................21 Hình 2-19: Sơ đồ chuyển trạng thái của hê thống hàng đợi Palm’s Machine repair .........................22 Hình 2-20: Sơ đồ chuyển trạng thái với N terminal và n server (computer) .....................................22 Hình 3-1: Kiến trúc chung của NS.....................................................................................................23 Hình 3-2: Minh họa cấu trúc node unicast và node multucast...........................................................24 Hình 3-3: Cấu trúc node unicast ........................................................................................................25 Hình 3-4: Cấu trúc một link bao gồm các thành phần .......................................................................26 Hình 3-5: tiến trình hoạt động của một link.......................................................................................26 Hình 3-6: Trình tự các bước thiết lập switch và bắt đầu quá trình kết nối giữa 2 node.....................30 Hình 3-7: Quá trình thiết lập input cho switch...................................................................................31 Hình 3-8: . Lưu đồ mô tả hoạt động hệ thống không có queue..........................................................33 Hình 3-9: Lưu đồ mô tả quá trình hoạt động hệ thống có queue (buffer)..........................................33 Hình 3-10: Code hàm next lớp ExpRandom......................................................................................35 Hình 3-11: Mô hình mô phỏng hoạt động ExpTraffic .......................................................................36 Hình 3-12: Mô tả sơ lượt hoạt động của mô phỏng ...........................................................................36 Hình 4-1: Kết quả mô phỏng khi thực hiện demo ứng với bảng kết quả trên....................................38 Hình 4-2: Một số kết quả so sánh blocking giữa thực nghiệm và lý thuyết của mô hình M/M/5/5. .38 Hình 4-3: Kết quả mô phỏng khi thực thi demo ứng với mô hình trên .............................................39 Hình 4-4: Một số kết quả so sánh blocking giữa thực nghiệm và lý thuyết của mô hình M/M/5/10 40 Hình 4-5: Một số kết quả so sánh delay giữa thực nghiệm và lý thuyết của mô hình M/M/5/10......41 Hình 4-6: So sánh thời gian trong queue giữa thực nghiệm và lý thuyết của mô hình M/M/5/10 ....41 Hình 4-7: Kết quả mô phỏng khi thực thi demo ứng với mô hình Binomial.....................................42 Hình 4-8: Kết quả mô phỏng khi thực thi demo ứng với mô hình Engset M/M/5/5/10 ....................43 Hình 4-9 : Kết quả mô phỏng mô hình Engset mở rộng (M/M/5/5/10).............................................45 Trang ii

Hình 4-10: Kết quả thực hiện mô phỏng mô hình Palm’s Machine repair ........................................46 Hình 4-11: Mô phỏng Palm’s machine repair (M/M/5/10/10) mở rộng ............................................47 Hình 4-12: Kết quả mô phỏng được mô tả ở Hình 4-11 ....................................................................47

Mục lục bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng

2-1: Bảng thống kê các tham số của mô hình M/M/n/n: .........................................................13 2-2: Bảng thống kê các tham số của mô hình M/M/n/K: ........................................................16 2-3: Bảng thống kê các tham số của mô hình Binomial:.........................................................19 3-1: So sánh giữa node ban đầu và node mở rộng...................................................................27 4-1: Kết quả mô phỏng M/M/5/5.............................................................................................37 4-2: mô hình M/M/5/10 ...........................................................................................................39 4-3: Kết quả demo mô hình Binomial – M/M/5/5/5................................................................42 4-4: Kết quả demo mô hình Engset – M/M/5/5/10..................................................................43 4-5: bảng thống kê mô phỏng Engset ......................................................................................44 4-6: Bảng thống kê mô phỏng mô hình Palm’s machine repair M/M/5/10/10........................45

Trang iii

Đề tài nghiên cứu khoa học

Chương 1: Giới thiệu đề tài

Chương 1 :Giới thiệu đề tài 1.1. Đặt vấn đề Hiện nay, hàng đợi được ứng dụng khá rộng rãi trong thực tế. Một bài toán trong thực tế đặt ra là phải tính, hay dự đoán được khả năng đáp ứng của một hệ thống với một hàng đợi cụ thể được áp dụng. Về mặt lý thuyết, đã có nhiều nghiên cứu về các mô hình hàng đợi này, cũng như các công thức để tính toán. Song một nhược điểm mà cách tính toán theo lý thuyết mắc phải là phức tạp và gặp rất nhiều khó khăn trong việc áp dụng tính toán vào thực tế. Các mô hình lý thuyết mới chỉ đáp ứng được các mô hình hàng đợi ở dạng đơn giản, trong khi các hàng đợi trên thực tế hoạt động khá phức tạp. Do có, một nhu cầu phát sinh là phải có một công cụ phục vụ cho việc mô phỏng cũng như tính toán trên các mô hình hàng đợi. Từ đó, đề tài được thực hiện nhằm cung cấp một cung công cụ giúp giải quyết bài toán trên cũng như phục vụ cho mục đích nghiên cứu học tập về các mô hình hàng đợi. 1.2. Mục tiêu đề tài Mục tiêu của đề tài là nghiên cứu các mô hình hàng đợi. Đồng thời, bước đầu xây dựng mô phỏng về các mô hình hàng đợi. Trong đó, các mô phỏng phải giải quyết được vấn đề cốt yếu là có khả năng mô phỏng các trường hợp trong hệ thống hàng đợi mà nếu tính toán lý thuyết là quá phức tạp. Hệ thống hàng đợi được nghiên cứu chỉ dừng lại ở mô hình M/M/n/K/N. Để thực hiện mục tiêu đề ra, đề tài đã thực hiện thông qua hai bước, bước một là nghiên cứu lý thuyết và bước hai là áp dụng lý thuyết để xây dựng mô phỏng. Tương ứng, bản báo cáo cũng được trình bày theo trình tự trên với: • Chương 2 trình bày về lý thuyết các mô hình hàng đợi • Chương 3 trình bày tường bước xây dựng mô phỏng • Chương 4 trình bày các kết quả đạt được • Chương 5 kết luận và hướng phát triển của đề tài 1.3. Giới hạn đề tài Nội dung nghiên cứu chỉ dừng lại ở mô hình hàng đợi kinh điển, gặp nhiều trong thực tế là M/M system (M/M/n/N/K) – Markov-Markov system. Trong đó: •

Tiến trình đến: Poison process (xét theo Xi ~ P(λ))

•

Thời gian phục vụ (holding time, service time): tuân theo phân phối hàm số mũ với mật độ μ

•

n: số server phục vụ

Trang 1

Đề tài nghiên cứu khoa học

Chương 1: Giới thiệu đề tài

•

K: dung lượng của hệ thống hay tổng khả năng phục vụ của hệ thống. Bao gồm số Server và số buffer. K>=n

•

N: số khách hàng

•

Các khách hàng luôn “kiên nhẫn”, không có hiện tượng hủy yêu cầu từ phía khách hàng khi chưa được phục vụ xong.

•

Không xãy ra quá trình “cố gắng thử lại” hay “yêu cầu lại” của customers

•

Trong M/M system, buffer (hay queue) được thực hiện ở dạng FIFO (First in fisrt out). Tuy nhiên, hoàn toàn có thể thay thế bằng một dạng khác. Do vấn đề này không thuộc phạm vi đề tài, nên chỉ có một dạng được áp dụng chung cho tất cả các mô phỏng là FIFO.

•

Mô phỏng được xây dựng bằng NS2 (phiên bản 2.29.3) trên Linux nên thừa kế các cơ chế của NS2. Đặc biệt là cơ chế gửi gói của NS2 (mô phỏng được thực hiện ở dạng gửi gói UDP).

Các mô phỏng chỉ mới dừng lại ở việc mô phỏng một mô hình đơn, chưa hình thành việc liên kết các hệ thống với nhau.

Trang 2

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Chương 2 : Lý thuyết hàng đợi 2.1. Lý thuyết tổng quát

2.1.1. Khái niệm traffic và đơn vị của traffic Trong lý thuyết về teletraffic, thường sử dụng khái niệm traffic để biểu thị cho mật độ traffic (traffic intensity) – số traffic mỗi giây. Theo ITU-T, định nghĩa traffic intensity như sau: Mật độ traffic tức thời trong một nguồn tài nguyên chung được tính bằng số tài nguyên bận tại thời điểm. Nguồn tài nguyên dùng chung có thề là các servers, các trung kế. Các thống kê về traffic được tính trong một khoảng thời gian có chù kỳ T cho trước. Khi đó, traffic trung bình được tính bởi: Y (T ) =

T

1 n(t )dt T ∫0

(2.1)

Trong đó, n(t)là số tài nguyên được sử dụng. Trong thực tế, ta thường bắt gặp khái niệm “carried traffic” để phân biệt với “offered traffic” và “lost traffic”: • Carried traffic: là các traffic được đáp ứng (hay “mang” – carried) bởi các servers trong khoảng thời gian T. Trong thực tế, gía trị này thường là giá trị trung bình.

Hình 2-1: Carried traffic (= số lượng kênh bận) được xác định như một hàm n(t) theo thời gian.

• Offerd traffic: Thường xuất hiện trong các mô hình lý thuyết. Đó là các traffic sẽ được đáp ứng (hay “mang” – carried) bởi các server nếu không có một yêu cầu nào bị từ chối do dung lượng hệ thống thiếu – vị dụ số server là hữu hạn. Offered traffic là một số mang Trang 3

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

tính lý thuyết, không thể đo lường được trong thực tế mà chỉ có thể ước lượng offered traffic thông qua carried traffic. Theo lý thuyết, offered traffic được tính bởi 2 tham số o Cường độ yêu cầu trung bình λ xét trong một đơn vị thời gian o Thời gian phục vụ trung bình s Khi đó, offered traffic được tính bởi: A = λ.s • Lost traffic: Sự chênh lệch giữa carried traffic và offered traffic chính là lost traffic. Giá trị này tăng giảm tùy thuộc vào dung lượng của hệ thống. Đơn vị đo lường traffic được sử dụng là Erlang (E) được định bởi CCIF năm 1946. Tổng số traffic được đáp ứng trong khoảng thời gian T được gọi là “traffic volume”, được đo bằng đơn vị Erlang-hour (Eh) hay theo đơn vị Erlang-second (Es) – ISO. 2.1.2. Poison Process • Khái niệm Arrival process: Arrival process, ví dụ như là một cuộc gọi điện thoại đến một tổng đài, được mô tả bằng mô hình toán học dạng stochastic point process. Trong đó, tại một thời điểm, hai arrival có thể được phân biệt với nhau. Mô hình toán cho point process được xây dựng và phát triển bởi Swede Conny Palm trong thập niên 1940. • Point process: Xét point processes đơn (simple point process). Giả sử cuộc gọi thứ i đến tại thời điểm Ti: 0 = T0 < T1 < T2 < … < Ti < Ti+1 < ….

(2.2)

Tổng số cuộc gọi trong khoảng [0, t) là Nt. Với Nt là một số ngẫu nhiên và đồng biến với thời gian t Khoảng thời gian giữa hai tiến trình đến là: Xi = Ti – Ti-1,

i = 1, 2 …

(2.3)

và khoảng thời gian này tuân theo một phân phối nào đó (một giá trị ngẫu nhiên) Như vậy, ta có hai giá trị ngẫu nhiên Nt và Xi. Một tiến trình đến có thể được mô tả bằng một trong hai thuộc tính: o Số lượng Nt (Number representation) : trong khoảng thời gian t (hằng), ta đo số lượng cuộc gọi đến (gía trị đo được gọi là Nt). Ví dụ: xét trong khoảng thời gian 120 giờ, đa đo được có Nt = 200 process (cuộc gọi) o Khoảng thời gian Ti (Interval representation) : số lượng cuộc gọi đến được giữ cố định, và quan sát khoảng giá trị ngẫu nhiên Ti cho tời khi có n cuộc gọi. Ví dụ: ta tiến hành đo và chờ cho đến khi có 200 process (cuộc gọi), thời gian đo được (thời gian chờ cho đến khi có đủ 200 porocess) là 126 giờ. Hai phương thức trên đồng thời cũng là hai cách để đo traffic của một hệ thống (ví dụ tổng đài). Do p{N t < n} = p{Tn ≥ t}, nên cả hai phương thức đo lường này đều cho

Trang 4

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

cùng một kết quả về traffic. Đối với các mô phỏng được thực hiện trong đề tài, phương thức được sử dụng là Number representation do đơn giản và dễ thực hiện. • Đặc điểm point process1 o Tính đồng nhất: bất chấp vị trí trên trục thời gian, xác suất mô tả cho point process là độc lập với thời gian. p{N t1+t 2 − N t1 = k } = p{N t1+t 2+t − N t1+t = k }

(2.4)

o Tính độc lập: Xác suất mà k (k>=0) sự kiện xãy ra trong khoảng [t1, t1+ t2) là độc lập với t1 p{N t 2 − N t1 = k | N t1 − N t 0 } = p{N t 2 − N t1 = k }

(2.5)

o Tiến trình đơn (simple point process): xác xuất mà có đồng thời hai sự kiện trong một thời điểm cho trước là 0 p{N t + Δt − N t ≥ 2} = o(Δt )

(2.6)

• Poison Process Poison process là một dạng phổ biến của point process. Trong đó: o Nếu xét theo Nt : số sự kiện xãy ra trong một khoảng thời gian cố định tuân theo phân phối Poison o Hay, nếu xét theo Xi : khoảng thời gian giữa hai sự kiện liên tiếp tuân theo phân phối hàm số mũ 2.2. Các mô hình hàng đợi 2.2.1. Giới thiệu: Nội dung sẽ xoay quanh dạng mô hình : M/M system (M/M/n/N/K) – Markov-Markov system, trong đó: • Tiến trình đến: Poison process (xét theo Xi ~ P(λ)) • Thời gian phục vụ (holding time, service time): tuân theo phân phối hàm số mũ với mật độ μ • n: số server phục vụ • K: dung lượng của hệ thống hay tổng khả năng phục vụ của hệ thống. Bao gồm số Server và số buffer. K>=n • N: số khách hàng • Các khách hàng luôn “kiên nhẫn”, không có hiện tượng hủy yêu cầu từ phía khách hàng khi chưa được phục vụ xong. • Không xãy ra quá trình “cố gắng thử lại” hay “yêu cầu lại” của customers 1

Tham khảo [1]

Trang 5

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

2.2.2. Phân loại Có thể phân loại theo hai cách: • Theo số khách hàng: o N = ∞ : Số khách hàng rất lớn. Theo qui ước, nếu số khách hàng lớn hơn 20 lần số server, thì xem như vô cùng (∞). Khi đó, các khách hàng được xem như một nguồn (khách hàng lớn), có tiến trình đến và thời gian phục vụ là trung bình của tất cả các khách hàng. Các mô hình thuộc loại này là: M/M/n/n và M/M/n/K o N < ∞: Số khách hàng là hữu hạn, không quá lớn. Do đó, ta có thể khảo sát trên từng khách hàng. Mỗi khách hàng phát “yêu cầu” theo tiến trình Poison và có thời gian phục vụ theo phân phối mũ. Các mô hình thuộc loại này: Binomial, Engset, Palm’s machine repair. • Theo buffer: o Không có buffer – loss system : Hệ thống chỉ bao gồm n server, không có buffer. Do đó, một “yêu cầu” chỉ có thể được xử lý ngay lập tức hoặc bị từ chối. Các mô hình thuộc loại này : M/M/n/n, Binomial, Engset. o Có buffer – delay system: Ngoài n servers, hệ thống còn có một lượng buffer bằng (K-n). Một “yêu cầu” có thể xảy ra ba khả năng: bị từ chối, chờ, hoặc được phục vụ ngay lập tức. Các mô hình thuộc loại này: M/M/n/K, M/M/n/N/N. 2.2.3. Một số mô hình phổ biến • M/M/n/n : Erlang lost o Nguồn phát (số khách hàng) : rất lớn, xem như vô cùng. Trong trường hợp này, ta có thể xem customer như là một nguồn duy nhất. o Số server : n o Buffer (queue): không có o Tiến trình đến: poison process, theo phân phối hàm số mũ, tần số λ o Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ o Hoạt động: khi một yêu cầu đến, nếu còn bất kỳ server trống, nó sẽ được phục vụ, ngược lại, yêu cầu sẽ bị drop (hủy hay từ chối)

Trang 6

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

• M/M/n/K : Erlang lost-delay o Nguồn phát (số khách hàng) : rất lớn, xem như vô cùng o Số server : n o Buffer (queue): hữu hạn. Q = K – n > 0. Cơ chế hoạt động: FIFO. o Tiến trình đến: poison process, theo phân phối hàm số mũ, tần số λ. o Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ o Hoạt động: khi nhận được một yêu cầu, bộ xử lý trung tâm sẽ xem xét và quyết định xử lý yêu cầu: hoặc chuyển cho một server xử lý ngay, hoặc đệm lại trong hàng đợi, hoặc drop nếu không còn server nào rỗi cũng như đã hết chổ trống trong buffer. • M/M/N/N/N : Binomial o Nguồn phát (số khách hàng) : hữu hạn (N) o Số server : N o Buffer (queue): không có o Tiến trình đến: poison process, mỗi nguồn phát yêu cầu theo phân phối hàm số mũ, tần số λ. o Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ o Hoạt động: khi một yêu cầu đến, nếu còn bất kỳ server trống, nó sẽ được phục vụ, ngược lại, yêu cầu sẽ bị drop (hủy hay từ chối) • M/M/n/n/N : Engset o Nguồn phát (số khách hàng) : hữu hạn (N) o Số server : n o Buffer (queue): không có o Tiến trình đến: poison process, mỗi nguồn phát yêu cầu theo phân phối hàm số mũ, tần số λ. o Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ o Hoạt động: khi một yêu cầu đến, nếu còn bất kỳ server trống, nó sẽ được phục vụ, ngược lại, yêu cầu sẽ bị drop (hủy hay từ chối) • M/M/n/N/N : Palm’s Machine repair o Nguồn phát (số khách hàng) : hữu hạn (N) o Số server : n o Buffer (queue): hữu hạn. Q = N – n > 0. Cơ chế hoạt động: FIFO. o Tiến trình đến: poison process, mỗi nguồn phát yêu cầu theo phân phối hàm số mũ, tần số λ. Trang 7

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

o Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ o Hoạt động: khi nhận được một yêu cầu, bộ xử lý trung tâm sẽ xem xét và quyết định xử lý yêu cầu: hoặc chuyển cho một server xử lý ngay, hoặc đệm lại trong hàng đợi, hoặc drop nếu không còn server nào rỗi cũng như đã hết chổ trống trong buffer. 2.2.4. Sơ đồ chuyển trạng thái 2 Tại thời điểm hệ thống đang đáp ứng k yêu cầu, ta nói, hệ thống đang ở trạng thái k. Sơ đồ chuyển hóa trạng thái của hệ thống:

Hình 2-2: Sơ đồ chuyển trạng thái của hệ thống với

Với: Pi : xác suất xảy ra trạng thái i λi : tần số chuyển đổi từ trạng thái i đến i+1 μi : tần số chuyển đổi từ trạng thái i về i-1 Với giả thuyết lượng traffic vào và ra một trạng thái là bằng nhau, ta có phương trình biểu diễn traffic xét tại trạng thái i (phương trình cắt (cut – equation) tại i ):

λ0 .P0 = μ1 P1 λ1 .P1 = μ 2 P2 λ 2 .P2 = μ 3 P3

λ0 P0 μ1 λλ λ P2 = 1 P1 = 0 1 P0 μ2 μ1 μ 2 λ λλ λ P3 = 2 P2 = 0 1 2 P0 μ3 μ1 μ 2 μ 2 P1 =

Tổng quát

λ x −1 .Px −1 = μ z Pz

2

x λ λ x −1 ⇒ Pz = Px −1 = ∏ i +1 P0 i =1 μ μ x −1 i

Tham khảo [1], [2]

Trang 8

(2.7)

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Mặt khác :

⎛ x λi −1 ⎞ P0 ⎟⎟ ⇒ P0 = 1 = ∑ Px = ∑ ⎜⎜ ∏ = 1 i μ x =0 x =0 ⎝ i ⎠ n

n

1 ⎛ x λi −1 ⎞ ⎜⎜ ∏ ⎟⎟ ∑ = 1 i μi ⎠ x =0 ⎝ n

(2.8)

Vậy :

λi −1 i =1 μ i Px = n ⎛ k λi −1 ⎞ ⎜⎜ ∏ ⎟⎟ ∑ k = 0 ⎝ i =1 μ i ⎠ x

∏

(2.9)

Đây là sơ đồ chuyển trạng thái và phương trình cơ bản cho tất cả các mô hình cụ thể. 2.2.5. Mô tả chi tiết các mô hình

2.2.5.1. Mô hình M/M/n/n Mô hình mô phỏng:

Hình 2-3: Mô hình mô phỏng hệ thống M/M/n/n

Với: Nguồn phát (số khách hàng) : rất lớn, xem như vô cùng. Trong trường hợp này, ta có thể xem customer như là một nguồn duy nhất. Số server : n Buffer (queue): không có Tiến trình đến: poison process, theo phân phối hàm số mũ, tần số λ.

Trang 9

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Hình 2-4: Sơ đồ phát yêu cầu của customers

Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ

Hình 2-5: Sơ đồ hoạt động của hệ thống với 2 server.

Hình 2-5 là ví dụ một hệ thống với 2 server. Yêu cầu 3 bị blocking do cả 2 server tại thời điểm mà yêu cầu 3 được phát đều bận. Sơ đồ chuyển trạng thái:

Hình 2-6: Sơ đồ chuyển trạng thái của mô hình M/M/n/n

Gọi A = λ/μ , A được gọi là offered traffic – số “yêu cầu” trung bình trong một đơn vị thời gian phục vụ.

Trang 10

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Sử dụng cut – equation: i A −1 ⎧ n Ai ⎫ p (0) = ⎨∑ ⎬ ⇒ p (i ) = n i! j A ⎩ j = 0 j! ⎭ ∑ j = 0 j!

,0≤i ≤ n (2.10)

(Erlang first formular) Xác suất có n kênh bận:

E n ( A) = p (n)

(2.11)

Một “yêu cầu” (cuộc gọi) bị từ chối khi tất cả các server đều đang hoạt động, hay hệ thống đang ở trạng thái n. Xác suất một cuộc gọi bị từ chối (blocking) bằng xác suất mà hệ thống đang ở trạng thái n:

B = p ( n) = E n ( A)

(2.12)

Trong thực tế tính toán, việc tính toán trực tiếp bằng công thức trên sẽ rất khó khăn do dễ làm tràn bộ nhớ máy tính do phép tính mũ và giai thừa. Để thuận tiện cho việc tính toán En(A) được sử dụng dưới dạng truy hồi:

Ex ( A) =

A.Ex −1 ( A) x + A.Ex −1 ( A)

E 0 ( A) = 1

(2.13)

Vậy:

B = En ( A) =

A.En −1 ( A) n + A.En −1 ( A)

(2.14)

Trang 11

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Chứng minh công thức truy hồi:

Ax x Ax A x! E x = x x! j = A x ⎛ x −1 A j A x ⎞ ⎜∑ ⎟ + ∑ ⎜ j ! A ⎝ j = 0 j! x! ⎟⎠ j =0 A x −1 A x −1 A ( x − 1)! ( x − 1)! (đpcm) = x −1 j = x −1 j x −1 x −1 x A A A A x∑ + +A ∑ A j = 0 j! ( x − 1)! ( x − 1)! j = 0 j!

Hình 2-7: Tương quan giữa Offered traffic (A) , xác suất blocking (En(A) = B) và số server3

3

Hình được trích từ tài liệu [1]

Trang 12

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Bảng 2-1: Bảng thống kê các tham số của mô hình M/M/n/n:

Các thông số input Các thông số output Tần số phát λ Xác xuất Blocking Thời gian phục vụ μ A.Ex −1 ( A) B = Ex ( A) = Offer traffic A = λ/μ x + A.Ex −1 ( A) Số server (hay channel) n

E 0 ( A) = 1

Ví dụ: Một hệ thống với số server (channel) n = 6, tần số phát yêu cầu λ = 2 yêu cầu mỗi đơn vị thời gian. Do đó, offered traffic A = 2 erlang. Tính xác xuất blocking. Theo công thức tổng quát:

An B = p ( n) = En ( A) = p ( n) = n n! j = A ∑ j =0 j!

26 6! = 0.0121 6 2j ∑ j =0 j!

Theo công thức truy hồi

B = Ex ( A) =

A.Ex −1 ( A) x + A.Ex −1 ( A)

E 0 ( A) = 1

Ta có: E0 = 1 E1 =

E3 =

E5 =

E6 =

2 ×1 2 = 1 + 2 ×1 3

2× 2

5 = 4 19 3+ 2× 2 5

E2 =

E4 =

2× 2

3 =2 5 2 + 2× 2 3 2× 4

19 = 2 21 4 + 2× 4 19

2× 2

21 = 4 109 5 + 2× 2 21 2× 4

109 = 4 ≈ 0.0121 ⇒ B = 0.0121 331 6 + 2× 4 109

Trang 13

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

2.2.5.2. Mô hình M/M/n/K Mô hình mô phỏng:

Hình 2-8: Mô hình mô phỏng hệ thống M/M/n/K

Mô tả: • Nguồn phát (số khách hàng) : rất lớn, xem như vô cùng • Số server : n • Buffer (queue): hữu hạn. Q = K – n > 0. Cơ chế hoạt động: FIFO • Tiến trình đến: poison process, theo phân phối hàm số mũ, tần số λ. • Thời gian phục vụ: theo phân phối mũ, giá trị trung bình tm = 1/μ Khác với mô hình M/M/n/n, đây là mô hình đặc trưng của mô hình có buffer. Khi một yêu cầu đến, nó chỉ bị drop khi và chỉ khi hệ thống hết khả năng phục vụ, hay nói cách khác, tất cả các server đều đã bận và không còn chỗ trống nào trong buffer. Như vậy, với dạng mô hình này sẽ xãy ra hiện tượng delay. Do đó, ngoài thông số blocking, cũng cần phải lưu ý đến 2 thông số khá quan trọng là xác suất một yêu cầu phải chờ và thời gian chờ trung bình. Hai thông số này cũng ảnh hưởng lớn đến chất lượng dịch vụ. Trong các mô hình đang xét, các customers được xem là rất kiên nhẫn, và sẽ không có việc thoát khỏi hàng đợi trong khi đang chờ phục vụ. Để tránh một yêu cầu sẽ bị chờ mãi trong queue, trong khi đó một yêu cầu khác vừa mới đến lại được phục vụ ngay do tại thời điểm mà yêu cầu đó vừa vào thì co ngay một server trống, bọ xử lý sẽ ưu tiên giải quyết các yêu cầu chờ trong queue trước. Để đơn giản, tất cả các yêu cầu đều được đưa vào queue trước khi được xử lý. Nếu có server trống, một yêu cầu sẽ ngay lập tức được chuyển từ queue vào server để xử lý (nếu có).

Trang 14

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Hình 2-9: Mô hình hoạt động của hệ thống (M/M/2/4).

Hình 2-9 làm rõ hơn về hoạt động của mô hình (ví dụ M/M/2/4). Customers phát với tần số 1/ λ, độc lập với thời gian xử lý 1/ μ. Các yêu cầu đến hoặc xử lý ngay (1,2,9) hoặc đệm lại trong queue (3,4,5,6,8) hoặc drop (7). Sơ đồ chuyển trạng thái

Hình 2-10: Sơ đồ chuyển trạng thái của mô hình M/M/n/K

Sử dụng phương trình cắt, cân bằng:

⎡ n−1 A x K −n ⎛ A ⎞ q An ⎤ + ∑⎜ ⎟ 1 = ∑ Px = P0 ⎢∑ ⎥ x n n ! ! ⎝ ⎠ q =0 x =0 ⎢⎣ x=0 ⎥⎦ K

−1

K − n +1 ⎤ ⎡ ⎛ A⎞ 1 − −1 ⎜ ⎟ ⎥ ⎢ n−1 x n n x n −1 ⎡ ⎤ A A A A n ⎝ ⎠ ⎥ = (K − n − 1)⎥ + ⇒ P0 = ⎢∑ + ⎢∑ ⎥ ⎢ x=0 x! n! A x ! n ! = 0 x ⎣ ⎦ A= n 1− ⎥ ⎢ n ⎦⎥ ⎣⎢

Trang 15

(2.15)

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

⎧ Ax Ax ⎪ x! x! ⎪ Px=0,..,n−1 = = n−1 x K −n+1 A An ⎪ ⎛ A⎞ (K − n − 1) + ∑ ⎟ ⎪ x n 1− ⎜ n−1 ! ! x n A A x=0 ⎝n⎠ A=n ⎪ + ∑ A ⎪ n! x=0 x! 1 − ⎪ n ⇒⎨ q n ⎛ A⎞ A Ax ⎪ ⎜ ⎟ (2.16) ⎪ ⎝ n ⎠ n! n! P = = ⎪ x=n,...K K −n+1 n−1 Ai An ⎛ A⎞ ⎪ q=0,...,K −n (K − n − 1) + ∑ ⎟ i n 1− ⎜ n−1 ⎪ ! ! i n A A i =0 ⎝n⎠ A=n + ⎪ ∑ A n! i =0 i! ⎪ 1− n ⎩

Xác xuất một yêu cầu phải chờ (delay): 4

Pdelay =

K − n −1

∑P q =0

x=n+ q

(2.17)

Xác xuất một yêu cầu bị từ chối (blocking):

Ploss = PK

(2.18)

Bảng 2-2: Bảng thống kê các tham số của mô hình M/M/n/K:

Các thông số input Tần số phát λ Thời gian phục vụ μ Offer traffic A = λ/μ Số server n Khả năng đáp ứng hệ thống K (K = n+q , với q là kích thước buffer)

4

Các thông số output Xác xuất Blocking

Tham khảo [2]

Trang 16

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

2.2.5.3. Mô hình Binomial Mô hình mô phỏng:

Hình 2-11: Mô hình mô phỏng hệ thống M/M/N/N/N

Mô tả: • Có N nguồn phát – khách hàng. Mỗi nguồn có hai trạng thái: o idle: khoảng thời gian rỗi – là khoảng thời gian customer không hoạt động (không yêu cầu cũng như không đang được phục vụ). Sau khoảng thời gian này, customer sẽ phát một yêu cầu. Khoảng thời gian này tuân theo phân phối mũ với giá trị trung bình là 1/λ o busy: là khoảng thời gian mà customer đang được phục vụ bởi hệ thống. Khoảng thời gian này tuân theo phân phối mũ với giá trị trung bình là 1/μ. Khi một yêu cầu được phát, trạng thái customer trở thành busy trong khoảng thời gian 1/μ (trong khoảng thời gian này, customer sẽ không phát yêu cầu). Sau đó, trạng thái customer trở về trạng thái Idle và sẵn sàng phát yêu cầu trong khoảng thời gian ngẫu nhiên 1/λ (Hình 2-12)

Hình 2-12: Biểu đồ phát yêu cầu của một customer bất kỳ.

• Trong khoảng thời gian đang được phục vụ, customer(s) sẽ không thể gửi yêu cầu được. • Để để kiểm chứng lý thuyết, customers có cùng λ và chỉ có một giá trị trung bình μ cho tất cả các customers. Song trên thực tế, các giá trị này khác nhau. Trong mô phỏng có hổ trợ cả trường hợp này, tuy nhiên không có kiểm chứng bằng lý thuyết. Trang 17

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

• Có N server • Không có buffer

Hình 2-13: Sơ đồ chuyển trạng thái của mô hình M/M/N/N/N,

Sử dụng cut-equation, cân bằng ta có: 5 p(1) =

Nλ

⎛ N ⎞⎛ λ ⎞ p(0 ) = p (0)⎜⎜ ⎟⎟⎜⎜ ⎟⎟ μ ⎝ 1 ⎠⎝ μ ⎠

1

⎛ N ⎞⎛ λ ⎞ ( N − 1)λ p(2 ) = p(1) = p (0)⎜⎜ ⎟⎟⎜⎜ ⎟⎟ 2μ ⎝ 2 ⎠⎝ μ ⎠

2

...

(N − i − 1)λ p (i ) = iμ

⎛ N ⎞⎛ λ ⎞ p (i − 1) = p (0)⎜⎜ ⎟⎟⎜⎜ ⎟⎟ ⎝ i ⎠⎝ μ ⎠

i

... p( N ) =

⎛ N ⎞⎛ λ ⎞ λ p ( N − 1) = p (0)⎜⎜ ⎟⎟⎜⎜ ⎟⎟ Nμ ⎝ N ⎠⎝ μ ⎠

N

Như vậy, N ⎧⎪ ⎛ N ⎞⎛ λ ⎞ ⎛ N ⎞⎛ λ ⎞ 2 ⎛ N ⎞⎛ λ ⎞ ⎫⎪ 1 = p (0)⎨1 + ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ + ... + ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ ⎬ ⎪⎩ ⎝ 1 ⎠⎝ μ ⎠ ⎝ 2 ⎠⎝ μ ⎠ ⎝ N ⎠⎝ μ ⎠ ⎪⎭

p (0) = (1 + a ) − N

Gọi α =

,a =

(2.19)

λ μ

a , 1+ a

⎛N⎞ ⎝i⎠

Ta có: p(i ) = ⎜⎜ ⎟⎟α i (1 − α ) N −i

, i = 0,1,...., N

,0 ≤ N ≤ n

(2.20)

Xác suất có n server đều bận : E=0

,N < n

E = p ( n) = p ( N ) = α N

, Binomial N = n

(2.21)

Xác suất có yêu cầu bị từ chối (blocking):

5

Tham khảo [1]

Trang 18

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

B=0

(2.22)

Bảng 2-3: Bảng thống kê các tham số của mô hình Binomial:

Các thông số input Tần số phát trên mỗi nguồn rỗi λ Thời gian phục vụ trung bình μ Offered traffic trên mỗi nguồn rỗi a = λ/μ Số server, số customers, và khả năng đáp ứng hệ thống: N

Các thông số output Xác xuất Blocking = 0 Offered traffic trên mỗi nguồn: α Tổng số offered traffic A = N.α

2.2.5.4. Mô hình Engset (M/M/n/n/N) Mô hình mô phỏng

Hình 2-14: Mô hình mô phỏng hệ thống M/M/n/n/N

Mô tả: mô hình Engset tương tự như mô hình Binonial, chỉ có điểm khác là số Server nhỏ hơn số customers. Do đó, sẽ có khả năng xãy ra hiện tượng blocking. Sơ đồ hoạt động tại một customer 6

Hình 2-15: Sơ đồ hoạt động tại customer ứng với mô hình M/M/n/n/N

Sơ đồ chuyển trạng thái

Hình 2-16: Sơ đồ chuyển trạng thái mô hình M/M/n/n/N 6

Tham khảo [1]

Trang 19

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Sử dụng phương trình cắt, và cân bằng, ta có: ⎛N⎞ i N −i ⎜⎜ ⎟⎟.α .(1 − α ) i p (i ) = n⎝ ⎠ , ⎛N⎞ j N− j ⎜⎜ ⎟⎟.α .(1 − α ) ∑ j =0 ⎝ j ⎠

0≤i≤n

(2.23)

,N≥n

(2.24)

Xác xuất cả n server đều bận: ⎛N⎞ n ⎜⎜ ⎟⎟.a n E n , N (a ) = p (n) = n⎝ ⎠ ⎛N⎞ j ⎜⎜ ⎟⎟a ∑ j =0 ⎝ j ⎠

Xác xuất một yêu cầu bị từ chối (Blocking) ⎛ N − 1⎞ n ⎜⎜ ⎟.a n ⎟⎠ p (n).( N − n).λ ⎝ = n Bn , N ( a ) = n = E n , N −1 (a ) ⎛ N − 1⎞ j p ( j ).( N − j ).λ ∑ ⎜⎜ ⎟.a ∑ j ⎟⎠ j =0 j =0 ⎝ Trong thực tế, En,N-1 được tính ở dạng truy hồi 7

E x , N (a) =

( N − x + 1)a.E x −1, N (a ) x + ( N − x + 1)a.E x −1, N (a )

, N ≥ n (2.25)

, E 0, N (a ) = 1 (2.26)

2.2.5.5. Mô hình Palm’s machine repair (PMR) Ở mô hình PMR, có thể hình dung là một hệ thống mà có sự phân chia thời gian phục vụ dịch vụ cho một nhóm lớn các customer sử dụng terminal của mình kết nới vào một mainframe. Mỗi cá nhân luôn cảm thấy mình là user duy nhất của máy tính. Mỗi user sẽ chuyển qua lại giữa 2 trạng thái trong suốt thời gian hoạt động: • User suy nghĩ (đang làm việc), hoặc • User chờ đáp ứng từ máy tính

7

Tham khảo [1]

Trang 20

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

Hình 2-17: Mô hình Palm’s Machine Repair

Hình 2-17 mô tả một hệ thống máy tính với N thiết bị đầu cuối (terminal) tương ứng một hệ thống hàng đợi với một lượng nguồn phát cố định. Khoảng thời gian mà user suy nghĩ là một số ngẫu nhiên Tt với giá trị trung bình mt. Khoảng thời gian, khi mà user đang giờ đáp ứng từ computer, được gọi là thời gian đáp ứng R, bao gồm khoảng thời gian Tw (giá trị trung bình mw) mà một công việc đang chờ để truy cập vào máy tính, và thời gian phục vụ dịch vụ của chính nó Ts (giá trị trung bình là ms). Tt + R được gọi là thời gian lưu thông (circulation time). Vào thời điểm kết thúc khoảng thời gian này, terminal trở về trạng thái trước đó. Một terminal đơn có ba trạng thái, hoặc user đang làm việc trên terminal (thinking), hoặc là đang chờ đáp ứng từ máy tính. Khoảng thời gian chờ đáp ứng được chia làm hai khoảng: khoảng thời gian chờ được đáp ứng (waiting) và khoảng thời gian thực thi (service) (Hình 218)

Hình 2-18: Sơ đồ hoạt động xét trên một terminal

Xét hệ thống chỉ gồm một server và N terminals. Khoảng thời gian “suy nghĩ” (thinking time) trên mỗi thiết bị là một ngẫu nhiên theo phân phối hàm số mũ với cường độ λ = 1/mt, và thời gian phục vụ (service time) ms tại máy tính cũng tuân theo phấn phối mũ với cường độ μ = 1/ms. Khi có một hàng đợi trên máy tính, terminal phải chờ. Trong khoảng thời gian Trang 21

Đề tài nghiên cứu khoa học

Chương 2: Lý thuyết hàng đợi

được phục vụ hay chờ, tiến trình đến trên terminal là 0 (hay nói cách khác, trong khoảng thời gian này, terminal không phát yêu cầu). Xét sơ đồ chuyển trạng thái:

Hình 2-19: Sơ đồ chuyển trạng thái của hê thống hàng đợi Palm’s Machine repair

Với trạng thái thứ i là số lượng terminal đang được phục vụ hay chờ trong hệ thống. (N – i) là số số terminal đang “suy nghĩ” (thinking). Sử dụng phương trình cắt, ta có:

(N − i )λ. p(i) = μ. p(i + 1)

, i = 0,1,..., N

(2.27)

Gọi ρ = μ / λ p( N − i) =

ρ

ρi i

i!

p( N ) =

i! N

∑ j =0

ρj

, i = 0,1,...., N

(2.28)

j!

Tham số ρ được gọi là tỷ lệ dịch vụ (service ratio). Nó tương tự như như offered traffic A trong Erlang-B. 8 Với n server, sơ đồ chuyển trạng thái được mở rộng như sau:

Hình 2-20: Sơ đồ chuyển trạng thái với N terminal và n server (computer)

8

Tham khảo [1]

Trang 22

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Chương 3 :Xây dựng mô phỏng 3.1. Bộ mô phỏng NS2 3.1.1. Giới thiệu NS-2 là một chương trình mô phỏng mạng điều khiển sự kiện riêng lẽ hướng đối tượng dựa trên hai ngôn ngữ : mô phỏng hướng đối tượng viết bằng C++ và trình biên dịch Otcl. Bốn lợi ích lớn nhất phải kể đến khi sử dụng NS-2 là: •

Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại

•

Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng

•

Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế

•

Khả năng mô phỏng được nhiều mô hình mạng khác nhau

NS-2 thực thi các giao thức mạng như Giao thức điều khiển truyền tải (TCP) và giao thức gói người dùng (UDP)… Để sử dụng NS-2 , người dùng có thể lập trình bằng ngôn ngữ kịch bản Tcl , kịch bản Tcl thực hiện những việc sau : •

Khởi tạo bộ lập lịch sự kiện

•

Thiết lập mô hình mạng dùng các đối tượng thành phần mạng

•

Báo cho nguồn traffic khi nào truyền và ngưng truyền packet trong bộ lập lịch sự kiện

3.1.2. Kiến trúc NS2 Người sử dụng có thể tưởng tượng mình đang đứng ở góc trái dưới , thiết kế và chạy mô phỏng trong Tcl , Tcl dùng các đối tượng mô phỏng trong Otcl, các đối tượng bộ lập lịch sự kiện thực thi bằng C++ và sẵn có cho Otcl qua một liên kết Otcl , liên kết Otcl này được thưc thi trong TclCL . Tất cả làm nên NS.

Hình 3-1: Kiến trúc chung của NS

Trang 23

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Các tính năng của NS-2 :9 • Các kỹ thuật hàng đợi Router như Droptail , RED , CBQ • Multicasting • Mô phỏng mạng không dây • Các agent truyền tải UDP , TCP • Định tuyến • Luồng Packet • Mô hình mạng • Các ứng dụng : Telnet , ping ,FTP • Các packet tracing trên tất cả các link và trên các link xác định

3.1.2.1. Node Node là đối tượng ghép từ đối tượng entry và classifiers . Trong Ns có hai loại node: unicast và multicast . Node unicast có một bộ định địa chỉ (address classifier) làm nhiệm vụ định tuyến unicast và một port classifier ,node multicast có thêm một bộ phân loại (classifier) làm nhiệm vụ phân loại các packet multicast với packet unicast .

Hình 3-2: Minh họa cấu trúc node unicast và node multucast

Một node tiêu biểu chứa các components sau : •

Địa chỉ ( khởi tạo bằng 0 và tăng lên 1 khi một node được tạo)

•

Một danh sách các neighbors

•

Một danh sách các agents

•

Định danh loại node

•

Một module định tuyến

Mặc định node trong ns được khởi tạo cho mô phỏng unicast, để có thể mô phỏng multicast, chương trình mô phỏng nên tạo ra tùy chọn “multicast on”.

9

Tham khảo [5]

Trang 24

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-3: Cấu trúc node unicast

3.1.2.2. Link Link là thành phần thứ hai để định ra một topology, là một đối tượng ghép trong NS. Một link đơn giản là sự kết nối giữa 2 node với nhau , và được thể hiện bằng các thuộc tính sau : •

Head : Đầu vào của một link , nó chỉ vào đối tượng đầu tiên trong một link.Ví dụ : Head là đối tựơng báo hiệu bắt đầu của một link và kết nối giữa một node với đối tượng queue của link .

•

Queue : một link đơn giản thường có một queue trên một link , các loại link phức tạp thì có nhiều queue trên một link . Ví dụ : Khi một gói dữ liệu truyền từ node 1 sang node 2 thì đầu tiên nó sẽ được đưa vào đối tượng queue của link trước khi đến node 2 nếu queue rỗng hay còn chỗ trống thì sẽ được lấy ra xử lý tíêp, còn nếu queue đầy thì gói sẽ bị drop

•

Link : Một tham chiếu đến yếu tố mà nó thật sự làm mô hình cho link , thể hiện đặc tính delay và bandwidth của link

•

TTL : thể hiện thời gian tồn tại của mỗi gói dữ liệu

•

Drophead : Tham chiếu đến một đối tượng là tiêu đề của link để xử lý link drop

Trang 25

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-4: Cấu trúc một link bao gồm các thành phần

Khi user tạo link bằng cách dùng hàm thành viên simplex-link của đối tượng Simulator thì sẽ có 2 simplex link 2 chiều được tạo ra . Một hàng đợi đầu ra của node được thực thi như một phần tử của đối tượng simplex link, các packet ra khỏi hàng đợi sẽ được chuyển đến đối tượng delay để thực thi trì hoãn liên kết. Các packet bị drop khỏi hàng đợi sẽ đựơc gửi đến Agent/Null và bị hủy tại đây , cuối cùng trường TTL tính TTL cho từng giá trị và cập nhật giá trị TTL mới .

Hình 3-5: tiến trình hoạt động của một link

Khi một gói muốn gửi từ một node này sang node khác, nó phải thông qua 1 link , một hàng đợi đầu ra của node được thực thi như một đối tượng của link , các packet ra khỏi hàng đợi sẽ được gửi đến đối tượng delay để thực thi trì hoãn , các packet bị drop sẽ được gửi tới Agent/Null và bị hủy tại đây , cuối cùng được đưa đến trường TTL để tính TTL (thời gian sống) cho từng packet (hình 3-5)

Trang 26

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

3.1.2.3. UDP Agent Hai lớp Agent và Application sẽ tạo nên traffic trong NS-2 . Mỗi node trong mạng muốn gửi và nhận traffic thì phải có Agent gắn vào. Một UDP agent chấp nhận gói dữ liệu có kích thước khác nhau từ một ứng dụng và phân đoạn dữ liệu nếu cần , kích thước lớn nhất mặc định của 1 gói UDP là 1000 byte, mỗi Agent có một tên là định danh duy nhất cho Agent đó . Bảng 3-1: So sánh giữa node ban đầu và node mở rộng

Node ban đầu Node ban đầu chỉ có chức năng xử lý packet bình thường ,không có một hàng đợi trong node để giải quyết nhiều gói gửi đến , node này không tích hợp các chức năng để giải quyết các vấn đề về xử lý 1 gói từ lúc vào node cho đến khi ra khỏi node, không thể tạo số random ….

Node mở rộng Để đáp ứng các yêu cầu như bên ta bổ sung thêm một số chức năng mới và gọi là node Switch : Xây dựng một Agent để hỗ trợ cho node nhằm xử lý các yêu cầu đối với 1 node như : nhận và xử lý gói Sử dụng bộ random để sinh số theo phân phối mũ Xây dựng một hàng đợi trong node theo kiểu FIFO Xây dựng một agent phục vụ cho việc gửi yêu cầu từ các customers ExpArrival

Trang 27

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

3.2. Xây dựng mô phỏng cụ thể 3.2.1. Hướng giải quyết: Hướng giải quyết là đưa ra một mô hình node mở rộng phục vụ cho mô phỏng Mô hình chung :

Mô hình gồm có: •

N nguồn phát: Nếu là mô phỏng cho M/M/n/n hay M/M/n/K thì N = 1. Mỗi nguồn phát tuân theo phân phối mũ với cường độ λ

•

Node Switch: là một node của NS2 song được mở rộng để đóng vai trò như một hệ thống, hoạt động theo một mô hình nhất định.

•

Output: là một tập gồm N (M
Như vậy, cần phải: •

Xây dựng một agent hổ trợ cho switch, làm nhiệm vụ nhận các yêu cầu, xử lý, phân phối đến các server hay từ chối (drop) – SWA (switch agent).

•

Xây dựng một hàng đợi cho switch. Hiện tại, hàng đợi được xây dựng là FIFO. Tương lai vẫn có thể mở rộng nhiều loại khác (không nằm trong phạm vi đề tài).

•

Sử dụng bộ random của NS2 để sinh số random theo phân phối mũ.

•

Xây dựng một agent phục vụ cho việc gửi yêu cầu từ các customers - ExpArrival

3.2.2. Xây dựng node SWITCH Không như một node thông thường của NS2, SWITCH đóng vai trò như một bộ tập trung, đóng vai trò như một trạm dịch vụ, tuân theo một trong các mô hình đã đề cập ở trên. Các loại SWITCH mô phỏng: • MMnn : M/M/n/n

MMnK: M/M/n/K

•

MMNNN : Binomial

MMnnN : Engset

•

MMnNN: Palm’s machine repair

Trang 28

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Như vậy, thuộc tính cần thêm đầu tiên cho node phải là type (loại switch). Đối với các mô hình cần hàng đợi, switch cần phải có một hàng đợi, như vậy thuộc tính thứ hai cần phải thêm là queue. Node cần một agent để quản lý việc nhận các yêu cầu từ customer, xử lý yêu cầu. Vậy cần kết nối một agent (swa) vào node. Để quản lý các server, hiện tại mô phỏng sử dụng agent UDP. Vậy cần có n agent UDP được kết nối với switch. Tùy theo loại switch mà ta có những cách khởi tạo khác nhau. Chương trình mô phỏng dùng cách xây dựng thêm các tập hàm cho lớp Simulator để phục vụ cho SWITCH. Các hàm sử dụng phục vụ cho SWITCH: •

Khởi tạo switch: Simulator instproc BuildSwitch {args} o Đối với mô hình M/M/n/n:

BuildSwitch MMnn <Server> [<customers = 1>] Mặc định, customers được qui ước là 1 dành cho loại này, tuy nhiên, vẫn có thể cấu hình với n customers, mà mỗi customer là một nguồn lớn. o Đối với mô hình M/M/n/K:

BuildSwitch MMnK <Server> [<customers = 1>] Tương tự như MMnn, mặc định customers = 1 o Đối với mô hình M/M/N/N/N – Binomial

BuildSwitch MMNNN <Server> Đối với mô hình này, số Server bằng số customers, và queuesize bằng 0. Do đó, chỉ cần khai báo số Server o Đối với mô hình M/M/n/n/N – Engset

BuildSwitch MMnnN <server> <customers> Do queue-size mặc định bằng 0. Ta chỉ cần khai báo server và customers.

Trang 29

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-6: Trình tự các bước thiết lập switch và bắt đầu quá trình kết nối giữa 2 node

•

Thiết lập input cho switch: Simulator instproc SetSwitchInput {sw itemlist} Trong đó, sw là switch. Itemlist là danh sách các item đóng vai trò input cho switch. Cấu trúc của item: {node traffic_type mean_arrival hold} node: một node của NS2, dùng làm nguồn phát traffic_type : cho biết cách mà nguồn sẽ phát, đồng thời nó cũng cho biết kiểu customer. 0: nguồn lớn, 1: nguồn riêng lẽ phát yêu cầu theo mô hình Binomio (2 trạng thái) mean_arrival: có giá trị là 1/μ. Đó ứng với giá trị trung bình cuả thời gian giữa hai lần phát yêu cầu (nguồn lớn), hay khoảng thời gian idle trung bình. Hold: một biến có kiểu là một bộ sinh giá trị trung bình theo phân phối mũ (sẽ đề cập sau). Tuy nhiên, ta có thể mở rộng cho các kiểu khác nếu có yêu cầu, miễn sao tuân theo một cấu trúc cho trước. Hold đóng vai trò sinh giá trị ngẫu nhiên cho thời gian phục vụ. Trong mô hình thực tiễn, Hold phải thuộc về node switch. Tuy vậy, khi cần mở rộng với mỗi nguồn phát có một thời gian phục vụ khác nhau trên cùng một switch, thì hold được đặt rời cho ta cách quản lý đơn giản. Số lượng item trong itemlist phải bằng với số lượng customers được khai báo tri khởi tạo switch. Tất cả các thuộc tính của item nhằm cung cấp dữ liệu để thiết lập agent exparrival cho nguồn phát – agent này điều khiển việc giao tiếp giữa nguồn phát (customer) với switch (sẽ được trình bày ở phần sau). Ngoài việc thiết lập các thuộc tính cần thiết cho customer, hàm thực hiện việc kết nối các node customers với switch. Cụ thể:

Trang 30

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-7: Quá trình thiết lập input cho switch

•

Thiết lập output: Phần này chỉ phục vụ cho việc mở rộng mô hình sau này, không có ý nghĩa trong mô phỏng hiện tại.

3.2.3. Thiết kế lớp SWA Lớp SWA là một Agent thừa kế từ Agent/UDP. SWA cung cấp các cơ chế nhận, liên kết agent phục vụ cho output và xử lý các yêu cầu … Các thuộc tính mở rộng cho SWA: •

received: đếm số yêu cầu nhận được

•

dropped: đếm số yêu cầu bị từ chối

•

delayed: đếm số yêu cầu phải chờ trong queue

•

server : số server mà agent này quản lý, tương tự với số server mà node có.

•

time_out_ {} : kiểu list, cho biết thông tin về thời điểm server [i] rỗi gần nhất. Như vậy, giả sử tại thời điểm t kênh i bắt đầu phục vụ, và phải phục vụ trong khoảng thời gian h, thì time_out [i] được thiết lập bằng (t + h). Một server i được xem là rỗi tại thời điểm t khi t nhỏ hơn hoặc bằng time_out_ [i].

•

link_up_ {}: kiểu list, chứa thông tin về việc kết nối ra output của switch. thông thường, link_up_[i] được đặt bằng 0. Nếu có kết nối ra ngoài tại server [i] thì link_up_[i] được đặt bằng 1. Khi link_up_[i] bằng 1, tại thời điểm time_out_[i] – thời điểm mà server[i] phục vụ (hay xử lý) xong yêu cầu agent UDP[i] của switch – đóng vai trò như server, đã trình bày ở trên – sẽ phát gói (yêu cầu). Nguyên nhân phải sử dụng biến link_up_ là để đảm bảo có sự kết nối giữa switch và bên ngoài. Nếu kết nối chưa được lập, việc gửi gói (yêu cầu) của switch ra ngoài sẽ gây ra lỗi hệ thống .

Trang 31

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Việc thiết lập link_up_ được thực hiện trong khi thiết lập output cho switch bằng hàm SWA instproc up_link {index} • node_ : đây là thuộc tính gốc của Agent/UDP, chứa node mà agent đó thuộc về. Agent SWA thông qua biến này để kiểm soát toàn bộ switch. Một đặc điểm của Agent/UDP hổ trợ đắc lực cho mô phỏng là khả năng cho phép người lập trình quyết định hành động cho Agent khi nhận được một gói có kèm dữ liệu người dùng. Đồng thời Agent/UDP cũng cung cấp cơ chế gửi gói có kèm dữ liệu người dùng send [] Khi đó, hàm “process_data{from data}” sẽ được NS2 triệu gọi để thực thi. Cơ chế này được sử dụng để thực hiện mô phỏng. Bằng việc thiết kế lại hàm process_data, đồng thời, tổ chức data hợp lý, sẽ cho phép việc quản lý mô phỏng trở nên dễ dàng. Hiện tại, cấu trúc của data được gửi phải tuân theo cấu trúc sau: {holdtime from} Với holdtime : thời gian phục vụ. from: là biến có kiểu là agent ExpTraffic – là Agent gửi yêu cầu. Sở dĩ cần gửi kèm Agent ExpTraffic là để tạo thuận tiện cho việc gửi phúc đáp từ switch đến customer (sẽ trình bày chi tiết trong phần về Agent ExpTraffic). Do switch bản thân là một node unicast, do đó, nếu kết nối kênh truyền từ agent swa của switch đến một agent nào đó, thì kết nối trước đó của agent swa sẽ bị hủy. Ta có thể tận dụng cơ chế này. Mỗi khi cần gửi thông điệp cho một customer nào, ta chỉ cần kết nối với agent ExpTraffic của customer mà agent ExpTraffic đó thuộc về. Từ đó gửi phúc đáp nếu có yêu cầu. Phúc đáp hiện tại dùng là một thông báo đơn giản cho biết một yêu cầu của một kênh nào đó đã phục vụ xong (hay bị từ chối). Nó không có ý nghĩa đối với một nguồn vô hạn. Một nguồn đơn (như trong mô hình Binomial hay Engset), nó dùng để customer cho biết thời điểm mà yêu cầu được phục vụ xong để bắt đầu một chu kỳ idle. Trong mô phỏng, tất cả các gói yêu cầu hay phúc đáp đều có kích thước rất nhỏ (1 byte) để thời gian trên đường truyền là rất nhỏ, không đáng kể, không làm ảnh hưởng đến mô phỏng. Khi nhận được yêu cầu, tùy theo mô hình cấu hình cho switch, mà có các cách xử lý khác nhau. Về cơ bản, có hai cách xử lý: có queue và không có queue. Với trường hợp không có hàng đợi, khi nhận được yêu cầu, swa chỉ việc kiểm tra xem có server nào rỗi không. Nếu có, thì phục vụ, không còn thì từ chối. Đồng thời gửi phúc đáp về cho customer đã gửi yêu cầu.

Trang 32

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-8: . Lưu đồ mô tả hoạt động hệ thống không có queue

Với trường hợp có queue, yêu cầu sẽ chỉ bị từ chối khi queue đã đầy. Một yêu cầu sẽ được đưa ngay vào hàng đợi trước khi được xử lý. Từ đó, ta đảm bảo cơ chế hoạt động FIFO cho queue. Nếu còn server rỗi, yêu cầu sẽ ngay lập tức được phục vụ. Một server chỉ được phép rỗi khi đã không còn một yêu cầu nào trong queue. Do đó, một server phải tự lập lịch cho chính nó để đọc yêu cầu từ queue ngay khi nó rỗi. Đó là lý do tại sau có vòng hồi tiếp trên mô hình. Cũng với mục đích báo hiệu, SWA sẽ gửi phúc đáp nếu gói được xử lý xong hay bị từ chối.

Hình 3-9: Lưu đồ mô tả quá trình hoạt động hệ thống có queue (buffer)

Khởi tạo: new SWA <số lượng server>

Trang 33

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

3.2.4. Thiết kế hàng đợi cho switch Hàng đợi được sử dụng là FIFO. Tuy vậy, hàng đợi có thể được thay đổi tùy theo mục đích người dùng (không thuộc phạm vi nghiên cứu hiện tại) Hai thao tác cơ bản của queue là enqueue và dequeue: • Enqueue {data time_in} : ngoài dữ liệu được đưa vào queue, còn phải cung cấp thêm thông tin về thời điểm mà data được đưa vào queue để phục vụ cho khả năng thống kê. • Dequeue {time_out}: lấy data từ queue. Đồng thời cung cấp thời điểm mà data được lấy khỏi queue. Như vậy, thời gian mà yêu cầu tồn tại trong queue bằng (time_out – time_in) 3.2.5. Cấu trúc lớp queue Các thuộc tính • capacity : dung lượng queue • index : kích thước hiện tại của queue • pkts_out : tổng số yêu cầu đã được đưa ra khỏi queue. • wait_time : tổng thời gian các gói đã phải chờ • last_wait_time : thời gian yêu cầu gần đây nhất đã phải chờ • time_in {} : thời điểm vào queue • data {} : dữ liệu chứa trong queue. Các hàm hổ trợ: • size: cho bíêt kích thước queue. • full: cho biết queue đã đầy hay chưa. • empty: cho biết queue rỗng hay không. Khởi tạo: new MyQueue –capacity

3.2.6. Tổ chức lớp random theo phân phối mũ – ExpRandom Để đơn giản hóa việc sinh số ngẫu nhiên, cung cấp các thuộc tính thông kê, đồng thời tạo ra chuẩn cho việc phát triển sau này, đó là lý do xây dựng lớp này. Các thành phần của lớp :( • Hàm next{}: cho phép sinh ra số ngẫu nhiên kế tiếp và có cả chức năng thống kê. Hàm này là bắt buộc phải có và được sử dụng bởi các module khác trong chương trình mô phỏng. Do đó, khi thiết kế lại lớp này với một phân phối khác, thì hàm này là bắt buộc. (hình 3-10) Tham số “totalvalue_” (dòng 5) cho biết tổng tất cả các giá trị đã sinh ra Tham số “count” (dòng 6) cho bíêt đã sinh bao nhiêu số. Như vậy, để thống kê trung bình, ta chỉ cần lấy totalvalue_/count (hàm mean) Trang 34

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

1 ExpRandom instproc next {args} { 2 $self instvar totalvalue_ count_ 3 $self instvar value_ 4 set val [$value_ value] 5 set totalvalue_ [expr $totalvalue_ + $val] 6 set count_ [expr $count_ + 1] 7 return $val Hình 3-10: Code hàm next lớp ExpRandom

• Hàm mean {} : là hàm trả về giá trị trung bình của các số đã sinh trước đó nhằm mục đích kiểm tra. Khởi tạo : new ExpRandom

3.2.7. Xây dựng lớp ExpTraffic Lớp ExpTraffic – thừa kế từ Agent/UDP – cho phép quản lý tiến trình gửi tải customers. Nó cho biết các thông số và cách mà customers sẽ gửi yêu cầu. Giống như lớp SWA, ExpTraffic cũng tận dụng những đặc tính của Agent/UDP đặc biệt là hàm process_data ExpTraffic được thiết lập và gắn vào customer trong quá trinh thiết lập inputs cho switch. ExpTraffic về cơ bản có hai phương thức gửi yêu cầu dựa trên đặc tính của customer: nguồn vô hạn (type = 0) và nguồn đơn (type = 1). Đối với nguồn vô hạn: yêu cầu sẽ được gửi liên tục với tần số λ. Kèm theo đó với data là { <self>} – với self là địa chỉ (bộ nhớ) của agent hiện tại. Đối với nguồn đơn, sau khi phát yêu cầu, sẽ tiến hành chờ cho đến khi có phúc đáp thì bắt đầu tiến trình idle mới. Việc điều khiển quá trình gửi thông qua hàm offer , và được hổ trợ bởi hàm process_data đối với nguồn đơn. Khởi tạo: new ExpTraffic <mean arrival> • Type: loại nguồn • Mean arrival = 1/λ • Hold: là biến thuộc kiểu ExpRandom, quản lý thời gian phục vụ.

Trang 35

Đề tài nghiên cứu khoa học

Chương 3: Xây dựng mô phỏng

Hình 3-11: Mô hình mô phỏng hoạt động ExpTraffic

3.2.8. Sơ đồ hoạt động mô phỏng

Hình 3-12: Mô tả sơ lượt hoạt động của mô phỏng

Trang 36

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Chương 4 : Kết quả mô phỏng và nhận xét 4.1. Đánh giá tool Phần này bao gồm các kết quả so sánh giữa tính toán dựa trên lý thuyết với kết quả mô phỏng. Các mô phỏng được kiểm chứng bao gồm M/M/n/n, M/M/n/K, Binomial và Engset. 4.1.1. Mô hình M/M/n/n: Bảng 4-1: Kết quả mô phỏng M/M/5/5

Lý thuyết Input

Thực nghiệm mô phỏng

Số Customers = ∞ Số Server = 5 Khả năng đáp ứng = 5 μ = 2.0 λ = 28.0

λ = 27.9632

tm = 1/μ = 0.5

tm = 0.4988

A =14

A = 13.9474

Output

Thời gian mô phỏng: 100 (đvtg) Sent : 2794 Lost: 1888 Blocking: 67.3675 %

Blocking : 67.5734 %

Trang 37

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Hình 4-1: Kết quả mô phỏng khi thực hiện demo ứng với bảng kết quả trên

Một số kết quả so sánh khác của mô hình M/M/n/n

Erlang - loss model (M/M/5/5)

Lý thuyết Thực nghiệm

90 80 70 60 50 40 30 20

A

10 0

4

8

12

16

20

24

28

19.9067

47.9008 62.6352

71.0621 76.4358

80.1428 82.8489

Thực nghiệm 19.8314

47.5874 62.1917

71.3283 76.4339

80.3001 83.3705

Lý thuyết

Hình 4-2: Một số kết quả so sánh blocking giữa thực nghiệm và lý thuyết của mô hình M/M/5/5.

Trang 38

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

4.1.2. Mô hình M/M/n/K – Erlang delay-loss Bảng 4-2: mô hình M/M/5/10

Input

Lý thuyết Số Customers = ∞ Số Server = 5 Khả năng đáp ứng = 10 μ = 1.0 λ = 16.0 tm = 1/μ = 1 A =16

Output Blocking: 68.7567 % Delay : 31.1599 % Thời gian chờ trung bình: 0.2842

Thực nghiệm mô phỏng

λ = 15.9886 tm = 1.0095 A = 16.1402 Thời gian mô phỏng: 100 (đvtg) Sent : 1599 Lost: 1089 Blocking : 68.1051 % Delay : 31.1599 % Thời gian chờ trung bình: 0.2835

Hình 4-3: Kết quả mô phỏng khi thực thi demo ứng với mô hình trên

Trang 39

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Một số kết quả khác: Lý thuyết

Erlang delay-loss (M/M/5/10)

Thực nghiệm 1 90 80

Blocking (B%)

70 60 50 40 30 20

A

10 0

Lý thuyết

4

8

12

16

20

24

28

4.2486 38.293 58.384 68.757 75.001 79.167 82.143

Thực nghiệm 1 4.0212 39.128 58.936 68.648 76.857 77.795 81.482

Hình 4-4: Một số kết quả so sánh blocking giữa thực nghiệm và lý thuyết của mô hình M/M/5/10

Trang 40

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét Lý thuyết

Erlang delay-loss (M/M/5/10)

Thực nghiệm 70 60 50 40 30 20

A

10 0

4

8

12

16

20

24

28

43.5852

57.7351

41.1789

31.1599

24.916

20.8253

17.8539

Thực nghiệm 43.5255

57.4542

40.5941

31.011

22.8719

21.9258

18.268

Lý thuyết

Hình 4-5: Một số kết quả so sánh delay giữa thực nghiệm và lý thuyết của mô hình M/M/5/10 Lý thuyết

Erlang delay-loss (M/M/5/10) lamda = A, Mu = 1.0

Thực nghiệm 1

0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1

A

0.05 0

4

8

12

16

20

24

28

Lý thuyết

0.2234

0.4458

0.3583

0.2842

0.2334

0.1974

0.1708

Thực nghiệm 1

0.2179

0.4446

0.3563

0.2754

0.2317

0.1981

0.1694

Hình 4-6: So sánh thời gian trong queue giữa thực nghiệm và lý thuyết của mô hình M/M/5/10

Trang 41

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

4.1.3. Mô hình Binomial: Bảng 4-3: Kết quả demo mô hình Binomial – M/M/5/5/5

Input

Các thông số đo được qua thực nghiệm

Output

Số lượng Customers (N) Số Server (n) Khả năng phục vụ của hệ thống (K) Tần số phát yêu cầu ở các nguồn phát (λ) Thời gian phục vụ trung bình (μ = 1/tm) tm λi Nguồn 0 Nguồn 1 Nguồn 2 Nguồn 3 Nguồn 4 Trung bình Tổng số yêu cầu đã phát Bị từ chối Xác xuất bị từ chối

5 5 5 0.2013 1/3 3.0195 0.1969 0.2019 0.1980 0.2134 0.1932 0.2007 2486 0 0%

Hình 4-7: Kết quả mô phỏng khi thực thi demo ứng với mô hình Binomial

Trang 42

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

4.1.4. Mô hình Engset: Bảng 4-4: Kết quả demo mô hình Engset – M/M/5/5/10

Input

Các thông số đo được qua thực nghiệm

Output

Số lượng Customers (N) Số Server (n) Khả năng phục vụ của hệ thống (K) Tần số phát yêu cầu ở các nguồn phát (λ) Thời gian phục vụ trung bình (μ = 1/tm) Thời gian thực hiện mô phỏng tm λi Nguồn 0 Nguồn 1 Nguồn 2 Nguồn 3 Nguồn 4 Nguồn 5 Nguồn 6 Trung bình Tổng số yêu cầu đã phát Bị từ chối Xác xuất bị từ chối Lý thuyết Mô phỏng

7 5 5 0.2 1/10 1000 10.0026 1.9634 2.1024 1.8287 1.9367 1.9740 1.9667 1.9623 1.9620 4078 3592 88.2105 88.0824

Hình 4-8: Kết quả mô phỏng khi thực thi demo ứng với mô hình Engset M/M/5/5/10

Trang 43

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Trên là bốn mô hình cơ bản của các mô hình hàng đợi, đồng thời, chúng khá đơn giản cho việc tính toán lý thuyết. Với các mô hình khác, việc tính toán có phần khó khăn hơn. Ở các ví dụ trên, cho thấy được sự chính xác của mô phỏng so vớ lý thuyết, nó đảm bảo mô hình mô phỏng đưa ra là đúng đắn và khá tin cậy. 4.2. Những kết quả mở rộng Ngoài những mô hình đơn giản trên có thể tính toán bằng lý thuyết, với những trường hợp phức tạp hơn, việc tính toán trên lý thuyết gặp nhiều khó khăn. Mô phỏng sẽ giúp giải quyết những vấn đề trên. Các kết quả mô phỏng khác: 4.2.1. Mô hình Engset mở rộng: Cũng là mô hình Engset như trên, song, nếu các tham số μ và λ thay đổi theo từng customer. Hay nói cách khác, mỗi customer được mô tả bởi một cặp tham số (λi, tmi) khác nhau (với tm = 1/μ) , thì việc tính toán xác xuất blocking trở nên rất khó khăn. Khi đó, việc mô phỏng sẽ giúp giải quyết bài toán một cách đơn giản. Kết quả mô phỏng: Mô tả: Bảng 4-5: bảng thống kê mô phỏng Engset

Các tham số Số lượng customer (N) Số lượng server (n) Khả năng đáp ứng (K) Nguồn 0 Nguồn 1 Nguồn 2 Nguồn 3 Nguồn 4 (λ,tm) Nguồn 5 Nguồn 6 Nguồn 7 Nguồn 8 Nguồn 9 Thời gian thực hiện mô phỏng Tổng số yêu cầu Số yêu cầu bị từ chối XÁC XUẤT BLOKING

Input 10 5 5 (0.9 , 3.0) (0.2 , 5.0) (1.0 , 4.0) (0.3 , 2.0) (0.6 , 3.0) (0.2 , 3.0) (0.5 , 5.0) (1.1 , 4.0) (0.8 , 5.0) (0.5 , 5.0)

Mô phỏng

(0.9144 , 3.0461) (0.1892 , 5.3750) (0.9428 , 4.1191) (0.3115 , 1.8447) (0.6344 , 3.0140) (0.2065 , 3.1296) (0.5112 , 4.9793) (1.2285 , 3.9947) (0.7820 , 5.0517) (0.5089 , 5.6637) 1000 2883 1717 59.5560%

Trang 44

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Hình 4-9 : Kết quả mô phỏng mô hình Engset mở rộng (M/M/5/5/10)

4.2.2. Mô hình Palm’s Machine repair: Bảng 4-6: Bảng thống kê mô phỏng mô hình Palm’s machine repair M/M/5/10/10

Các tham số Số lượng customer (N) Số lượng server (n) Khả năng đáp ứng (K) Nguồn 0 Nguồn 1 Nguồn 2 Nguồn 3 Nguồn 4 (λ,tm) Nguồn 5 Nguồn 6 Nguồn 7 Nguồn 8 Nguồn 9 Nguồn 0 Nguồn 1 Nguồn 2 Offered Nguồn 3 Traffic xét Nguồn 4 trên từng Nguồn 5 nguồn (a) a = λ/μ = λ*tm Nguồn 6 Nguồn 7 Nguồn 8 Nguồn 9

Input 10 5 10

(0.9 , 3)

2.7

Mô phỏng

(0.8331 , 3.5154) (0.8494 , 3.0631) (0.8804 , 3.0429) (0.9847 , 3.0804) (0.8805 , 3.4189) (0.9797 , 2.5460) (0.8962 , 2.6164) (0.8777 , 3.1873) (0.8865 , 3.2297) (0.9029 , 3.0529) 2.9287 2.6018 2.6791 3.0333 3.0105 2.4943 2.3449 2.7974 2.8630 2.7470 Trang 45

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Thời gian thực hiện mô phỏng Tổng số yêu cầu Số yêu cầu bị từ chối Số yêu cầu bị trì hoãn (đợi) XÁC XUẤT BLOKING XÁC XUẤT DELAY

1000 1649 0 1582 0% 95.9369%

Hình 4-10: Kết quả thực hiện mô phỏng mô hình Palm’s Machine repair

4.2.3. Mô hình Palm’s machine repair mở rộng: Ở ví dụ trên, tất cả các nguồn phát với cùng một tần số phát λ và thời gian phục vụ μ (về mặt lý thuyết). Ngoài ra, ta hoàn toàn có thể mở rộng mô phỏng với mỗi nguồn đặc trưng bởi một cặp tham số (λ, tm) khác nhau. Ví dụ với mô hình mô phỏng Palm’s machine repair M/M/5/10/10

Trang 46

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Hình 4-11: Mô phỏng Palm’s machine repair (M/M/5/10/10) mở rộng

Hình 4-12: Kết quả mô phỏng được mô tả ở Hình 4-11

4.3. Bài toán ví dụ Một bài toán ví dụ ứng dụng tool như sau: Giả sử ta có tổng đài quản lý 4 khu vực, mỗi khu vực có đặc trưng về tần số phát cũng như thời gian phục vụ trung bình riêng. Yêu cầu đặt ra là tính được xác suất một cuộc gọi bị blocking hay bị chờ của hệ thống, từ bổ sung server vừa đủ để khả năng đáp ứng khách hàng đủ tốt (giả sử blocking dưới 10% và khách hàng không phải Trang 47

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

đợi quá lâu). Giả sử hệ thống hàng đợi được sử dụng là M/M/n/N/K (limited source and queue). Mô tả hệ thống: Hệ thống quản lý 4 khu vực, mỗi khu vực có các đặc trưng sau: Khu vực

số máy 15 24 30 18

0 1 2 3

lamda

tm 0.10 0.13 0.09 0.02

3.00 4.00 5.00 2.00

Tổng số máy hiện tại: 87 Æ hệ thống : M/M/15/35/87 (15 server và buffer = 20) Một số kết quả mô phỏng khi lần lượt tăng số server server

queue

15 16 17 18 19 20

Xác xuất blocking

20 20 20 20 20 20

Xác suất chờ

2.9721 1.5131 0.7137 0.3650 0.2894 0.2719

95.3767 92.0860 85.7393 70.2196 58.7290 43.4604

Thời gian chờ trung bình (đvtg) 3.2106 2.4570 1.6944 1.0302 0.6496 0.3955

Với số server = 15, thời gian một cuộc gọi phải chờ là khá lớn (3.2106 đvtg). Nếu đơn vị thời gian được tính bằng phút thì thời gian một cuộc gọi phải chờ là hơn 3 phút. Với việc tăng dần số server, thời gian chờ trung bình giảm dần. Đến khi số server là 20, một cuộc gọi chỉ còn phải chờ 0.4 đvtg. Và với giá trị này, chất lượng hệ thống là chấp nhận được. Sau một thời gian hoạt động, số máy ở các vùng tăng lên: Khu vực 0 1 2 3

Số máy 45 48 60 180

lamda

tm 0.10 0.13 0.09 0.02

3.00 4.00 5.00 2.00

Vấn đề cần giải quyết là phải dự trù được số server cần thiết để đảm bảo bloking dưới 10%. Bằng cách sử dụng tool, bài toán có thể được giải quyết đơn giản bằng cách tăng dần số server hay buffer đến một giá trị thích hợp. Có 2 cách tiếp cận, hoặc chỉ điều chỉnh số server hoặc kết hợp cả việc hiệu chỉnh số server và buffer. Giữ nguyên số buffer, tăng server, ta có kết quả sau: server 20 21 22 30 35 36 37 38 39

queue 20 20 20 20 20 20 20 20 20

Xác xuất blocking 56.9650 54.2900 51.5648 30.2963 16.3586 13.9361 11.2554 8.9498 6.4940

Xác suất chờ 42.9545 45.6282 48.3514 69.5965 82.3820 84.8095 86.3331 87.1192 85.8362

Thời gian chờ trung bình 1.5489 1.5664 1.5597 1.5274 1.3470 1.3057 1.2455 1.1304 0.9810

Trang 48

Đề tài nghiên cứu khoa học

Chương 4: Kết quả mô phỏng và nhận xét

Hoặc hiệu chỉnh kết hợp số server và buffer: server 20 20 20 20 30 30

queue 20 30 40 50 50 60

Xác xuất blocking 56.9650 53.3833 49.9178 45.8086 14.6058 8.7402

Xác suất chờ 42.9545 46.509 49.9475 54.02 85.2107 91.0183

Thời gian chờ trung bình 1.5489 2.5083 3.5622 4.7827 4.6552 5.6766

Như vậy, ta có thể giải quyết bài toán bằng cách tăng số server từ 20 lên 39 sẽ đáp ứng yêu cầu do xác suất blocking chỉ còn xấp xĩ 7% và một cuộc gọi phải chờ không quá một đơn vị thời gian. Tuy nhiên, kết quả chỉ mang tính tham khảo, với bài toán thực tế, cần có sự kết hợp với lợi ích về kinh tế.

Trang 49

Đề tài nghiên cứu khoa học

Chương 5: Kết luận

Chương 5 : Kết luận Về mặt lý thuyết, đề tài đã nghiên cứu các mô hình hàng đợi phổ biến, nắm được phương thức hoạt động cũng như các tính chất của các mô hình cũng như lý thuyết về hàng đợi. Từ đó, đã đưa ra được mô hình mô phỏng tương ứng cho từng mô hình dựa trên các đặc điểm chung và riêng của các mô hình. Hiện tại, việc mô phỏng đã giải quyết được bài toán về đo lường traffic trên một số mô hình phức tạp. Tuy vậy, đề tài chỉ dừng lại ở việc nghiên cứu lý thuyết hàng đợi tổng quát. Các mô phỏng vẫn còn đơn giản, chỉ để phục vụ cho từng mô hình cụ thể mà chưa xem xét chúng trong một mối liên kết. Đề tài có hai hướng phát triển: • Thứ nhất, mở rộng đề tài bằng cách xem xét, đo lường lưu lượng trong hệ thống bao gồm nhiều hàng đợi kết hợp. • Thứ hai, đi sâu vào một ứng dụng thực tiễn về hệ thống hàng đợi. Ví dụ, có thể phát triển bằng cách xây dựng mô phỏng để đo lường traffic trong một tổng đài.

Trang 50

Đề tài nghiên cứu khoa học

Phụ lục A

Phụ lục A: Hướng dẫn cài đặt NS2 Có hai cách cài đặt ns2: cài đặt từng gói nhỏ bên trong NS2 hoặc cài trọn bộ. Sau đây là cách cài trọn bộ. • Bước 1: Download gói http://www.isi.edu/nsnam/ns/.

phần

mềm

ns-allinone-2.29.3.tar

về

từ

địa

chỉ

• Bước 2: Cài đặt, chuyển đến thư mục ta muốn cài đặt NS (chẳng hạn như /usr/local/src/), giải nén gói ns-allinone-2.29.3.tar bằng lệnh: tar xvf ns-allinone-2.28.tar và chạy script: ./install • Bước 3: Thiết lập biến môi trường: o 3.1: Đặt đường dẫn đến {đường dẫn đến thư mục ns-allinone-2.29}/bin, {đường dẫn đến thư mục ns-allinone-2.29}/tcl8.4.11/unix, {đường dẫn đến thư mục ns-allinone2.29}/tk8.4.11/unix vào biến PATH export PATH=$PATH:{đường dẫn đến thư mục ns-allinone-2.29}/bin:{đường dẫn đến thư mục ns-allinone-2.29}/tcl8.4.11/unix:{đường dẫn đến thư mục ns-allinone2.29}/tk8.4.11/unix o 3.2: Đặt {đường dẫn đến thư mục ns-allinone-2.29}/otcl-1.11, {đường dẫn đến thư mục ns-allinone-2.29.3}/lib, vào trong biến môi trường LD_LIBRARY_PATH export LD_LIBRARY_PATH <đường dẫn> o 3.3: Thêm {đường dẫn đến thư mục ns-allinone-2.29}/tcl8.4.11/library vào trong biến môi trường TCL_LIBRARY để tránh việc ns và nam báo lỗi khi khởi động Lưu ý: mỗi khi đóng terminal hiện tại (cửa sổ console trong linux) hay khi mở một terminal bất kỳ để chạy chương trình mô phỏng, bước này phải được thực hiện lại. • Bước 4: Kiểm tra (không bắt buộc) cd {đường dẫn đến thư mục ns-allinone-2.29}/ns-2.29 ./validate

Đề tài nghiên cứu khoa học

Phụ lục B

Phụ lục B: Cài đặt và thiết lập mô phỏng Để chạy mô phỏng, các tập tin cần phải có là: • Simulator-config.tcl • SWA.tcl • ExpRandom.tcl • MyQueue.tcl • MyTraffic.tcl • QueueTheory.tcl (chỉ cần thiết khi chạy các mô phỏng xây dựng sẵn có kèn so sánh kết quả lý thuyết) Từ những file trên, ta đã hoàn toàn có thể xây dựng một mô phỏng riêng hoặc sử dụng một số mô phỏng được xây dựng sẵn như: • MMnn.tcl : mô hình Erlang loss • MMnk.tcl : mô hình Erlang delay-loss • Binomial.tcl • Engset.tcl • Engset_ex.tcl : mô hình engset mở rộng • PMR : palm’s machine repair • PMR_ex: palm’s machine repair mở rộng Để thiết lập một mô phỏng mới, phải được đảm bảo nắm các đặc điểm của các đối tượng đã được xây dựng. Bắt đầu xây dựng: Khai báo file tiêu đề có liên quan:

Đề tài nghiên cứu khoa học

Phụ lục B

Để đơn giản, các thông số về hệ thống nên được khai báo trước

Hình 0-1: Các biến mô tả các thông số cho hệ thống.

Khởi tạo node switch tùy theo yêu cầu. Hiện tại, mô phỏng chỉ dừng lại ở việc mô phỏng một mô hình đơn, nên thông thường chỉ có một node loại này được khởi tạo. Ở ví dụ này, node switch được tạo là một node dạng MMnNN (Engset). Tùy theo loại node switch mà có cách khai báo khác nhau như đã trình bày trong các phần trước. Thiết lập các node customer cũng như các thuộc tính của nó. Đồng thời, chuẩn bị kết nối các customer với switch. Các thông số cần thiết để khởi tạo cho customer như: • Một node đóng vai trò làm customer • Một đối tượng thuộc kiểu ExpRandom quản lý việc sinh số ngẫu nhiên theo phân phối mũ đặc trưng cho thời gian trung bình cần phục vụ một yêu cầu phát đi từ nguồn này. Nếu tất cả các nguồn cùng phát với một thời gian phục vụ như nhau, ta có thể chỉ cần khai báo một đối tượng thuộc kiểu này và gán cho tất cả các nguồn. Nếu không, ta cũng có thể khai báo N đối tượng và gán tương ứng cho N nguồn. trong vú dụ sau là trường hợp N nguồn được gắn với N đối tượng ExpRandom tương ứng. Do việc kết nối, liên kết customers và switch được thực hiện hoàn toàn tự động bởi hàm SetSwitchInput nên ta không phải bận tâm về việc nối kết giữa customers, đối tượng ExpRandom và switch là như thế nào. Chi tiết về cách thức đã được trình bày cụ thể ở phần

Đề tài nghiên cứu khoa học

Phụ lục B

xây dựng mô phỏng trong chương trước.Ở đây, ta chỉ cần quan tâm làm cách nào để truyền tham số cho hàm SetSwitchInput đúng với mục đích mô phỏng của mình. Hàm SetSwitchInput tự nó định ra một danh sách chứa các item theo một chuẩn để dễ dàng giao tiếp giữa hàm này với người dùng. Danh sách này thực ra thuộc kiểu danh sách bình thường (list) trong tcl. Bên trong nó chứa các item, mà các item này bản thân nó lại là một danh sách, mô tả các thuộc tính của một customers theo chuẩn sau: {<node> <1/λ> <ExpRandom>} Như vậy, ta cần xây dựng một danh sách các item phù hợp với mục đích mô phỏng của mình:

Thiết lập kết nối, đồng thời lưu các đối tượng trả về. Đối tượng trả về là một tập danh sách các agent điều khiển việc phát các yêu cầu của customers. Sở dĩ phải lưu lại các giá trị này vì ta phải dùng nó để điều khiển việc lập lịch phát các yêu cầu cũng như lấy các thông số mô phỏng trả về. Khởi động quá trình phát yêu cầu của các nguồn:

Xác định thời gian kết thúc mô phỏng cũng như định ra những kết quả cần thiết để xuất (thông qua hàm finish).

Các thông số cần thiết cho output: • Số yêu cầu đã gửi, từ chối và trễ: lấy được từ đối tượng swa trong switch thông qua agent 0

• Các thông số về thời gian chờ trong queue (nếu có)

Đề tài nghiên cứu khoa học

Phụ lục B

• Lấy các thông số về nguồn phát như λ và tm:

Khởi động mô phỏng. Lưu ý: $ns là một biến kiểu Simulator toàn cục, không được khai báo lại bất kỳ một biến nào khác thuộc lơp Simulator mà sử dụng ngay biến này cho mô phỏng

Đề tài nghiên cứu khoa học

Phụ lục C: Code

Phụ lục C: Code

Simulation-Config.tcl source MyTraffic.tcl Simulator instproc BuildSwitch {args} { puts stdout "| * Building switch node ..." puts stdout "| + node type : [lindex $args 0]" set sw [$self node] $sw label "SWITCH" $sw set type [lindex $args 0] switch [lindex $args 0] { MMnn { ;#Erlang-loss set queuesize 0 set Server [lindex $args 1] if {[llength $args] == 3} { set customers_ [lindex $args 2] } else { set customers_ 1 } puts stdout "| ! Description: Erlang-loss" puts stdout [format "| + Servers: %i" $Server]

} MMnK { ;#Erlang delay system with inf Queue set Server [lindex $args 1] set queuesize [lindex $args 2] if {[llength $args] == 4} { set customers_ [lindex $args 3] } else { set customers_ 1 }

puts stdout "| ! Description: Loss-Delay System" puts stdout [format "| + Servers: %i" $Server] puts stdout [format "| + queue-size: %i" $queuesize] if {$queuesize<=0} { error "queue size must be greater than 0" }

} MMNNN { ;#Binomial set Server [lindex $args 1] set queuesize 0 set customers_ [lindex $args 1] set K [expr $queuesize+$Server] puts puts puts puts }

stdout stdout stdout stdout

"| ! Description: Binomial System" [format "| + Servers: %i" $Server] [format "| + queue-size: %i" $queuesize] [format "| + customer: %i" $customers_]

Đề tài nghiên cứu khoa học

Phụ lục C: Code

MMnnN { ;#Engset set Server [lindex $args 1] set queuesize 0 set customers_ [lindex $args 2] set K [expr $queuesize+$Server] puts puts puts puts

stdout stdout stdout stdout

"| ! Description: Engset System" [format "| + Servers: %i" $Server] [format "| + queue-size: %i" $queuesize] [format "| + customer: %i" $customers_]

if {$Server>=$customers_} { error {For Engset model, n must be greater N} } } MMnNN { ;#palm's mechine repair set Server [lindex $args 1] set customers_ [lindex $args 2] set queuesize [expr $customers_-$Server] set K $customers_ puts puts puts puts

stdout stdout stdout stdout

"| ! Description: Palm's Mechine Repair" [format "| + Servers: %i" $Server] [format "| + queue-size: %i" $queuesize] [format "| + customer: %i" $customers_]

if {$queuesize<=0} { error {For PMR, N must be greater than n} } } MMnKN { set set set set

Server [lindex $args 1] K [lindex $args 2] customers_ [lindex $args 3] queuesize [expr $K-$Server]

puts puts puts puts

stdout stdout stdout stdout

"| ! Description: M/M/n/K/N" [format "| + Servers: %i" $Server] [format "| + queue-size: %i" $queuesize] [format "| + customer: %i" $customers_]

if {$queuesize<=0} { error {For this, queue-size must be greater than 0} }

} default {error "unknown switch type"}

} $sw set queue [new MyQueue -capacity $queuesize] $sw set customers $customers_ set swa [new SWA $Server] $self attach-agent $sw $swa

}

for {set i 0} {$i<$Server} {incr i} { set udp($i) [new Agent/UDP] $self attach-agent $sw $udp($i) } return $sw

Đề tài nghiên cứu khoa học

Phụ lục C: Code

#---------------------Simulator instproc SetSwitchInput {sw itemlist} { puts stdout "| * Setup inputs of switch" puts stdout "| + quantity: [llength $itemlist]" set n [llength $itemlist] set type [$sw set type] set cap [$sw set customers] if {$n!=$cap} { error {Number of inputs is wrong} } set swa [$sw agent 0] set agent_addr {} for {set i 0} {$i<$n} {incr i} { set item [lindex $itemlist $i] set node_ [lindex $item 0] set trfftype_ [lindex $item 1] set mean_arrival_ [lindex $item 2] set hold_ [lindex $item 3] set agt [new ExpArrival $trfftype_ $mean_arrival_ $hold_] set agent_addr [lappend agent_addr $agt] $node_ attach $agt 250 $self duplex-link $node_ $sw 2Mb 0ms DropTail $self connect $agt $swa } return $agent_addr

} #---------------------Simulator instproc SetSwitchOutput {sw ilist} { puts stdout "| * Setup outputs of switch" puts stdout "| + quantity: [llength $ilist]" set n [llength $ilist] set swa [$sw agent 0] set agent_addr {} set server [$swa set server_] if {$n>$server} { set n $server puts stdout "| !!! Warning: the number of server less than connection" } for {set i 0} {$i<$n} {incr i} { $swa up_link $i set node_ [lindex $ilist $i] set null [new Agent/Null] set agent_addr [lappend agent_addr $null] $self attach-agent $node_ $null set udp [$sw agent [expr $i+1]] $self connect $udp $null } return $agent_addr

} #==============================================

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set ns [new Simulator]

SWA.tcl Class SWA -superclass Agent/UDP #---------------------SWA instproc init {server} { $self set received 0 $self set dropped 0 $self set delayed 0 $self set server_ $server set link_up_ {} set time_out_ {} for {set i 0} {$i<$server} {incr i} { $self set time_out_ [lappend time_out_ 0.0] $self set link_up_ [lappend link_up_ 0] } $self next } #---------------------SWA instproc up_link {index} { $self instvar link_up_ set link_up_ [lreplace $link_up_ $index $index 1] } #---------------------SWA instproc down_link {index} { $self instvar link_up_ set link_up_ [lreplace $link_up_ $index $index 0] } #---------------------SWA instproc process_data {from dta} { global ns $self instvar node_ set data [lindex $dta 0] set agt [lindex $dta 1] switch [$node_ set type] { MMnn { $self MMnn $data $agt } MMnK { $self MMnK $data $agt } MMNNN { $self MMnn $data } MMnnN { $self MMnn $data } MMnNN { $self MMnK $data } MMnKN { $self MMnK $data }

$agt $agt $agt $agt

} } #---------------------SWA instproc MMnn {data agt} { $self instvar node_ server_ time_out_ link_up_ received dropped global ns

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set received [expr $received+1] set hold_time $data set now [$ns now] set busy 1 for {set i 0} {$i<$server_} {incr i} { if {[lindex $time_out_ $i]<$now} { set Agt [$node_ agent [expr $i+1]] set next [expr $now+$hold_time] if {[lindex $link_up_ $i]} { $ns at $next "$Agt send 1 data" } set time_out_ [lreplace $time_out_ $i $i $next] $ns at $next "$ns connect $self $agt; $self send 1 ack" set busy 0 break; } } if {$busy} { set dropped [expr $dropped+1] $ns connect $self $agt $self send 1 ack }

} #---------------------SWA instproc process {server next from} { global ns $self instvar link_up_ node_ $ns connect $self $from $self send 1 ack

}

if {[lindex $link_up_ $server]} { set agt [$node_ agent [expr $server +1]] $agt send 1 x } $self Serve $server $next

SWA instproc Serve {server now} { global ns $self instvar node_ time_out_ delayed set qu [$node_ set queue] if {![$qu set set set

empty]} { data [$qu dequeue $now] hold [lindex $data 0] from [lindex $data 1]

set wait [$qu set last_wait_time] if {$wait != 0} { set delayed [expr $delayed +1] } set next [expr $now + $hold] set time_out_ [lreplace $time_out_ $server $server $next] $self set queue $qu

Đề tài nghiên cứu khoa học

}

$ns at $next "$self process $server $next $from"

} SWA instproc SearchServer {now} { $self instvar server_ time_out_ set flag 0 set index 0 for {set i 0} {$i<$server_} {incr i} { if {[lindex $time_out_ $i]<=$now} { set flag 1 set index $i break } } if {$flag} { $self Serve $index $now } } SWA instproc MMnK {data from} { $self instvar node_ server_ time_out_ received dropped global ns set set set set set set

qu [$node_ set queue] received [expr $received+1] hold_time $data data_ "$data $from" agt [$node_ agent 0] now [$ns now]

set done 0 if {[$qu full]} { $self SearchServer $now set done 1 }

}

if {[$qu full]} { $ns connect $self $from $self send 1 ack set dropped [expr $dropped+1] } else { $qu enqueue $data_ $now $node_ set queue $qu } if {!$done} { $self SearchServer $now }

Mytraffic.tcl source ExpRandom.tcl Class ExpArrival -superclass Agent/UDP ExpArrival instproc init {trff_type arrival hold} { set Arrival [new ExpRandom $arrival] $self set Arrival_ $Arrival

Phụ lục C: Code

Đề tài nghiên cứu khoa học

Phụ lục C: Code

$self set Holding_ $hold $self set type_ $trff_type $self next } ExpArrival instproc offer {} { global ns $self instvar Arrival_ Holding_ type_ set now [$ns now] set hold [$Holding_ next] switch $type_ { 0 { set val [$Arrival_ next] set next [expr $now+$val] $ns at $next "$self offer" } 1 { } default { error {type is not supported} } }

#

set data {} set data [lappend data $hold] set data [lappend data $self] puts stdout "[$ns now] $self" $self send 1 $data

} #---------------------ExpArrival instproc process_data {from dta} { global ns $self instvar Arrival_ Holding_ type_ if {$type_==1} { set val [$Arrival_ next] set now [$ns now] $ns at [expr $now + $val] "$self offer" } }

Myqueue.tcl Class MyQueue MyQueue instproc init {args} { $self set capacity 10 ;# tong dung luong cua queue $self set index 0 ;# so luong pkts trong queue hien tai $self set pkts_out 0 ;# so pkts out $self set wait_time 0 ;# tong thoi gian cho $self set last_wait_time {} ;# thoi gian ma goi gan nhat phai cho #$self set hold_time {} ;# thoi gian xu ly goi $self set time_in {} ;# thoi diem goi vao queue $self set data {} ;# du lieu

Đề tài nghiên cứu khoa học

Phụ lục C: Code

if {[llength $args]>0} { if {[llength $args]==2} { set key [lindex $args 0] if {[string match {-capacity} $key]} then { set key [string range $key 1 end] $self set $key [lindex $args 1] } else { error {Paramaters error} } } else { error {wrong number of arguments} } }

} MyQueue instproc enqueue {data_ time_in_} { $self instvar capacity index data time_in if {$index < $capacity} { set data [linsert $data 0 $data_] set time_in [linsert $time_in 0 $time_in_] set index [expr $index+1] } }

MyQueue instproc dequeue {time_out} { $self instvar index data time_in pkts_out wait_time last_wait_time if {$index>0} { set index [expr $index-1] set set set set

last_wait_time [expr $time_out - [lindex $time_in $index]] data_ [lindex $data $index] time_in [lreplace $time_in $index $index] data [lreplace $data $index $index]

set wait_time [expr $wait_time+$last_wait_time] set pkts_out [expr $pkts_out+1] return $data_ } return -1

} MyQueue instproc size {} { $self instvar index return $index } MyQueue instproc full {} { $self instvar index capacity if {$capacity==inf} { return 0 } if {$index==$capacity} { return 1 } return 0 } MyQueue instproc empty {} { $self instvar index if {$index==0} { return 1

Đề tài nghiên cứu khoa học

}

} return 0

ExpRandom.tcl Class ExpRandom ExpRandom instproc init {avg} { $self set totalvalue_ 0 $self set count_ 0 set rng [new RNG] $rng seed 0 set value [new RandomVariable/Exponential] $value set avg_ $avg $value use-rng $rng $self set value_ $value } ExpRandom instproc next {args} { $self instvar totalvalue_ count_ $self instvar value_ set val [$value_ value] set totalvalue_ [expr $totalvalue_ + $val] set count_ [expr $count_ + 1] return $val } ExpRandom instproc mean {} { $self instvar totalvalue_ count_ if {$count_==0} { return 0 } else { return [expr ($totalvalue_*1.0)/$count_] } }

QueueThoery.tcl proc MMnn {A n} { set E 1.0 for {set i 1} {$i<=$n} {incr i} { set tmp [expr $E*$A] set E [expr $tmp/($i+$tmp)] } return $E } proc f1n {A n} { ;# f(n) = A^n/n! set re 1 set A_ [expr $A*1.0] for {set i 1} {$i<=$n} {incr i} { set re [expr $re* [expr $A_/$i]] } return $re

Phụ lục C: Code

Đề tài nghiên cứu khoa học

Phụ lục C: Code

} proc f2n {A n q} { ;# f(n) = (A/n)^q set re [expr $A/($n*1.0)] return [expr {pow($re,$q)}] } proc f3n {A n} { ;#sum A^i/i! set re 1 for {set i 1} {$i<=$n} {incr i} { set tmp [f1n $A $i] set re [expr $re+$tmp] } return $re } proc MMnK set set set set set set

{A n K} { q [expr $K-$n] n_ [expr $n-1] q_ [expr $q+1] A_ [expr $A*1.0] A_n [expr $A_/$n] A_n_ [expr 1- $A_n]

if {$A!=$n} { set tmp_l [f2n $A $n $q] set tmp_d [expr [expr 1 - [f2n $A $n $q]] / $A_n_] set tmp [expr [expr 1 - [f2n $A $n $q_]] / $A_n_] } else { set tmp_l 1 set tmp_d $q set tmp $q_ } set ms [expr [f3n $A $n_] + [expr [f1n $A $n]*$tmp]] set ts_d [expr [f1n $A $n]*$tmp_d] set ts_l [expr [f1n $A $n]*$tmp_l] #tinh tq - average queue length in M/M/n/K if {$A!=$n} { set Pn [expr [f1n $A $n]/$ms] set tmp1 [expr 1-[expr [f2n $A $n $q]*[expr 1+($q*$A_n_)]]] set tmp2 [expr [expr $A_n*$Pn]/[expr {pow($A_n_,2)}]] set tq [expr $tmp1*$tmp2] } else { set tq [expr [expr [expr $q*($q+1)]*[f1n $A $n]]/[expr $ms*2]] } return "[expr $ts_l/$ms] [expr $ts_d/$ms] $tq" } proc MMnnN {a n N} { set re 1.0 for {set i 1} {$i<=$n} {incr i} { set re [expr 1 +[expr [expr $i*$re]/[expr ($N-$i)*$a]]] } return [expr 1.0/$re] }

Đề tài nghiên cứu khoa học

Phụ lục C: Code

proc MMNNN {a n N} { set re 0 puts stdout "n=$n" for {set x 0} {$x<$n} {incr x} { set tmp [I $x $a $n $N $N] #puts $tmp set re [expr $re+[expr 1.0/$tmp]] } return $re }

MMNN.tcl source source source source source

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

set server 5 set lamda 28.0 set Mu 2.0 #================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server hold_rd scra $ns flush-trace set set set set set

swa [$sw agent 0] sent [$swa set received] lost [$swa set dropped] A [expr ($lamda*1.0)/$Mu] arr [$scra set Arrival_]

puts stdout [format "| puts stdout [format "|

+ mean tm: %8.4f" [$hold_rd mean]] + mean lm: %8.4f" [expr 1.0/[$arr mean]]]

puts stdout [format "| + Model M/M/n/n <-> M/M/%i/%i" $server $server] puts stdout [format "| + A: %6.4f" [expr [$hold_rd mean]/[$arr mean]]] puts stdout [format "| + sent: %i lost: %i" $sent $lost] puts stdout [format "| + P{loss}: %8.4f%% - thoery: %8.4f%%" [expr ($lost*100.0)/$sent] [expr [MMnn $A $server]*100.0]] puts stdout "----------------------------------------------------" exit } #=========================================================== #Chuong trinh chinh puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnn $server] set hold_rd [new ExpRandom [expr 1.0/$Mu]]

Đề tài nghiên cứu khoa học set lscr {} set set set set

scr [$ns node] item {} item [lappend item $scr 0 [expr 1.0/$lamda] $hold_rd] lscr [lappend lscr $item]

set agent_addr [$ns SetSwitchInput $sw $lscr] puts puts puts puts

stdout stdout stdout stdout

"| * Set up traffic" [format "| - lamda: %6.4f" $lamda] [format "| - Mu: %6.4f" $Mu] "| * Simulator started, please wait ..."

set scra [lindex $agent_addr 0] $ns at 0.1 "$scra offer" #----------------------------------------------------------set timeout [expr 100.0] $ns at $timeout "finish" $ns run #==================================================

MMNK.tcl source source source source source set set set set

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

server 5 capacity 10 lamda 16 Mu 1

#================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server capacity hold_rd scra $ns flush-trace set arr [$scra set Arrival_] set swa [$sw agent 0] set qu [$sw set queue] set sent [$swa set received] set lost [$swa set dropped] set delay [$swa set delayed] set A [expr ($lamda*1.0)/$Mu] set re [MMnK $A $server $capacity]

Phụ lục C: Code

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set tlost [expr [lindex $re 0]*100.0] set tdelay [expr [lindex $re 1]*100.0] set tq [expr [lindex $re 2]] set waittime [$qu set wait_time] set pktsout [$qu set pkts_out] puts stdout [format "| puts stdout [format "|

+ mean tm: %8.4f" [$hold_rd mean]] + mean lm: %8.4f" [expr 1.0/[$arr mean]]]

puts stdout [format "| + Model M/M/n/K <-> M/M/%i/%i" $server $capacity] puts stdout [format "| + A: %6.4f" [expr [$hold_rd mean]/[$arr mean]]] puts stdout [format "| + sent: %i lost: %i" $sent $lost] puts stdout [format "| + P{loss} : %8.4f%% -theory: %8.4f%%" [expr ($lost*100.0)/$sent] $tlost] puts stdout [format "| + P{delay}: %8.4f%% -theory: %8.4f%%" [expr ($delay*100.0)/$sent] $tdelay] puts stdout [format "| + tq : -theory: %8.4f" $tq] puts stdout [format "| + hold arg: %8.4f -theory: %8.4f" [expr ($waittime*1.0)/[expr $pktsout+$lost]] [expr $tq/$lamda]] puts stdout "----------------------------------------------------" exit } #=========================================================== #Chuong trinh chinh puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnK $server [expr $capacity-$server]] set hold_rd [new ExpRandom [expr 1.0/$Mu]] set lscr {} set set set set

scr [$ns node] item {} item [lappend item $scr 0 [expr 1.0/$lamda] $hold_rd] lscr [lappend lscr $item]

set agent_addr [$ns SetSwitchInput $sw $lscr] puts puts puts puts

stdout stdout stdout stdout

"| * Set up traffic" [format "| - lamda: %6.4f" $lamda] [format "| - Mu: %6.4f" $Mu] "| * Simulator started, please wait ..."

set scra [lindex $agent_addr 0] $ns at 0.1 "$scra offer" #----------------------------------------------------------set timeout 100 $ns at $timeout "finish" $ns run #==================================================

Binomial.tcl

Đề tài nghiên cứu khoa học

source source source source source

Phụ lục C: Code

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

set server 10 set lamda 0.20131 set Mu 0.3333 #================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server hold_rd agent_addr $ns flush-trace set set set set

swa [$sw agent 0] sent [$swa set received] lost [$swa set dropped] A [expr ($lamda*1.0)/$Mu]

puts stdout [format "|

+ mean tm: %8.4f" [$hold_rd mean]]

puts stdout [format "| + lm in each source:"] set sum 0 for {set i 0} {$i<$server} {incr i} { set scr [lindex $agent_addr $i] set arr [$scr set Arrival_] set lm [expr 1.0/[$arr mean]] set sum [expr $sum+$lm] puts stdout [format "| ~ scr (%i) :%8.4f" $i $lm] } puts stdout [format "| --> mean :%8.4f" [expr $sum/$server]] puts stdout [format "| + Model M/M/N/N/N <-> M/M/%i/%i/%i" $server $server $server] puts stdout [format "| + A: %6.4f" $A] puts stdout [format "| + sent: %i lost: %i" $sent $lost] puts stdout [format "| + P{loss}: %8.4f%% - thoery: %8.4f%%" [expr ($lost*100.0)/$sent] 0] puts stdout "----------------------------------------------------" exit } #=========================================================== #Chuong trinh chinh puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMNNN $server] set hold_rd [new ExpRandom [expr 1/$Mu]] set lscr {} for {set i 0} {$i<$server} {incr i} {

Đề tài nghiên cứu khoa học set set set set

scr($i) [$ns node] item {} item [lappend item $scr($i) 1 [expr 1.0/$lamda] $hold_rd] lscr [lappend lscr $item]

} set agent_addr [$ns SetSwitchInput $sw $lscr] puts puts puts puts

stdout stdout stdout stdout

"| * Set up traffic" [format "| - lamda: %6.4f" $lamda] [format "| - Mu: %6.4f" $Mu] "| * Simulator started, please wait ..."

for {set i 0} {$i<$server} {incr i} { $ns at 0.1 "[lindex $agent_addr $i] offer" } #----------------------------------------------------------set timeout [expr 4000.0/$lamda/$server] $ns at $timeout "finish" $ns run #==================================================

Engset.tcl source source source source source set set set set

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

server 5 customers 7 lamda 2.0 Mu 0.1

#================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server customers hold_rd agent_addr $ns flush-trace set set set set

Phụ lục C: Code

swa [$sw agent 0] sent [$swa set received] lost [$swa set dropped] a [expr ($lamda*1.0)/$Mu]

puts stdout [format "| + mean tm: %8.4f" [$hold_rd mean]] puts stdout [format "| + lm in each source:"] set sum 0 for {set i 0} {$i<$customers} {incr i} { set scr [lindex $agent_addr $i] set arr [$scr set Arrival_]

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set lm [expr 1.0/[$arr mean]] set sum [expr $sum+$lm] puts stdout [format "| ~ scr (%i) :%8.4f" $i $lm]

} puts stdout [format "|

--> mean :%8.4f" [expr $sum/$customers]]

puts stdout [format "| + Model M/M/n/n/N <-> M/M/%i/%i/%i" $server $server $customers] puts stdout [format "| + a: %6.4f" $a] puts stdout [format "| + sent: %i lost: %i" $sent $lost] puts stdout [format "| + P{loss}: %8.4f%% - thoery: %8.4f%%" [expr ($lost*100.0)/$sent] [expr [MMnnN $a $server $customers]*100.0]] puts stdout "----------------------------------------------------" exit } #=========================================================== #Chuong trinh chinh puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnnN $server $customers] set hold_rd [new ExpRandom [expr 1/$Mu]] set lscr {} for {set i 0} {$i<$customers} {incr i} { set scr($i) [$ns node] set item {} set item [lappend item $scr($i) 1 [expr 1.0/$lamda] $hold_rd] set lscr [lappend lscr $item] } set agent_addr [$ns SetSwitchInput $sw $lscr] puts puts puts puts

stdout stdout stdout stdout

"| * Set up traffic" [format "| - lamda: %6.4f" $lamda] [format "| - Mu: %6.4f" $Mu] "| * Simulator started, please wait ..."

for {set i 0} {$i<$customers} {incr i} { $ns at 0.1 "[lindex $agent_addr $i] offer" } #----------------------------------------------------------set timeout 1000 $ns at $timeout "finish" $ns run #==================================================

Engset_ex.tcl source source source source source

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

set server 5

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set customers 10 set lamda(0) 0.9 set lamda(1) 0.2 set lamda(2) 1.0 set lamda(3) 0.3 set lamda(4) 0.6 set lamda(5) 0.2 set lamda(6) 0.5 set lamda(7) 1.1 set lamda(8) 0.8 set lamda(9) 0.5 set Mu(0) [expr 1.0/3] set Mu(1) [expr 1.0/5] set Mu(2) [expr 1.0/4] set Mu(3) [expr 1.0/2] set Mu(4) [expr 1.0/3] set Mu(5) [expr 1.0/3] set Mu(6) [expr 1.0/5] set Mu(7) [expr 1.0/4] set Mu(8) [expr 1.0/5] set Mu(9) [expr 1.0/6] #================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu server customers hold_rd agent_addr $ns flush-trace set swa [$sw agent 0] set sent [$swa set received] set lost [$swa set dropped] puts stdout [format "| + In each source:"] for {set i 0} {$i<$customers} {incr i} { set scr [lindex $agent_addr $i] set arr [$scr set Arrival_] set lm [expr 1.0/[$arr mean]] set tm [$hold_rd($i) mean] puts stdout [format "| ~ %i : lm = %8.4f , tm = %8.4f" $i $lm $tm] } puts stdout [format "| + Model M/M/n/n/N <-> M/M/%i/%i/%i" $server $server $customers] puts stdout [format "| + sent: %i lost: %i" $sent $lost] puts stdout [format "| + P{loss}: %8.4f%% " [expr ($lost*100.0)/$sent]] puts stdout "----------------------------------------------------" exit } #=========================================================== #Chuong trinh chinh puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnnN $server $customers] for {set i 0} {$i<$customers} {incr i} { set hold_rd($i) [new ExpRandom [expr 1/$Mu($i)]] }

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set lscr {} for {set i 0} {$i<$customers} {incr i} { set scr($i) [$ns node] set item {} set item [lappend item $scr($i) 1 [expr 1.0/$lamda($i)] $hold_rd($i)] set lscr [lappend lscr $item] } set agent_addr [$ns SetSwitchInput $sw $lscr] puts stdout "| * Set up traffic" for {set i 0} {$i<$customers} {incr i} { puts stdout [format "| - Source (%i): lamda= %6.4f, (Mu= %6.4f -> tm = %6.4f)" $i $lamda($i) $Mu($i) [expr 1/$Mu($i)]] } puts stdout "| * Simulator started, please wait ..." for {set i 0} {$i<$customers} {incr i} { $ns at 0.1 "[lindex $agent_addr $i] offer" } #----------------------------------------------------------set timeout [expr 1000.0] $ns at $timeout "finish" $ns run #==================================================

PMR.tcl //mô hình palm’s machine repair source source source source source set set set set

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

server 5 customers 10 lamda 0.9 Mu [expr 1.0/3]

#================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server customers hold_rd agent_addr $ns flush-trace set swa [$sw agent 0] set sent [$swa set received]

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set lost [$swa set dropped] set delay [$swa set delayed] set a [expr ($lamda*1.0)/$Mu] set qu [$sw set queue] set waittime [$qu set wait_time] set pktsout [$qu set pkts_out] puts stdout [format "| $customers] puts stdout [format "|

+ Model M/M/n/N/N <-> M/M/%i/%i/%i" $server $customers + a (= lamda*tm): %6.4f" $a]

puts stdout [format "| + in each source:"] set suml 0 set sumt 0 set suma 0 for {set i 0} {$i<$customers} {incr i} { set scr [lindex $agent_addr $i] set arr [$scr set Arrival_] set lm [expr 1.0/[$arr mean]] set tm [$hold_rd($i) mean] set suml [expr $suml+$lm] set sumt [expr $sumt+$tm] set suma [expr $suma+[expr $lm*$tm]] puts stdout [format "| ~ %i : (lm = %8.4f, tm = %8.4f) --> a = %8.4f" $i $lm $tm [expr $lm*$tm]] } puts stdout [format "| --> mean: (lm = %8.4f, tm = %8.4f) --> a = %8.4f" [expr $suml/$customers] [expr $sumt/$customers] [expr $suma/$customers]] puts stdout puts stdout puts stdout puts stdout $pktsout+$lost]]]

[format [format [format [format

"| "| "| "|

+ + + +

sent: %i lost: %i delay: %i" $sent $lost $delay] P{loss} : %8.4f%% " [expr ($lost*100.0)/$sent]] P{delay}: %8.4f%% " [expr ($delay*100.0)/$sent]] hold arg: %8.4f" [expr ($waittime*1.0)/[expr

puts stdout "----------------------------------------------------" exit

} #=========================================================== #Chuong trinh chinh

puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnNN $server $customers] set lscr {} for {set i 0} {$i<$customers} {incr i} { set hold_rd($i) [new ExpRandom [expr 1/$Mu]] set scr($i) [$ns node] set item {} set item [lappend item $scr($i) 1 [expr 1.0/$lamda] $hold_rd($i)] set lscr [lappend lscr $item] } set agent_addr [$ns SetSwitchInput $sw $lscr] puts stdout "| * Set up traffic" puts stdout [format "| - lamda: %6.4f" $lamda]

Đề tài nghiên cứu khoa học

Phụ lục C: Code

puts stdout [format "| - Mu: %6.4f" $Mu] puts stdout "| * Simulator started, please wait ..." for {set i 0} {$i<$customers} {incr i} { $ns at 0.1 "[lindex $agent_addr $i] offer" } #----------------------------------------------------------set timeout 1000 $ns at $timeout "finish" $ns run #==================================================

Mô hình tổng quát M/M/n/K/N – phục vụ cho bài toán ví dụ source source source source source

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

set server 30 set queue 60 #set customers 4 set set set set

area_pop(0) area_pop(1) area_pop(2) area_pop(3)

set set set set

lamda(0) lamda(1) lamda(2) lamda(3)

set set set set

Mu(0) Mu(1) Mu(2) Mu(3)

45; 48; 60; 180;

0.01 0.13 0.09 0.02

[expr [expr [expr [expr

1.0/3] 1.0/4] 1.0/5] 1.0/2]

#================================================= proc monitor {} { global ns percent monitor_period set now [$ns now] set percent [expr $now/4000*100] puts stdout [format "%6.0f %%..." $percent] $ns at [expr $now+$monitor_period] "monitor"

} #================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server hold_rd agent_addr K pop $ns flush-trace

Đề tài nghiên cứu khoa học set set set set

Phụ lục C: Code

swa [$sw agent 0] sent [$swa set received] lost [$swa set dropped] delay [$swa set delayed]

set qu [$sw set queue] set waittime [$qu set wait_time] set pktsout [$qu set pkts_out] puts stdout puts stdout puts stdout puts stdout puts stdout $pktsout+$lost]]]

[format [format [format [format [format

"| "| "| "| "|

+ + + + +

Model M/M/n/N/K <-> M/M/%i/%i/%i" $server $K $pop] sent: %i lost: %i delay: %i" $sent $lost $delay] P{loss} : %8.4f%% " [expr ($lost*100.0)/$sent]] P{delay}: %8.4f%% " [expr ($delay*100.0)/$sent]] hold arg: %8.4f" [expr ($waittime*1.0)/[expr

puts stdout "----------------------------------------------------" exit

} #=========================================================== set percent 0; set monitor_period [expr 4000*0.05]; #Chuong trinh chinh

puts stdout "----------------------------------------------------" set pop 0 for {set i 0} {$i<4} {incr i} { set pop [expr $pop+$area_pop($i)]; } set K [expr $queue + $server] set sw [$ns BuildSwitch MMnKN $server $K $pop] set lscr {} set c 0 for {set i 0} {$i<4} {incr i} { set hold_rd($i) [new ExpRandom [expr 1/$Mu($i)]] for {set j 0} {$j<$area_pop($i)} {incr j} { set scr($c) [$ns node] set item {} set item [lappend item $scr($c) 1 [expr 1.0/$lamda($i)] $hold_rd($i)] set lscr [lappend lscr $item] }

set c [expr $c+1]

} set agent_addr [$ns SetSwitchInput $sw $lscr] puts stdout "| * Set up traffic" for {set i 0} {$i<4} {incr i} { puts stdout [format "| - area (%i) : pop = %3i lamda = %6.4f, tm = %6.4f --> a = %6.4f" $i $area_pop($i) $lamda($i) [expr 1.0/$Mu($i)] [expr $lamda($i)/$Mu($i)]] } puts stdout "| * Simulator started, please wait ..." for {set i 0} {$i<$pop} {incr i} {

Đề tài nghiên cứu khoa học $ns at 0.1 "[lindex $agent_addr $i] offer" } $ns at 0.1 "monitor" #----------------------------------------------------------set timeout 4000.0 $ns at $timeout "finish" $ns run #==================================================

PMR_ex.tcl // Palm’s machne repair mở rộng source source source source source

MyQueue.tcl SWA.tcl Simulator-Config.tcl MyTraffic.tcl QueueThoery.tcl

set set set set set set set set set set set set

server 5 customers 10 lamda(0) 0.9 lamda(1) 0.2 lamda(2) 1.0 lamda(3) 0.3 lamda(4) 0.6 lamda(5) 0.2 lamda(6) 0.5 lamda(7) 1.1 lamda(8) 0.8 lamda(9) 0.5

set set set set set set set set set set

Mu(0) Mu(1) Mu(2) Mu(3) Mu(4) Mu(5) Mu(6) Mu(7) Mu(8) Mu(9)

[expr [expr [expr [expr [expr [expr [expr [expr [expr [expr

1.0/3] 1.0/4] 1.0/5] 1.0/2] 1.0/7] 1.0/3] 1.0/4] 1.0/5] 1.0/3] 1.0/6]

#================================================= proc finish {} { puts stdout "| finished !" puts stdout "| -------------------" puts stdout "| * Result:" global ns sw Mu lamda server customers hold_rd agent_addr $ns flush-trace set set set set

swa [$sw agent 0] sent [$swa set received] lost [$swa set dropped] delay [$swa set delayed]

Phụ lục C: Code

Đề tài nghiên cứu khoa học

Phụ lục C: Code

set qu [$sw set queue] set waittime [$qu set wait_time] set pktsout [$qu set pkts_out] puts stdout [format "| + in each source:"] for {set i 0} {$i<$customers} {incr i} { set scr [lindex $agent_addr $i] set arr [$scr set Arrival_] set lm [expr 1.0/[$arr mean]] set tm [$hold_rd($i) mean] puts stdout [format "| ~ %i : (lm = %8.4f, tm = %8.4f) --> a = %8.4f" $i $lm $tm [expr $lm*$tm]] } puts stdout $customers] puts stdout puts stdout puts stdout puts stdout $pktsout+$lost]]]

[format "|

+ Model M/M/n/N/N <-> M/M/%i/%i/%i" $server $customers

[format [format [format [format

+ + + +

"| "| "| "|

sent: %i lost: %i delay: %i" $sent $lost $delay] P{loss} : %8.4f%% " [expr ($lost*100.0)/$sent]] P{delay}: %8.4f%% " [expr ($delay*100.0)/$sent]] hold arg: %8.4f" [expr ($waittime*1.0)/[expr

puts stdout "----------------------------------------------------" exit

} #=========================================================== #Chuong trinh chinh

puts stdout "----------------------------------------------------" set sw [$ns BuildSwitch MMnNN $server $customers] set lscr {} for {set i 0} {$i<$customers} {incr i} { set hold_rd($i) [new ExpRandom [expr 1/$Mu($i)]] set scr($i) [$ns node] set item {} set item [lappend item $scr($i) 1 [expr 1.0/$lamda($i)] $hold_rd($i)] set lscr [lappend lscr $item] } set agent_addr [$ns SetSwitchInput $sw $lscr] puts stdout "| * Set up traffic" for {set i 0} {$i<$customers} {incr i} { puts stdout [format "| - scr (%i) : lamda = %6.4f, tm = %6.4f --> a = %6.4f" $i $lamda($i) [expr 1.0/$Mu($i)] [expr $lamda($i)/$Mu($i)]] } puts stdout "| * Simulator started, please wait ..." for {set i 0} {$i<$customers} {incr i} { $ns at 0.1 "[lindex $agent_addr $i] offer" } #----------------------------------------------------------set timeout [expr 4000.0] $ns at $timeout "finish" $ns run #==================================================

Đề tài nghiên cứu khoa học

Tài liệu tham khảo

Tài liệu tham khảo 1. Handbook “TELETRAFFIC ENGINEERING” – ITU-D – study group 2 – Jan/2005 2. AT77.05 Teletraffic Engineering/TE 14.09.2003 – Học viện công nghệ châu Á 3. Practical Programming in Tcl and Tk, Fourth Edition. By Brent B. Welch, Ken Jones, Jeffrey Hobbs 4. Tài liệu Networking laboratory – Helsinki University of Technology – Jan/2006 - Kendall 5. The ns Manual (formerly ns Notes and Documentation) - UC Berkeley, LBL, USC/ISI, and Xerox PARC. Kevin Fall [email protected], Editor. Kannan Varadhan [email protected]. Editor. July 24, 2006 6. NS Simulator for beginner - Eitan Altman and Tania Jiménez – Dec/2/2003