شبكة كلوز

إذا كان m  ≥  2n − 1 ، فإن شبكة كلوز تكون غير مانعة بالمعنى الدقيق ، أي أنه يمكن دائمًا توصيل مدخل غير مستخدم في مفتاح الدخول بمخرج غير مستخدم في مفتاح الخروج، دون الحاجة إلى إعادة ترتيب المكالمات الحالية . هذه هي النتيجة التي شكلت أساس ورقة كلوز الكلاسيكية عام 1953. لنفترض وجود طرفية فارغة على مدخل مفتاح الدخول، ويجب توصيلها بطرفية فارغة على مفتاح خروج معين. في أسوأ الحالات، تكون n − 1 مكالمة أخرى نشطة على مفتاح الدخول المعني، و n − 1 مكالمة أخرى نشطة على مفتاح الخروج المعني. لنفترض، أيضًا في أسوأ الحالات، أن كل مكالمة من هذه المكالمات تمر عبر مفتاح وسيط مختلف. وبالتالي، في أسوأ الحالات، لا يستطيع 2n − 2 من مفاتيح المرحلة الوسيطة نقل المكالمة الجديدة. لذلك، ولضمان التشغيل غير المحظور بالمعنى الدقيق للكلمة، يلزم وجود مفتاح مرحلة وسيطة آخر، مما يجعل المجموع 2 n − 1.

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

إذا كان m ≥ n ، فإن شبكة Clos قابلة لإعادة الترتيب وغير مانعة ، مما يعني أنه يمكن دائمًا توصيل مدخل غير مستخدم على مفتاح الدخول بمخرج غير مستخدم على مفتاح الخروج، ولكن لكي يحدث هذا، قد يلزم إعادة ترتيب المكالمات الحالية عن طريق تخصيصها لمفاتيح مركزية مختلفة في شبكة Clos. ^{[ 6 ]} لإثبات ذلك، يكفي النظر إلى m = n ، مع استخدام شبكة Clos بالكامل؛ أي r × n مكالمة جارية. يوضح البرهان كيف يمكن تقسيم أي تبديل لهذه المحطات الطرفية المدخلة r × n على المحطات الطرفية المخرجة r × n إلى تباديل أصغر يمكن تنفيذ كل منها بواسطة مفاتيح التقاطع الفردية في شبكة Clos مع m = n .

يستند البرهان إلى نظرية هول للزواج ^{[ 7 ]،} والتي سُميت بهذا الاسم لأنها تُشرح غالبًا على النحو التالي: لنفترض وجود r من الأولاد و r من البنات. تنص النظرية على أنه إذا كانت كل مجموعة جزئية من k من الأولاد (لكل k بحيث 0 ≤ k ≤ r ) تعرف k أو أكثر من البنات، فإنه يمكن إقران كل ولد بفتاة يعرفها. من الواضح أن هذا شرط ضروري لحدوث الإقران؛ والمثير للدهشة أنه شرط كافٍ.

في سياق شبكة كلوز، يُمثل كل ولد مفتاح دخول، وتُمثل كل فتاة مفتاح خروج. يُقال إن الولد يعرف فتاة إذا كان مفتاحا الدخول والخروج المقابلان يحملان نفس المكالمة. يجب أن تعرف كل مجموعة من k ولدًا k فتاة على الأقل، لأن k مفتاح دخول تحمل k × n مكالمة، ولا يمكن أن تحملها أقل من k مفتاح خروج. بالتالي، يمكن إقران كل مفتاح دخول بمفتاح خروج يحمل نفس المكالمة، عبر ربط واحد لواحد. يمكن أن يحمل مفتاح وسيط واحد هذه المكالمات r . إذا أُزيل هذا المفتاح الوسيط من شبكة كلوز، فإن m ينخفض ​​بمقدار 1، ويتبقى لدينا شبكة كلوز أصغر. تتكرر العملية حتى m = 1، ويتم تخصيص كل مكالمة لمفتاح وسيط.

نادراً ما تكون أنظمة تحويل المكالمات الهاتفية الحقيقية غير مانعة تماماً لأسباب تتعلق بالتكلفة، ولديها احتمال ضئيل للحجب، والذي يمكن تقييمه باستخدام تقريب لي أو جاكوبايوس ، ^{[ 8 ]} بافتراض عدم وجود إعادة ترتيب للمكالمات القائمة. هنا، يكون العدد المحتمل للمكالمات النشطة الأخرى على كل مفتاح دخول أو خروج هو u = n − 1.

