120	CLASS OF SERVICE AND QUALITY OF SERVICE

require vast numbers of queues. In this environment, CoS and QoS are applied to highly aggregated flows of data.

9.2 CoS/QoS FUNCTIONAL ELEMENTS

CoS and QoS are pretty generic terms. However, there are a number of functional elements required for a full CoS/QoS implementation.

9.2.1 CLASSIFICATION

In order for one class of traffic to be treated preferentially over a different class of traffic, it is clearly necessary to be able to identify traffic that falls into each of the following classes:

•Ingress classification. Classification is generally carried out as close to the edge of the network as possible. Ideally, this would be right out at the host sourcing the packet. However, allowing customers to set the class of a particular packet would potentially cause problems if not adequately monitored. Consider the situation where you offer four service levels to your customers (e.g. gold, silver, bronze and best efforts) and that gold obtains better service than silver, which obtains better service than bronze, which obtains better service than best efforts. If you leave it entirely up to your customers and apply no monitoring or reclassification at your borders, it is highly likely that your customers will associate all packets with the gold class of service.

•Per-hop classification. Despite the fact that a classification is applied at the ingress to the network, it is still necessary to perform a classification function as each packet arrives at each network device. If the ingress classification has been recorded in the Layer 2 or Layer 3 headers of the packet, then the process of classification is simple. If the classification has not been marked, then a complete reclassification exactly as at the ingress to the network must be completed at each step.

•Rewriting on egress. The default behaviour with all the QoS mechanisms is to leave the CoS/QoS markings exactly as they were when the packet arrived at the device. However, there are a number of situations when it is desirable to modify the marking of the packet before it is transmitted. The obvious example is at the point where the packet is initially classified. The packets arrive with no classification markings. Then, through some arbitrary classification process, they are identified as belonging to a particular class. If you do not want to have to reclassify each packet at each hop throughout the network based on those arbitrary criteria, it is necessary to modify the QoS marking. This allows subsequent devices along the path to trivially identify the class into which packets should be placed.

9.2 CoS/QoS FUNCTIONAL ELEMENTS

121

9.2.2CONGESTION NOTIFICATION MECHANISMS

Despite all your best efforts, it is almost inevitable that your network will experience congestion at some point, even if it is only on the lower bandwidth links to your customers. It is extremely useful to be able to inform the source and, to a lesser extent, the destination that there is some congestion in the path between them. This notification provides the information based upon which the end hosts can modify their behaviour. Retransmission of lost data can actually exacerbate congestion because the packets that previously could not be transmitted are retransmitted in addition to the new data.

For example, I have seen traffic load on a new circuit drop by as much as 25% when a massively over-provisioned link was substituted for a significantly over-subscribed link. A pair of E2 (8 Mbps) links was struggling hard trying to carry an offered load of 20 Mbps between two routers. When these two links were replaced with a single STM-1 POS link, the total traffic over the link dropped to around 15 Mbps.

9.2.2.1 Implicit Congestion Notification

Several protocols rely upon an acknowledgement (ACK) being sent for each packet received. The loss of a packet, or of the acknowledgement packet, will be noted by the transmitting host and it will send the packet again. However, it is implicit in the loss of the packet that there is congestion somewhere on the path from source to destination or on the return path. Since there is congestion, the transmitting host can slow down (the mechanism used to slow down the transmission is protocol specific). If an ACK is dropped, then the receiver will receive a second copy of the transmitted packet. It can also, therefore, assume that its ACK for that packet was dropped, probably due to congestion in the path back to the source. On receipt of the duplicate packet, the destination can slow down the speed at which it transmits packets back to the source.

9.2.2.2 Explicit Congestion Notification

Implicit congestion notification is effective only in protocols that require ACKs and that adapt their behaviour to the loss of packets. Many protocols simply do not use ACKs so an alternative mechanism is required. They can use explicit congestion notification (ECN) techniques to inform both source and destination of the congestion. These messages are sent to both source and destination by the device on which congestion is experienced.

