(4) MoonShine交换机构     Moonshine交换机构也是基于排序--选路（Batcher-Banyan）概念的，最初由Hui于1987年提出。它采用不同于Starlite的交换方法来避免Batcher-Banyan网络的输出竞争问题。Moonshine交换机构是为处理变长的分组而设计的，因而比单纯的ATM交换更具一般性。     为了解决输出端口的冲突，提出了一种和每个输入端口的输入排队相结合的三步算法，这种输入排队会引起HOL（队头）阻塞，因此，Moonshine要求在每个分组期间采用内部加速的方法来实现这个三步算法。     －问题和求解     面对要解决的问题：Starlite交换机构需要从阀门的最右边输出(对Banyan来讲是具有竞争同一输出端口的多个输入)反馈回排序网的输入。由于需加buffer和增大信元延迟，并且还要采取保证信元顺序等问题，所以系统控制复杂。     新的思路：把解决输出端口竞争之问题和每个输入端口的输入排队相结合，即通过三个阶段来解决，分别是：仲裁、认可、发送。     总体做法：(ⅰ) 先送出试探分组，试探对同一输出端口的竞争情况               (ⅱ)对有竞争同一输出端口的多个输入，只允许其中一个输入通过，其余暂等(注意：对暂等输入排队，存在HOL效应)               (ⅲ) 被认可可以发送的输入端口在无输出端口竞争的情况下穿过交换机构               (ⅳ) 要求交换机构具有一定的加速比(Speed up)     －三步算法     下图表示了MoonShine三步算法，分别是仲裁、认可和发送(对应(a)、(b)、(c))。     仲裁阶段要检查是否有冲突的信元在输入端等待。这一过程是通过发送一个称作请求的特殊“消息”来完成的。一旦这些竞争的请求被排序，并从中选出优胜者，就应通知其他等待的信元，这一功能在认可阶段完成。最后，获胜的输入端口将在发送阶段把信元发送出去。     为了对冲突进行仲裁，需设立一个本身的内部互连网。排序网通过排序可使得那些冲突的请求相互邻接在一起。按照排队后的顺序如果一个请求的前面没有相同的请求，它就可以继续下去（无输出竞争）。也就是说，在算法的第I阶段（仲裁阶段），每一输入端口i都将送出一个试探分组，这实际上是一个短请求分组，它仅含有源和目的地址对（i，ji）。     排序（Batcher）网按照分组的目的地址ji以非递减的顺序对请求进行排序。只有在排好的目的地址表里ji和它前面的值不同时，这个请求才被认可。所举例子中，具有源地址2、4和3的分组获得成功，并分别到达Batcher网的输出1、2和4。从输入1去往输出3的分组未获得成功，原因是另一分组（来自输入4）也同时要去往输出端口3。经过排序后，这两个冲突的分组出现在Batcher网的相邻出线上。     接下来输入端口需要知道仲裁的结果，或获胜或失败，这由阶段Ⅱ（认可阶段）来完成。仲裁阶段获胜的请求分组（i,ji）应当通过互连网络向输入端口i送一个认可消息。     这样，一个从Batcher网的输出K到输入K的固定连接（图b）使得已被接受的分组能从输入口K（排序后请求分组所处的位置）到Batcher-Banyan网的输出（也是输入）端口i发回一个认可分组。     在本例中，Batcher网的输出口1、2和4分别将获胜情况通知输入口1、2和4，这样使得这些输入端口向不同目的地发送ACK分组，其中，输入1的目的地为（2），输入2为（4），输入4为（3）。当目的地2、3、4收到ACK分组时，输入2、3、4就知道它们可以继续前行。     在阶段Ⅲ，收到认可的输入端口将通过Batcher-Banyan网发送信息分组，此时不会再有冲突出现在输出端口上，在阶段I中未成功的输入端口将把信息分组存储到输入缓冲器中，待到下一个仲裁阶段，经缓冲的分组将重新参加裁决。      ·由于在Moonshine的三步算法中，前两个阶段只是做了一些辅助操作，而未真正传送分组，所以这二步操作相当于交换机构内部增加的开销，所以在交换机构内部需要加速处理。      ·Hui的计算结果，其值约提高14%，也就是说如果外部输入端口速率是150Mbit/s，则内部链路操作速率为170Mbit/s左右。      ·之后有人提出了另一种交换机构：Sunshine。 （有兴趣的同学可查找有关Sunshine 交换结构的资料研究之）