Agrégation informatique externe 2020, épreuve 2, option ingénierie informatiqueSujet et rapport du jury

• -d'un dossier sujet de la page 2 à la page 24 ;
• -d'un dossier technique de la page 25 à la page 27.

Conseils aux candidats

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Réseau de diffusion de contenu vidéo

Présentation du système

Figure 1 : Trafic agrégé sur l'ensemble des ports réseaux du point d'échange Internet d'Amsterdam (AMS-IX)

Figure 2 : Trafic Internet en France selon l'Arcep en 2017

• -les fournisseurs de contenu et d'application (FCA) : les propriétaires du contenu, qui font appel à plusieurs intermédiaires pour acheminer leur contenu aux utilisateurs finals ;
• -les hébergeurs : les propriétaires des serveurs hébergeant un contenu géré par des tiers (FCA ou individus) ;
• -les transitaires : les gestionnaires des réseaux internationaux qui font office d'intermédiaires entre les FCA et les FAI pour acheminer le trafic ;
• -les points d'échange Internet (IXP - Internet Exchange Point) : les infrastructures qui permettent aux différents acteurs de s'interconnecter directement, via un point d'échange, plutôt que par le biais d'un ou de plusieurs transitaires ;
• -les réseaux de diffusion de contenu (CDN - Content Delivery Network) : les réseaux se spécialisent dans la livraison de volumes de trafic importants vers plusieurs FAI, dans des zones géographiques variées et grâce à des serveurs de cache au plus proche des clients finals ;
• -les fournisseurs d'accès Internet (FAI) : les opérateurs de réseaux qui sont chargés de livrer le trafic au client final ;
• -les clients finals : les individus qui utilisent leurs propres équipements et contractent un abonnement auprès d'un FAI pour accéder à du contenu sur Internet.

Figure 3 : Architecture traditionnelle de distribution de contenu avec un serveur origine (à gauche) et architecture avec un CDN (à droite)

• -contenus statiques : des données qui sont stockées une fois chez les fournisseurs de contenu en lecture seule, puis qui sont distribuées. Cette catégorie comprend par exemple les photos, les livres électroniques, ainsi que certains services de partage de fichiers ;
• -services interactifs : cette catégorie est principalement liée aux services Web qui permettent aux utilisateurs de conserver leurs propres données ou de gérer des transactions en ligne sur Internet. Par exemple, cela inclut les services de sauvegarde et de synchronisation, les services d'annuaire et le commerce électronique ;
• -streaming : les services de streaming utilisent de plus en plus de CDN. II existe une demande croissante pour ce type de contenu avec un niveau d'attentes en matière de qualité de service en augmentation constante, notamment en termes de temps de réponse et de débit. C'est principalement le cas de la diffusion vidéo, notamment de la vidéo à la demande et de la diffusion en direct.

• -il doit faire face à des variations brusques et inattendues de la popularité du contenu qu'il rend accessible aux clients ;
• -il doit éviter de gaspiller des ressources matérielles et réduire autant que possible le stockage et l'utilisation du réseau ;
• -il doit offrir un faible temps de réponse et une disponibilité de bande passante élevée en optimisant son architecture et en employant des techniques autoadaptatives.

Partie 1. Modélisation de la connexion des utilisateurs

Figure 4 : Séquence simplifiée d'échange de paquets pour 2 requêtes client de demande de contenu

• Q1.En supposant que chaque requête et chaque réponse ne requiert qu'un paquet et que le temps de traitement de chaque serveur est négligeable, quelle est la durée totale des échanges représentés dans la figure 4 ?
• Q2.Après la première requête DNS, est-il nécessaire de faire d'autres requêtes DNS pour accéder au contenu fourni par le même FCA ? Justifier.
• Q3.Expliquer pourquoi la requête B nécessite une communication avec le serveur FCA.
• Q4.Quand le CDN communique-t-il avec le DNS ?

• • -une communication entre le serveur CDN et le client implique de traverser k commutateurs ;
  • -toutes les liaisons de données utilisées emploient le même protocole de liaison qui ajoute un en-tête de H bits pour P bits de données utiles dans un paquet ;
  • -toutes les liaisons ont un débit identique de B bps (bit par seconde);
  • -toutes les liaisons ont une latence identique de L secondes (temps que met un bit pour aller d'un équipement à l'autre en empruntant la liaison) ;
  • -les temps de traitement dans les commutateurs et le temps de traitement des accusés de réception sont négligés ;
  • - d désigne le délai inter-trame (temps d'attente entre la fin de l'envoi de la trame précédente et le début de la trame suivante) ;
  • -il n'y a pas de congestion sur les liens.

