Subsections


A standard XML format for a network topology representation

In this section, we will explain the XML format we defined to represent network topology information. We have chosen the XML language because it is widely used and many tools exist for dealing with this language. We have created an XML Schema[1] 5. The schema allows us to validate a domain file so that we are sure that an XML instance satisfies the data structure we have defined.

Description of the XML network representation format

The root element of the XML file is the domain element. It contains five sub-elements: info, topology, mpls, igp and bgp. The topology and the info elements are mandatory. In this document, by default, all the elements and attributes are optional except when the contrary is specified. We decided to separate the information into sections for a clarity and ease of use reason. So, for example, if an algorithm only needs topology and igp information, it may just not care about the mpls and the bgp section... The domain element has two attributes : a name (string) and an ASID (integer). The ASID attribute is mandatory.

The info element contains all the extra information about the topology, including the units in use. The topology element contains all the information about the topology seen at the network layer (IP level). So it is a set of nodes and links. The mpls element is composed of a list of lsp elements. The igp element contains all the information of the intra-domain routing protocol. And finally, the bgp element contains all the information of the inter-domain routing protocol.


Table 1: Example of the XML DOMAIN element usage.
<domain name="domain_test" ASID="1234">
    <info>
        ...
    </info>
    <topology>
        ...
    </topology>
    <mpls>
        ...
    </mpls>
    <igp>
        ...
    </igp>
    <bgp>
        ...
    </bgp>
</domain>



The info element

The info element contains all the extra information about the topology. It contains the following sub-elements : title (string), date (date), author (string) and description (a string). It contains also a units element which is used to specify the units of the values found in the document. The units element is a list of unit sub- elements. One unit element only has two mandatory attributes : type (which can be either delay or bandwidth) and value (which can be ns, $ \mu$ s, ms, s for the delay values and bps, kbps, mbps, gbps or tbps for the bandwidth values). The units element is mandatory and must contain two unit sub-elements, one for bandwidth and the other for delay. The info element also contains a diff-serv element that contains the Diffserv information, which is the correspondance between the pairs (Classes Types, Preemption level) and the priority levels. Formally, the diff-serv element is a list of priority elements (minimum 1 and maximum 8 priority elements) which are composed of three mandatory attributes : an id (the identifier of the priority, i.e. an integer in the interval [0,7]), a ct (the identifier of the corresponding class type, i.e. an integer in the interval [0,7]) and a preemption (the corresponding preemption level, i.e. an integer in the interval [0,7]). The info element can also include a class-of-services element which is a list of cos subelements. A class of service is identified by a name which is a string. It can also have subclasses to represent the drop preference. The last sub-element of the info element is the srlgs element which is a list of srlg elements (at least one). A srlg element is a string (the information about the physical origin of the Shared Risk Link Group) and has one mandatory id attribute which is an integer).


Table 2: Example of the XML INFO element usage.
<info>
    <title>This is the title of the topology</title>
    <date>2005-02-16</date>
    <author>University of Li´┐Że</author>
    <description>
        The description of this domain
    </description>
    <units>
        <unit type="delay" value="ms"/>
        <unit type="bandwidth" value="kbps"/>
    </units>
    <diff-serv>
        <priority id="0" ct="0" preemption="0"/>
        <priority id="1" ct="0" preemption="1"/>
        <priority id="2" ct="1" preemption="0"/>
        <priority id="3" ct="1" preemption="1"/>
    </diff-serv>
    <classes-of-service>
        <cos name="EF"/>
        <cos name="AF1">
            <sub-class>AF11</sub-class>
            <sub-class>AF12</sub-class>
        </cos>
        <cos name="BE"/>
    </classes-of-service>
    <srlgs>
        <srlg id="241">information about this SRLG</srlg>
    </srlgs>
</info>



The topology element

The topology element contains all the information about the topology seen at the network layer (IP level). So it is a set of nodes and links.

The topology element is composed of two sub-elements : nodes (which is mandatory) and links.

One nodes element is a list of node elements (at least one). Each node element contains one mandatory attribute : id which is an unique identifier (string). The node element contains the following sub-elements : status which can be UP or DOWN (UP by default), rid (IP address), description (string), type which can be CORE, EDGE, NEIGH or VIRTUAL, location (which contains two mandatory float attributes : latitude and longitude) and finally an interfaces element which is a list of interface elements (at least one). An interface element has one mandatory id attribute (string which is (locally) unique). An interface element contains the following sub-elements : status which can be UP or DOWN (UP by default), ip which is an IP address and has a mandatory mask attribute (IP mask of the form X.X.X.X/Y, Y is in [0, 32])

