项目经理案头手册:computer networks --systems and approaches

6.2 queuing disciplines

The queuing algorithm can be thought of as allocating bandwidth and buffer space. Also affects the latency.

6.2.1 FIFO

Also called first come first served (FCFS).

FIFO is scheduling discipline.

Tail drop is drop policy.

FIFO with tail drop is the most widely used in internet routers.

TCP takes responsibility for detecting and responding to congestion.

A simple variation on basic FIFO queuing is priority queuing.

Problem: the high-priority queue can starve out all the other queues.

Internet is to protect the most important packets, such as the routing updates.

6.2.2fair queuing

Problems of FIFO queuing:

It does not discriminate between different traffic sources, or it does not separate packets according to the flow to which they belong.

Any host-based congestion control algorithm will be able to adequately control congestion.

FIFO queuing provide no means to police how well the sources adhere to this mechanism, it is possible for an ill-behaved source(flow) to capture an arbitrarily large fraction of the network capacity.

Fair queuing (FQ):

Maintain a separate queue for ach flow. The router services these queues in a sort of round-robin.

A given source cannot arbitrarily increase its share of the network’s capacity at the expense of other flows.

It is necessary to take packet length into consideration: bit-by-bit round-robin.

(2011-08-29)

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

We want time to advance by one tick each time all the active flows get one bit of service under bit-by-bit round-robin, so we need a special clock.

We treat all the Fi as timestamps, and the next packet to transmit is always the packet with lowest timestamp.

A newly arriving packet cannot preempt a packet that is currently being transmitted.

Two things to notice:

Work-conserving: the link is never left idle as long as there is at least one packet in the queue.

If the link is fully loaded and there are n flows sending data, I cannot use more than 1/nth of the link bandwidth.

Weighted fair queuing(WFQ):

Allows a weight to be assigned to each flow(queue).

A rather weak form of reservation

The discussion of queue management illustrates an important system design principle known as separating policy and mechanism.

6.3 TCP congestion control

The essential strategy of TCP is to send packets into the network without a reservation and then to react t the observable events that occur.

TCP assumes only FIFO queuing in the network’s router, but also works with fair queuing.

In 1980s, the internet was suffering from congestion collapse.

It uses an ACK as a signal that one of its packets has left the network, so it is safe to insert a new packet into the network without adding to the level of congestion.

By using ACKs to pace the transmission of packets, TCP is said to be self-clocking.

6.3.1 Additive increase/multiplicative decrease (AIMD)

Congestion window

Maxwindow = min(congestionwindiow, advertisedwindow)

Effectivewindow = maxwindow – (lastbytesent - lastbyteaacked)

TCP interprets timeouts as a sign of congestion and reduces the rate at which it is transmitting.

Each time a timeouts occurs, the source sets congestionwindow to half of its previous value.

Each time the source successfully sends a congestionwindow’s worth of packets, it adds the equivalent of 1 packet to congestionwindow.

Increment = MSS*(MSS/congestionwindow)

Congestiongwindow += increment

TCP needs the most accurate timeout mechanism it can afford.

Two main things to remember about the timeout mechanism:

(1)    Timeout are set as a function of both the average RTT and the standard deviation in that average.

(2)    Due to the cost of measuring each transmission with an accurate clock, TCP only samples the round-trip time once per RTT using a coarse-grained clock.

6.3.2 slow start

Even though its exponential growth is faster than linear growth, slow start is much slower than sending an entire advertised window’s worth of data at once.

There are two situations slow start runs in:

The very beginning of a connection.

The connection goes dead while waiting for a timeout to occur.

Congestionthreshold

Congestionwindow flatten

Behavior of tcp congesting control:

A timeout happens, congestion window to be divided by 2, and set to congestion threshold

Congestion window is reset to one packet, and enters slow start

Congestion window grow exponentially until it reaches congestion threshold

Congestion window then grow linearly

Too many packets buffered in some router will be an increasingly severe as the delay * bandwidth product of networks increases.

Quick start: a TCP sender can ask for an initial sending rate greater than slow start would allow. If one or more routers could not support the quick start request, it falls to standard slow start.

6.3.3 fast retransmit and fast recovery

When a packet arrives out of order, TCP resends the same ACK it sent the last time.

TCP waits until it has seen three duplicate ACKs before retransmitting the packet.

