Παραγωγή, μορφοποίηση και έλεγχος κίνησης σε δίκτυα IP με χρήση προγραμματιζόμενης μονάδας χρονισμού

Abstract

The nodes of modern packet-switched networks are called to support increasingly complicated functions that depart from the traditional store and forward ones. In this regime, there is a need for modular architecture of the hardware that supports dynamic reconfiguration according to the selected control functions. Timing units constitute a basic block of most traffic control functions at the packet level, while at the same time they provide the foundations for the implementation of accurate and efficient traffic generation tools. In this context, this Ph.D. thesis focuses on the design, implementation and evaluation of an external to the host processor timing and silence-enforcement unit, implemented in hardware. This unit is associated with a control and algorithm-execution module (implemented in software) and is capable of supporting shaping, traffic control and traffic generation in IP networks. The advantages of the proposed architecture are illustrated through experiments in a real laboratory-based network. The design philosophy behind the timing unit is based on the need for modular implementation of the timers and counters, in a way that permits their dynamic reconfiguration. The timing and silence-enforcement unit comprises a bank of timers and counters, is implemented in FPGA logic and is placed on a PC ISA card. The unit is capable of supporting a number of flows, either aggregate or individual, with different demands for timing resolution. The proposed timing module allows for dynamic reconfiguration in run time; by this means it adapts to the changing network dynamics. Its design principles follow the demands posed by the functions of traffic shaping, policing and charging in packet networks. Nevertheless, a great part of the thesis is devoted to traffic generation because not only this function does exploit efficiently the presence of an accurate and flexible timing unit, but also it constitutes a precondition for the experimental evaluation of traffic control mechanisms. As far as traffic generation itself is concerned, the exploitation of the timing and silence- enforcement unit provides the implementation with the ability to schedule the packet transmissions accurately, without relying on the timers of the operating system. The architecture of the traffic generator is accompanied by the software that interfaces with the timing unit and by an efficient implementation for UDP packet generation and transmission. These tasks are executed in the kernel space of the Linux operating system. Apart from the traffic generation, the thesis also focuses on traffic analysis tools. In this context, our work illustrates an implementation that is based on an external to the host processor timing unit that is capable of providing great accuracy (within a few microseconds) in measurements of the one-way packet delay in small experimental networks. As far as the traffic control is concerned, each controlled flow is subjected to shaping, policing (and consequently marking or dropping) and charging, independent of the others, according to the corresponding algorithms that are supported by the design. For this purpose, the timing unit interacts with an algorithm execution module implemented in embedded software that provides the overall architecture with better control and greater programming flexibility. The shaping algorithm that is studied in depth provides quantitative quality-of-service guarantees of statistical nature, and is based on the fact that in the presence of a large number of shaped streams, the linear multiplexer is acting like an M/GI/1 queueing system. The shaping law enforces data spacing according to a predetermined effective rate. Charging is based on a scheme that takes into account the duration of the flow, the effective rate commitment, as well as the degree of the effective bandwidth utilization. The experimental evaluation of the shaping law and its implementation is done for traffic with statistical properties and for traffic that corresponds to real MPEG-4 sources corresponding to real time streaming applications. The increased transmission delay introduced by the shaper can be counterbalanced either by rate adaptation or by controlled packet losses. Towards this direction, apart from studying the effects of the delay that is introduced by the shaper (and the experimental evaluation of a rate adaptive scheme that is based on a queue length average), our work also focuses on the effects of losses to the quality of the observed image at the receiver’s side. The experiments evaluate packet drops by internal nodes of the network that embody active queue management and congestion avoidance schemes (e.g. RED and WRED). The evaluation of the effectiveness of such schemes is done according to a performance metric that takes into account the distribution of the losses of different types of frames of simple-profile MPEG-4 video flows.