Figure 5 : Transmission de paquets entre le serveur CDN et le client

• Q5.Calculer la durée d'émission T_p d'un paquet comprenant P données utiles, c'est à dire le temps entre l'émission du premier bit du paquet et l'émission du dernier bit du paquet.
• Q6.En supposant que le dernier paquet a la même taille que les autres, montrer que la durée totale d'émission T_e du fichier pour le serveur CDN (temps entre l'envoi du premier bit par le serveur et l'envoi du dernier bit par le serveur) est égale à :
  T_e = T_p ⋅ ⌈N/P⌉ + d ⋅ (⌈N/P⌉ − 1)
• Q7.Calculer la durée totale nécessaire au transfert du fichier (temps entre l'envoi du premier bit par le serveur et la réception du dernier bit par le client).
• Q8.Calculer le temps nécessaire pour transmettre un fichier de 4 Gigaoctets avec :
  • - k = 25;
  • - L = 2 ms;
  • - B = 10Gbps;
  • - H = 18 octets ;
  • - P = 1500 octets ;
  • - d = 9, 6 ns.

• Q9.Calculer la durée nécessaire pour transmettre le fichier de 4 Go en utilisant des trames plus grandes (jumbo frames) de P = 9000 octets. Justifier le choix d'utiliser ces trames pour la communication entre le serveur FCA et le serveur CDN.
• Q10.Calculer la durée nécessaire pour transmettre le fichier de 4 Go en utilisant k = 10, P = 1500 octets et B = 15Mbps. Commenter sur l'impact de la bande passante disponible dans le cas du transfert entre le serveur CDN et le client.
• Q11.Avec le diagramme de la figure 4 en considérant les durées de transferts calculées dans les questions précédentes, pour la requête B, quelle communication requiert le plus de temps entre les deux communications nécessaires : celle entre le client et le serveur CDN ou celle entre le serveur CDN et le serveur FCA ?

• Q12.Dans le code à trous ci-après qui implémente en Python le côté client du socket, écrire le code qui devrait se trouver en ligne 7 à la place de [...].

import socket # Import du module socket
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) # Création du socket
hote = 'www.monserveur.fr' # Adresse du serveur
port = 8080 # Port sur lequel se connecter
[...]
with open('monfichier', 'wb') as f:
    while True:
        print('Réception des données...')
        donnees = s.recv(1024)
        if not donnees:
            break
        f.write(donnees)
f.close()
print('Successfully get the file')
s.close()
print('connection closed')

import socket # Import module socket
port = 8080 # Port utilisé par le service
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) # Création du socket
hote = socket.gethostname() # Nom de la machine
s.bind((hote, port)) # Bind du socket au port
s.listen(5) # Attente des clients.
while True:
    conn, addr = s.accept() # Etablissement de la connexion avec le client.
    data = conn.recv(1024)
    filename='fichier'
    f = open(filename,'rb')
    1 = f.read(1024)
    [...]
        [...]
        [...]
    f.close()
    conn.close()

• Q14.Dans le code d'établissement du socket entre le client et le serveur, à quel moment a lieu la requête DNS de la figure 4 ?
• Q15.Dans le code Python serveur ci-dessus, le serveur ne peut accepter qu'un seul client. Détailler le mécanisme nécessaire au serveur pour accepter plusieurs connexions simultanées.
• Q16.En considérant les temps d'établissement des connexions et de transferts de fichiers, pour un fichier volumineux tel que celui d'une vidéo (plusieurs Go) et dans des conditions réalistes pour Internet, justifier si c'est la latence ou la bande passante qui a le plus d'impact sur le temps d'acquisition d'une vidéo par un client depuis un CDN.

Partie 2. Modélisation de l'infrastructure du CDN

from collections import defaultdict
class Lgraphe:
    def __init__(self):
        self.noeuds = set()
        self.arretes = defaultdict(list)
        self.latences = {}
    def ajouter_noeud(self, valeur):
        self.noeuds.add(valeur)
    def ajouter_arrete(self, noeud_src, noeud_dst, latence):
        self.arretes[noeud_src].append(noeud_dst)
        self.arretes[noeud_dst].append(noeud_src)
        self.latences[(noeud_src, noeud_dst)] = latence
        self.latences[(noeud_dst, noeud_src)] = latence

