Uah Cs 470 Final (Dr. Zhu)

Front 1

Where is the transport layer located?

Back 1

-Applications: App, Pres
-Network OS: Sess, Trans, Net
-Hardware: DL, PHY

Front 2

3 Characteristics of UDP:

Back 2

-IP with ports
-Best effort (not reliable)
-Connectionless

Front 3

Why a Best Effort protocol?

Back 3

-Speed
-Simplicity

Front 4

UDP features that give simplicity and speed:

Back 4

Connectionless, so no pretransmit setup
Small Headers
-Unregulated flow rate, no error re-xmits
-stateless

16Bits 16Bits
Source Port Dest Port
Checksum Length
Payload

Front 5

UDP applications:

Back 5

Used for many apps where reliability is less critival than speed:
-streaming multimedia
-internet telephony
-DNS service

Front 6

TCP Extension:

Back 6

-32-bit Timestamp vs. RTT
-Extended SequenceNum
-Large AdvertisedWindow field

Front 7

How does congestion arise?

Back 7

•Router receives data faster than it can send it
-Downstream link or router congested or failed
-Extreme traffic on one output link

•Usually a transient condition, but crisis can occur if not relieved quickly
-Congestion cascades back into upstream routers
-Whole sections of the network can be blocked quickly

Front 8

Taxonomy 2 common strategies:

Back 8

–Best-effort
–QoS-based

Front 9

Congestion Indicators at routers:

Back 9

–Average queue lengths
–Number of dropped queue items
–Ping delay to neighbors

Front 10

Congetsion Indicators at senders, receivers:

Back 10

–Number of timeouts
–RTT (measured from data send to ACK receive)
–Ping delay
–Receive buffer fullness

Front 11

Generating additional traffic to report congestion makes the situation:

Back 11

worse –piggybacking on existing traffic is better

Front 12

Short timeouts lead to:

Back 12

needless re-transmits, aggravating congestion

Front 13

Queuing:

Back 13

•FIFO
•Tail drop
•Most widely used
–TCP takes responsibility
•Priority queuing
–Starving, low priority queues
–Charge

Front 14

Fair Queuing:

Back 14

–Separate queues for flows
–Packet length
–Bit-by-bit round-robin

Front 15

TCP Congetsion Control:

Back 15

•Send packet then observe for events
•Congestion -> retransmit packets -> more congestion
•Self clocking using ACKs

Front 16

Additive Increase/Multiplicative Decrease:

Back 16

•CongestionWindow
•Use MIN(CongestionWindow, AdvertisedWindow) in EffectiveWindow calculation
•Source perceives
–Packet dropped
--Multiplicative decrease
–Additive increase

Front 17

Fast Retransmit:

Back 17

•TCP waits 3 duplicate ACKs before retransmition

Front 18

Fast Recovery:

Back 18

•Cut congestion window in half

Front 19

“DEC bit” for Digital Network Architecture:

Back 19

•Router monitor load
•When a router is nearing overload, it sets a special “congestion bit” in the packets/segments it processes.
•The congestion bit is returned to senders as part of ACKs
•When a sender sees congestion bit set, it can reduce send rate to that destination

Front 20

Random Early Deletion (RED):

Back 20

•Designed to work with TCP Congestion Window approach
•Router implicitly notify source
–When router nears overload, it starts randomly dropping packets
•This triggers timeouts, which will ultimately cause congestion window size to be reduced.
•Drop probability
–Early random drop

Front 21

Source-based control (TCP-Vegas):

Back 21

•No new requirements on routers, source-based
•Sending TCP determines “no-congestion” RTT (usually determined by ACK for first seg to a destination)
•Dynamic RTT (measured from ACKs) is compared to no-congestion RTT.
•As RTT increases, CW_size is reduced

Front 22

The Idea of Data Compression:

Back 22

Compressing a data item so it will take less time to send

Front 23

Lossless compression:

Back 23

–The original data can be perfectly recovered by decompression.
–Needed for text files, code, executables…

Front 24

Lossy compression:

Back 24

–The original data cannot be exactly recovered.
–OK for photos, video, voice…
--Usually achieve much better compression ratios

Front 25

Run-Length Encoding (lossless):

Back 25

