BÀI THẢO LUẬN TỔ CHỨC MANG VIÊN THÔNG ̣ ̃

Chia sẻ: Manh Tuan | Ngày: | Loại File: DOC | Số trang:22

Thêm vào BST

Báo xấu

113
lượt xem 26
download

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

Chất lượng dịch (QoS) vụ là một thành phần quan trọng của các mạng gói đa dịch vụ. Các mạng hỗ trợ QoS có thể cung cấp đồng thời các loại dịch vụ khác nhau bằng cách xử lý hợp lý lưu lượng ở các điểm tắc nghẽn.

Chủ đề:

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

Lưu

Nội dung Text: BÀI THẢO LUẬN TỔ CHỨC MANG VIÊN THÔNG ̣ ̃

TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP KHOA ĐIỆN TỬ BỘ MÔN ĐIỆN TỬ VIỄN THÔNG BÀI THẢO LUẬN TỔ CHỨC MANG VIÊN THÔNG ̣ ̃ Sinh viên : Nguyễn Mạnh Tuấn MSSV : DTK0851030289 Lớp : K44DVT02 THÁI NGUYÊN – 2011 1
NHẬN XÉT CỦA GIÁO VIÊN .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... 2
̀ YÊU CÂU 1. Chât lượng dich vụ QoS. ́ ̣ 2. Cac kỹ thuât hang đợi. ́ ̣̀ 3. Phân tich môt hang đợi đơn. ́ ̣̀ 4. Tông kêt và so sanh cac thuât toan. ̉ ́ ́ ́ ̣ ́ I. Chât lượng dich vụ QoS ́ ̣ Chất lượng dịch (QoS) vụ là một thành phần quan trọng của các mạng gói đa d ịch vụ. Các mạng hỗ trợ QoS có thể cung cấp đồng thời các loại dịch vụ khác nhau bằng cách xử lý hợp lý lưu lượng ở các điểm tắc nghẽn.  Để đánh giá chất lượng dịch vụ của mạng IP người ta dựa vào các tham số sau đây: Tỷ lệ mất gói: tham số này cho biết tỷ lệ phần trăm số gói IP bị mất trên • tổng số toàn bộ số gói IP đầu gửi đã chuyển vào mạng cho phía đầu nhận. Độ trễ gói: tham số này cho biết khoảng thời gian gói IP được chuyển từ • đầu gửi đến đầu nhận. Độ biến thiên trễ (jitter): tham số này cho biết sự dao động về độ lớn của • độ trễ gói. Khả năng đáp ứng của dịch vụ: tham số này cho biết xác suất sử dụng • thành công dịch vụ. Để đảm bảo chất lượng dịch vụ cho mạng IP người ta đưa ra các biện pháp  khắc phục sau: Cải thiện băng thông: Nâng cấp đường truyền vật lí; Xác định mức độ ưu • tiên các gói tin; Nén các packet or frame cho nhỏ gọn 3
Độ trễ: Chia nhỏ links hoặc nén chúng lại; Áp dụng thuật toán hàng đợi • Độ tin cậy: Nâng cấp đường truyền vật lý, tránh tắc nghẽn; Đảm bảo • băng thông cho các gói tin quan trọng; Loại bỏ ngẫu nhiên các gói tin không quan trọng gây tắc nghẽn.  Các giải pháp QoS: Cấu trúc Best-Effort: dữ liệu đi vào mạng đều tuân theo quy tắc FIFO. • Không có sự đối xử nào của QoS đối với dữ liệu Cấu trúc Guaranteed Services: dữ liệu đi qua mạng được dành riêng 1 băng • thông chắc chắn cho dữ liệu. Thực hiện thông qua cơ chế RSVP và CBWFQ của QoS. Cấu trúc Differentiated Services: dữ liệu đi vào mạng được phân loại • thành các lớp khác nhau để phân loại cách đối xử của mạng đối với dữ liệu. Thực hiện thông qua các tool QoS là PQ, CQ, WFQ và WRED.  Cơ chế thực hiện QoS Classificaion: phân loại gói tin theo mức độ quan trọng của dịch vụ, mức • ưu tiên từ thấp đến cao Making: Đánh dấu các gói tin thuộc lớp thông tin nào, dùng 3 bits header • của gói tin để đánh dấu Congestion Management: Áp dụng các thuật toán hàng đợi • Congestion Avoidance: Thực hiện loại bỏ ngẫu nhiên 1 số gói tin khi mà • hàng đợi đạt đến 1 con số định trước nhưng chưa đầy. Policing & Shaping: sử dụng một giỏ đựng thẻ tại nút, số lượng thẻ • được qui định trước theo khả năng của nút, mỗi gói tin sẽ được cấp 1 thẻ, sau khi được xử lí xong thì trả lại thẻ cho giỏ. Nếu gói tin đến mà trong giỏ không còn thẻ thì: + Cơ chế policing bỏ gói tin đó đi và yêu cầu ruyền lại sau 4
+ Cơ chế Shaping chuyển gọi tin đó vào hàng đợi -> cần bộ đệm lớn Link Fragmentaion & Interleaving: Phân nhỏ các gói tin thành nhiều gói tin • nhỏ hơn để giảm đỗ trễ trong khoảng thời gian truyền các gói tin Compression: các gói tin có thể có các header giống nhau nên việc xử lí • gói tin có thẻ giam bằng cách chỉ đọc header của gói đầu. II. Cac kỹ thuât hang đợi ́ ̣ ̀ a. Hàng đợi trong Router Lý thuyết hàng đợi nảy sinh một cách tự nhiên trong việc nghiên cứu các chuyển mạch kênh, và chuyển mạch gói. Trong các mạng chuyển mạch kênh, cuộc gọi đ ến chuyển mạch ngẫu nhiên, mỗi cuộc gọi sẽ giữ kênh trong một khoảng thời gian ngẫu nhiên nào đó. Trong mạng chuyển mạch gói, các gói tin với các chiều dài khác nhau đi qua mạng, tài nguyên mạng (các chuyển mạch,kết nối sẽ được chia sẻ cho các gói). Các bản tin được định tuyến đến các node tiếp theo. Thời gian sử dụng bộ đ ệm (tr ễ hàng đợi) là một vấn đề quan trọng trong truyền dẫn thông tin. Thời gian này phụ thuộc vào các thời gian xử lý, độ dài bản tin hay thời gian chờ xử lý khi chưa có tài nguyên s ử dụng. Trong các ứng dụng tương tác và thời gian thực thì thời gian trả lời trung bình đ ược xem như một tiêu chuẩn quan trọng còn trong các ứng dụng khác thì thông l ượng l ại là điều quan trọng nhất. Việc mô tả hàng đợi theo lý thuyết toán học r ất phức tạp nên ta chỉ mô tả chúng theo mô hình đơn giản được sử dụng trong các mạng IP: Dispatching arrivals Queue departure s discipline Server λ =arrival rate Ts= service time w=items wait P= utilization Tw=wait time q= items in queuing system Tq = queuing time 5
Mô hình hàng đợi đơn giản trong mạng Tin tức (có thể là gói tin hay bản tin) đến hệ thống để yêu cầu phục vụ. Nếu server rỗi thì gói tin sẽ được phục vụ ngay lập tức, ngược lại chúng sẽ được lưu giữ trong các hàng đợi. Khi rời khỏi hàng đợi các gói sẽ được xử lý. Các tham số cơ bản liên quan tới hang đợi ̀ Tham số Kí Chú thích hiệu Tốc độ đến TB Thời gian gói tin đến hệ thống hàng đợi với λ vận tốc λ trên một đơn vị thời gian(s) Tốc độ rời khỏi TB Các gói tin rời khỏi hệ thống với tốc độ μ μ trên một đơn vị thời gian Hiệu suất sử dụng Là khoảng thời gian server bận do phải xử lý p lý,đo bằng P= λ /μ dịch vụ Độ dài TB Là số gói nằm trong hàng đợi trung bình Lw tại tất cả các thời điểm t Thời gian đợi TB Có hai định nghĩa: Tw Thứ nhất: được tính bằng tất cả thời gian gói tin đến xử lý (bao gồm cả các gói không phải chờ trong hàng đợi) Thứ hai: chỉ tính TB thời gian các gói tin phải chờ trong hàng đợi Thời gian phục vụ TB Thời gian TB giữa thời điểm gửi gói tới Ts server và thời điểm rời khỏi server Độ dài hàng đợi TB Số gói trung bình trong hệ thống, bao gồm Lq các gói đang được sử dụng và các gói đang 6
chờ trong hàng đợi. Thời gian xếp hàng TB Thời gian các gói ở trong hệ thống. Tq TB Bảng các tham số cơ bản của hàng đợi Các gói đến hàng đợi với tốc độ thay đổi λ và đây là một quá trình poisson, thời giạ phục vụ có phân bố mũ tốc độ μ (thực chất là thời gian trung bình mà các gói tin r ời khỏi hàng đợi). Khi các gói đến hệ thống tăng thì hiệu suất sử dụng hệ thống cũng tăng, dẫn tới tắc nghẽn có khả năng xảy ra. Với p =1 thì các server bão hoà do đó tốc lớn nhất theo lý thuyết mà hệ thống có thể xử lý được là: λmax= 1/Ts Tại λmax thì kích thước hàng đợi rất dài không thể kiểm soát được. Trong thực tế thời gian trả lời và những yêu cầu kích thước hàng đợi giới hạn tốc độ đầu vào của thông tin là 70-90% so với λmax theo lý thuyết. Để hiểu rõ về các hàng đợi được sử dụng trong có chế điều khiển tắc nghẽn ta phải trả lời các câu hỏi: • Các gói sẽ được lắp đặt như thế nào trong hàng đợi. • Thứ tự hay cách thức nào mà các thiết bị mạng phục vụ các hàng đợi của chúng. • Các hoạt động nào của mạng để đối xử với các bó lưu l ượng và hàng đợi bị tràn. Router được xem như hộp lớn, trong đó có các thành phần thực hiện việc truy ền thông tin. Trong ví dụ này ta xét router có 2 giao diện. Gói tin đi từ mạng A tới mạng B. Mạng A tiếp xúc với router qua giao diện IF0, mạng B tiếp xúc với router qua giao diện IF1. Sau khi các gói được đưa đến từ giao diện IF0 sẽ được đặt vào trong hàng đợi queue 0 (hàng đợi đầu vào). Tiếp theo các gói đi vào trong router và được định hướng tới router kế tiếp dựa trên địa chỉ đích lưu giữ trong phần header của gói tin,một số gói tin đi ra từ hàng đợi queue 0 được đưa vào hàng đợi queue 1 kết nối với giao diện IF1. Hàng đợi queue1 còn gọi là hàng đợi đầu ra. 7
Có rất nhiều kĩ thuật hàng đợi: FIFO (first in first out), PQ (priority queue-hàng đợ ưu tiên), FQ (fair queue-hàng đợi cân bằng). FIFO đây là kĩ thuật xếp hàng vào trước ra trước cơ bản. Các gói đến trước sẽ là các gói đầu tiên được xử lý. Khi hàng đợi đầy và có tắc nghẽn xảy ra thì các gói đến sẽ bị loại bỏ. Hàng đợi FIFO dựa vào hệ thống đầu cuối để điều khiển tắc nghẽn thông qua cơ chế điều khiển tắc nghẽn. Do loại hàng đợi này rất đơn giản nhiều khi không điều khiển được tắc nghẽn nên ta thường xét các loại hàng đợi hiệu quả hơn: hàng đợi ưu tiên(PQ), hàng đợi cân bằng (FQ), hàng đợi có trọng số (WQ). b. Hàng đợi FIFO (First In First Out) FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế giới. Hoạt động của FIFO. Các gói đến từ các luồng khác nhau được đối xử công bằng bằng cách đưa vào các hàng đợi theo trật tự đến (gói nào đến trước sẽ được đưa vào trước và được phục vụ trước). Hoat đông cua hang đợi FIFO ̣ ̣ ̉ ̀ của cisco, khi không có kế hoạch hàng đợi nào khác được cấu hình, thì tất cả các giao diện(ngoại trừ các giao diện có tốc độ bằng hoặc nhỏ hơn luồng E1) đều sử dụng hàng đợi FIFO mặc định. Tốc Hàng đợi hoạt động như một nơi lưu giữ các gói để tránh việc loại bỏ các gói không cần thiết khi có dấu hiệu của tắc nghẽn. Khi có tắc nghẽn xảy ra, và hàng đợi tràn thì tất cả các gói đến sẽ bị loại bỏ. Hàng đợi FIFO đ ược sử dụng hầu hết trong các router, nó đơn giản do không phải định cấu hình cho nó mà chỉ việc sử dụng luôn. Trong các router độ xử lý gói phải nhanh hơn tốc độ các gói đến hàng đợi IF0 thì mới tránh được hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng), khi tốc 8
độ xử lý quá thấp hơn so với tốc độ các gói vào, có nghĩa là tốc độ ra nhỏ hơn t ốc gói vào (hàng đợi đầu ra dễ bị tràn) thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong mạng, và khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ. c. Hàng đợi ưu tiên PQ (Priority Queue) Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có một mức ưu tiên khác nhau, hàng đợi nào có mức ưu tiên cao nhất sẽ được ưu tiên phục vụ trước. Khi có tắc nghén xảy ra thì các gói trong các hàng đợi có độ ưu tiên thấp s ẽ b ị loại bỏ. Có một vấn đề đối với kĩ thuật này: khi các hàng đợi có độ ưu tiên cao quá nhiều thì các gói trong hàng đợi có độ ưu tiên thấp sẽ không bao giờ đ ược phục vụ. Các gói đ ược phân loại và được sắp xếp vào hàng đợi tuỳ thuộc vào thông tin bên trong các gói. Tuy nhiên kĩ thuật này dễ bị lạm dụng bởi người sử dụng hay các ứng dụng do ấn định các độ ưu tiên không cho phép. Cơ chế hàng đợi đầu ra ưu tiên có thể được sử dụng để quản lý lưu lượng từ tất cả các giao thức trong mạng. PQ cung cấp cách đối sử ưu tiên cho các luồng l ưu l ượng có độ ưu tiên cao, chắc chắn rằng các luồng lưu lượng then chốt khi qua các kết nối WAN sẽ đạt được độ ưu tiên cao. Cơ chế lam viêc cua PQ ̀ ̣ ̉ Các gói được phân loại như thế nào trong kĩ thuật PQ 9
Danh sách ưu tiên là một tập các luật lệ mô tả các gói sẽ được ấn đ ịnh các đ ộ ưu tiên như thế nào trong các hàng đợi. Ngoài ra nó cũng có thể mô tả độ ưu tiên mặc định hoặc giới hạn kích thước hàng đợi của các hàng đợi ưu tiên. Các gói được phân loại theo: • Loại giao thức hoặc giao thức con • Giao diện đầu vào • Kích thước các gói tin • Các Fragment • Danh sách truy nhập Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn định độ ưu tiên cao nhất để trong trường hớp có tắc nghẽn xảy ra thì chúng được ưu tiên truy ền trước. Các lưu lượng không được ấn định mức ưu tiên nào thì được đ ưa vào các hàng đợi bình thường. PQ cung cấp thời gian đáp ứng nhanh hơn so với các kĩ thuật hàng đợi khác. Mặc dù có thể ấn định các độ ưu tiên cho các hàng đợi tại bất kì giao diện đ ầu nào nh ưmg nó thường được sử dụng cho các lưu lượng có băng thông thấp. d. Hàng đợi cân bằng FQ (Fair Queue) Kĩ thuật này giải quyết vấn đề một số hàng đợi không được phục vụ trong một thời gian dài do tài nguyên dùng để phục vụ cho các hàng đợi có độ ưu tiên cao hơn. Thuật toán Round Robin trong lập lịch được dùng để phục vụ tất cả các hàng đợi một cách công bằng. Kĩ thuật này ngăn chặn một số nguồn dùng quá nhiều tài nguyên của mạng mà không chia sẻ cho các nguồn khác. Các vấn đề có thể xảy ra khi các gói có chiều dài thay đổi, và các hàng đợi chỉ được cho phép giải phóng một gói tại một thời đi ểm. Lược đồ định hướng một byte có thể được sử dụng để cân bằng các hàng đợi. Thêm vào đó một số hàng đợi có thể bị đầy hơn các hàng đợi khác và chúng yêu c ầu phải được phục vụ nhiều hơn nhưng kĩ thuật hàng đợi cân bằng sẽ phục vụ mỗi hàng đợi công bằng 10
e. Hàng đợi cân bằng có trọng số WFQ (Weighted Fair Queue) Thuật toán hàng đợi cân bằng có trọng số là một thuật toán nằm trong họ các thuật toán hàng đợi cân bằng (FQ). Kĩ thuật này có thể được xem là sự phối hợp c ủa hai kĩ thuật hàng đợi cân bằng và hàng đợi ưu tiên. Tất cả các hàng đợi đều được phục vụ do đó có thể tránh được tình trạng bỏ đói hàng đợi, tuy nhiên sẽ có một số hàng đợi đ ược ưu tiên phục vụ nhiều hơn. Một trọng số sẽ được gán cho một số hàng đợi để ấn định chỉ số ưu tiên cao hơn cho chúng. Hoạt động của hàng đợi WFQ Khi các gói đến nó sẽ được phân loại bởi bộ phân loại và được ấn định tới một cửa. Cửa này là một thực thể của hàng đợi mà cùng với các cửa khác được sắp xếp theo trật tự của thuật toán round robin có trọng số. Chỉ theo cách này thì dịch vụ mới thực sự được đối sử công bằng cho mỗi hàng đợi. Chìa khoá của sự phân loại là đàm thoại, điều này có nghĩa là việc thể hiện trọng số để phân loại phụ thuộc vào thông tin nằm trong phần tiêu đề gói tin (địa chỉ nguồn, địa chỉ đích, giao thức cổng nguồn, IP precedence). Bởi vì trong thực tế không thể áp dụng một hàng đợi cho một cuộc đàm thoại, WFQ sẽ sử dụng thuật toán Băm để chia cắt luồng lưu lượng ra thành các luồng nhỏ rồi đưa vào một số gới hạn các hàng đợi được lựa chọn bởi người sử dụng hay được cố định bởi mặc định. Cách này làm tăng số lượng lớn nhất có thể của các hàng đợi, thể hiện sự cân bằng của thuật toán. Điều này có nghĩa là ta có thể có rất nhiều luồng cùng chia sẻ trong cùng một hàng đợi (được thể hiện dựa trên màu sắc khác nhau của các gói trong hàng đợi). Khi các gói đến, bộ phân loại sẽ kiểm tra thông tin trong 11
phần header của gói tin và sử dụng các thông tin này, tính toán số lượng nằm giữa 1 và số hàng đợi. Sau đó lắp đặt các gói này vào các hàng đợi định nghĩa bởi các số này. WFQ cung cấp sự quản lý ưu tiên lưu lượng động theo từng loại lưu lượng bên trong các gói. WFQ có thể quản lý các luồng dữ liệu duplex, ví dụ như giữa các cặp ứng dụng, và các luồng dữ liệu đơn giản như thoại và thoại và video. WFQ cung cấp giải pháp cho các trường hợp yêu cầu thời gian nhất quán cho các người sử dụng mạng có tải nặng và nhẹ giống như là không cung cấp thêm băng thông thừa. WFQ tự động tương thích để thay đổi các điều kiện lưu lượng của mạng. ˖So sánh các kĩ thuật hàng đợi Cơ WFQ PQ FQ FIFO sở so sánh Hoạt +Ấn định trọng +Ấn định độ ưu tiên +Các hàng đợi +Gói nào động số cho hàng đợi. khác nhau cho từmg hàng được đối xử đến trước Luồng lưu lượng đợi phù hợp với từng như nhau được phục có độ ưu tiên cao loại lưu lượng. Hàng đợi +Không xảy ra vụ trước được truyền có độ ưu tiên cao nhất hiện tượng bỏ không phân trước được truyền đầu tiên biệt loại dịch đói hàng đợi vụ +Hạn chế được +Xảy ra trường hợp bỏ hiện tượng bỏ đói các hàng đợi có độ +Không có đói các hàng đợi ưu tiên thấp hiện tượng có độ ưu tiên bỏ đói hàng thấp đợi Loại Không được ấn Ưu tiên sử dụng cho các Không được Sử dụng cho lưu định cho loại lưu loại lưu lượng yêu cầu ấn định cho mọi loại lưu lượn lượng có độ trễ độ trễ latency thấp, do loại lưu lượng lượng, cung latency thấp. Do các gói quan trọng sẽ có độ trễ cấp cách xếp g thời gian phục vụ được ấn định độ ưu tiên latency thấp. hàng nhanh của hàng đợi cao và luôn được truyền Do thời gian nhất và hiệu phục thuộcvào số trước. phục vụ của quả đối với lượng gói có hàng đợi phục các kết nối trong hàng đợi thuộcvào số có độ tắc 12
lượng gói có nghẽn nhỏ trong hàng đợi nhất. Cấu Không yêu cầu Có yêu cầu cấu hình Không yêu cầu Không yêu thiết lập cấu thiết lập cấu cầu cấu hình hình hình danh sách hình danh sách truy nhập khi truy nhập khi quyết định luồng quyết định lưu lượng nào sẽ luồng lưu được truyền tại lượng nào sẽ cổng serial được truyền Bộ Sử dụng trong Sử dụng trong bộ lập Sử dụng trong Ít sử dụng lập bộ lập lịch tương lịch ưu tiên chặt bộ lập lịch trong bộ lập lịch tương thích lịch thích So sánh các loại hàng đợi III. Phân tich môt hang đợi đơn ́ ̣ ̀ a. Ký hiệu Kendall Ký hiệu Kendall được sử dụng rộng rãi để mô tả hệ thống xếp hàng A/S/m/B/K/SD A :phân bố của tiến trình đến S :Phân bố của phục vụ m :số kênh phục vụ B :Kích thước bộ đệm K : Quy mô mật độ (số các cuộc gọi đến) SD :Thứ tự phục vụ các cuộc gọi đến hệ thống như thế nào! (Quy tắc phục vụ). VD: FCFS, LCFS, SIRO.... 13
Thời gian giữa các lần đến A và thời gian phục vụ S thường được giả thiết là các biến số ngẫu nhiên độc lập và được phân bố đồng nhất, ký hiệu là IID (Independent Identycaly Distributed) ü Các tiến trình thông dụng : M : Tiến trình mũ Markov (không nhớ) D : Tiến trình tất định (thời gian như nhau) G : Tiến trình chung Er : Tiến trình Erlang bậc r VD: hàn đợi thông dụng nhất như :M/M/1.M/D/1.M/M/h M/D/1 : - Tiến trình đến là hàm mũ - Tiến trình phục vụ D - Số Server là m=1 b. Quá trình Sinh-Tử (Birth-Death) Trạng thái của hệ thống được biểu diễn bằng số các công việc n trong một hệ thống Khi có một công việc mới đến thì trạng thái của hệ thống sẽ thay đổi sang n+1, khi có một công việc ra đi thì trạng thái hệ thống sẽ thay đổi sang n-1, ta có lược đồ chuyển tiếp trạng thái là quá trình sinh tử. 14
λ n : Tốc độ của lần đến n µ : Tốc độ của lần đi λ0λ1...λn Pn = P µ0 µ1...µn 0 Pn : Xác suất ổn định trạng thái n c. Hàng đợi M/M/1 Lược đồ : Tất cả các tốc độ đến đều là l , m λ : Tốc độ của lần đến µ : Tốc độ của lần đi n λ �� Pn = � �P0 = ρn.P0 µ �� Pn : Xác suất ổn định trạng thái n Po : Xác suất ổn định trạng thái 0 ρ=λ 15 µ
ρ : Mật độ lưu lượng Trong trừng hợp này số kênh phục vụ bằng 1, chỉ có 1 server Các công thức tính toán : Xac suât có n job trong hệ thông. ́ ́ ́ - Pn = ( 1 − ρ) ρn ; n =1, 2, 3,... ρ P =1 − ) ( 0 Số lượng trung bình các job trong hệ thống - ρ L =E ( n ) = 1 −ρ ρ Phương sai: δn = 2 ( 1 − ρ) 2 Tham số thời gian : Thời gian trung bình của 1 job trong hệ thống :W - ρ L 1 W= = = λ( 1 − ρ) λ µ −λ Thời gian phục vụ trung bình cho một job : WS - ρ 1 Ws = = µ λ Thời gian trung bình của job trong hàng đợi - ρ2 ρ ρ Wq = W − Ws = −= λ ( 1− ρ ) λ λ ( 1− ρ ) Chiều dài hàng đợi : Số lượng trung bình các job trong hệ thống - 16
ρ L= 1− ρ Số lượng trung bình các job trong server : L S - Ls = P ( n >= 1) = 1 − P ( n = 0 ) = 1 − ( 1 − ρ ) = ρ Số lượng trung bình của các công việc trong hàng đợi L q - ρ2 Lq = L − Ls = (1− ρ ) d. Hang đợi M\M\1\K ̀ Với số công việc (job) là k: n λ �� Pn = � � 0 ; 0
e. Hang đợi M\M\C ̀ n λ 1�� Pn = � �P ;0
Bước 2: Kiểm tra tất cả các nút đã kết nối với nhau chưa? +)Nếu có thì dừng +)Nếu không thì tiếp tục Bước 3: Đánh dấu liên kết đầu tiểntong bảng liên kết Bước 4: Nếu không còn liên kết nào mà chưa kết nối thì dừng. Bước 5: Kiểm tra liên kết đánh dấu có tạo vào hay không? +)Nếu có thì bỏ ra khỏi bảng liên kết +)Nếu không thì thêm vào đồ thị, bỏ khỏi bảng liên kết. Quay trở lại bước 2. ̣ ́ b. Thuât toan Prim Mục đích: Tìm cây MST Các bước: - Phát triển cây từ một nút ban đầu trong mạng. - Có các bước kế tiếp nhau. - Ở mỗi 1 bước tìm nút mới thêm vào cây bằng cách chọn 1 liên kết có độ dài nhỏ nhất (liên kết nối giữa nút thuộc cây và 1 nút không thuộc cây) ̣ ́ c. Thuât toan Dijkstra Mục đích là tìm cây PTS (path shortest tree) Xây dựng cây nối từ nút nguồn đến tất cả các nút khác trong mạng sao cho đường đi từ nút nguồn đến mọi nút là ngắn nhất. Điều kiện : N = tập các nút trong mạng C : nút nguồn ( trung tâm) M :tập các nút đã xác định được đường dẫn ngắn nhất 19
dij :giá liên kết từ nút i j ;dij=0, dij=nếu i,j không nối trực tiếp với nhau Ln: giá của đường dẫn ngắn nhất từ nút C đến nút N Các bước : 1)Khởi tạo M= C Ln =dCn cho nc 2)Với mọi wN ; Lw =m.n.Lj với jM thêm w vào M 3) Tính toán :Ln=m.n(Ln, Lw+dwn) với mọi n không thuộc M ̣ ́ d. Thuât toan Mentor - Dùng thiết kế mạng Backbone, mạng đa dịch vụ, mạng phân tán. - Là thuật toán lai ghép giữa MSTvà pST -Bước 1:tìm tâm c của mạng : Mi =Cijwj Mi =min =>i là tâm C của mạng N : số nút của mạng wj: trọng số của nút j Cij :giá liên kết (i;j) Wj = (r kj +r jk ) r jk :lưu lượng từ nút jk rkj :lưu lượng từ nút kj -Bước 2: Tìm các nút Back bone trong mạng - So sánh tất cả các Wi với W, nếu thoả mãn WjW thì gán i là nút Back bone - Lấy i làm tâm quay vòng tròn tâm i bán kính R, thì các nút sau đây là nút truy nhập của nút i . Xét hàm: Fj = Pc.D/Cjc + (1-Pc)W/wj Cjc :giá từ nút j đến tâm c D : đường kính mạng (khoảng cách giữa 2 nút trong mạng) 20