Unified Algebraic Theory for Sorting, Routing, Multicasting, & Concentration Networks

By

Prof. Shuo-Yen Robert Li
Professor of Information Engineering, CUHK
 
 

Date: May 11, 2009 (Monday)

Time: 4:00p.m. - 5:00 p.m.

Venue:Rm. 1009 William MW Mong Engineering Building, CUHK

 

Abstract :

This talk is presented in the plain language plus intuitive examples. Multistage networks for sorting, routing, and concentration are commonly deployed in packet switching and parallel processing. In terms of switching, these are all unicast devices. The arithmetic of these devices can be treated as a special case of Boolean algebra over a distributive lattice. The general Boolean principle applies to multicast switching as well. Moreover, it unifies and demystifies well-known properties of these unicast devices, including various zero-one principles. One of its useful results is the generalization of the Multicast Concentrator Theorem with practical application in Internet routing/switching. Concomitant to the Boolean algebra is the theory of cut-through coding, which allows digital signals to progress through a multistage switching network in a self-routing manner with essentially zero delay. The cut-through characteristic also greatly reduces the hardware complexity in switch construction.