Question

In: Computer Science

How the token buckets and WFQs can be used together to provide policing mechanisms. book: Computer...

How the token buckets and WFQs can be used together to provide policing mechanisms.

book: Computer networking: a top-down approach

Solutions

Expert Solution

The token bucket is an algorithm used in packet switched computer networks and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness.

The token bucket algorithm is based on an analogy of a fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e.g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e.g., for transmission. The packet does not conform if there are insufficient tokens in the bucket, and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:

  • They may be dropped.
  • They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket.
  • They may be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.

A conforming flow can thus contain traffic with an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket. This burstiness may be expressed in terms of either a jitter tolerance, i.e. how much sooner a packet might conform (e.g. arrive or be transmitted) than would be expected from the limit on the average rate, or a burst tolerance or maximum burst size, i.e. how much more than the average level of traffic might conform in some finite period.

Weighted fair queueing (WFQ) is a method of automatically smoothing out the flow of data in packet-switched communication networks by sorting packets to minimize the average latency and prevent exaggerated discrepancies between the transmission efficiency afforded to narrowband versus broadband signals. In WFQ, the priority given to network traffic is inversely proportional to the signal bandwidth. Thus, narrowband signals are passed along first, and broadband signals are buffered. It is a flow-based queuing algorithm that does two things simultaneously: It schedules interactive traffic to the front of the queue to reduce response time, and it fairly shares the remaining bandwidth between high bandwidth flows.

WFQ has little or no effect on the speed at which narrowband signals are transmitted, but tends to slow down the transmission of broadband signals, especially during times of peak network traffic. Broadband signals share the resources that remain after low-bandwidth signals have been transmitted. The resource sharing is done according to assigned weights. In flow-based WFQ, also called standard WFQ, packets are classified into flows according to one of four criteria: the source Internet Protocol address (IP address), the destination IP address, the source Transmission Control Protocol (TCP) or User Datagram Protocol (UDP) port, or the destination TCP or UDP port. Each flow receives an equal allocation of network bandwidth, hence the term fair.

WFQ can prevent high-bandwidth traffic from overwhelming the resources of a network, a phenomenon which can cause partial or complete failure of low-bandwidth communications during periods of high traffic in poorly managed networks.


Related Solutions

Evaluate and provide example of how hypothesis testing and confidence interval are used together in healthcare...
Evaluate and provide example of how hypothesis testing and confidence interval are used together in healthcare research. Also provide a workplace example that illustrates your ideas.
How can phylogenies be used to test a hypothesis? provide an example.
How can phylogenies be used to test a hypothesis? provide an example.
Analysis of how joints, muscles, and neuromuscular mechanisms work together to create squat movement.
Analysis of how joints, muscles, and neuromuscular mechanisms work together to create squat movement.
What types of information can variance analysis provide to the manager? How can it be used?...
What types of information can variance analysis provide to the manager? How can it be used? Give examples.
With different types of computer systems available, how can these be used to sustain competitive organizational...
With different types of computer systems available, how can these be used to sustain competitive organizational advantage?
What are the principal integrating mechanisms used in the organization? Do they provide sufficient coordination among...
What are the principal integrating mechanisms used in the organization? Do they provide sufficient coordination among individuals and functions? How might they be improved?
Provide an real life example of a confidence interval and how it can be used, listing...
Provide an real life example of a confidence interval and how it can be used, listing also advantages and disadvantages associated with it. (In 300 words or more)
Explain how forwards or futures can be used to manage risk. Provide an example of a...
Explain how forwards or futures can be used to manage risk. Provide an example of a hedge that uses a short futures position.   Why might you chose to use a put option as a hedge instead of a short futures position?
Can you provide an example on how a decision tree might be used in practice?
Can you provide an example on how a decision tree might be used in practice?
Define the term ‘goitrogen’ and provide two mechanisms by which a goiter can be formed. List...
Define the term ‘goitrogen’ and provide two mechanisms by which a goiter can be formed. List two consequences of hypothyroidism in an animal.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT