English French
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. 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.
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. 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.
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. 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.
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.
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.
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.
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.
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.
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. 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.
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. 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.
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.
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.
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`.
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.
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.
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.
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. 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.
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.
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 :
There are two possible organizations for the network layer : Il y a deux organisations possibles pour la couche réseau :