Speaker: Dr. S. Sergeev Abstract: It is well known that the sequence of max-algebraic powers of irreducible nonnegative matrices is ultimately periodic. We express this periodicity in terms of CSR-representations and give new bounds on the transient time after which the max-algebraic powers become periodic.

Hamilton Institute Seminars (HD / large)

Periodicity of Matrix Powers in Max Algebra

Speaker: Prof. L. Rizzo Abstract: In this talk I will give a survey of solutions and tools that we have developed in recent years to achieve extremely high packet processing rates in commodity operating systems, running on bare metal and on virtual machines. Our NETMAP framework supports processing of minimum size frames from user space at 10 Gbits per second (14.88 Mpps) with very small CPU usage. Netmap is hardware independent, supports multiple NIC types, and it does not require IOMMU or expose critical resources (e.g. device registers) to userspace. A libpcap library running on top of netmap gives instant acceleration to pcap clients without even the need to recompile applications. VALE is a software switch using the netmap API, which delivers over 20 Mpps per port, or 70 Gbits per second with 1500 byte packets. Originally designed to interconnect virtual machines, VALE is actually very convenient also as a testing tool and as a high speed IPC mechanism. More recently we have extended QEMU, and with a few small changes (using VAEL as a switch, paravirtualizing the e1000 emulator, and with small device driver enhancements), we reached guest to guest communication speeds of over 1 Mpps (with socket based clients) and 5 Mpps (with netmap based clients). NETMAP and VALE are small kernel modules, part of standard FreeBSD and also available as add-on for Linux. QEMU extensions are also available from the author and are being submitted to the qemu-devel list for inclusion in the standard distributions.

Very High Speed Networking in VMs and Bare Metal

Speaker: C. Lancia Abstract: Consider the arrival process defined by t_i=i + xi_i, where xi_i are i.i.d random variables. First introduced in the 50's, this arrival process is of remarkable importance in Air Traffic Flow Management and other transportation systems, where scheduled arrivals are intrinsically subject to random variations; other frameworks where this model has proved to be capable of a good description of actual job arrivals include health care and crane handling systems. This talk is ideally divided in two parts. In the first half, I will show through numerical simulations two of the most important features of the model, namely, the insensitivity with respect to the nature (i.e. the law) of the delays xi_i and the extremely valuable goodness of fit of simulated queue length distribution against the empirical distribution obtained from actual arrivals at London Heathrow airport. Further, I will show that the congestion related to this process is very different from the congestion of a Poisson process. This is due to the negative autocorrelation of the process. In the second part, I will restrict the analysis to the case where the delays xi_i are exponentially distributed. In this context, I will show some preliminary results on a possible strategy to find the stationary distribution of the queue length using a bivariate generating function.

ROMA: Random Overlook Mastering ATFM

Speaker: Dr. M. Dohler Abstract: The unprecedented communication paradigm of machine-to-machine (M2M), facilitating 24/7 ultra-reliable connectivity between a prior unseen number of automated devices, is currently gripping both industrial as well as academic communities. Whilst applications are diverse, the in-home market is of particular interest since undergoing a fundamental shift of machine-to-human communications towards fully automatized M2M. The aim of this presentation is thus to provide academic, technical and industrial insights into latest key aspects of wireless M2M networks, with particular application to the emerging smart city and smart grid verticals. Notably, I will provide an introduction to the particularities of M2M systems. Architectural, technical and privacy requirements, and thus applicable technologies will be discussed. Notably, we will dwell on the capillary and cellular embodiments of M2M in smart homes. The focus of capillary M2M, useful for real-time data gathering in homes, will be on IEEE (.15.4e) and IETF (6LoWPAN, ROLL, COAP) standards compliant low-power multihop networking designs; furthermore, for the first time, low power Wifi will be dealt with and positioned into the eco-system of capillary M2M. The focus of cellular M2M will be on latest activities, status and trends in leading M2M standardization bodies with technical focus on ETSI M2M and 3GPP LTE-MTC. Open technical challenges, along with the industry’s vision on M2M and its shift of industries, will be discussed during the talk.

Machine-to-Machine in Smart Cities & Smart Grids Vision, Technology & Applications

Speaker: Prof. R. Vinter Abstract: Estimates on the distance of a nominal state trajectory from the set of state trajectories that are confined to a closed set have an important unifying role in optimal control theory. They can be used to establish non-degeneracy of optimality conditions such as the Pontryagin Maximum Principle, to show that the value function describing the sensitivity of the minimum cost to changes of the initial condition is characterized as a unique generalized solution to the Hamilton Jacobi equation, and for numerous other purposes. We discuss the validity of various presumed distance estimates and their implications, recent counter-examples illustrating some unexpected pathologies and pose some open questions.

State Constrained Optimal Control

