Transcript Integration of a new algorithm

The traffic engineering toolbox
architecture of the TOTEM project
University of Liège (ULg), RUN
www.run.montefiore.ulg.ac.be
Simon Balon - Olivier Delcourt
Guy Leduc - Fabian Skivée
Joint work with University of Louvain (UCL):
Olivier Bonaventure - Cristel Pelsser
Bruno Quoitin - Steve Uhlig
TF4.2 - 15 April 2004 - © RUN, ULG
1
Overview





Introduction
Topology standardization
Current toolbox state
Integration of a new algorithm
Future work
TF4.2 - 15 April 2004 - © RUN, ULG
2
Toolbox objectives





Modularity: can plug an algorithm or test a combination
of different algorithms, useful for researchers who want to
promote new algorithms or for simulations on operational
networks
Interoperability: provides a standard interface to existing
tools
Flexibility: adapted to different configuration modes like
centralized/decentralized or on-line/off-line
Performance: the on-line algorithms require short
computation times
Multi-language: few constraints on languages used in
the toolbox
TF4.2 - 15 April 2004 - © RUN, ULG
3
Integration with existing tools
Toolbox (TF 4.2)
Measurement
system
Modularity, Interoperability
And Scalability
(TF 4.1)
Performance,
accuracy, platformspecific
Request
Actions
Provisioning tool
(TSOM, Tunnel Builder, …)
Graphical interface
Managed network
TF4.2 - 15 April 2004 - © RUN, ULG
4
Toolbox Architecture
TF4.2 - 15 April 2004 - © RUN, ULG
5
Overview





Introduction
Topology standardization
Current toolbox state
Integration of a new algorithm
Future work
TF4.2 - 15 April 2004 - © RUN, ULG
6
Standardization of the topology




The first step is to standardize the input
information of our TE methods
We define a standard format for representing
topology (nodes and links), MPLS, IGP and BGP
information
We use XML because it is widespread and a lot
of tools are available to work with XML
This format will be used as a common
denominator between tools and algorithms
TF4.2 - 15 April 2004 - © RUN, ULG
7
XML advantages
Algorithm
output
Router
information

BRITE
topology


XML

Graphical
representation
Topology
validation
Algorithm
input
TF4.2 - 15 April 2004 - © RUN, ULG

XML schema for
validation
Tool to convert “show ISIS” to XML
Tool for creating object
topology from the XML
schema
XML parser available in a
lot of languages
We will create a tool to
convert different formats
to XML and from XML to
other well-known formats
like ns or JavaSim.
8
Format description

Topology:
 Node: id, IP, location, interfaces
 Link: id, source, destination, type,
bandwidth, delay,
SRLG

MPLS:
 LSP:
id, path, bandwidth, DiffServ, preemption,
backup (bypass, detour)

IGP :
 Link:
metric, TE-metric, bandwidth, reservable
bandwidth per priority level

BGP :
 Router:
neighbour, in-filter, out-filter, localpref
TF4.2 - 15 April 2004 - © RUN, ULG
9
Example of XML topology
<domain name="RUN-topo1" ASID="1234">
<topology>
<nodes>
<node id="run1">
<rid>139.165.223.1</rid>
<interfaces>
<interface id="139.165.223.0/30"/>
</interfaces>
</node>
<node id="run2">
<rid>139.165.223.2</rid>
<interfaces>
<interface id="139.165.223.0/30"/>
</interfaces>
</node>
</nodes>
<links>
<link id="run1 -> run2">
<from node="run1" if="139.165.223.0/30"/>
<to node="run2" if="139.165.223.0/30"/>
</link>
</links>
</topology>
</domain>
TF4.2 - 15 April 2004 - © RUN, ULG
10
Overview





Introduction
Topology standardization
Current toolbox state
Integration of a new algorithm
Future work
TF4.2 - 15 April 2004 - © RUN, ULG
11
Current toolbox






Definition of the XML standard for representing a
topology and the associated XML-Schema
Converting IS-IS information to the XML
representation
Full parsing and integration of the XML topology
Integration of a CSPF module
Integration of our DAMOTE routing module for
MPLS LSPs (written in C)
First test: creation of a full mesh of LSPs on a
real topology with the two routing algorithms
TF4.2 - 15 April 2004 - © RUN, ULG
12
Toolbox technologies




We have chosen Java for the toolbox to achieve
interoperability and multi-language requirements
The Java environment provides a lot of tools to
deal with XML and easily integrate web-services
With the JNI interface, we can integrate C or C++
algorithms into the toolbox
We made some tests and the actual
implementation in Java provides nearly the same
performance as C++
TF4.2 - 15 April 2004 - © RUN, ULG
13
Topology package
TF4.2 - 15 April 2004 - © RUN, ULG
14
Overview





Introduction
Topology standardization
Current toolbox state
Integration of a new algorithm
Future work
TF4.2 - 15 April 2004 - © RUN, ULG
15
Integrating new algorithms
We would like to provide a framework for
adding new algorithms easily
 The toolbox provides different services:

 Topology
information (nodes, links, …)
 Statistical information (fairness, utilisation,
throughput, …)
 Scenario execution (add LSP, remove LSP)
TF4.2 - 15 April 2004 - © RUN, ULG
16
Integrating new algorithms

A new algorithm must implement the following
methods:
 start():
used to instantiate the algorithm. All information
needed by the algorithm (simplified topology, …) must
be sent with this method
 stop(): used to terminate the algorithm

Depending on the type of algorithm, additional
core methods must also be implemented.
For example, a routing algorithm must implement
the route() method.
TF4.2 - 15 April 2004 - © RUN, ULG
17
Repository package
TF4.2 - 15 April 2004 - © RUN, ULG
18
Collaboration between modules
JAVA
C / C++
TOTEM
TotemRouting
Native
CSPF
DB
JNI_interface
TotemCSPF
start();
route();
stop();
JNI_start();
JNI_addNode();
JNI_addLink();
JNI_route();
JNI_stop();
integration cost
TF4.2 - 15 April 2004 - © RUN, ULG
19
Toolbox performance
We have tested the toolbox on a real
topology of 23 nodes on which a full mesh
of 506 LSPs is computed.
 Here are some results:

 Topology
creation (XML to Java): 853 ms
 Scenario creation (XML to Java): 123 ms
 Mean time to compute a path :
CSPF : 480 µs
 DAMOTE : 6 ms

TF4.2 - 15 April 2004 - © RUN, ULG
20
DAMOTE Integration time
Total mean time
per LSP : 6 ms
Java overhead
DAMOTE
computation
algorithm
execution time
Mean time per
LSP in C: 5,9 ms
C
C overhead
The total overhead contains Java and C code and
takes 0,1 ms
TF4.2 - 15 April 2004 - © RUN, ULG
21
Overview





Introduction
Topology standardization
Current toolbox state
Integration of a new algorithm
Future work
TF4.2 - 15 April 2004 - © RUN, ULG
22
Future work






Integration of new algorithms
Development of the web-service interface
Create a consistency module that provides
warning about errors in configuration of a
network
Development of a simulation mode that can
generate topology, traffic and be used to
compare algorithms
Improve the architecture to support decentralized
on-line algorithms
Development of a configuration module
TF4.2 - 15 April 2004 - © RUN, ULG
23
References
URL : http://totem.info.ucl.ac.be
Email : [email protected]
TF4.2 - 15 April 2004 - © RUN, ULG
24