OPT 012 LECTURE:
"Applied Mathematics in Industrial Research"
2006-07, Winter Semester
Organized jointly by Dr. Lukas Kencl,
Intel Research, and Prof. RNDr. Ludek Kucera, DrSc.,
Department of Applied Mathematics (KAM).
Monday 9.00-12.20, approximately bi-weekly. Lecture room S1, the
Mala Strana building.
There will be a 1.5hr lecture on the topic, followed by a 1.5hr interactive
seminar, open to questions and some exercises. Students will be evaluated based on a final examination at the end of the lecture and on homework assignments after each lecture.
For past lectures please see here: Applied Methods in Industrial Research 2005-06.
Attendees of all interests and backgrounds welcome!
Program:
9.10.
Lukas Kencl,
Intel Research
"Adaptive Load Sharing in Networking Systems"
Abstract:
Performance and fault-tolerance demands often require that multiple processing units within a networking system (such as a network processor or a router) share the packet- or request-processing workload. Balancing the load among the multiple units is further complicated by the need for a flow-preserving packet-to-processor mapping and by the heavy-tailed flow popularity probability distribution. We will review several solutions originating from the field of distributed web caching, demonstrate the complexity of the problem and the need for traffic-adaptive solutions, and discuss some recently proposed algorithms and their performance.
Speaker Bio:
Lukas Kencl is a Senior Researcher at the Intel Research Laboratory in Cambridge since June 2003. Prior to joining Intel, he was a member of the IBM Zurich Research Laboratory (1999-2003). He received a Master's degree in Computer Science from the Charles University, Prague, Czech Republic, in 1995, and a Ph.D. degree in Communication Networks from the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in March 2003. For the past several years, he has been active in research of methods, algorithms and architectures for complex network elements, such as network processors, routers or network monitors.
[Talk Slides, including Homework ]
16.10.
Will Hasenplaugh, Intel Digital Enterprise Group, Hudson, MA, USA
"A Fast Cyclic-Redundancy-Check (CRC) Circuit"
Abstract:
Error detection and correction mechanisms allow networks to
achieve data rates arbitrarily close to Shannon's Channel Capacity.
However, as data rates increase, encoder / decoder complexity can limit
performance. We will examine some basic principles of error detection and
correction, digital circuits used to realize them and a new circuit for
implementing the ubiquitous Cyclic Redundancy Check. This new circuit has
a critical path which is O(log2(n)), where n is the input word size, and is a
significant improvement on standard Linear Feedback Shift Register
implementations which are O(n).
Speaker Bio:
Will Hasenplaugh joined Intel as a computer architect in 2002. He first worked in cryptographic algorithm development and is now designing
a new cache architecture based on Information Theory. He spent two years, prior
to joining Intel, in the IBM storage division, designing low-complexity signal
processing algorithms. Will holds a Master's degree in Electrical Engineering
from the University of Arizona.
[Talk Slides, including Homework]
23.10.
Milan Vojnovic,
Microsoft Research Cambridge
"File Swarming Systems"
Abstract:
File swarming is used in the Internet for peer-to-peer file sharing,
e.g. BitTorrent. The main feature of these systems is that a file is
disseminated by users exchanging file pieces. Performance of such
systems is captured, for example, by file download time and workload
imposed on a server. In this talk, I will talk about analysis results
that suggest how critical on performance are file-pieces replication
strategies and user non altruism in offering pieces only if receiving
pieces of interest in return.
Speaker Bio:
Milan Vojnovic is a researcher with systems and networking group at Microsoft Research, Cambridge, United Kingdom. His research interests are in performance and architecture of computer & communication systems in the areas of mobile communications, information dissemination, and network congestion control. He earned a Ph.D. degree in technical sciences, from EPFL, Switzerland in 2003. He earned both B.Sc. and M.Sc. in electrical engineering from FESB, the University of Split, Croatia, in 1995 and 1998, respectively. In 2001, he was an intern with the Maths Center, Bell Laboratories, Murray Hill, New Jersey. Since 2005, he has been a visiting lecturer at the University of Split.
[ Talk ] [Homework: questions on slides 16, 31, 33, 41, 56, 60, 61, 62]
20.11.
Joerg Widmer,
NTT DoCoMo Labs, Munich
"Network Coding for Efficient Communication in Wireless Networks"
Abstract:
We show that network coding allows to realize significant energy
savings in a wireless ad-hoc network, when each node of the network is
a source that wants to transmit information to all other nodes.
Energy efficiency directly affects battery life and thus is a critical
design parameter for wireless ad-hoc networks. We propose an
implementable method for performing network coding in such a
setting. We analyze theoretical cases in detail, and use the insights
gained to propose a practical, fully distributed method for realistic
wireless ad-hoc scenarios.
The robustness provided by network coding also makes it possible to
deal with challenging network environments where end-to-end
connectivity is rare. Such environments can be found for example in
very sparse mobile networks where nodes meet only occasionally and are
able to exchange information, or in wireless sensor networks where
nodes sleep most of the time to conserve energy. Forwarding mechanisms
in such networks usually resort to some form of intelligent flooding,
as for example in probabilistic routing. A network coding based
forwarding algorithm can significantly reduce the overhead compared to
probabilistic routing, making it a suitable building block for a
delay-tolerant network architecture.
Speaker Bio:
Joerg Widmer is a senior researcher at DoCoMo Euro-Labs in Munich,
Germany, where he supervises projects in the area of wireless
communication. Before joining DoCoMo, he spent two years as
postdoctoral researcher at EPFL, Switzerland, doing research on
ultra-wide band networks. Joerg Widmer obtained his M.S. degree in
business administration and computer science and his Ph.D. degree in
computer science from the University of Mannheim, Germany in 2000 and
2003, respectively. In 1999 and 2000, he was at the ICSI Center for
Internet Research, Berkeley, CA working on equation-based congestion
control. His research interests include efficient algorithms for
wireless ad-hoc and sensor networks, network coding, and transport
protocols.
[ Talk and Homework ]
4.12.
Christos Gkantsidis,
Microsoft Research Cambridge
"Network Coding for Content Distribution"
Abstract:
Multicast routing, i.e. the distribution of information from a source node to a large number of destination nodes over a communication network, has attracted a lot of attention for more than a decade (e.g. native IP multicast, CDNs, and, recently, peer-to-peer networks). A fundamental problem in large scale distribution is the optimal scheduling of the data streams. Recently, network coding proposed a novel solution to the scheduling problem by encouraging the network nodes to mix the transmitted data. In this talk, we will review network coding, study its advantages over the traditional store-and-forward paradigm, and describe the design of Avalanche, which is a peer-to-peer system that uses network coding.
Speaker Bio:
Christos is a researcher in the Systems and Networking Research Group at Microsoft Research in Cambridge, UK. Prior to joining Microsoft, Christos had been a Ph.D. student at the College of Computing at Georgia Institute of Technology, GA, USA. His current research interests include the areas of content distribution networks, peer-to-peer technologies, analysis and modelling of complex communication networks.
Christos is a member of the IEEE and the ACM.
[Talk Background, including Homework]
18.12.
Leo Eisner,
Schlumberger Cambridge Research
"Applying Graph Theory to Earthquakes"
Abstract:
Firstly, we provide a brief introduction into Earthquake seismology, which has recently been put in use to monitor oil repositories. Further, we shall discuss a specific application of graph theory to microseismic events. To visualize and more effectively analyze the microseismic datasets, we propose to represent the data as a graph in which individual events are represented as nodes while physical relations between the events are represented as edges. For example, a physical relationship may be a measure of the waveform similarity; i.e., doublets. A large number of algorithms developed for graphs can then be applied to the analysis of microseismic events. For example, we group doublets into multiplets by a simple search for the connected parts of a graph. Based on this grouping, we can then determine precise relative source locations and possibly composite focal mechanisms, which simplifies the structural interpretation of the microseismic data.
Speaker Bio:
Leo is a senior research scientist at Schlumberger Research in Cambridge, UK since April 2001. He received an M.Sc. degree in Physics from the Charles University, Prague, Czech Republic, in 1994, and a Ph.D. degree in Geophysics from California Institute of Technology, Pasadena, California, USA, in 2001. His research interests include seismology and analysis of microseismic events.
[Talk materials available upon request.]
For more information please contact Ludek Kucera,
<ludek@kam.ms.mff.cuni.cz>, or
Lukas Kencl, <lukas.kencl@ieee.org>.