Network Coding/Routing Techniques for Multicasting Networks         

                  Prof.Sun-Yuan Kung(貢三元教授)
Dept.of Electrical Engineering,Princeton University,USA

 

時  間:中華民國九十五年一月十日(星期二)
地  點:國立清華大學資訊電機館B1演講廳
主辦單位:國立清華大學積體電路設計技術研發中心
     經濟部學界開發產業技術計畫「前瞻高效能低耗能之雙處理器系統技術研發」
     
協辦單位:工業技術研究院系統晶片技術發展中心、台灣SoC推動聯盟、清華大學資訊工程學系、

         

大會主席:國立清華大學 資訊工程學系 賴尚宏教授
議程主席:國立交通大學 電子工程學系 林大衛教授


                    Agenda

Time
Topic
Speaker

Chairman

9:30-9:50
Registration
9:50-10:00
Opening工研院STC 張志偉副主任
10:00-10:50
Hybrid Network Routing/Coding
Prof.S.Y.Kung
工研院STC
張志偉副主任
10:50-11:10
Coffee Break
11:10-12:00
Network Utility Maximization
Prof. S.Y.Kung
清大資工系
石維寬教授
12:00-14:00
Lunch Break
14:00-14:50
Minimum Energy Multicasting in Mobile Ad Hoc Network
Prof. S.Y.Kung
交大電子系
林大衛教授
14:50-15:20
Multicasting Correlated Data
Prof. S.Y.Kung
交大電子系
林大衛教授
15:20-15:40
Coffee Break
15:40-16:30
Practical Network Coding&Discussion
Prof. S.Y.Kung
清大資工系
賴尚宏教授
費用:1.1月6日以前報名及繳費:學生300元;教師、工研院、SoC聯盟會員500元;其他1,500元。
   2.1月6日以後報名及繳費:學生400元、教師、工研院、SoC聯盟會員700元;其他1,800元。
(以上費用包含講義、餐盒、茶點)
諮詢專線:(03)5742300、5742311     FAX:(03)5745594
網路報名:http://pllab.cs.nthu.edu.tw/moeapac/20060110workshop/workshop.php
     名額共120位[1月6日(五)截止網路報名]
繳費方式:報名費請于1月6日報名截止日期之前,以郵局匯票或支票(僅接受即期支票)方式寄達
     【匯票戶名:國立清華大學  支票戶名:國立清華大學】
地址:30013 新竹市光復路二段101號 清華大學積體電路中心 曾雯姬小姐 收

 

Abstract

In a computer network, broadcasting to a collection of receivers is ordinarily handled by distributing the information along a multicast tree. The maximum rate at which the sender s can send to any particular receiver t, is derivable as the minimum cut between s and t. Hence the maximum possible rate at which one could hope to broadcast common information from s to all receivers is the minimum of these minimum cuts over the set of  receivers.  This ideal maximum  rate is termed multicast capacity.

In this talk, we will discuss some important progresses recently made to the theory and practice of network coding for multicasting.  It establishes vital evidences to show that the network coding approach holds advantages over network routing in  many aspects, such as (1) resource efficiency, (2) computational efficiency, and (3) robustness to network dynamics, etc.  The main topics to be covered are summarized below:

1. Hybrid Network Routing/Coding:  First we shall establish a fundamental graph theorem that unifies Edmonds' Routing Theorem and Ahlswede et al.'s network coding theorem.  It shows that the multicast capacity can be achieved even if information mixing is only allowed on links entering relay nodes.

2.  Network Utility Maximization:  We will provide a comprehensive treatment on the network utility maximization related to multicasting.   In order to determine the multicast rate and the bit-rate for achieving optimal allocation of network resources, we propose a special constrained optimization formulation solvable by   a novel Lagrangian dual approach.   This leads to an algorithm  based on repeatedly solving the well established shortest-path problems.

3. Minimum Energy Multicasting in Mobile Ad Hoc Network:   We shall  demonstrate that the minimum energy-per-bit can be attained by performing network coding. Moreover,  thanks to the unique max of flows structure, it computationally amounts to solving a linear programming solution.  This is in sharp contrast with the NP-hardness of constructing the minimum energy multicast tree as the optimal routing solution.

4. Multicasting Correlated Data:  We shall also address the problem of multicasting correlated information from
two source nodes  to multiple destination nodes.  This problem  remains one of the most challenging problem in
information theory as it involves a joint consideration of compression and information relaying.  Although the
optimal admissible rate region was previously characterized,  we will describe a practical communication scheme for the case where the two sources are related by a binary symmetric channel.

5.  Practical Network Coding:  A practical network coding strategy is vital for the technique can be economically integrated into the full-scale communication networks. The talk will discuss a scheme for implementing network coding in a practical packet network and a network coding node architecture to synchronize arbitrarily arriving packets as well as to support a distributed processing framework for practical network coding. Such a framework can effectively obviate the need for information to be communicated synchronously through the network.

About the Speakers

Prof. Sun-Yuan Kung

Professor S.Y. Kung received his Ph.D. Degree in Electrical Engineering from Stanford University in 1977. In 1974, he was an Associate Engineer of Amdahl Corporation, Sunnyvale, CA. From 1977 to 1987, he was a Professor of Electrical Engineering-Systems of the University of Southern California, L.A. Since 1987, he has been a Professor of Electrical Engineering at the Princeton University. In addition, he held a Visiting Professorship at the Stanford University  and the Delft University of Technology (1984); a Toshiba Chair Professorship at the Waseda University,  Japan (1984); an Honorary Professorship at the Central China University of  Science and Technology (1994);  and  a Distinguished Chair Professorship at the Hong Kong Polytechnic University (2001- 2003). Since 1990, he has been the Editor-In-Chief of the Journal of VLSI Signal Processing Systems.

        His research interests include  VLSI array processors, system modelling and identification, neural networks, wireless communication, sensor array processing, multimedia signal processing, bioinformatic data mining and biometric authentication. Professor Kung has co-authored more than 400 technical publications and numerous textbooks  including  "VLSI and Modern Signal Processing," with Russian translation, Prentice-Hall (1985), ``VLSI Array Processors'', with Russian and Chinese translations, Prentice-Hall (1988); ``Digital Neural Networks'', Prentice-Hall (1993) ; ``Principal Component Neural Networks'', John-Wiley (1996); and ``Biometric Authentication: A  Machine Learning and Neural Network Approach'', Prentice-Hall (2004).

         Professor Kung is a Fellow of IEEE since 1988.  He served as a Member of the Board of Governors of the IEEE Signal Processing Society (1989-1991).  He was a founding member of several Technical Committees (TC) of the IEEE Signal Processing Society , including  VLSI Signal Processing TC (1984), Neural Networks for Signal Processing  TC (1991) and Multimedia Signal Processing TC (1998), and was appointed as the first Associate Editor in VLSI Area (1984) and later the first Associate Editor in Neural Network (1991)  for the IEEE Transactions on Signal Processing. He presently serves on Technical Committees on Multimedia Signal Processing.

         Professor Kung  was a recipient of  IEEE Signal Processing Society's Technical Achievement Award for
his contributions on "parallel processing and neural network algorithms for signal processing" (1992);  a
Distinguished Lecturer of IEEE Signal Processing Society (1994) ; a recipient of IEEE Signal Processing Society's Best Paper Award  for his publication on principal component neural networks (1996); and a recipient of the IEEE Third Millennium Medal (2000).