Quality of Service (QoS)

Inhalt

QoS im CSN

QoS im CSN

Chemnitzer Studentennetz (CSN)

• Initiative von Studenten für Studenten
• Ziel: Anschluss der privaten Wohnheim-Rechner an Campusnetz
• Anfänge reichen zurück bis ins Jahr 1994

• derzeit etwa 1700 Nutzer
• alle Wohnheime sind angeschlossen
• eines der größten Studentennetze

QoS im CSN

Netztopologie CSN

QoS im CSN

Motivation

• Transfervolumen 3000 GByte/Monat (jetzt 6000)
• jährlich 550.000 DM
• nächste Kategorie 200.000 DM teurer
• bei Überschreitung Mahnungen und Bandbreitenbeschränkung

• Idee: Traffic-Limit für Nutzer
• bei Überschreitung erst Verwarnung, dann Sperrung
• Probleme bei notwendigen größeren Datenmengen
• Ausnutzung des Limits bei Ablauf der Gültigkeitsfrist
• "unfreundlicher Akt" und Beschneidung der persönlichen Freiheit

• Ausweg: intelligenteres Bandbreiten-Management

QoS im CSN

Prinzipielle Funktionsweise

• Nutzer nach Trafficmenge in Gruppen eingeteilt
• mehr Traffic -> schlechtere Gruppe mit weniger Bandbreite
• schrittweise wieder besserer Gruppe zugewiesen
• Vorteil: geringerer Verwaltungsaufwand
• keine Verwarnungen/Sperrungen mehr

• Bandbreitenbeschränkungen auf dem CSN-Server eingesetzt
• Parameter der Gruppen über Webinterface einstellbar
• automatische Regelung der Bandbreiten
• Ausnahmeregelungen: WWW- und FTP-Server der TU, News
• Webinterface für Nutzer, E-Mail bei Einordnung

QoS im CSN

Einordnung in eine Gruppe

QoS im CSN

Automatische Regelung

• optimale Ausnutzung des Monatslimits
• keine Überschreitung
• bisher verursachter Traffic (T) auf Monat hochgerechnet (Tm)
• Monatslimit (Lm) überstiegen/unterschritten -> Bandbreiten angepasst
• ersten 5 Tage und Korrekturfaktoren nahe 1 ausgenommen
• Bandbreite hoch genug -> vom Shaping ausgenommen

Tm = T * Dm / D
                         Lm
Tm > Lm:  Bneu = Balt * ----  ____
                         Tm  /
                        _   / Lm
Tm < Lm:  Bneu = Balt *  | / ----
                         |/   Tm

QoS im CSN

Architektur des Systems

QoS im CSN

Warum XML-RPC?

• Remote-Procedure-Call-Protokoll
• Übertragungsprotokoll HTTP, Payload XML

• einfach zu verstehen und einfach zu implementieren
• Sprachunabhängigkeit
• strukturierte Daten (einfache Datentypen + Felder und Tupel)
• Daten zentral verwaltbar
• Programme verteilbar

Was ist QoS?

Was ist QoS?

Szenario

• bisher Best-Effort-Service
• heutzutage sehr starke Nutzung
• Bandbreiten- und Latenzzeitforderungen kaum erfüllbar

Anforderungen

• kurze Antwortzeiten für Management-Daten
• stabile Bandbreite für Videodaten
• keine Behinderung geschäftskritischer Anwendungen

Was ist QoS?

Quality of Service (QoS)

• Unterscheidung von Verkehrsklassen und Services
• unterschiedliche Behandlung

Quality

• bestimmte qualitative Parameter garantiert
• verlässliche Datenlieferung, garantierte Bandbreiten, minimale Verzögerung
• bevorzugte Behandlung von Management-Daten

Service

• verschiedene Arten von Anwendungen / Protokollen: Classes of Service (CoS)
• E-Mail, WWW, Chat, Videoströme; TCP, IP, IPX
• Klassifikation anhand Protokoll, Quell-/Zieladresse, Port