h = Lgraphe()
h.ajouter_noeud('a')
h.ajouter_noeud('b')
h.ajouter_noeud('c')
h.ajouter_arrete('a', 'b', 10)
h.ajouter_arrete('b', 'c', 10)
h.ajouter_arrete('a', 'c', 15)

Figure 6 : Exemple de graphe considéré pour la couverture d'un CDN.

Entrées : un graphe G(N,A) et i un nœud de N
P = Ø
d[a] = + > pour chaque nœud a de N
d[i] = 0
while P = (N privé de {i})
    Choisir un nœud a qui est hors de P ayant la plus petite
distance d[a]
    Mettre a dans P
    foreach nœud b qui est hors de P et est voisin de a
        d[b] = min(d[b], d[a]+latence(a,b))
    endfor
endwhile
Sortie : d

{'a': 0, 'b': 1, 'c': 1, 'd': 1, 'e': 1, 'k': 1, 'l': 1, 'n': 1, 'm': 2, 'f': 2, 'g': 2, 'h': 2, 'j': 2, 'i': 3}.

• Q20.Dans l'exemple de la figure 6, pour |S| = 1, quel est le nœud qui minimise la latence moyenne ?
• Q21.Dans l'exemple de la figure 6, pour |S| = 1, quel nœud minimise la pire latence ?
• Q22.Écrire en Python la fonction NoeudMoyen qui prend en entrée un Lgraphe et retourne un nœud du graphe qui minimise L_(moy). Quelle est la complexité de cette fonction en temps de calcul ?

def MaFonction(lgraphe):
    lesnoeuds = {}
    for noeud in lgraphe.noeuds:
        visite = dijsktra(lgraphe, noeud)
        lmax = 0
        for dst in visite:
            if lmax < visite[dst]:
                lmax = visite[dst]
        lesnoeuds[noeud] = lmax
    return min(lesnoeuds, key=lesnoeuds.get)

• Q23.Que renvoie la fonction Python MaFonction donnée ci-avant ? A quoi sert-elle ? Quelle est la complexité de cette fonction en temps de calcul ?
• Q24.Écrire en Python la fonction NoeudsMoyens2 qui prend en entrée un Lgraphe et retourne deux nœuds du graphe ( |S| = 2 ) qui minimisent L_(moy).
• Q25.Quelle est la complexité en temps de calcul dans le cas général de la fonction qui retourne S, un ensemble de nœuds qui minimisent |S| et L_(moy)(S) ? Qu'implique cette complexité en pratique pour de grands graphes ?

Entrées : un graphe G(N,A) et un entier k
S = 0
Choisir arbitrairement un nœud et l'ajouter à S
while |s| < k
    ajouter à S le point le plus éloigné des points de S
endwhile
Sortie : S

Partie 3. Modélisation du flux vidéo

Figure 7 : Courbe de téléchargement d'un fichier vidéo par un client du CDN

Figure 8 : Architecture client-serveur DASH (Dynamic Adaptive Streaming Over HTTP)

• Q33.Quel est l'intérêt de permettre un débit d'émission adaptatif ? Quelle contrainte cela impose sur la taille des segments des différentes résolutions ?
• Q34.Pourquoi le contrôle adaptatif du débit d'émission est-il réalisé par le client ?
• Q35.Quel est l'intérêt de s'appuyer sur le protocole HTTP pour faire du streaming vidéo ?
• Q36.Pourquoi avoir choisi d'utiliser TCP plutôt qu'UDP (User Datagram Protocol) dans l'implémentation de DASH ?
• Q37.Quelles sont les deux métriques sur lesquelles le client peut s'appuyer pour réaliser le contrôle adaptatif du débit d'émission ?
• Q38.Quels sont les deux mécanismes fonctionnant comme des boucles de rétroaction qui permettent de réguler le débit d'émission du serveur en fonction des capacités de téléchargement du client ?

Figure 9 : Exemple pour Netflix de PSNR pour différentes résolutions et débits d'émission