One links element is a list of link elements (at least one). Each link element contains one mandatory attribute : id which is a unique identifier (string). A link joins two nodes and more precisely, two interfaces on two nodes. So a link must have from and to sub-elements which point respectively to the source interface and to the destination interface. A from element has two attributes : node (string, the identifier of the source node) which is mandatory and if (string, the identifier of the interface on the source node). A to element has three attributes : as (integer, the AS number of the destination node, which is used for inter-domain links), node (string, the identifier of the destination node) which is mandatory and if (string, the identifier of the interface on the destination node). A link element can also contain the following sub-elements : status which can be UP or DOWN (UP by default), description (string), type which can be INTRA, ACCESS, PEERING, INTER or VIRTUAL, bw which is the bandwidth of the link (float), technology (string), delay which is the delay of the link (float) and srlgs which is a list of srlg elements. An srlg element is an integer (the identifier of the SRLG the link belong to).


Table 3: Example of the XML TOPOLOGY element usage.
<topology>
    <nodes>
        <node id="router1.foo.net">
            <rid>10.0.0.1</rid>
            <interfaces>
                <interface id="10.0.2.0/30">
                    <ip mask="10.0.2.0/30">10.0.2.1</ip>
                </interface>
            </interfaces>
        </node>
        ...
    </nodes>
    <links>
        <link id="1 -> 2">
            <from if="10.0.2.0/30" node="10.0.0.1"/>
            <to if="10.0.2.0/30" node="10.0.0.2"/>
        </link>
        ...
    </links>
</topology>


The mpls element

The mpls element is composed of a list of lsp elements (at least one). An lsp element is composed of the following sub-elements : path (which is mandatory), bw which is the bandwidth demand of the LSP (float), metric which is the metric of the LSP (a float), max_rate which is the maximal bandwidth rate of the LSP (a float), diff-serv, accepted_cos and backup. An lsp element also has a mandatory attribute id which is the identifier of the LSP (a string).

A path element is a list of at least one link sub-element which is the identifier of a link (string).

A diff-serv element contains the following mandatory sub-elements : ct (the identifier of the corresponding class type, i.e. an integer in the interval [0,7]) and preemption which has two mandatory attributes : setup and holding which are the setup and holding preemption levels, i.e. an integer in the interval [0,7].

A accepted_cos element is a list of cos sub-elements that represents the classes of service that can be routed on the LSP. If the element is not present, the LSP is considered to accept all classes of service.

The backup element must be present if the LSP is a backup LSP. This element has one mandatory attribute type, a string that can be DETOUR_LOCAL (for a local detour LSP), DETOUR_E2E (for an end-to-end detour LSP) or BYPASS (for a local bypass LSP). The backup element has the following sub-elements : protected_lsp (string) which contains the identifier of the protected lsp (in case of detour LSP) and protected_links which is mandatory and is composed of a list of protected_link elements (at least one). A protected_link element is a string which is the identifier of the link that is protected by the LSP. In case of local protection, the list should contain the protected link and in case of end-to-end protection, the list should contain all the links of the primary path.


Table 4: Example of the XML MPLS element usage.
<mpls>
    <lsp id="LSP1">
        <path>
            <link>1 -> 2</link>
            <link>2 -> 3</link>
        </path>
        <bw>155000</bw>
        <diff-serv>
            <ct>0</ct>
            <preemption holding="0" setup="0"/>
        </diff-serv>
        <accepted_cos>
            <cos>BE</cos>
            <cos>AF1</cos>
        </accepted_cos>
    </lsp>
    ...
</mpls>



The igp element

The igp element contains all the information of the intra-domain routing protocol. The type attribute specify the running routing protocol (string that can be ISIS or OSPF). The igp element contains a list of link elements (at least one). One link element contains all the link state information that is transmitted by the intra-domain routing protocol. The id attribute (mandatory) of the link element is a string that contains the identifier of the link to which the information is related. One link element contains two sub-elements : static and dynamic.

The static element contains the following sub-elements : metric (the IGP metric of the link, a float), te-metric (the Traffic-Engineering metric, also a float), mrbw (maximum reservable bandwidth, a float), mbw (maximum bandwidth, a float), admingroup (integer) and finally diff-serv. One diff-serv element contains the following sub-elements : bcm which is mandatory and contains the bandwidth constraint model, a string that can be either MAM (Maximum Allocation Model) or RDM (Russian Doll Model), and a list of bc elements (at least one). One bc element contains a float (which is the value of the bandwidth constraint) and a mandatory attribute id (integer) which identifies to what the bandwidth constraint is related (in MAM, it is related to one Class Type).

The dynamic element contains one mandatory sub-element : rbw (for Reservable BandWidth). The rbw element is a list of between 1 and 8 (inclusive) priority elements. One priority element has one mandatory attribute id (which is an integer in the interval [0,7] and should correspond to a priority defined under the diff-serv element of the info element) and contains a float which is the reservable bandwidth associated with this priority.

