The Centre for Mathematics and ICT at Queen Mary will be an internationally leading and distinctive centre of critical mass, unique in the UK as a national centre bringing together world class mathematicians, computer scientists, and top flight academic and industrial expertise in information and communication technologies [ICT]. Its goal is to tackle research challenges in ICT, particularly unified models of networks and devices, through cross-cutting research in mathematics and theoretical computer science.

Mathematical modelling has played a central role in the development of computer networks; for just one example, models of network flow impacted the design of the Arpanet, the precursor of today’s Internet. Although significant, the traditional mathematics of networks is becoming increasingly strained, and distant from current technology. Current networks are highly dynamic – their topologies change over time – and more and more computation is being pushed into network nodes. In addition, with the rise of ad hoc networks of mobile devices, network architectures are becoming much more decentralised. Thus, mathematical modelling of networks has to come to terms with the fact that the traditional view of a network as a static graph is no longer viable.

Consequently, the driving focus of our Centre is the development of the fundamental theory of future networks. This will, of course, be inspired by current technological trends, but it will look past what is possible now to what might or will be possible in the future. Stated plainly, the right academic approach should attempt to leapfrog rather than chase present industrial developments. We admit that this vision is ambitious and demanding: we would not claim to be close to a unified model now, or in the very near future. However, for far-reaching results of longstanding significance to be obtained, input from mathematics, computer science, and engineering are all essential. The models themselves must be mathematically elegant, for them to persist; computer science methods, such as from logic and model checking and mobile processes, can bring significant leverage beyond the traditional technique of simulation; and it is essential for there to be a back-and-forth between engineering and mathematical ideas, if the force of the models is to be tested and convincingly demonstrated.

As we have emphasised in the introduction, almost all aspects of networks give rise to difficult and interesting mathematical problems. It is probably the statistics of networks that is the most established field. Nevertheless, there are still many unresolved questions: it is hard to ground the observed statistics in an empirically accurate model of the Internet (see Mondragon’s talk), and real data shows anomalies which are difficult to describe, or to explain by any model (see Griffin’s talk).

Simulation is another area rich in problems. Even quite simple simulations – such as that in Clegg’s talk – are capable of exhibiting complex, Internet-like behaviour, and can usefully be investigated as testbeds.

Not all networks are large: however, even small networks can be interesting. Olafsson draws attention to the problem of optimising power consumption in mobile networks: this has quite a satisfactory solution for cellular phones – where each cell has a base station which can direct the negotiation – but the problem becomes much harder when we are dealing with ad hoc, decentralised networks.

These problems are also close to the problems of ad hoc networks of mobile devices described in Toh’s talk. As he points out, it is not clear even what the mathematical description of an evolving network should be, and, even granted that, almost all areas of traditional network theory become problematic in this new context.

There are also problems which are much more fundamental. Almost all current communication – whether packet- or circuit-switched – prevents different messages from interfering with each other. Riis has some startling results which show that, if we allow network nodes to combine messages in “non-linear” ways, we can achieve significant efficiency gains. Although this work is far from implementation, its possible applications could be extremely significant.

“Some Mathematical Problems Related to Power Control in Mobile Wireless Systems”

Developments in computing and sensing hardware and in wireless communications have made it technologically feasible and economically viable to develop low-power sensor nodes that integrate general-purpose computing with multipurpose sensing and wireless communications capabilities. One of the new challenging problems for such networks is the problem of power control (roughly speaking, a low-power sensors is supposed to ‘sleep’ almost all time to save power, but be on the alert to transmit a signal to its neighbours if necessary).

Dr. Olafsson discussed some mathematical problems relating to power control in mobile wireless systems. He started with the iterative control algorithms that have been developed for cellular systems: here everything is controlled by a central base station, and good algorithms are known and quite well understood. He then discussed some of the issues that arisen when one tried to generalise these algorithms to the decentralised case of ad hoc networks. He discussed several approaches: iterative algorithms, differential equations and an agent-based approach using game theory.

The challenging problems are concerned with replacing heuristics by rigorous mathematics:

1. How to start a new transmission/transaction within the network having no central coordinator.
2. Dynamic control: conditions for equilibria under probabilistic time delays.
3. Game theory: local equilibria, the constructive semantics of Nash equilibria.

“Monitoring the Internet’s Interdomain Routing Dynamics”

Dr Griffin focused on the control plane primarily made up of dynamic routing protocols.

