Introduction

Queuing:

• Solves performance degradation of datagram networks in the presence of congestion
• Methods of Congestion control
• Methods have two points of implementation:
  1. at the source, where flow control algorithms vary the rate at which the source sends packets
  2. at the gateway, where congestion can be controlled through routing and queuing algorithms
• Control the order in which packets are sent and the usage of the gateway’s buffer space, although it does not affect congestion directly, in that they do not change the total traffic on the gateway’s outgoing line
• Determines the way in which packets from different sources interact with each other
• Algorithms can be thought of by the following three nearly independent properties:
  1. Bandwidth-which packets get transmitted
  2. Promptness-when do those packets get transmitted
  3. Buffer space-which packets are discarded by the gateway/router
• FCFS (first-come-first-serve)
  • Relegates all congestion control to the sources, since order or arrival determines the bandwidth, promptness, and buffer space allocations
  • A single source sending packets to a gateway at a sufficiently high speed, can capture an arbitrarily high fraction of the bandwidth of the outgoing line and starve other sources
• Fair Queuing (FQ)
  • Algorithm in which gateways maintain separate queues for packets from each individual source or flows
  • Queues are serviced in a round-robin manner
  • Prevents a source from arbitrarily increasing its share of the bandwidth or starving other sources