•The idea: Replace runs of a symbol with one copy of the symbol + the count.
•Example:
–“AAAABCCCDD” (10 symbols) A4BC3D2 (7 symbols)
•Good where there are long runs of a symbol (faxes, .bmp images…)
•Typical Performance:
–For scanned text, 8:1 compression is common

Front 26

Huffman encoding (lossless):

Back 26

The idea: Instead of using the same number of bits for every symbol in a string, we encode each symbol with a number of bits that is inversely proportional to the symbol’s frequency in the string.

Front 27

Huffman Encoding Example:

Back 27

1000-symbol string
With 4 symbols
Frequency:
A 30%
B 50%
C 15%
D 5%
--------------------------------
Normal encoding
A 00
B 01
C 10
D 11

Total bits 2000
----------------------------------
Huffman encoding
A 012x300 = 600 bits
B 01x500 = 500 bits
C 0113x150 = 450 bits
D 01114x50 = 200 bits

Total bits 1750

Front 28

Pulse-Code Modulation (Differential) (lossless)

Back 28

•The idea: Symbols are encoded based on their “distance” from a reference symbol.

•Effective when adjacent symbols are “similar” (e.g, imagery)

Front 29

Pulse-Code Modulation (Differential) Example:

Back 29

–ASCII Source string = “AAABCCDDEGF” (88 bits)
–We choose to encode symbols with 8 bits and distances with 2 bits (when the distance becomes greater than 3, choose a new base symbol).
–Encoded string = “A0012233E21”
Number of bits = 82222222822(35 bits)

Front 30

Dictionary methods (Lempel-Ziv) (lossless):

Back 30

