／var／logmarcus chiu

CN - Chapter 6 - Congestion Control and Resource Allocation

Created on · Last Modified on

Sections

  • Issues in Resource Allocation - overview of congestion control and resource allocation
  • Queueing Disciplines - different queuing disciplines that can be implemented on the routers inside the network
  • TCP Congestion Control - description of the congestion-control algorithm provided by TCP on the hosts
  • Congestion Avoidance Mechanisms - techniques involving both routers and hosts that aim to avoid congestion before it becomes a problem
  • Quality of Service (QoS) - examine the broad area of quality of service
  • Equation-Based Congestion Control -

Issues in Resource Allocation

resource allocation - process by which network hosts and network elements try to meet the competing demands that applications have for network resources— primarily link bandwidth and buffer space in routers or switches
congestion control/avoidance - efforts made by network hosts and network elements to prevent or respond to overload conditions

flow control - involves keeping a fast sender from overrunning a slow receiver
congestion control - responds to congestion, and tries to resolve it
congestion avoidance - avoids congestion in the first place

Network Model

3 prominent features of the network architecture:

Packet-Switch Network

in a packet-switch network a source may have more than enough capacity on the immediate outgoing link to send a packet, but somewhere in the middle of a network its packets encounter a link that is being used by many different traffic sources

access-control algorithms of ethernet and wifi are, in some sense, analogous to congestion-control algorithms in a switched network

Connectionless Flow

idea of a flow—a sequence of packets sent between a source/destination pair and following the same route through the network

