7 - Rate Limiting and Traffic Shaping

Question 1

Traffic Shaping Approaches

Answer 1

Leaky Bucket, (r, T) Traffic Shaper, Token Bucket, Composite using all 3

Question 2

Motivation for Traffic Shaping

Answer 2

resource control, ensure flows don’t exceed rate.

Question 3

Data Traffic can be

Answer 3

bursty, periodic, regular

Question 4

Audio traffic is

Answer 4

continuous, strongly periodic

Question 5

Video Traffic is

Answer 5

continuous, bursty do to the nature of how video is compressed, periodic

Question 6

The two classes of traffic

Answer 6

Constant Bit Rate source (CBR) - Traffic arrives at regular intervals. Packets are the same size as the arrive. Audio is this.

Variable Bit Rate (VBR) - video, data, shaped according to both an averate rate, and a peak rate. Where the average rate might be a small fraction of the peak rate. You can see that at certain times, the peak rate might well exceed the avg.

Question 7

Leaky Bucket Traffic Shaping (Isochronous)

Answer 7

Each flow has its own bucket
Data arrives in a bucket of size beta, and drains at rate rho. rho controls the avg rate, data can arrive faster or slower into the bucket but can’t drain faster than rho. So the max avg rate that traffic can be sent is the smooth rate rho. The size of thebucket controls the max burst size that can be sent for a flow. So even though the avg rate can’t exceed rho, sometimes the sender can send at a faster rate as long as the burst isn’t exceed the bucket size. The bucket allows for periodical bursts, and the regulator ensures the avg rage doesnt exceed the drain rate. Setting a larger bucket size can allow a larger burst rate. A larger rho value can make for faster avg packet rate.

Question 8

(r, T) Traffic Shaping

Answer 8

Traffic is dividedinto T-bit frames.
Flow can inject <= to r bits in any T-bit frame. If you want to send more than one packet of r bits, you have to wait for the next T-bit frame. This obeys the (t, T) smooth traffic shape.
In this, you can’t send a packet that’s bigger than r bits long.
Unless T is long, the max packet size may be small. So the range is limited to fixed rate flows. Variable flows must request data rates that are equal to the peak rate, and that’s wasteful.
This traffic shaper is relaxed from the simple leaky bucket bc rather than sending one packet every time unit, the flow can send a certain number of bits every time unit.
When a flow exceeds it’s rate, the excess packets in that flow are given a lower priority. If the network is heavily congested, the packets may be dropped.
Priorities might be assigned by the sender or the network. The sender’s app would mark the packets since it knows which ones are important.
Routers that mark packet priorities is called policing.

Question 9

Shaping bursty traffic patterns (Token Bucket)

Answer 9

To shape bursty traffic, allowing for bursts but still making sure the flow doesn’t exceed an avg rate. The Token Bucket is good for this.
Tokens arrive in a bucket at rate rho, and beta is the capacity of the bucket.
Traffic can arrive at an avg rate, lambda avg, and a peak rate lambda peak. Traffic can be sent by the regulator as long as there are tokens in the bucket.

Question 10

The difference between Token Bucket and Leaky Bucket

Answer 10

Consider sending a packet of size b that’s less than beta.

• If the token bucket is full, packet is sent, and b tokens are removed.
• if the bucket is empty, the packet must wait until b tokens drip into the bucket.
• If the bucket is partially full, then it depends. If the number of tokens in the bucket exceed b then the packet is sent immediately. Otherwise, we have to wait until there are b tokens in the bucket before we can send the packet.

Question 11

Token vs Leaky Bucket Cont (Token Bucket explained)

Answer 11

Token Bucket

• permits burstiness, but bounds it by the rate rho.
• The bound is:
  
  • If bucket size beta, then we know that at any interval, T, then the rat is always less than beta, that is the max number of tokens that can be accumulated in the bucket. Plus the rate at which tokens accumulate, times that interval.
  • We also know that the long term rate will always be less than rho.
• No discard, or policies
• More flexible since it has additional params that we can use to configure the burst size.
• One of the limitations is that at any traffic level of length T, the flow can send beta plus T times rho tokens of data. If a network tries to plice the flows by simply measuring their traffic over intervals of length T. The flow can cheat by sending this amount of data each interval.
• Consider, for example, an interval of twice this length. If the flow can send data plus T times rho in each interval.
• Then over 2T the flow can consume 2 times betwa plus tau times rho tokens. But actually this is greater than how much the flow is actually supposed to be able to send which is beta plus 2T times rho. So policing traffic being sent by token buckets is actually rather difficult. So token buckets allow for long bursts. And if the bursta are high priority traffic, they are difficult to police and may interfere with other high priority traffic. So there’s some need to limit how long a token bucket sender can monopolize the network.

Question 12

Token Bucket vs Leaky Bucket (Token Bucket more…)

Answer 12

• Permits burstiness, but bounds it to the rate rho.
• The bound is:
  
  • if the bucket size, beta then we know that at any interval, T, then the rate is always less than beta, that is the max number of tokens that can be accumulated in the bucket. Plus the rate at which tokens accumulate, times that time interval.
