Colloquium

Speaker: Professor Tony T. Lee (Chinese University of Hong Kong)
Title: Information Theoretic Aspects of Packet Switching Systems
Time: 2009-12-10 (Thu.)  15:00 - 16:00
Place:
Abstract: In circuit switched networks, reliable communication requires the error-tolerant transmission of bits over noisy channels. In packet switched networks, however, not only can bits be corrupted with noise, but resources along connection paths are also subject to contention. In this talk, we will show the similar characteristics of noise and contention and address the following analogies between a packet switching system and a transmission channel: 1. Buffering against contention is a process that is similar to the error correction of noise corrupted signals. A signal-to-noise ratio that represents the carried load of packet switches can be deduced from the Boltzmann model of packet distribution. Consider Clos network as a noisy channel, we show that the maximum data rate satisfies Shannon's noisy channel capacity formula. 2. When deflection routing is applied to the Clos networks the loss probability decreases exponentially, which is similar to the exponential behavior of the error probability of binary symmetric channels with random channel coding. In information theory, this result is stated as the noisy channel coding theorem. 3. The similarity between Hall's condition of bipartite matching and expander graph manifests the resemblance between non-blocking route assignments and error-correcting codes. An extension of Sipser-Speilman decoding algorithm of expander codes to route assignments of Benses networks is given to illustrate their correspondence. 4. Scheduling in packet switching serves the same function as source coding in digital transmission. The smoothness of scheduling, like noiseless channel coding, is bounded by entropy inequalities. 5. The sampling theorem of band-limited signals provides the cornerstone of digital communication and signal processing. Recently, Birkhoff-von Neumann decomposition of traffic matrices has been widely applied to packet switches. With respect to the complexity reduction of packet switching, we show that the decomposition of a doubly stochastic traffic matrix plays a similar role to that of the sampling theorem in digital transmission. We conclude that packet switching systems are governed by mathematical laws that are similar to those of digital transmission systems as envisioned by Shannon in his seminal 1948 paper, A Mathematical Theory of Communication.  
  || Close window ||