สวิตช์แบบครอสส์บาร์

สวิตช์แบบครอสส์บาร์มีความสามารถในการเชื่อมต่ออินพุต N ค่า ไปยัง เอาต์พุต N ค่า ผลที่ได้จะเป็นการจัดกลุ่มแบบหนึ่งต่อหนึ่ง โดยจะเชื่อมต่อผู้โทรศัพท์ไปยังผู้รับซึ่งปลายสายว่างอยู่ ทำให้การให้บริการโทรศัพท์เป็นไปได้อย่างสมบูรณ์

อย่างไรก็ตามสวิตช์แบบครอสส์บาร์ใช้เสียค่าใช้จ่ายเป็นเท่าตัวจากการใช้สวิตซ์แบบSPST ซึ่งสำหรับค่า N ขนาดใหญ่ถือว่าเป็นค่าใช้จ่ายที่สูงเกินไป นอกจากนี้สวิตช์แบบครอสส์บาร์ยังมีปัญหาด้านกายภาพด้วย ไม่เพียงแต่การใช้เนื้อที่มาก แต่แถบโลหะของสวิตซ์นั้นเมื่อผ่านไปจะมีการโค้งและไม่น่าไว้ใจในคุณภาพ วิศวกรพบว่าแถบของวิตช์แบบครอสส์บาร์ในแต่ละชิ้นนั้นจะมีการเชื่อมต่อแบบเดียว การเชื่อมต่ออื่นๆในอีกสองแถบจะไม่ได้ถูกใช้ นับว่าเป็นโครงสร้างที่สิ้นเปลือง

มีการคิดหาทางที่จะสร้างสวิตช์แบบครอสส์บาร์ด้วยขนาดที่เล็กลง มีการเลียนแบบสวิตช์แบบครอสส์บาร์โดยการจัดเรียงสวิตช์แบบครอสส์บาร์ที่เล็กกว่า ซึ่งการเปลี่ยนโครงสร้างจากการใช้ชิ้นส่วนที่ได้มาตรฐานจะทำให้ได้โครงสร้างที่มีประสิทธิภาพ ซึ่งเรียกว่าเครือข่ายคลอส

สวิตซ์เชื่อมต่อสมบูรณ์ 3 ชั้น

เป็นการแบ่งสวิตช์แบบครอสส์บาร์ออกเป็น 3 ส่วน ได้แก่ ชั้นอินพุต ชั้นกลาง และ ชั้นเอาต์พุต สวิตซ์จะมีขนาดเล็กลง ง่ายต่อการสร้าง และมีราคาไม่แพง

ในระบบโทรศัพท์จะเป็นการเชื่อมต่อแบบหนึ่งต่อหนึ่ง ซึ่งหมายถึงการที่จำนวนอินพุตจะเท่ากับจำนวนเอาต์พุตในแต่ละสวิตซ์ย่อยๆ หากต้องการสร้างแบบ16 ด้วยสวิตช์แบบครอสส์บาร์ 16 ตัว ในการออกแบบจะมี 4 สวิตซ์ย่อยในการรับอินพุต 16 ตัว ในส่วนของเอาต์พุต ก็จะมี4สวิตซ์ย่อย สำหรับ 16 ผลลัพธ์ เป็นการออกแบบที่ใช้สายไฟน้อย ทำให้ประหยัดค่าใช้จ่าย ซึ่งจำนวนน้อยที่สุดซึ่งใช้เชื่อมโยงสวิตซ์ย่อย 2 ตัว ก็คือใช้สายไฟเพียง 1 เส้น ดังนั้นสวิตซ์ย่อยของอินพุตแต่ละตัวจะมีเส้นเชื่อมเพียงเส้นเดียวไปยังสวิตซ์ย่อยกลาง และ สวิตซ์ย่อยกลางแต่ละตัวจะมีเส้นเชื่อมเพียงเส้นเดียวที่ถูกเชื่อมกับสวิตซ์ย่อยของเอาต์พุต

แต่มีคำถามต่อว่า จำนวนของสวิตซ์ย่อยกลางที่จำเป็นคือเท่าใด และจำนวนเส้นเชื่อมที่จะโยงไปยังสวิตซ์ชั้นกลางเป็นเท่าใด ตั้งแต่โทรศัพท์มีการติดต่อกันได้ระหว่างผู้โทรและผู้รับสาย จะมีความสมมาตร จึงใช้หลักการเดียวกันนี้ในการเชื่อมโยงในชั้นของเอาต์พุต และชั้นกลาง ซึ่งจะเป็นสี่เหลี่ยมจัตุรัส ที่จำนวนอินพุตเท่ากับเอาต์พุต

