كتب group broadcast tree

شجرة البث المجوعاتي هي شجرة متفرعة مكونة من مجموعة من العقد والوصلات، تُمثّل العقد التجهيزات العاملة على مستوى الطبقة الثالثة في النظام الوسيطي، أمّا الوصلات فتمثل الوصلات الفيزيائية التي تربط بينها. يجب أن تكون شجرة البث المجموعاتي خالية من الحلقات ، وأن تصل إلى جميع أعضاء المجموعة بأقصر الطرق الممكنة، ولذلك، تُوصف شجرة البثّ المجموعاتي بأنها شجرة أقصر المسارات (بالإنجليزية: Shortes-Path Tree)‏.

البنية

يختلف البث المجموعاتي عن البث المنفرد بشكل المسار، ففي حين يكون المسار خطاً وحيداً يصلُ بين مصدر الرزمة ووجهتها في البثّ المنفرد، فإنّه يأخذ شكلاً شجريّاً مُتفرعاً في البثّ المجموعاتي، وتُسمّى الشجرة الناتجة بشجرة البث المجموعاتي، وهي تمتد، بدون أن تشكّل حلقات، لتصل إلى جميع أفراد المجموعة.

تتألف شجرة البث المجموعاتي من مجموعة من العقد هي عقدة الجذر والعقد الوسيطية والعقد الأوراق. أمّا عقدة الجذر فهي أول عقدة في الشجرة، ومنها تبدأ عملية التفرع. عند توجيه الرزمة عبر الشجرة، تبدأ عملية مضاعفة الرزمة في العقدة الجذر، أي أنها العقدة التي يبدأ عندها تفرّع المسارات نحو كل أعضاء المجموعة.

تتفرّع شجرة البثّ المجموعاتي انطلاقاً من عقدة الجذر، وتُشكّل حركة بيانات تسمى التيار الصاعد (بالإنجليزية: Upstream)‏، وينتشر هذا التيار الصاعد من الجذر إلى العُقد الأخرى في الشجرة. تُسمّى العقدة التي يسلكها التيار الصاعد نحو عقدة واحدة أو أكثر، بالعقدة الوسيطية، وهي العقد التي تستقبل التيار الصاعد من عقدة واحدة أو أكثر وتمرره نحو عقدة واحدة أو أكثر. أمّا إذا لم تكن العقدة تمتلك أي عقد جيران، إلا العقدة التي ورد منها التيار الصاعد، فإنها تسمى عقدة ورقة، لأنها لا تمرر التيار الصاعد محو أي عقد جديدة في الشجرة.

يتواجد أعضاء المجموعات في شبكات محليّة تتصل مع عقد الشجرة، سواء كانت عقدة الجذر أو عقداً وسيطية أو عقد أوراق. في البداية، يتمّ توجيه رزم البث المجموعاتي من أعضاء المجموعة نحو العقدة الجذر دوماً، ثُمّ تبدأ بعد ذلك عمليّة مُضاعفة الرزمة ونشرها عبر شجرة البث المجموعاتي. بما أن الشبكات المحليّة التي يتواجد فيها الأعضاء قد لا تتصل بشكل مباشر مع العقدة الجذر، بل عقدٍ أوراق أو مع عقد وسيطية، لذلك فإن بعض الرزم تتجه بشكل معاكس للتيار الصاعد، أي من العقد الأوراق أو الوسيطيّة نحو العقدة الجذر، ويسمى ذلك بالتيار الهابط (بالإنجليزية: Downstream)‏.

الأنواع

تُصنّف أشجار البث المجموعاتي بحسب الطريقة التي يتم إنشاؤها بها إلى نوعين، هما:

• الشجرة المبنيّة بحسب المصدر (بالإنجليزية: Source-Based Tree)‏: وهي شجرة متفرعة خاصّة بمصدر محدد لزرم البث المجموعاتي، حيث يقوم بروتوكول توجيه رزم البث المجموعاتي ببناء شجرة بث مجموعاتي من أجل كل مصدر لرزم المجموعة، ويكون جذر الشجرة هو المُوجّه الأقرب إلى المصدر، في هذه الحالة من أجل مجموعة ما (G)، ومصدرين (S1) و(S2)، سيكون هناك شجرتين هما (S1,G) و(S2,G)، إن هذه الطريقة غير فعالة من حيث استهلاك عرض النطاق المتاح وموارد التوجيه.
• الشجرة المشتركة (بالإنجليزية: Shared Tree)‏، وهي شجرة متفرعة مُوحدة من أجل كل أعضاء مجموعة البث المجموعاتي. لبناء هذه الشجرة، يُعرّف بروتوكول التوجيه نقطة التقاء من أجل كل مجموعة، وتكون هذه النقطة هي جذر الشجرة المشتركة، ويقوم كل مصدر عضو في المجموعة بإرسال رزم البث المجموعاتي إلى النقطة المشتركة أولاً، وبعد ذلك يجري مضاعفة الرزم بحسب شجرة البث المجموعاتي، ويكون جذر الشجرة هو المُوجّه الذي يلعب دور نقطة الالتقاء. في هذه الحالة من أجل مجموعة ما (G)، ومصدرين (S1) و(S2)، سيكون هناك شجرة واحدة هي (G,*). إذا تمّ اختيار عقدة أو عقد محددة لتكون جذراً للشجرة المشتركة، فعندها تُسمّى الشجرة مركزية النواة (بالإنجليزية: Core-Based Tree)‏،

تقوم بروتوكولات التوجيه الخاصّة بالبث المجموعاتي بإنشاء أشجار البث المجموعاتي لنقل البيانات إلى كل أعضاء المجموعة.

خوارزميات البناء

خوازمية بناء شجرة البث المجموعاتي هي خوارزمية لإنشاء شجرة متفرعة، خالية من الحلقات ، تمتد عبر مخطط بياني مكون من (N) عقدة، يضم مجموعة جزئية من العقد عددها (T) وهي تشكل أعضاء مجموعة البث المجموعاتي. تتصل العقد مع بعضها البعض بواسطة فروع أو أضلاع لكل منها وزن محدد، يتعلق بمحددات الشبكة.

تُصنّف الأشجار المتفرعة بحسب امتداد الشجرة إلى صنفين أساسيين هما:

• شجرة أقصر المسارات (بالإنجليزية: Shortest-Spanning Tree)‏: وهي شجرة متفرعة، تمتد من مصدر محدد نحو مجموعة جزئية من العقد، بحيث تكون أوزان المسارات التي تربط المصدر مع العقد هي أصغر مايمكن.
• الشجرة المتفرعة الصغرى (بالإنجليزية: Minimum Spanning Tree اختصاراً MST)‏: وهي شجرة متفرعة تمتد لتصل إلى جميع العقد، بحيث يكون مجموع أوزان كل المسارات هو أصغر ما يمكن.

إذا كان (G) هو مخطط بياني مُكوّن من (N)عقدة و(E) ضلع، وكانت (G1) هي مجموعة جزئية من (G)، احتوي عنصرين على الأقل، وعدد عناصرها هو (T)، فإنّ اختيار خوارزمية بناء شجرة البث المجموعاتي يكون بحسب ما يلي:

• إذا كان عدد العناصر في المجموعة الجزئية هو (T=2)، فإن الشجرة تؤول إلى مسار خطي بين عقدتين، بحالة مشابهة لمسارات الرزم المنفردة، والأفضل هو استعمال خوارزمية ديكسترا أو بلمان فورد.
• إذا كان عدد عناصر المجموعة الجزئية هو نفسه عدد عناصر المجموعة الكلية (T=N)، أي أن الشجرة تمتد إلى كل عناصر المجموعة الكلية، فالشجرة المراد بناؤها هي شجرة متفرعة صُغرى (MST)، ومن الخوارزميات المناسبة لذلك خوارزمية كروسكال وخوارزمية برايم.
• إذ كان عدد العناصر في المجموعة الجزئية أكبر من (2) ولكنّه أقل من عدد عناصر المجموعة الكليّة أي (2<N>T)،أي أن الشجرة تمتد على مجموعة جزئية من العقد، وتسمى شجرة ستينر، وهي الحالة الأكثر تعقيداً في بناء الشجرة بسبب وجود عدة إمكانيّات واحتمالات متاحة.