ĐỀ CƯƠNG BÀI GIẢNG MÔN KỸ THUẬT CHUYỂN MẠCH

Chia sẻ: Nguyễn Trung Thành | Ngày: | Loại File: DOC | Số trang:18

Thêm vào BST

Báo xấu

263
lượt xem 97
download

ĐỀ CƯƠNG BÀI GIẢNG MÔN KỸ THUẬT CHUYỂN MẠCH

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: ĐỀ CƯƠNG BÀI GIẢNG MÔN KỸ THUẬT CHUYỂN MẠCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI KHOA ĐIỆN TỬ – VIỂN THÔNG --------------------------------------------------------------------- ĐỀ 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 Author Nguyen Tai Hung Hanoi University of Technology Tel 844 833 4400 Faculty of Electronic & Telecommunication Fax 844 833 4372 Department of Communication Engineering Handy Phone 84 9021 7248 http://www.hut.edu.vn E.mail Hungnt@mail.hut.edu.vn
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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 2 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 1. Đặ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. 2. Đị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 3 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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: o Trễ trong các mạng Ethernet (LAN) o Thời gian lổi trung bình của các card giao tiếp thuê bao của các PBX o Các bộ đệm gói tại các PAD o Hiệu suất của một máy chủ quản lý các printer trong 1 mạng LAN o Các đường trung kế T1/E1 nối giữa các tổng đài PBX o Xác suất tắc nghẽn cuộc gọi của một tổng đài PBX o Các cuộc gọi chờ trong các tổng đài PBX với LCR (Least Cost Routing) o Chất lượng các hệ thống thoại được gói hoá ..... 2.2. 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. 4 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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 5 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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: 6 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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 7 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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) 2.3. 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: 8 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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. 3. 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. 9 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering  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 10 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering  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à tốc độ đến trung bình của các yêu cầu. Do đó: rho = (λ) 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 = λ 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 = λ x (1/x [bar]) Ký hiệu: mu = 1/ x [bar] rho = λ /mu 11 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering Đối với 1 hệ thống hàng đợi có m server thì: rho = λ x (x [bar])/m 4. 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 = λ/(mu - λ). [n = 0] W = 1/(mu - λ). [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]], [c -1] khi 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/[(λ)(1 - p [K])]. (1 - rho)(K - c + 1)(rho) [K - c]}/ M/M/c {c!(1 - rho) [ 2]}; rho = λ/(c)(mu). L: the algebraic expression is too long to show pn = (λ)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] /[(λ)(1 - p [K])]. p [n] = (λ) [n]p [0]/[(c) [n - c]c!(mu) [n]], khi M/M/c/c n 12 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering 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) - λ] [2] }p [0] + rho = (λ)/[(c)(mu)]. 1/mu; M/E [k ]/1 L = (λ)W. Wq = [(k + 1)/(2k)] [λ/(mu) M/M/c/K (mu – λ)]. r = λ/mu, và Lq = (λ)W [q] (from Little's result). s = λ/(c)(mu) = rho. p [n] = [1/n!](r) [n]p [0], when n is between 1 M/G/1 and c, and p [n] = [1/(c) [n - c] c!](r) [n]p [0], khi n nằm L = (rho) + [(rho) [2] + (λ) [2](s [B] giữa c và K. [2])]/ [2(1 - rho)] với s [B] [2] = V(B) = E(B [2] ) - E(B) [2] W = L/(λ) W [q ] = W - 1/(mu) L [q] = L - (λ)/(mu) 4.1. 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] = (λ )/[mu(mu - λ )] 13 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering Thời gian tổng cộng trung bình trong hệ thống là: W = 1/(mu - λ ) 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 = λ/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 - λ ) = 1/(0.500 - 0.475) = 40 giây Thời gian này là khá dài vì một user sẽ rất bực mình khi phải đ ợi đ ến 40 s mới nghe được 1 thông bào từ hệ thống sau khi ấn một phím trên máy điện thoại hoặc máy tính. Giải pháp là người quản trị hệ thống có thể mua thêm ổ cứng hoặc bộ điều khiển để giảm thời gian phục vụ xuống còn 0.350 ms. Khi đó tính toán lại ta s ẽ có: λ = (1/t [bar]) = 2.0 và λ = (1/x [bar]) = 2.85 nên rho = λ/mu = 0.7. Số yêu cầu trung bình trong hệ thống bây giờ là: L = rho/(1 - rho) = 0.7/0.3 = 2.3. Tổng thời gian trung bình trong hệ thống là: 14 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering W = 1/(mu - λ) = 1/(0.500 - 0.350) = 6.6 giây. Thời gian đợi bây giờ đã giảm đáng kể xuống còn 6.6 giây do đó rõ ràng với ổ cứng mới đã cải thiện đáng kể hiệu suất làm việc của hệ thống Voice Mail. Đây là lý do tại sao một kỹ sư viễn thông phải rất thành thạo về lý thuy ết hàng đ ợi khi thiết kế các hệ thống thông tin. 4.2. Mô hình M/M/1/K , với luật hàng đợi là FIFO ( K là số vị trí rỗi trong hàng đợi)..... M/M/1/K là hệ thống có số lượng vị trí trong hàng đợi có giới hạn: chỉ có K vị trí rổi ( theo định nghĩa K cũng bao gồm số server). Mô hình này gặp rất nhiều trong thực tế, đặc biệt trong các hệ thống thông tin: các đường trung kế Tie Line giữa 2 tổng đài PBX, các thanh ghi trong chuyển mạch điện thoại, các cổng quay số tới 1 PAD, các bộ nhớ đệm trong các FEP (Front-End Processor),.... ở đây cần có lý thuyết xếp hàng do các loại dịch vụ khác nhau trong hệ thống yêu cầu số vị trí trong bộ đệm khác ngau, hơn nữa cũng có rất nhiều yêu cầu bị tắc nghẽn trong hệ thống. Người thiết kế cần phải biết bao nhiêu yêu cầu không được phục vụ, số server cần thiết,.... Xác suất có n yêu cầu đến hệ thống (tất nhiên n
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering ( trực bàn điện thoại viên) ( ở đây K=5). Khi bàn điện thoại viên bận, các cuộc gọi được chờ trong hàng đợi bằng các câu thông báo ( ví dụ, “ Xin quí khách vui lòng chờ trong giây lát”); Tuy nhiên do chỉ có 5 đường trong vòng quay nên chỉ có chỉ có nhiều nhất 5 khách hàng có thể chờ trong hệ thống tại một thời điểm bất kỳ (1 được phục vụ và 4 nằm chờ). Các dữ liệu tập hợp được cho thấy: λ = 5 mổi phút ( là số khách hàng đến trong 1 phút) mu = 6 mổi phút ( số khách được phục vụ trung bình trong 1 phút) Trước khi quyết định tăng thêm số đường trong vòng quay ( nhưng vẫn chỉ 1 Operator), người chủ cửa hàng cần biết : kích thước trung bình của hệ thống, chiều dài hàng đợi trung bình, thời gian đợi trung bình để được phục vụ, và thời gian đợi trung bình đối với những khách hàng đang chờ bằng các câu thông báo. Người chủ sẽ tính như sau: rho = 5/6 = 0.833; L = 0.833[1 - 6(0.833) [5] + 5(0.833) [6 ]]/[0.833(1 - 0.833 [6])] = 1.97; L [q] = 1.97 - (0.833)[1 - (0.833) [5 ]]/[1 - (0.833) [6]] = 1.22; p [5] = (0.833) [5](1 - 0.833)/[1 - (0.833) [6]] = 0.10, Từ đó W = 1.97/[(5)(1 - 0.1)] = 0.438 phút; W [q] = 0.438 - 0.167 = 0.271 phút. Để xác định trung bình có bao nhiêu khách hàng bị mất, phải xác định xác suất mà một cuộc gọi đến thì thấy có 4 khách hàng khác đang chờ thao tác viên (Operator) và nhân xác suất này với tốc độ đến trung bình λ. Như sau: (λ)(p [5]) = (5)(0.10) = 0.5 khách hàng/phút, Hoặc 1 khách hàng trong 2 phút. Do đó, người chủ cửa hàng phải đầu tư thêm 1 số đường trong vòng quay nữa, vì tỉ lệ này là tương đối cao ( 10% khách hàng đến bị mất). 4.3. Hệ thống hàng đợi đa server M/M/c : c là số server Kiểu hệ thống hàng đợi đa server này có rất nhiều ứng dụng trong thực tế, ví dụ: nhóm các đường trung kế nối giữa 2 tổng đài, 1 PAD (Packet Assembler/Disassembler) với nhiều cổng vào,... . Các phương trình để đo lường hiệu suất của hệ thống hàng đợi đa server này mặc nhiên rất phức tạp, nhưng trong thực tế người ta đưa ra biểu thức đại s ố đơn giản có thể lập chương trình để tính hệ số sử dụng của nó là: rho = λ/(c)(mu) 16 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering Lưu ý rằng: n! = n(n - 1)(n - 2)(n - 3) ... (3)(2)(1); ví dụ, 5! = (5)(4)(3)(2)(1) = 120. Để tiện tính toán, ta định nghĩa r = λ/mu. Do đó các phương trình quản lý hàng đợi kiểu FIFO là: p [n] = (λ) [n]p [0]/[n!(mu) [n]], khi n nằm giữa 1 và c, và p [n] = (λ) [n]p [0]/[(c) [n - c]c!(mu) [n]], khi n > c Trước hết phải tính p [o] : po = 1/[(r [n]/n!) + cr [c] /c!(c - r)]. n=0 Ký hiệu r [n]/n! là viết tắt toán học của biểu thức: 1 + r + r [2]/2 + r [3 ]/6 + r [4]/24 + ... + r [c ] - 1/(c - 1)!. Thời gian đợi trung bình trong hệ thống là: W = {r [c](mu)/(c - 1)![c(mu) - λ] [ 2]}p [0] +1/mu; Từ phương trình của Little thì số khách hàng trung bình trong hệ thống là: L = (λ)W. Ví dụ sau đây cho thấy các biểu thức trên hết sức đơn giản: Một Server quản lý việc in ấn trong một mạng LAN có 3 máy in. Server này s ẽ quản lý các yêu cầu in trên 3 máy in trên. Trung bình có 6 yêu cầu in trong 1 phút, và mổi máy in có thể in trung bình 3 công việc trong 1 phút. Người ta cần xác định 2 thông số sau đây: 1. Thời gian trung bình một công việc in tiêu tốn trên hệ thông server 2. Trung bình có bao nhiêu công việc in đang đợi ở đây c = 3, mu = 3, λ = 6. Do đó r = λ / mu = 2. Vậy nên ta có: p [o]= 1/[(1 + 2 + 2 [2] /2!) + 3(2) [3]/3!(3 - 2)] = 0.11; Do đó: W = 1/3 + {3(2) [3]/2![(3)(3) - 6] [2 ]}(0.11) = 0.48 phút và L = (6)(0.48) = 2.88. 17 Nguyen Tai Hung – Packet Switching Engineering
Hanoi University of Technology – Faculty of Electronic & Telecommunication Department of Communication Engineering Tương tự xét các mô hình khác. (thực hiện sau) 5. Mô phỏng Khi phân tích các loại mô hình hàng đợi ở trên, chúng ta có thể thấy các mô hình đó có những hạn chế sau: • Người kỹ sư cần giải quyết 1 vấn đề nhưng lại không biết liệu một mô hình nào đó đã được giải quyết rồi hay chưa và có thể tìm giải pháp ở đâu • Thứ 2 các mô hình này có thể tìm thấy trong các tài liệu, nhưng giải pháp lại không nằm dưới dạng các phương trình đại số. • Thứ 3, mô hình có thể tìm thấy, nhưng giải pháp lại quá phức tạp đ ể có thể thực hiện nó • Thứ 4, có những mô hình tương tự đã được giải quyết rồi, nhưng những mô hình này lại không hoàn toàn phù hợp với yêu cầu. Có một cách để vượt qua các hạn chế đó là sử dụng mô phỏng. Mô phỏng là một luật đã được phát triển cho phép các kỹ sư xây dựng các mô hình vi mô của hệ thống thực tế trên máy tính và sau đó để cho máy tính tìm ra giải pháp. Nó yêu cầu các chuyên gia thiết kế, các nhà lập trình để đạt được giải pháp cho những vấn đề cực kỳ phức tạp. Chương trình mô phỏng có thể được viết bằng những ngôn ngữ bậc cao, tuy nhiên người ta thường dùng những ngôn ngữ chuyên dụng cho mô phỏng. Thông dụng nhất là các hệ thống: GPSS (General Purpose Simulation System), 1 sản phẩm của IBM, hoặc SIMSCRIPT,..... Có thể tìm thông tin về các phần mềm trên tại: http://ww.isye.gatech.edu/informs-sim/comm.html 6. Các ứng dụng Các nhà lập kế hoạch và thiết kế mạng thường xuyên gặp 6 nhiệm vụ sau: • Cung cấp 1 kết nối hiệu quả về chi phí giữa 2 vị trí • Đánh giá và tham gia vào các công nghệ mới • Xác định sự tương thích giữa các phần tử mạng • Đảm bảo rằng mạng có đủ dung lượng để đảm bảo được băng thông yêu cầu • Đảm bảo độ trễ đầu cuối đến đầu cuối hoặc thời gian đáp ứng đủ bé. • 7. Kết luận 8. Tham khảo 18 Nguyen Tai Hung – Packet Switching Engineering

CÓ THỂ BẠN MUỐN DOWNLOAD