Sliding Window Protocol

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Το Πρωτόκολλο Συρόμενου Παραθύρου (Sliding Window Protocol, SWP) είναι ένα αξιόπιστο και αποτελεσματικό[1] πρωτόκολλο μετάδοσης δεδομένων. Στο μοντέλο OSI ανήκει στο στρώμα διασύνδεσης δεδομένων (datalink layer)[2]. Το συρόμενο παράθυρο χρησιμοποιείται στα περισσότερα connection oriented πρωτόκολλα δικτύου, ανάμεσα σε άλλα στο Point-to-Point protocol (PPP) και στο TCP[3]. Ωστόσο, η δημιουργία σύνδεσης δεν είναι μέρος πρωτοκόλου[1]. Παρέχει full-duplex επικοινωνία και χρησιμοποιείται έλεγχο ροής (flow control). Το όνομα του περιγράφει το παράθυρο αναγνώρισης που χρησιμοποιείται, το οποίο μοιάζει να "γλιστράει" καθώς προχωράει μεταδίδοντας νέα δεδομένα.

Γενική περιγραφή[Επεξεργασία | επεξεργασία κώδικα]

Η βασική ιδέα στο πρωτόκολλο συρόμενου παραθύρου είναι ότι τόσο ο αποστολέας όσο και ο παραλήπτης διατηρούν ένα παράθυρο αναγνώρισης (acknowledgement). Σε κάθε πλευρά του είναι ενεργή μια διεργασία η οποία αναλαμβάνει τη σωστή μετάδοση. Περιλαμβάνει δύο μέρη, ένα το οποίο στέλνει εξερχόμενα δεδομένα και ένα το οποίο διαχειρίζεται τα εισερχόμενα. Με τον τρόπο αυτό παρέχεται full-duplex μετάδοση, καθώς ο κάθε host μπορεί να είναι ταυτόχρονα αποστολέας και παραλήπτης[1][3].

Το πρωτόκολλο είναι ικανό να θυμάται τα πακέτα που έχουν αναγνωρισθεί. Για κάθε μη-αναγνωρισμένο πακέτο χρησιμοποιείται ξεχωριστός χρονομετρητής και αν ο προκαθορισμένος χρόνος λήξει (π.χ. το πακέτο χαθεί) ο αποστολέας ξαναστέλνει τα δεδομένα. Το παράθυρο μετακινείται πέρα από όλα τα ήδη αναγνωρισμένα πακέτα, όταν ο αποστολέας επαναρυθμίζει τη θέση του. Στην πλευρά του παραλήπτη, όταν γίνει λήψη όλων των αναμενόμενων πακέτων το παράθυρο προχωράει[4]. Το παράθυρο επομένως χωρίζει την ακολουθία των πακέτων σε

  • αναγνωρισμένα, τα οποία έχουν αποσταλεί επιτυχώς,
  • πακέτα εντός του παραθύρου τα οποία μεταδίδονται και
  • μη απεσταλμένα πακέτα εκτός του παραθύρου.

Παραλλαγές λειτουργίας[Επεξεργασία | επεξεργασία κώδικα]

Sliding window colormap.png

Stop-And-Wait[Επεξεργασία | επεξεργασία κώδικα]

Καλείται επίσης και One Bit Sliding Window Protocol. Σε αυτό το πρωτόκολλο το πλαίσιο που αποστέλεται έχει μοναδιαίο μήκος (1). Επομένως είναι απαραίτητη η αναγνώριση κάθε πακέτου πριν να αποσταλεί το επόμενο, από όπου προέρχεται και το όνομά του, που σημαίνει "σταμάτησε και περίμενε".

Το πρωτόκολλο Stop-And-Wait είναι εξαιρετικά αργό και αναποτελεσματικό. Κάθε στιγμή μπορεί να μεταδίδεται μόνο ένα πακέτο και ο αποστολέας περιμένει τουλάχιστον ένα χρόνο απόκρισης (round trip time) πριν να στείλει το επόμενο.

Go-Back-Ν[Επεξεργασία | επεξεργασία κώδικα]

Go-Back-N

Ο αποστολέας δεν μπορεί να διοχετεύει περισσότερα από N πακέτα στον αγωγό (pipeline)[5]. Αν κάποιο πακέτο με αριθμό ακολουθίας k λείπει, ο παραλήπτης απορρίπτει όλα όσα το ακολουθούν και δεν στέλνει αναγνώριση για τα πακέτα με αριθμό ακολουθίας k+1, k+2, κλπ. Με τον τρόπο αυτό ο αποστολέας αναγκάζεται να ξαναστείλει όλα τα πακέτα από το k και ύστερα.

