Network Optimisation and Control
Many network management and control functions (routing, flow control, admission control, provisioning) perform some kind of resource allocation. Resource allocation problems can be formulated as dynamic constrained optimisation problems. Optimisation theory therefore provides a unified setting in which to specify the objectives of network control tasks. We are pursuing and developing the idea that the distributed control processes themselves can also be specified within an optimisation theoretic framework. Decomposition techniques, breaking down a global optimisation problem into many smaller sub-problems, play an important role. Our model captures the interactions between different processes, operating in different locations or different layers in the network, each trying to solve a local optimisation problem..
One of our research aims is to provide a programming environment and language to explore the optimisation decomposition semantics outlined above. We call this endeavour 'computational networking', recognising that it sees network control as a computational process. Aspects of optimisation, control theory, constraint satisfaction and programming language techniques are brought together. We are working with Imperial College and University College London to explore how model checking techniques can be used to verify the properties of processes defined in our optimisation context. Our broader aim is to provide an integrated suite of tools offering various types of analysis for design and verification of network infrastructure.
The agenda outlined above touches on several very active research areas. The combination of Optimisation and Control Theory has been applied successfully in the analysis of protocols for rate control in the Internet and power control in wireless networks. In Computer Science, there is great interest in process models that try to capture notions of interaction, communication, and concurrency in distributed systems. Our framework also connects with other fields such as Dynamic Systems, Game Theory, and Economics.
We are applying results from our work and from similar research to problems as they arise in BT's infrastructure design. A recent application has been the design of overload protocols to protect call control servers from overload conditions caused by flash crowds and similar events. Moreover, network design and architecture are inseparable from how the distributed control processes are organised. Accordingly, it is our view that distribution and decomposition of optimisation problems offers a structured framework within which to study network architecture.
Selected Publications
Papers
Interactions in Transport Networks, Electronic Notes in Theoretical Computer Science 141(5), 2005, 97-114
Presentations
A modelling framework for network processes based on Lagrangian duality (
PPT), Imperial College, London, April 2006
Interactions in Transport Networks (
PDF) Workshop on the Foundations of Interactive Computation, FInCo 2005, Edinburgh, April 2005.
People
Nigel Walker (Lead),
Ben Strulo and
Marc Wennink.
&text=Networks Research Centre)