• Q39.Pour l'exemple de la figure 9, expliquer pourquoi le point A qui a une résolution de 1280 × 720 obtient un moins bon PSNR que le point B qui a une résolution de 720 × 480 pour le même débit d'émission. Qu'est-ce que cela implique sur le choix de la meilleure résolution possible ?
• Q40.Pour l'exemple de la figure 9, citer une méthode permettant de déterminer la courbe de meilleur débit-distorsion.
• Q41.En plus du débit, quel autre paramètre permet de déterminer la résolution la plus adaptée pour le streaming d'un flux vidéo pour un client donné ?
• Q42.Pour la figure 9, expliquer pourquoi cette courbe de meilleur débit-distorsion est différente pour chaque vidéo. Est-il envisageable de calculer cette courbe pour toutes les vidéos hébergées par le CDN ?
• Q43.Dans ce système, quelle méthode permettrait de construire rapidement la courbe de meilleur débit-distorsion sans calculer la distorsion induite par chaque résolution à chaque débit possible ?
• Q44.Pour l'exemple de la figure 9, considérant que tous les formats disponibles fournis par le CDN pour une vidéo donnée sont représentés sur la figure, combien d'exemplaires différents de la vidéo sont stockés par le CDN ? Donnez deux raisons pour lesquelles chaque exemplaire n'est pas calculé à la volée (ou à la demande du client) à partir de la vidéo originale.

• Q45.Considérant une vidéo avec une résolution de 1920 × 1080 pixels avec 24 images par seconde (format 1080p) et chaque pixel encodé sur 24 bits, quel débit théorique faudrait-il pour la diffuser telle quelle ? Comparer avec les débits offerts sur l'exemple de la figure 9 pour la même résolution de vidéo et donner deux raisons pour expliquer la différence observée entre le débit théorique calculé et les débits représentés sur la figure 9.

• • -les vidéos proposées par les fournisseurs de contenu (FCA) ont toutes une durée identique ;
  • -une fois encodées dans les représentations souhaitées, elles occupent la même taille d'espace disque ;
  • -le FCA propose 100000 vidéos qui nécessitent chacune 8 Go de disque pour être stockées (ces 8 Go incluent toutes les représentations souhaitées pour une même vidéo) ;
  • -le CDN dispose de 10 emplacements géographiquement distants qui contiennent les serveurs utilisés pour diffuser ces 100000 vidéos ;
  • -chaque emplacement a la même capacité en terme de stockage et de serveurs ;
  • -chaque emplacement stocke au maximum un exemplaire de toutes les représentations d'une vidéo.
• Q46.Expliquer pourquoi le CDN doit placer plus de 80 To de stockage dans chaque emplacement pour diffuser ces vidéos à l'ensemble des clients. Dans le même contexte, expliquer pourquoi le CDN place probablement moins de 800 To de stockage dans chaque emplacement.

Partie 4. Modélisation de la consommation énergétique

• • -une partie fixe, qui correspond à l'énergie consommée par l'équipement lorsqu'il est sous tension, mais ne fait rien (pas de calcul ni de transfert de donnée par exemple) ;
  • -une partie dynamique, qui correspond à l'énergie supplémentaire (c'est-à-dire en plus de la partie fixe) qui dépend des tâches effectuées par l'équipement.

Figure 10 : Consommation énergétique utile pour le visionnage sur poste client d'une vidéo

• Q49.En utilisant la relation ci-avant, calculer l'énergie dépensée par la box pour le visionnage d'une vidéo de 1 Go en supposant un débit utile parfait de 10 Mbps, c'està-dire sans considérer les bits ajoutés par les protocoles réseau et en supposant qu'il n'y a pas de perte de paquet ni de congestion. Noter cette valeur E_(box.)
• Q50.En utilisant la relation précédente, calculer la partie dynamique de la consommation de la box pour le visionnage d'une vidéo de 1 Go avec un débit utile parfait de 10 Mbps. Noter cette valeur E_(box-dynamique). Quelle hypothèse est faite si uniquement cette partie dynamique de la consommation de la box est considérée pour modéliser l'impact du visionnage d'une vidéo ?

Figure 11 : Consommation énergétique d'un serveur diffusant des vidéos

• Q51.En supposant que le serveur est toujours chargé à son maximum et en utilisant la relation précédente, quelle est sa consommation énergétique pour diffuser 1 Go de vidéo ? Noter cette valeur E_(serveur).

• -au système de refroidissement du centre, nécessaire à cause de la dissipation de chaleur des serveurs ;
• -aux installations électriques, batteries et systèmes de secours (tels que des groupes électrogènes) utilisés pour éviter les coupures d'électricité en cas de panne d'alimentation ;
• -aux équipements informatiques (serveurs et équipements réseau) ;
• -aux installations du centre, telles que l'éclairage par exemple.

