Author :
Li, Shuo-Yen ; Adachi, Fumiyuki ; Liu, Zhen
Abstract :
For routing, sorting, parallel processing, and other purposes, a multistage interconnection network (MIN) is often deployed for interconnecting 2×2 switches into a large one, which is then characterized by interstage connection patterns in the MIN. A transform of a mathematical object in general means an alternative characterization, and the purpose is to facilitate the manipulation on the object as well as the rendering of attributes. The most commonly seen MINs can be algebraically transformed into integer sequences. Such a transform readily characterizes: • network equivalence under intrastage rearrangement • routability of the network • unique routing control over the network • conditionally nonblocking properties of the large switch constructed by the network • rearrangeability of the tandem cascade between two copies of the network Classical switching theory treats I/O of a switch simply as two sets and solves switching problem by combinatorics. The present talk belongs to algebraic switching theory that studies the geometric structure of I/O, which can be linear, circular, or n-dimensional.