Transcript Introduction - Rudra Dutta

Introductory Concepts
Rudra Dutta
CSC 401- Fall 2011
Digital Communication

Digital representation of information
–
–
–
–

Reduces diverse information to same form
Allows infinite replication
Allows general purpose manipulation (computers)
Allows transmission from one computer to another
Digital communication
–
–
–
Revolution in our times
Created digital economy
Large number of products and services seen as information
Copyright Fall 2011, Rudra Dutta, NCSU
2
Components for Communication



Nodes (computers, …)
Links
Communication primitive
Copyright Fall 2011, Rudra Dutta, NCSU
3
Scalability
Copyright Fall 2011, Rudra Dutta, NCSU
4
Cooperation



Nodes - endpoint nodes and intermediate nodes
Links
Communication primitive
Copyright Fall 2011, Rudra Dutta, NCSU
5
Forwarding

Performed by intermediate node
–

May be performed at physical layer
–
–
–

Process of copying data off one incoming link, on
some outgoing link
(Sub-bitpipe)
Utilize physical phenomena - “Switching”
Electrical circuit, etc.
May be at higher layer
–
–
–
Bits or some organization of bits
“Forwarding”
“Routing” (ambiguity)
Copyright Fall 2011, Rudra Dutta, NCSU
6
The Need for Sharing

Taking turns
 “Multiplexing”
–
Time division, frequency division
Copyright Fall 2011, Rudra Dutta, NCSU
7
Reserved Timeslots

Two modes of TDM
–
–
Timeslots are reserved for end stations - “slotted”
First-come-first-serve - “statistical”
Copyright Fall 2011, Rudra Dutta, NCSU
8
Protocols
On = “1”
or “0” ?



“Rule set”, “language”
Standards for communication hardware/software
Common guidelines for implementations
–
–
Different implementations of same protocol
Standards bodies make protocols

–
ITU-T, IETF, IEEE
Software manufacturers produce implementations
Copyright Fall 2011, Rudra Dutta, NCSU
9
Delay

Two meanings
–
–
How fast can successive bits be put into the pipe?
How long does a bit take to traverse the pipe?
“Distance”
Sender
Copyright Fall 2011, Rudra Dutta, NCSU
Time
Receiver
10
Concept Problem

Imagine you have trained your St. Bernard, Bernie, to carry a box of three 8mm tapes instead of
a flask of brandy. (When your disk fills up, you consider that an emergency.) These tapes each
contain 7 gigabytes. The dog can travel to your side, wherever you may be, at 18 km/hour.
(a) For what range of distances does Bernie have a higher data rate than a transmission line
whose data rate (excluding overhead) is 150 Mbps?
(b) We distinguished between two types of delay:
–
–
–
Propagation Delay: The time from when the first bit of the message is sent to when the first bit of the message is received. Often
called simply delay.
Transmission Delay: The time from when the first bit is sent (received) to when the last bit is sent (received). This can be
considered as the ratio of the time taken to the number of bits in the message. Often the reciprocal of this ratio is considered
very important, and is called bit rate, or throughput.
In the problem in part (a) of this question, which of the above two quantities are you being
asked to compare, or what combination of them?
Copyright Fall 2011, Rudra Dutta, NCSU
11
Throughput

Total number of bits transferred, over given time
–
–
–
–
Related obviously to the transmission delay
Propagation delay often referred to simply as “delay”
or “latency”
Throughput sometimes referred to as “bandwidth”
“Bandwidth-delay product” - filling the pipe
Copyright Fall 2011, Rudra Dutta, NCSU
12
Example - Slotted TDM

Stations A-H each get
equal time slots of 1 ms
each
–

Time 0 slot for A
Scheduling - after
packet is received, it is
sent at next slot for
station, if room
C
B
A
R1
D
E
H 80 Mbps
F
G
R2
A
0
B
1
C
2
D
3
E
4
F
5
G
6
H A
7
8
B …
9
10 …
Time (ms)
Station
Packet size
(kB)
0
A
5
0.5
B
5
1.5
D
10
2.1
C
5
3.5
A
5
4.2
A
5
4.9
E
5
5.0
F
10
6.1
F
10
6.9
G
5
Example - Slotted TDM

