Advanced Computer Networks: Lecture 39 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (369.4 KB, 32 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 39
2
Presentation Formatting
Outline
Presentation Formatting
Data compression
3
Presentation Formatting
Application
Application
Data
Data
Presentation
Presentation
Decoding
Encoding
Message
Message
■■■
Message
4
Presentation Formatting
• Data types we consider
–
–
–
–
–
Integers
Floats
Strings
Arrays
Structs
• Types of data we do not consider
– Images
– Video
– Multimedia documents
5
Difficulties
• Representation of base types
– Floating point: IEEE 754 versus nonstandard
– Integer: bigendian vs littleendian (e.g., 34,677,374)
(2)
Big-endian
(17)
(34)
(126)
00100010
01111110
(34)
(17)
(2)
00100010
00010001
00000010
00000010 00010001
(126)
Little-endian 01111110
Low
address
• Compiler layout of structures
High
address
6
Taxonomy
• Data types
– Base types (e.g. ints, floats), must convert
– Flat types (e.g. structures, arrays), must pack
– Complex types (e.g. pointers), must linearize
Application data structure
Argument marshaller
7
Taxonomy
• Conversion Strategy
– Canonical intermediate form
– Receivermakesright (an N x N
solution)
8
Taxonomy (cont)
• Tagged versus untagged data
type =
len = 4
INT
value = 417892
9
Taxonomy (cont)
• Stubs
– Compiled
– Interpreted
Interface
descriptor for
procedure P
Call P
Arguments
Client
stub
Code
P
Specification
Stub
compiler
Code
Marshalled
arguments
Arguments
Server
stub
Marshalled
arguments
RPC
RPC
Message
10
eXternal Data Representation
(XDR)
• Defined by Sun for use with SunRPC
• C type system (without function
pointers)
• Canonical intermediate form
• Untagged (except array length)
• Compiled stubs
11
Example Code (XDR)
#define MAXNAME 256;
#define MAXLIST 100;
struct item {
int
count;
char
name[MAXNAME];
int
list[MAXLIST];
};
bool_t
xdr_item(XDR *xdrs, struct item *ptr)
{
return(xdr_int(xdrs, &ptr->count) &&
xdr_string(xdrs, &ptr->name, MAXNAME) &&
xdr_array(xdrs, &ptr->list, &ptr->count,
MAXLIST, sizeof(int), xdr_int));
}
Count
3
Name
7
J
O
H
N
S
O
N
List
3
497
8321
265
12
•
•
•
•
•
•
Abstract Syntax Notation One
(ASN1)
An ISO standard
Essentially the C type system
Canonical intermediate form
Tagged
Compiled or interpreted stubs
BER: Basic Encoding Rules
(tag, length, value)
type length type length
value
type length
value
INT
4
4-byte integer
13
value
ASN.1 BER Representation
(a)
0 length
(b)
1
k
k containing length
14
Network Data Representation (NDR)
– IntegerRep
• Defined by DCE
• 0 = bigendian
• Essentially the C type
• 1 = littleendian
system
– CharRep
• 0 = ASCII
• Receivermakesright
• 1 = EBCDIC
(architecture tag)
– FloatRep
• Individual data items
• 0 = IEEE 754
untagged
• 1 = VAX
• 2 = Cray
• Compiled stubs from IDL
• 3 = IBM
• 4byte architecture tag
0
4
IntegrRep CharRep
8
16
FloatRep
24
Extension 1
31
Extension 2
15
Data Compression
Outline
– Compression
16
Compression Overview
• Encoding and Compression
– Huffman codes
• Lossless
– Data received = data sent
– Used for executables, text files, numeric data
• Lossy
– Data received is not equal to data sent
– Used for images, video, audio
17
Lossless Algorithms
• Run Length Encoding (RLE)
– Example: AAABBCDDDD encoding as
3A2B1C4D
– Good for scanned text (8to1
compression ratio)
– Can increase size for data with variation
(e.g. some images)
18
Lossless Algorithms
• Differential Pulse Code Modulation
(DPCM)
– Example AAABBCDDDD encoding as
A0001123333
– Change reference symbol if delta
becomes too large
– Works better than RLE for many digital
images (1.5to1)
19
DictionaryBased Methods
• Build dictionary of common terms
– Variable length strings
• Transmit index into dictionary for each term
• LempelZiv (LZ) is the bestknown example
• Commonly achieve 2to1 ration on text
• Variation of LZ used to compress GIF images
– First reduce 24bit color to 8bit color
– Treat common sequence of pixels as terms in
dictionary
– Not uncommon to achieve 10to1 compression (x3)
20
Image Compression
• JPEG: Joint Photographic Expert Group (ISO/ITU)
• Lossy stillimage compression
• Three phase process
JPEG compression
Source
image
DCT
Quantization
Encoding
Compressed
image
– Process in 8x8 block chunks (macroblock)
– Grayscale: each pixel is three values (YUV)
– DCT: transforms signal from spatial domain into and equivalent
signal in the frequency domain (lossless)
– Apply a quantization to the results (lossy)
– RLElike encoding (lossless)
21
Quantization and Encoding
• Quantization Table
3 5 7 9 11 13 15 17
5 7 9 11 13 15 17 19
7 9 11 13 15 17 19 21
9 11 13 15 17 19 21 23
11 13 15 17 19 21 23 25
13 15 17 19 21 23 25 27
15 17 19 21 23 25 27 29
17 19 21 23 25 27 29 31
• Encoding Pattern
22
MPEG
• Motion Picture Expert Group
• Lossy compression of video
• First approximation: JPEG on each
frame
• Also remove interframe redundancy
23
• Frame types
MPEG (cont)
– I frames: intrapicture
– P frames: predicted picture
– B frames: bidirectional predicted picture
Input
stream
Frame 1 Frame 2 Frame 3 Frame 4 Frame 5
Frame 6 Frame 7
MPEG
compression
Forward
prediction
CompressedI frame B frame B frame P frame B frame B frame I frame
stream
Bidirectional
prediction
• Example sequence transmitted as I P B B I B B
24
MPEG (cont)
• B and P frames
– Coordinate for the macroblock in the frame
– Motion vector relative to previous reference frame (B, P)
– Motion vector relative to subsequent reference frame (B)
– Delta for each pixel in the macro block
• Effectiveness
– Typically 90to1
– As high as 150to1
– 30to1 for I frames
– P and B frames get another 3 to 5x
25
