msgid "" msgstr "" "Project-Id-Version: French (cnp3-ebook)\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2026-04-18 18:16+0200\n" "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n" "Last-Translator: FULL NAME \n" "Language-Team: French \n" "Language: fr\n" "MIME-Version: 1.0\n" "Content-Type: text/plain; charset=UTF-8\n" "Content-Transfer-Encoding: 8bit\n" "Plural-Forms: nplurals=2; plural=n > 1;\n" "X-Generator: Weblate 5.14.3\n" #: ../../principles/network.rst:6 msgid "Building a network" msgstr "Construction d'un réseau" #: ../../principles/network.rst:10 msgid "" "This is an unpolished draft of the third edition of this e-book. If you find " "any error or have suggestions to improve the text, please create an issue " "via https://github.com/CNP3/ebook/issues?milestone=2 or help us by providing " "pull requests to close the existing issues." msgstr "" "Ceci est un brouillon non peaufiné de la troisième édition de cet e-book. Si " "vous avez trouvé une erreur ou avez des suggestions pour améliorer le texte, " "merci de créer une *issue* via https://github.com/CNP3/ebook/" "issues?milestone=2 ou de nous aider en ouvrant des *pull requests* pour " "fermer les *issues* existantes." #: ../../principles/network.rst:13 msgid "" "In the previous section, we have explained how reliable protocols allow " "hosts to exchange data reliably even if the underlying physical layer is " "imperfect and thus unreliable. Connecting two hosts together through a wire " "is the first step to build a network. However, this is not sufficient. Hosts " "usually need to interact with other hosts that are not directly connected " "through a direct physical layer link. This can be achieved by adding one " "layer above the datalink layer: the `network` layer." msgstr "" "Dans la section précédente, on a vu comment les protocoles fiables " "permettaient aux hôtes d'échanger des données de manière fiable même si la " "couche physique sous-jacente est imparfaite et par conséquent non fiable. " "Connecter deux hôtes ensemble via une liaison est la première étape pour " "construire un réseau. Cependant, ce n'est pas suffisant. Les hôtes ont " "habituellement besoin d'interagir avec d'autres hôtes dont ils ne sont pas " "directement connectés via la couche physique. On peut accomplir cette tâche " "en ajoutant une couche au-dessus de la couche de liaison de données : la " "couche `réseau`." #: ../../principles/network.rst:15 msgid "" "The main objective of the network layer is to allow hosts, connected to " "different networks, to exchange information through intermediate systems " "called :term:`router`. The unit of information in the network layer is " "called a :term:`packet`." msgstr "" "L'objectif principal de la couche réseau est de permettre aux hôtes, " "connectés à différents réseaux, d'échanger des informations à travers des " "systèmes intermédiaires appelés :term:`routeurs`. L'unité d'information de " "la couche réseau est appelée un :term:`paquet`." #: ../../principles/network.rst:18 msgid "" "Before explaining the operation of the network layer, it is useful to " "remember the characteristics of the service provided by the `datalink` " "layer. There are many variants of the datalink layer. Some provide a " "reliable service while others do not provide any guarantee of delivery. The " "reliable datalink layer services are popular in environments such as " "wireless networks where transmission errors are frequent. On the other hand, " "unreliable services are usually used when the physical layer provides an " "almost reliable service (i.e. only a negligible fraction of the frames are " "affected by transmission errors). Such `almost reliable` services are " "frequently used in wired and optical networks. In this chapter, we will " "assume that the datalink layer service provides an `almost reliable` service " "since this is both the most general one and also the most widely deployed " "one." msgstr "" "Avant d'expliquer le fonctionnement de la couche réseau, il est utile de se " "rappeler les caractéristiques du service fourni par la couche de `liaison " "des données`. Il y a plusieurs types de couche de liaison de données. " "Certains fournissent un service fiable alors que d'autres n'ont aucune " "garantie de livraison des données. Les couches de liaison de données fiables " "sont populaires dans des contextes où les erreurs de transmissions sont " "fréquentes, comme par exemple les réseaux sans fil. D'autre part, les " "services non fiables sont généralement utilisés là où la couche physique " "fourni un service quasi fiable (c-à-d. seulement une partie négligeable des " "frames souffrent d'erreurs de transmission). Ce genre de services `quasi " "fiables` sont fréquemment utilisés dans les réseaux filaires et optiques. " "Dans ce chapitre, on considère que les couches de liaison des données " "fournissent un service `quasi fiable` étant donné que c'est le cas le plus " "général mais aussi le plus largement déployé." #: ../../principles/network.rst:26 msgid "" "There are two main types of datalink layers. The simplest datalink layer is " "when there are only two communicating systems that are directly connected " "through the physical layer. Such a datalink layer is used when there is a " "point-to-point link between the two communicating systems. These two systems " "can be hosts or routers. PPP (Point-to-Point Protocol), defined in " ":rfc:`1661`, is an example of such a point-to-point datalink layer. Datalink " "layer entities exchange `frames`. A datalink :term:`frame` sent by a " "datalink layer entity on the left is transmitted through the physical layer, " "so that it can reach the datalink layer entity on the right. Point-to-point " "datalink layers can either provide an unreliable service " "(frames can be corrupted or lost) or a reliable service " "(in this case, the datalink layer includes retransmission mechanisms)." msgstr "" "Il y a deux principaux types de couches de liaison de données. La couche de " "liaison de données la plus simple est celle en place lorsqu'il n'y a que " "deux systèmes communiquant entre eux qui sont directement connectés via la " "couche physique. Une telle couche de liaison de données est utilisée " "lorsqu'il y a une liaison point-to-point (point à point) entre les deux " "systèmes communicants. Ces deux systèmes peuvent être des hôtes ou des " "routeurs. Le PPP (Point-to-Point Protocol), défini dans le :rfc:`1661`, est " "un exemple d'une telle couche de liaison de données point-to-point. Les " "couches de liaison de données échangent des frames. Une :term:`frame` de la " "couche datalink envoyée par une couche de liaison de données à gauche est " "transmise à travers la couche physique, de sorte à ce qu'elle puisse " "atteindre la couche de liaison de données sur la droite. Les couches de " "liaison de données Point-to-point peuvent soit fournir un service non fiable " "(les frames pouvant être corrompues ou perdues), soit un service fiable (" "dans ce cas, la couche de liaison de données inclut des mécanismes de " "retransmission)." #: ../../principles/network.rst:29 msgid "" "The second type of datalink layer is the one used in Local Area Networks " "(LAN). Conceptually, a LAN is a set of communicating devices such that any " "two devices can directly exchange frames through the datalink layer. Both " "hosts and routers can be connected to a LAN. Some LANs only connect a few " "devices, but there are LANs that can connect hundreds or even thousands of " "devices. In this chapter, we focus on the utilization of point-to-point " "datalink layers. We describe later the organization and the operation of " "Local Area Networks and their impact on the network layer." msgstr "" "Le second type de couche de liaison de données est celui utilisé dans les " "réseaux locaux (LAN). Fondamentalement, une LAN est un ensemble de " "périphériques qui communiquent ensemble de sorte à ce que n'importe quelle " "paire de périphériques puissent directement échanger des frames à travers la " "couche de liaison de données. Les hôtes et les routeurs peuvent tous deux " "être connectés à un réseau LAN. Certaines LAN peuvent accepter seulement " "quelques périphériques, mais il existe des lan qui peuvent connecter des " "centaines voire des milliers de périphériques. Dans ce chapitre, nous nous " "concentrons sur l'utilisation de couches de liaison de données point-to-" "point. Nous décrirons plus tard l'organisation et la maintenance des réseaux " "locaux ainsi que leur impact sur la couche réseau." #: ../../principles/network.rst:35 msgid "" "As a first step, let us assume that we only need to exchange a small amount " "of data. In this case, there is no issue with the maximum length of the " "frames. However, there are other more interesting problems that we need to " "tackle. To understand these problems, let us consider the network " "represented in the figure below." msgstr "" "Pour commencer, considérons que nous avons besoin d'échanger seulement une " "petite quantité de données. Dans ce cas, il n'y a pas de problème avec la " "taille maximale de la frame. Cependant, il y a des problèmes plus " "intéressants auxquels nous allons devoir nous confronter. Pour comprendre " "ces problèmes, considérons le réseau représenté dans la figure ci-dessous." #: ../../principles/network.rst:66 msgid "" "This network contains two types of devices. The hosts, represented with " "circles and the routers, represented as boxes. A host is a device which is " "able to send and receive data for its own usage in contrast with routers " "that most of the time simply forward data towards their final destination. " "Routers have multiple links to neighboring routers or hosts. Hosts are " "usually attached via a single link to the network. Nowadays, with the growth " "of wireless networks, more and more hosts are equipped with several physical " "interfaces. These hosts are often called `multihomed`. Still, using several " "interfaces at the same time often leads to practical issues that are beyond " "the scope of this document. For this reason, we only consider `single-homed` " "hosts in this e-book." msgstr "" "Ce réseau contient seulement deux types de périphériques. Les hôtes, " "représentés par des cercles, et les routeurs, représentés par des " "rectangles. Un hôte est un périphérique capable d'envoyer et recevoir des " "données pour son propre usage contrairement aux routeurs qui, la plupart du " "temps, ne se chargent que de relayer les données vers leur destination " "finale. Les routeurs ont plusieurs connexions à leurs voisins ou hôtes. Ces " "derniers sont habituellement connecté via une unique liaison au réseau. De " "nos jours, avec la croissance des réseaux sans fil, de plus en plus d'hôtes " "sont équipés de plusieurs interfaces de couche physique. Ces hôtes sont " "souvent appelés `multihomed`. Même si, utiliser plusieurs interfaces en même " "temps amène souvent en pratique des problèmes qui vont au-delà de ce qui est " "couvert dans ce document. Pour cette raison, nous ne considérons que des " "hôtes dits `single-homed` dans cet e-book." #: ../../principles/network.rst:68 msgid "" "To understand the key principles behind the operation of a network, let us " "analyze all the operations that need to be performed to allow host `A` in " "the above network to send one byte to host `B`. Thanks to the datalink layer " "used above the `A-R1` link, host `A` can easily send a byte to router `R1` " "inside a frame. However, upon reception of this frame, router `R1` needs to " "understand that this byte is destined to host `B` and not to itself. This is " "the objective of the network layer." msgstr "" "Pour comprendre les principes clés derrière la gestion d'un réseau, " "analysons toutes les opérations à effectuer pour permettre à l'hôte `A` dans " "le réseau ci-dessus d'envoyer un byte à l'hôte `B`. Grâce à la couche de " "liaison de données utilisée par-dessus la liaison `A-R1`, l'hôte `A` peut " "aisément envoyer un byte au routeur `R1` à l'intérieur d'une frame. " "Cependant, lors de la réception de cette frame, le routeur `R1` doit " "comprendre que ce byte est destiné à l'hôte `B` et non à lui-même. " "L'objectif de la couche réseau consiste à gérer cette situation." #: ../../principles/network.rst:74 msgid "" "To send one byte of information to host `B`, host `A` needs to place this " "information inside a `packet`. In addition to the data being transmitted, " "the packet also contains either the addresses of the source and the " "destination nodes or information that indicates the path that needs to be " "followed to reach the destination." msgstr "" "Pour envoyer un byte d'information vers l'hôte `B`, l'hôte `A` doit placer " "cette information à l'intérieur d'un `paquet`. En plus des données " "transmises, le paquet contient également soit l'adresse de la source et " "celle du noeud destinataire, soit des informations qui indiquent le chemin à " "prendre pour atteindre la destination." #: ../../principles/network.rst:76 msgid "There are two possible organizations for the network layer :" msgstr "Il y a deux organisations possibles pour la couche réseau :" #: ../../principles/network.rst:78 msgid "`datagram`" msgstr "les `datagram`" #: ../../principles/network.rst:79 msgid "`virtual circuits`" msgstr "les `circuits virtuels`" #: ../../principles/network.rst:83 msgid "The datagram organization" msgstr "L'organisation `datagram`" #: ../../principles/network.rst:85 msgid "" "The first and most popular organization of the network layer is the datagram " "organization. This organization is inspired by the organization of the " "postal service. Each host is identified by a `network layer address`. To " "send information to a remote host, a host creates a packet that contains:" msgstr "" "La première organisation, et la plus populaire, de la couche réseau est " "l'organisation par `datagram`. Cette organisation s'inspire de " "l'organisation du service postal. Chaque hôte est identifié par une `adresse " "sur la couche réseau`. Afin d'envoyer de l'information à un hôte distant, un " "hôte crée un paquet qui contient  :" #: ../../principles/network.rst:87 msgid "the network layer address of the destination host" msgstr "l'adresse de l'hôte de destination sur la couche réseau" #: ../../principles/network.rst:88 msgid "its own network layer address" msgstr "sa propre adresse sur la couche réseau" #: ../../principles/network.rst:89 msgid "the information to be sent" msgstr "l'information à envoyer" #: ../../principles/network.rst:91 msgid "" "To understand the datagram organization, let us consider the figure below. A " "network layer address, represented by a letter, has been assigned to each " "host and router. To send some information to host `J`, host `A` creates a " "packet containing its own address, the destination address and the " "information to be exchanged." msgstr "" "Pour comprendre l'organisation par datagram, considérons la figure ci-" "dessous. Une adresse sur la couche réseau, représentée par une lettre, a été " "assignée à chaque hôte et routeur. Pour envoyer de l'information à l'hôte `J`" ", l'hôte `A` crée un paquet contenant sa propre adresse, l'adresse de " "destination et l'information à échanger." #: ../../principles/network.rst:102 msgid "" "With the datagram organization, routers use `hop-by-hop forwarding`. This " "means that when a router receives a packet that is not destined to itself, " "it looks up the destination address of the packet in its `forwarding table`. " "A `forwarding table` is a data structure that maps each destination address " "(or set of destination addresses) to the outgoing interface over which a " "packet destined to this address must be forwarded to reach its final " "destination. The router consults its forwarding table to forward each packet " "that it handles." msgstr "" "Avec l'organisation datagram, les routeurs utilisent le `hop-by-hop " "forwarding`. Cela signifie que lorsqu'un routeur reçoit un paquet qui ne lui " "est pas destiné, il va chercher l'adresse de destination du paquet dans sa `" "table de forwarding`. Une `table de forwarding` (forwarding table) est une " "structure de données qui associe à chaque adresse de destination une " "interface de sortie qu'un paquet destiné à cette adresse doit suivre pour " "atteindre sa destination finale. Le retoueur consulte sa forwarding table " "pour transférer chaque paquet à traiter." #: ../../principles/network.rst:104 msgid "" "The figure illustrates some possible forwarding tables in this network. By " "inspecting the forwarding tables of the different routers, one can find the " "path followed by packets sent from a source to a particular destination. In " "the example above, host `A` sends its packet to router `R1`. `R1` consults " "its forwarding table and forwards the packet towards `R2`. Based on its own " "table, `R2` decides to forward the packet to `R5` that can deliver it to its " "destination. Thus, the path from `A` to `J` is `A -> R1 -> R2 -> R5 -> J`." msgstr "" "La figure illustre quelques forwarding tables possibles dans ce réseau. En " "inspectant les forwarding tables des différents routeurs, on peut trouver le " "chemin suivi par les paquets envoyés depuis une source vers une destination " "particulière. Dans l'exemple ci-dessus, l'hôte `A` envoie son paquet au " "routeur `R1`. `R1` consulte sa forwarding tables et transmet le paquet vers " "`R2`. En se basant sur sa propre table, `R2` décide de transmettre le paquet " "à `R5` qui peut le livrer à sa destination. Ainsi, le chemin de `A` à `J` " "est `A -> R1 -> R2 -> R5 -> J`." #: ../../principles/network.rst:108 msgid "" "In a network, a path can be defined as the list of all intermediate routers " "for a given source destination pair. For a given source/destination pair, " "the path can be derived by first consulting the forwarding table of the " "router attached to the source to determine the next router on the path " "towards the chosen destination. Then, the forwarding table of this router is " "queried for the same destination... The queries continue until the " "destination is reached. In a network that has valid forwarding tables, all " "the paths between all source/destination pairs contain a finite number of " "intermediate routers. However, if forwarding tables have not been correctly " "computed, two types of invalid paths can occur." msgstr "" #: ../../principles/network.rst:112 msgid "" "A path may lead to a `black hole`. In a network, a black hole is a router " "that receives packets for at least one given source/destination pair but " "does not have an entry inside its forwarding table for this destination. " "Since it does not know how to reach the destination, the router cannot " "forward the received packets and must discard them. Any centralized or " "distributed algorithm that computes forwarding tables must ensure that there " "are not black holes inside the network." msgstr "" #: ../../principles/network.rst:116 msgid "" "A second type of problem may exist in networks using the datagram " "organization. Consider a path that contains a cycle. For example, router `R1`" " sends all packets towards destination `D` via router `R2`. Router `R2` " "forwards these packets to router `R3` and finally router `R3`'s forwarding " "table uses router `R1` as its nexthop to reach destination `D`. In this " "case, if a packet destined to `D` is received by router `R1`, it will loop " "on the `R1 -> R2 -> R3 -> R1` cycle and will never reach its final " "destination. As in the black hole case, the destination is not reachable " "from all sources in the network. In practice the loop problem is more " "annoying than the black hole problem because when a packet is caught in a " "forwarding loop, it unnecessarily consumes bandwidth. In the black hole " "case, the problematic packet is quickly discarded. We will see later that " "network layer protocols include techniques to minimize the impact of such " "forwarding loops." msgstr "" #: ../../principles/network.rst:118 msgid "" "Any solution which is used to compute the forwarding tables of a network " "must ensure that all destinations are reachable from any source. This " "implies that it must guarantee the absence of black holes and forwarding " "loops." msgstr "" #: ../../principles/network.rst:122 msgid "" "The `forwarding tables` and the precise format of the packets that are " "exchanged inside the network are part of the `data plane` of the network. " "This `data plane` contains all the protocols and algorithms that are used by " "hosts and routers to create and process the packets that contain user data. " "On high-end routers, the data plane is often implemented in hardware for " "performance reasons." msgstr "" #: ../../principles/network.rst:128 msgid "" "Besides the `data plane`, a network is also characterized by its `control " "plane`. The control plane includes all the protocols and algorithms " "(often distributed) that compute the forwarding tables that are installed on " "all routers inside the network. While there is only one possible `data plane`" " for a given networking technology, different networks using the same " "technology may use different control planes." msgstr "" #: ../../principles/network.rst:130 msgid "" "The simplest `control plane` for a network is to manually compute the " "forwarding tables of all routers inside the network. This simple control " "plane is sufficient when the network is (very) small, usually up to a few " "routers." msgstr "" #: ../../principles/network.rst:136 msgid "" "An alternative to manually computed forwarding tables is to use a network " "management platform that tracks the network status and can push new " "forwarding tables on the routers when it detects any modification to the " "network topology. This solution gives some flexibility to the network " "managers in computing the paths inside their network. However, this solution " "only works if the network management platform is always capable of reaching " "all routers even when the network topology changes. This may require a " "dedicated network that allows the management platform to push information on " "the forwarding tables. Openflow is a modern example of such solutions " "[MAB2008]_. In a nutshell, Openflow is a protocol that enables a network " "controller to install specific entries in the forwarding tables of remote " "routers and much more." msgstr "" #: ../../principles/network.rst:138 msgid "" "Another interesting point that is worth being discussed is when the " "forwarding tables are computed. A widely used solution is to compute the " "entries of the forwarding tables for all destinations on all routers. This " "ensures that each router has a valid route towards each destination. These " "entries can be updated when an event occurs and the network topology " "changes. A drawback of this approach is that the forwarding tables can " "become large in large networks since each router must always maintain one " "entry for each destination inside its forwarding table." msgstr "" #: ../../principles/network.rst:140 msgid "" "Some networks use the arrival of packets as the trigger to compute the " "corresponding entries in the forwarding tables. Several technologies have " "been built upon this principle. When a packet arrives, the router consults " "its forwarding table to find a path towards the destination. If the " "destination is present in the forwarding table, the packet is forwarded. " "Otherwise, the router needs to find a way to forward the packet and update " "its forwarding table." msgstr "" #: ../../principles/network.rst:143 msgid "Computing forwarding tables" msgstr "Le calcul des tables de forwarding" #: ../../principles/network.rst:147 msgid "" "The first technique assumes that the underlying network topology is a tree. " "A tree is the simplest network to be considered when forwarding packets. The " "main advantage of using a tree is that there is only one path between any " "pair of nodes inside the network. Since a tree does not contain any cycle, " "it is impossible to have forwarding loops in a tree-shaped network." msgstr "" #: ../../principles/network.rst:151 msgid "" "In a tree-shaped network, it is relatively simple for each node to " "automatically compute its forwarding table by inspecting the packets that it " "receives. For this, each node uses the source and destination addresses " "present inside each packet. Thanks to the source address, a node can learn " "the location of the different sources inside the network. Each source has a " "unique address. When a node receives a packet over a given interface, it " "learns that the source (address) of this packet is reachable via this " "interface. The node maintains a data structure that maps each known source " "address to an incoming interface. This data structure is often called the " "`port-address table` since it indicates the interface (or port) to reach a " "given address." msgstr "" #: ../../principles/network.rst:153 msgid "" "Learning the location of the sources is not sufficient, nodes also need to " "forward packets towards their destination. When a node receives a packet " "whose destination address is already present inside its port-address table, " "it simply forwards the packet on the interface listed in the port-address " "table. In this case, the packet will follow the port-address table entries " "in the downstream nodes and will reach the destination. If the destination " "address is not included in the port-address table, the node simply forwards " "the packet on all its interfaces, except the interface from which the packet " "was received. Forwarding a packet over all interfaces is usually called " "`broadcasting` in the terminology of computer networks. Sending the packet " "over all interfaces except one is a costly operation since the packet is " "sent over links that do not reach the destination. Given the tree-shape of " "the network, the packet will explore all downstream branches of the tree and " "will finally reach its destination. In practice, the `broadcasting` " "operation does not occur too often and its performance impact remains " "limited." msgstr "" #: ../../principles/network.rst:187 msgid "" "By inspecting the source and destination addresses of packets, network nodes " "can automatically derive their forwarding tables. As we will discuss later, " "this technique is used in :term:`Ethernet` networks. Despite being widely " "used, it has two important drawbacks. First, packets sent to unknown " "destinations are broadcasted in the network even if the destination is not " "attached to the network. Consider the transmission of ten packets destined " "to `Z` in the network above. When a node receives a packet towards this " "destination, it can only broadcast that packet. Since `Z` is not attached to " "the network, no node will ever receive a packet whose source is `Z` to " "update its forwarding table. The second and more important problem is that " "few networks have a tree-shaped topology. It is interesting to analyze what " "happens when a port-address table is used in a network that contains a " "cycle. Consider the simple network shown below with a single host." msgstr "" #: ../../principles/network.rst:216 msgid "the `data packets`" msgstr "" #: ../../principles/network.rst:217 msgid "the `control packets`" msgstr "" #: ../../principles/network.rst:249 msgid "" "For example, consider again the network topology above. `A` sends a control " "packet towards `B`. The initial `record route` is empty. When `R1` receives " "the packet, it adds its own address to the `record route` and forwards a " "copy to `R2` and another to `R3`. `R2` receives the packet, adds itself to " "the `record route` and forwards it to `R3`. `R3` receives two copies of the " "packet. The first contains the `[R1,R2]` `record route` and the second `[R1]`" ". In the end, `B` will receive two control packets containing `[R1,R2,R3,R4]" "` and `[R1,R3,R4]` as `record routes`. `B` can keep these two paths or " "select the best one and discard the second. A popular heuristic is to select " "the `record route` of the first received packet as being the best one since " "this likely corresponds to the shortest delay path." msgstr "" #: ../../principles/network.rst:251 msgid "" "With the received `record route`, `B` can send a `data packet` to `A`. For " "this, it simply reverses the chosen `record route`. However, we still need " "to communicate the chosen path to `A`. This can be done by putting the `" "record route` inside a control packet which is sent back to `A` over the " "reverse path. An alternative is to simply send a `data packet` back to `A`. " "This packet will travel back to `A`. To allow `A` to inspect the entire path " "followed by the `data packet`, its `source route` must contain all " "intermediate routers when it is received by `A`. This can be achieved by " "encoding the `source route` using a data structure that contains an index " "and the ordered list of node addresses. The index always points to the next " "address in the `source route`. It is initialized at `0` when a packet is " "created and incremented by each intermediate node." msgstr "" #: ../../principles/network.rst:255 msgid "Flat or hierarchical addresses" msgstr "" #: ../../principles/network.rst:257 msgid "" "The last, but important, point to discuss about the `data plane` of the " "networks that rely on the datagram mode is their addressing scheme. In the " "examples above, we have used letters to represent the addresses of the hosts " "and network nodes. In practice, all addresses are encoded as a bit string. " "Most network technologies use a fixed size bit string to represent source " "and destination address. These addresses can be organized in two different " "ways." msgstr "" #: ../../principles/network.rst:259 msgid "" "The first organization, which is the one that we have implicitly assumed " "until now, is the `flat addressing` scheme. Under this scheme, each host and " "network node has a unique address. The unicity of the addresses is important " "for the operation of the network. If two hosts have the same address, it can " "become difficult for the network to forward packets towards this " "destination. `Flat addresses` are typically used in situations where network " "nodes and hosts need to be able to communicate immediately with unique " "addresses. These `flat addresses` are often embedded inside the network " "interface cards. The network card manufacturer creates one unique address " "for each interface and this address is stored in the read-only memory of the " "interface. An advantage of this addressing scheme is that it easily supports " "unstructured and mobile networks. When a host moves, it can attach to " "another network and remain confident that its address is unique and enables " "it to communicate inside the new network." msgstr "" #: ../../principles/network.rst:269 msgid "" "This hierarchical allocation of addresses can be applied in any type of " "network. In practice, the allocation of the addresses must follow the " "network topology. Usually, this is achieved by dividing the addressing space " "in consecutive blocks and then allocating these blocks to different parts of " "the network. In a small network, the simplest solution is to allocate one " "block of addresses to each network node and assign the host addresses from " "the attached node." msgstr "" #: ../../principles/network.rst:295 msgid "" "In the above figure, assume that the network uses 16 bits addresses and that " "the prefix `01001010` has been assigned to the entire network. Since the " "network contains four routers, the network operator could assign one block " "of sixty-four addresses to each router. `R1` would use address " "`0100101000000000` while `A` could use address `0100101000000001`. `R2` " "could be assigned all addresses from `0100101001000000` to " "`0100101001111111`. `R4` could then use `0100101011000000` and assign " "`0100101011000001` to `B`. Other allocation schemes are possible. For " "example, `R3` could be allocated a larger block of addresses than `R2` and " "`R4` could use a sub-block from `R3` 's address block." msgstr "" #: ../../principles/network.rst:302 msgid "Dealing with heterogeneous datalink layers" msgstr "" #: ../../principles/network.rst:304 msgid "" "Sometimes, the network layer needs to deal with heterogeneous datalink " "layers. For example, two hosts connected to different datalink layers " "exchange packets via routers that are using other types of datalink layers. " "Thanks to the network layer, this exchange of packets is possible provided " "that each packet can be placed inside a datalink layer frame before being " "transmitted. If all datalink layers support the same frame size, this is " "simple. When a node receives a frame, it decapsulates the packet that it " "contains, checks the header and forwards it, encapsulated inside another " "frame, to the outgoing interface. Unfortunately, the encapsulation operation " "is not always possible. Each datalink layer is characterized by the maximum " "frame size that it supports. Datalink layers typically support frames " "containing up to a few hundreds or a few thousands of bytes. The maximum " "frame size that a given datalink layer supports depends on its underlying " "technology. Unfortunately, most datalink layers support a different maximum " "frame size. This implies that when a host sends a large packet inside a " "frame to its nexthop router, there is a risk that this packet will have to " "traverse a link that is not capable of forwarding the packet inside a single " "frame. In principle, there are three possibilities to solve this problem. To " "discuss them, we consider a simple scenario with two hosts connected to a " "router as shown in the figure below." msgstr "" #: ../../principles/network.rst:323 msgid "" "Consider in the network above that host `A` wants to send a 900 bytes packet " "(870 bytes of payload and 30 bytes of header) to host `B` via router `R1`. " "Host `A` encapsulates this packet inside a single frame. The frame is " "received by router `R1` which extracts the packet. Router `R1` has three " "possible options to process this packet." msgstr "" #: ../../principles/network.rst:325 msgid "" "The packet is too large and router `R1` cannot forward it to router `R2`. It " "rejects the packet and sends a control packet back to the source (host `A`) " "to indicate that it cannot forward packets longer than 500 bytes " "(minus the packet header). The source could react to this control packet by " "retransmitting the information in smaller packets." msgstr "" #: ../../principles/network.rst:327 msgid "" "The network layer is able to fragment a packet. In our example, the router " "could fragment the packet in two parts. The first part contains the " "beginning of the payload and the second the end. There are two possible ways " "to perform this fragmentation." msgstr "" #: ../../principles/network.rst:332 msgid "" "Each of the packet fragments is a valid packet that contains a header with " "the source (host `A`) and destination (host `B`) addresses. When router `R2` " "receives a packet fragment, it treats this packet as a regular packet and " "forwards it to its final destination (host `B`). Host `B` reassembles the " "received fragments." msgstr "" #: ../../principles/network.rst:335 msgid "" "These three solutions have advantages and drawbacks. With the first " "solution, routers remain simple and do not need to perform any fragmentation " "operation. This is important when routers are implemented mainly in " "hardware. However, hosts must be complex since they need to store the " "packets that they produce if they need to pass through a link that does not " "support large packets. This increases the buffering required on the hosts." msgstr "" #: ../../principles/network.rst:337 msgid "" "Furthermore, a single large packet may potentially need to be retransmitted " "several times. Consider for example a network similar to the one shown above " "but with four routers. Assume that the link `R1->R2` supports 1000 bytes " "packets, link `R2->R3` 800 bytes packets and link `R3->R4` 600 bytes " "packets. A host attached to `R1` that sends large packet will have to first " "try 1000 bytes, then 800 bytes and finally 600 bytes. Fortunately, this " "scenario does not occur very often in practice and this is the reason why " "this solution is used in real networks." msgstr "" #: ../../principles/network.rst:339 msgid "" "Fragmenting packets on a per-link basis, as presented for the second " "solution, can minimize the transmission overhead since a packet is only " "fragmented on the links where fragmentation is required. Large packets can " "continue to be used downstream of a link that only accepts small packets. " "However, this reduction of the overhead comes with two drawbacks. First, " "fragmenting packets, potentially on all links, increases the processing time " "and the buffer requirements on the routers. Second, this solution leads to a " "longer end-to-end delay since the downstream router has to reassemble all " "the packet fragments before forwarding the packet." msgstr "" #: ../../principles/network.rst:341 msgid "" "The last solution is a compromise between the two others. Routers need to " "perform fragmentation but they do not need to reassemble packet fragments. " "Only the hosts need to have buffers to reassemble the received fragments. " "This solution has a lower end-to-end delay and requires fewer processing " "time and memory on the routers." msgstr "" #: ../../principles/network.rst:343 msgid "" "The first solution to the fragmentation problem presented above suggests the " "utilization of control packets to inform the source about the reception of a " "too long packet. This is only one of the functions that are performed by the " "control protocol in the network layer. Other functions include :" msgstr "" #: ../../principles/network.rst:345 msgid "" "sending a control packet back to the source if a packet is received by a " "router that does not have a valid entry in its forwarding table" msgstr "" #: ../../principles/network.rst:346 msgid "" "sending a control packet back to the source if a router detects that a " "packet is looping inside the network" msgstr "" #: ../../principles/network.rst:347 msgid "verifying that packets can reach a given destination" msgstr "" #: ../../principles/network.rst:349 msgid "" "We will discuss these functions in more details when we will describe the " "protocols that are used in the network layer of the TCP/IP protocol suite." msgstr "" #: ../../principles/network.rst:353 msgid "Virtual circuit organization" msgstr "" #: ../../principles/network.rst:362 msgid "the outgoing interface for the packet" msgstr "" #: ../../principles/network.rst:363 msgid "the label for the outgoing packet" msgstr "" #: ../../principles/network.rst:365 msgid "" "For example, consider the `label forwarding table` of a network node below." msgstr "" #: ../../principles/network.rst:369 #: ../../principles/network.rst:410 #: ../../principles/network.rst:420 #: ../../principles/network.rst:430 #: ../../principles/network.rst:440 msgid "index" msgstr "" #: ../../principles/network.rst:369 #: ../../principles/network.rst:410 #: ../../principles/network.rst:420 #: ../../principles/network.rst:430 #: ../../principles/network.rst:440 msgid "outgoing interface" msgstr "" #: ../../principles/network.rst:369 #: ../../principles/network.rst:410 #: ../../principles/network.rst:420 #: ../../principles/network.rst:430 #: ../../principles/network.rst:440 msgid "label" msgstr "" #: ../../principles/network.rst:371 #: ../../principles/network.rst:412 #: ../../principles/network.rst:414 #: ../../principles/network.rst:422 #: ../../principles/network.rst:432 #: ../../principles/network.rst:442 msgid "0" msgstr "0" #: ../../principles/network.rst:371 msgid "South" msgstr "" #: ../../principles/network.rst:371 msgid "7" msgstr "" #: ../../principles/network.rst:373 #: ../../principles/network.rst:412 #: ../../principles/network.rst:414 #: ../../principles/network.rst:424 #: ../../principles/network.rst:434 #: ../../principles/network.rst:444 msgid "1" msgstr "" #: ../../principles/network.rst:373 #: ../../principles/network.rst:422 #: ../../principles/network.rst:444 msgid "none" msgstr "" #: ../../principles/network.rst:375 #: ../../principles/network.rst:377 msgid "2" msgstr "" #: ../../principles/network.rst:375 msgid "West" msgstr "" #: ../../principles/network.rst:377 msgid "3" msgstr "" #: ../../principles/network.rst:377 msgid "East" msgstr "" #: ../../principles/network.rst:380 msgid "" "If this node receives a packet with `label=2`, it forwards the packet on its " "`West` interface and sets the `label` of the outgoing packet to `2`. If the " "received packet's `label` is set to `3`, then the packet is forwarded over " "the `East` interface and the `label` of the outgoing packet is set to `2`. " "If a packet is received with a label field set to `1`, the packet is " "discarded since the corresponding `label forwarding table` entry is invalid." msgstr "" #: ../../principles/network.rst:382 msgid "" "`Label switching` enables a full control over the path followed by packets " "inside the network. Consider the network below and assume that we want to " "use two virtual circuits : `R1->R3->R4->R2->R5` and `R2->R1->R3->R4->R5`." msgstr "" #: ../../principles/network.rst:412 msgid "->R2" msgstr "" #: ../../principles/network.rst:414 #: ../../principles/network.rst:424 msgid "->R5" msgstr "" #: ../../principles/network.rst:417 msgid "" "Since a packet received with `label=1` must be forwarded to `R5` with " "`label=1`, `R2`'s `label forwarding table` could contain :" msgstr "" #: ../../principles/network.rst:427 msgid "" "Two virtual circuits pass through `R3`. They both need to be forwarded to " "`R4`, but `R4` expects `label=1` for packets belonging to the virtual " "circuit originated by `R2` and `label=0` for packets belonging to the other " "virtual circuit. `R3` could choose to leave the labels unchanged." msgstr "" #: ../../principles/network.rst:432 #: ../../principles/network.rst:434 msgid "->R4" msgstr "" #: ../../principles/network.rst:442 msgid "->R3" msgstr "" #: ../../principles/network.rst:447 msgid "" "The figure below shows the path followed by the packets on the " "`R1->R3->R4->R2->R5` path in red with on each arrow the label used in the " "packets." msgstr "" #: ../../principles/network.rst:472 msgid "" "MultiProtocol Label Switching (MPLS) is the example of a deployed networking " "technology that relies on label switching. MPLS is more complex than the " "above description because it has been designed to be easily integrated with " "datagram technologies. However, the principles remain. `Asynchronous " "Transfer Mode` (ATM) and Frame Relay are other examples of technologies that " "rely on `label switching`." msgstr "" #: ../../principles/linkstate.rst:128 #: ../../principles/network.rst:505 msgid "Footnotes" msgstr "Notes de pied de page" #: ../../principles/network.rst:506 msgid "" "We will see later a more detailed description of Multiprotocol Label " "Switching, a networking technology that is capable of using one or more " "labels." msgstr "" #: ../../principles/network.rst:511 msgid "The control plane" msgstr "" #: ../../principles/network.rst:513 msgid "" "One of the objectives of the `control plane` in the network layer is to " "maintain the routing tables that are used on all routers. As indicated " "earlier, a routing table is a data structure that contains, for each " "destination address (or block of addresses) known by the router, the " "outgoing interface over which the router must forward a packet destined to " "this address. The routing table may also contain additional information such " "as the address of the next router on the path towards the destination or an " "estimation of the cost of this path." msgstr "" #: ../../principles/network.rst:515 msgid "" "In this section, we discuss the main techniques that can be used to maintain " "the forwarding tables in a network." msgstr "" #: ../../principles/dv.rst:7 msgid "Distance vector routing" msgstr "" #: ../../principles/dv.rst:9 msgid "" "Distance vector routing is a simple distributed routing protocol. Distance " "vector routing allows routers to automatically discover the destinations " "reachable inside the network as well as the shortest path to reach each of " "these destinations. The shortest path is computed based on `metrics` or " "`costs` that are associated to each link. We use `l.cost` to represent the " "metric that has been configured for link `l` on a router." msgstr "" #: ../../principles/dv.rst:11 msgid "" "Each router maintains a routing table. The routing table `R` can be modeled " "as a data structure that stores, for each known destination address `d`, the " "following attributes :" msgstr "" #: ../../principles/dv.rst:13 msgid "" "`R[d].link` is the outgoing link that the router uses to forward packets " "towards destination `d`" msgstr "" #: ../../principles/dv.rst:14 msgid "" "`R[d].cost` is the sum of the metrics of the links that compose the shortest " "path to reach destination `d`" msgstr "" #: ../../principles/dv.rst:15 msgid "" "`R[d].time` is the timestamp of the last distance vector containing " "destination `d`" msgstr "" #: ../../principles/dv.rst:17 msgid "" "A router that uses distance vector routing regularly sends its distance " "vector over all its interfaces. This distance vector is a summary of the " "router's routing table that indicates the distance towards each known " "destination. This distance vector can be computed from the routing table by " "using the pseudo-code below." msgstr "" #: ../../principles/dv.rst:31 msgid "" "When a router boots, it does not know any destination in the network and its " "routing table only contains its local address(es). It thus sends to all its " "neighbors a distance vector that contains only its address at a distance of " "`0`. When a router receives a distance vector on link `l`, it processes it " "as follows." msgstr "" #: ../../principles/dv.rst:54 msgid "" "The router iterates over all addresses included in the distance vector. If " "the distance vector contains a destination address that the router does not " "know, it inserts it inside its routing table via link `l` and at a distance " "which is the sum between the distance indicated in the distance vector and " "the cost associated to link `l`. If the destination was already known by the " "router, it only updates the corresponding entry in its routing table if " "either :" msgstr "" #: ../../principles/dv.rst:59 msgid "" "The first condition ensures that the router discovers the shortest path " "towards each destination. The second condition is used to take into account " "the changes of routes that may occur after a link failure or a change of the " "metric associated to a link." msgstr "" #: ../../principles/dv.rst:61 msgid "" "To understand the operation of a distance vector protocol, let us consider " "the network of five routers shown below." msgstr "" #: ../../principles/dv.rst:70 msgid "" "Assume that router `A` is the first to send its distance vector `[A=0]`." msgstr "" #: ../../principles/dv.rst:72 msgid "" "`B` and `D` process the received distance vector and update their routing " "table with a route towards `A`." msgstr "" #: ../../principles/dv.rst:73 msgid "" "`D` sends its distance vector `[D=0,A=1]` to `A` and `E`. `E` can now reach " "`A` and `D`." msgstr "" #: ../../principles/dv.rst:74 msgid "`C` sends its distance vector `[C=0]` to `B` and `E`" msgstr "" #: ../../principles/dv.rst:75 msgid "" "`E` sends its distance vector `[E=0,D=1,A=2,C=1]` to `D`, `B` and `C`. `B` " "can now reach `A`, `C`, `D` and `E`" msgstr "" #: ../../principles/dv.rst:76 msgid "" "`B` sends its distance vector `[B=0,A=1,C=1,D=2,E=1]` to `A`, `C` and `E`. " "`A`, `B`, `C` and `E` can now reach all five routers of this network." msgstr "" #: ../../principles/dv.rst:77 msgid "`A` sends its distance vector `[A=0,B=1,C=2,D=1,E=2]` to `B` and `D`." msgstr "" #: ../../principles/dv.rst:79 msgid "" "At this point, all routers can reach all other routers in the network thanks " "to the routing tables shown in the figure below." msgstr "" #: ../../principles/dv.rst:90 msgid "" "To deal with link and router failures, routers use the timestamp stored in " "their routing table. As all routers send their distance vector every `N` " "seconds, the timestamp of each route should be regularly refreshed. Thus no " "route should have a timestamp older than `N` seconds, unless the route is " "not reachable anymore. In practice, to cope with the possible loss of a " "distance vector due to transmission errors, routers check the timestamp of " "the routes stored in their routing table every `N` seconds and remove the " "routes that are older than :math:`3 \\times N` seconds." msgstr "" #: ../../principles/dv.rst:92 msgid "" "When a router notices that a route towards a destination has expired, it " "must first associate an :math:`\\infty` cost to this route and send its " "distance vector to its neighbors to inform them. The route can then be " "removed from the routing table after some time " "(e.g. :math:`3 \\times N` seconds), to ensure that the neighboring routers " "have received the bad news, even if some distance vectors do not reach them " "due to transmission errors." msgstr "" #: ../../principles/dv.rst:94 msgid "" "Consider the example above and assume that the link between routers `A` and " "`B` fails. Before the failure, `A` used `B` to reach destinations `B`, `C` " "and `E` while `B` only used the `A-B` link to reach `A`. The two routers " "detect the failure by the timeouts in the affected entries in their routing " "tables. Both routers `A` and `B` send their distance vector." msgstr "" #: ../../principles/dv.rst:96 msgid "" "`A` sends its distance vector :math:`[A=0,B=\\infty,C=\\infty,D=1,E=\\infty]`" ". `D` knows that it cannot reach `B` anymore via `A`" msgstr "" #: ../../principles/dv.rst:97 msgid "" "`D` sends its distance vector :math:`[D=0,B=\\infty,A=1,C=2,E=1]` to `A` and " "`E`. `A` recovers routes towards `C` and `E` via `D`." msgstr "" #: ../../principles/dv.rst:98 msgid "" "`B` sends its distance vector :math:`[B=0,A=\\infty,C=1,D=2,E=1]` to `E` and " "`C`. `C` learns that there is no route anymore to reach `A` via `B`." msgstr "" #: ../../principles/dv.rst:99 msgid "" "`E` sends its distance vector :math:`[E=0,A=2,C=1,D=1,B=1]` to `D`, `B` and " "`C`. `D` learns a route towards `B`. `C` and `B` learn a route towards `A`." msgstr "" #: ../../principles/dv.rst:113 msgid "" "Consider now that the link between `D` and `E` fails. The network is now " "partitioned into two disjoint parts: (`A` , `D`) and (`B`, `E`, `C`). The " "routes towards `B`, `C` and `E` expire first on router `D`. At this time, " "router `D` updates its routing table." msgstr "" #: ../../principles/dv.rst:115 msgid "" "If `D` sends :math:`[D=0, A=1, B=\\infty, C=\\infty, E=\\infty]`, `A` learns " "that `B`, `C` and `E` are unreachable and updates its routing table." msgstr "" #: ../../principles/dv.rst:117 msgid "" "Unfortunately, if the distance vector sent to `A` is lost or if `A` sends " "its own distance vector ( :math:`[A=0,D=1,B=3,C=3,E=2]` ) at the same time " "as `D` sends its distance vector, `D` updates its routing table to use the " "shorter routes advertised by `A` towards `B`, `C` and `E`. After some time " "`D` sends a new distance vector : :math:`[D=0,A=1,E=3,C=4,B=4]`. `A` updates " "its routing table and after some time sends its own distance vector :math:`" "[A=0,D=1,B=5,C=5,E=4]`, etc. This problem is known as the `count to infinity " "problem` in the networking literature." msgstr "" #: ../../principles/dv.rst:119 msgid "" "Routers `A` and `D` exchange distance vectors with increasing costs until " "these costs reach :math:`\\infty`. This problem may occur in other scenarios " "than the one depicted in the above figure. In fact, distance vector routing " "may suffer from count to infinity problems as soon as there is a cycle in " "the network. Unfortunately, cycles are widely used in networks since they " "provide the required redundancy to deal with link and router failures. To " "mitigate the impact of counting to infinity, some distance vector protocols " "consider that :math:`16=\\infty`. Unfortunately, this limits the metrics " "that network operators can use and the diameter of the networks using " "distance vectors." msgstr "" #: ../../principles/dv.rst:124 msgid "" "This count to infinity problem occurs because router `A` advertises to " "router `D` a route that it has learned via router `D`. A possible solution " "to avoid this problem could be to change how a router creates its distance " "vector. Instead of computing one distance vector and sending it to all its " "neighbors, a router could create a distance vector that is specific to each " "neighbor and only contains the routes that have not been learned via this " "neighbor. This could be implemented by the following pseudocode." msgstr "" #: ../../principles/dv.rst:141 msgid "" "This technique is called `split-horizon`. With this technique, the count to " "infinity problem would not have happened in the above scenario, as router `A`" " would have advertised :math:`[A=0]` after the failure, since it learned all " "its other routes via router `D`. Another variant called `split-horizon with " "poison reverse` is also possible. Routers using this variant advertise a " "cost of :math:`\\infty` for the destinations that they reach via the router " "to which they send the distance vector. This can be implemented by using the " "pseudo-code below." msgstr "" #: ../../principles/dv.rst:167 msgid "" "After having detected the failure, router `B` sends its distance vectors:" msgstr "" #: ../../principles/dv.rst:169 msgid ":math:`[A=\\infty,B=0,C=\\infty,E=1]` to router `C`" msgstr "" #: ../../principles/dv.rst:170 msgid ":math:`[A=\\infty,B=0,C=1,E=\\infty]` to router `E`" msgstr "" #: ../../principles/dv.rst:172 msgid "" "If, unfortunately, the distance vector sent to router `C` is lost due to a " "transmission error or because router `C` is overloaded, a new count to " "infinity problem can occur. If router `C` sends its distance vector :math:`" "[A=2,B=1,C=0,E=\\infty]` to router `E`, this router installs a route of " "distance `3` to reach `A` via `C`. Router `E` sends its distance vectors " ":math:`[A=3,B=\\infty,C=1,E=1]` to router `B` and :math:`" "[A=\\infty,B=1,C=\\infty,E=0]` to router `C`. This distance vector allows `B`" " to recover a route of distance `4` to reach `A`." msgstr "" #: ../../principles/dv.rst:177 msgid "Forwarding tables versus routing tables" msgstr "" #: ../../principles/dv.rst:179 msgid "" "Routers usually maintain at least two data structures that contain " "information about the reachable destinations. The first data structure is " "the `routing table`. The `routing table` is a data structure that associates " "a destination to an outgoing interface or a nexthop router and a set of " "additional attributes. Different routing protocols can associate different " "attributes for each destination. Distance vector routing protocols will " "store the cost to reach the destination along the shortest path. Other " "routing protocols may store information about the number of hops of the best " "path, its lifetime or the number of sub paths. A `routing table` may store " "different paths towards a given destination and flag one of them as the best " "one." msgstr "" #: ../../principles/dv.rst:181 msgid "" "The `routing table` is a software data structure which is updated by " "(one or more) routing protocols. The `routing table` is usually not directly " "used when forwarding packets. Packet forwarding relies on a more compact " "data structure which is the `forwarding table`. On high-end routers, the `" "forwarding table` is implemented directly in hardware while lower " "performance routers will use a software implementation. A `forwarding table` " "contains a subset of the information found in the `routing table`. It only " "contains the nexthops towards each destination that are used to forward " "packets and no attributes. A `forwarding table` will typically associate " "each destination to one or more outgoing interface or nexthop router." msgstr "" #: ../../principles/linkstate.rst:9 msgid "Link state routing" msgstr "" #: ../../principles/linkstate.rst:11 msgid "" "Link state routing is the second family of routing protocols. While distance " "vector routers use a distributed algorithm to compute their routing tables, " "link-state routers exchange messages to allow each router to learn the " "entire network topology. Based on this learned topology, each router is then " "able to compute its routing table by using a shortest path computation such " "as Dijkstra's algorithm [Dijkstra1959]_. A detailed description of this " "shortest path algorithm may be found in [Wikipedia:Dijkstra]_." msgstr "" #: ../../principles/linkstate.rst:13 msgid "" "For link-state routing, a network is modeled as a `directed weighted graph`. " "Each router is a node, and the links between routers are the edges in the " "graph. A positive weight is associated to each directed edge and routers use " "the shortest path to reach each destination. In practice, different types of " "weights can be associated to each directed edge :" msgstr "" #: ../../principles/linkstate.rst:15 msgid "" "unit weight. If all links have a unit weight, shortest path routing prefers " "the paths with the least number of intermediate routers." msgstr "" #: ../../principles/linkstate.rst:16 msgid "" "weight proportional to the propagation delay on the link. If all link " "weights are configured this way, shortest path routing uses the paths with " "the smallest propagation delay." msgstr "" #: ../../principles/linkstate.rst:17 msgid "" ":math:`weight=\\frac{C}{bandwidth}` where `C` is a constant larger than the " "highest link bandwidth in the network. If all link weights are configured " "this way, shortest path routing prefers higher bandwidth paths over lower " "bandwidth paths." msgstr "" #: ../../principles/linkstate.rst:19 msgid "" "Usually, the same weight is associated to the two directed edges that " "correspond to a physical link " "(i.e. :math:`R1 \\rightarrow R2` and :math:`R2 \\rightarrow R1`). However, " "nothing in the link state protocols requires this. For example, if the " "weight is set in function of the link bandwidth, then an asymmetric ADSL " "link could have a different weight for the upstream and downstream " "directions. Other variants are possible. Some networks use optimization " "algorithms to find the best set of weights to minimize congestion inside the " "network for a given traffic demand [FRT2002]_." msgstr "" #: ../../principles/linkstate.rst:24 msgid "" "When a link-state router boots, it first needs to discover to which routers " "it is directly connected. For this, each router sends a HELLO message every " "`N` seconds on all its interfaces. This message contains the router's " "address. Each router has a unique address. As its neighboring routers also " "send HELLO messages, the router automatically discovers to which neighbors " "it is connected. These HELLO messages are only sent to neighbors that are " "directly connected to a router, and a router never forwards the HELLO " "messages that it receives. HELLO messages are also used to detect link and " "router failures. A link is considered to have failed if no HELLO message has " "been received from a neighboring router for a period of :math:`k \\times N` " "seconds." msgstr "" #: ../../principles/linkstate.rst:33 msgid "" "Once a router has discovered its neighbors, it must reliably distribute all " "its outgoing edges to all routers in the network to allow them to compute " "their local view of the network topology. For this, each router builds a " "`link-state packet` (LSP) containing the following information:" msgstr "" #: ../../principles/linkstate.rst:35 msgid "LSP.Router: identification (address) of the sender of the LSP" msgstr "" #: ../../principles/linkstate.rst:36 msgid "LSP.age: age or remaining lifetime of the LSP" msgstr "" #: ../../principles/linkstate.rst:37 msgid "LSP.seq: sequence number of the LSP" msgstr "" #: ../../principles/linkstate.rst:42 msgid "" "These LSPs must be reliably distributed inside the network without using the " "router's routing table since these tables can only be computed once the LSPs " "have been received. The `Flooding` algorithm is used to efficiently " "distribute the LSPs of all routers. Each router that implements `flooding` " "maintains a `link state database` (LSDB) containing the most recent LSP sent " "by each router. When a router receives a LSP, it first verifies whether this " "LSP is already stored inside its LSDB. If so, the router has already " "distributed the LSP earlier and it does not need to forward it. Otherwise, " "the router forwards the LSP on all its links except the link over which the " "LSP was received. Flooding can be implemented by using the following pseudo-" "code." msgstr "" #: ../../principles/linkstate.rst:59 msgid "Which is the most recent LSP ?" msgstr "" #: ../../principles/linkstate.rst:61 msgid "" "A router that implements flooding must be able to detect whether a received " "LSP is newer than the stored LSP. This requires a comparison between the " "sequence number of the received LSP and the sequence number of the LSP " "stored in the link state database. The ARPANET routing protocol [MRR1979]_ " "used a 6 bits sequence number and implemented the comparison as follows " ":rfc:`789`" msgstr "" #: ../../principles/linkstate.rst:69 msgid "" "This comparison takes into account the modulo :math:`2^{6}` arithmetic used " "to increment the sequence numbers. Intuitively, the comparison divides the " "circle of all sequence numbers into two halves. Usually, the sequence number " "of the received LSP is equal to the sequence number of the stored LSP " "incremented by one, but sometimes the sequence numbers of two successive " "LSPs may differ, e.g. if one router has been disconnected for some time. The " "comparison above worked well until October 27, 1980. On this day, the " "ARPANET crashed completely. The crash was complex and involved several " "routers. At one point, LSP `40` and LSP `44` from one of the routers were " "stored in the LSDB of some routers in the ARPANET. As LSP `44` was the " "newest, it should have replaced LSP `40` on all routers. Unfortunately, one " "of the ARPANET routers suffered from a memory problem and sequence number " "`40` (`101000` in binary) was replaced by `8` (`001000` in binary) in the " "buggy router and flooded. Three LSPs were present in the network and `44` " "was newer than `40` which is newer than `8`, but unfortunately `8` was " "considered to be newer than `44`... All routers started to exchange these " "three link state packets forever and the only solution to recover from this " "problem was to shutdown the entire network :rfc:`789`." msgstr "" #: ../../principles/linkstate.rst:71 msgid "" "Current link state routing protocols usually use 32 bits sequence numbers " "and include a special mechanism in the unlikely case that a sequence number " "reaches the maximum value (with a 32 bits sequence number space, it takes " "136 years to cycle the sequence numbers if a link state packet is generated " "every second)." msgstr "" #: ../../principles/linkstate.rst:73 msgid "" "To deal with the memory corruption problem, link state packets contain a " "checksum or CRC. This checksum is computed by the router that generates the " "LSP. Each router must verify the checksum when it receives or floods an LSP. " "Furthermore, each router must periodically verify the checksums of the LSPs " "stored in its LSDB. This enables them to cope with memory errors that could " "corrupt the LSDB as the one that occurred in the ARPANET." msgstr "" #: ../../principles/linkstate.rst:75 msgid "" "Flooding is illustrated in the figure below. By exchanging HELLO messages, " "each router learns its direct neighbors. For example, router `E` learns that " "it is directly connected to routers `D`, `B` and `C`. Its first LSP has " "sequence number `0` and contains the directed links `E->D`, `E->B` and `E->C`" ". Router `E` sends its LSP on all its links and routers `D`, `B` and `C` " "insert the LSP in their LSDB and forward it over their other links." msgstr "" #: ../../principles/linkstate.rst:87 msgid "" "Flooding allows LSPs to be distributed to all routers inside the network " "without relying on routing tables. In the example above, the LSP sent by " "router `E` is likely to be sent twice on some links in the network. For " "example, routers `B` and `C` receive `E`'s LSP at almost the same time and " "forward it over the `B-C` link. To avoid sending the same LSP twice on each " "link, a possible solution is to slightly change the pseudo-code above so " "that a router waits for some random time before forwarding a LSP on each " "link. The drawback of this solution is that the delay to flood an LSP to all " "routers in the network increases. In practice, routers immediately flood the " "LSPs that contain new information (e.g. addition or removal of a link) and " "delay the flooding of refresh LSPs (i.e. LSPs that contain exactly the same " "information as the previous LSP originating from this router) [FFEB2005]_." msgstr "" #: ../../principles/linkstate.rst:89 msgid "" "To ensure that all routers receive all LSPs, even when there are " "transmissions errors, link state routing protocols use `reliable flooding`. " "With `reliable flooding`, routers use acknowledgments and if necessary " "retransmissions to ensure that all link state packets are successfully " "transferred to each neighboring router. Thanks to reliable flooding, all " "routers store in their LSDB the most recent LSP sent by each router in the " "network. By combining the received LSPs with its own LSP, each router can " "build a graph that represents the entire network topology." msgstr "" #: ../../principles/linkstate.rst:98 msgid "Static or dynamic link metrics ?" msgstr "" #: ../../principles/linkstate.rst:100 msgid "" "As link state packets are flooded regularly, routers are able to measure the " "quality (e.g. delay or load) of their links and adjust the metric of each " "link according to its current quality. Such dynamic adjustments were " "included in the ARPANET routing protocol [MRR1979]_ . However, experience " "showed that it was difficult to tune the dynamic adjustments and ensure that " "no forwarding loops occur in the network [KZ1989]_. Today's link state " "routing protocols use metrics that are manually configured on the routers " "and are only changed by the network operators or network management tools " "[FRT2002]_." msgstr "" #: ../../principles/linkstate.rst:104 msgid "" "When a link fails, the two routers attached to the link detect the failure " "by the absence of HELLO messages received during the last :math:`k \\times N`" " seconds. Once a router has detected the failure of one of its local links, " "it generates and floods a new LSP that no longer contains the failed link. " "This new LSP replaces the previous LSP in the network. In practice, the two " "routers attached to a link do not detect this failure exactly at the same " "time. During this period, some links may be announced in only one direction. " "This is illustrated in the figure below. Router `E` has detected the failure " "of link `E-B` and flooded a new LSP, but router `B` has not yet detected " "this failure." msgstr "" #: ../../principles/linkstate.rst:116 msgid "" "When a router has failed, its LSP must be removed from the LSDB of all " "routers [#foverload]_. This can be done by using the `age` field that is " "included in each LSP. The `age` field is used to bound the maximum lifetime " "of a link state packet in the network. When a router generates a LSP, it " "sets its lifetime (usually measured in seconds) in the `age` field. All " "routers regularly decrement the `age` of the LSPs in their LSDB and a LSP is " "discarded once its `age` reaches `0`. Thanks to the `age` field, the LSP " "from a failed router does not remain in the LSDBs forever." msgstr "" #: ../../principles/linkstate.rst:118 msgid "" "To compute its forwarding table, each router computes the spanning tree " "rooted at itself by using Dijkstra's shortest path algorithm [Dijkstra1959]" "_. The forwarding table can be derived automatically from the spanning as " "shown in the figure below." msgstr "" #: ../../principles/linkstate.rst:129 msgid "" "It should be noted that link state routing assumes that all routers in the " "network have enough memory to store the entire LSDB. The routers that do not " "have enough memory to store the entire LSDB cannot participate in link state " "routing. Some link state routing protocols allow routers to report that they " "do not have enough memory and must be removed from the graph by the other " "routers in the network, but this is outside the scope of this e-book." msgstr ""