Was ist QoS?

Probleme bei der Umsetzung von QoS

• Netzwerkcharakteristiken müssen vorhersagbar bleiben
• z.B. Round-Trip Time -> wichtig für TCP-Timeouts
• Filtering bevorzugt an Endpunkten
• aber: dadurch leicht manipulierbar

• sehr eng mit Routing verbunden (z.B. QoSR)
• aber: lastabhängiges Routing noch sehr unausgereift
• Problem wegen Asymmetrie (Hin- und Rückweg)

• QoS-Maßnahmen meist nur in Überlastsituationen bemerkbar
• eher "Versicherung gegen Netzengpässe"
• Aufwand für Netzbetreiber, Folgen schwer vorhersehbar
• Messungen verfälschen Ergebnis zusätzlich

Herangehensweisen

Herangehensweisen

Integrated Services (IntServ)

• ähnliche Bedeutung wie bei ATM
• genaue Definition der Services

Schlüsselkomponenten

• Application Service (End-To-End Ansprüche)
• Router Scheduling (Informationen für Router)
• Router Validation (stehen Services zur Verfügung?)
• Resource-Sharing-Anforderungen (Link-Sharings)
• Usage Feedback (Accounting)
• Dynamische QoS-Anforderungen (RSVP)

Herangehensweisen

Differentiated Services (DiffServ)

• verschiedene Serviceklassen / Output Queues
• durch unterschiedliche Queuing Disciplines behandelbar
• Festlegung der Parameter an den Endpunkten oder beim Provider
• Klassifizierung im TOS-Byte mitgeführt (DSCP)
• Vorteil: skaliert besser als IntServ
• Nachteil: statisches Setup, kein RSVP

Grundlegende Serviceklassen

• Assured Forwarding (AF)
• Expedited Forwarding (EF)
• Best Effort (BE) bzw. Default (DE)

Grundlegende Verfahren

Grundlegende Verfahren

Admission Control

• welcher Traffic ist erlaubt
• Festlegung über Policies

• passive Admission Control: Endpunkte legen Policies fest
• aktive Admission Control: Ingress-Router legt Policies fest

Grundlegende Verfahren

Traffic Shaping

• Menge und Rate des Datenverkehrs kontrollieren
• Ziel: Anschein von vorhersagbarem Verhalten

Leaky Bucket

• Traffic-Bursts gepuffert und in konstanten Raten abgegeben
• wenn Puffer überläuft, neue Pakete gedroppt
• Nachteil: bei genügend Bandbreite Verkehr unnötig eingeschränkt

Token Bucket

• Bucket in bestimmten Abständen mit Tokens versorgt
• repräsentieren gewisse Menge von Datenbytes
• Daten nur bei genügend Tokens sendbar, Bursts möglich

Grundlegende Verfahren

Preferential Queuing

Priority Queuing

• hochpriorisierte Pakete vor anderen in Queue eingeordnet
• langsamer als FIFO (Analyse, Umordnung), unfair

Weighted Fair Queuing (WFQ)

• Traffic mit niedriger Datenmenge bevorzugt behandelt

Stochastic Fair Queuing (SFQ)

• Hashbildung über Quell- und Zieladresse -> Queues -> Round Robin
• Alternative: Weighted Round Robin (WRR)

Class-Based Queuing (CBQ)

• Bandbreite hierarchisch (Baum) auf Klassen verteilt, borgbar
• Fairness: jede Klasse behandelt, auch niedrigpriorisierte
• Alternative: Hierarchical Token Bucket (HTB)

Grundlegende Verfahren

TCP-Mechanismen

Random Early Detection/Drop (RED)

• Unterstützung der TCP-Flusskontrolle
• abhängig vom Füllstand der Queue Wegwerfen von Paketen
• TCP-Flows zu verschiedenen Zeitpunkten langsamer, Überlastung verhindert
• Problem: UDP (Multimedia!) nicht erfasst