Speaker: Prof. L. Tassiulas Abstract: Increased replication of information is observed in modern wireless networks either in pre-planned content replication schemes or through opportunistic caching in intermediate relay nodes as the information flows to the final destination or through overhearing of broadcast information in the wireless channel. In all cases the available other node information might be used to effectively increase the efficiency of the information delivery process. We will consider first an information theoretic perspective and present a scheme that exploits the opportunistically available overheard information to achieve the Shannon capacity of the broadcast erasure channel. Then we will consider information transport in a multi-hop flat wireless network and present schemes for spatial information replication based on popularity, in association with any-casting routing schemes, that achieve asymptotically optimal performance.

Effective Information Delivery Through Opportunistic Replication in Wireless Networks

Speaker: Prof. P. van den Driessche Abstract: The World Health Organization estimates that there are 3 to 5 million cholera cases per year with 100 thousand deaths spread over 40 to 50 countries. For example, there has been a recent cholera outbreak in Haiti. Cholera is a bacterial disease caused by the bacterium Vibrio cholerae, which can be transmitted to humans directly by person to person contact or indirectly via the environment (mainly through contaminated water). To better understand the dynamics of cholera, ageneral ordinary differential equation compartmental model is formulated that incorporates these two transmission pathways as well as multiple infection stages and pathogen states. In the model analysis, some matrix theory is used to derive a basic reproduction number, and Lyapunov functions are used to show that this number gives a sharp threshold determining whether cholera dies out or becomes endemic. In the absence of recruitment and death, a final size equation or inequality is derived, and simulations illustrate how assumptions on cholera transmission affect the final size of the epidemic. Further models that incorporate temporary immunity and hyperinfectivity using distributed delays are formulated, and numerical simulations show that oscillatory solutions may occur for parameter values taken from cholera data in the literature.

Dynamics of Some Cholera Models

Speaker: Prof. A. Banchs Abstract: Distributed Opportunistic Scheduling (DOS) techniques have been recently proposed to improve the throughput performance of wireless networks. With DOS, each station contends for the channel with a certain access probability. If a contention is successful, the station measures the channel conditions and transmits in case the channel quality is above a certain threshold. Otherwise, the station does not use the transmission opportunity, allowing all stations to recontend. A key challenge with DOS is to design a distributed algorithm that optimally adjusts the access probability and the threshold of each station. To address this challenge, in this paper we first compute the configuration of these two parameters that jointly optimizes throughput performance in terms of proportional fairness. Then, we propose an adaptive algorithm based on control theory that converges to the desired point of operation. Finally, we conduct a control theoretic analysis of the algorithm to find a setting for its parameters that provides a good tradeoff between stability and speed of convergence. Simulation results validate the design of the proposed mechanism and confirm its advantages over previous proposals.

Distributed Opportunistic Scheduling: A Control Theoretic Approach

Speaker: Dr. M. Fiore Abstract: Vehicular networks are large scale communication systems that exploit wireless technologies to interconnect moving cars. Vehicular networks are envisioned to provide drivers with real time information on potential dangers, on road traffic conditions, and on travel times, thus improving road safety and traffic efficiency. Direct vehicle-to-vehicle communication is also foreseen to enable nonsafety applications, such as pervasive urban sensing and fast data dissemination throughout metropolitan regions. The quantity and relevance of potential usages make pervasive inter-vehicular communication one of the highest impact future applications of the wireless technology, which explains the growing interest of both industry and academy towards this research field. In this talk, we will address two intertwined topics in vehicular networks: the modeling of vehicular mobility in large scale urban environments and the topological characterization of the vehicular network built on top of such a mobility. Both are fundamental, yet often oversought, aspects of vehicular networking, defining the strengths and weaknesses of the vehicle-to-vehicle communication system and dictating the rules for the design of dedicated protocols.

Large-scale urban vehicular networks: mobility and connectivity

Speaker: Dr. T. Weber Abstract: Inter-cellular variability in the duration of the cell cycle is a well documented phenomena which has been integrated into mathematical models of cell proliferation since the 70’s. Here I present a minimalist stochastic cell cycle model that allows for inter-cellular variability at the level of each single phase, i.e. G1, S and G2M. Fitting this model to flow cytometry data from 5-bromo-2'-deoxyuridine (BrdU) pulse labeling experiments of two different cell lines shows that the mean field predictions mimic closely the measured average kinetics. However as indicated by bayesian inference, scenarios with deterministic or purely stochastic waiting times especially in the G1 phase seem to explain the data equally well. To resolve this uncertainty a novel experimental proto col is proposed able to provide sufficient information about cell kinetics to fully determine both the inter-cellular average and variance of the duration of each of the phases. Finally I present a case in which this model is extended in order to estimate cell cycle parameters in germinal centers. The latter play a central role in the generation of highly effective antibodies that protect our body against invading pathogens.

Learning Cell Cycle Variability at the Level of each phase

