Muriel Médard (MIT, Cambridge, MA):
Network Coding - A Personal Account of
Combining Theory and Practice
Abstract:
This talk seeks to illustrate the interplay between theoretical development and engineering implementation, with a personal slant. It centers on Network Coding (NC), a modern information theoretic development that leverages algebraic data manipulation during transport through a network to enhance resource usage. The addition of data manipulation to network modeling went beyond traditional graph theoretic considerations, allowing a significant relaxation of constraints that had original been treated as essential and, consequently, to the circumvention of impasses. The new model afforded opportunities for improved resource usage in existing networks through developments such as our Random Linear Network Coding (RLNC). While RLNC provided provably optimal throughput within standard theoretical frameworks, introducing it into the most common Internet transport protocol, Transmission Control Protocol (TCP), required an inventive reinterpretation of TCP’s control signals. Our recent theoretical results in Equivalence Theory show there is no benefit, in terms of throughput, in combining NC with the type of coding commonly used to palliate mistransmissions in error-prone media such as wireless links. These results confirm the sense behind current operational practice, but contradict long-standing folk-theorems regarding the benefit of joint coding. However, when other performance metrics such as energy consumption are taken into account, in practice we have shown that combining NC with coding for wireless links leads to marked, cumulative gains. We shall conclude the talk with open challenges and research directions driven by the coming convergence of data storage and networking. No background knowledge will be assumed.
Bio:
Muriel Médard is the Cecil H. Green Professor in the Electrical Engineering and Computer Science Department at MIT and leads the Network Coding and Reliably Communications Group at the Research Laboratory for Electronics at MIT. She has co-founded two companies to commercialize network coding, CodeOn and Steinwurf. She has served as editor for many publications of the Institute of Electrical and Electronics Engineers (IEEE), of which she was elected Fellow, and she is currently Editor in Chief of the IEEE Journal on Selected Areas in Communications. She was President of the IEEE Information Theory Society in 2012, and served on its board of governors for eleven years. She has served as technical program committee co-chair of many of the major conferences in information theory, communications and networking. She received the 2009 IEEE Communication Society and Information Theory Society Joint Paper Award, the 2009 William R. Bennett Prize in the Field of Communications Networking, the 2002 IEEE Leon K. Kirchmayer Prize Paper Award and several conference paper awards. She was co-winner of the MIT 2004 Harold E. Edgerton Faculty Achievement Award. In 2007 she was named a Gilbreth Lecturer by the U.S. National Academy of Engineering.
Peter Key (Microsoft Research, Cambridge, UK):
Networks, Auctions and the Cloud
Abstract:
Network allocation problems typically seek to assign various resources in the best possible way, perhaps to maximise user welfare or fairness, and which can often be framed as stochastic optimisations. Similar resource allocation problems occur in economic settings, such as online ad-auctions where users bid for slots, and where auctions are often used to allocate the slots. We illustrate the connections between the two areas by considering large-scale Ad-auctions where adverts are assigned over a continuum of search types. For this pay-per-click market, we provide an efficient and highly decomposed mechanism that maximizes social welfare. In particular, we show that the social welfare optimization can be solved in separate optimizations conducted on the time-scales relevant to the advertisement platform and advertisers. This decomposition is implemented in an adversarial setting. Exploiting the information asymmetry between the platform and advertiser, we describe a simple mechanism which incentivizes truthful bidding and has a unique Nash equilibrium that is socially optimal, and thus implements our decomposition. Further, we consider models where advertisers adapt their bids smoothly over time, and prove convergence to the solution that maximizes aggregate utility. In a Cloud setting, the goods allocated may be multidimensional and have associated temporal constraints, adding further layers of complexity. Questions of fairness and allocation remain, and we outline some of this scheduling and pricing issues in this exciting new area.
Bio:
Peter Key is a Principal Researcher at Microsoft Research, Cambridge. His current research interests focus on Networks, Economics, and Algorithms, spanning both theory and practice. In the past he has worked on Telecommunication Networks, Computer Networks and Social Networks. He is a Fellow of the ACM, IEEE, IET and IMA. Peter has a PhD and MSC in Statistics from London University and a MA in Mathematics from Oxford.