จำนวนของสวิตซ์ย่อยในชั้นกลางจะขึ้นอยู่กับขั้นตอนวิธีในการจัดการการเชื่อมต่อ ขั้นตอนวิธีพื้นฐานในการจัดการสวิตซ์แบบสามชั้นคือการค้นหา สวิตซ์ย่อยชั้นกลางที่มีเส้นเชื่อมที่ไม่ได้จำเป็นในการใช้งานของอินพุตและเอาต์พุต เมื่อมีการเชื่อมต่อในสวิตซ์ย่อยชั้นกลางจะมีผลต่อการเชื่อมต่อของสวิตซ์อินพุตและเอาต์พุตด้วย

ในทางทฤษฎีแล้ว ตัวอย่างที่ประกอบด้วยสี่สวิตซ์กลางมีความจำเป็น แต่ละส่วนจะมีเพียงการเชื่อมต่อเดียวกับสวิตซ์อินพุตและเอาต์พุต ซึ่งจะเรียกว่าสวิตซ์แบบทอดข้ามต่ำสุด

ในการคิดนั้นจะแสดงให้เห็นว่าเป็นเรื่องง่ายที่จะหาสวิตซ์ที่น้อยสุดในเงื่อนไขไม่มีสวิตซ์กลางที่เชื่อมต่อทั้งสวิตซ์อินพุตและสวิตซ์เอาต์พุต ในความเป็นจริงถ้ามีคนโทรต่อหนึ่งสวิตซ์และแสดงผลลัพธ์ต่อหนึ่งสวิตซ์ หลังจากมีการโทรสิบหกครั้งของการสลับสายนี้ จะมีการบล็อกสิบห้าสายที่เข้ามาเพิ่มเติมที่มีการเชื่อมต่อคล้ายกัน

ด้วยเหตุนี้ในสวิตซ์ที่มีการเชื่อมต่อแบบไม่ปิดกั้นแบบ 16x16 สวิตซ์ จะเป็นสี่สวิตซ์อินพุตย่อย และสี่สวิตซ์เอาต์พุต ซึ่งจะส่งไปยังสวิตซ์กลาง 7 ตัว จึงมีคนเรียกว่าสวิตซ์ 2n-1 ซึ่ง n เป็นจำนวนสวิตซ์ย่อยของอินพุต

ตัวอย่างเช่นการตั้งใจปรับขนาดให้เล็กลงอาจไม่ได้เป็นการประหยัดสวิตซ์ สวิตช์แบบครอสส์บาร์แบบ16x16จะมี256การเชื่อมต่อ ในขณะที่แบบทอดข้ามต่ำสุดจะมี 4x4x4x3 = 192 การเชื่อมต่อ ซึ่งการการสลับสายโทรศัพท์จริงๆจะมีแสนอินพุตและสิบล้านเอาต์พุตของสวิตซ์การเชื่อมต่อ

การจัดการสวิตซ์แบบทอดข้ามต่ำสุด

ในการค้นพบนี้เป็นหนทางในการจัดการการเชื่อมต่อในสวิตซ์ชั้นกลาง นับเป็นเส้นเชื่อมที่ใช้แลกเปลี่ยน เพื่อให้การเชื่อมต่อใหม่สำเร็จ

ในขั้นแรกของขั้นตอนวิธีไม่ปิดกั้นของสวิตซ์แบบทอดข้ามต่ำสุดเป็นการออกแบบในแบบตรงๆ คือ หาสวิตซ์ย่อยในชั้นกลางที่มีความจำเป็นต่อการรับส่งสัญญาณ ถ้าในสวิตซ์ย่อยชั้นกลางนี้เจอการเชื่อมต่อที่จำเป็นสำหรับสวิตซ์ย่อยอินพุตและสวิตซ์ย่อยเอาต์พุตก็จะจัดสรรและใช่เป็นเส้นทางในการเชื่อมต่อ

อย่างไรก็ตาม จำนวนของสวิตซ์ย่อยกลางในสวิตซ์แบบทอดข้ามต่ำสุดมีขนาดเล็กกว่าใน 2n-1 สวิตซ์ บางครั้งการค้นหาก็อาจล้มเหลว ถ้าสวิตซ์ย่อยที่จำเป็นกับคู่การเชื่อมต่อนั้นหาไม่พบ คู่การเชื่อมต่อของสวิตซ์ย่อยจะต้องหาพบ ในหนึ่งสวิตซ์ย่อยจะมีการเชื่อมต่อที่จำเป็นของสวิตซ์อินพุต และส่วนอื่นๆก็ต้องเชื่อมต่อกับสวิตซ์ย่อยเอาต์พุตที่จำเป็นได้ สวิตซ์ย่อยเหล่านี้จำเป็นต้องมี เนื่องจาก อินพุตของสวิตซ์แบบทอดข้ามต่ำสุด จะมีเส้นเชื่อมระหว่างสวิตซ์ย่อยอินพุตกับสวิตซ์ย่อยกลาง เนื่องจากเป็นสวืตซ์ที่ใช้ในระบบโทรศัพท์ ซึ่งผู้โทรและผู้รับมีการติดต่อสื่อสารกัน และยังมีความสมมาตร นอกจากนี้ยังมีเส้นเชื่อมที่ว่างจากสวิตซ์ย่อยชั้นกลางตัวหนึ่งไปยังสวิตซ์ย่อยเอาต์พุตที่จำเป็น

