Đồ án Tìm hiểu Multitst

gởi thông điệp Membership Report đến router, và hủy(suppress) thông điệp của nó. Cơ chế này (Report Suppression) làm giảm được lưu lượng trên nhánh mạng. 4. Host H3 cũng nhận được thông điệp Membership Query và nó cũng trả lời lại thông điệp Membership Report đến nhóm mà nó đã đăng ký 224.2.2.2. Kết quả của quá trình Query-Response là Router A biết được các máy muốn nhận gói tin từ nhóm 224.1.1.1 và 224.2.2.2 trên nhánh mạng. Ngoài ra, Router B cũng lắng nghe được trên toàn bộ quá trình và cũng biết các thông tin như router A. Cơ chế Report Suppression Cơ chế giúp giảm số lưu lượng IGMP trên một nhánh mạng đến mức tối thiểu. - Khi một host nhận thông điệp Membership Query, host bắt đầu đếm ngược thời gian trả lời (report-timer) đối với nhóm multicast mà nó tham gia vào. Mỗi report-timer được khởi tạo ngẫu nhiên từ 0 đến thời gian trả lời tối đa. Mặc định là 10 giây. - Sau thời gian đó, host gởi thông điệp Membership Report kết hợp với report-timer đến nhóm multicast. - Nếu host nghe một host khác gởi thông điệp Membership Report, thì nó hủy thông điệp Membership Report và report – timer. Bằng cách đó, triệt tiêu được việc gởi thông điệp đến nhóm multicast. IGMPv1 Querier Nếu tất cả router trên một nhánh mạng đều gởi thông điệp Membership Query thì gây ra lãng phí băng thông mạng. Do đó cần phải có 1 router là IGMPv1 Querier. IGMPv1 dựa trên các giao thức định tuyến (PIM, DVMRP, …) để chỉ định 1 router (Designated Router) cho nhánh mạng. Các host có thể gởi một hay nhiều thông điệp Membership Report (unsolicited report) tham gia vào các nhóm multicast ở bất kỳ thời điểm nào mà không cần phải chờ thông điệp Membership Query kế tiếp từ router. IGMPv1 không có cơ chế để cho phép một host rời khỏi một nhóm, khi host đó không còn quan tâm đến nội dung của nhóm multicast đó. Thay vào đó, router sẽ kết luận là một cổng giao tiếp của nó không còn thuộc về một nhóm multicast, nếu router không nhận được Membership Report trong ba chu kỳ truy vấn liên tiếp. Điều này có nghĩa là, ở chế độ mặc định, các multicast traffic vẫn gửi vào một phân đoạn mạng trong ba chu kỳ truy vấn liên tiếp sau khi tất cả các thành viên của nhóm không còn lắng nghe multicast traffic nữa. Ngoài ra, do cơ chế Report Suppression nên các router không giữ một danh sách đầy đủ các host thành viên cho từng nhóm multicast. Thay vào đó, nó cần phải lưu những nhóm multicast nào đang tồn tại trên những cổng của nó. ii. IGMPv2 Khuôn dạng thông điệp - Type: Trong IGMPv2 có 4 loại thông điệp được sử dụng giữa host và router Membership Query (0x11): có hai dạng: + General Query: Dùng để xác định các nhóm multicast hoạt động. General Query được biểu thị bởi giá trị 0 trong Group Address. + Group-Specific Query: Dùng để xác định một nhóm multicast cụ thể chứa các thành viên. Group-Specific Query chứa địa chỉ của nhóm đang được truy vấn. Version 1 Membership Report (0x12): Loại thông điệp này dùng để tương thích với phiên bản IGMPv1. Version 2 Membership Report (0x16) Leave Group (0x17): Loại thông điệp này được dùng khi một host muốn rời khỏi nhóm multicast. - Maximum Response Time: Chỉ dùng trong thông điệp Membership Query, nó chỉ định thời gian tối đa (đơn vị 1/10 giây) mà 1 host có thể chờ để trả lời 1 thông điệp truy vấn. Giá trị mặc định là 100 (10 giây). - Checksum: Trường này gồm 16 bit, và chứa tổng số bit của thông điệp. - Group Address: Khi một thông điệp General Query được gởi đi, trường này được gán giá trị là 0 để phân biệt với thông điệp Group-Specific Query. Khi thông điệp Membership Report hoặc Leave Group gởi đi thì trường này chứa giá trị nhóm multicast được gởi đến. Quá trình Leave Nhờ thông điệp Leave Group, Group-Specific Query và Maximum Response Time mà IGMPv2 giảm được việc các router vẫn gửi truy vấn đến các nhánh mạng dù các host không quan tâm đến gói multicast. Trong mô hình này host H2, H3 đang là thành viên của nhóm 224.1.1.1, host H2 muốn rời khỏi nhóm: - H2 gởi thông điệp Leave Group đến địa chỉ all-router (224.0.0.2) thông báo cho tất cà các router trên nhánh mạng biết nó muốn rời khỏi nhóm. - Router A (IGMP Query Router) lắng nghe thông điệp Leave Group từ host H2. Tuy nhiên, Router A chỉ lưu danh sách các nhóm thành viên hoạt động trên nhánh mạng (không có host nào cụ thể). Do đó, Router A gởi thông điệp Group-Specific Query để xác định host đến nhóm 224.1.1.1 - Host H3 vẫn là thành viên của nhóm 224.1.1.1, do đó nó nhận thông điệp và trả lời lại bằng thông điệp Membership Report thông báo cho router biết rằng trên nhánh mạng vẫn còn Host tham gia vào nhóm. Host H3 là thành viên cuối cùng của nhóm 224.1.1.1, và bây giờ H3 cũng muốn rời khỏi nhóm: - H3 gởi thông điệp Leave Group đến địa chỉ all-router (224.0.0.2) - Router A lắng nghe thông điệp Leave Group từ host H3 và gởi thông điệp Group-Specific Query để xác định host đến nhóm 224.1.1.1 - Và bây giờ không còn thành viên nào trong nhóm 224.1.1.1 trên nhánh mạng. Do đó, không có host trả lời thông điệp Group-Specific Query. Router A đợi 1 giây, sau đó lại gởi một thông điệp khác mà vẫn không nhận được thông điệp trả lời. Lúc này, Router ngừng việc chuyển gói tin multicast đến nhánh mạng này. IGMP Query Router Không như phiên bản IGMPv1 phải phụ thuộc vào các giao thức định tuyến, IGMPv2 sử dụng địa chỉ IP trong thông điệp General Query để chọn IGMP Query Router - Các router gởi thông điệp General Query đến tất cả các router còn lại trong mạng (224.0.0.1) kèm theo địa chỉ cổng của nó trong trường địa chỉ Source IP của thông điệp. - Khi một router nhận được thông điệp General Query, router sẽ so sánh địa chỉ Source IP với địa chỉ cổng của nó. Router có địa chỉ IP nhỏ nhất trên nhánh mạng được chọn là IGMP Query Router. - Cứ sau 250s (querier-timer) các router lại thực hiện quá trình chọn ra 1 IGMP Query Router mới. iii. IGMPv3 IGMP v3 là một dự thảo sơ bộ. Nó giới thiệu bổ sung bản tin Group - Source Report cho phép một host có thể quyết định nhận lưu lượng từ các nguồn riêng biệt của một nhómMulticast. Một bản tin Group - Source Report cho phép một host chỉ ra địa chỉ IP của các nguồn riêng biệt mà nó muốn nhận. Một bản tin Exclusion Group - Source Report cho phép một host nhận dạng chính xác các nguồn mà nó không muốn nhận. Cuối cùng, bản tin Leave Group đã giới thiệu trong IGMPv2 đã nâng cao thành bản tin Group-Source Leave. Đặc điểm này cho phép một host dời khỏi toàn bộ nhóm hay chỉ ra các địa chỉIP riêng biệt của cặp (nguồn, nhóm) mà nó muốn rời khỏi. 1.5. Cây Phân Phối Các router hỗ trợ multicast tạo ra các cây phân phối để quản lý các con đường của lưu lượng IP multicast đến tất cả các máy nhận. Hai loại cây phân phối cơ bản là cây nguồn (Source tree) và cây chia sẻ (Shared tree). 1.5.1 Source Tree Cây nguồn là dạng cây phân phối đơn giản nhất với gốc là nguồn dữ liệu multicast và các nhánh là đường dẫn tới máy nhận dữ liệu. Do loại cây này sử dụng đường đi ngắn nhất nên còn có tên là SPT (Shortest Path Tree). Mô hình sau là ví dụ một SPT đối với nhóm 224.1.1.1 có gốc là nguồn gởi Host A, và các máy nhận Host B, C. Kí hiệu (S,G) là một SPT trong đó S là địa chỉ IP của nguồn và G là địa chỉ nhóm multicast, như trong hình sẽ là (192.1.1.1, 224.1.1.1). (S,G) có nghĩa là một SPT riêng biệt tồn tại cho mỗi nguồn gởi đến mỗi nhóm. Chẳng hạn như host B cũng gởi lưu lượng đến nhóm 224.1.1.1 và host A và C là các máy nhận, thì tồn tại một SPT và được ký hiệu (192.2.2.2, 224.1.1.1). 1.5.2 Shared Tree Không có gốc từng nguồn như các cây nguồn, các cây chia sẻ sử dụng một gốc chung duy nhất tại một điểm đã chọn trên mạng. Gốc của cây chia sẻ được gọi là điểm hẹn (RP, Rendezvous Point). Trong mô hình sau là ví dụ shared tree đối với nhóm 224.2.2.2 với gốc được chỉ định tại Router D. Khi sử dụng cây chia sẻ, nguồn phải gửi lưu lượng của nó tới gốc và sau đó lưu lượng này được chuyển tiếp theo các nhánh của cây đến các máy nhận dữ liệu. Trong ví dụ này, lưu lượng multicast từ nguồn gởi host A và host D đến gốc (Router D) sau đó xuống shared tree đến các host nhận B và C. Bởi vì tất cả các nguồn trong nhóm multicast sử dụng một shared tree, do đó kí hiệu (*, G) đại diện cho cây. Trong đó, * có nghĩa là tất cả các nguồn (all sources) và G đại diện cho một nhóm multicast. Do đó, trong ví dụ shared tree được ký hiệu là (*, 224.2.2.2). Do các thành viên của nhóm có thể tham gia hoặc rời khỏi nhóm bất cứ lúc nào nên các cây phân phối phải cập nhật động. Giải pháp sử dụng source tree có ưu điểm tạo ra đường dẫn tối ưu giữa nguồn dữ liệu và các host nhận dữ liệu, giảm thiểu sự trễ khi truyền dẫn các lưu lượng multicast. Tuy nhiên, các router phải duy trì các thông tin về đường dẫn cho từng nguồn. Với mạng có hàng ngàn nguồn dữ liệu và hàng ngàn nhóm thì vấn đề sẽ trở nên nghiêm trọng đối với các router đặc biệt là vấn đề tiêu thụ không gian lưu trữ các bảng định tuyến multicast. Giải pháp sử dụng shared tree không gặp phải vấn về bộ nhớ cần thiết cho bảng định tuyến nhưng trong một số trường hợp cụ thể đường dẫn giữa nguồn và đích không tối ưu gây trễ trong quá trình phân phát dữ liệu. Lựa chọn điểm hẹn là vấn đề quan trọng nhất khi áp dụng giải pháp này cho mạng multicast. Chương 2 CÁC GIẢI THUẬT ĐỊNH TUYẾN MULTICAST 2.1. Giải thuật Flooding Trong giải thuật này khi router nhận được một gói multicast, đầu tiên nó kiểm tra xem gói tin này đã nhận được trước đó chưa. - Nếu là lần đầu tiên, router sẽ gởi gói tin đến tất cả các cổng của nó, ngoại trừ cổng mà đã gởi gói tin đến. - Nếu gói tin đã được nhận, router sẽ loại bỏ gói tin này. Bằng cách này, chắc chắn rằng tất cả các router sẽ nhận được ít nhất là một gói tin. : (Source ) nguồn gởi. : Router. : Nhánh mạng con có tham gia vào nhóm (Group members). : Nhánh mạng con không tham gia vào nhóm. : Đường chuyển gói chấp nhận : Đường các gói bị loại bỏ Mặc dù giải thuật này đơn giản nhưng có một số bất lợi. Giải thuật flooding tạo ra một số lượng lớn các gói trùng lắp và lãng phí băng thông mạng. Hơn nữa, để các router nhận biết được một gói mà nó nhận được có phải là lần đầu hay không, nó cần phải lưu lại các gói mà đã nhận trước đó, gây tốn bộ nhớ của router. 2.2. Spanning Tree Giải thuật Spanning Tree được đánh giá là tốt hơn giải thuật Flooding. Trong giải thuật này, một nhóm trong mạng được chọn để xác định cấu trúc cây, như vậy chỉ có một con đường hoạt động giữa hai router bất kỳ. Từ cây này mở rộng cho tất cả các nút trong mạng nó được gọi là “cây bao trùm”. Khi một router nhận được một gói multicast, nó sẽ chuyển các gói trên tất cả các đường mà thuộc cây bao trùm ngoại trừ con đường đã các gói, bảo đảm rằng các gói multicast đến tất cả các routers trong mạng. Rõ ràng, các thông tin mà một router cần giữ là một biến boolean cho mỗi cổng mạng cho dù con đường đó có thuộc cây bao trùm hay không. : Đường chuyển gói tin : Cây bao trùm. 2.3. Reverse Path Forwarding Các router thường phải thực hiện một phép kiểm tra trên tất cả các gói multicast mà nó nhận. Reverse Path Forwarding (RPF) là một công cụ để đảm bảo rằng các gói tin không bị đưa ngược trở về cây multicast ở một vị trí bất kỳ nào đó. Khi một gói tin được nhận trên một cổng của router, ví dụ cổng S1 của router, địa chỉ nguồn của gói sẽ được kiểm tra. Sau đó router sẽ so sánh địa chỉ nguồn này với một entry trong bảng định tuyến unicast. Nếu cột out-going interface của bảng định tuyến cũng đúng bằng cổng nhận gói multicast, gói multicast sẽ được xử lý và chuyển ra các nhánh của cây. Nếu cổng là không so trùng, điều này có nghĩa là có một ai đó đã đưa gói vào một vị trí không mong đợi, chuyển gói tin ngược về root. Gói tin lúc này sẽ bị loại bỏ. 2.4. Giải thuật Reverse Path Broadcasting (RPB) Giải thuật RPB là sự cải biến của giải thuật Spanning Tree. Trong giải thuật này, thay vì xây dựng một cây bao trùm toàn mạng, thì chỉ xây dựng cho mỗi nguồn. Dựa trên giải thuật này khi một router nhận được một gói multicast từ con đường “L” và từ nguồn “S”, router sẽ kiểm tra nếu con đường “L” thuộc con đường ngắn nhất từ nguồn “S”, gói tin sẽ được gởi tới các con đường ngoại trừ đường “L”. Ngược lại, gói tin sẽ bị loại bỏ. Nếu một router không nằm trên con đường ngắn nhất giữa nút nguồn và router lân cận, gói tin sẽ bị loại bỏ tại router lân cận. Giải thuật này hiệu quả và dễ dàng thực hiện. Hơn nữa các gói được gởi thông qua con đường ngắn nhất từ nguồn gởi đến nút rất nhanh. Giải thuật RPB không cần cơ chế để ngừng quá trình chuyển tiếp. Các router không cần biết cây bao trùm toàn mạng và các gói được chuyển trên nhiều cây bao trùm nên lưu lượng được phân phối trên nhiều nhánh, mạng được tận dụng tối đa. Tuy nhiên, giải thuật RPB có một thiếu sót là: Nó không lưu thông tin thành viên nhóm multicast khi xây dựng cây phân phối. - Truncated Reverse Path Broadcasting (TRPB) Giải thuật TRPB được đề xuất để khắc phục một số hạn chế của giải thuật RPB. Như đã biết, bằng cách sử dụng giao thức IGMP, một router có thể xác định xem các thành viên của nhóm multicast, có trong 1 nhánh mạng hay không. Nếu nhánh mạng này là một lá của cây multicast (không có router nào kết nối tới nó) thì router sẽ xén bớt trong cây bao trùm. Nó được đánh dấu lại và cũng tương tự như giải thuật RPB gói tin sẽ không được gởi đến router lân cận nếu router không thuộc con đường ngắn nhất từ router lân cận đến nút nguồn. Mặc dù, thành viên nhóm multicast được sử dụng trong giải thuật TRPB và lá (nhánh mạng con) được cắt bớt từ cây bao trùm, tuy nhiên nó không loại trừ những lưu lượng không cần thiết trên các lá mà không có nhóm thành viên multicast. 2.5. Reverse Path Multicast (RPM) Giải thuật RPM là sự cải tiến của giải thuật RPB và TRPB. RPM xây dưng cây phân phối chỉ gồm: - Nhánh mạng chứa những thành viên nhóm multicast (Active Branch). - Những router trên con đường ngắn nhất đến nhánh mạng chứa các thành viên nhóm multicast. Gói multicast đầu tiên sẽ được gởi đi theo giải thuật TRPB. Những router nào không có liên kết với bất kỳ router nào trong cây TRPB thì được gọi là router lá. Nếu một router lá nhận gói tin và nó không có nhóm thành viên nào trên nhánh mạng, nó sẽ gởi một thông điệp “Prune” ngược về các router mà nó đã nhận gói tin. Thông điệp “Prune” thông báo cho router trước đó (upstream) là không nên gởi gói tin trên con đường này, những router upstream phải lưu lại thông điệp “Prune”. Nếu router upstream nhận được thông điệp từ tất cả các router con của nó trong cây TRPB, thì nó lại một gởi thông điệp prune về router cha trong cây TRPB cho biết rằng gói tin không cần gởi đến nó. Những thông điệp “prune” sẽ xén bớt cây TRPB ban đầu kết quả là gói multicast chỉ được chuyển đến những con đường dẫn đến nút đích (nhóm thành viên). Nhóm thành viên và mô hình mạng có thể thay đổi theo mỗi lần xén bớt cây phân phối. Do đó, trong giải thuật RPM các thông tin prune trong router được bỏ đi theo chu kỳ và gói multicast kế tiếp được gởi đến tất cả các router lá. Đây là mặt hạn chế của giải thuật RPM. Cần không gian bộ nhớ tương đối để lưu thông tin của mỗi gói tin là điều trở ngại khác làm cho giải thuật này không được mở rộng (và do đó không phù hợp với mô hình mạng lớn). 2.6. Steiner Tree Trong các giải thuật trước (RPB, TRPB, và RPM) con đường ngắn nhất giữa nút nguồn và các nút đến được dùng để chuyển gói multicast, đảm bảo các gói được chuyển càng nhanh càng tốt. Tuy nhiên, giải thuật nào cũng cần tốn nhiều tài nguyên mạng. Trong hình cây RPB, C là nút nguồn; A,D là các nút đến. Dễ dàng nhận thấy cây thứ hai sử dụng ít con đường hơn. Dù cây này chậm hơn so với cây RPB (vì các gói cần phải qua 3 hop để đến được D thay vì 2 hop trong cây RPB ), nhưng sử dụng ít con đường hơn. Loại cây này được gọi là Steiner Tree. Mặc dù Steiner Tree giảm được số lượng con đường để xây dựng cây phân phối, nhưng khó khăn trong việc tính toán được cây này do đó làm cho nó thiếu thực tế. Cây dễ thay đổi khi một nút tham gia hoặc rời nhóm multicast, do đó Steiner Tree không ổn định. 2.7. Core Based Tree Không như các giải thuật trước, Core Based Tree (CBT) tạo cây phân phối riêng cho mỗi nhóm. Nói cách khác, cây được dùng để chuyển tiếp gói multicast cho một nhóm riêng biệt, là một cây đơn bất chấp vị trí của nút nguồn. Một router đơn, hay một tập router, được chọn làm core router của cây phân phối. Tất cả thông điệp đến một nhóm multicast thì được chuyển tiếp như thông điệp unicast hướng tới core router cho đến khi chúng đến được một router thuộc về các cây phân phối tương ứng. Sau đó, gói tin được chuyển tiếp đến tất cả các cổng thuộc cây phân phối ngoại trừ các cổng mà nó đã tới. Trong giải thuật này các router multicast lưu giữ ít thông tin hơn so với các giải thuật khác. CBT cũng tiết kiệm băng thông mạng, vì nó không gởi tràn các gói trên toàn bộ mạng. Tuy nhiên, sử dụng cây đơn cho mỗi nhóm có thể dẫn đến lưu lượng tập trung và tắt nghẽn xung quanh core router, gây ra chậm trễ trong việc chuyển các gói tin. 2.8. Multicast Backbone Multicast trên Internet diễn ra trên Multicast Backbone(MBone). MBone là tập hợp những router có khả năng chuyển tiếp lưu lượng multicast (mrouter) và các host được kết nối với nhau. MBone thuộc phần trên cùng của Internet đóng vai trò như một mạng ảo. Trong MBone các nhánh mạng có hỗ trợ multicast được kết nối với nhau bằng một liên kết ảo là “tunnels”. Nhờ tunnels này mà các thông điệp multicast được chuyển tiếp đến các phần Internet không hỗ trợ chuyển tiếp multicast. Khi chuyển tiếp qua tunnels, các gói IP được đóng gói trong một gói IP khác (IP over IP) khi đó chúng như các gói unicast thông thường chuyển tiếp giữa các router. Chương 3 CÁC GIAO THỨC ĐỊNH TUYẾN 3.1. Giao thức PIM Protocol Independent Multicast (PIM) là một giao thức định tuyến có thể được dùng để chuyển các multicast traffic. PIM hoạt động độc lập với các giao thức định tuyến IP vì vậy PIM sử dụng bảng định tuyến IP và không giữ các bảng multicast routing. Cần chú ý là bảng unicast routing cũng không phụ thuộc vào các giao thức định tuyến vì nhiều giao thức định tuyến có thể đóng góp vào cùng một bảng định tuyến. PIM có thể hoạt động ở hai chế độ: - PIM Dense Mode - PIM Sparse Mode 3.1.1. PIM Dense Mode Các PIM router có thể được cấu hình theo kiểu Dense Mode (còn gọi là PIM -DM) nếu các host tham gia vào multicast group nằm ở khắp nơi trên tất cả các subnet. Địa chỉ multicast nguồn trở thành gốc của cây và cây multicast được xây dựng từ nguốn đến đích. Cơ chế này còn được gọi bằng ký hiệu (S,G) trong đó đường đi từ nguồn đến các thành viên trong nhóm là duy nhất và được xác định. Cây multicast được xây dựng bằng cách cho phép phát tán các traffic từ nguồn đến tất cả các router trong mạng. Cây sẽ phát triển từ trên xuống dưới. Trong một thời gian ngắn, các traffic không cần thiết sẽ được lưu chuyển giống như trong broadcast traffic gọi là quá trình Flooding. Khi các router nhận được traffic cho một nhóm, router sẽ quyết định nó có các máy nhận muốn nhận dữ liệu hay không? Nếu là muốn, router sẽ duy trì tình trạng im lặng và để dòng traffic tiếp tục. Nếu không có host nào đăng ký cho nhóm multicast đó (thông qua IGMP), router sẽ gửi thông điệp Prune đến các router láng giềng của nó (theo hướng về gốc của cây) gọi là quá trình Pruning. Nhánh của cây sau đó sẽ bị loại bỏ (prune) sao cho các traffic không cần thiết sẽ không được phát tán về hướng đó. PIM-DM sẽ nhận biết các thiết bị láng giềng bằng cách trao đổi các gói hello. Thông tin láng giềng này được dùng để xây dựng cây đến tất cả các láng giềng. Sau đó, các nhánh của cây sẽ lần lượt được loại bỏ. Nếu một dòng multicast bắt đầu, cây sẽ được xây dựng, cây sẽ chỉ tồn tại khi các thành viên tích cực còn tồn tại. Nếu một host mới đăng ký tham gia nhóm, nhánh của phân đoạn mạng đó sẽ được đính thêm vào cây. 3.1.2. PIM Sparse Mode PIM Sparse Mode (PIM-SM) dùng một giải pháp khác. Cây multicast không mở rộng đến router cho đến khi nào một host đã tham gia vào một nhóm. Cây multicast được xây dựng bằng các thành viên ở các node lá và mở rộng ngược về root. PIM - SM cũng hoạt động dựa trên ý tưởng cấu trúc shared-tree, trong đó gốc của cây không nhất thiết là nguồn của multicast. Thay vào đó, root là router PIM-SM thường được đặt ở trung tâm của mạng. Router làm gốc này gọi là Rendezvous Point (RP). Cây từ điểm RP đến các thành viên thật ra là một cây con của cây từ nguồn đến các thành viên. Nếu một router ở bất kỳ đâu trong mạng có thể đăng ký với RP, cấu trúc cây này sẽ hoàn tất. Chế độ spare-mode còn được gọi là Shared tree. Các dòng multicast được mô tả như (*,G) bởi vì cây luôn cho phép bất cứ nguồn nào gửi đến một nhóm. Khi một host tham gia vào một nhóm multicast dùng IGMP, router cục bộ sẽ chuyển các thông điệp Membership report về gốc của cây multicast. Mỗi router dọc theo đường đi sẽ thêm nhánh đó vào cây dùng chung shared-tree. Quá trình loại bỏ nhanh chỉ thực hiện khi một thành viên của nhóm bị xóa ra khỏi một nhóm. 3.2. DVMRP Distance Vector Multicast Routing Protocol (DVMRP) là Giao thức định tuyến multicast theo vectơ khoảng cách. Trong giao thức này, bộ định tuyến nhận gói multicast sẽ xác định các mrouter được kết nối với nó có cần nhận gói này hay không (nghĩa là các mrouter này có máy là thành viên của nhóm).DVMRP gửi gói đến tất cả các bộ định tuyến được kết nối và đợi trả lời. Bộ định tuyến có máy không là thành viên của nhóm sẽ trả về một thông điệp “xén bớt”, nhờ đó tránh việc gởi các thông tin tiếp theo cho bộ định tuyến này. Sự khác nhau giữa PIM-DM và DVMRP được định nghĩa như sau: - Cisco IOS không hỗ trợ DVMRP, tuy nhiên nó hỗ trợ kết nối đến một mạng DVMRP. - DVMRP dùng giao thức định tuyến của chính nó, tương tự như RIPv2. Nó gửi cập nhật mỗi 60 giây và xem 32 hop là giới hạn trên cùng. DVMRP dùng giao thức định tuyến của riêng nó nên tốn thêm phí tổn nếu so sánh với PIM-DM. - DVMRP dùng các thông điệp Probe để tìm router láng giềng, dùng địa chỉ nhóm là 224.0.0.4. - DVMRP dùng cây broadcast thu gọn, là một dạng tương tự như SPT với vài nhánh bị loại bỏ. Giải thuật DVMR xây dưng cây phân phối dựa trên giải thuật TRPB Đầu tiên gói tin được gởi đến tất cả các router trong mạng. Sau đó, những thông điệp “Prune” xén bớt các nhánh mạng không dẫn đến nhóm thành viên tham gia multicast. Router C là một nút lá vì vậy nó gửi về thông điệp “Prune” về router B Router X,Y cũng là nút lá thông điệp “Prune” gửi về router E, bây giờ router E trở thành nút lá, nó lại gởi thông điệp “Prune” về router cha là D Một thông điệp mới “graft” để ghép lại nhánh đã xén trước đó của cây phân phối trong trường hợp có máy tham gia vào nhóm multicast. Thông điệp “graft” được gởi lại router cho đến khi tạo được một nút trên cây phân phối. Receiver 2 tham gia vào nhóm multicast, do đó router Y gởi thông điệp “graft” đến router E, router gởi lại thông điệp trả lời cho Y, và gởi thông điệp “graft” đến router D, router gởi gói trả lời và bắt đầu gởi gói tin. Giải thuật bị hạn chế không phù hợp với mô hình mạng lớn vì các quá trình Flood và Prune. 3.3. Giao thức MOSPF Multicast Open Shortest Path First (MOSPF) là giao thức xác định đường đi ngắn nhất. Bộ định tuyến MOSPF xây dựng bản đồ của mô hình mạng, bao gồm vị trí các nút, các đường đi và xác định đường đi tốt nhất để đến các mrouter khác. Hoạt động cơ bản của MOSPF: - MOSPF dùng địa chỉ nhóm LSA, được phát tán trên toàn vùng của router. Cùng với unicast OSPF, tất cả các MOSPF router trong một area phải có cùng cơ sở dữ liệu liên kết sao cho tất cả các router MOSPF trong một area có thể tính toán cùng một thuật toán SPT. - Thuật toán SPT được tính toán theo yêu cầu. Khi gói tin multicast đầu tiên của nhóm đến. - Thông qua quá trình tính toán, tất cả các router biết các thành viên nhóm ở đâu dựa trên các thành viên nhóm LSAs. - Sau vài phép tính toán SPF là hoàn tất, các hàng sẽ được đưa vào bảng định tuyến multicast. - Cũng giống như định tuyến unicast OSPF, cây đường đi ngắn nhất là không bị vòng lặp và tất cả các router biết các cổng upstream/downstream. Kết quả là không cần phép kiểm tra RPF. 3.3.1 Định tuyến nội miền MOSPF sử dụng một loại LSA OSPF gọi là LSA thành viên nhóm để thông báo sự tồn tại của thành viên nhóm trong các mạng. LSAs thành viên nhóm được phát flood định kỳ trong cả vùng giống như LSA OSPF. Nó sử dụng thuật toán Dijkstra để tính toán cây đường đi ngắn nhất cho tất cả các cặp nhóm mạng- nguồn. Ở đây, vùng 1 có các thành viên của nhóm A,B trong khi vùng 2 chỉ chứa các thành viên của nhóm A. Các router nối trực tiếp với các thành viên tạo ra các LASs thông báo sự tồn tại của các thành viên trong mạng. LAS thành viên nhóm không truyền qua giữa vùng 1 và vùng 2. Khi tất cả router trong vùng biết vị trí của tất cả các thành viên trong cấu hình mạng, ta có thể thiết lập cây mạng – nguồn cho chuyển tiếp Multicast. Trong mô hình trên, nguồn S1 nằm trong vùng 1 bắt đầu gửi lưu lượng Multicast tới nhóm B ( S1,B). Khi dữ liệu tới router trong vùng, nó thực hiện tính toán Dijkstra và tính toán c