•The idea: Build a dictionary of the “phrases” in the source. Assign each phrase a number and transmit the numbers. (phrases can be anything –fixed # characters, words in a language…)
•Note: you either must have a standard dictionary, or you must send the dictionary along with the encoded string
•Effective when the number of phrases is small relative to the length of the string.
•Used in Unix “Compress” and Windows “Zip”

Front 31

Dictionary methods (Lempel-Ziv) Example:

Back 31

“one small step for man one giant leap for mankind” (392 bits in ASCII)
--------------------------------------------------------------------
Dictionary
one_000
small_001
step_010
for_011
man_100
giant_101
leap_110
mankind_111
---------------------------------------------------------------------
Encoded form: 000 001 010 011 100 000 101 110 011 111 -> 30 bits
If you must send the dictionary, you have an additional 42 characters ->336 bits
So, for standard dictionary = 30 bits, ~ 13:1 compression
for non-standard dictionary = 366 bits, ~ 1.1:1 compression

Front 32

Graphical Interchange Format (GIF) (lossless):

Back 32

•Used for image compression –only lossless when original image has fewer than 256 colors
•Algorithm:
1.If necessary, reduce # colors to 256 (8 bits per pixel)
2.Run LZ on the result
•Works best for images that have repeating patterns
•Typical: 4:1 –10:1 compression ratio

Front 33

JPEG (lossy):

Back 33

•JPEG = ISO “Joint Photographic Experts Group”
•Algorithm:
1.Do a spectral analysis of each 8x8 pixel block (lossless)
2.Quantize (round) the spectral results (lossy, least significant information)
3.Run RLE and Huffman on the result (lossless)
•User controls quality of reconstructed image by choosing how much rounding is done in step 2 trade quality for size

Front 34

MPEG (lossy):

Back 34

Motion Picture Experts Group

Front 35

MPEG Standards:

Back 35

MPEG-1
MPEG-2
MPEG-3
MPEG-4

Front 36

MPEG-1:

Back 36

VCR-quality video, 1.2Mbps

Front 37

MPEG-2:

Back 37

HDTV-quality video, 4-8Mbps

Front 38

MPEG-3 (“MP3”):

Back 38

CD-quality audio, 96-128Kbps

Front 39

MPEG-4:

Back 39

MPEG-2 + VRML, DRM, Interactive video

Front 40

MPEG video concepts:

Back 40

•Based on JPEG
–We could just do a JPEG image of each frame of video
–But we can improve on that by taking advantage of common features across framesThere

Front 41

MPEG-2 Approach:

Back 41

•Each frame in the video stream are encoded as one of the following types:
–I-frame:
–P-frame:
–B-frame:

Front 42

I-frame:

Back 42

•A JPEG-encoded still image
•I-frames are included periodically as a reference

Front 43

P-frame:

Back 43

•An encoding of the differences between the last frame and this one
•Image broken up into 16x16 subimages that are similar in both frames, maybe in different places (“macroblocks”)
•Differences expressed in terms of movement, transformation of macroblocks.

Front 44

B-frame:

Back 44

•Like a P-frame, but based on either previous or next frame

Front 45

Audio streams:

Back 45

•Uncompressed POTS-quality sound
–4Khz Bandwidth
–8bit sample / 125usec 64Kbps
•Uncompressed CD-quality audio:
–44Khz Bandwidth
–16-bit sample / 23usec x 2 channels for stereo 1.4Mbps

Front 46

MPEG-3 audio compression Idea:

Back 46

Strong sounds at one frequency tend to mask softer sounds at nearby frequencies –do not transmit the masked sounds

Front 47

MPEG-3 audio compression Algorithm:

Back 47

–For every 26msec, measure power in 32 frequency bands
–Allocate higher bps to bands with most power, less bps to bands with less power
–Huffman code the allocated bits

Front 48

Network Applications (4):

Back 48

•SMTP –Simple Mail Transfer Protocol
•HTTP –Hyper Text Transport Protocol
•DNS –Domain Name System Protocol
•SNMP –Simple Network Management Protocol

Front 49

Domain Name System:

Back 49

•Map user-friendly names to router-friendly addresses
•Host names
–Variable length
–Mnemonic
•IP address
–Fixed length
•Early implementation
–hosts.txt

Front 50

Domain Hierarchy:

Back 50

•Right to left
•Tree structure
•Divided into zones corresponding to administrative authorities

Front 51

Resource Records:

Back 51

•Name to value binding
•{ Name, Value, Type, Class, TTL}
•Type
–A: IP address
–NS: name server
–CNAME: aliases
–MX: mail server
•Class
–Only widely used one is the Internet
•TTL

Front 52

Hierarchies:

Back 52

•Top-level domain
–edu
•University level
–uah.edu
•Department level
–cs.uah.edu,

Front 53

Name Resolution:

Back 53

•Client contacts a local name server
•Local server caches responses

Front 54

Three levels of Identifiers

Back 54

•Domain names, IP addresses, physical network addresses
•Applications use domain names
•DNS resolves domain names to IP addresses
•IP address are put in packets
•ARP translates IP addresses to physical addresses

Front 55

Overlay Networks:

Back 55

•Applications make forwarding decisions
•A logical network on top of a physical network
•In an application-specific way
•Multiple overlay networks on top a underlying network

Front 56

Routing Overlays:

Back 56

•Alternative routing strategy, simplest
•Introduce new routing technologies
–MBone(Multicast backbone)
–6-BONE (IPv6 multicast)

Front 57

End System Multicast:

Back 57

•Only Internet hosts
•Exchange messages through UDP tunnels
•General strategy: measure roundtrip latency
•Build mesh
–Send “Join mesh” message
–Periodically send “Keep alive”message
•Leave the group
–Send “Leave mesh” message
–Silently leave
•Build multicast tree

Front 58

Resilient Overlay Networks (RON):

Back 58

•Triangle inequality does not hold in the Internet
–BGP’s normal operation may override by human-directed policies
•RON scales to a few dozen nodes
–N * N connected nodes
•Monitoring
–Latency
–Available bandwidth
–Loss probability
•Performance improvement & fast failure recovery

Front 59

Peer-to-Peer Networks (P2P):

Back 59

•A community of users to pool resources
–Content
–Network bandwidth
–Storage
–CPU
•Decentralized & self-organizing
–Napster
–KaZaA
•They are overlay networks

Front 60

Gnutella:

Back 60

•First system that not depend on a centralized registry
•A node knows some other nodes
•Find a object
–Send “Query” message to neighbors
–If a node knows, replies “Query Response” message
–Otherwise, forward the “Query” message to meighbors
•Get the object
•A node maintains a copy of a query message
•Use TTL to limit the range of message forwarding (flooding)
•Unique query identifier (QID)
–Cut off forwarding loops
•A node is free to decide who is its neighbor