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

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

สวิตช์แบบครอสส์บาร์ขนาด 16x16 ที่สร้างจาก สวิตช์แบบครอสส์บาร์ขนาด 4x4 จำนวน 12 อัน

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

ความเป็นมาของการเปลี่ยนแปลงโครงสร้าง

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

สวิตช์แบบครอสส์บาร์มีความสามารถในการเชื่อมต่ออินพุต 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) และเป็นส่วนหนึ่งของขั้นตอนวิธีควบคุมของสวิตซ์แบบทอดข้ามต่ำสุด

การนำสวิตซ์มาใช้งาน

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

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

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

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

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

สวิตซ์สมัยใหม่

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

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

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

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

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

ตัวอย่างการเปลี่ยนเส้นทางสวิตซ์

ดูเพิ่ม

• Time Slot Interchange
• Clos Network
• Crossbar switch
• Banyan switch
• Fat tree
• Omega network

อ้างอิง

Clos, Charles (1953). "A study of non-blocking switching networks" (PDF). Bell System Technical Journal. 32 (2): 406–424. ISSN 0005-8580. Unknown parameter |month= ignored (help)