Speaker: Prof. B. Hanzon Abstract: Exponential Polynomial Trigonometric (EPT) functions are being considered as probability density functions. A specific matrix-vector representation is proposed for doing calculations with these functions. We investigate when these functions are non-negative and under which conditions the density functions are infinitely divisible--in which case there is an associated Levy process. Application to option price computations in finance will be presented. For background information on this topic the website www.2-ept.com can be considered.

EPT functions: Non-negativity analysis, Levy processes and Financial applications

Speaker: Dr. F. Gringoli Abstract: Experimenting in the field is a key activity for the evolution of the modern Internet: this is especially true for radio access protocols like IEEE 802.11 that are usually affected by unpredictable issues due to noise, competing stations and interference. Here we introduce OpenFWWF, an opensource firmware that implements a fully compliant 802.11 MAC on off-the-shelf WiFi boards: we show how it can be used in conjunction with the Linux kernel to play with the wireless stack. To this end we further demonstrate how we can easily customize the basic DCF access firmware to explore either performance boosting variations or to measure physical properties of the wireless channel.

Playing with Standards: the IEEE 802.11 case

Speaker: Dr. M. A. Chaudry Abstract: Network coding has gained significant interest from the research community since the first paper by Alshwede et al., in 2000. Network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. We focus on network coding for wireless networks; specifically we investigate the Index Coding problem. In wireless networks, each transmitted packet is broadcasted within a certain region and can be overheard by the nearby users. When a user needs to transmit packets, it employs the Index Coding that uses the knowledge of what the user's neighbors have heard previously (side information) in order to reduce the number of transmissions. The objective is to satisfy the demands of all the users with the minimum number of transmissions. With the Index Coding, each transmitted packet can be a combination of the original packets. The Index Coding problem has been proven to be NP-hard, and NP-hard to approximate. Noting that the Index Coding problem is not only NP-hard but NP-hard to approximate, we look at it from a novel perspective and define the Complementary Index Coding problem; where the objective is to maximize the number of transmissions that are saved by employing the Index Coding compared to the solution that does not involve coding. We prove that the Complementary Index Coding problem can be approximated in several cases of practical importance. We investigate both the multiple unicast and multiple multicast scenarios for the Complementary Index Coding problem for computational complexity, and provide polynomial time approximation algorithms.

In Search of Optimality: Network Coding for Wireless Networks

Speaker: Dr. B. Radunović Abstract: Consider a distributed system that consists of a coordinator node connected to multiple sites. Items from a data stream arrive to the system one by one, and are arbitrarily distributed to different sites. The goal of the system is to continuously track a function of the items received so far within a prescribed relative accuracy and at the lowest possible communication cost. This class of problems is called a continual distributed stream monitoring. In this talk we will focus on two problems from this class. We will first discuss the count tracking problem (counter), which is an important building block for other more complex algorithms. The goal of the counter is to keep a track of the sum of all the items from the stream at all times. We show that for a class of input loads a randomized algorithm guarantees to track the count accurately with high probability and has the expected communication cost that is sublinear in both data size and the number of sites. We also establish matching lower bounds. We then illustrate how our non-monotonic counter can be applied to solve more complex problems, such as to track the second frequency moment and the Bayesian linear regression of the input stream. We will next discuss the online non-stochastic experts problem in the continual distributed setting. Here, at each time-step, one of the sites has to pick one expert from the set of experts, and then the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret with respect to the optimal choice in hindsight, while simultaneously keeping communication to the minimum. This problem is well understood in the centralized setting, but the communication trade-off in the distributed setting is unknown. The two extreme solutions to this problem are to communicate with everyone after each payoff, and not to communicate at all. We will discuss how to achieve the trade-off between these two approaches. We will present an algorithm that achieves a non-trivial trade-off and show the difficulties of further improving its performance.

On Continuous Counting and Learning in a Distributed System

Speaker: Dr. C. Cano Abstract: Wireless Sensor Networks (WSNs) are networks formed by highly constrained devices that communicate measured environmental data using low-power wireless transmissions. The increase of spectrum utilization in non-licensed bands along with the reduced power used by these nodes is expected to cause high interference problems in WSNs. Therefore, the design of new dynamic spectrum access techniques specifically tailored to these networks plays an important role for their future development. In this talk the main challenges of dynamic spectrum access in WSNs will be described and a first approach to coordinate sensor nodes will be presented.

Multi-channel MAC Protocols for Wireless Sensor Networks

The Hamilton Institute is a multi-disciplinary research centre established at the National University of Ireland, Maynooth in November 2001. The Institute seeks to provide a bridge between mathematics and its applications in ICT and biology. In this podcast feed, we make accessible some of the best seminars held by members of the Hamilton Institute, visitors or guest speakers. Futhermore, it will also contain the lectures give as part of the 'Network Mathematics Graduate Programme'.

hubhopper

Hamilton Institute Seminars (HD / large)

hubhopper