Weighted RED (WRED)

• Dropwahrscheinlichkeit von Priorität abhängig
• Token-Bucket-Schwellen (Tresholds)
• überschritten -> niedrigere Priorität (Treshold Triggering)

Generalized RED (GRED)

• Drop-Precedences und -Wahrscheinlichkeiten pro Queue

QoS in Linux

QoS in Linux

• ab Kernel 2.2 QoS unterstützt
• zum Management Kommandozeilen-Tool tc
• Support im Kernel aktivieren (Networking Options ---> QoS and/or fair queueing)
• benötigte Algorithmen als Modul oder fest einkompiliert
• Module explizit laden

modprobe sch_qdisc
modprobe cls_classifier

QoS in Linux

Zuweisung der Queuing Discipline

• Queuing Discipline (QDisc) an Netzinterface binden

Unterstützte QDiscs (Auswahl)

• CBQ, CSZ (currently broken)
• PFIFO und BFIFO, PRIO
• RED und GRED
• SFQ, TBF
• DSMARK, TEQL
• HTB und WRR patchbar

tc qdisc add dev eth0 root handle 1: cbq bandwidth 100MBit avpkt 1000 cell 8

QoS in Linux

Einrichten der Klassenhierarchie

• Anordnung der Klassen im Vaterbaum
• Kinder können Eltern Bandbreite abgeben
• andere Kinder können diese von Eltern "borgen"
• an Blätter andere QDiscs anfügen
• jede Serviceklasse lässt sich anders behandeln
• Zuordnung über Filter (Classifier)

tc class add dev eth0 parent 1:0 classid 1:1 cbq bandwidth 100MBit rate 100MBit\
   allot 1514 cell 8 weight 10MBit prio 8 maxburst 20 avpkt 1000
tc class add dev eth0 parent 1:1 classid 1:3 cbq bandwidth 100MBit rate 100MBit\
   allot 1514 cell 8 weight 10MBit prio 8 maxburst 20 avpkt 1000
# Klasse fuer Gruppe 5
tc class add dev eth0 parent 1:3 classid 1:35 cbq bandwidth 100MBit rate 100KBit\
   allot 1514 cell 8 weight 10KBit prio 5 maxburst 20 avpkt 1000 bounded
tc qdisc add dev eth0 parent 1:35 tbf rate 100KBit buffer 10Kb/8 limit 15Kb

QoS in Linux

Klassenhierarchie im CSN

QoS in Linux

Klassifizierung der Pakete

• Zuordnung von Paketen zu Klassen
• sequentiell durchlaufen
• Hashing Filters evtl. schneller

Filterarten

• routingbasiert, Firewall-Marks
• U32-Classifier (wertet Paketkopf aus)
• RSVP, TC-Index (ab Kernel 2.4)

# Filter fuer Gruppe 5, fuer jede IP
tc filter add dev eth0 parent 1:0 protocol ip prio 100 u32\
   match ip dst 134.109.96.165/32 flowid 1:35

QoS in Linux

Zusammenfassung

modprobe sch_qdisc
modprobe cls_classifier

tc qdisc add dev eth0 root handle 1: cbq bandwidth 100MBit avpkt 1000 cell 8

tc class add dev eth0 parent 1:0 classid 1:1 cbq bandwidth 100MBit rate 100MBit\
   allot 1514 cell 8 weight 10MBit prio 8 maxburst 20 avpkt 1000
tc class add dev eth0 parent 1:1 classid 1:3 cbq bandwidth 100MBit rate 100MBit\
   allot 1514 cell 8 weight 10MBit prio 8 maxburst 20 avpkt 1000
# Klasse fuer Gruppe 5
tc class add dev eth0 parent 1:3 classid 1:35 cbq bandwidth 100MBit rate 100KBit\
   allot 1514 cell 8 weight 10KBit prio 5 maxburst 20 avpkt 1000 bounded