flows can be defined at different granularities:

  • host-to-host flow (i.e., have the same source/destination host addresses)
  • process-to-process flow (i.e., have the same source/destination host/port pairs

soft state - state information for each flow that can be used to make resource allocation decisions about the packets that belong to the flow. soft state represents a middle ground between a purely connectionless network that maintains no state at the routers and a purely connection- oriented network that maintains hard state at the routers

flow can be either:

  • implicitly defined - each router watches for packets that happen to be traveling between the same source/destination pair—the router does this by inspecting the addresses in the header—and treats these packets as belonging to the same flow for the purpose of congestion control
  • explicitly established - source sends a flow setup message across the network, declaring that a flow of packets is about to start

Service Model

best-effort service model
  • all packets are equal
  • tries to deliver data but makes no promises and leaves to cleanup operation to the edges
  • subset of quality of service model
quality of service model
  • requires differentiation of packets
  • first asks the network for a level of service, the network then responds by providing it or perhaps saying it cannot promise anything better at the moment
  • superset of best-effort service model
  • submodels of QoS model

3 Dimensions of Resource Allocation Mechanisms

Router-Centric vs Host-Centric
  • host-centric - address the resource allocation problem from the edges of the network
  • router-centric - address the resource allocation problem from within the network
Reservation-Based vs Feedback-Based
  • reservation-based - some entity (e.g., the end host) asks the network for a certain amount of capacity to be allocated for a flow
    • reservation-based system always implies a router-centric resource allocation mechanism
  • feedback-based - end hosts begin sending data without first reserving any capacity and then adjust their sending rate according to the feedback they receive.
    • feedback can be either:
      • explicit - a congested router sends a “please slow down” message to the host
      • implicit - the end host adjusts its sending rate according to the externally observable behavior of the network, such as packet losses
    • a feedback-based system can imply either a router- or host-centric mechanism.
      • typically, if the feedback is explicit, then the router is involved, to at least some degree, in the resource allocation scheme
      • typically, if the feedback is implicit, then almost all of the burden falls to the end host; the routers silently drop packets when they become congested
Window Based vs Rate Based
  • window based - corresponds to how much buffer space the receiver has, and it limits how much data the sender can transmit
  • rate based - how many bits per second the receiver or network is able to absorb

Evaluation Criteria

one final issue is figuring out whether a resource allocation mechanism is good or not based on:

Effective Resource Allocation

  • throughput vs delay: increasing throughput will increase queue size and thus increases delay

    List indent undo

  • power is typically defined relative to a single connection (flow); it is not clear how it extends to multiple, competing connections

  • objective is to maximize this power ratio

Fair Resource Allocation

metric that can be used to quantify the fairness of a congestion-control mechanism
given a set of flow throughputs (x1, x2, …, xn) (measured in consistent units such as bits/second), the following function assigns a fairness index to the flows:

the fairness index always results in a number between 0 and 1, with 1 representing greatest fairness

Queueing Disciplines

each router must implement some queuing discipline that governs how packets are buffered while waiting to be transmitted

two common queuing algorithms:

First-in First-Out (FIFO)

Variations of FIFO

  • priority queuing - each packet is marked with a priority.

Fair Queueing (FQ)

problem with FIFO queuing is that it does not discriminate between different traffic sources

idea of FQ is to maintain a separate queue for each flow currently being handled by the router. the router then services these queues in a sort of round-robin

the main complication is that the packets being processed at a router are not necessarily the same length. To truly allocate the bandwidth of the outgoing link in a fair manner, it is necessary to take packet length into consideration

bit-by-bit algorithm

consider the behavior of a single flow and imagine a clock that ticks once each time one bit is transmitted from all of the active flow (a flow is active when there is data in its queue).

for this flow, let:

Pi = length of packet i
Si = time when the router starts to transmit packet i
Fi = time when the router finishes transmitting packet

therefore:

Fi = Si + Pi

when do we start transmitting packet i?
the answer to this question depends on whether packet i arrived before or after the router finished transmitting packet i−1 from this flow

If we let

Ai = time that packet i arrives at the router

then

Si = max(Fi− 1,Ai)

and thus

Fi = max(Fi− 1,Ai) + Pi

Now, for every flow, we calculate Fifor each packet that arrives using the above formula. We then treat all the Fi as timestamps, and the next packet to transmit is always the packet that has the lowest timestamp— the packet that, based on the above reasoning, should finish transmission before all others

FQ guarantees minimum share of bandwidth to each flow, with the possibility that it can get more than its guarantee if other flows are not using their shares

Variations of Fair Queueing
  • weighted fair queuing (WFQ)
    • allows a weight to be assigned to each flow (queue)
    • this weight logically specifies how many bits to transmit each time the router services that queue, which effectively controls the percentage of the link’s bandwidth that that flow will get
    • for example, a simple FQ gives each queue a weight of 1, which means that logically only 1 bit is transmitted from each queue each time around. This results in each flow getting (1/n)th of the bandwidth when there are n flows. With WFQ, however, one queue might have a weight of 2, a second queue might have a weight of 1, and a third queue might have a weight of 3. Assuming that each queue always contains a packet waiting to be transmitted, the first flow will get one-third of the available bandwidth, the second will get one-sixth of the available bandwidth, and the third will get one-half of the available bandwidth
    • a router performing WFQ must learn what weights to assign to each queue from somewhere, either by manual configuration or by some sort of signalling from the sources

TCP Congestion Control

the idea of TCP congestion control is for each source to determine how much capacity is available in the network

types of mechanisms:

TCP Implementations:

CongestionWindow
  • a state variable for each TCP connection
  • used by the source to limit how much data it is allowed to have in transit at a given time
  • (congestion control is to congestion window) as (flow control is to advertised window)

TCP is modified such that the maximum number of bytes of unacknowledged data allowed is now the minimum of the congestion window and the advertised window

MaxWindow = MIN(CongestionWindow,AdvertisedWindow)
EffectiveWindow = MaxWindow −(LastByteSent − LastByteAcked)

Additive Increase/Multiplicative Decrease Mechanism (AIMD)

  • general idea: decreasing the congestion window when the level of congestion goes up and increasing the congestion window when the level of congestion goes down
  • how does the source determine that the network is congested? the answer is based on the observation that the majority of packets not delivered, and resulting in timeouts, is that a packet was dropped due to congestion (it is rare that a packet is dropped because of an error during transmission)
Multiplicative Decrease

each time a timeout occurs, the source sets CongestionWindow to half of its previous value (if the resulting value is less than 1, CongestionWindow=1)

Additive Increase

2 ways implementing additive increase, either:

  • each round trip time, increment CongestionWindow by 1 packet (MSS - maximum segment size) 
    CongestionWindow += MSS
  • each acknowledgement, increment CongestionWindow by a little (this is done in practice such as in TCP) 
    Increment = MSS × (MSS/CongestionWindow) 
CongestionWindow += Increment

this pattern of continually increasing and decreasing the congestion window continues throughout the lifetime of the connection

Slow Start Mechanism

  • slow start is a second mechanism provided by TCP
  • slow start is used to increase the congestion window rapidly from a cold start
  • slow start effectively increases the congestion window exponentially, rather than linearly

2 different situations in which slow start runs:

  • first is at the very beginning of a connection
  • second occurs when the connection goes dead while waiting for a timeout to occur

algorithm:

  • CongestionWindow is initialized to some starting value (e.g. 1, 2, 4 or 10 maximum-segment-size MSS)
  • the value CongestionWindow will be increased by 1 for each ACK received, effectively doubling the CongestionWindow each round-trip time (RTT)
  • this process continues until there is a loss, at which time a timeout causes multiplicative decrease to divide CongestionWindow by 2
  • TCP introduces a temporary variable CongestionThreshold
  • CongestionThreshold is set equal to the CongestionWindow value after the result of multiplicative decrease.
  • CongestionWindow is then reset to 1 packet
  • CongestionWindow is incremented 1 packet per ACK received until it reaches CongestionThreshold, at which point it is incremented by 1 packet per RTT.

In other words, TCP increases the CongestionWindow as defined by the following code fragment:

cw = state.CongestionWindow 
incr = state.maxseg
if (cw > state.CongestionThreshold)
 incr = incr * incr / cw; 
state.CongestionWindow = MIN(cw + incr, TCP_MAXWIN)

There are several things to notice about this trace. The first is the rapid increase in the congestion window at the beginning of the connection. This corresponds to the initial slow start phase. The slow start phase continues until several packets are lost at about 0.4 seconds into the connection, at which time CongestionWindow flattens out at about 34 KB. (Why so many packets are lost during slow start is discussed below.) The reason why the congestion window flattens is that there are no ACKs arriving, due to the fact that several packets were lost. In fact, no new packets are sent during this time, as denoted by the lack of hash marks at the top of the graph. A timeout eventually happens at approximately 2 seconds, at which time the CongestionWindow is divided by 2 (i.e., cut from approximately 34 KB to around 17 KB) and CongestionThreshold is set to this value. Slow start then causes CongestionWindow to be reset to 1 packet/mss and starts ramping up from there.

There is not enough detail in the trace to see exactly what happens when a couple of packets are lost just after 2 seconds, so we jump ahead to the linear increase in the congestion window that occurs between 2 and 4 seconds. This corresponds to additive increase. At about 4 seconds, CongestionWindow flattens out, again due to a lost packet.

Now, at about 5.5 seconds:

  1. A timeout happens, causing the CongestionWindow to be divided by 2, dropping it from approximately 22 KB to 11 KB, and CongestionThreshold is set to this amount
  2. CongestionWindow is reset to 1 packet/mss
  3. Slow start causes CongestionWindow to grow exponentially until it reaches CongestionThreshold
  4. CongestionWindow then grows linearly

The same pattern is repeated at around 8 seconds when another timeout occurs.

Quick Start Mechanism

The basic idea is that a TCP sender can ask for an initial sending rate greater than slow start would allow by:

  1. putting a requested rate in its SYN packet as an IP option
  2. routers along the path can examine the option, evaluate the current level of congestion on the outgoing link for this flow, and decide if that rate is acceptable, if a lower rate would be acceptable, or if standard slow start should be used
  3. by the time the SYN reaches the receiver, it will contain either a rate that was acceptable to all routers on the path or an indication that one or more routers on the path could not support the quick-start request.
    1. In the former case, the TCP sender uses that rate to begin transmission
    2. in the latter case, it falls back to standard slow start.
  4. if TCP is allowed to start off sending at a higher rate, a session could more quickly reach the point of filling the pipe, rather than taking many round-trip times to do so

Fast Retransmit

  • triggers the retransmission of a dropped packet sooner than the regular timeout mechanism
  • does not replace regular timeouts; it just enhances that facility

Every time a data packet arrives at the receiving side, the receiver responds with an acknowledgment, even if this sequence number has already been acknowledged. Thus, when a packet arrives out of order—when TCP cannot yet acknowledge the data the packet contains because earlier data has not yet arrived—TCP resends the same acknowledgment it sent the last time. This second transmission of the same acknowledgment is called a duplicate ACK. When the sending side sees a duplicate ACK, it knows that the other side must have received a packet out of order, which suggests that an earlier packet might have been lost. Since it is also possible that the earlier packet has only been delayed rather than lost, the sender waits until it sees some number of duplicate ACKs and then retransmits the missing packet. In practice, TCP waits until it has seen three duplicate ACKs before retransmitting the packet

in the figure above, the destination receives packets 1 and 2, but packet 3 is lost in the network. Thus, the destination will send a duplicate ACK for packet 2 when packet 4 arrives, again when packet 5 arrives, and so on. (To simplify this example, we think in terms of packets 1, 2, 3, and so on, rather than worrying about the sequence numbers for each byte) When the sender sees the third duplicate ACK for packet 2—the one sent because the receiver had gotten packet 6—it retransmits packet 3. Note that when the retransmitted copy of packet 3 arrives at the destination, the receiver then sends a cumulative ACK for everything up to and including packet 6 back to the source.

Trace of TCP with Fast Retransmit

Figure 6.13 illustrates the behavior of a version of TCP with the fast retransmit mechanism. It is interesting to compare this trace with that given in Figure 6.11, where fast retransmit was not implemented—the long periods during which the congestion window stays flat and no packets are sent has been eliminated. However, given enough lost packets (e.g. during the initial slow start phase 0-2 seconds) the sliding window algorithm eventually blocks the sender until a timeout occurs

Fast Recovery

  • effectively removes the slow start phase that happens between when fast retransmit detects a lost packet and additive increase begins (note that fast-retransmit detection of lost packet is different than a timeout)
  • e.g. fast recovery avoids the slow start period between 3.8 and 4 seconds in Figure 6.13 and instead simply cuts the CongestionWindow in half (from 22 KB to 11 KB) and resumes additive increase. In other words, slow start is only used at the beginning of a connection and whenever a timeout occurs. At all other times, the congestion window is following a pure multiplicative decrease pattern

Congestion Avoidance Mechanisms

congestion-avoidance mechanisms:

DECbit

Each router monitors the load and explicitly notifies the end nodes when congestion is about to occur by setting a DECbit in the packets that flow through the router. The destination host then copies this bit into the ACK and sends back to the source. Finally, the source adjusts its sending rate so as to avoid congestion:

  • If less than 50% of the packets had the bit set, then the source increases its congestion window by 1
  • If 50% or more of the last window’s worth of packets had the congestion bit set, then the source decreases its congestion window to 0.875 times the previous value
Random Early Detection (RED)

RED differs from the DECbit scheme in 2 ways:

  1. rather than explicitly sending a DECbit to source, it implicitly notifies the source by dropping one of its packets. i.e. the router drops a few packets before it has exhausted its buffer space completely, so as to cause the source to slow down, with the hope that this will mean it does not have to drop lots of packets later on.
  2. deciding when to drop a packet and what packet it decides to drop - consider a simple FIFO queue:
    1. in DECbit we wait for the queue to become full and then be forced to drop each arriving packet
    2. in RED we decide to drop each arriving packet with some drop probability whenever the queue length exceeds some drop level
AvgLen = (1 − Weight) × AvgLen + Weight × SampleLen

if AvgLen ≤ MinThreshold
	→ queue the packet
if MaxThreshold ≤ AvgLen
	→ drop the arriving packet

TempP = MaxP × (AvgLen − MinThreshold)/(MaxThreshold − MinThreshold)
P = TempP/(1 − count × TempP)

if MinThreshold < AvgLen < MaxThreshold
	→ calculate probability P
	→ drop the arriving packet with probability P
weight
  • 0 < Weight < 1
  • Weight determines the time constant of the filter
count
  • count keeps track of how many newly arriving packets have been queued (not dropped), and AvgLen has been between the two thresholds. P increases slowly as count increases, thereby making a drop increasingly likely as the time since the last drop increases. This makes closely spaced drops relatively less likely than widely spaced drops. This extra step in calculating P was introduced by the inventors of RED when they observed that, without it, the packet drops were not well distributed in time but instead tended to occur in clusters. Because packet arrivals from a certain connection are likely to arrive in bursts, this clustering of drops is likely to cause multiple drops in a single connection. This is not desirable, since only one drop per round-trip time is enough to cause a connection to reduce its window size, whereas multiple drops might send it back into slow start
  • count is re-initialized to zero each time RED drops a packet
  • e.g. suppose that we set MaxP to 0.02 and count is initialized to zero. If the average queue length were halfway between the two thresholds, then TempP, and the initial value of P, would be half of MaxP, or 0.01. An arriving packet, of course, has a 99 in 100 chance of getting into the queue at this point. With each successive packet that is not dropped, P slowly increases, and by the time 50 packets have arrived without a drop, P would have doubled to 0.02. In the unlikely event that 99 packets arrived without loss, P reaches 1, guaranteeing that the next packet is dropped. The important thing about this part of the algorithm is that it ensures a roughly even distribution of drops over time

Consider the setting of the two thresholds: MinThreshold and MaxThreshold

If the traffic is fairly bursty, then MinThreshold should be sufficiently large to allow the link utilization to be maintained at an acceptably high level. Also, the difference between the two thresholds should be larger than the typical increase in the calculated average queue length in one RTT. Setting MaxThreshold to twice MinThreshold seems to be a reasonable rule of thumb given the traffic mix on today’s Internet. In addition, since we expect the average queue length to hover between the two thresholds during periods of high load, there should be enough free buffer space above MaxThreshold to absorb the natural bursts that occur in Internet traffic without forcing the router to enter tail drop

Consider the setting of the Weight Parameter

We noted above that Weight determines the time constant for the running average low-pass filter, and this gives us a clue as to how we might pick a suitable value for it. Recall that RED is trying to send signals to TCP flows by dropping packets during times of congestion. Suppose that a router drops a packet from some TCP connection and then immediately forwards some more packets from the same connection. When those packets arrive at the receiver, it starts sending duplicate ACKs to the sender. When the sender sees enough duplicate ACKs, it will reduce its window size. So, from the time the router drops a packet until the time when the same router starts to see some relief from the affected connection in terms of a reduced window size, at least one round-trip time must elapse for that connection. There is probably not much point in having the router respond to congestion on time scales much less than the round-trip time of the connections passing through it. As noted previously, 100 ms is not a bad estimate of average round-trip times in the Internet. Thus, Weight should be chosen such that (changes in queue length over time scales much less than 100 ms) are filtered out.

Source-Based Congestion Avoidance

Observation 1: as packet queues build up in the network’s routers, there is a measurable increase in the RTT for each successive packet it sends

1st Algorithm Exploiting Observation 1

the congestion window normally increases as in TCP, but every two round-trip delays the algorithm checks to see if the current RTT is greater than the average of the minimum and maximum RTTs seen so far. If it is, then the algorithm decreases the congestion window by one-eighth

2nd Algorithm Exploiting Observation 1

the decision as to whether or not to change CurrentWindow is based on changes to both the RTT and CurrentWindow

CurrentWindow is adjusted once every 2 RTT based on the product:

(CurrentWindow − OldWindow) × (CurrentRTT − OldRTT)

following algorithm is as follows

CurrentRTT = get-current-rtt()

value = (CurrentWindow − OldWindow) × (CurrentRTT − OldRTT)

OldWindow = CurrentWindow
OldRTT = CurrentRTT

if value > 0:
	CurrentWindow *= 7/8
else:
	CurrentWindow += maximum-segment-size

the window changes during every adjustment; that is, it oscillates around its optimal point

Observation 2: as the network approaches congestion the sending rate flattens

3rd Algorithm Exploiting Observation 2

every RTT, it increases the window size by 1 packet/mss and compares the throughput achieved to the throughput when the window was one packet smaller. If the difference is less than one-half the throughput achieved when only one packet was in transit—as was the case at the beginning of the connection—the algorithm decreases the window by one packet. throughput is calculated by dividing the number of bytes outstanding in the network by the RTT

at each round-trip time
	CurrentWindow += mss
	throughput = num-outstanding-bytes() / get-rtt()

// TODO: I don't clearly understand...
4th Algorithm (TCP Vegas) Exploiting Observation 2

similar to the 3rd algorithm in that it looks at changes in the throughput rate or, more specifically, changes in the sending rate. However, it differs from the third algorithm in the way it calculates throughput, and instead of looking for a change in the slope of the throughput it compares the measured throughput rate with an expected throughput rate. The algorithm, TCP Vegas, is not widely deployed in the Internet, but the strategy it takes continues to be studied

  • top graph - traces the connection’s congestion window
  • middle graph - shows the average sending rate as measured at the source
  • bottom graph - shows the average queue length as measured at the bottleneck router

the period between 4.5 and 6.0 seconds (shaded region), the congestion window increases (top graph). We expect the observed throughput to also increase, but instead it stays flat (middle graph). This is because the throughput cannot increase beyond the available bandwidth. Beyond this point, any increase in the window size only results in packets taking up buffer space at the bottleneck router

TCP Vegas Algorithm
  1. Calculate Normal/Base RTTBaseRTT = the RTT of a packet when the flow is not congested. In practice, TCP Vegas uses the minimum of all measured round-trip times; it is commonly the RTT of the first packet sent by the connection, before the router queues increase due to traffic generated by this flow
  2. Calculate Expected Throughput 
    ExpectedRate = CongestionWindow / BaseRTT
  3. Calculate Actual Throughput
    ActualRate = is done by recording the sending time for a distinguished packet, recording how many bytes are transmitted between the time that packet is sent and when its acknowledgment is received, computing the sample RTT for the distinguished packet when its acknowledgment arrives, and dividing the number of bytes transmitted by the sample RTT. This calculation is done once per round-trip time
  4. Compare ActualRate to ExpectedRate & Adjust Window Accordingly
    define two thresholds, α < β, roughly corresponding to having too little and too much extra data in the network, respectively 
    Diff = ExpectedRate − ActualRate

if Diff < α:
	// congestion window increases linearly
	CongestionWindow++
else if Diff > β:
	// congestion window decreases linearly
	CongestionWindow--
else if α < Diff < β:
	// CongestionWindow is left unchanged

overall goal is to keep between α and β extra bytes in the network

traces of the TCP Vegas congestion-avoidance algorithm

top graph - traces the congestion window

bottom graph - traces the expected and actual throughput rates

  • ExpectedRate - colored line
  • ActualRate - black line
  • α and β thresholds - shaded strip

the goal is to keep the ActualRate between these two thresholds, within the shaded region.

  • whenever ActualRate falls below the shaded region (i.e., gets too far from ExpectedRate), TCP Vegas decreases the CongestionWindow because it fears that too many packets are being buffered in the network
  • whenever ActualRate goes above the shaded region (i.e., gets too close to the ExpectedRate), TCP Vegas increases the CongestionWindow because it fears that it is underutilizing the network
  • whenever CongestionWindow is changed, the ExpectedRate is recalculated(ExpectedRate = CongestionWindow / BaseRTT)

TCP Vegas does use multiplicative decrease when a timeout occurs; the linear decrease just described is an early decrease in the congestion window that should happen before congestion occurs and packets start being dropped

Quality of Service (QoS)

real-time applications

  • applications that are sensitive to the timeliness of data
  • need some sort of assurance from the network that data is likely to arrive “on time”

Taxonomy of Applications

  • non-real-time (aka traditional data or elastic) - not concerned with the timeliness of data
  • real-time - concerned with the timeliness of data
    • intolerant - cannot tolerate occasional loss/late
    • tolerant - can tolerate occasional loss/late
      • non-adaptive - cannot adapt to networks changing delay and/or bandwidth
      • adaptive - can adapt to the networks changing delay and/or bandwidth
        • rate adaptive - exchanging bitrate vs quality
        • delay adaptive - changing the playback point

Quality of Service Submodels

subclasses of the CN - Chapter 6 - Congestion Control and Resource Allocation:

  • guaranteed service class
    • designed for intolerant applications
  • controlled load service class
    • meet the needs of tolerant adaptive applications
    • uses a queuing mechanism such as weighted fair queuing (WFQ)to isolate controlled load traffic from the other traffic
    • uses some form of admission control to limit the total amount of controlled load traffic on a link such that the load is kept reasonably low

Categories of QoS Model Support

Integrated Services

  • a fine-grained approach that provides QoS to individual applications or flows
  • defined a number of service classes to meet the needs of some of the application types
  • defined how RSVP makes reservations using these service classes

Overview of Mechanisms

  • pieces involved in supporting best-effort service:
    1. just tells the network where we want the packets to go
  • pieces involved in supporting real-time service:
    1. flowspec - involves telling the network about the type of service we required
      • may give:
        • qualitative information such as “use a controlled load service”
        • quantitative information such as “I need a maximum delay of 100 ms”
    2. admission control - network decides if it can provide that service at that moment
    3. resource reservation - mechanism by which the users of network and the components of network exchange information such as: requests for service, flowspec, and admission control decisions
    4. packet scheduling - managing the way packets are queued and scheduled for transmission in switches and routers
Flowspec

2 parts of flowspec:

  • RSpec - part that describes the requested service
  • TSpec - part that describes the flow’s traffic characteristics
    • token bucket filter - a way to describe the bandwidth characteristics of sources. contains 2 parameters:
      • token rate
      • bucket depth

Admission Control
  • idea of admission control: When some new flow wants to receive a particular level of service, admission control looks at the TSpec and RSpec of the flow and tries to decide if the desired service can be provided to that amount of traffic, given the currently available resources, without causing any previously admitted flow to receive worse service than it had requested. If it can provide the service, the flow is admitted; if not, then it is denied
  • for guaranteed service - uses weighted fair queuing (WFQ)
  • admission control vs policing
    • admission control - per-flow decision to admit a new flow or not
    • policing - per-packet basis to make sure that a flow conforms to the TSpec that was used to make the reservation
Reservation Protocol
  • one implementation is the RSVP
RSVP
  • receiver-oriented
  • maintains a soft state in routers
  • each receiver periodically sends refresh messages to keep the soft state in place
  • In the event of a host crash, resources allocated by that host to a flow will naturally time out and be released
  • 2 things that need to happen before a receiver can make the reservation:
    1. the receiver needs to know what traffic the sender is likely to send so that it can make an appropriate reservation. That is, it needs to know the sender’s TSpec.
    2. it needs to know what path the packets will follow from sender to receiver, so that it can establish a resource reservation at each router on the path
  • both of these requirements can be met by sending a message from the sender to the receiver that contains the TSpec
  • Having received a PATH message, the receiver sends a reservation back up the multicast tree in a RESV message. This message contains the sender’s TSpec and an RSpec describing the requirements of this receiver. Each router on the path looks at the reservation request and tries to allo- cate the necessary resources to satisfy it. If the reservation can be made, the RESV request is passed on to the next router. If not, an error message is returned to the receiver who made the request. If all goes well, the cor- rect reservation is installed at every router between the sender and the receiver. As long as the receiver wants to retain the reservation, it sends the same RESV message about once every 30 seconds

    List indent undo

Packet Classifying and Scheduling
  • for routers to deliver the requested service to the data packets, there are 2 things:
    • classifying packets - associate each packet with the appropriate reservation so that it can be handled correctly
    • scheduling packets - manage packets in the queues so that they receive the service that has been requested

Differentiated Services

  • a coarse-grained approach that provides QoS to classes of data or aggregated traffic
  • rather than using RSVP to tell all the routers that some flow is sending premium packets, it would be better if the packets identify themselves to the router when they arrive
  • with this approach, there are 2 questions:
    • who sets the premium bit and under what circumstances
      • common approach is at an administrative boundary
    • what does a router do differently when it sees a packet with the bit set

Expedited Forwarding (EF) PHB

  • packets marked for EF treatment should be forwarded by the router with minimal delay and loss
  • several possible implementations:

Assured Forwarding (AF) PHB

  • similar to CN - Chapter 6 - Congestion Control and Resource Allocation with a twist: RED In and Out (RIO) or Weighted RED (WRED)
    • RED In and Out (RIO) - packets are differentiated into 2 categories: IN packets have higher priority & OUT has lower priority
    • Weighted RED (WRED) - packets can be differentiated into multiple categories
  • figure 6.26 shows how RIO works. the probability on the y-axis increasing as average queue length increases along the x-axis

    List indent undo

  • the idea of RIO can be generalized to provide more than two drop probability curves, and this is the idea behind the approach known as weighted RED (WRED)

Equation-Based Congestion Control

  • several so called TCP-friendly congestion-control algorithms have been proposed. These algorithms have two main goals:
    • slowly adapt the congestion window. done by adapting over relatively longer time periods (e.g. over RTT rather than on per-packet basis)
    • being fair to competing TCP flows