Draw the timeline, obtain delays
B
A
C
F
A A E
D
0
1
A
F
2
B
3
C
4
D
G
5
E
6
F
7
G
8
H
9 10 …
A B …
Time
(ms)
Station
Packet
size
(kB)
0
A
5
0.5
B
5
1.5
D
10
2.1
C
5
3.5
A
5
4.2
A
5
4.9
E
5
5.0
F
10
6.1
F
10
6.9
G
5
Example - Statistical TDM

Now do the same for statistical mux
–
B
A
Assume FIFO scheduling
C
F
A A E
D
0
1

2
3
4 5
F
G
6
What would happen with
periodic sources?
7 8
9 10 …
Time
(ms)
Station
Packet
size
(kB)
0
A
5
0.5
B
5
1.5
D
10
2.1
C
5
3.5
A
5
4.2
A
5
4.9
E
5
5.0
F
10
6.1
F
10
6.9
G
5
Software Protocols



Syntax of a message
– what fields does it contain?
– in what format?
Semantics of a message
– what does a message mean?
– for example, not-OK message means receiver got a
corrupted file
Actions to take on receipt of a message
– for example, on receiving not-OK message,
retransmit the entire file
Copyright Fall 2011, Rudra Dutta, NCSU
16
Service view of protocol



A protocol is a software module providing a service
ftp provides reliable file transfer service
Peer entities use a protocol to provide a service to a higher-level
peer entity
–

for example, postal workers use a protocol to present customers
with the abstraction unreliable letter transfer service
Service interaction between modules constrained to very
specific pattern  layering
Copyright Fall 2011, Rudra Dutta, NCSU
17
Some terminology

Service access point (SAP)
–

Protocol data units (PDUs)
–

Service data units (SDUs)
–

Encapsulation
–

PDU = SDU + optional header or trailer
Copyright Fall 2011, Rudra Dutta, NCSU
18
The importance of being layered



Breaks up a complex problem into smaller
manageable pieces
– can compose simple service to provide complex
ones
– for example, WWW (HTTP) is Java layered over
TCP over IP (and uses DNS, ARP, DHCP, RIP,
OSPF, BGP, PPP, ICMP)
Abstraction (hiding) of implementation details
– separation of implementation and specification
– can change implementation as long as service
interface is maintained
Can reuse functionality
Copyright Fall 2011, Rudra Dutta, NCSU
19
ISO OSI reference model




A set of protocols is open if
– protocol details are publicly available
– changes are managed by an organization whose membership
and transactions are open to the public
A system that implements open protocols is called an open
system
International Organization for Standards (ISO) prescribes a
standard to connect open systems
– open system interconnect (OSI)
Has greatly influenced thinking on protocol stacks
Copyright Fall 2011, Rudra Dutta, NCSU
20
Node-to-node
End-to-end
The seven layers
Application
Top level user of the system
Presentation
Resolve platform issues (data
representation, possibly encryption)
Session
Full-duplex, expedited data delivery,
session synchronization
Transport
Error control, flow control, multiplex
Reliability
Network
Concatenates links to form end-to-end
abstraction
Data Link Control Organizes bit transmissions into frame
transmissions (LLC, MAC sublayers)
Physical
Copyright Fall 2011, Rudra Dutta, NCSU
Moves bits between physically connected
end-systems
21
Peer Processes
End Node
Copyright Fall 2011, Rudra Dutta, NCSU
DLC
DLC
DLC
DLC
Phy
Phy
Phy
Phy
Intermediate Node
Intermediate Node
End Node
22
Network Components

Different network components function at
different layers
 Embody service at different protocol layers
 Nomenclature is not very well standardized, and
is changing
 Mixed, “layer-blurring” devices complicate