The global Internet is currently stitched together by the Border Gateway Protocol (BGP), which implements routing between so-called “autonomous networks” (these are entities such as large service providers). BGP routing updates – available at a number of public sites around the world – exhibit many of the statistical characteristics that we have come to expect of Internet data: high variability over many time scales, scale invariance, long-range correlations. Although these statistics are quite familiar, they are not well understood: in particular, BGP traffic shows strange and inexplicable deviations and artefacts on almost all time scales.

The talk posed a number of challenges concerning the modelling and analysis of this data, in particular:

1. We need a good, accurate description of the statistics which the BGP exhibits
2. We need rigorous, accurate statistical models.
3. Given such a model, could we, with any confidence, improve the protocol design?

“Analysis of Mobile Networks”

This talk addressed problems of networks (such as cellular networks, or ad hoc wireless networks) with a dynamically changing topology. There are, in this area, many more problems than solutions: some of the more challenging problems are these.

1. for cellular networks, how can one estimate the frequency of handoffs between cells (or macrocells, or clusters . . . )
2. for packet radio networks (where all nodes can be mobile) what is the optimal transmission range for best performance (so that routing and autoconfiguration still function, but interference is minimised). In particular, which transmission range gives maximum forward progress? (Given, say, a particular transmission strategy.)
3. what is an appropriate mathematical description for a dynamic network topology of this sort? Given such a description, can one estimate, for example, the node degrees? What would be a suitable shortest path routing algorithm? Is the Dijkstra shortest path algorithm still optimal?
4. how do empirical networks compare with statistical models (for example, the Waxman model) of self-similar networks?
5. how do we estimate the carrying capacity of ad hoc networks, where there is no fixed infrastructure? Relevant factors are:
   1. the number of neighbours
   2. the amount of interference
   3. how much traffic does route relaying cause?
   4. what influence does route length have on performance?
   5. how are these questions affected by routing and relaying policies?
6. Does mobility increase the capacity of networks?
• maybe so: it increases possibilities for communication links
• but probably not: it increases overhead, for example, for rerouting.

“Markov Chains and Buffering Strategies in Networks”

Richard Clegg described simulations of network traffic and the use of local buffers to control correlations in traffic. He proved interesting theorems for an extremely simple Markov Chain which has a known form for the auto-correlation function. These results are used to model packet traffic as an on-off series with a known correlation structure which exhibits long-range dependence with given parameters.

In the second part of his presentation, simulation results were given to show how local buffering could be used to change correlations at different lags. Buffers can be used to selectively suppress correlations and change the statistical nature of the traffic.

The challenging problems are to give a mathematical interpretation to the simulation results on the degree of fine control.

“Utilising public information in Network Coding”

Dr. Riis presented a number of interesting results on Network Coding, a new mathematical theory for information networks. Unlike traditional network theory, in which information does not interact as it flows through the network, the core notion of network coding is to allow and encourage mixing of data at intermediate network nodes: that is, intermediate nodes can use non-linear Boolean functions to combine data. A receiver sees these mixed data packets and reconstructs from them the messages that were originally intended for it. Because data mixing of this sort can avoid bottlenecks, quite dramatic performance gains are possible.

There are theoretical gains as well. Network coding gives a new measure of network capacity, and this measure has deep connections not only with the theory of error-correcting codes, but also with information-theoretic invariants of graphs such as the so-called “guessing number”.

“Traffic, topology, congestion and scalability”

Dr. Mondragon modelled the Internet as a graph which grows subject to certain restrictions. The Internet is a monster that has evolved through many years of uncontrolled activity, and growth models are known to yield quite good simulations of Internet statistics.

However, difficulties remain. The challenging problems are

1. to find a model which accurately represents the Internet: growth models can be easily made to look plausible, but finding a model that fits the subtler statistical properties of the Internet demands some tuning. Good models exhibit what is called interactive growth:
   • new nodes are preferentially linked to existing network nodes which have a large degree, but also
   • new edges appear between nodes which themselves have large degrees.
2. to understand the interaction between the structure of a network and the behaviour of the traffic on that network.
   • For example, what effect does the connectivity of a network have on when it succumbs to congestion?
   • Conversely, what statistics of a graph are relevant for predicting its network behaviour? One good statistic seems to be betweenness centrality, which measures how important a particular node is to communications between other nodes. Betweenness centrality seems to be a good predictor of average delay.
     The final goal of research such as this would be to use such models to understand why the Internet is as it is: for example, why is it so efficient? Why so fragile? Can it be improved?