These notification messages are sent back to the source in packets travelling in the reverse direction. In TCP packets, ECN can be marked using the two high-order bits of the ToS byte. Bit 6 is the ECN capable transport (ECT) bit that is used to identify a source as capable of responding to ECN messages. Bit 7 is the congestion experienced (CE) bit, which is set by the router on which congestion was identified. This is rarely implemented. The DiffServ standard for the use of the ToS byte describes bits 6 and 7 as unused.

122	CLASS OF SERVICE AND QUALITY OF SERVICE

ECN is more widely implemented in ATM and Frame Relay switches. Frame Relay uses 3 bits for forward explicit congestion notification (FECN), backward explicit congestion notification (BECN) and discard eligible (DE). FECN and BECN are set by the data communication equipment (DCE) on which congestion occurred to inform data terminating equipment (DTE) of the congestion. FECN indicates that traffic arriving at the DTE experienced congestion. BECN indicates that traffic transmitted by the DTE experienced congestion. DE is set by the source DTE to provide a very crude mechanism to identify lower priority traffic that can be dropped by the DCE in preference to other, nominally higher priority, packets.

In TCP, BECN packets are sent in the ACK packets sent back to the source and on that basis, the source can slow down. However, with UDP packets, there are no inherent replies (no ACKs) so there are no packets in which to set the BECN and the source cannot be informed of the congestion. In order to overcome this, on receipt of the packet with the FECN bit set, the DTE can send a test frame back towards the source with the BECN bit set. The DE bit in these test frames must be cleared to minimize the chance of that test frame being dropped.

9.2.3 CONGESTION AVOIDANCE MECHANISMS

The whole reason for QoS and CoS is to make a selection between packets when two or more packets require transmission at the same time but there are insufficient resources to transmit both. This is known as congestion and, while it is possible to deal with congestion after it has happened, it is better to avoid the situation in the first place. Congestion avoidance mechanisms make use of features of the protocols to cause certain arbitrarily selected flows to slow down their transmission speed.

9.2.3.1 Random Early Detect

When left unchecked, an over-subscribed link will tend to see a throughput pattern characterized by the graph in Figure 9.1.

This effect is known as global synchronization. It is caused by the synchronization of the reduction and expansion of TCP window sizes in all (or a significant proportion of) the flows traversing the link. As the utilization approaches 100%, the buffers start to drop packets from the rear of the buffer as there is no room to buffer the packets requiring transmission. This is known as tail dropping and is the worst possible form of dropping because of the inherent lack of control over the process. High-priority packets are dropped with equal preference to low priority packets. As packets are dropped, the TCP sources start to notice that they are not receiving TCP acknowledgements (ACKs) for transmitted packets. This causes them to reduce their TCP window size, thus reducing the volume of traffic being transmitted. As the link becomes even more heavily over-subscribed, many flows are simultaneously affected and they all reduce their window size simultaneously. This causes the link to become dramatically under-utilized. Gradually, all the flows will increase their window size and the utilization approaches 100%. This starts the whole process again

9.2 CoS/QoS FUNCTIONAL ELEMENTS

123

100

percent max throughput

0

time

Figure 9.1 Global TCP synchronization

causing a clipped sinusoidal throughput over time. This makes the overall throughput of the link significantly less than could be carried if global synchronization did not occur.

Random Early Detect (a.k.a. Random Early Discard) uses the windowing mechanism of TCP to cause source hosts to slow down. By dropping randomly selected packets, RED prevents the receiver of the TCP flow from receiving the packet and, therefore, prevents the receiver from sending an ACK. When the TCP source does not receive an ACK for the discarded packet, it reduces its window size. This effectively reduces the throughput of the flow.

The random nature of the selection of packets to be discarded means that no single flow is unduly affected. However, the overall impact is to round off the growth of traffic flowing over a particular link (see Figure 9.2). The maximum utilization of the link is slightly below 100% because packets are dropped more aggressively as the utilization approaches 100%.

100

percent

max

throughput

0

time

Figure 9.2 Output with RED applied