Transcript 07_intro - Rudra Dutta

Introductory Concepts
Rudra Dutta
ECE/CSC 570 - Fall 2007, Section 001
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 2007, Rudra Dutta, NCSU
2
Components for Communication



Nodes (computers, …)
Links
Communication primitive
Copyright Fall 2007, Rudra Dutta, NCSU
3
Scalability
Copyright Fall 2007, Rudra Dutta, NCSU
4
Cooperation



Nodes - endpoint nodes and intermediate nodes
Links
Communication primitive
Copyright Fall 2007, 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 2007, Rudra Dutta, NCSU
6
The Need for Sharing

Taking turns
 “Multiplexing”
–
Time division, frequency division
Copyright Fall 2007, Rudra Dutta, NCSU
7
Reserved Timeslots

Two modes of TDM
–
–
Timeslots are reserved for end stations - “slotted”
First-come-first-serve - “statistical”
Copyright Fall 2007, 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 2007, 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 2007, Rudra Dutta, NCSU
Time
Receiver
10
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 2007, Rudra Dutta, NCSU
11
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 2007, Rudra Dutta, NCSU
12
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 2007, Rudra Dutta, NCSU
13
Some terminology

Service access point (SAP)
–

Protocol data units (PDUs)
–

Service data units (SDUs)
–

Encapsulation
–

PDU = SDU + optional header or trailer
Copyright Fall 2007, Rudra Dutta, NCSU
14
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 2007, Rudra Dutta, NCSU
15
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 2007, Rudra Dutta, NCSU
16
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 2007, Rudra Dutta, NCSU
Moves bits between physically connected
end-systems
17
Peer Processes
End Node
Copyright Fall 2007, Rudra Dutta, NCSU
DLC
DLC
DLC
DLC
Phy
Phy
Phy
Phy
Intermediate Node
Intermediate Node
End Node
18
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 2007, Rudra Dutta, NCSU
19
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 2007, Rudra Dutta, NCSU
20
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 2007, Rudra Dutta, NCSU
21
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 2007, Rudra Dutta, NCSU
22
Layers in a Router/Switch
Copyright Fall 2007, Rudra Dutta, NCSU
A
R
D
NET
NET
NET
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
23
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 2007, Rudra Dutta, NCSU
Almost certainly at
higher than the bitpipe
layer
24
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 2007, Rudra Dutta, NCSU
A
R
D
NET
NET
NET
DLC
DLC
DLC
DLC
PHY
PHY
PHY
PHY
25
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 2007, Rudra Dutta, NCSU
26
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 2007, Rudra Dutta, NCSU
27
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 2007, Rudra Dutta, NCSU
28
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 2007, Rudra Dutta, NCSU
29
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 2007, Rudra Dutta, NCSU
30
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 2007, Rudra Dutta, NCSU
31
A View of Aggregation
1
2
burstiness
4
2
3
1
3
4
4
bandwidth
Copyright Fall 2007, Rudra Dutta, NCSU
32
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 2007, Rudra Dutta, NCSU
33
Providing Guarantees - About Delay

Controversial proposition:
–
–

Delay for static traffic / slotted TDM aggregation
–

Small, constant
Delay for bursty traffic / statistical TDM
–

“If delay is not important, capacity is not important”
“If delay is important, capacity must be large OR
aggregation must be slotted OR both”
Large range
Delay for circuits - telephony
–
Very small and constant, operative quantity is
blocking ratio
Copyright Fall 2007, Rudra Dutta, NCSU
34
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 2007, Rudra Dutta, NCSU
35
Two Modes of Networking


Traffic Networks and Transport Networks
Traffic networks: where stochastic demand picture is
operative
–

Transport networks: where traffic demands of static
magnitude are seen to be operative
–
–
–



Short term switching/routing
(Semi-) Permanent
QoS considerations paramount
Demands seen to be injected at transport network nodes, lower
level networks not visible
Links must have capacity to carry traffic
Routers must have memory and processor capacity to
switch traffic
Network design / resource provisioning problem
Copyright Fall 2007, Rudra Dutta, NCSU
36
Delay for Packets, Single Link


Bursty traffic, statistical TDM
Usual M/M/1 assumptions
–


In reality, traffic process is heavier-tailed
D(l, m) = 1 / (m - l)
“Statistical Multiplexing Gain”
Copyright Fall 2007, Rudra Dutta, NCSU
579, 573
37
Blocking in Telephony
Average call rate l
 Average holding time t
 Offered traffic load or intensity a = lt

ac / c!
 B(a,c) = -------------------
777
S ak / k!
Copyright Fall 2007, Rudra Dutta, NCSU
38
Static Traffic Performance

Give “matrix” of traffic demand components
–
–
–
Static, “always-on”
Usually aggregate
Measured or estimated
791
(Opt, Surv)

Delay - fairly constant for each demand
 Blocking - none; loss - none
–

Except in unusual circumstances
Performance is measured globally
–
–
–
Various objectives
Delay or throughput (global, across all components)
Revenue, fairness, protection, …
Copyright Fall 2007, Rudra Dutta, NCSU
39
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 2007, Rudra Dutta, NCSU
Ckt-switched
voice
Private
Line
IP
Networks
CrossConnect
Digital
Transmission
Optics
Media
40
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 2007, Rudra Dutta, NCSU
41