PrevNextAll

Packet queues

• Internet protocols such as TCP need packet queues
• Incoming packets can arrive out of order
• Best data structure depends on rarity of out of order packets
• Rare out-of-order packet
  • Inserting late packet may be slow
  • Can use a linear list
• Common out-of-order packet
  • Inserting late packet must be fast
  • Use a priority queue