The reservable bandwidth is dynamic in the sense that it can vary with the time (when a new LSP is established on the link, for example).


Table 5: Example of the XML IGP element usage.
<igp type="IS-IS">
    <links>
        <link id="1 -> 2">
            <static>
                <metric>20050.0</metric>
                <te-metric>50.0</te-metric>
                <mrbw>2488320.0</mrbw>
                <mbw>2488320.0</mbw>
            </static>
            <dynamic>
                <rbw>
                    <priority id="0">2488320.0</priority>
                    <priority id="1">2488320.0</priority>
                    <priority id="2">2488320.0</priority>
                    <priority id="3">2488320.0</priority>
                </rbw>
            </dynamic>
        </link>
        ...
    </links>
</igp>



The bgp element

The bgp element contains the information related to the inter-domain routing protocol, BGP. The bgp element is thus the place where nodes existing in the topology element will be defined as BGP routers. This is also the place one defines the BGP sessions between the BGP routers as well as the IP prefixes to be advertised outside the domain. An example of the XML BGP element usage is shown in Table 6.


Table 6: Example of the XML BGP element usage.
<bgp>
    <routers>
        <router id="router1.foo.net">
            <rid>10.0.0.1</rid>
            <networks>
                <network prefix="10.0.1/24"/>
            </networks>
            <neighbors>
                <neighbor ip="10.0.0.2" as="666"/>
                <neighbor ip="10.0.0.3" as="666"/>
            </neighbors>
        </router>
        ...
    </routers>
</bgp>


Basically, the bgp element is a sequence of BGP router definitions. Each BGP router is encoded in a router element which is composed of many attributes. The router is identified by a mandatory id attribute whose value is a free-form string of characters. There is currently a single uniqueness constraint on the id attribute. That is there cannot exist two routers that share the same value of the id attribute.

In addition to this, the router element also has a mandatory rid attribute which represents the router-ID. This rid attribute is an IP address that identifies the BGP router in the BGP protocol. Usually, the router-ID is taken as the highest IP address of the router or as the loopback of the router. In the toolbox, we will assume that the value of the rid attribute corresponds to the rid of the corresponding node element in the topology section.

Then, comes the definition of the networks that this router will advertise through the BGP protocol. The networks are defined in a networks element which is a sequence of network elements. Each network element contains a single CIDR prefix. This CIDR prefix has the form of a dotted IP address followed by a slash (``/'') followed by a mask length. The networks element is optional and can be omitted if no network is originated by this router. However, if a networks element is present, it cannot be empty. That is, it must contain at least a network element.

Finally, the router also contains a list of neighbors, i.e. a list of other BGP neighbors with which it has BGP sessions. The list of neighbors is defined with a neighbors element which is a sequence of neighbor elements. Each neighbor represents a single BGP neighbor and has several attributes. Two attributes are used to identify the neighbor: an IP address and an AS number. The IP address is specified using the ip element. It represents the router-ID of the neighbor router. The AS number is specified using the as element. It represents the AS number of the neighbor router. This AS number can be the same as the local router if both routers share an internal (iBGP) session or they are different if both routers share an external (eBGP) session.

The neighbor element also makes possible the definition of BGP filters. This part is however still in development and the form that will be given to these filters is not yet precisely defined.

Example

In table 7, we present an example of the very simple network of figure 1.

Figure 1: An example simple topology
\includegraphics[width=0.40 \textwidth]{img/simple_topo.eps}


Table 7: Example of an XML domain file.
<?xml version="1.0" encoding="UTF-8"?>
<domain ASID="1234">
    <info>
        <title>Test Topology</title>
        <date>2005-01-31</date>
        <author>RUN - University of Liege</author>
        <description>
            TOTEM Project (http://totem.info.ucl.ac.be/)
        </description>
        <units>
            <unit type="bandwidth" value="kbps"/>
            <unit type="delay" value="ms"/>
        </units>
    </info>
    <topology>
        <nodes>
            <node id="0">
                <location latitude="5" longitude="7"/>
                <interfaces>
                    <interface id="0">
                    </interface>
                </interfaces>
            </node>
            <node id="1">
                <location latitude="44" longitude="1"/>
                <interfaces>
                    <interface id="0">
                    </interface>
                </interfaces>
            </node>
        </nodes>
        <links>
            <link id="0_0->1_0">
                <from node="0" if="0"/>
                <to node="1" if="0"/>
                <bw>200000</bw>
                <delay>1.4</delay>
            </link>
        </links>
    </topology>
</domain>


Simon Balon 2008-06-18