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";
15 Demystifying the routing
16 ########################
18 When describing a platform, routing is certainly the most complex
19 and error-prone part. This section explains the basics of SimGrid's
20 routing mechanism which allows you to easily compose and scale your
25 .. |flat_img| image:: img/zone_hierarchy.png
28 .. |tree_img| image:: img/zone_tree.svg
31 Circles represent processing units and squares represent network
32 routers. Bold lines represent communication links. The zone "AS2" models the core of a national network interconnecting a
33 small flat cluster (AS4) and a larger hierarchical cluster (AS5), a
34 subset of a LAN (AS6), and a set of peers scattered around the world
37 Networking zones (:ref:`pf_tag_zone`) are an advanced concept used to factorize the description
38 to reduce the size of your platform on disk and in memory.
39 Any zone may contain sub-zones, allowing for a hierarchical
40 decomposition of the platform (as you can see in the tree representation on the left).
41 Routing can be made more efficient (as the
42 inter-zone routing gets factored with :ref:`pf_tag_zoneroute`) and
43 allows you to have more than one routing model in your platform. For
44 example, you can have a coordinate-based routing for the WAN parts
45 of your platforms, a full routing within each datacenter, and a highly
46 optimized routing within each cluster of the datacenter. In this
47 case, determining the route between two given hosts gets
48 "somewhat more complex" but SimGrid still computes
49 these routes for you in a time- and space-efficient manner.
52 Routing basic elements: hosts and links
53 ***************************************
55 A platform is composed of a set of resources, namely hosts, links and disks.
56 On these resources you may run activities that will require some capacity and
57 will make the time advance.
59 Given a look at this example of some hosts and links being declared
63 <zone id="AS5-4" routing="Full">
64 <host id="host0" speed="1Gf"/>
65 <host id="host1" speed="2Gf"/>
66 <link id="link0" bandwidth="125MBps" latency="100us"/>
69 It describes a simple FullZone with 2 hosts inside connected through
70 a link. Note that the ``link0`` just represents a resource with a
71 certain bandwidth capacity and latency. It's only when you add
72 a route between ``host0`` and ``host1`` that this link will be used by
73 SimGrid in the communications.
77 <zone id="AS5-4" routing="Full">
79 <route src="host0" dst="host1"><link_ctn id="link0"/></route>
82 Note that no verification is performed concerning the links you use in a route.
83 This is quite flexible and enables interesting features. However, it also allows you
84 to do some strange topologies, such as having a single link used by a pair
85 of hosts from different zone:
89 <zone id="Nonsense" routing="Full">
90 <host id="host3" speed="1Gf"/>
91 <host id="host4" speed="2Gf"/>
92 <route src="host3" dst="host4"><link_ctn id="link0"/></route>
95 Probably you do not want to do this, but it's your responsibility to write
96 your platform file properly. SimGrid will not try to be smarter than you!
98 Describing routes: intra vs inter
99 *********************************
104 TLDR: use :ref:`pf_tag_route`
106 The routing mechanism inside a given zone is defined by ``routing=`` parameter
107 in the :ref:`pf_tag_zone` (see options in :ref:`intra-zone section <intra_zone>`). For example, in a *Full* zone, the user must declare
108 a :ref:`pf_tag_route` for each pair of hosts inside the zone. Other zones, such as *Floyd*
109 or *Dijkstra* will calculate the shortest path, while *DragonFly* and *Fat-Tree* uses
110 specialized routing algorithms to improve performance.
112 When adding a route inside a zone, keep in mind that you need 3 main parameters:
113 - src: Host (or router) source
114 - dst: Host (or router) destination
115 - links: list of resources (links in this case) used in the communication
120 TLDR: use :ref:`pf_tag_zoneroute`
122 When describing complex topologies, such as the one depicted in the beginning
123 of this page, you will need to connected not only hosts but zones too. The rationale
124 behind a route between zone is exactly the same as for hosts. The only difference is
125 the 2 new gateway parameters in the syntax of :ref:`pf_tag_zoneroute`.
127 A zone is not a physical resource, just a collection of resources (including other zones).
128 Consequently, you need to describe the gateway, i.e. the physical resource inside the zone used for the route.
129 It gives you 4 parameters to describe a zoneRoute:
131 - src: The object of source zone
132 - dst: The object of destination zone
133 - gw_src: Gateway inside src zone. A Host (or router) belonging to src zone.
134 - gw_dst: Gateway inside dst zone. A Host (or router) belonging to dst zone.
135 - links: Links that connect gw_src to gw_dst.
137 .. note:: The gateways must be a component of the zone (either directly or member of some child sub-zone). SimGrid will verify these parameters when adding a route.
139 .. warning:: SimGrid does not have the concept of default gateway/router. Each zoneRoute must describe the appropriate gateways which may be different for each route.
141 Calculating the routes
142 **********************
144 This section is not mandatory for a normal SimGrid user. However, if you want
145 to know a little more of we calculate the route
146 between nodes inside SimGrid, keep reading it.
151 Intra-zone communications
152 =========================
154 This is the easy, happy case. When
155 a host wants to communicate with another host belonging to the same
156 zone, it is the zone's duty to find the list of links that are
157 involved in the communication.
159 As we stated earlier, each zone implements a different strategy, defined
160 through the ``routing=`` parameter.
162 - **Full**: all routes must be explicitly given using the
163 :ref:`pf_tag_route` and :ref:`pf_tag_link_ctn` tags (this :ref:`routing
164 model <pf_rm>` is both simple and inefficient :). It is OK to not
165 specify each and every route between hosts, as long as you do not try
166 to start a communication on any of the missing routes during your
168 - **Dijkstra/Floyd**: calculates the shortest path between each pair
169 of nodes using the routes described by the user (:ref:`pf_tag_route`).
170 As long as you graph is connected, no problems.
172 - Dijkstra: shortest-path calculated considering the path's latency. As
173 the latency of links can change during simulation, it's recomputed each
174 time a route is necessary.
176 - Floyd: use the number of hops to build shortest path. It's calculated only
177 once at the beginning of the simulation (as the platform is fixed).
179 - **Cluster/Fat-Tree/DragonFly/Torus**: routing is defined by the topology, automatically created.
180 These zones must be defined through the :ref:`pf_tag_cluster` tag in the XML.
181 - **Star**: star-like topology. Users describe routes from/to every host in the zone.
182 - **Vivaldi/Wi-Fi**: "fully-connected" zones with special characteristics.
186 Inter-zone communications
187 =========================
189 .. image:: ./img/zoom_comm.svg
192 Inter-zone communications are a little more complicated since you need to pass
193 through several zones. Let's have a look in more details in a communication
194 within our initial topology.
196 In this case, *Host1* within *AS2* wants to communicate with *Host2* from *AS5-4*.
197 As we can see, they're not part of the same zone nor have direct links connecting
198 them. The routing procedure is as follows:
200 1. **Find common root and ancestors**: As a SimGrid's platform is a tree of zones,
201 it is assured that we have a common zone that includes both hosts. Also, we need
202 the zone within the root zone that contains the hosts. In our case, we have:
204 - **Common root**: *AS1*, it is the root zone that contains all hosts in our example
206 - **Src ancestor**: *AS2*, it is the own *Host1's* zone.
208 - **Dst ancestor**: *AS5*, it's the *AS5* that contains *AS5-4*.
210 2. **Adding route from src to dst ancestor**: Ask *AS1* for the route between *AS2* and *AS5*.
212 This route is defined by the following configuration
216 <zoneRoute> src="AS2" dst="AS5" gw_src="Host1" gw_dst"="gw1">
217 <link_ctn id="Link1">
220 Add *Link1* to our list of links.
222 Also, we can see in this route that the gateway for *AS2* is *Host1* and for *AS5* is *gw1*.
224 Consequently, we need to go from *Host1* to *AS2*'s gateway (*Host1*) and from *Host2* to *AS5*'s
227 3. **Recursively search for route between hosts (Host1/Host2) and ancestors (AS2, AS5)**
229 3.1. **Route from Host1 to AS2's gateway (Host1)**: nothing to do, same zone.
231 3.2. **Route from Host2 to AS5's gateway (gw1)**: start step 1 again, searching
232 for a common root (*AS5* in this case) and the common ancestors (*AS5-4* and *AS5-3*).
234 This route is defined as follows.
238 <zoneRoute> src="AS5-4" dst="AS5-3" gw_src="gw2" gw_dst"="gw1">
239 <link_ctn id="Link3">
242 Add *Link3* to list of links.
244 4. **Add local links in src and dst zones**
246 4.1. **Route from Host1 to AS2's gateway**: same node, no link to add.
248 4.2. **Route from Host2 to AS5-4's gateway**: follow intra-zone and add *Link2*.
250 The last route, as it is an internal route in *AS5-4*, is defined using the :ref:`pf_tag_route` tag.
254 <route> src="Host2" dst="gw2">
255 <link_ctn id="Link2">
259 In the end, our communication from *Host1/AS2* to *Host2/AS5-4* will pass through
260 the links: *Link1, Link3* and *Link2*.
262 Note that a communication between *Host3/AS2* and *Host2/AS5-4* follow the same procedure, except
263 for step 4.1 where we would add the link between *Host3* and *Host1* inside *AS2* zone.
269 The link used of loopback communications has a special treatment in SimGrid. As it can be
270 quite tedious to describe each a loopback link for each host in the platform, SimGrid provides
271 a global **FATPIPE** link which is used by all hosts by default.
273 By default, this link has the following characteristics:
275 - **Bandwidth**: 10GBps. It can be changed through configuration, see :ref:`cfg=network/loopback`.
277 - **Latency**: 0ms. See :ref:`cfg=network/loopback` for more details.
281 These default values are arbitrary chosen and must be carefully configured to reflect
282 your environment if needed.
284 In addition, you can add :ref:`pf_tag_route` from a node to itself to modify the loopback link
285 for a specific node. In this case, SimGrid will get this link (instead of the global one) for
286 the local communications.
290 <link id="loopback" bandwidth="100MBps" latency="0"/>
291 <route src="Tremblay" dst="Tremblay">
292 <link_ctn id="loopback"/>
295 Finally, some zones (e.g. :ref:`pf_tag_cluster`) allow you to describe the characteristics of
296 the loopback nodes inside the zone. These links are equivalent to adding specific routes and
297 have higher priority than the global loopback link.
301 **Loopback links are used only for local communications**.
303 You may have noticed that we didn't include them at step 3.1 in :ref:`inter_zone`.
304 Loopback links will be used only when src and dst are the same, not in the recursive search