on 18-03-2011
João Sobrinho (IST - TU Lisbon / IT).
March 18, 2011, Friday, 16h15m.
Abstract: What is the minimum number of links in a network whose failure interrupts the flow of traffic from a node X to a node Y? If all paths in the network can be used to carry traffic, then Menger’s theorem provides the answer: the minimum number of links whose failure interrupts the flow of traffic from X to Y equals the maximum number of link-disjoint paths from X to Y, a quantity which can be computed in polynomial-time. However, routing policies preclude some paths from carrying traffic. Moreover, these routing policies are substantiated by routing protocols which, alas, discover some paths all the while hiding others. The bottom line is that, in a networking setting, the question above is not answered by Menger’s theorem or any other result from graph theory. We algebraically identify a broad class of routing policies for which we can answer our opening question with a polynomial-time algorithm. Complementarily, we show the counter-intuitive behavior of routing policies that call out of that class. The theory is applied to a public description of the Internet’s topology to quantify how much of its intrinsic connectivity is lost to current routing policies and how much is recovered with simple alternative ones.
Room: 3.10, Mathematics
Support: SQIG/IT with support from FCT and FEDER, namely via the following projects:
* PTDC/MAT/68723/2006 KLog;
* POCI/MAT/55796/2004 QuantLog;
* POSC/EIA/55582/2004 Space-Time-Types
More Information..
on 17-03-2011
Side Information Fusion for Multiview Distributed Video Coding
Frederic Dufaux, CNRS Research Director at Telecom ParisTech
Sala de Reuniões do IT, Torre Norte, 10º Piso
17 Março, 11h
Distributed video coding (DVC) offers a number of potential advantages which make it well-suited for emerging upstream applications. First, it allows for a flexible partitioning of the complexity between the encoder and decoder. Furthermore, due to its intrinsic joint source-channel coding framework, DVC is robust to channel errors. Because it does not rely on a prediction loop, DVC provides codec independent scalability. DVC is also well-suited for multi-view coding by exploiting correlation between views without requiring communications between the cameras, which may be an important architectural advantage. Moreover, multi-view coding is gathering a lot of interests lately, as it is attractive for a number of applications such as stereoscopic video, free viewpoint television, multi-view 3D television, or camera networks for surveillance and monitoring. When compared to mono-view, the main difference in multi-view DVC is that the Side Information (SI) can be computed not only from previously decoded frames in the same view, but also from frames in other views. It is then possible to generate multiple SI using either motion compensated temporal interpolation or disparity compensated interpolation. The next issue is how to effectively combine these different predictions. For fusion at the decoder side, the challenge lies in the difficulty of determining the best predictor. In this talk, we will introduce some new SI fusion approaches and present performance assessment results.
Biography
Dr. Frederic Dufaux is a CNRS Research Director at Telecom ParisTech. He is also Editor-in-Chief of Signal Processing: Image Communication. Frederic received his M.Sc. in physics and Ph.D. in electrical engineering from the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in 1990 and 1994 respectively. Frederic has over 20 years of experience in research. He has been a senior research fellow at EPFL, chief scientist at Emitall Surveillance, principal solutions architect at Genimedia, senior member of research staff at Compaq / Digital Equipment, postdoctoral fellow at MIT, and visiting researcher at AT&T Bell Laboratories. Frederic has been involved in the standardization of digital video and imaging technologies for more than 15 years, participating both in the MPEG and JPEG committees. He is currently co-chairman of JPWL and JPSearch. He is the recipient of two ISO awards for these contributions. His research interests include image and video coding, distributed video coding, 3D video, visual quality assessment, video surveillance, privacy protection, image and video analysis, multimedia content search and retrieval, video transmission over wireless network. He is the author or co-author of more than 100 research publications and holds 17 patents issued or pending.
More Information..