Tiểu luận Tổ chức mạng 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 MẠNG VIỄN THÔNG Sinh viên : Nguyễn Mạnh Tuấn MSSV : DTK0851030289 Lớp : K44DVT02 THÁI NGUYÊN – 2011 NHẬN XÉT CỦA GIÁO VIÊN .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... YÊU CẦU Chất lượng dịch vụ QoS. Các kỹ thuật hàng đợi. Phân tích một hàng đợi đơn. Tổng kết và so sánh các thuật toán. I. Chất lượng dịch vụ 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 Độ 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 + 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. Các kỹ thuật hàng đợ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. Server Queue Dispatching discipline departures w=items wait Tw=wait time q= items in queuing system Tq = queuing time Ts= service time P= utilization arrivals λ =arrival rate 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: 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 hàng đợi Tham số Kí hiệu Chú thích 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 dịch vụ p Là khoảng thời gian server bận do phải xử lý lý,đo bằng P= λ /μ Độ dài TB Lw Là số gói nằm trong hàng đợi trung bình tại tất cả các thời điểm t Thời gian đợi TB Tw Có hai định nghĩa: 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 Ts Thời gian TB giữa thời điểm gửi gói tới server và thời điểm rời khỏi server Độ dài hàng đợi TB Lq Số gói trung bình trong hệ thống, bao gồm các gói đang được sử dụng và các gói đang chờ trong hàng đợi. Thời gian xếp hàng TB TB Tq Thời gian các gói ở trong hệ thống. 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. 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). Hoạt động của hàng đợ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 độ 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ế làm việc của PQ Các gói được phân loại như thế nào trong kĩ thuật PQ 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 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 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ơ sở so sánh WFQ PQ FQ FIFO Hoạt động +Ấn định trọng số cho hàng đợi. Luồng lưu lượng có độ ưu tiên cao được truyền trước +Hạn chế được hiện tượng bỏ đói các hàng đợi có độ ưu tiên thấp +Ấn định độ ưu tiên khác nhau cho từmg hàng đợi phù hợp với từng loại lưu lượng. Hàng đợi có độ ưu tiên cao nhất được truyền đầu tiên +Xảy ra trường hợp bỏ đói các hàng đợi có độ ưu tiên thấp +Các hàng đợi được đối xử như nhau +Không xảy ra hiện tượng bỏ đói hàng đợi +Gói nào đến trước được phục vụ trước không phân biệt loại dịch vụ +Không có hiện tượng bỏ đói hàng đợi Loại lưu lượng Không được ấn định cho loại lưu lượng có độ trễ latency thấp. Do thời gian phục vụ của hàng đợi phục thuộcvào số lượng gói có trong hàng đợi Ưu tiên sử dụng cho các loại lưu lượng yêu cầu độ trễ latency thấp, do các gói quan trọng sẽ được ấn định độ ưu tiên cao và luôn được truyền trước. Không được ấn định cho loại lưu lượng có độ trễ latency thấp. Do thời gian phục vụ của hàng đợi phục thuộcvào số lượng gói có trong hàng đợi Sử dụng cho mọi loại lưu lượng, cung cấp cách xếp hàng nhanh nhất và hiệu quả đối với các kết nối có độ tắc nghẽn nhỏ nhất. Cấu hình Không yêu cầu thiết lập cấu hình danh sách truy nhập khi quyết định luồng lưu lượng nào sẽ được truyền tại cổng serial Có yêu cầu cấu hình Không yêu cầu thiết lập cấu hình danh sách truy nhập khi quyết định luồng lưu lượng nào sẽ được truyền Không yêu cầu cấu hình Bộ lập lịch Sử dụng trong bộ lập lịch tương thích Sử dụng trong bộ lập lịch ưu tiên chặt Sử dụng trong bộ lập lịch tương thích Ít sử dụng trong bộ lập lịch So sánh các loại hàng đợi III. Phân tích một hàng đợ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.... 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ử. : Tốc độ của lần đến n : Tốc độ của lần đi 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 Pn : Xác suất ổn định trạng thái n Po : Xác suất ổn định trạng thái 0 : Mật độ lưu lượng Trong trừng hợp này số kênh phục vụ bằng 1, chỉ có 1 server Các công thức tính toán : Xác suất có n job trong hệ thống. Số lượng trung bình các job trong hệ thống Phương sai: Tham số thời gian : Thời gian trung bình của 1 job trong hệ thống :W Thời gian phục vụ trung bình cho một job : WS Thời gian trung bình của job trong hàng đợi Chiều dài hàng đợi : Số lượng trung bình các job trong hệ thống Số lượng trung bình các job trong server : L S Số lượng trung bình của các công việc trong hàng đợi L q Hàng đợi M\M\1\K Với số công việc (job) là k: Xác suất job đến hệ thống bị từ chối là PK Tốc độ thực tế đến hệ thống Mật độ lưu lượng e. Hàng đợi M\M\C Xác suất xuất hiện hàng đợi ; công thức Erlang Độ dài hàng đợi : Thời gian đợi : IV. Các thuật toán tìm đường a. Thuật toán kruskal Các bước của thuật toán: - Cho đồ thị có các tập các nút và các cạnh (cạnh……) Bước 1: Sắp xếp tất cả liên kết theo giá thấp tới cao vào bảng giá liên kết 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 toán 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 toán 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 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 toán 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) wj :trọng số W :mức ngưỡng ; Pc=0¸1 - Tính toán giá trị Fj cho tất cả các nút thuộc tập U nếu Fj lớn nhất thì chọn nút nút j làm nút Back bone và lại quay vòng tròn tâm j bán kính r, các nút thuộc vòng tròn này là các nút truy nhập và quá trình lại tiếp tục cho tới khi các nút nằm trong mạng -Bước 3: Xây dựng cây kết nối giữa các nút Back bone với nhau. Cây MST : Total Length = min Total path = max PST : Total Length = max Total path = min Mentor : Kết hợp MST và pST - Cây MST +) Chọn nút gốc trùng tâm c +) Chọn tập cây đã kết nối Nban đầu N= {c} +) Tính giá liên kết Lj = dij +) Lj = min =>thêm nút j và liên kết (i,j) vào N -Cây PST:( tương tự) +) Lj =dij +Li -Cây lai ghép Mentor : +) Lj =dij + a .li với a :0¸1 -Cây Mentor: a = 0® MST a = 1® PST e. Thuật toán CMTS Mục đích: Là tìm một cây bao trùm tối thiểu sao cho cây không có lien kết tạo thành vòng và tổng các nút trên từng nhánh xuất phát từ nút trung tâm không vượt quá giới hạn dung lượng W cho phép Các bước thực hiện : Bước 1:Sắp xếp liên kết theo giá ,theo thứ tự tăng dần Bước 2:Kiểm tra xem các nút có liên thông hay không Nếu có thì dừng thuật toán Nếu không thì tiếp tục Bước 3:Chọn liên kết ở dòng đầu tiên của bảng Bước 4:Kiểm tra xem các liên kết them vào có tạo thành chu trình hay không hoặc liên kết vừa tạo có làm tổng trọng số của các nút trên cây vượt quá giới hạn dung lượng W hay không Nếu đúng thì xóa liên kết vừa tạo quay về bước 2 Nếu sai thì them liên kết đó vào cây