3 <object id="TOC" data="graphical-toc.svg" type="image/svg+xml"></object>
5 window.onload=function() { // Wait for the SVG to be loaded before changing it
6 var elem=document.querySelector("#TOC").contentDocument.getElementById("RoutingBox")
7 elem.style="opacity:0.93999999;fill:#ff0000;fill-opacity:0.1;stroke:#000000;stroke-width:0.35277778;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1";
18 SimGrid platforms are divided in networking zones (:ref:`pf_tag_zone`) to compose larger platforms from smaller parts.
19 This factorizes the description and improves the simulation performance, both in time and in size. Any zone may contain
20 sub-zones, allowing for a hierarchical decomposition of the platform as depicted in the example below. Inter-zone routes
21 are then factorized with :ref:`pf_tag_zoneRoute`.
23 In addition to the efficiency improvement, multi-zones routing also improve the modeling expressiveness, as each zone
24 can use different models. For example, you can have a coordinate-based routing for the WAN parts of your platform, a
25 full routing within each datacenter, and a highly optimized routing within each cluster of the datacenter. In all cases,
26 SimGrid strives to compute routes in a time- and space-efficient manner.
31 .. |flat_img| image:: img/zone_hierarchy.png
34 .. |tree_img| image:: img/zone_tree.svg
37 Both images above represent the same platform. On the left, circles represent hosts (i.e. processing units) and squares
38 represent network routers. Bold lines represent communication links. The zone "AS2" models the core of a national
39 network interconnecting a small flat cluster (AS4) and a larger hierarchical cluster (AS5), a subset of a LAN (AS6), and
40 a set of peers scattered around the world (AS7). On the right, the corresponding hierarchy of zones is highlighted.
45 Each zone implements a routing strategy according to the ``routing`` attribute of :ref:`pf_tag_zone`.
50 When ``routing=full``, all routes must be explicitly given using the :ref:`pf_tag_route` and :ref:`pf_tag_link_ctn` tags.
51 This routing model is both simple and inefficient :) It is OK to not specify each and every route between hosts, as
52 long as you do not try to start a communication on any of the missing routes during your simulation.
54 .. _platform_rm_shortest:
59 SimGrid can compute automatically the paths between all pair of hosts in a zone. You just need to provide the one-hop routes to connect all hosts.
60 Several algorithms are provided:
62 - ``routing=Floyd``: use the number of hops to build shortest path. It is calculated only once at the beginning of the
64 - ``routing=Dijkstra``: shortest-path calculated considering the path's latency. As the latency of links can change
65 during simulation, it is recomputed each time a route is necessary.
66 - ``routing=DijkstraCache``: Just like the regular Dijkstra, but with a cache of previously computed paths for performance.
68 Here is a small example describing a star-shaped zone depicted below. The path from e.g. *host0* to *host1* will be
69 computed automatically at startup. Another way to describe the same platform can be found :ref:`here
70 <platform_example_3hosts>`, with a full routing and without the central router.
75 <!DOCTYPE platform SYSTEM "https://simgrid.org/simgrid.dtd">
76 <platform version="4.1">
77 <zone id="my zone" routing="Floyd">
78 <host id="host0" speed="1Gf"/>
79 <host id="host1" speed="2Gf"/>
80 <host id="host2" speed="40Gf"/>
81 <link id="link0" bandwidth="125MBps" latency="100us"/>
82 <link id="link1" bandwidth="50MBps" latency="150us"/>
83 <link id="link2" bandwidth="250MBps" latency="50us"/>
85 <!-- Only 1-hop routes for topological information. Missing routes are computed with Floyd -->
86 <route src="center" dst="host0"><link_ctn id="link0"/></route>
87 <route src="center" dst="host1"><link_ctn id="link1"/></route>
88 <route src="center" dst="host2"><link_ctn id="link2"/></route>
92 .. image:: /tuto_smpi/3hosts.png
100 Clusters constitute a fundamental building bricks of any cyberinfrastructure. SimGrid provides several kinds of clusters:
101 crossbar clusters (contention-free internal network), backbone clusters (constrained internal network), fat-trees,
102 DragonFly, Torus and generic Star clusters. Each of them are created through the :ref:`pf_tag_cluster` tag, and have a
103 highly optimized implementation in SimGrid source code.
105 The documentation of each cluster kinds is given as :ref:`platform_examples`.
112 This routing model is particularly well adapted to Peer-to-Peer and Clouds platforms: each component is connected to the
113 cloud through a private link of which the upload and download rate may be asymmetric.
115 The network core (between the private links) is assumed to be over-sized so only the latency is taken into account.
116 Instead of a matrix of latencies that would become too large when the amount of peers grows, Vivaldi netzones give a
117 coordinate to each peer and compute the latency between host A=(xA,yA,zA) and host B=(xB,yB,zB) as follows:
119 latency = sqrt( (xA-xB)² + (yA-yB)² ) + zA + zB
121 The resulting value is assumed to be in milliseconds.
123 .. image:: img/vivaldi.svg
127 So, to go from a host A to a host B, the following links would be used: ``private(A)_UP``, ``private(B)_DOWN``, with the
128 additional latency computed above. The bandwidth of the UP and DOWN links is not symmetric (in contrary to usual SimGrid
129 links), but naturally correspond to the values provided when the peer was created. See also :ref:`pf_tag_peer`.
131 The script ``examples/platforms/syscoord/generate_peer_platform.pl`` in the archive can be used to convert the
132 coordinate-based platforms from the OptorSim project into SimGrid platform files.
134 Such Network Coordinate systems were shown to provide rather good latency estimations in a compact way. Other systems,
135 such as `Phoenix network coordinates <https://en.wikipedia.org/wiki/Phoenix_network_coordinates>`_ were shown
136 superior to the Vivaldi system and could be also implemented in SimGrid.
138 Here is a small platform example:
142 <?xml version='1.0'?>
143 <!DOCTYPE platform SYSTEM "https://simgrid.org/simgrid.dtd">
144 <platform version="4">
146 <zone id="zone0" routing="Vivaldi">
147 <peer id="peer-0" coordinates="173.0 96.8 0.1" speed="730Mf" bw_in="13.38MBps" bw_out="1.024MBps" lat="500us"/>
148 <peer id="peer-1" coordinates="247.0 57.3 0.6" speed="730Mf" bw_in="13.38MBps" bw_out="1.024MBps" lat="500us" />
149 <peer id="peer-2" coordinates="243.4 58.8 1.4" speed="730Mf" bw_in="13.38MBps" bw_out="1.024MBps" lat="500us" />
156 Please see :ref:`models_wifi`.
161 When using :ref:`models_ns3`, SimGrid configures the ns-3 simulator according to the configured platform.
162 Since ns-3 uses a shortest path algorithm on its side, all routes must be of length 1.
169 If you want to define a route within a given zone, you simply have to use the :ref:`pf_tag_route` tag, providing the
170 ``src``, ``dst`` parameters along with the list of links to use from ``src`` to ``dst``.
172 Defining a route between two separate zones with :ref:`pf_tag_zoneroute` takes more parameters: ``src``, ``dst``,
173 ``gw_src`` (source gateway) and ``gw_dst`` (destination gateway) along with the list of links. Afterward, the path from
174 ``src_host`` in zone ``src`` to ``dst_host`` in zone ``dst`` is composed of 3 segments. First, move within zone ``src`` from
175 ``src_host`` to the specified gateway ``gw_src``. Then, traverse all links specified by the zoneRoute (purportedly within
176 the common ancestor) and finally, move within zone ``dst`` from ``gw_dst`` to ``dst_host``.
178 SimGrid enforces that each gateway is within its zone, either directly or in a sub-zone to ensure that the algorithm
179 described in the next section actually works.
181 One can also use :ref:`pf_tag_bypassRoute` and :ref:`pf_tag_bypassZoneRoute` to define exceptions to the classical routing
182 algorithm. This advanced feature is also detailed in the next section.
186 Calculating network paths
187 *************************
189 Computing the path between two hosts is easy when they are located in the same zone. It is done directly by the routing
190 algorithm of that zone. Full routing looks in its table, Vivaldi computes the distance between peers, etc.
192 Another simple case is when a :ref:`pf_tag_bypassRoute` was provided. Such routes are used in priority, with no further
193 routing computation. You can define a bypass between any hosts, even if they are not in the same zone.
195 When communicating through several zones, a recursive algorithm is used. As an illustration, we will apply this
196 algorithm to a communication between `host1` in `AS1` and `host2` in `AS5-4`, in our previous topology. This section
197 only gives an overview of the algorithm used. You should refer to the source code for the full details, in
198 ``NetZoneImpl::get_global_route()``.
200 .. image:: ./img/zoom_comm.svg
203 1. **Find common ancestor** zone of ``src`` and ``dst``, the ancestors of ``src`` and ``dst`` and how they are connected.
205 In our case, *AS1* is the common ancestor while *AS2* and *AS5* are the respective ancestors of ``src`` and ``dst``.
206 Assume that the relevant route was defined as follows:
210 <zoneRoute src="AS2" dst="AS5" gw_src="Host1" gw_dst="gw1">
211 <link_ctn id="Link1"/>
214 2. **Add the route up to the ancestor**, i.e. from ``src`` to the ``gw_src`` in the route between ancestor zones. This is a recursive call to the current algorithm.
216 That's easy in our case, as both ``src`` and ``gw_src`` are *Host1*, so that route segment is empty. If we were to compute the path from *Host3* to *Host2*, we would have to add the route from *Host3* to the gateway that is *Host1*
218 3. **Add the zoneRoute between ancestors**.
220 From the XML fragment above defining the zoneRoute between *AS2* and *AS5*, we need to add ``Link1`` to the path.
222 4. **Add the route down from the ancestor**, i.e. from ``gw_dst`` to ``dst`` in the route between ancestor zones. This is another recursive call to the current algorithm.
224 Here, we need the route from *gw1* and *host2*. The common ancestor is *AS5*, and the relative ancestors are *AS5-4* and *AS5-3*. This route is defined as follows (routes are symmetrical by default).
228 <zoneRoute src="AS5-4" dst="AS5-3" gw_src="gw2" gw_dst="gw1">
229 <link_ctn id="Link3"/>
232 So to compute the route from *gw1* to *Host2*, we need to add:
234 - the route from the source to the gateway, i.e. from *gw1* to *gw1* (empty route segment),
235 - the links listed in the zoneRoute (*Link3*)
236 - the route from the gateway to the destination, i.e. from *gw2* to *Host2* (they are in the same zone *AS5-4*, and that path is limited to *Link2*). The last segment is because of the following fragment:
240 <route> src="Host2" dst="gw2">
241 <link_ctn id="Link2">
244 In the end, our communication from *Host1@AS2* to *Host2@AS5-4* follows this path: ``{Link1, Link3, Link2}``
246 It is possbile to use :ref:`pf_tag_bypassZoneRoute` to provide a path between two zones that are not necessarily sibilings.
247 If such routes exist, SimGrid will try to match each of the ancestor zones of the source with each of the ancestor zone of
248 the destination, looking for such a bypass to use intead of the common ancestor.
255 Loopback links are used when from an host to itself (they are excluded in the recursive search described above). As it
256 can be quite tedious to describe each a loopback link for each host in the platform, SimGrid provides a default global
257 **FATPIPE** link which is used by all hosts. Its bandwidth is 10GBps while its latency is 0ms, but these arbitrary
258 values should changed through configuration to reflect your environment (see :ref:`cfg=network/loopback`).
260 To give a specific loopback link to a given host, simply a add :ref:`pf_tag_route` from this node to itself. SimGrid
261 will then use the provided link(s) as a loopback for this host instead of the global one.
265 <link id="loopback" bandwidth="100MBps" latency="0"/>
266 <route src="Tremblay" dst="Tremblay">
267 <link_ctn id="loopback"/>
270 Some zones such as :ref:`pf_tag_cluster` provide ways to describe the characteristics of
271 the loopback nodes inside the zone.