• No discard or priority policies.
• More flexible since it has additional params that we can use to configure the burst size.
• One of the limitations is that at any traffic level of length T, the flow can simply send beta plus T time rho tokens of data. If a network tries to police the flows by simply measuring their traffic over intervals of length T. The flow can cheat by sending this amount of data in each interval.
• Consider, for example an interval of twice this length. If the flow can send beta plus T times rho in each interval. Then over 2T the flow can consume 2 times beta plus tau times rho tokens. But actually, this greater than how much the flow is at actually supposed to be able to send which is beta plus 2T times rho. So policing traffic being sent by token buckets is rather difficult. So token buckets allow for long bursts. And if the bursts are of high priority traffic, they are difficult to police and may interfere with other high priority traffic. So there’s some need to limit how long a token bucket sender can monopolize the network.

Question 13

Token Bucket vs Leaky Bucket (Leaky Bucket)

Answer 13

• Forces the bursty traffic to be smoothed

- Implement priority policies for flows that exceed the smoothing rate.

Question 14

Policing With Token Buckets

Answer 14

• In order to police Token buckets, a Composite Shaper is used.
• Composite Shaper: to combine a Token bucket shaper with a leaky bucket.
• The combination of the token bucket shaper with the leaky bucket shaper allow for good policing. Confirming that the flows data rate does not exceed the avg data rate allowed by the smooth leaky bucket is easy.. But the implementation is more complex since each bucket flow now requires two counters, and two timers. One timer and one counter for each bucket.

Question 15

Quiz Token Bucket Shaper:
The size of the bucket (beta) is 100KB, rho is 10 packets/second, and that packets are 1KB. Assume that we are talking about an interval of 1 second. Remember that an any given interval, a flow can never send more than beta plus tau times rho bits of data. Give your answer in kilobits per second kepping in mind that 1 byte is 8 bits.

Answer 15

The max rate would be 100KB times 1 second plus 10 packets/second times 10KB, or 110KB, which is 880 kbs/second.

Question 16

Power Boost

Answer 16

A traffic shaping mechanism that was first deployed in commercial broadband networks in 2006 by comcast.
- Allows a subscriber to send at a higher rate for a brief period of time. Then it shapes you back to your subscribed rate. It boosts targets spare capacity in the network for use by subscribers who don’t put a lot of load on the network.

Question 17

The two types of power boost

Answer 17

• If the rate at which the user can achieve during the burst window is set to not exceed a particular rate, then it is a power boost.
• Otherwise, the capping/shaping is called uncapped power boost. The uncapped setting, the config is simple. The area is the power boost bucket size, the max amount of traffic that can be sent that exceeds the sustained rate. The max sustained rate is rho. If we wanted to cap the rate the sender can send during the power boost window. We simply apply a second token bucket with another value of rho. That token bucket limits the peak sending rate for power boost eligible packets to the rate rho C, where rho C is larger than rho. Remember this value of rho also affects how quickly tokens can refill the bucket so it plays a role in the max rate that can be sustained during the power boost window.

Question 18

Calculating Power Boosts

Answer 18

if someone wants to send at rate r, that’s bigger than R that they’re supposed to be sedning at, and suppose the bucket size is beta. how long can the sender send at rate r, that exceeds the sustained rate R? In other words, whats the value of d?
- We know that the bucket size, beta, as shown in the shaaded green area is d times r minus the sustained rate R. So the sender can send at the rate r, that exceeds the sustained rate R, for beta divided by r minus R sustained.

Question 19

PowerBoost Quiz - Suppose that the sustained rate that a subscriber subscribes to is ten megabits per second. But they like to burst at a rate of 15 megabits per second. Suppose the bucket size is 1 megabyte or 8 megabits. How long can the sender send at the higher rate?

Answer 19

We know that 1MB is 8 MegaBits, and from our previous calculation, we know that the duration should be 8 megabits, over 5 megabits per second. or 1.6 seconds.

Question 20

Examples of Power Boost

Answer 20

The Bismarck Project at Georgia Tech, there have been measurements of Comcast power boosts in diffferent home networks. Some homes exhibit different shaping profiles. Some have a very steady pattern, whereas others have a more erratic pattern. Interestingly, you can see in some cases there appear to be 2 different tiers of higher throughput rates.

Question 21

Turbo Boost Effects on Latency

Answer 21

It effects the latency that users receive as well as the loss rate. Even though power boost allows a user to send at a higher traffic rate, actually users may experience high latency/loss over the duration that they’re sending at a hirher rate. This is because the axis may not be able to support the higher rate. If a sender can only send at R sustained for an extended period of time but is allowed to burst at a rate r for some shorter period of time, then buffers may fill up and the resulting buffers may introduce additional delays in the network since packets are being buffered up rather than dropped. TCP senders can continue to send at higher rate,s such as little r without seeing any packet loss een though the access link may not be able to send at a higher rate. As a result, packets buffer up, and users see higher latency over the course of the power boost. To solve this problem the sender might shape its rate never to exceed the sustained rate R. If it did this, then it could avoid seeing latency. So senders who are more interested in keepign latency under control than sending bursty volumes will run a traffic shaper in frontof a power boost link. To keep the rate less than the sustained rate, r could prevent buffering.

