Main results so far:
- The design of an algorithm for optimal routing based on
multicommodity flow optimisation that
- is computationally tractable for online optimisation
- requires only small modifications to the packet
forwarding mechanisms used today
- provides a simple way of tuning the trade-off between
balance and utilisation.
- A flow analysis study
- A simulation platform.
When modelling the multi-commodity flow optimisation problem
we aggregate all traffic destined to a certain egress node
into one commodity.
It is this way of modelling the problem that both makes the optimisation
computationally tractable
and also makes the output from the optimisation
well suited for packet forwarding in the routers.
The output tells each router how traffic to a certain egress node in the
network should be divided between its set of outgoing links.
So, if a mapping between destination addresses and egress nodes
is added to the forwarding process
then the traffic can be distributed over multiple links
using a hashing mechanism similar to the one already in use today for
the equal cost multi-path extension to OSPF.
The optimisation includes an objective function which allows the
network operator to choose a maximum desired link utilisation level.
The optimisation then finds the most effective solution
satisfying this constraint. This enables the operator to control the
trade-off between minimising the network utilisation and balancing
load over multiple paths.
Ongoing and future work:
The optimisation needs as input a traffic matrix that describes the
current traffic situation and for the resulting routing to be useful
the traffic matrix must also be a good prediction of the near future.
Our current work include a continued study of traffic flow stability and
investigation of techniques for estimating the traffic matrix.
A longer term goal with the project is to design a routing protocol
based on optimisation.
|
