X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/bd8b1f6f7a1fb9e79540cb9eb850c0dc6b99fe3e..adbdcbddadcbd685b72259874d1ebfd9cbbcc497:/docs/source/Platform_routing.rst?ds=sidebyside diff --git a/docs/source/Platform_routing.rst b/docs/source/Platform_routing.rst index 8aa53541c1..fe5a7c424d 100644 --- a/docs/source/Platform_routing.rst +++ b/docs/source/Platform_routing.rst @@ -12,41 +12,265 @@ .. _platform_routing: -Defining a Routing -################## - -Networking zones (:ref:`pf_tag_zone`) are an advanced concept used to factorize the description -to reduce the size of your platform on disk and in memory. Then, when -a host wants to communicate with another host belonging to the same -zone, it is the zone's duty to find the list of links that are -involved in the communication. In the above examples, since we use -``routing="Full"``, all routes must be explicitly given using the -:ref:`pf_tag_route` and :ref:`pf_tag_link_ctn` tags (this :ref:`routing -model ` is both simple and inefficient :) It is OK to not -specify each and every route between hosts, as long as you do not try -to start a communication on any of the missing routes during your -simulation. - -Any zone may contain sub-zones, allowing for a hierarchical -decomposition of the platform. Routing can be made more efficient (as the -inter-zone routing gets factored with :ref:`pf_tag_zoneroute`), and -allows you to have more than one routing model in your platform. For -example, you can have a coordinate-based routing for the WAN parts -of your platforms, a full routing within each datacenter, and a highly -optimized routing within each cluster of the datacenter. In this -case, determining the route between two given hosts gets :ref:`routing_basics` -"somewhat more complex" but SimGrid still computes -these routes for you in a time- and space-efficient manner. -Here is an illustration of these concepts: - -.. image:: img/zone_hierarchy.png - -Circles represent processing units and squares represent network -routers. Bold lines represent communication links. The zone "AS2" models the core of a national network interconnecting a -small flat cluster (AS4) and a larger hierarchical cluster (AS5), a -subset of a LAN (AS6), and a set of peers scattered around the world -(AS7). - -.. todo:: Add more examples, such as the cloud example described in - previous paragraph +Advanced routing +################ +SimGrid platforms are divided in networking zones (:ref:`pf_tag_zone`) to compose larger platforms from smaller parts. +This factorizes the description and improves the simulation performance, both in time and in size. Any zone may contain +sub-zones, allowing for a hierarchical decomposition of the platform as depicted in the example below. Inter-zone routes +are then factorized with :ref:`pf_tag_zoneRoute`. + +In addition to the efficiency improvement, multi-zones routing also improve the modeling expressiveness, as each zone +can use different models. For example, you can have a coordinate-based routing for the WAN parts of your platform, a +full routing within each datacenter, and a highly optimized routing within each cluster of the datacenter. In all cases, +SimGrid strives to compute routes in a time- and space-efficient manner. + + +|flat_img| |tree_img| + +.. |flat_img| image:: img/zone_hierarchy.png + :width: 45% + +.. |tree_img| image:: img/zone_tree.svg + :width: 45% + +Both images above represent the same platform. On the left, circles represent hosts (i.e. processing units) and squares +represent network routers. Bold lines represent communication links. The zone "AS2" models the core of a national +network interconnecting a small flat cluster (AS4) and a larger hierarchical cluster (AS5), a subset of a LAN (AS6), and +a set of peers scattered around the world (AS7). On the right, the corresponding hierarchy of zones is highlighted. + +Routing models +************** + +Each zone implements a routing strategy according to the ``routing`` attribute of :ref:`pf_tag_zone`. + +Explicit routing +================ + +When ``routing=full``, all routes must be explicitly given using the :ref:`pf_tag_route` and :ref:`pf_tag_link_ctn` tags. +This routing model is both simple and inefficient :) It is OK to not specify each and every route between hosts, as +long as you do not try to start a communication on any of the missing routes during your simulation. + +.. _platform_rm_shortest: + +Shortest path +============= + +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. +Several algorithms are provided: + + - ``routing=Floyd``: use the number of hops to build shortest path. It is calculated only once at the beginning of the + simulation. + - ``routing=Dijkstra``: shortest-path calculated considering the path's latency. As the latency of links can change + during simulation, it is recomputed each time a route is necessary. + - ``routing=DijkstraCache``: Just like the regular Dijkstra, but with a cache of previously computed paths for performance. + +Here is a small example describing a star-shaped zone depicted below. The path from e.g. *host0* to *host1* will be +computed automatically at startup. Another way to describe the same platform can be found :ref:`here +`, with a full routing and without the central router. + +.. code-block:: XML + + + + + + + + + + + + + + + + + + + +.. image:: /tuto_smpi/3hosts.png + :align: center + +.. _pf_rm_cluster: + +Clusters +======== + +Clusters constitute a fundamental building bricks of any cyberinfrastructure. SimGrid provides several kinds of clusters: +crossbar clusters (contention-free internal network), backbone clusters (constrained internal network), fat-trees, +DragonFly, Torus and generic Star clusters. Each of them are created through the :ref:`pf_tag_cluster` tag, and have a +highly optimized implementation in SimGrid source code. + +The documentation of each cluster kinds is given as :ref:`platform_examples`. + +.. _pf_rm_vivaldi: + +Vivaldi +======= + +This routing model is particularly well adapted to Peer-to-Peer and Clouds platforms: each component is connected to the +cloud through a private link whose upload and download rates may be asymmetric. + +The network core (between the private links) is assumed to be over-provisioned so that only the latency has to be +taken into account. Instead of a matrix of latencies that would become too large when the amount of peers grows, +Vivaldi netzones give a coordinate to each peer and compute the latency between host A=(xA,yA,zA) and host B=(xB,yB,zB) +as follows: + + latency = sqrt( (xA-xB)² + (yA-yB)² ) + zA + zB + +The resulting value is assumed to be in milliseconds. + +.. image:: img/vivaldi.svg + :scale: 60% + :align: center + +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 +additional latency computed above. The bandwidth of the UP and DOWN links is not symmetric (in contrary to usual SimGrid +links), but naturally correspond to the values provided when the peer was created. See also :ref:`pf_tag_peer`. + +The script ``examples/platforms/syscoord/generate_peer_platform.pl`` in the archive can be used to convert the +coordinate-based platforms from the OptorSim project into SimGrid platform files. + +Such Network Coordinate systems were shown to provide rather good latency estimations in a compact way. Other systems, +such as `Phoenix network coordinates `_ were shown +superior to the Vivaldi system and could be also implemented in SimGrid. + +Here is a small platform example: + +.. code-block:: XML + + + + + + + + + + + + +Wi-Fi +===== + +Please see :ref:`models_wifi`. + +ns-3 +==== + +When using :ref:`models_ns3`, SimGrid configures the ns-3 simulator according to the configured platform. +Since ns-3 uses a shortest path algorithm on its side, all routes must be of length 1. + +.. _pf_routes: + +Describing routes +***************** + +If you want to define a route within a given zone, you simply have to use the :ref:`pf_tag_route` tag, providing the +``src``, ``dst`` parameters along with the list of links to use from ``src`` to ``dst``. + +Defining a route between two separate zones with :ref:`pf_tag_zoneroute` takes more parameters: ``src``, ``dst``, +``gw_src`` (source gateway) and ``gw_dst`` (destination gateway) along with the list of links. Afterward, the path from +``src_host`` in zone ``src`` to ``dst_host`` in zone ``dst`` is composed of 3 segments. First, move within zone ``src`` from +``src_host`` to the specified gateway ``gw_src``. Then, traverse all links specified by the zoneRoute (purportedly within +the common ancestor) and finally, move within zone ``dst`` from ``gw_dst`` to ``dst_host``. + +SimGrid enforces that each gateway is within its zone, either directly or in a sub-zone to ensure that the algorithm +described in the next section actually works. + +One can also use :ref:`pf_tag_bypassRoute` and :ref:`pf_tag_bypassZoneRoute` to define exceptions to the classical routing +algorithm. This advanced feature is also detailed in the next section. + +.. _pf_route_usage: + +Calculating network paths +************************* + +Computing the path between two hosts is easy when they are located in the same zone. It is done directly by the routing +algorithm of that zone. Full routing looks in its table, Vivaldi computes the distance between peers, etc. + +Another simple case is when a :ref:`pf_tag_bypassRoute` was provided. Such routes are used in priority, with no further +routing computation. You can define a bypass between any hosts, even if they are not in the same zone. + +When communicating through several zones, a recursive algorithm is used. As an illustration, we will apply this +algorithm to a communication between `host1` in `AS1` and `host2` in `AS5-4`, in our previous topology. This section +only gives an overview of the algorithm used. You should refer to the source code for the full details, in +``NetZoneImpl::get_global_route()``. + +.. image:: ./img/zoom_comm.svg + :scale: 70% + +1. **Find common ancestor** zone of ``src`` and ``dst``, the ancestors of ``src`` and ``dst`` and how they are connected. + + In our case, *AS1* is the common ancestor while *AS2* and *AS5* are the respective ancestors of ``src`` and ``dst``. + Assume that the relevant route was defined as follows: + + .. code-block:: XML + + + + + +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. + + 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* + +3. **Add the zoneRoute between ancestors**. + + From the XML fragment above defining the zoneRoute between *AS2* and *AS5*, we need to add ``Link1`` to the path. + +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. + + 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). + + .. code-block:: XML + + + + + + So to compute the route from *gw1* to *Host2*, we need to add: + + - the route from the source to the gateway, i.e. from *gw1* to *gw1* (empty route segment), + - the links listed in the zoneRoute (*Link3*) + - 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: + + .. code-block:: XML + + src="Host2" dst="gw2"> + + + +In the end, our communication from *Host1@AS2* to *Host2@AS5-4* follows this path: ``{Link1, Link3, Link2}`` + +It is possbile to use :ref:`pf_tag_bypassZoneRoute` to provide a path between two zones that are not necessarily sibilings. +If such routes exist, SimGrid will try to match each of the ancestor zones of the source with each of the ancestor zone of +the destination, looking for such a bypass to use intead of the common ancestor. + +.. _pf_loopback: + +Loopback links +************** + +Loopback links are used when from an host to itself (they are excluded in the recursive search described above). As it +can be quite tedious to describe each a loopback link for each host in the platform, SimGrid provides a default global +**FATPIPE** link which is used by all hosts. Its bandwidth is 10GBps while its latency is 0ms, but these arbitrary +values should changed through configuration to reflect your environment (see :ref:`cfg=network/loopback`). + +To give a specific loopback link to a given host, simply a add :ref:`pf_tag_route` from this node to itself. SimGrid +will then use the provided link(s) as a loopback for this host instead of the global one. + +.. code-block:: XML + + + + + + +Some zones such as :ref:`pf_tag_cluster` provide ways to describe the characteristics of +the loopback nodes inside the zone. + +.. |br| raw:: html + +