



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

Prof.
ShuoYen 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 wellknown
properties of these unicast devices, including various
zeroone 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 cutthrough coding, which allows digital signals
to progress through a multistage switching network
in a selfrouting manner with essentially zero delay.
The cutthrough characteristic also greatly reduces
the hardware complexity in switch construction.