• Q55.En supposant que ce stockage est utilisé à pleine capacité, en utilisant une modélisation de la consommation énergétique proportionnelle à la taille de stockage, quelle part d'énergie est consommée pour 1 Go de données ? Noter cette valeur E_(stockage). Du point de vue de la consommation énergétique du système global (incluant le CDN et le réseau FAI), citer une condition nécessaire pour que l'utilisation d'un CDN soit plus avantageuse qu'un unique centre de calcul centralisé hébergeant toutes les vidéos et donc avec une distance moyenne en nombre de routeurs plus grande par rapport à un CDN.

Partie 5. Synthèse

Figure 12 : Consommation énergétique d'une vidéo en streaming ou sur DVD commandé en ligne

• Q56.En utilisant les valeurs E_(routeur), E_(stockage), E_(serveur-environné), E_(box) calculées dans la partie précédente, les facteurs de réplication moyen et de redondance moyenne, en supposant qu'il y a 4 routeurs entre la box et le serveur CDN, calculer le pourcentage représenté par chaque partie (box, routeurs, serveurs et stockage) dans la consommation énergétique totale pour diffuser 1 Go de vidéo à un client. Comparer ces pourcentages avec les proportions présentées sur la figure 12 pour les cas de streaming.
• Q57.Avec l'hypothèse du second scénario de streaming, conformément à la figure 12, en passant du DVD au streaming, la consommation énergétique globale de la vidéo estelle réduite ? Quel facteur principal fait qu'au cours des dernières années, la consommation énergétique mondiale due à la vidéo a augmenté malgré les progrès liés à l'efficacité énergétique des équipements informatiques ?

• -Amsterdam Internet exchange point : https://www.ams-ix.net/ams
• -« L'état d'Internet en France », rapport d'activité, tome 3, ARCEP, juin 2018.
• -Guthemberg Da Silva Silvestre. « Designing Adaptive Replication Schemes for Efficient Content Delivery in Edge Networks », thèse de doctorat de l'Université Pierre et Marie Curie - Paris VI, 2013.
• -«Open Connect Everywhere: A Glimpse at the Internet Ecosystem through the Lens of the Netflix CDN », T. Böttger, F. Cuadrado, G. Tyson, I. Castro et S. Uhlig, SIGCOMM Comput. Commun. Rev. 48, 1, pages 28-34, avril 2018.
• -« The environmental footprint of a distributed cloud storage », Lorenzo Posani, rapport, mars 2018.
• -« Client-Side Energy Costs of Video Streaming », O. Ejembi et S. N. Bhatti, IEEE International Conference on Data Science and Data Intensive Systems, pages 252-259, 2015.
• -« Complexity-based consistent-quality encoding in the cloud », J. De Cock, Z. Li, M. Manohara and A. Aaron, IEEE International Conference on Image Processing, pages 1484-1488, 2016.
• -« A Survey of Rate Adaptation Techniques for Dynamic Adaptive Streaming Over HTTP », J. Kua, G. Armitage and P. Branch, IEEE Communications Surveys & Tutorials, vol. 19, no. 3, pages 1842-1866, 2017.
• -« Greening the Internet with Nano Data Centers », V. Valancius, N. Laoutaris, L. Massoulié, C. Diot, et P. Rodriguez, ACM international conference on emerging networking experiments and technologies, pages 37-48, 2009.
• -« Shipping to streaming: is this shift green? », A. Seetharam, M. Somasundaram, D. Towsley, J. Kurose et P. Shenoy, ACM SIGCOMM workshop on Green networking, pages 61-68, 2010.
• -« The controller placement problem », B. Heller, R. Sherwood et N. McKeown, workshop on Hot topics in software defined networks, pages 7-12, 2012.

Document technique DT1

Méthodes et fonctions de manipulation d'objets conteneurs standard de Python

Fonctions natives

Méthodes des objets de type liste

Document technique DT1 (Suite)

a = {}
a["nom"] = "engel"
a["prenom"] = "olivier"
## a contient alors {'nom': 'engel', 'prenom': 'olivier'}

dict.get()

data = {"name": "Olivier", "age": 30}
a = data.get("name")
## a contient : 'Olivier'
A = data.get("adresse", "Adresse inconnue")
## a contient : 'Adresse inconnue'

dict.keys()

dict = {'Name': 'Zara', 'Age': 7}
    print ("Valeurs : %s" % dict.items())

Document technique DT2