tc qdisc add dev eth0 parent 1:35 tbf rate 100KBit buffer 10Kb/8 limit 15Kb
# Filter fuer Gruppe 5, fuer jede IP
tc filter add dev eth0 parent 1:0 protocol ip prio 100 u32\
   match ip dst 134.109.96.165/32 flowid 1:35

Einsatzerfahrungen

Einsatzerfahrungen

Auswertung der Daten von Januar-März 2001 (1561 Rechner)

Einsatzerfahrungen

Test mit vorhandenen Daten

• verwendete alte Daten
• keine Begrenzungsregeln aktiv
• Verhalten des Systems bei realen Daten
• keine Auswirkungen auf erzeugten Traffic
• keine Voraussagen über verändertes Nutzerverhalten

• Bandbreite pro Nutzer in Gruppe 5: 19 KBit/s (26 Nutzer)
• Summe des erzeugbaren Traffics: 67 GByte/Tag
• Bearbeitungszeit: ca. 20s pro ausgewertetem Tag

Einsatzerfahrungen

Anzahl der Nutzer in den Gruppen

Einsatzerfahrungen

Test auf dem CSN-Server

• ohne aktive Begrenzung
• Verhalten des Systems unter realen Bedingungen
• Werte deutlich unter denen von Test 1 (Semesterferien)
• Bandbreiten bis zum Maximum nach oben korrigiert
• Monatstraffic: 572 GByte

• durch Einsatz des DynShapers Netz evtl. besser genutzt

Einsatzerfahrungen

Einsatzverlauf

• seit August 2001 Testbetrieb, zufriedenstellend
• ab 03.09.2001 zeitweise mit aktiven Begrenzungsregeln
• ab 23.10.2001 offizieller Testbetrieb

• Wegfall der 250MByte-Limits
• Behebung einiger Bugs & Features
• Traffic Uni-CSN zu 50% eingerechnet (Tunneling)
• wieder aufgehoben, da Behinderung zu groß

• Akzeptanzprobleme, v.a. wegen Begriffswahl
• Renaming von "Klasse" in "Gruppe"

Einsatzerfahrungen

Probleme und Lösungen

• geshapte Bandbreite fair auf offene Verbindungen verteilt
• viele Verbindung -> anteilig mehr Bandbreite
• Behinderung der anderen Nutzer (v.a. Gruppe 5)
• Ausweg 1: mehr Gruppen (feinere Aufteilung der Nutzer)
• Ausweg 2: HTB statt CBQ (in Gruppen eigene Klasse pro Nutzer -> Verteilung pro Nutzer)
• Ausweg 3: WRR statt SFQ (Verteilung pro Zieladresse)
• Ausweg 4: Prioritäten für Filter (bei Sortierung der Nutzer)

• gedroppte TCP-Pakete nochmal gesendet
• mehrfache Zählung + erhöhte Netzlast
• aber: Flusskontrolle drosselt Rate
• UDP nicht betroffen

Einsatzerfahrungen

Verhalten bei vielen Klassen

• CBQ ungenau bei Trafficabschätzung und -begrenzung (wegen EWMA)
• deswegen als QDisc an den Blättern TBF
• aber: maximaler Durchsatz von 15 MBit/s
• Anzahl der Klassen nicht an Einbruch schuld!
• Anzahl der Klassen hat keinen Einfluss auf Durchsatz

• eine Verkehrsklasse pro Nutzer denkbar
• aber: Anlegen der Klassen zeitintensiv (mehrere Minuten für 2000 Klassen)
• deswegen Beibehaltung der Gruppen
• mit HTB eigene Klasse pro Nutzer möglich

Einsatzerfahrungen

Verhalten bei vielen Filtern

Einsatzerfahrungen

Neue Auswertung