matters
Copyright Fall 2011, Rudra Dutta, NCSU
23
C
A
A
B
C
D
E
E
D
NET
NET
NET
NET
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
PHY
B
Component C in this figure is a wire, or hub.
Copyright Fall 2011, Rudra Dutta, NCSU
24
A
A
B
C
NET
NET
DLC
DLC
DLC
PHY
PHY
PHY
D
E
E
NET
NET
DLC
DLC
DLC
PHY
PHY
PHY
C
D
B
Computer C in this figure is a bridge.
(Could be a switch, if dumb component.)
Copyright Fall 2011, Rudra Dutta, NCSU
25
A
B
C
D
E
NET
NET
NET
NET
NET
DLC
DLC
DLC
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
PHY
PHY
PHY
E
A
C
B
D
Computer C in this figure is a router, or switch
Copyright Fall 2011, Rudra Dutta, NCSU
26
Layers in a Router/Switch
Copyright Fall 2011, Rudra Dutta, NCSU
A
R
D
NET
NET
NET
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
27
Software Operation

Some of L2 and all of L3 protocols are software
processes
 Exchange of data requires IPC, and blocking

Buffering may be
employed between
layers
–
Copyright Fall 2011, Rudra Dutta, NCSU
Almost certainly at
higher than the bitpipe
layer
28
Buffering at L3

Operation of L3 itself may require buffering data
–

Input-buffer-process-buffer-output cycle
–

Store-and-forward
May fall behind
Discard data  loss
Copyright Fall 2011, Rudra Dutta, NCSU
A
R
D
NET
NET
NET
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
29
Layering

We have broken a complex problem into
smaller, simpler pieces
–
–

HOWEVER - sacrifices efficiency
–
–

Provides the application with sophisticated services
Each layer provides a clean abstraction to the layer
above
Might even sacrifice functionality, or optimality
Recently, cross-layer approaches have started
gaining ground
Example - power-aware routing in ad-hoc
networks
Copyright Fall 2011, Rudra Dutta, NCSU
30
Layer Overhead


Suppose that a certain communications protocol stack involves an overhead on the
application layer PDU of 100 bytes for headers and framing. We send 1 million bytes
of data using this application and this protocol stack; however, exactly one data byte
is corrupted during transmission, and the packet containing it is thus lost and must
be retransmitted.
What is the total number of overhead + loss bytes retransmitted, for packet data
sizes (not including overhead) of 100, 500, 1000, and 2000 bytes?
Copyright Fall 2011, Rudra Dutta, NCSU
31
Network Performance

Ultimately, measured in quantities the end-user
cares about
–
–

Delay, throughput
Other metrics derived from these
More sophisticated metrics
–
Predictability / Reliability / Survivability
– Variability of delay or throughput
– Guarantees - Quality of Service contracts
– Security
Copyright Fall 2011, Rudra Dutta, NCSU
32
Traffic Characterization

Traffic - that which is carried by network
–
Generated and consumed by end-nodes
– “Demand” for networking services: b/w and switching

Magnitude (bandwidth)
–

Lifetime
–

Could vary with time, if “reasonably long” life
How long it is resident in the network
Arrival and departure patterns
–
Call (like telephony) arrival and departure
– Increment and decrement
– Periodic (scheduled)
– Static (long-term)

Requirement of performance
–
Hard or statistical
Copyright Fall 2011, Rudra Dutta, NCSU
33
Network View

Connectivity is always less than full (esp. in large networks)
 Because of scalability, hierarchy seems inevitable
 Nature of end-nodes and intermediate nodes vary
 All links are TDM (FDM modeled as separate links)
4
2
1
3
Copyright Fall 2011, Rudra Dutta, NCSU
34
Traffic Aggregation - Static Traffic


Consider lowest level networks
Assume each station injects traffic steadily
–

Due to aggregation, magnitude increases as traffic
climbs hierarchy
–


But constant nature of traffic remains
Aggregation/dis-aggregation process is straightforward
for intermediate nodes
–

Number of bits injected per time unit is constant for each source
Effectively same as slotted TDM
Therefore static traffic is stable - remains static at higher
levels of hierarchy
Magnitude and therefore capacity, of course, must
increase at higher levels
Copyright Fall 2011, Rudra Dutta, NCSU
35
Bursty Traffic

