|
|
|
|
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.
|
|
|
|