Thursday, November 22, 2012

Notes - Quality of Service

The following are notes from Tanenbaum's Computer Networks 5th Edition.
  • techniques to guarantee stronger performance
  • overprovisioning build a network with more capacity than the traffic that can be thrown at it
  • four issues to ensure quality of service
    • what applications need from the network
    • how to regulate traffic that enters the network
    • how to reserve resources at routers to guarantee performance
    • whether the network can safely accept more traffic
Application requirements
  • stream of packets from a source to destination is called a flow
    • characterized by bandwidth, delay, jitter, loss
    • determines quality of service
  • delay requirements
    • file transfer applications such as e-mail and video are not delay sensitive, few seconds delay doesn't mean much
    • interactive much more delay sensitive, such as web surfing remote login
    • variation in delay or packet arrival is jitter
    • To accomodate variety of applications networks must support
      • Constant bit rate(telephony)
      • Real-time Variable Bit rate (video conference)
      • Non-Real-time Variable Bit rate (video on demand)
      • Available bit rate (file transfer)
Traffic Shaping
  • must know what traffic is
    • voice call needs 64kbps one 8 bit sample every 125 microseconds
    • traffic in data networks is bursty, nonuniform rates, variety of traffic
  • traffic shaping is to regulate the average rate and burstiness of a flow of data
  • SLA(Service Level Agreement)
    • aggregate flows and long periods of time based on the customer
  • Traffic policing monitoring a traffic flow
  • Leaky and Token Buckets
  • Leaky bucket algorithm
    • send a packet to a network, arrives, packet is queued until enough packets exit so it can be sent
  • Token bucket algorithm
    • tokens allocated into bucket users take contents out of the bucket that is already allocated
  • example of use token bucket and leaky bucket
  • routers shaped by token bucket go up to maximum rate until tokens are used up by this user
  • later on in a second job, the rate is used as the tokens come in
  • the last graph is showing a token bucket that is empty which is equivalent to a leaky bucket algorithm constant usage
  • counter of a token bucket implemented R/ΔT units every ΔT seconds
  • calculating maximum burst until bucket empties
  • where M is the maximum output rate, B is the token bucket capacity bytes, R is the token arrival rate, S is the burst length in seconds
  • example calculation
B = 9600 KB
M = 125 MB/sec
R=25 MB/sec
burst time about 94 msec
Packet Scheduling
  • packet scheduling algorithms resources reserved for different flows
    • Bandwidth
      • not oversubscribing any output line
    • Buffer space
      • when packet arrives goes into buffer, needs enough room
    • CPU cycles
      • takes router time to process a packet
  • FIFO(First in First out)
    • usually drop newly arriving packets
    • tail drop
  • FCFS(First come First serve)
  • fair queueing algorithm
    • input queues go based on output line, whichever full packet is shortest will be sent, imagine a vertical line moving across from right to left on the following image, whichever packet is fully gone over will be sent next
  • WFQ (Weighted Fair Queueing) 
    • Weighted queueing algorithm is similar to fair queueing, but in order to weight, the line can go across at different rates, so that the bottom queue for example could go over twice as quickly so the first two packets could be sent before the middle packet gets sent in the above picture
    • where A is the arrival time, F is the finish time, L is the length of the packet, W is the weight of a flow
  • deficit round robin
  • priority scheduling
    • each packet assigned priority to be sent
  • timestamp
    • each packet assigned with time, records how far ahead or behind a packet is and speeds up or slows down
Admission Control
  • QoS routing
    • find the single best path between source and destination send traffic over this path
    • QoS new flows can be accommodated by different path
    • split traffic
  • Flow specification
    • set of parameters token bucket rate, bucket size, peak data rate, min packet size, max packet size
    • under assumption of poisson arrival/sending rates
    • M/M/1 markov distribution mean delay of a packet is
  • rho is lambda over service time
Integrated Services
  • integrated services ability to support unicast and multicast applications
  • RSVP-The Resource Reservation Protocol
    • allows for reservations, to get better reception and eliminate congestion
    • reverse path forwarding algorithm message
    • use a weighted fair queue method to schedule the reservation
    • receiver can specify one or more sources it wants to receive from
Differentiated Services
  • flow based algorithms offer good quality of service to one or more flows
  • class-based instead of flow-based quality of service
    • implement setup without having whole path involved
    • per hop behavior
  • Expedited Forwarding
    • IETF network independent service classes
    • this idea is to have classes of services, expedited packets are on their own route as opposed to regular packets
      • kind of like having a carpool lane in a freeway that is reserved based on class and marks
  • Assured  Forwarding
    • 4 priority classes, gold, silver, bronze, regular weighted fair queueing used on this

No comments:

Post a Comment