This technique is able to eliminate about half of the coarse-grained timeouts on a typical TCP connection, resulting in roughly a 20% improvement in the througthput over what could otherwise have been achieved.

Fast recovery: when fast retransmit detects a lost packet , simply cuts the congestion window in half and resumes additive increase.

slow start is only used at the beginning of a connection and whenever a coarse-grained timeout occurs. At all other times, the congestion window is following a pure additive increase/multiplicative decrease pattern.

A fast TCP

There was the claim that TCP was too complex to run fast in host software as networks headed toward the gigabit range

The “high-speed TCP” proposal

The “Quick start” proposal

end>

6.4 congestion-avoidance mechanisms

Predict when congestion is about to happen and then to reduce the rate at which hosts send data just before packets start being discarded.

6.4.1 DECbit

Each router monitors the load it is experiencing and explicitly notifies the end nodes when congestion is about to occur, by setting binary congestion bit in the packets.

The source host: “increase by 1, decrease by 0.875” rule

6.4.2 random early detection (RED)

Each router monitors its own queue length, and when it detects that congestion is imminent, to notify the source to adjust its congestion window implicitly.

RED implicitly notifies the source of congestion by dropping one of its packets.

RED drops each arriving packet with some drop probability whenever the queue length exceeds some drop level. (early random drop)

Originally proposed RED algorithm:

Avglen = (1-weight)*avglen+weight*samplelen

Using an average queue length rather than an instantaneous one is that it more accurately captures the notion of congestion.

The weight running average calculation tries to detect long-lived congestion.

tempP=maxP*(avglen-minthreshold)/(maxthreshold-minthreshold)

P = tempP/(1-count*tempP)

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.

“Unresponsive flow”

Explicit congestion notification (ECN)

Dropping a packet is probably the right things for long-lived bulk transfers, while hurts applications that are sensitive to the delay or loss of one or more packets.

end>

6.4.3 source-based congestion avoidance

Watch for some sign from the network that some router’s queue is building up and that congestion will happen soon if nothing is done about it.

For example:

1) Checks to see if the current RTT is greater than the average of the minimum and maximum RTTs seen so far.

2) (currentwindow-oldwindow)*(currentRTT-oldRTT)

If the result is positive, the source decreases the window size by one-eighth; else increases one maximum packet size.

3) compares the new throughput to the old throughput

4) TCP vegas: compare the measured throughput rate with an expected throughput rate.

Expectedrate = congestionwindow/baseRTT

Actualrate =

Diff = expectedrate – actualrate

TCP vegas uses multiplicative decrease when a timeout occurs; the linear decrease is an early decrease in the congestion window that happens before congestion occurs and packets start being dropped.

6.5 Quality of Service

Real-time application

Non-real-time application can use an end-to-end retransmission strategy to make sure that data arrives correctly.

Timely arrival must be provided by network itself(the routers), not just at the network edges(the hosts).

Best effort model is not sufficient for real-time app…

QoS model: the network will treat some packets differently from others.

6.5.1 Application requirements

Elastic appl…

(1) Real-time audio example

At the receiving host, the data must be played back at some appropriate rate.

It is difficult to guarantee that all data traversing a packet-switched network will experience exactly the same delay.

Playback buffer: Buffer up some amount of data in reserve.

Playback point

Figure 6.22 example distribution of delays for an internet connection.

(2) taxonomy of real time appl…

Tolerant, adaptive

(3) approache to QoS support

Fine-grained approaches: RSVP, ATM’s approach to QoS

Coarse-grained approaches: differentiated services

6.5.2 integrated services (RSVP)

IntServ

Service classes

(1) service classes

Intolerant application, guaranteed service

Controlled load service

(2) overview of mechanisms

tell the network the flowspec.

Admission control: deciding when to say no

Resource reservation: a mechanism by which the users of network and the components of the network itself exchange info…, using resource reservation protocol

Packet scheduling: managing the way packets are queued and scheduled for transmission in the switched and routers.

(3) flowspecs

TSpec: describe flow’s traffic characteristics

RSpec: describe service requested form the network

Token bucket: describe the bandwidth characteristics of sources

Token rate r, bucket depth B

(4) admission control

When to say yes and no

Don’t confuse with policing, admission control is a per-flow decision to admit a new flow or not.

Related to the issue of policy.