Question 22

Buffer Bloat

Answer 22

We previously saw the effects of power boost allowing a sender to send at a higher rate than the sustained rate. If there’s a buffer that can support the higher rate, we’ll see the buffer start filling up. But it can only drain at a sustained rate. So even if the sender can send at a faster rate for a period of time, all the packets get queued up in the buffer waiting to be sent by the router. This causes more delays. More than they would if they arrived at the front of the buffer queue. The delay the packet will see in the buffer is the amount of data in the buffer divided by the rate the rate that the buffer can drain. Large buffers can cause performance issues for media streaming. Large buffers are in home WIFI devices and even in switches and routers.

Question 23

Solutions to the Buffer Bloat Problem

Answer 23

• Use smaller buffers, but given that we’ve already deployed our infrastructure, reducing buffer size in deployed routers, switches, home wifi devices and so forth is not reasonable. the other thing we can do is use traffic shaping methods. Shape the traffic such that traffic comming into the access link never exceeds the uplink that the ISP has provided us so the buffer doesn’t over fill.

Question 24

Network Measurement

Answer 24

How to see traffic is being sent on the network.

Question 25

The two types of Network Measurement

Answer 25

- passive measurement: we collect packets, flow stats, and so forth of traffic already being sent on the network. this includes packet traces, flow stats, and app logs. - Active measurement: We inject additional traffic into the network to measure various characteristics of the network, so we've seen some examples of active measurement already, where we actively sent traffic on the network to measure download speeds.. Other active measurement tools are ping and trace route. Ping is used to measure delay. Traceroute is used to measure the network level, or the IP level path between two hosts on the network.

Question 26

Why Measure

Answer 26

Billing, we may want to charge a customer based on how much traffic they've sent on the network. To do that we need to passively measure how much traffic they're sending. A user may be billed based on how much traffic they send. A common billing mode is called 95th percentile billing, where a customer pays for a committed info rate, or CIR, of 5 minute samples. A network operator may want to measure traffic on the network to detect compromised hosts or the presence of bonnets or ddos attacks.

Question 27

How to measure Passively

Answer 27

One way is to use packet and byte counters provided by the simple network management protocol. Many network devices provide whats' called a management info base, or MIB that can be polled or queried for particular info. One common use for SNMP is to poll a particular interface on a network device. For the number of bytes or packets that it sent. By periodically polling we can then determine the rates at which traffic is being sent on a link by simply taking the difference between these packet and byte counters over particular intervals. The advantage of SNMP is that it's fairly ubiquitous. supportied on all networking equipment and there are many products for polling and analyzing SNMP data. However, it's coarse and you can't express complex queries on the data. Because we are just polling byte or packet counts on the interface. We can't ask specific questions, such as how traffic has been sent by a particular host or by a particular flow. Two other ways to measure passively are by monitoring at a packet granularity, whereby monitors can see full packet contents. Or at a flow level where a monitor may see specific stats about individual flows in the network.

Question 28

Packet Monitoring

Answer 28

a monitor might see the full packet contents, or at least the packet headers that traverse a particular link. Common ways of performing packet monitoring include tcpdump, ethereal, or wireshark. Sometimes packet monitoring is performed using hardware mounted in the servers along the routers that forward the traffic. Sometimes the link will split the traffic to be sent to the monitor as well. On a switch network, you wouldn't see many packets that weren't destined for your mac address. But on a network where there's a lot of traffic, you'd see a lot more traffic than destined for an interface that you're using to monitor.

Question 29

What you can see in packet monitoring

Answer 29

You can see timing info, packet headers, but it's a lot of overhead and hard to keep up with high speed links. and requires a separate monitoring device.

Question 30

Flow Monitoring

Answer 30

A monitor that might be running on the router itself, records stats per flow. A flow consists of packets that share a common source and destination IP address, source and destination port, protocol type, TOS byte, and interface, on which the packets arrive. A flow monitor can then record the stats for a flow that's defined by a group of packets that share these features. The flow records may also contain additional info such as the next hop ip address,and other info related to routing. Such as the source and destination AS on which those packets appear to be coming from and going to based on the routing tables, as well as the prefix that those packets matched in the routing table. Flow monitoring is much less overhead than packet monitoring, but it's much more coarse than packet monitoring because the monitor doesn't see individual packets or payloads. Therefore it's impossible to get certain info from it. Such as packet timing ifno. In addition to grouping packets into flows based on the fact that they share common elements in their headers, typically packets are grouped into flows if they occur close together in time. So if packets that share common sets of header fields don't appear for a particular time interval, the router simple declares the flow to be over, and sends a flow record to the monitor based on the packets it's seen up to that point. Sometimes to reduce monitoring overhead, flow level monitoring may also be accompanied with samples. Sampling build flow stats based only on samples of the packets. So for example, flows may be created based on one out of every ten or 100 packets. Or a packet might be sampled with a particular probability and flow stats might only be tabulated based on the packets that end up being sampled randomly from the total set of packets.