ตอนนี้แนวคิดของขั้นตอนวิธีมีการจัดการในการเชื่อมต่อของสวิตซ์ย่อยกลาง2ตัว ซซึ่งจะเรียกว่า Aและ B มีแนวคิดที่ให้การเชื่อมต่อที่มีอยู่เดิมนั้นผ่าน A และ B เพื่อป้องกันการเกิดสายหลุด และนำมารวมกัน ซึ่ง A และ B จะนำส่วนที่จำเป็นของสวิตซ์ย่อยอินพุตและเอาต์พุต

ขั้นแรก แต่ละการเชื่อมต่อจะมีเพียงอินพุตตัวเดียวหรือเอาต์พุตตัวเดียว ซึ่งสืบเนื่องจากการรวมAและB ในวิธีคิดแบบดินสอและกระดาษ ซึ่งจะมีการย้ายการเชื่อมต่อที่คิดไว้

เริ่มจากรับอินพตหรือเอาต์พุตซึ่งเป็นหนึ่งเส้นทางของการเชื่อมต่อไปยังเอาต์พุตแล้วต่อไปยังการเชื่อมต่ออื่นๆที่อินพุต เอาต์พุตและอื่นๆ จนสิ้นสุดด้วยไม่มีการเชื่อมต่ออื่นๆ

ในแต่ละครั้งที่มีหนึ่งเส้นทางจากอินพุตไปยังเอาต์พุต การเชื่อมต่อจะถูกจัดสรรให้สวิตซ์ย่อย A เมื่อเส้นทางไปยังทิศอื่นๆ การเชื่อมต่อจะถูกจัดสรรให้กับ B

หลังจากที่ทุกการเชื่อมต่อนั้นขึ้นกับอินพุตตัวเดียวหรือเอาต์พุตตัวเดียวไม่มีแล้ว จะกลายเป็นกราฟวงกลมหรือเกิดวงวนขึ้นในการเชื่อมต่อ และเมื่อเส้นทางสมบูรณ์ การกำหนดการเชื่อมต่อไปยังสวิตซ์ย่อยๆ และการลบแต่ละการเชื่อมต่อของรายการการเชื่อมต่อ

มีการจัดเก็บข้อมูลที่น้อยลงหากไม่ใช่กราฟที่มีวงวนและจะมีการตรวจสอบและลบก่อน ในทางหนึ่งที่จะไม่ต้องตรวจสอบอินพุตหรือเอาต์พุตมากเกินหว่า2ครั้ง และไม่จะเป็นที่จะเก็บรายการของอินพุตและเอาต์พุตที่ได้รับการตรวจสอบ

มันไม่ตำเป็นว่า A หรือ B ที่จะได้รับทอศทางของเส้นทางเพราะ A และ B มีจำนวนเการเชื่อมต่อท่ากัน คือหนึ่งเส้นเชื่อมของทุกอินพุตและเอาต์พุตของสวิตซ์ย่อย

หลังจากที่การเชื่อมต่อได้ถูกจัดสรรแล้วในอาเรย์ที่อยู่ในซอฟต์แวร์ อิเล็กทรอนิกส์ของสวิตซ์จะสามารถปรับโครงสร้าง และปรับเปลี่ยนการเชื่อมต่อ สวิตซ์ที่ได้รับการออกแบบเพื่อให้ข้อมูลใหม่ถูกเขียนในระบบอิเล็กทรอนิกส์และจะมีผลต่อสัญญาณ ผลที่ได้จากการเชื่อมต่อที่มีการเคลื่อนย้ายแบบฉับพลัน จะมีการชะงักเล็กน้อยในการสื่อสาร ในสวิตซ์แบบเก่าจะมีการได้ยินเสียงเวลามีการสับเปลี่ยน

ขั้นตอนวิธีนี้เป็นรูปแบบหนึ่งของการเรียงลำดับทอพอโลจิคัล(อังกฤษ: Topological sorting) และเป็นส่วนหนึ่งของขั้นตอนวิธีควบคุมของสวิตซ์แบบทอดข้ามต่ำสุด