Policy and resource availability may both be addressed when admission control decisions are made.

(5) reservation protocol

RSVP

Maintain robustness by using soft state, which does not need to explicitly deleted when it is no longer needed. soft state times out after some fairly short period if it is not periodically refreshed.

Support multicast flows just as effectively as unicast flows.

Receiver-oriented approach is adopted by RSVP: the receivers keep track of their own needs.

Connection-oriented networks usually leave resource reservation to the sender.

It is very straightforward to increase or decrease the level of resource allocation provided to a receiver.

PATH msg, figure out reverse path

RSEV msg: the receiver wants to retain the reservation

Routing protocols will adapt to the failure and create a new path from the sender to receiver.

How to cope with multicast?

(6) packet classifying and scheduling

Classifying packets

Packet scheduling

(2011-08-30)

(7) scalability issues

IntServ architecture andRSVP represented a significant enhancement of the best-effort service model of IP.

IntServ providers felt that it was not the right model for them to deploy for the scalability issues.

6.5.3 differentiated service (EF, AF)

Diffserv allocates resources to a small number of classes of traffic.

Packets could just identify themselves to the router when they arrive.

At an administrative boundary, some bit in the packet will be set for identifying itself.

Per-hop behaviors (PHBs)

Diffserv code point (DSCP)

(1) expedited forwarding (EF) PHB

Forward with minimal delay and loss

Rate limiting of EF packets is achieved by configuring the routers at the edge of an administrative domain to allow a certain maximum rate of EF packet arrivals into the domain.

Strategies for EF behavior:

Give EF packets strict priority over all other packets

Perform weight fair queuing between EF packets and other packets.

(2) assured forwarding (AF) PHB

RED with in and out (RIO)

Or weight RED

RIO has two separate drop probability curves.

A profile meter at the edge marks the customer’s packets “in” or “out”.

A third way to provide diffserv is to use the DSCP value to determine which queue to put a packet into in a weight fair queuing scheduler.

Use one code point to indicate the best-effort queue and a second to select the premium queue.

ATM quality of service

One of its real contributions was in the area of QoS.

Five service classes

end>

6.5.4 eqation-based congestion control

TCP itself is not appropriate for real-time applications.

One reason is the that TCP is reliable protocol.

What if add TCP-like congestion control to an unreliable protocol like UDP? Could real-time appl… make use of such a protocol?

Can we: compatibility with TCP congestion control for the sake of fairness, while sustaining a smooth transmission rate for the sake of the app…?

Recently:

TCP-friendly congestion control algorithms

Slowly adapt the congestion window.

Being fair to competing TCP flows:

Enforced by ensuring that the flow’s behavior adheres to an equation that models TCP’s behavior

Hence, called eqation-based congestion control

6.6 summary

Resource allocation

Congestion control

Different qualities of service

Congestion control mechanism: most targeted at the best effort model, host based, uses feedback

Routers, queuing algorithm

IntServ allows individual appl… flows to specify their needs to the routers.

DiffServ assigns packets into a small number of classes.

Open issue: inside versus outside the network

To be continue…

7 End-to-End Data

(coarsely read this chapter)

How to best encodes the different kinds of data

Presentation format

Efficiency of the encoding

Data Compression

Data manipulation functions

7.1 presentation formatting

Transformation

Encoding: argument marshalling

Decoding: unmarshalling

Big-endian form

Little-endian form

7.1 taxonomy

(1) data types

Base types, flat types, complex types

Argument marshalling usually involves converting the base types, packing the structures, and linearing the complex data structures, all to form a contiguous message that can be transmitted over the network.

(2) conversion strategy

Canonical intermediate form and receiver-makes-right

Canonical intermediate form: Settle on an external representation for each type.

receiver-makes-right: receiver translating the data to its own format. N-by-N solution

(3) tags

How to knows what kinds of data is contained in the msg.

Tagged data and untagged data

The untagged approach means that the presentation formatting is truly end-to-end. It is not possible for some intermediate agent to interpret the msg unless the data is tagged.

(4) stubs

A stub is the piece of code that implements argument marshalling.

7.1.2 examples (XDR, ASN.1, NDR)

ASN.1:

7.1.3 markup language (XML)

7.2 Data Compression

Some app… need to send more data in a timely fashion than bandwidth of the network supports.