Traffic is generated intermittently at each end
node
–

Assume (peak) rates are known
Question of capacity and aggregation become
intertwined
–
One approach: pretend each end node is a steady
source at its peak rate, then provision as before

–
Aggregation will be easy
Another approach: provision for average




Do bursts arrive deterministically?
Sometimes link will be busy when traffic arrives to use it
Must store-and-forward, or discard
Question of slotting TDM comes in - work conservation
Copyright Fall 2011, Rudra Dutta, NCSU
36
A View of Aggregation
1
2
burstiness
4
2
3
1
3
4
4
magnitude (“bandwidth”)
Copyright Fall 2011, Rudra Dutta, NCSU
37
Static Traffic in Real Networks

Aggregation can tend to cancel out bursts
 Finite capacity of pipe will appear as static-ness
of traffic to next level of aggregation
–
Also: Concept of “elastic traffic”



Source-to-destination traffic flows in the Internet are not
static as generated, but congestion slows down bursts
In response, flow duration will increase
Empirical observation tends to confirm
–
–
For example, CAIDA data
Exhibits “busy hour” traffic patterns

Changes from hour to hour, but each pattern stable over
days and weeks
Copyright Fall 2011, Rudra Dutta, NCSU
38
About Loss

Loss may occur on the link
–
–

Loss may occur at intermediate nodes
–
–

Usually very little in guided medium - ignore
Usually handled by L2 transmissions or ignored
Store-and-forward buffers are finite - may overflow
Other mechanism at intermediate node may discard
Does retransmission occur?
–
–
May not be required / desired
If desired,


May be at L2, on link
May be at L4, E2E
Copyright Fall 2011, Rudra Dutta, NCSU
39
Providing Guarantees - About Delay

Controversial proposition:
–
–

“If delay is not important, capacity is not important”
“If delay is important, capacity must be large OR
aggregation must be slotted OR both”
Links must
–
–
Provide connectivity
Have capacity to carry traffic

Routers must have memory and processor
capacity to switch traffic
 Network design / resource provisioning problem
Copyright Fall 2011, Rudra Dutta, NCSU
40
Two Modes of Networking


Traffic Networks and Transport Networks
Traffic networks: where stochastic demand picture is
operative
–
–

Short term switching/routing
Design for connectivity
Transport networks: where traffic demands of static
magnitude are seen to be operative
–
–
–
–
(Semi-) Permanent
QoS considerations paramount
Demands seen to be injected at transport network nodes, lower
level networks not visible
Design for connectivity and capacity
Copyright Fall 2011, Rudra Dutta, NCSU
41
Network Design

Static traffic / slotted TDM aggregation
–
–

Bursty traffic / statistical TDM
–
–

Small, constant delay should result
Performance metric is global – demands satisfied,
global delay
Larger range of delay, but statistically smaller
Design for statistical delay, or simply connectivity
Circuits – canonical telephony
–
–
Very small and constant delay
Operative performance metric is blocking ratio
Copyright Fall 2011, Rudra Dutta, NCSU
42
Multi-layer Networks

Generalized protocol
layering can create
complicated networks
–
–

Better thought of as
multiple layers
Each layer satisfies flow
constraints
Generally, demand is
specified in one layer
and capacity in another
–
Must assume some
mapping method possibly constrained
Copyright Fall 2011, Rudra Dutta, NCSU
Ckt-switched
voice
Private
Line
IP
Networks
CrossConnect
Digital
Transmission
Optics
Media
43
Review







Networks have varied and extensive current and future uses
Computers communicate digital information over physical media /
links
Network components perform cooperative effort
Protocols enable communication, arranged in layers
Holistic concepts such as connection-orientation, circuit-switching,
emerge
Traffic is “demand” for network
Resource provisioning + protocols and policies produce
measurable performance metrics experienced by traffic demand
Copyright Fall 2011, Rudra Dutta, NCSU
44