Rate Limiting and Traffic Shaping

Question 1

Would you use a leaky bucket or a token bucket to traffic shape a constant bit rate (CBR) audio stream?

Answer 1

Since a constant bit rate stream isn’t bursty, the traffic shaping mechanism doesn’t need to handle bursts. Since the original stream is “smooth”, it would be better to use the leaky bucket to keep the stream “smooth” and even out any bursts.

Question 2

Properties of Constant Bit Rate (CBR) traffic.

Answer 2

Traffic Arrives at Regular Intervals

Packets are typically the same size when they arrive.

Question 3

Properties of Variable Bit Rate (VBR) traffic.

Answer 3

Shaped according to average rate and peak rate

Average rate may be small fraction of peak rate

Question 4

Properties of a Leaky Bucket

Answer 4

Each flow has its own bucket of size Beta

Data arrives in a bucket and drains from the bucket at a rate rho, that controls the average rate

Data can arrive at a rate faster or slower into the bucket but it cannot drain at a rate faster than rho.

Size of bucket controls maximum burst size that a sender can send for a particular flow. Even if average rate cannot exceed rho, sender might be able to send at a faster rate as long as bucket does not overflow.

Question 5

Properties of (r,T) Traffic Shaping

Answer 5

Traffic is divided into T-bit frames

A flow can inject <= r bits in any T-bit frame

A flow that obeys this rule has an (r,T) smooth traffic shape

In the case of (r,T) smooth traffic shaping, One cannot send a packet that is greater than r bits long. Maximum packet size is relatively small, so range of behaviors is typically limited to fixed rate flows.

If a flow exceeds its rate, the excess packets in the flow are given a lower priority

Question 6

Properties of a Token Bucket

Answer 6

Tokens arrive in a bucket, of size Beta, at a rate rho

Traffic may arrive at an average rate lambda(average) and a peak rate lambda(peak)

Traffic can be sent by the regulator as long as there are tokens in the bucket.

If the bucket is empty, a packet must wait until a number of tokens equal to the packets size are added to the bucket before it can be sent.

Question 7

How many bits in a Byte?

Answer 7

8 bits = 1 Byte

Question 8

Traffic Shaping Equation:

Answer 8

Beta = (Burst Rate - rho(average rate)) * T

Rate < B + T * P

Question 9

Composite Shaper

Answer 9

Combines token bucket shaper with leaky bucket shaper.

Combination of token bucket shaper with leaky bucket shaper allows for good policing.

Question 10

Policing

Answer 10

If a flow exceeds its rate, excess packets are given lower priority. If network is heavily loaded or congested.

Routers marking packets with lower priority on flows that exceed its rate.

Question 11

Power Boost

Answer 11

Traffic shaping mechanism that allows a subscriber to send at a higher rate for a brief time

Targets Spare Capacity for users who do not put a sustained load on the network

Question 12

Buffer Bloat

Answer 12

Buffer will start filling up with more packets if sender sends at faster rate because Buffer will only be able to drain at the previous constant rate.

Question 13

Passive Measurement

Answer 13

Packets, Flow Statistics, etc are collected on traffic that is already being sent on the network.

Ex. Packet Traces, Flow Stats, or Application Level Logs

Question 14

Active Measurement

Answer 14

Additional traffic is injected into the network to measure various characteristics of the network.

Question 15

Simple Network Management Protocol

Answer 15

Internet-standard protocol for collecting and organizing information about managed devices on IP networks and for modifying that information to change device behavior

Packet and Byte Counters provided by protocol can be used to perform passive network traffic management.

Question 16

Two Types of Passive Measurement

Answer 16

Packet Monitoring: Monitors can see full packet contents or headers

Flow Monitoring: Monitor may see specific stats about individual flows in the network.

Question 17

Packet Monitoring:

Answer 17

A monitor might see full packet contents, or at least packet headers, that traverse a particular link

Common methods include TCPDump, Ethereal, Wireshark.

Packet Monitoring provides lots of detail, but has fairly high overhead.

Question 18

Flow Monitoring

Answer 18

A monitor records stats per flow.

A flow consists of packets that share a common: 
src & dst IP
src & dst Port
Protocol Type
TOS (Type of Service) Byte
Interface on which packets arrived

Flow monitor can then record stats for a flow that is defined by the group of packets that share these features.

Much less overhead than packet monitoring. Much more coarse than packet monitoring.

Question 19

Sampling

Answer 19

Builds flow stats based only on samples of packets. Used to reduce monitoring overhead.

Question 20

Read about the following two Active Queue Management (AQM) techniques: Random Early Detection (RED) and CoDel . Although they vary in specifics, these two algorithms share a common basic approach to solving the buffer bloat problem. Explain what that approach is and why it works.

Answer 20

Their approach is to drop packets even when their buffers are not full

RED determines whether to drop a packet statistically based off how close to full the buffer is, whereas CoDel calculates the queuing delay of packets that it forwards and drops packets if the queuing delay is too long.

Question 21

If you want to find out if a remote host (i.e., not your server) is currently under a DoS attack, would you use active or passive measurement? Explain why.

Answer 21

Active measurements, such as ping, are required here. Only the server’s owner or ISP would be able to use passive measurements, since they control the machines over which the server’s traffic is handled. Excessive ping delays to the server are a sign of congestion on the server’s link. (It’s hard to be sure that it’s due to a DoS attack without additional context, but it’s a sign that something is wrong…)

Question 22

If you want to compute the traffic intensity, I=La/R, on a router interface (i.e., the ratio between arrival rate and forwarding rate), would you use Counters, Flow Monitoring, or Packet Monitoring? Explain why.

Answer 22

The sending rate is a known quantity (it’s just the maximum rate of that device’s interface). The average length of packets and the average arrival rate of the packets can be determined from simple counters. (We do not need to inspect the packet contents, so packet monitoring is unnecessary. Since we are only concerned with all packets on a particular interface and do not care about which flow each packet belongs to, flow monitoring is also unnecessary.