Οι αυξανόμενες απαιτήσεις από τους κόμβους μεταγωγής και δρομολόγησης των δικτύων υψηλών ταχυτήτων απαιτούν αρθρωτή αρχιτεκτονική του υλικού και ικανότητα για δυναμική προσαρμογή αυτού και των αντίστοιχων λειτουργιών ελέγχου. Οι μονάδες χρονισμού αποτελούν βασικό δομικό στοιχείο των περισσότερων λειτουργιών ελέγχου κίνησης σε επίπεδο πακέτων παράλληλα παρέχουν τη βάση για την υλοποίηση αποδοτικών εργαλείων παραγωγής κίνησης. Στα πλαίσια αυτά, η παρούσα διδακτορική διατριβή επικεντρώνεται στην μελέτη, υλοποίηση και αξιοποίηση, εξωτερικής ως προς τον κεντρικό επεξεργαστή του κόμβου, μονάδας χρονισμού και επιβολής καθυστέρησης, υλοποιημένης σε υλικό, η οποία συνεπικουρούμενη από μια μονάδα ελέγχου και εκτέλεσης αλγορίθμων (υλοποιημένη σε λογισμικό), είναι ικανή να υποστηρίξει λειτουργίες μορφοποίησης, ελέγχου και παραγωγής κίνησης σε δίκτυα IP. Τα πλεονεκτήματα της προτεινόμενης αρχιτεκτονικής αναδεικνύονται μέσα από πειράματα σε πραγματικό εργαστηριακό δίκτυο. Η προσέγγιση για την μονάδα χρονισμού υποδηλώνεται κυρίως από την ανάγκη για αρθρωτή υλοποίηση των χρονιστών, με τρόπο που να επιτρέπει την δυναμική τους διαμόρφωση. Η μονάδα χρονισμού και επιβολής σιωπής αποτελούμενη από ομάδες χρονιστών-μετρητών και υλοποιούμενη σε πειραματική κάρτα επέκτασης ISA είναι ικανή να υποστηρίξει, ταυτόχρονα, ροές (είτε αθροιστικές είτε ανεξάρτητες) με διαφορετικές απαιτήσεις χρονικής ανάλυσης (ακρίβειας). Η προτεινόμενη μονάδα χρονισμού επιδέχεται επαναπρογραμματισμό στο χρόνο εκτέλεσης (run-time)· με τον τρόπο αυτό προσαρμόζεται στις αλλαγές της δυναμικής του δικτύου. Ο σχεδιασμός της βασίζεται κατά κύριο λόγο στις απαιτήσεις που θέτουν οι λειτουργίες της μορφοποίησης, της αστυνόμευσης και της χρέωσης στα δίκτυα πακέτων. Ωστόσο, η διατριβή πραγματεύεται παράλληλα (σε ότι αφορά ένα μεγάλο μέρος της) και θέματα που άπτονται της παραγωγής κίνησης, διότι αφενός και η λειτουργία αυτή εκμεταλλεύεται αποδοτικά την ύπαρξη μιας ευέλικτης και ακριβούς μονάδας χρονισμού και επιβολής καθυστέρησης, και αφετέρου αποτελεί προαπαιτούμενο στοιχείο για την πειραματική αξιολόγηση των μηχανισμών ελέγχου κίνησης. Στα πλαίσια αυτά της παραγωγής κίνησης, η εκμετάλλευση των μονάδων χρονισμού και επιβολής καθυστέρησης παρέχει στην υλοποίηση μεγάλη ακρίβεια χρονοπρογραμματισμού των διεργασιών εκπομπής πακέτων, αποδεσμεύοντας αυτές από τον χρονιστή του λειτουργικού συστήματος. Η αρχιτεκτονική της γεννήτριας κίνησης υψηλού επιπέδου συνοδεύεται από το λογισμικό διεπαφής με την μονάδα χρονισμού και από αποδοτικές υλοποιήσεις για δημιουργία και αποστολή πακέτων UDP σε επίπεδο πυρήνα του λειτουργικού συστήματος Linux. Παράλληλα, μελετάται η ανάλυση κίνησης και παρουσιάζεται μια υλοποίηση που βασίζεται στην ύπαρξη εξωτερικής προς τον φιλοξενούντα κόμβο μονάδας χρόνου, ικανής να παρέχει με μεγάλη ακρίβεια (εντός μερικών μικροδευτερολέπτων) μετρήσεις απόλυτης καθυστέρησης από άκρο σε άκρο σε ένα μικρό πειραματικό δίκτυο. Όσον αφορά στον έλεγχο κίνησης, κάθε ελεγχόμενη ροή μπορεί να υπόκειται σε μορφοποίηση, αστυνόμευση (και κατά συνέπεια σε σήμανση ή απόρριψη) και χρέωση, ανεξάρτητα από τις άλλες, σύμφωνα με τους αλγόριθμους που υποστηρίζονται από τη σχεδίαση. Για το σκοπό αυτό η μονάδα χρονισμού περιβάλλεται από μια μονάδα εκτέλεσης αλγόριθμων σε ενσωματωμένο λογισμικό, η οποία προσφέρει στην συνολική αρχιτεκτονική καλύτερο έλεγχο και μεγαλύτερη προγραμματιστική ευελιξία. Ο αλγόριθμος μορφοποίησης που μελετάται εκτενώς παρέχει ποσοτικές εγγυήσεις ποιότητας υπηρεσίας στατιστικής φύσης και βασίζεται στην θεώρηση του πολυπλέκτη ως ένα αναμονητικό σύστημα M/GI/L εφαρμόζει δε αραίωση στα μεταδιδόμενα πακέτα με ταυτόχρονη επιβολή ενεργού ρυθμού. Η χρέωση βασίζεται σε ένα σχήμα το οποίο λαμβάνει υπόψη τη διάρκεια μιας ροής, τη δέσμευση εύρους ζώνης (ενεργού ρυθμού) καθώς και το βαθμό χρησιμοποίησης του δεσμευμένου αυτού εύρους ζώνης. Η πειραματική αξιολόγηση του αλγόριθμου μορφοποίησης γίνεται τόσο για τεχνητή κίνηση όσο και για κίνηση που προέρχεται από εφαρμογές video MPEG-4 πραγματικού χρόνου. Εξισορρόπηση της αυξημένης καθυστέρησης που εισάγει η μορφοποίηση μπορεί να γίνει είτε μέσω προσαρμογής του ρυθμού του μορφοποιητή είτε μέσω ελεγχόμενων απορρίψεων. Προς την κατεύθυνση αυτή, πέρα από την μελέτη της επίδρασης της καθυστέρησης που εισάγει ο μορφοποιητής (και την πειραματική αξιολόγηση ενός σχήματος προσαρμογής του ρυθμού αυτού), μέρος της διδακτορικής διατριβής αφιερώνεται και στην μελέτη της επίδρασης των απωλειών στην ποιότητα της λαμβανόμενης εικόνας. Τα πειράματα αξιολογούν την απόρριψη πακέτων από κόμβους του δικτύου, οι οποίοι εφαρμόζουν ενεργά σχήματα διαχείρισης ουρών και αποφυγής συμφόρησης (π.χ. RED και WRED). Η αποτίμηση της αποτελεσματικότητας των μηχανισμών αυτών γίνεται με βάση ένα μέτρο επίδοσης το οποίο βασίζεται στην κατανομή των απωλειών πλαισίων διαφορετικής κωδικοποίησης ροών video MPEG-4.