Bandwidth limited

The idea of Huffman codes

Lossless compression and lossy compression

Considering the time spending on compress/decompress

7.2.1 lossless comprssion algorithm

(1) run length encoding ( RLE)

aaabbcddd >>3a2b1c4d

used to digital imaginary

(2) differential pulse code modulation

aaabbcdddd >> a0001123333

a slightly different approach: delta encoding:

aaabbcdddd >> a001011000

(3) dictionary-based methods

Lempel-Ziv (LZ)

7.2.2 image compression (JPEG)

Jpeg, gif and mpeg are more than just compression algorithm, they also define the format for image or video data.

Moving picture experts group

Remove interframe redundancy present in a video sequence.

Also encoding an audio signal with the video.

(1) frame types

I frames, intrapicture, can be decompressed at the receiver independently.

P frames

B frames

(2) effectiveness and performance

(3) other video encoding standards

7.2.4 transmitting MPEG over a network

MPEG defines the format of a video stream.

7.2.5 audio compression (MP3)

CD-quality audio: sampled at a rate of 44.1 KHz,16bits, 1.41Mbps stream

Telephone: sampled at 8KHz, 8bits, 64Kbps

MP3, used techniques that are similar to those used by MPEG to compress video.

8 Network Security

Adversary, eavesdrop, tamper, intercept, DNS attack

Confidentiality,

Integrity: Data integrity, originality, timelines

Availability: Authentication, access control, DoS attacks

Nonrepudiation, nonforgeability

8.1 cryptographic tools

Plaintext msg, ciphertext msg

Encryption, decryption

Cipher

Encryption and decryption functions should be parameterized by a key, and furthermore that the functions should be considered public knowledge, only the key need be secret.

There is considerable cost and risk in deploying a new cipher.

Parameterizing a cipher with keys provides us with what is in effect a very large family of ciphers; by switching the keys we essentially switch ciphers, thereby limiting the amount of data that a cryptanalyst can use to try to break our key/cipher, and the amount she can read if she succeeds.

A potential attacker receives a piece of ciphertext, he may have more info… at his disposal than just the ciphertext itself.

Known plaintext attack

Ciphertext only attack

Chosen plaintext attack

Block ciphers, electronic codebook(ECB) mode, a given plaintext block value will always result in the same ciphertext

Modes of operation:

cipher block chaining(CBC), XORed with previous block’s ciphertext, initialization vector (IV).

Counter mode, a counter are incorporated

8.1.2 symmetric-key ciphers

Data encryption standard (DES)

Triple DES (3DES)

3DES solves DES’s key-length problem, it inherits some shortcoming: software are slow

Advanced encryption standard (AES): support key lengths of 128, 192, or 256 bits, block length is 128 bits, permits fast implementations in both soft- and hard-ware, does not require much memory, suitable for small mobile devices.

8.1.3 public-key ciphers

Confidentiality

Authentication

Since 1976

Best-known: RSA, at least 1024bits

ElGamal, at least 1024bits

Sysmmtric-key ciphers are used for the vast majority of encryption, while public-key ciphers are reserved for use in authentication and session key establishment.

8.1.4 authentication

Authenticator, include redundant info… about the msg, some proof of a secret knowledge.

Encrypted msg digest

Cryptographic hash function, public knowledge, message digest

It must be computationally infeasible for an adversary to find any plaintext msg that has the same digest as the original.

Collision attacks

Message digest 5 (MD5), 128-bit digest, discovered techniques for finding MD5 collisions much more efficiently than brute force, and well within computational feasibility.

Secure hash algorithm 1 (SHA-1), 160-bit digest

Digest signature, digital signature standard (DSS),

Another authentator:

Hashlike function, msg authentation code (MAC): E(plaintext, secret value) >> MAC

E(plaintext+secret value) >> HMAC

Confidentiality: encrypt entire msg including its authenticator with symmetric-key ciphers for they are much faster than public key ciphers.

A common simplification is to encrypt the msg with its raw digest, in this case, the entire ciphertext msg is considered to be an authenticator.

8.2 key predistribution

Session key

Predistributed key

Session key establishment protocol

Motivation for division of labor between session keys and predistributed keys

8.2.1 predistribution of public keys

Public key infrastructure (PKI): certifying binding between public keys and identities, and bind them out-of-band

(2011-08-31)