في تقريب لي، يُفترض أن كل رابط داخلي بين المراحل مشغول بالفعل بمكالمة باحتمالية معينة p ، وأن هذه الاحتمالية مستقلة تمامًا بين الروابط المختلفة. هذا يُبالغ في تقدير احتمالية الحجب، خاصةً لقيم r الصغيرة . احتمالية انشغال رابط داخلي معين هي p = uq / m ، حيث q هي احتمالية انشغال رابط الدخول أو الخروج. في المقابل، احتمالية خلو الرابط هي 1 − p . احتمالية خلو المسار الذي يربط مفتاح الدخول بمفتاح الخروج عبر مفتاح مرحلة وسيطة معينة هي احتمالية خلو كلا الرابطين، (1 − p ) ^² . وبالتالي، فإن احتمالية عدم توفره هي 1 − (1 − p ) ^² = 2p − p² ^. إذن ، احتمالية الحجب، أو احتمالية عدم خلو أي مسار من هذا النوع، هي [1 − (1 − p ) ^² ] ^m .

يُعدّ تقريب جاكوبايوس أكثر دقة، ولتوضيح كيفية اشتقاقه، نفترض وجود ربط مُحدد للمكالمات الواردة إلى شبكة كلوس (مكالمات الإدخال) بمفاتيح المرحلة الوسطى. يعكس هذا حقيقة أن التكوينات النسبية لمفاتيح الإدخال والإخراج هي فقط ذات الصلة. هناك i مكالمة إدخال تدخل عبر مفتاح الإدخال نفسه الذي يُمثل طرف الإدخال المتاح المراد توصيله، وهناك j مكالمة تغادر شبكة كلوس (مكالمات الإخراج) عبر مفتاح الإخراج نفسه الذي يُمثل طرف الإخراج المتاح المراد توصيله. وبالتالي، 0 ≤ i ≤ u ، و 0 ≤ j ≤ u .

لنفترض أن A هو عدد طرق تخصيص استدعاءات الإخراج j لمفاتيح المرحلة الوسطى m . ولنفترض أن B هو عدد هذه التخصيصات التي تؤدي إلى الحجب. هذا هو عدد الحالات التي تتطابق فيها مفاتيح المرحلة الوسطى المتبقية m − j مع m − j من استدعاءات الإدخال i ، وهو عدد المجموعات الجزئية التي تحتوي على m − j من هذه الاستدعاءات. عندئذٍ، يكون احتمال الحجب هو:

${\displaystyle \beta _{ij}={\frac {B}{A}}={\frac {\left({\begin{array}{c}i\\mj\end{array}}\right)}{\left({\begin{array}{c}m\\j\end{array}}\right)}}={\frac {i!j!}{(i+jm)!m!}}}$

إذا كانت f _i هي احتمالية أن تكون i مكالمات أخرى نشطة بالفعل على مفتاح الدخول، و g _j هي احتمالية أن تكون j مكالمات أخرى نشطة بالفعل على مفتاح الخروج، فإن احتمالية الحظر الإجمالية هي:

${\displaystyle P_{B}=\sum _{i=0}^{u}\sum _{j=0}^{u}f_{i}g_{j}\beta _{ij}}$

يمكن تقييم ذلك باستخدام fᵢ _و gⱼ ، حيث يُرمز لكل منهما _بتوزيع ذي الحدين . بعد إجراء بعض العمليات الجبرية، يمكن كتابة ذلك على النحو التالي:

${\displaystyle P_{B}={\frac {(u!)^{2}(2-p)^{2u-m}p^{m}}{m!(2u-m)!}}}$

تُسمى الشبكة غير المحظورة القابلة لإعادة الترتيب من هذا النوع، حيث m = n = 2، عمومًا بشبكة بينيش ، على الرغم من أنها نوقشت وحُللت من قبل آخرين قبل فاتسلاف إي. بينيش . عدد المدخلات والمخرجات هو N = r × n = 2r . تحتوي هذه الشبكات على 2log2N _- 1 مرحلة ، تحتوي كل منها على N /2 من مفاتيح التبديل المتقاطعة 2 × 2 _، وتستخدم ما مجموعه Nlog2N - N / 2 من مفاتيح التبديل المتقاطعة 2 × 2. على سبيل المثال، تُظهر الصورة أدناه شبكة بينيش 8 × 8 (أي حيث N = 8)؛ تحتوي على 2log28 _- 1 = 5 مراحل، تحتوي كل منها على N/2 = 4 من مفاتيح التبديل المتقاطعة 2 × 2، وتستخدم ما مجموعه Nlog2N - N / 2 ₌ 20 من مفاتيح التبديل المتقاطعة 2 × 2 . تتألف المراحل الثلاث المركزية من شبكتين أصغر من نوع بينيش 4 × 4، بينما في المرحلة المركزية، يمكن اعتبار كل مفتاح متقاطع 2 × 2 شبكة بينيش 2 × 2 بحد ذاته. يُبرز هذا المثال البناء التكراري لهذا النوع من الشبكات، مع تسليط الضوء على إحدى شبكتي بينيش 4 × 4 المكونتين. تم اختيار لون الخطوط بين كتل 2 × 2 للتأكيد على التفكيك التكراري الفردي-الزوجي للمدخلات، حيث تذهب المدخلات ذات الأرقام الفردية إلى كتلة فرعية، والمدخلات ذات الأرقام الزوجية إلى الكتلة الفرعية الأخرى.