• gleitende Zählung (Durchschnitt über letzte 14 Tage) -> Peaks geglättet
• Auswertung und Gruppeneinordnung stündlich neu (keine Verweildauer)
• Einordnung nicht nach Klassenlimits
• Nutzer nach Traffic sortiert und prozentual in Klassen eingeteilt
• jede Gruppe gleichviel Traffic
• neben Bandbreitenregelung Nutzerverteilung als weitere Einflussmöglichkeit
• bei Volllast in Gruppe 10 für jeden 24 KBit/s
• Auslastung in jetziger Gruppe 5 bei 75-80%, Gruppe 4 bei 25-30%

Weighted Moving Average

• andere Idee für Durchschnitt

_                 _
T = (1-gewicht) * T + gewicht * T

Einsatzerfahrungen

Initialwerte der Gruppen

• jetzt 10 Gruppen -> feinere Aufteilung der Nutzer
• Initialbandbreite für Gruppe 10: 1/10 des erlaubten Traffics
• Initialbandbreite für Gruppe 1: Bandbreite des Interfaces
• Initialbandbreiten dazwischen als geometrische Folge
• evtl. besser anhand gemessener Werte

• in kleinen Gruppen viele Nutzer, in großen wenige
• in kleinen Gruppen hohe Bandbreite (+ Priorität), in großen geringe
• wegen Durchschnittsbildung bleibt Verteilung relativ konstant
• festes Bandbreiten-Verhältnis sinnvoll

Einsatzerfahrungen

Neue Gruppenaufteilung

Einsatzerfahrungen

Neue Regelung - Variante 1 (mpa)

• reines Regelsystem
• ebenfalls gleitender Durchschnitt
• nur über die letzten 7 Tage -> schnellere Reaktion
• Durchschnitt: kurzzeitige Einflüsse abfangen, "Schwingen" der Bandbreiten verhindern
• Nachteil: bei Spitzen eines Nutzers alle bestraft (zuerst fallen Bandbreiten, erst später Auswirkung auf Bandbreite dieses Nutzers)

- Last = 7-Tage-Traffic / 7-Tage-Limit (gesamtes CSN)
- wenn Last < 1 dann Last := sqrt(Last)
- Delta(Last) := Last - 1 (> 0: Limit überschritten)
- Negator (hohe Last -> BB verringern)
- Integrator (entspricht fortlaufender Multiplikation im bisherigen System)
- Tiefpass mit Grenzfrequenz 1/(7 Tage)  (Durchschnitt: "Bremsen" der Stellgröße)
- BB = InitialBB * (1 + Delta(BB))

Einsatzerfahrungen

Neue Regelung - Variante 2 (scno)

• Regelung des Faktors, mit dem Initialbandbreiten multipliziert werden
• schnelle Reaktionszeit bei Trafficanstiegen
• möglichst wenig Überschwingen
• Problem: evtl. Springen von Nutzern zwischen Gruppen

     7-Tage-Durchschnittstraffic des gesamten CSN
x = ---------------------------------------------
    14-Tage-Durchschnittstraffic des gesamten CSN

- wenn x > 1,1 dann Faktor = Faktor / (x^y)
  (1,1 -> nur sprunghafte Erhöhungen des Traffics; y >= 2)
- BB = InitialBB * Faktor

Einsatzerfahrungen

Neue Regelung - Diagramm

Ausblick

Ausblick

Geplant für die Zukunft

• Projektantrag beim DFN
• geplanter Einsatz an mehreren Hochschulen
• generischer
• Unterstützung für Einrichtungen, wo keine 1:1-Zuordnung Nutzer-IP
• Installationsanleitung und -unterstützung
• evtl. Integration einer eigenen Datenbank + Trafficzähler
• Option zur Benutzung einer vorhandenen Datenbank (wie im CSN)
• Komplettpaket zur Zählung und Behandlung von Netzverkehr

• faire Behandlung von Caches (Proxy) -> "Gutschriften"
• Differenzierung auch nach Anwendungen (Ports)
• Parallelisierbarkeit (mehrere Router)?

Vielen Dank für Ihre Aufmerksamkeit :-)