X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/d8d70cda91e405d93449fda28d339a98bf8358cb..f973433226af2e2e3059b62578bb0f3b215380fb:/docs/source/Platform_routing.rst diff --git a/docs/source/Platform_routing.rst b/docs/source/Platform_routing.rst index 93156f29f6..fe5a7c424d 100644 --- a/docs/source/Platform_routing.rst +++ b/docs/source/Platform_routing.rst @@ -57,11 +57,11 @@ 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. -Two algorithms are provided: +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=Dijksta``: shortest-path calculated considering the path's latency. As the latency of links can change + - ``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. @@ -92,24 +92,30 @@ computed automatically at startup. Another way to describe the same platform can .. image:: /tuto_smpi/3hosts.png :align: center +.. _pf_rm_cluster: + Clusters ======== -TODO +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`. - - **Cluster/Fat-Tree/DragonFly/Torus**: routing is defined by the topology, automatically created. - These zones must be defined through the :ref:`pf_tag_cluster` tag in the XML. - - **Star**: star-like topology. Users describe routes from/to every host in the zone. +.. _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 of which the upload and download rate may be asymmetric. +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-sized so only the latency is 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: +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 @@ -129,7 +135,7 @@ 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 @@ -148,7 +154,13 @@ Here is a small platform example: Wi-Fi ===== -TODO +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: @@ -162,12 +174,15 @@ Defining a route between two separate zones with :ref:`pf_tag_zoneroute` takes m ``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``. +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. -TODO: bypassRoute +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 ************************* @@ -175,6 +190,9 @@ 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 @@ -190,9 +208,9 @@ only gives an overview of the algorithm used. You should refer to the source cod .. 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. @@ -208,9 +226,9 @@ only gives an overview of the algorithm used. You should refer to the source cod .. code-block:: XML - - - + + + So to compute the route from *gw1* to *Host2*, we need to add: @@ -224,8 +242,13 @@ only gives an overview of the algorithm used. You should refer to the source cod -In the end, our communication from *Host1@AS2* to *Host2@AS5-4* follows this path: ``{Link1, Link3, Link2}`` +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 ************** @@ -246,7 +269,7 @@ will then use the provided link(s) as a loopback for this host instead of the gl Some zones such as :ref:`pf_tag_cluster` provide ways to describe the characteristics of -the loopback nodes inside the zone. +the loopback nodes inside the zone. .. |br| raw:: html