Question

Suppose a router's drop policy is to drop the highest-cost packet whenever queues are full, where it defines the "cost" of a packet to be the product of its size by the time remaining that it will spend in the queue. (Note that in calculating cost it is equivalent to use the sum of the sizes of the earlier packets in lieu of remaining time.) (a) What advantages and disadvantages might such a policy offer, compared to tail drop? (b) Give an example of a sequence of queued packets for which dropping the highest-cost packet differs from dropping the largest packet. (c) Give an example where two packets exchange their relative cost ranks as time progresses.

Short answer

Part (a): Balances load but may delay large packets. Part (b): Three packets with largest different than highest cost. Part (c): Two packets' costs swapping due to changing queues.

Step-by-step solution

Understand the Drop Policy

The router drops the packet with the highest cost when queues are full. The cost is defined as the product of the packet's size and the time it will remain in the queue. Alternatively, it may use the sum of sizes of earlier packets.

Analyze Part (a)

Advantages: This policy prioritizes smaller and shorter-lived packets, potentially lowering latency and improving throughput for smaller packets. Disadvantages: It may lead to some large packets never getting through, which could be problematic for applications that require the transmission of larger data packets.

Example for Part (b)

Consider three packets with the following characteristics: Packet 1: size = 10, time remaining = 3; Packet 2: size = 7, time remaining = 6; Packet 3: size = 12, time remaining = 2. Cost of Packet 1: 10 * 3 = 30, Cost of Packet 2: 7 * 6 = 42, Cost of Packet 3: 12 * 2 = 24. The highest-cost packet is Packet 2. Dropping the largest packet would drop Packet 3.

Example for Part (c)

Consider two packets with the following characteristics: Packet A: size = 10, sum of sizes of earlier packets = 2, remaining time = 3; Packet B: size = 6, sum of sizes of earlier packets = 5, remaining time = 6. Initial cost of Packet A: 10 * 3 = 30, Initial cost of Packet B: 6 * 6 = 36. If some packets ahead of Packet B are processed, reducing its remaining time significantly, Packet A might then have a higher cost as it requires less time. The relative costs can thus change.

Key concepts

router drop policies

Router drop policies are essential mechanisms in networking, used to manage congestion and ensure efficient data flow. When a router's queue becomes full, it must decide which packets to drop. Different strategies can be employed:

• Tail Drop: The simplest method, where the router drops the most recent incoming packets when the queue is full.
• Priority-Based Drop: Packets are dropped based on different priority levels assigned to them.
• Highest-cost drop: The router drops the packet with the highest cost, as defined by a combination of the packet’s size and the remaining time in the queue.

Different policies have distinct advantages and disadvantages. For instance, the highest-cost policy can help reduce network latency by focusing on keeping smaller, quicker packets, but it might disadvantage larger packets which could be important for certain applications.

tail drop

Tail drop is one of the most simplistic and widely used packet drop policies.
When a router's queue fills up, it immediately drops any new packets at the tail end of the queue. This method is straightforward and does not require complex calculations or monitoring.
However, tail drop has its drawbacks:

• It can lead to global synchronization, where multiple TCP flows reduce their transmission rate simultaneously, causing under-utilization of the network.
• Large bursts of packets can cause multiple packets to be dropped at once, potentially disrupting important data flows.

Despite these issues, the simplicity of tail drop makes it an attractive option for many network implementations.

packet prioritization

Packet prioritization is a method used to manage network traffic by giving certain packets higher priority.
This involves setting priority levels based on several criteria, such as:

• Application Type: For example, VoIP packets might be given higher priority over email transmissions.
• Source or Destination: Critical servers or users could have their packets prioritized.
• Time Sensitivity: Packets that are time-sensitive, such as those in live streaming or gaming, can be prioritized.

By prioritizing packets, networks can ensure that critical data is transmitted efficiently, improving overall performance and user experience. One of the challenges, however, is managing the complexity of assigning and maintaining these priority levels.

network latency

Network latency is the time it takes for a data packet to travel from the source to the destination.
There are several factors that contribute to latency:

• Propagation Delay: The time it takes for a signal to travel through the medium (fiber optics, copper cables, etc.).
• Transmission Delay: The time needed to push all the packet's bits onto the wire.
• Processing Delay: The time routers take to process the packet header and decide where to forward it.
• Queueing Delay: The time a packet spends waiting in the router's queue before being transmitted.

High latency can lead to noticeable delays in communication and inefficient performance. Lowering latency often involves optimizing routes, reducing queue times, and improving overall network infrastructure.

throughput optimization

Throughput optimization aims to maximize the amount of data successfully sent from one place to another in a given time period.
This can be achieved through several techniques:

• Efficient Routing: Using algorithms to find the shortest and least congested paths.
• Congestion Management: Implementing drop policies and prioritization to manage network traffic better.
• Bandwidth Management: Allocating bandwidth based on usage patterns and priority needs.

By focusing on these areas, networks can enhance their throughput, ensuring that data flows smoothly and efficiently, even under heavy load conditions.
Effective throughput optimization is critical for maintaining high-performance levels in any networking environment, especially as data demands continue to grow.