Θεωρώντας ως βάση τον αριθμό ακολουθίας του παλαιότερου μη-αναγνωρισμένου πακέτου και λαμβάνοντας υπόψιν το επόμενο πακέτο (με αριθμό ακολουθίας k+1), έχει νόημα ο ορισμός των παρακάτω διαστημάτων:

  • [0, βάση-1], απεσταλμένα και αναγνωρισμένα
  • [βάση, επόμενο-1], απεσταλμένα, μη-αναγνωρισμένα
  • [επόμενο, βάση+N-1], αριθμοί ακολουθίας (sequence numbers) που μπορούν να χρησιμοποιηθούν για νέα πακέτα και
  • πακέτα με αριθμό ≥ βάση+N, δε μπορούν να χρησιμοποιηθούν μέχρι να αναγνωριστεί η βάση.

Selective Repeat[Επεξεργασία | επεξεργασία κώδικα]

Επιλεκτική επανάληψη (selective repeat)

Ένας άλλος τρόπος είναι να μεταδίδονται ξανά μόνο τα πακέτα που έχουν χαθεί ή καταστραφεί. Ο παραλήπτης χρησιμοποιεί buffer για όλα τα πακέτα που φτάνουν μετά από κάποιο μη-αναγνωρισμένο. Όταν ο αποστολέας τελικά αντιληφθεί το πρόβλημα με τη λήξη του προκαθορισμένου χρόνου στο χρονομετρητή ξαναστέλνει το πακέτο. Τα πακέτα επομένως μπορούν να φτάνουν εκτός σειράς. Ωστόσο, στο αμέσως ανώτερο στρώμα του OSI layer, το στρώμα δικτύου (network layer), τα πακέτα διοχετεύονται πάντα σε σειρά[2].

Έλεγχος Ροής[Επεξεργασία | επεξεργασία κώδικα]

Ο αλγόριθμος που χρησιμοποιείται στο πρωτόκολλο συρόμενου παραθύρου έχει σημαντικό ρόλο στον έλεγχο ροής (flow control). Συνήθως το πρωτόκολλο υλοποιείται με τρόπο τέτοιο ώστε ο παραλήπτης όχι μόνο στέλνει αναγνώριση των πακέτων που έχει λάβει, αλλά και ενημερώνει τον αποστολέα για το πλήθος των πακέτων που μπορεί να δεχτεί στη συνέχεια. Ο αριθμός των πακέτων που μπορεί να δεχτεί ο παραλήπτης αντιστοιχεί στον ελεύθερο χώρο που υπάρχει στο buffer. Καθώς ο buffer του παραλήπτη γεμίζει, ανακοινώνει μικρότερο μέγεθος παραθύρου στον αποστολέα. Αντιθέτως όταν απελευθερώνεται χώρος ενημερώνει για μεγαλύτερο μέγεθος παραθύρου. Όπως και στη διανομή πακέτων σε σειρά, πρέπει να είναι απαραίτητος ο έλεγχος ροής πριν να υλοποιηθεί στο πρωτόκολλο συρόμενου παραθύρου[6]. Ο μηχανισμός χρησιμοποιείται ιδιαίτερα στο πρωτόκολλο TCP[3].

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

  1. 1,0 1,1 1,2 S. Mauw, G. J. Veltink, Algebraic Specification of Communication Protocols, Cambridge University Press, 1993, Chapter 4, "Sliding window protocols" by J J Brynekreef, ISBN 0-521-41883-6
  2. 2,0 2,1 Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, 2002, σελ. 211, ISBN 0-13-066102-3
  3. 3,0 3,1 3,2 Michael A. Gallo, Bill Hancock, Networking Explained, Digital Press, 2001, σελ. 196, ISBN 1-55558-252-4
  4. Douglas E. Comer, Internetworking with TCP/IP: Principles, Protocols and Architectures, Pearson Prentice Hall, 2005, σελ 193, ISBN 0-13-187671-6
  5. Michael Maher, Logic Programming:Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming, MIT Press, 1996, σελ. 173, ISBN 0-262-63173-3
  6. Larry L. Peterson, Bruce S. Davie, Computer Networks: A Systems Approach, Morgan Kaufmann, 2003, σελ. 110, ISBN 1-55860-832-X

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

  • Sliding Window Demo — Επίδειξη του τρόπου με τον οποίο λειτουργεί το sliding window