Đề cương bài giảng môn kỹ thuật chuyển mạch phần các kỹ thuật chuyển mạch gói

ĐỀ CƯƠNG BÀI GIẢNG MÔN KỸ THUẬT CHUYỂN MẠCH Phần CÁC KỸ THUẬT CHUYỂN MẠCH GÓI Chương 1 LÝ THUYẾT XẾP HÀNG Tóm tắt Xếp hàng là gì? Các nguyên tắc cơ bản của lý thuyết xếp hàng Các yếu tố trực giác Các thành phần của 1 hàng đợi Ký hiệu của hàng đợi Các phân bố xác suất Các phương pháp phân tích hàng đợi Giá trị trung bình và biến thiên Các thông số đo lường hiệu suất của một hàng đợi Một số thuật ngữ chung về hàng đợi Các hệ thống hàng đợi cơ bản Mô hình hàng đợi M/M/1 Mô hình M/M/1/K, luật xếp hàng FIFO M/M/c M/M/c/K So sánh mô hình M/M/1 và M/M/c Mô hình M/M/c/c ( phương trình Erlange B) Các hàng đợi với nguồn hạn chế Các hàng đợi có luật phục vụ phụ thuộc trạng thái (State Dependent Service) Các hàng đợi với 2 kiểu lưu lượng đến Các hàng đợi Impatience Các mô hình Erlange (M/Ek/1 và Ek/M/1) Các hệ thống hàng đợi tiên tiến M/G/1 M/G/c và M/G/c/c G/M/1 G/G/1 Các mô hình khác Mô phỏng Các ứng dụng Kết luận Tham khảo Các thuật ngữ và từ viết tắt về hàng đợi Đặt vấn đề Không giống các bộ chuyển mạch kênh, các chuyển mạch gói cần các bộ nhớ đệm để lưu các gói đầu vào không biết trước. Thậm chí khi mà luồng gói vào chuyển mạch là biết trước thì cũng rất cần có bộ đệm đề phòng trường hợp trường chuyển mạch ( Switch Fabric) hoặc các trung kế ra bận để đảm bảo không mất gói. Các bộ đệm này có thể được đặt trước hoặc sau trường chuyển mạch hoặc tại một vị trí chung mà có thể truy nhập được cả từ cổng vào lẫn cổng ra. Tuy nhiên một vấn đề quan trọng là cách quản lý các bộ đệm này như thế nào để vừa đảm bảo một chi phí thấp (dung lượng bộ đệm) mà lại vừa đảm bảo được hiệu suất cũng như quyền ưu tiên của từng loại lưu lượng khác nhau. Người ta đã đưa ra một lý thuyết gọi là “ Lý thuyết xếp hàng” tiếng anh là “Queuing System” trong đó quy định cách thông tin được lưu vào bộ đệm và cách đọc chúng ra cũng như các luật quản lý thông tin lưu trong nó. Sau đây sẽ nghiên cứu kỹ về các mô hình hàng đợi chủ yếu trong lĩnh vực thông tin và viễn thông. Trong khoá học này sinh viên sẽ hiểu biết và giải thích được các khái niệm cơ bản về lý thuyết hàng đợi bao gồm: mật độ phân bố của một nguồn thông tin nói chung, phân bố thời điểm đến của các yêu cầu trong một hệ thống thông tin, các luật quản lý hàng đợi, cơ chế phục vụ, các kiểu hệ thống hàng đợi, và các chỉ số đo hiệu suất của hệ thống. Ngoài ra sinh viên cũng sẽ được nghiên cứu về các mô hình hàng đợi cơ bản cũng như tiên tiến. Định nghĩa & các khái niệm trong lý thuyết xếp hàng 2.1. Định nghĩa : Lý thuyết xếp hàng là 1 phần của lý thuyết xác suất thống kê, nó được định nghĩa là 1 bộ các quy tắc và luật (discipline) đề cập đến việc tắc nghẽn và phương pháp giải quyết tắc nghẽn như: dự đoán độ trễ, trễ bé nhất, độ dài hàng đợi và số server cần thiết trong 1 hệ thống thông tin. Lý thuyết hàng đợi có rất nhiều ứng dụng từ việc nghiên cứu lưu lượng xe cộ trên đường phố, phương thức phục vụ khách hàng (tại các siêu thị, bệnh viện, nhà băng,...) cho đến các hệ thống thông tin. ở đây chỉ tập trung nêu lên các ứng dụng của lý thuyết hàng đợi trong các hệ thống thông tin nói chung và trong các chuyển mạch gói nói riêng. Bảng sau đây nêu lên mối quan hệ giữa một số mô hình liên quan với nhau: Mô hình Định nghĩa Xác suất Là luật nghiên cứu các sự kiện mà đầu ra của chúng không xác định Hàng đợi Là luật nghiên cứu tắc nghẽn và trễ khi các yêu cầu phục vụ đến hệ thống một cách ngẫu nhiên Teletraffic Là lý thuyết nghiên cứu các hàng đợi trong môi trường thông tin thoại và dữ liệu Thống kê Là luật nghiên cứu việc tập hợp dữ liệu trong các môi trường xác suất bất kỳ Viễn thông, truyền thông số liệu, các hệ thống máy tính là các ví dụ trong đó các nguồn tài nguyên của chúng là thiết bị, đường truyền, ... thường bé hơn số thực thể yêu cầu sử dụng chúng, điều này có nghĩa là 1 số user sẽ phải đợi cho đến khi các user khác giải phóng tài nguyên họ đang chiếm hoặc có thể bị từ chối phục vụ. Phân tích hàng đợi đã trở thành cơ sở cho việc thiết kế và quản lý hệ thống như trên. Sau đây liệt kê tóm tắt một số ví dụ thông tin viễn thông và thông tin số liệu ứng dụng lý thuyết xếp hàng trong hoạt động của chúng: Trễ trong các mạng Ethernet (LAN) Thời gian lổi trung bình của các card giao tiếp thuê bao của các PBX Các bộ đệm gói tại các PAD Hiệu suất của một máy chủ quản lý các printer trong 1 mạng LAN Các đường trung kế T1/E1 nối giữa các tổng đài PBX Xác suất tắc nghẽn cuộc gọi của một tổng đài PBX Các cuộc gọi chờ trong các tổng đài PBX với LCR (Least Cost Routing) Chất lượng các hệ thống thoại được gói hoá ..... Các khái niệm & ký hiệu cơ bản về hàng đợi Các nhân tố nhận giạng bằng trực giác hệ thống hàng đợi Xem xét việc thiết kế một nhóm các đường trung kế giữa 2 tổng đài điện thoại. Mỗi tổng đài có thể có hàng nghìn thuê bao. Tất nhiên người ta sẽ không dùng hàng nghìn đường trung kế để nối 2 tổng đài này với nhau. Mà thực tế người ta làm như sau: trung bình chỉ có khoảng 5% khách hàng yêu cầu được phục vụ cùng 1 lúc, trong đó lại chỉ có khoảng 50% khách hàng cần kết nối với các thuê bao ở tổng đài bên kia và ngược lại. Ví dụ, nếu mỗi tổng đài có 5000 đường thuê bao, thì chỉ có 125 (5000 x 5% x 50%) thuê bao sử dụng các đường trung kế nối 2 tổng đài theo mỗi hướng có nghĩa là trung bình có tổng cộng 250 thuê bao sử dụng đường trung kế cùng lúc, do đó người thiết kế chỉ cần thiết kế hệ thống đảm bảo được yêu cầu trung bình này. Gọi số đường trung kế cần thiết này là E. Tại một thời điểm bất kỳ khi mà số thuê bao cùng nhấc máy gọi lớn hơn giá trị E này thì số lượng thuê bao lớn hơn đó sẽ phải đợi. Vì hệ thống chỉ được thiết kế để phục vụ E thuê bao tại mỗi thời điểm. Tương tự như vậy cũng có một số thời điểm mà số yêu cầu kết nối cuộc gọi đồng thời bé hơn giá trị E. Và điều không may là giá trị dư ra này lại không thể để dành để phục vụ số khách hàng dôi ra khi số yêu cầu kết nối lớn hơn E. Số lượng khách hàng dôi ra cũng như khả năng hệ thông dôi ra ở trên gọi là giá trị biến thiên V. Bằng trực giác có thể thấy nếu lượng biến thiên số yêu cầu đến càng lớn thì trễ sẽ càng lớn. Ví dụ nếu giá trị trung bình E là 20, và giá trị biến thiên là 2, thì tại một số thưòi điểm lượng yêu cầu đến là 18, tại một số thời điểm khác lại là 22. ở đây lượng quá tải là khá bé nên trễ chờ được phục vụ cũng bé. Tuy nhiên nếu giá trị biến thiên tăng lên 10, thì lượng yêu cầu phải chờ tại một số thời điểm là 10, điều này sẽ gây ra một trễ khá lớn. Biến thiên của các yêu cầu đến một hệ thống thông tin được điều khiển bởi một luật được gọi là “ Phân bố thời điểm đến” Ngoài việc phụ thuộc vào phân bố thời điểm đến của các yêu cầu, trễ thông tin còn phụ thuộc vào hàm thời gian phục vụ của hệ thống. Tức phụ thuộc vào thời gian phục vụ một yêu cầu là bao lâu, tuy nhiên thời gian phục vụ này là không giống nhau đối với mọi yêu cầu. Sự phụ thuộc này được điều khiển bởi một luật gọi là “ Phân bố thời gian phục vụ” Các thành phần của 1 hệ thống hàng đợi Môi trường hàng đợi là 1 hệ thống mà trong đó có tắc nghẽn xảy ra vì lượng tài nguyên ít hơn số yêu cầu phục vụ đồng thời. Mô hình hàng đợi là 1 tóm tắt về toán học của 1 tình huống thực tế nào đó với mục đích là cung cấp phương tiện biểu diển để định lượng hiệu suất của các luồng thông tin ( Telephone call, Data packets, LAN token,...) khi đi qua các bộ đệm. Khi xem xét một hệ thống hàng đợi nói riêng mà một hệ thống tắc nghẽn nói chung người ta quan tâm đến 7 tham số sau: Tổ hợp các loại yêu cầu khác nhau đến , nếu có nhiều hơn 1 loại yêu cầu đến hệ thống hàng đợi. Ví dụ, tại một cửa hàng thì các khách hàng nữ tạo thành 1 loại và khách hàng nam tạo thành 1 loại. Vì thời gian phục vụ của mỗi loại yêu cầu có thể khác nhau Phân bố thời điểm đến của từng loại yêu cầu Độ lớn luồng lưu lượng đến của từng loại yêu cầu Phân bố thời gian phục vụ của các hệ thống hàng đợi. Trong nhiều hệ thống thông tin, điều này tương đương với phân bố chiều dài cuộc gọi Phương pháp quản lý hàng đợi: FIFO, Random Order, Priorities,... Chiều dài tối đa của hàng đợi (liên quan đến dung lượng bộ đệm) Phản ứng của các yêu cầu bị trễ (gọi lại, huỷ yêu cầu,...) Ký hiệu của các hệ thống hàng đợi Một hệ thống hàng đợi thường được ký hiệu như sau: A/B/m/K/p A : tên mã của phân bố thời gian đến hàng đợi của các yêu cầu B : tên mã của phân bố thời gian phục vụ của hàng đợi m : là số server rỗi của hệ thống hàng đợi K : số vị trí rỗi trong bộ đệm p : số yêu cầu tối đa mà một hệ thống hàng đợi có thể phục vụ được ( ví dụ một cửa hàng bán mỹ phẩm ở Hà Nội lượng khách tối đa là 100 người chẳng hạn) Khi không cần thiết thì 1 hoặc 2 tham số cuối được bỏ đi Sau đây minh hoạ một số kiểu hệ thống hàng đợi thường gặp trong các hệ thống thông tin: Hình 1: Các hệ thống hàng đợi thông dụng trong viễn thông Một số kiểu phân bố thường gặp trong nhiều hệ thống viễn thông gồm: Kiểu “không nhớ” và có tên mã là M (cũng được gọi là kiểu phân bố theo hàm mũ): phân bố này có nghĩa là xác suất mà một yêu cầu đến và đã đợi được T phút phải đợi thêm Z phút nửa cũng bằng xác suất mà 1 yêu cầu khác vừa mới đến cũng phải đợi Z phút (có nghĩa nó không nhớ rằng có 1 yêu cầu đã đợi được T phút rồi). Điển hình của kiểu này là lưu lượng Internet (các gói đến 1 Router) Phân bố kiểu Erlange tầng r , tên mã là E[r]: giống quy luật các cuộc gói đến tổng đài PSTN hàm xác suất Erlange Phân bố kiểu Hyperexponential tầng r, tên mã là H[r] Và kiểu phân bố xác định, tên mã D ( quy luật đến đã biết trước) Một phân bố chung thường được gọi là G Một số mô hình hàng đợi điển hình liên quan đến các hệ thống viễn thông: Hệ thống hàng đợi 1 server với phân bố thời gian đến ngẫu nhiên (memoryless), phân bố thời gian phục vụ ngẫu nhiên. Ví dụ, các hệ thống Communication Servers như: hệ thông hộp thư thoại (Voice Mail Server) trong các tổng đài PBX, hay một hệ thống thư điện tử trong các mạng LAN. Hệ thống giống trường hợp trên nhưng có c server. Ví dụ, nhóm gồm c đường trung kế Tie line nối giữa các PBX hoặc các cổng quay số trong các hệ thống modem truy nhập từ xa của các nhà cung cấp dịch vụ Internet. Hệ thống hàng đợi có một server với phân bố thời gian đến của các yêu cầu là ngẫu nhiên, phân bố thời gian phục vụ cố định. Ví dụ, dịch vụ các cổng ra trong 1 thiết bị chuyển mạch gói (Routers, Switches) Các phân bố xác suất Trong các hệ thống xác suất hoặc hệ thống hàng đợi ngẫu nhiên, các thời điểm đến của các yêu cầu và thời gian phục vụ từng yêu cầu là không biết trước. Do đó các thực thể đó hoàn toàn phải xác định bằng phân bố xác suất. Trong lý thuyết xác suất thì một sự kiện không thể yêu cầu một kết quả duy nhất mà là một số khả năng có thể. Phân bố xác suất liệt kê các trường hợp có thể đó. Các phân bố thời gian đến và thời gian phục vụ trong các hệ thống hàng đợi chia thành 2 kiểu: rời rạc và liên tục. Các phân bố rời rạc là các phân bố mà trong khoảng thời gian xét có một số lượng sự kiện không thể đếm được ( ở đây khác vô hạn). Còn các phan bố liên tục là các phân bố mà khoảng thời gian xét được tạo bởi vô hạn điểm. Các kiểu phân bố và đặc tính của chúng được mô tả trong lý thuyết xác suất, ở đây không xét chi tiết. Tất nhiên, chỉ xác định kiểu phân bố không thôi chưa đủ mà phải xác định tất cả cả hoặc một số thông số mô tả phân bố đó. Ví dụ, có thể có hệ thống ngẫu nhiên (Memoryless) với trung bình 5 hoặc 15 yêu cầu đến trong một đơn vị thời gian. Một số phân bố yêu cầu nhiều hơn 1 thông số. Sau đây chúng ta xét một ví dụ về phân bố xác suất: Ví dụ (phân bố rời rạc): Trễ trong một mạng LAN kiểu Ethernet Hệ thống bus chung trong mạng LAN được chi khe thời gian với độ dài bằng nhau. Một khe tương ứng với thời gian để truyền một gói kích thước cố định. Vì có nhiều user trên bus cùng cố gắng chiếm 1 khe thời gian nên va chạm có thể xảy ra và khi đó sẽ không thể truyền dữ liệu. Khi bộ điều khiển truyền thông của một user phát hiện ra rằng dữ liệu của nó bị va chạm, nó sẽ định lại lịch trình phát của nó trong một khe thời gian sắp tới ( trượt từ khe thời gian hiện thời một số khe). Giả sử rằng tại một khe thời gian bất kỳ một bộ điều khiển sẽ truyền một gói đang ùn tắc của nó với xác suất p = 0.1 và không truyền với xác suất là 0.9. Phân bố điều khiển quá trình trên là phân bố hình học. Phân bố này có không gian xét là tập các số nguyên (danh sách các đầu ra có thể ); xác suất xảy ra số nguyên i là p(1-p)[i], với p là thông số cho trước giữa 0 và 1. Giả sử rằng chiều dài khe thời gian là 50ms. Ta sẽ có: Xác suất gói được truyền lại trong khe thời gian 0 là: (0.1)(0.9)[0] = 0.100 Xác suất gói được truyền lại trong khe thời gian 1 là: (0.1)(0.9)[1] = 0.090 Xác suất gói được truyền lại trong khe thời gian 2 là: (0.1)(0.9)[2] = 0.081 Xác suất gói được truyền lại trong khe thời gian 3 là: (0.1)(0.9)[3] = 0.072 Xác suất gói được truyền lại trong khe thời gian 4 là: (0.1)(0.9)[4] = 0.065, vv..... ( Truyền lại trong khe thời gian 0 có nghĩa là khe thời gian theo sau ngay lập tức khe thời gian vời xảy ra va chạm ). Số lượng khe thời gian trung bình trước khi truyền lại sẽ là (1-p)/p = 0.9/0.1 = 9. Do đó tổng thời gian trung bình cho một cố gắng truyền lại sẽ là 9 x 45 = 450ms. Kỹ thuật này cũng được sử dụng trong các hệ thống thông tin dạng cụm của Motorola. Nó cũng được sử dụng trong các hệ thống VSAT (Very Small Aperturre Terminal) truyền thoại và dữ liệu. Các phương pháp phân tích 1 hệ thống hàng đợi Khi phân tích 1 hệ thống hàng đợi thì tuỳ thuộc vào kiểu phân bố thời gian đến của các yêu cầu và phân bố thời gian phục vụ là xác định trước hay ngẫu nhiên mà có phương pháp phân tích cụ thể. Tuy nhiên các hệ thống thực tế được phân tích dựa vào 2 trường hợp gần đúng sau đây: Phần lớn các yêu cầu đến theo 1 quy luật có thể biết trước, chỉ 1 số là ngẫu nhiên. Các công cụ của lý thuyết xác suất đã chứng minh được rằng đối xử của hệ thống đối với phần lớn các yêu cầu phục vụ là có thể đoán trước 1 cách chính xác, gần với trường hợp xác định. Giá trị trung bình và biến thiên Trong lý thuyết xác suất thì xác suất xảy ra của một trong các sự kiện: x [1] , x [2], x [3], ..., x [n] Là: p [1], p [2], p [ 3], ..., p [n] Giá trị trung bình của phân bố các giá trị xác suất trên là E(X), gọi là giá trị mong muốn được tính như sau: E(X) = x [1]p [1] + x [2]p [2] + x [3 ]p [3] + ... + x [n] p [n] = x [i]p [i] Dung sai của phân bố ( nghĩa là sai lệnh giữa 1 giá trị xác suất bất kỳ với giá trị trung bình trên là: V(X) = (E(X2) - E(X)2 ) Theo công thức trên ta có: E(X2) = x [1]2 p [1] + x [2]2p [2] + x [3]2p [3 ] + ... + x [n]2 p [n] = x [i]2 [Pi]. Ví dụ: Tung con súc sắc, phân bố sự kiện này như sau: Sự kiện (số của mặt) Xác suất 1 1/6 2 1/6 3 1/6 4 1/6 5 1/6 6 1/6 Giá trị trung bình (giá trị mong muốn) của một số (từ 1 đến 6) trên mặt con súc sắc là: E(X) = 1 x 1/6 + 2 x 1/6 + 3 x 1/6 + 4 x 1/6 + 5 x 1/6 + 6 x 1/6 = 3.5 Giá trị biên thiên được tính như sau: trước hết tính E(X2) = 1x1 x 1/6 + 2 x 2 x 1/6 + 3 x3 x 1/6 + 4 x 4 x 1/6 + 5 x 5 x 1/6 + 6 x 6 x 1/6 = 15.16 V(X) = 15.16 – (3.5)2 = 2.91 Các yếu tố đánh giá hiệu suất của 1 hệ thống hàng đợi Người ta dựa vào các thông số sau để đánh giá hiệu suất hoặc tính hiệu quả của 1 hệ thống hàng đợi: Thời gian đợi của mổi yêu cầu trong hàng đợi Số yêu cầu trong hàng đợi Khoảng thời gian bận của hệ thống Chiều dài thời gian rỗi Các công việc đang bị ùn lại Phân bố đầu ra (quan trọng đối với hệ thống hàng đợi gồm nhiều bộ đệm nối tiếp nhau) Một số thuật ngữ trong lý thuyết xếp hàng Hệ số sử dụng Hệ số sử dụng là tỉ số giữa tốc độ công việc đưa vào hệ thống và tốc độ tối đa (dung lượng) mà hệ thống có thể thực hiện công việc này. Tiếng hy lạp ký hiệu tỉ số này là: rho (0 £ rho £ 1). rho là một thông số đặc tính quan trọng của 1 hệ thống hàng đợi, khi nó tiến gần tới 1 thì trễ trong hàng đợi sẽ trở nên rất lớn (vô cùng). Công việc mà một yêu cầu đưa đến cho hệ thống bằng thời gian mà hệ thống phục vụ nó. Do đó đối với 1 hệ thống hàng đợi đơn server chúng ta có: rho = (tốc độ đến trung bình của các yêu cầu ) x (thời gian phục vụ trung bình) Phân bố thời gian đến của các yêu cầu A có giá trị mong muốn (trung bình) là t[bar], là khoảng thời gian trung bình giữa các yêu cầu khác nhau đến hệ thống, hàm nghịch đảo của nó là 1/ t[bar] được ký hiệu theo ký tự hy lạp l là tốc độ đến trung bình của các yêu cầu. Do đó: rho = (l) x (thời gian phục vụ trung bình) Để cho tiện người ta ký hiệu giá trị của thời gian phục vụ trung bình là x [bar]. Nên: rho = l x (x [bar]) Một hệ thống hàng đợi đơn server có dung lượng tối đa để thực hiện công việc mà tương đương với 1 giây mỗi giây, và mỗi yêu cầu đến mang theo 1 lượng công việc bằng x [bar] giây. Có thể viết: rho = l x (1/x [bar]) Ký hiệu: mu = 1/ x [bar] rho = l /mu Đối với 1 hệ thống hàng đợi có m server thì: rho = l x (x [bar])/m Một số mô hình hàng đợi điển hình trong viễn thông và chuyển mạch gói Các hệ thống hàng đợi cơ bản được tóm tắt trong bảng sau: Tóm tắt một số kết quả L = Chiều dài trung bình của hàng đợi W = Trễ trung bình [c - 1] M/M/1 p [0] = 1/{[ 1/{[(r) [n]/n!] + [r [c] /c!] L = l/(mu - l). [n = 0] W = 1/(mu - l). [1 - s [K - c + 1]]/[1 - s]}, khi s không M/M/1/K bằng 1, p [n] = (rho) [ n] (1 - rho)/[1 - (rho) [K+1]], khi [c -1] rho < 1, và p [0] = 1/{[10 (r) [n ]/n!] + (r [c]/c!)(K - c + 1)}, p [n] = 1/(K + 1), khi rho = 1. n = 0 L = (rho)(g/h), với khi s bằng 1. g = [1 - (K + 1) Lq = + K(rho)K + 1], và (rho) [K] Lq = h = [1 - (rho) [K + 1]] (1 - rho). {p [0][(c)(rho)] [c]rho} h = [1 - (rho) [K + 1]] (1 - rho) {1 - (rho) [K - c + 1] - W = L/[(l)(1 - p [K])]. (1 - rho)(K - c + 1)(rho) [K - c]}/ M/M/c {c!(1 - rho) [ 2]}; rho = l/(c)(mu). L: the algebraic expression is too long to show pn = (l)np0/[n!(mu)n], khi n nằm ở đây, xấp xĩ L [q] + c. giữa 1 và c, và W [q ]= L [q] /[(l)(1 - p [K])]. p [n] = (l) [n]p [0]/[(c) [n - c]c!(mu) [n]], khi n M/M/c/c vượt quá c. (Erlang B) c – 1 c p [0] = 1/[(;bccf10r [n]n!) + cr [c]/c!(c - r)]. pc = {[(c)(rho)] [ c]/c!}/{[10[(c)(rho)] [n]/n!], with [n = 0] [n = 0] W = (r [ c](mu)/(c - 1)![c(mu) - l] [2] }p [0] + rho = (l)/[(c)(mu)]. 1/mu; M/E [k ]/1 L = (l)W. Wq = [(k + 1)/(2k)] [l/(mu) M/M/c/K (mu – l)]. r = l/mu, và Lq = (l)W [q] (from Little's result). s = l/(c)(mu) = rho. p [n] = [1/n!](r) [n]p [0], when n is between 1 and c, and M/G/1 p [n] = [1/(c) [n - c] c!](r) [n]p [0], khi n nằm giữa c và K. L = (rho) + [(rho) [2] + (l) [2](s [B] [2])]/ [2(1 - rho)] với s [B] [2] = V(B) = E(B [2] ) - E(B) [2] W = L/(l) W [q ] = W - 1/(mu) L [q] = L - (l)/(mu) M/M/1 Đây là hệ thống hàng đợi đơn server, các yêu cầu đến phân bố theo hàm mũ, luật quản lý hàng đợi là FIFO. Do đó xác suất có n yêu cầu đến hệ thống là: p [n] = (rho) [n](1 - rho) Và số yêu cầu trung bình trong hệ thống là: L = rho/(1 - rho) Số yêu cầu trong hàng đợi là: L [q] = (rho) [2]/(1 - rho) Thời gian đợi trung bình trong hàng đợi là: W [q] = (l)/[mu(mu - l)] Thời gian tổng cộng trung bình trong hệ thống là: W = 1/(mu - l) Ví dụ: Xem xét 1 hệ thống hộp thư thoại (Voice Mail) của các tổng đài PBX. Có một số lượng lớn user yêu cầu truy nhập hệ thống hộp thư thoại này, với phân bố thời gian đến của các yêu cầu này là theo hàm mũ (ngẫu nhiên) và thời gian trung bình giữa các yêu cầu là 500 ms. Thời gian trung bình truy nhập cơ sở dữ liệu của hệ thống Voice Mail là 475 ms. Hỏi các user sẽ nhận được kiểu phục vụ như thế nào? ở đây, t [bar] = 0.500 và x [bar] = 0.475, do đó lambda = (1/t [bar]) = 2.0 và mu = (1/x [bar]) = 2.105 vậy rho = l/mu = 0.95 Xác suất để n user truy nhập hệ thống Voice mail cùng 1 lúc là: p [n] = (rho) [n](1 - rho) = (0.95) [n](0.05) Do đó: Xác suất mà 0 có user nào truy nhập là: p [0] = 0.05 Xác suất mà 1 có user nào truy nhập là: p [1] = 0.0475 Xác suất mà 0 có user nào truy nhập là: p [0] = 0.0451 ..... Số user trung bình đợi trong hệ thống là: L = rho/(1 - rho) = 0.95/0.05 = 19 Thời gian tổng cộng trung bình trong hệ thống là: W = 1/(mu - l) = 1/(0.500 - 0.475) = 40 giây Thời gian này l