Transcript Packet Switching

Computer Networks
2009/Fall
Division of Computer Science & Engineering
Chonbuk University
Mobile Computing Lab.
Computer Network
2009/Fall
1
Gihwan Cho
Lecture Topic I
Overall Introduction
Dream as if you will live forever
Live as if you will die today
Never too late!
Movie “ The bucket list”
Mobile Computing Lab.
Computer Network
2009/Fall
2
Gihwan Cho
Chapter 1 : Data Communications &
Networking Overview

Simplified communications model
Mobile Computing Lab.
Computer Network
2009/Fall
3
Gihwan Cho
Key Communications Tasks











Transmission system utilization
Interfacing
Signal generation
Synchronization
Exchange management
Error detection and correction
Addressing and routing
Recovery
Message formatting
Security
Network management
Mobile Computing Lab.
Computer Network
2009/Fall
4
Gihwan Cho
Simplified Data Communications Model
Mobile Computing Lab.
Computer Network
2009/Fall
5
Gihwan Cho
Why Data Networking

Background



Point to point communication not usually practical



growth of number & power of computers is driving need for
interconnection
also seeing rapid integration of voice, data, image & video
technologies
devices are too far apart
large set of devices would need impractical number of
connections
Solution is a communications network


Wide Area Network (WAN)
Local Area Network (LAN)
Mobile Computing Lab.
Computer Network
2009/Fall
6
Gihwan Cho
Simplified Network Model
Switching
node
Source System
Source
Wide-area
network
Destination System
Transmitter
Transmission
System
Receiver
Destination
Local area
network
Mobile Computing Lab.
Computer Network
2009/Fall
7
Gihwan Cho
Chapter 2 : Protocol Architecture

Protocol Architectures and Networks
Mobile Computing Lab.
Computer Network
2009/Fall
8
Gihwan Cho
Operation of a Protocol Architecture
Mobile Computing Lab.
Computer Network
2009/Fall
9
Gihwan Cho
Standardized Protocol Architectures




Required for devices to communicate
Vendors have more marketable products
Customers can insist on standards based equipment
Two standards:



OSI reference model
never lived up to early promises
TCP/IP protocol suite
most widely used
Also: IBM Systems Network Architecture (SNA)
Mobile Computing Lab.
Computer Network
2009/Fall
10
Gihwan Cho
Layered Model
Mobile Computing Lab.
Computer Network
2009/Fall
11
Gihwan Cho
The OSI Environment
Mobile Computing Lab.
Computer Network
2009/Fall
12
Gihwan Cho
TCP/IP Protocol Architecture

Dominant commercial (Internet) protocol architecture



specified and extensively used before OSI
developed by research funded US department of defense
No official model but a working one





application layer
communication between processes or applications
end to end or transport layer (TCP/UDP/…)
end to end transfer of data
Internet layer (IP)
addressing, and routing of data
network layer
logical interface between end system and network
physical layer
transmission medium, signal rate and encoding
Mobile Computing Lab.
Computer Network
2009/Fall
13
Gihwan Cho
PDUs in TCP/IP
Mobile Computing Lab.
Computer Network
2009/Fall
14
Gihwan Cho
Some Protocols in TCP/IP Suite
Mobile Computing Lab.
Computer Network
2009/Fall
15
Gihwan Cho
Lecture Topic III
Wide Area Networks
사자는 사냥감이 토끼냐 말이냐에 따라서
사냥방법을 달리하지 않는다.
단지 최선을 다할 뿐이다.
Mobile Computing Lab.
Computer Network
2009/Fall
16
Gihwan Cho
Chapter 10 : Circuit Switching & Packet
Switching

Simple switched network
Mobile Computing Lab.
Computer Network
2009/Fall
17
Gihwan Cho
Nodes

Long distance transmission is typically done over a
network of switched nodes



a collection of nodes and connections is a communication network
data routed by being switched from node to node
Nodes



nodes may connect to other nodes only, or to stations and other
nodes
network is usually partially connected
some redundant connections are desirable
have two different switching technologies
circuit switching
packet switching
Mobile Computing Lab.
Computer Network
2009/Fall
18
Gihwan Cho
Circuit Switching


Uses a dedicated path between two stations
Has three phases




Inefficient




establish
transfer
disconnect
channel capacity dedicated for duration of connection
if no data, capacity wasted
Set up (connection) takes time
Once connected, transfer is transparent

developed for voice traffic (phone)
Mobile Computing Lab.
Computer Network
2009/Fall
19
Gihwan Cho
Public Circuit Switched Network
Mobile Computing Lab.
Computer Network
2009/Fall
20
Gihwan Cho
Telecommunications Components

Subscriber


Local loop




subscriber loop
connection to network
twist-pair wire
Exchange



devices attached to network
switching centers
end office - supports subscribers
Trunks


branches between exchanges
multiplexed
Mobile Computing Lab.
Computer Network
2009/Fall
21
Gihwan Cho
Circuit Switch Elements

Circuit establishment
Mobile Computing Lab.
Computer Network

Circuit switch elements
2009/Fall
22
Gihwan Cho
Blocking or Non-blocking

Blocking



may be unable to connect stations because all paths are in use
used on voice systems
short duration calls
Non-blocking


permits all stations to connect (in pairs) at once
used for some data connections
Mobile Computing Lab.
Computer Network
2009/Fall
23
Gihwan Cho
Space Division Switching



Developed for analog environment
Separate physical paths
Crossbar switch




number of crosspoints grows as square of number of stations
loss of crosspoint prevents connection
inefficient use of crosspoints
all stations connected, only a few crosspoints in use
Multistage switch




reduced number of crosspoints
more than one path through network
increased reliability
more complex control
may be blocking
Mobile Computing Lab.
Computer Network
2009/Fall
24
Gihwan Cho
Crossbar Matrix
Mobile Computing Lab.
Computer Network
2009/Fall
25
Gihwan Cho
Three Stage Switch
Mobile Computing Lab.
Computer Network
2009/Fall
26
Gihwan Cho
Time Division Switching




Modern digital systems rely on intelligent control of
space and time division elements
Use digital time division techniques to set up and
maintain virtual circuits
Partition low speed bit stream into pieces that share
higher speed stream
Individual pieces manipulated by control logic to flow
from input to output
Mobile Computing Lab.
Computer Network
2009/Fall
27
Gihwan Cho
Packet Switching




Circuit switching was designed for voice
Packet switching was designed for data
Transmitted in small packets
Packets contains user data and control info



user data may be part of a larger message
control info includes routing (addressing) info
Packets are received, stored briefly (buffered) and past on
to the next node
Mobile Computing Lab.
Computer Network
2009/Fall
28
Gihwan Cho
Advantages

Line efficiency



Data rate conversion



each station connects to the local node at proper speed
nodes buffer data if required to equalize rates
No blocking of calls



dynamic sharing of link by many packets over time
packets queued and transmitted as fast as possible
packets are accepted even when network is busy
delivery may slow down - delivery delay increases
Priorities can be used
Mobile Computing Lab.
Computer Network
2009/Fall
29
Gihwan Cho
Switching Technique



Station breaks long message into packets
Packets sent one at a time to the network
Packets handled in two ways


datagram
virtual circuit
Mobile Computing Lab.
Computer Network
2009/Fall
30
Gihwan Cho
Datagram
Diagram
Mobile Computing Lab.
Computer Network
2009/Fall
31
Gihwan Cho
Virtual Circuit
Diagram
Mobile Computing Lab.
Computer Network
2009/Fall
32
Gihwan Cho
Virtual Circuits vs. Datagram

Virtual circuits




network can provide sequencing and error control
packets are forwarded more quickly
no routing decisions to make
less reliable
failure of a node lose all circuits through that node
Datagram



no call setup phase
better if few packets
more flexible
routing can be used to avoid congested parts of the network
more reliable
if a node fails, find an alternate route
Mobile Computing Lab.
Computer Network
2009/Fall
33
Gihwan Cho
Packet Size
Mobile Computing Lab.
Computer Network
2009/Fall
34
Gihwan Cho
Circuit vs. Packet Switching
Mobile Computing Lab.
Computer Network
2009/Fall
35
Gihwan Cho
X.25 (I)

ITU-T standard for interface between an attached device
and a packet switched network


it is a traditional packet switched networks
Defines three layers



physical
link
packet
Mobile Computing Lab.
Computer Network
2009/Fall
36
Gihwan Cho
X.25 (II)

Physical




Link


interface between DTE and DCE
physical layer specification is X.21
can substitute alternative such as EIA-232
Link Access Protocol Balanced (LAPB) as a subset of HDLC
Packet



provides a logical connections (virtual circuit) between
subscribers
all data in this connection form a single stream between the end
stations
established on demand
Mobile Computing Lab.
Computer Network
2009/Fall
37
Gihwan Cho
X.25 (III)

Use of virtual circuits
Mobile Computing Lab.
Computer Network
2009/Fall
38
Gihwan Cho
Issues with X.25

Key features include




So, it has considerable overhead


call control packets, in band signaling
multiplexing of virtual circuits at layer 3
layers 2 and 3 include flow and error control
not appropriate for modern digital systems with high reliability
Frame relay designed to eliminate most X.25 overhead
Mobile Computing Lab.
Computer Network
2009/Fall
39
Gihwan Cho
Frame Relay

Key differences are





It can be used for access speeds up to and over 2Mbps
With frame relay




call control carried in separate logical connection
multiplexing and switching at layer 2
no hop by hop error or flow control, hence end to end flow and
error control (if used) are done by higher layer
not protected by flow or error control
uses separate connection for call control
overall results in significantly less work in network
Replaced with a much matured standard, ATM
Mobile Computing Lab.
Computer Network
2009/Fall
40
Gihwan Cho
Chapter 11 : Asynchronous Transfer Mode

Similarities between ATM and packet switching




In ATM flow on each logical connection is in fixed sized
packets called cells
Minimal error and flow control


transfer of data in discrete chunks
multiple logical connections over single physical interface
reduced overhead
Data rates (physical layer)




622.08Mbps
155.52Mbps
51.84Mbps
25.6Mbps
Mobile Computing Lab.
Computer Network
2009/Fall
41
Gihwan Cho
Protocol Architecture
Mobile Computing Lab.
Computer Network
2009/Fall
42
Gihwan Cho
Reference Model Planes

User plane


Control plane


provides for user information transfer
call and connection control
Management plane


plane management
whole system functions
layer management
resources and parameters in protocol entities
Mobile Computing Lab.
Computer Network
2009/Fall
43
Gihwan Cho
ATM Logical Connections

Virtual channel connections (VCC)






analogous to virtual circuit in X.25
basic unit of switching
between two end users
full duplex flow of fixed size cells
data, user-network exchange (control) and network-network
exchange (network management and routing)
Virtual path connection (VPC)


bundle of VCC with same end points
reduce the control cost by grouping connections sharing
common paths into a single unit
Mobile Computing Lab.
Computer Network
2009/Fall
44
Gihwan Cho
ATM Connection Relationships

VPC : bundle of VCC with same end points

Advantages of virtual paths

simplified network architecture
increased network performance and reliability
reduced processing
short connection setup time
enhanced network services




Mobile Computing Lab.
Computer Network
2009/Fall
45
Gihwan Cho
ATM Cells

Fixed size





5 octet header
48 octet information field
Small cells reduce queuing delay for high priority cells
Small cells can be switched more efficiently
Easier to implement switching of small cells in hardware
Mobile Computing Lab.
Computer Network
2009/Fall
46
Gihwan Cho
ATM Cell Format
Mobile Computing Lab.
Computer Network
2009/Fall
47
Gihwan Cho
ATM Adaptation Layer


Support for information transfer protocol not based on ATM
PCM (voice)



IP (Internet Protocol)



assemble bits into cells
re-assemble into constant flow
map fragmented IP packets onto ATM cells
use LAPF (Link Access Procedure for Frame-Mode Bearer
Services) over ATM to retain all IP infrastructure
Issues with ATM




currently, most users are used to make use of TCP/IP
it is well known the adaptation overhead is too high
even, TCP/IP never utilizes the good features of ATM
so, ATM is getting to be disappeared from the early 2000’s
Mobile Computing Lab.
Computer Network
2009/Fall
48
Gihwan Cho
Chapter 12 : Routing in Switched Network


Many connections will need paths through more than
one switch
Need to find a route



Public telephone switches are a tree structure


efficiency
resilience
static routing uses the same approach all the time
Dynamic routing allows for changes in routing depending
on traffic situations

uses a peer structure for nodes
Mobile Computing Lab.
Computer Network
2009/Fall
49
Gihwan Cho
Routing in Packet Switched Network


Complex, crucial aspect of packet switched networks
Characteristics required







correctness
simplicity
robustness
stability
fairness
optimality
efficiency
Mobile Computing Lab.
Computer Network
2009/Fall
50
Gihwan Cho
Performance Criteria


Used for selection of route
Approach for the optimum route



minimum-hop (least number of nodes)
least-cost(more common)
the higher data rate, the lower the cost
the lower delay, the lower the cost
least-cost algorithms
Dijkstra’s algorithm
Bellman-Ford algorithm
Mobile Computing Lab.
Computer Network
2009/Fall
51
Gihwan Cho
Example Packet Switched Network
Mobile Computing Lab.
Computer Network
2009/Fall
52
Gihwan Cho
Decision Time and Place

Time


packet or virtual circuit basis
Place



distributed routing
made by each node
centralized routing
made by some designated node
network control center
source routing
made by source station
allows the user to dictate a route
Mobile Computing Lab.
Computer Network
2009/Fall
53
Gihwan Cho
Network Information Source and
Update Timing


Routing decisions usually based on knowledge of
network (not always)
Distributed routing



Central routing


nodes use local knowledge, i.e., the cost of outgoing link
may collect information from adjacent nodes
collect information from all nodes
Update timing



when network information is used, updated
fixed routing : never updated , simple, not sensible
adaptive routing : regular updates , more overload
Mobile Computing Lab.
Computer Network
2009/Fall
54
Gihwan Cho
Routing Strategies (I)

Fixed routing







single permanent route for each source to destination pair
determine routes using a least cost algorithm
route fixed, at least until a change in network topology
no difference between routing for datagram and virtual circuits
simplicity
reliable network with a stable load
lack of flexibility
dose not react to network congestion or failures
Mobile Computing Lab.
Computer Network
2009/Fall
55
Gihwan Cho
Fixed Routing Tables
2
5
Mobile Computing Lab.
Computer Network
2009/Fall
56
Gihwan Cho
Routing Strategies (II)

Flooding







no network information required
packet sent to every neighbor
incoming packets retransmitted on every link except incoming link
eventually a number of copies will arrive at destination
nodes can remember packets already forwarded to keep network
load in bounds
each packet is uniquely numbered so duplicates can be discarded
include a hop count in packets
each time a node passes on a packet, decrements the count
by one
count reaches zero, the packet is discarded
Mobile Computing Lab.
Computer Network
2009/Fall
57
Gihwan Cho
Flooding Example
Mobile Computing Lab.
Computer Network
2009/Fall
58
Gihwan Cho
Properties and Disadvantage

All possible routes are tried


At least one packet will have taken minimum hop count
route


can be used to set up virtual circuit
All nodes are visited


very robust, military network
useful to distribute information
High traffic load
Mobile Computing Lab.
Computer Network
2009/Fall
59
Gihwan Cho
Routing Strategies (III)

Random Routing





node selects one outgoing path for retransmission of incoming
packet
selection can be random or round robin
can select outgoing path based on probability calculation (based
on data rate)
no network info needed
route is typically not least cost nor minimum hop
Mobile Computing Lab.
Computer Network
2009/Fall
60
Gihwan Cho
Routing Strategies (IV)

Adaptive routing





used by almost all packet switching networks
routing decisions change as conditions on the network change
due to failure or congestion
requires information about network
disadvantages
decisions more complex
tradeoff between quality of network info and overhead
reacting too quickly can cause oscillation
reacting too slowly means info may be irrelevant
advantages
improved performance
aid congestion control
due to its complexity, it may not realize theoretical benefits
Mobile Computing Lab.
Computer Network
2009/Fall
61
Gihwan Cho
ARPANET Routing Evolution (I)

1st generation : 1969



distributed adaptive using estimated delay, such as queue length
use Bellman-ford algorithm
doesn’t consider line speed, just queue length
queue length not a good measurement of delay
responds slowly to congestion
2nd generation : 1979




distributed adaptive using measured delay, such as timestamps
of arrival, departure & ACK times
re-computes average delays every 10secs
any changes are flooded to all other nodes
use Dijkstra’s algorithm
good under light, medium loads, but under heavy loads, little
correlation between reported delays and those experienced
Mobile Computing Lab.
Computer Network
2009/Fall
62
Gihwan Cho
ARPANET Routing Evolution (II)

3rd generation : 1987




link cost calculations changed
to damp routing oscillations
and reduce routing overhead
measure average delay over last 10 secs and transform into link
utilization estimate
normalize this based on current value and previous results
set link cost as function of average utilization
Mobile Computing Lab.
Computer Network
2009/Fall
63
Gihwan Cho
Least Cost Algorithms

Basis for routing decisions



Given network of nodes connected by bi-directional links



each link has a cost in each direction
Define cost of path between two nodes as sum of costs
of links traversed
For each pair of nodes, find path with least cost


can minimize hop with each link cost 1
can have link value inversely proportional to capacity
nb. link costs in different directions may be different
Alternatives: Dijkstra or Bellman-Ford algorithms
Mobile Computing Lab.
Computer Network
2009/Fall
64
Gihwan Cho
Dijkstra’s Algorithm Definitions

Find shortest paths from given source node to all other
nodes, by developing paths in order of increasing path
length




w(i, j) = link cost from node i to node j




N = set of nodes in the network
s = source node
T = set of nodes so far incorporated by the algorithm
w(i, i) = 0
w(i, j) =  if the two nodes are not directly connected
w(i, j)  0 if the two nodes are directly connected
L(n) = cost of least-cost path from node s to node n
currently known

at termination, L(n) is cost of least-cost path from s to n
Mobile Computing Lab.
Computer Network
2009/Fall
65
Gihwan Cho
Dijkstra’s Algorithm Method

Step 1 [initialization]




Step 2 [get next node]




find neighboring node not in T with least-cost path from s
incorporate node into T
also incorporate the edge that is incident on that node and a node in T
that contributes to the path
Step 3 [update least-cost paths]



T = {s} set of nodes so far incorporated consists of only source node
L(n) = w(s, n) for n ≠ s
initial path costs to neighboring nodes are simply link costs
L(n) = min[L(n), L(x) + w(x, n)] for all n  T
if latter term is minimum, path from s to n is path from s to x
concatenated with edge from x to n
Algorithm terminates when all nodes have been added to T
Mobile Computing Lab.
Computer Network
2009/Fall
66
Gihwan Cho
Example of Dijkstra’s Algorithm
Mobile Computing Lab.
Computer Network
2009/Fall
67
Gihwan Cho
Results of Example Dijkstra’s Algorithm
Iteration
T
L(2)
Path
L(3)
Path
L(4)
Path
L(5)
Path
L(6)
Path
1
{1}
2
1–2
5
1-3
1
1–4

-

-
2
{1,4}
2
1–2
4
1-4-3
1
1–4
2
1-4–5

-
3
{1, 2, 4}
2
1–2
4
1-4-3
1
1–4
2
1-4–5

-
4
{1, 2, 4,
5}
2
1–2
3
1-4-5–3
1
1–4
2
1-4–5
4
1-4-5–6
5
{1, 2, 3,
4, 5}
2
1–2
3
1-4-5–3
1
1–4
2
1-4–5
4
1-4-5–6
6
{1, 2, 3,
4, 5, 6}
2
1-2
3
1-4-5-3
1
1-4
2
1-4–5
4
1-4-5-6
Mobile Computing Lab.
Computer Network
2009/Fall
68
Gihwan Cho
Bellman-Ford Algorithm Definitions

Idea





s = source node
w(i, j) = link cost from node i to node j




find shortest paths from given node subject to constraint that paths
contain at most one link
find the shortest paths with a constraint of paths of at most two links
…
w(i, i) = 0
w(i, j) =  if the two nodes are not directly connected
w(i, j)  0 if the two nodes are directly connected
Lh(n) = cost of least-cost path from s to n under constraint of
no more than h links

h = maximum # of links in path at current stage of the algorithm
Mobile Computing Lab.
Computer Network
2009/Fall
69
Gihwan Cho
Bellman-Ford Algorithm Method

Step 1 [initialization]



L0(n) = , for all n  s
Lh(s) = 0, for all h
Step 2 [update]




for each successive h  0, n ≠ s
compute Lh+1(n)=minj[Lh(j)+w(j,n)]
connect n with predecessor node j that achieves minimum
eliminate any connection of n with different predecessor node
formed during an earlier iteration
path from s to n terminates with link from j to n
Mobile Computing Lab.
Computer Network
2009/Fall
70
Gihwan Cho
Example of Bellman-Ford Algorithm
Mobile Computing Lab.
Computer Network
2009/Fall
71
Gihwan Cho
Results of Bellman-Ford Example
h Lh(2)
Path
Lh(3) Path
Lh(4)
Path
Lh(5)
Path
Lh(6)
Path
0 
-

-

-

-

-
1 2
1-2
5
1-3
1
1-4

-

-
2 2
1-2
4
1-4-3
1
1-4
2
1-4-5
10
1-3-6
3 2
1-2
3
1-4-5-3 1
1-4
2
1-4-5
4
1-4-5-6
4 2
1-2
3
1-4-5-3 1
1-4
2
1-4-5
4
1-4-5-6
Mobile Computing Lab.
Computer Network
2009/Fall
72
Gihwan Cho
Comparison


Results from two algorithms agree
Information gathered


Bellman-Ford
calculation for node n involves knowledge of link cost to all
neighboring nodes plus total cost to each neighbor from s
each node can maintain set of costs and paths for other node
can exchange information with direct neighbors
can update costs and paths based on information from
neighbors and knowledge of link costs
Dijkstra
each node needs complete topology
must know link costs of all links in network
must exchange information with all other nodes
Mobile Computing Lab.
Computer Network
2009/Fall
73
Gihwan Cho
Evaluation

Dependent on







processing time of algorithms
amount of information required from other nodes
Implementation specific
Both converge under static topology and costs
Converge to same solution
If link costs change, algorithms will attempt to catch up
If link costs depend on traffic, which depends on routes
chosen, then feedback

may result in instability
Mobile Computing Lab.
Computer Network
2009/Fall
74
Gihwan Cho
Chapter 13 : Congestion Control in
Data Networks





Congestion occurs when the number of packets being
transmitted through the network approaches the packet
handling capacity of the network
Congestion control aims to keep number of packets
below level at which performance falls off dramatically
Data network is a network of queues
Generally 80% utilization is critical
Finite queues mean data may be lost
Mobile Computing Lab.
Computer Network
2009/Fall
75
Gihwan Cho
Effects of Congestion




Packets arriving are stored at input buffers
Routing decision made
Packet moves to output buffer
Packets queued for output transmitted as fast as
possible




statistical time division multiplexing
If packets arrive to fast to be routed, or to be output,
buffers will fill
Can discard packets
Can use flow control

can propagate congestion through network
Mobile Computing Lab.
Computer Network
2009/Fall
76
Gihwan Cho
Interaction of Queues
Mobile Computing Lab.
Computer Network
2009/Fall
77
Gihwan Cho
Ideal vs. Practical
Performance

Practical performance



ideal assumes infinite
buffers and no overhead
buffers are finite
overheads occur in
exchanging congestion
control messages
Mobile Computing Lab.
Computer Network
2009/Fall
78
Gihwan Cho
Effects of
Congestion No Control
Mobile Computing Lab.
Computer Network
2009/Fall
79
Gihwan Cho
Mechanisms for Congestion Control
Mobile Computing Lab.
Computer Network
2009/Fall
80
Gihwan Cho
Backpressure

If a node becomes congested it can slow down or halt
flow of packets from other nodes






may mean that other nodes have to apply control on incoming
packet rates
propagates back to source
Can restrict to logical connections generating most traffic
Used in connection oriented that allow hop by hop
congestion control (e.g. X.25)
Not used in ATM nor frame relay
Only recently developed for IP
Mobile Computing Lab.
Computer Network
2009/Fall
81
Gihwan Cho
Choke Packet

Control packet




generated at congested node
sent to source node
e.g. ICMP source quench
from router or destination
source cuts back until no more source quench message
sent for every discarded packet, or anticipated
Rather crude mechanism
Mobile Computing Lab.
Computer Network
2009/Fall
82
Gihwan Cho
Congestion Signaling

Implicit congestion signaling






transmission delay may increase with congestion
packet may be discarded
source can detect these as implicit indications of congestion
useful on connectionless (datagram) networks
used in frame relay LAPF
Explicit congestion signaling




network alerts end systems of increasing congestion
end systems take steps to reduce offered load
backwards
congestion avoidance in opposite direction to packet required
forwards
congestion avoidance in same direction as packet required
Mobile Computing Lab.
Computer Network
2009/Fall
83
Gihwan Cho
Categories of Explicit Signaling

Binary


Credit based



a bit set in a packet indicates congestion
indicates how many packets source may send
common for end to end flow control
Rate based


supply explicit data rate limit
e.g. ATM
Mobile Computing Lab.
Computer Network
2009/Fall
84
Gihwan Cho
Traffic Management

Fairness


Quality of service


provide equal treatment of various flows
different treatment for different connections
Reservations


traffic contract between user and network
carry best-effort or discard excess traffic
Mobile Computing Lab.
Computer Network
2009/Fall
85
Gihwan Cho
Congestion Control in Packet
Switched Networks

Send control packet to some or all source nodes


Rely on routing information


may react too quickly
End to end probe packets


requires additional traffic during congestion
adds to overhead
Add congestion info to packets as they cross nodes

either backwards or forwards
Mobile Computing Lab.
Computer Network
2009/Fall
86
Gihwan Cho
Capter14 : Cellular Wireless Networks




Key technology for mobiles, wireless nets etc
Developed to increase mobile phone capacity
Based on multiple low power transmitters
Area divided into cells





in a tiling pattern to provide full coverage
each with own antenna
each with own range of frequencies
served by base station
adjacent cells use different frequencies to avoid crosstalk
Mobile Computing Lab.
Computer Network
2009/Fall
87
Gihwan Cho
Cellular Network Organization

Multiple low power transmitters


100w or less
Area divided into cells




each with own antenna
each with own range of frequencies
served by base station
transmitter, receiver, control unit
adjacent cells on different frequencies to avoid crosstalk
Mobile Computing Lab.
Computer Network
2009/Fall
88
Gihwan Cho
Shape of Cells


Square
 width d cell has 4 neighbors at distance d and 4 at distance
 better if all adjacent antennas equidistant
simplifies choosing and switching to new antenna
Hexagon
 provides equidistant antennas
 radius defined as radius of circum-circle
distance from center to vertex equals length of side
 distance between centers of cells radius R is 3 R
 not always precise hexagons
topographical limitations
local signal propagation conditions
location of antennas
Mobile Computing Lab.
Computer Network
2009/Fall
89
Gihwan Cho
2d
Cellular Geometries
Mobile Computing Lab.
Computer Network
2009/Fall
90
Gihwan Cho
Frequency Reuse (I)


Must manage reuse of frequencies
Power of base transceiver controlled





allow communications within cell on given frequency
limit escaping power to adjacent cells
allow re-use of frequencies in nearby cells
typically 10 – 50 frequencies per cell
example for Advanced Mobile Phone Service (AMPS)
N cells all using same number of frequencies
K total number of frequencies used in systems
each cell has K/N frequencies
K=395, N=7 giving 57 frequencies per cell on average
Mobile Computing Lab.
Computer Network
2009/Fall
91
Gihwan Cho
Frequency Reuse (II)

Pattern
Mobile Computing Lab.
Computer Network
2009/Fall
92
Gihwan Cho
Increasing Capacity

Add new channels


Frequency borrowing


use smaller cells in high use areas
cell sectoring



taken from adjacent cells by congested cells
Cell splitting


not all channels used to start with
cell divided into wedge shaped sectors (3–6 per cell)
directional antennas
microcells

use reduced power to cover a much smaller area
Mobile Computing Lab.
Computer Network
2009/Fall
93
Gihwan Cho
Call Stages
Mobile Computing Lab.
Computer Network
2009/Fall
94
Gihwan Cho
Lecture Topic V
Internet and Transport
Protocols
The fundamental problem of communication is
that of reproducing at one point either exactly or approximately
a message selected at another point
the mathematical theory of communication, Claude Shannon
Mobile Computing Lab.
Computer Network
2009/Fall
95
Gihwan Cho
Chapter 18 : Internetwork Protocols

Protocol functions have a small set of functions that form
basis of all protocols









encapsulation
fragmentation and reassembly
connection control
ordered delivery
flow control
error control
addressing
multiplexing
transmission services
Mobile Computing Lab.
Computer Network
2009/Fall
96
Gihwan Cho
Encapsulation

Data usually transferred in blocks




Three categories of control





protocol data units (PDUs)
each PDU contains data and control information
some PDUs only control
address of sender and/or receiver
error-detecting code, e.g. frame check sequence
protocol control
additional information to implement protocol functions
Addition of control information to data is encapsulation
Data accepted or generated by entity and encapsulated
into PDU

containing data plus control information
Mobile Computing Lab.
Computer Network
2009/Fall
97
Gihwan Cho
Fragmentation and Reassembly
(Segmentation – OSI)



Exchange data between two entities
Lower-level protocols may need to break data up into
smaller blocks, so it is called fragmentation
For various reasons




network only accepts blocks of a certain size, such as ATM 53
octets, Ethernet 1526 octets
more efficient error control & smaller retransmission units
fairer access to shared facilities
smaller buffers
Mobile Computing Lab.
Computer Network
2009/Fall
98
Gihwan Cho
Disadvantages of Fragmentation

Make PDUs as large as possible because



PDU arrival generates interrupt



PDU contains some control information
smaller block, larger overhead
smaller blocks, more interrupts
More time processing smaller, more numerous PDUs
Reassembly


segmented data must be reassembled into messages
more complex if PDUs out of order
Mobile Computing Lab.
Computer Network
2009/Fall
99
Gihwan Cho
PDUS and Fragmentation
Mobile Computing Lab.
Computer Network
2009/Fall
100
Gihwan Cho
Connection Control

Connectionless data transfer


Connection-oriented data transfer




each PDU treated independently, e.g. datagram
involves a logical association, or connection, established
between entities
preferred (even required) for lengthy data exchange
or if protocol details are worked out dynamically
Three phases occur for connection-oriented




connection establishment
data transfer
connection termination
may be interrupt and recovery phases to handle errors
Mobile Computing Lab.
Computer Network
2009/Fall
101
Gihwan Cho
Phases of Connection Oriented
Transfer
Mobile Computing Lab.
Computer Network
2009/Fall
102
Gihwan Cho
Connection Establishment


Entities agree to exchange data
Typically, one station issues connection request







in connectionless fashion
Receiving entity accepts or rejects (simple)
May include negotiation
Syntax, semantics, and timing
Both entities must use same protocol
May allow optional features
Must be agreed

e.g. protocol may specify max PDU size 8000 octets; one station
may wish to restrict to 1000 octets
Mobile Computing Lab.
Computer Network
2009/Fall
103
Gihwan Cho
Data Transfer and Termination

Both data and control information exchanged




e.g. flow control, error control
Data flow and acknowledgements may be in one or both
directions
One side may send termination request
Or central authority might terminate
Mobile Computing Lab.
Computer Network
2009/Fall
104
Gihwan Cho
Sequencing

Many connection-oriented protocols use sequencing


All connection-oriented protocols include some way of
identifying connection



unique connection identifier
combination of source and destination addresses
PDUs numbered sequentially


e.g. HDLC, IEEE 802.11
each side keeps track of outgoing and incoming numbers
Supports three main functions



ordered delivery
flow control
error control
Mobile Computing Lab.
Computer Network
2009/Fall
105
Gihwan Cho
Ordered Delivery

PDUs may arrive out of order


PDU order must be maintained



different paths through network
so, number PDUs sequentially
Easy to reorder received PDUs
Use finite sequence number field



numbers repeat modulo maximum number
maximum sequence number greater than maximum number of
PDUs that could be outstanding
in fact, maximum number may need to be twice maximum
number of PDUs that could be outstanding
e.g. selective-repeat ARQ
Mobile Computing Lab.
Computer Network
2009/Fall
106
Gihwan Cho
Flow Control



receiving entity limits amount / rate of data sent
simplest protocol is stop-and-wait
more efficient protocols use concept of credit


amount of data sent without acknowledgment
Must be implemented in several protocols



network traffic control
buffer space
application overflow
e.g. waiting for disk access
Mobile Computing Lab.
Computer Network
2009/Fall
107
Gihwan Cho
Error Control


To guard against loss or damage
Implemented as separate error detection and
retransmission functions





Can use an error-correction code


sender inserts error-detecting code in PDU
receiver checks code on incoming PDU
if error, discard
if transmitter doesn’t get acknowledgment in reasonable time,
retransmit
enables receiver to detect and possibly correct errors
Performed at various protocol layers
Mobile Computing Lab.
Computer Network
2009/Fall
108
Gihwan Cho
TCP/IP Concepts : for Addressing
Mobile Computing Lab.
Computer Network
2009/Fall
109
Gihwan Cho
Addressing Level



Level in comm. architecture at which entity is named
Have unique address for each end system e.g., server
and each intermediate system, e.g., router
Network-level address to route PDU through network



IP address or internet address
OSI - network service access point (NSAP)
At destination data must routed to some process



each process assigned an identifier
TCP/IP port
service access point (SAP) in OSI
Mobile Computing Lab.
Computer Network
2009/Fall
110
Gihwan Cho
Addressing Scope

Global address which identifies unique system






Need unique address for each interface on network




unambiguous
synonyms permitted
system may have more than one global address
global applicability
enables internet to route data between any two systems
MAC address on IEEE 802 network and ATM host address
enables network to route data units through network
Only relevant for network-level addresses
Port or SAP above network level is unique within system
Mobile Computing Lab.
Computer Network
2009/Fall
111
Gihwan Cho
Connection Identifiers


Used by both entities for future transmissions
Reduced overhead


Routing


connection identifier identifies route to intermediate systems
Multiplexing



generally shorter than global identifiers
entity may wish more than one connection simultaneously
PDUs must be identified by connection identifier
Once connection established, end systems can maintain
state information about connection

flow and error control using sequence numbers
Mobile Computing Lab.
Computer Network
2009/Fall
112
Gihwan Cho
Addressing Mode

Usually address refers to single system or port


individual or unicast address
Address can refer to more than one entity or port



multiple simultaneous recipients for data
broadcast for all entities within domain
multicast for specific subset of entities
Mobile Computing Lab.
Computer Network
2009/Fall
113
Gihwan Cho
Multiplexing

Multiple connections into single system



Upward multiplexing


e.g. frame relay, can have multiple data link connections
terminating in single end system
e.g. multiple TCP connections to given system
have multiple higher level connections over a single lower level
connection
Downward multiplexing

have single higher level connection built on multiple lower level
connections
Mobile Computing Lab.
Computer Network
2009/Fall
114
Gihwan Cho
Transmission Services

Protocol may provide additional services to entities, as




priority
connection basis
on message basis
quality of service
e.g. minimum throughput or maximum delay threshold
security
security mechanisms, restricting access
These services depend on underlying transmission
system and lower-level entities
Mobile Computing Lab.
Computer Network
2009/Fall
115
Gihwan Cho
Internetworking Terms (I)

Communications network


An internet


collection of communications networks interconnected by
bridges and/or routers
The Internet (note upper case I)


facility that provides data transfer service
the global collection of thousands of individual machines and
networks
Intranet


corporate internet operating within the organization
uses Internet (TCP/IP and http) technology to deliver documents
and resources
Mobile Computing Lab.
Computer Network
2009/Fall
116
Gihwan Cho
Internetworking Terms (II)

End System (ES)



Intermediate System (IS)



device used to connect two networks
permits comm. between end systems attached to different networks
Bridge : OSI layer 2 (data link)



device attached to one of the networks of an internet
supports end-user applications or services
IS used to connect two LANs using similar LAN protocols
address filter passing on packets to the required network only
Router : OSI layer 3 (network)


connects two (possibly dissimilar) networks
uses internet protocol present in each router and end system
Mobile Computing Lab.
Computer Network
2009/Fall
117
Gihwan Cho
Requirements of Internetworking

Link between networks




minimum physical and link layer
Routing and delivery of data between processes on
different networks
Accounting services and status info
Independent of network architectures
Mobile Computing Lab.
Computer Network
2009/Fall
118
Gihwan Cho
Architectural Approaches (I)

Connection oriented


virtual circuit
Connectionless




datagram
PDU’s routed independently from source ES to destination ES
through routers and networks
share common network layer protocol, e.g. IP
below have network access on each node
Mobile Computing Lab.
Computer Network
2009/Fall
119
Gihwan Cho
Architectural Approaches(II)

Connectionless internetworking (cont.)


advantages
flexibility
robust
no unnecessary overhead
unreliable
not guaranteed delivery
not guaranteed order of delivery
 packets can take different routes
reliability is responsibility of next layer up (e.g. TCP)
Mobile Computing Lab.
Computer Network
2009/Fall
120
Gihwan Cho
IP Operation
Mobile Computing Lab.
Computer Network
2009/Fall
121
Gihwan Cho
The Internet
as a Network

Design issues





routing
datagram lifetime
fragmentation
error control
flow control
Mobile Computing Lab.
Computer Network
2009/Fall
122
Gihwan Cho
Design Issues (I)

Routing

end systems and routers maintain routing tables
indicate next router to which datagram should be sent
static
 may contain alternative routes
dynamic
 flexible response to congestion and errors


source routing
source specifies route as sequential list of routers to be
followed
for the sake of security and/or priority
route recording
Mobile Computing Lab.
Computer Network
2009/Fall
123
Gihwan Cho
Design Issues (II)

Datagram lifetime


datagrams could loop indefinitely
consumes resources
transport protocol may need upper bound on datagram life
datagram can be marked with lifetime
time to live field in IP
once lifetime expires, datagram discarded (not forwarded)
hop count
 decrement time to live on passing through a each router
time count
 need to know how long since last router
Mobile Computing Lab.
Computer Network
2009/Fall
124
Gihwan Cho
Design Issues (III-1)

Fragmentation and re-assembly


may have different packet sizes on networks
issue of when to re-assemble
at destination
 results in packets getting smaller as data traverses internet
intermediate re-assembly
 need large buffers at routers
 buffers may fill with fragments
 all fragments must go through same router
 inhibits dynamic routing
Mobile Computing Lab.
Computer Network
2009/Fall
125
Gihwan Cho
Design Issues (III-2)

IP fragmentation


IP re-assembles at destination only
uses fields in header
data unit identifier (ID)
 identifies end system originated datagram
 source and destination address
 protocol layer generating data (e.g. TCP)
 identification supplied by that layer
data length
 length of user data in octets
offset
 position of fragment of user data in original datagram
 in multiples of 64 bits (8 octets)
more flag
 indicates that this is not the last fragment
Mobile Computing Lab.
Computer Network
2009/Fall
126
Gihwan Cho
Fragmentation Example
Mobile Computing Lab.
Computer Network
2009/Fall
127
Gihwan Cho
Design Issues (III-3)

Dealing with failure




re-assembly may fail if some fragments get lost
need to detect failure
re-assembly time out
assigned to first fragment to arrive
if timeout expires before all fragments arrive, discard partial
data
use packet lifetime (time to live in IP)
if time to live runs out, kill partial data
Mobile Computing Lab.
Computer Network
2009/Fall
128
Gihwan Cho
Design Issues (IV)

Error control







not guaranteed delivery
router should attempt to inform source if packet discarded
e.g. for time to live expiring
source may modify transmission strategy
may inform high layer protocol
datagram identification needed
see ICMP
Flow control




allows routers and/or stations to limit rate of incoming data
limited in connectionless systems
send flow control packets
requesting reduced flow
see ICMP
Mobile Computing Lab.
Computer Network
2009/Fall
129
Gihwan Cho
Internet Protocol (IP) Version 4

Part of TCP/IP, which is used by the Internet





defined in RFC 791
specifies interface with higher layer, e.g. TCP
specifies protocol format and mechanisms
will (eventually) be replaced by IPv6
IP services


primitives
functions to be performed
form of primitive implementation dependent
send : request transmission of data unit
deliver : notify user of arrival of data unit
parameters
used to pass data and control info
Mobile Computing Lab.
Computer Network
2009/Fall
130
Gihwan Cho
IP Services : Parameters (I)



Source address
Destination address
Protocol


Type of Service


recipient e.g. TCP
specify treatment of data unit during transmission through
networks
Identification




source, destination address and user protocol
uniquely identifies PDU
needed for re-assembly and error reporting
send only
Mobile Computing Lab.
Computer Network
2009/Fall
131
Gihwan Cho
IP Services : Parameters (II)

Don’t fragment indicator





Time to live
Data length
Option data






whether IP can fragment data
if not, may not be possible to deliver
security
source routing
route recording
stream identification
timestamping
User data
Mobile Computing Lab.
Computer Network
2009/Fall
132
Gihwan Cho
IP Protocol
Mobile Computing Lab.
Computer Network
2009/Fall
133
Gihwan Cho
IP Protocol : Header Fields (I)

Version



Internet header length




in 32 bit words
including options
Type of service
Total length


currently 4
IP v6 - see later
of datagram, in octets
Identification


sequence number
used with addresses and user protocol to identify datagram
uniquely
Mobile Computing Lab.
Computer Network
2009/Fall
134
Gihwan Cho
IP Protocol : Header Fields (II)

Flags





Fragmentation offset
Time to live
Protocol


more bit
don’t fragment
next higher layer to receive data field at destination
Header checksum



reverified and recomputed at each router
16 bit ones complement sum of all 16 bit words in header
set to zero during calculation
Mobile Computing Lab.
Computer Network
2009/Fall
135
Gihwan Cho
IP Protocol : Header Fields (III)




Source address
Destination address
Options
Padding


to fill to multiple of 32 bits long
Data



carries user data from next layer up
integer multiple of 8 bits long (octet)
max length of datagram (header plus data) 65,535 octets
Mobile Computing Lab.
Computer Network
2009/Fall
136
Gihwan Cho
IP Address Formats
Mobile Computing Lab.
Computer Network
2009/Fall
137
Gihwan Cho
IP Addresses (I)



32 bit global Internet address
Network part and host part
Class A





start with binary 0
all 0 reserved
01111111 (127) reserved for loopback
range 1.x.x.x to 126.x.x.x
all allocated
Mobile Computing Lab.
Computer Network
2009/Fall
138
Gihwan Cho
IP Addresses (II)

Class B






start 10
range 128.x.x.x to 191.x.x.x
second octet also included in network address
214 = 16,384 class B addresses
all allocated
Class C





start 110
range 192.x.x.x to 223.x.x.x
second and third octet also part of network address
221 = 2,097,152 addresses
nearly all allocated
see IPv6
Mobile Computing Lab.
Computer Network
2009/Fall
139
Gihwan Cho
Subnets and Subnet Masks

Internet allows arbitrary complexity of internetworked
LANs within organization



Each LAN has to be assigned an IP address


it required the central authority to handle all requests for address
for networks, of which there were many more than anticipated
One possible way is that host portion of IP address is
partitioned into subnet number and host number


insulate overall Internet from growth of network numbers and
routing complexity
site looks to rest of Internet like single network
local routers route within subnetted network
Subnet mask indicates which bits are subnet number
and which are host number
Mobile Computing Lab.
Computer Network
2009/Fall
140
Gihwan Cho
IP Addresses and Subnet Masks
(a) Dotted Decimal and binary representations of IP address and subnet masks
(b) Default Subnet Masks
Mobile Computing Lab.
Computer Network
2009/Fall
141
Gihwan Cho
Routing Using Subnets
Mobile Computing Lab.
Computer Network
2009/Fall
142
Gihwan Cho
Mapping IP Addresses to the DL

Consider an 802.3 LAN running IP




recall DL has it’s own 48-bit addresses used to identify LLC
entities on the LAN
NL superimposes an internetwork on top of the LAN and
provides it’s own 32-bit IP address space
DL knows nothing about IP addresses
How do these two sets of addresses get mapped to
each other?
That’s
me!
Who is
1.2.3.4?
A
B
C
D
Ethernet
Mobile Computing Lab.
Computer Network
2009/Fall
143
Gihwan Cho
Address Resolution Protocol (ARP) (I)

Another control protocol which resides at the NL is ARP




ARP builds a DL broadcast frame with a packet “what’s the DL
address for IP address w.x.y.z?” and sends it
broadcast frame is received by all hosts and one says “that’s me!”
or another says “I know”
ARP is a low-level protocol that hides the underlying
network physical addressing, permitting one to assign an
arbitrary IP address to every machine
Now, the broadcasting is too expensive. How can it be
solved?

when a host receives an ARP reply, it saves the sender’s IP
address and corresponding physical address in its cache for
successive lookups
Mobile Computing Lab.
Computer Network
2009/Fall
144
Gihwan Cho
Address Resolution Protocol (ARP) (II)

Is it be possible more refinement?



the sender’s IP-to-physical address binding is included in every
ARP broadcast; receivers update the binding in their cache
ARP is a part of the physical network system, and is not a
part of the Internet protocols
Reverse address resolution protocol (RARP)


ARP finds out Ethernet address that corresponds to a given IP
RARP finds the IP address of the host using an Ethernet address
associated with the Ethernet card
when the machine is booted, it broadcasts its 48-bit Ethernet
address and ask for its IP address
RARP server that is available at each network responds with
the IP address
Mobile Computing Lab.
Computer Network
2009/Fall
145
Gihwan Cho
Table Driven IP Routing



IP routing algorithm employs an Internet routing table on
each machine (host and router), which contains info. about
the possible destinations and how to reach them
It consults the table to decide where to send the datagram
Then, what information should be kept in routing tables?



minimal information principle : keep network prefix only
- makes routing efficient and keeps routing table small
information hiding principle : the details of specific hosts confined
to the local environment : next-hop routing
- the routing table in a router only specifies one step along the
path from the router to a destination
Default routing : If no route appears in the table, the
routing routines send the datagram to a default router

it makes their routing decisions efficiently to possible distant dest.
Mobile Computing Lab.
Computer Network
2009/Fall
146
Gihwan Cho
Table Driven IP Routing (An Example)
20.0.0.5
Internet
Q
00.0.0.5
Mobile Computing Lab.
30.0.0.6
Network
20.0.0.0
R
20.0.0.6
40.0.0.7
Network
30.0.0.0
S
Network
40.0.0.0
30.0.0.7
To reach hosts
on network
Route to
this address
20.0.0.0
Deliver Directly
30.0.0.0
Deliver Directly
40.0.0.0
30.0.0.7
50.0.0.0
30.0.0.7
Default
20.0.0.5
Computer Network
50.0.0.8
2009/Fall
T
Network
50.0.0.0
40.0.0.8
147
Gihwan Cho
IP Routing Algorithm
Route_IP_Datagram(datagram, routing_table)
Extract destination IP address, ID, from datagram
Compute IP address of destination network, IN
if IN matches any directly connected network address
send datagram to destination over that network;
else if ID appears as a host-specific route
route datagram as specified in the table;
else if IN appears in routing table
route datagram as specified in the table;
else if a default route has been specified
route datagram to the default gateway;
else declare a routing error;
Mobile Computing Lab.
Computer Network
2009/Fall
148
Gihwan Cho
Routing Protocols in IPv4

IP routing is based on the destination network ID alone, ?




all IP traffic for a given network tales the same path regardless to
the delay or throughput of physical network
only the final router can determine if the destination exists or is
operational, the router only can report the delivery to the sender
each router routes traffic independently - someone should find out
if two-way communication is always possible
IP routing selects the next hop to be sent the datagram, ?



where does IP store the next hop address? not IP itself!
IP simply passes the datagram and the next hop address to the
network interface software (so-called network driver)
the driver software responsible for the physical network over which
the datagram must be sent - binds the next hop IP address to a
physical address, forms a frame, and sends it
Mobile Computing Lab.
Computer Network
2009/Fall
149
Gihwan Cho
ICMP




Internet Control Message Protocol
RFC 792 (get it and study it)
Transfer of (control) messages from routers and hosts to
hosts
Feedback about problems


e.g. time to live expired
Encapsulated in IP datagram

not reliable
Mobile Computing Lab.
Computer Network
2009/Fall
150
Gihwan Cho
ICMP Message Formats
Mobile Computing Lab.
Computer Network
2009/Fall
151
Gihwan Cho
Why Change IP?

Address space exhaustion







two level addressing (network and host) wastes space
network addresses used even if not connected to Internet
growth of networks and the Internet
extended use of TCP/IP
single address per host
Requirements for new types of service
IPv6 RFCs



1752 - recommendations for the IP Next Generation Protocol
2460 - overall specification
2373 - addressing structure
Mobile Computing Lab.
Computer Network
2009/Fall
152
Gihwan Cho
IPv6 Enhancements

Expanded address space


Improved option mechanism


dynamic assignment of addresses
Increased addressing flexibility


separate optional headers between IPv6 header and transport
layer header (most are not examined by intermediate routes)
Address auto-configuration


128 bit
anycast - delivered to one of a set of nodes
Support for resource allocation


replaces type of service
labeling of packets to particular traffic flow
Mobile Computing Lab.
Computer Network
2009/Fall
153
Gihwan Cho
IPv6 Packet
Structure
Mobile Computing Lab.
Computer Network
2009/Fall
154
Gihwan Cho
IPv6 Header
Mobile Computing Lab.
Computer Network
2009/Fall
155
Gihwan Cho
IPv6 Flow Label




Related sequence of packets
Needing special handling
Identified by src & dest addr + flow label
Router treats flow as sharing attributes


May treat flows differently



e.g. path, resource allocation, discard requirements, accounting,
security
buffer sizes, different forwarding precedence, different quality of
service
Alternative to including all info in every header
Have requirements on flow label processing
Mobile Computing Lab.
Computer Network
2009/Fall
156
Gihwan Cho
IPv6 Addresses




128 bits long
Assigned to interface
Single interface may have multiple unicast addresses
Three types of address



unicast
single interface
anycast
set of interfaces (typically different nodes)
delivered to any one interface, usually the “nearest”
multicast
set of interfaces
delivered to all interfaces identified
Mobile Computing Lab.
Computer Network
2009/Fall
157
Gihwan Cho
Extension Headers

Hop-by-hop options


Routing




similar to v4 source routing
Fragmentation


require processing at each router
only allowed at source, no fragmentation at intermediate routers
Authentication
Encapsulating security payload
Destination options

carries optional information for destination node
Mobile Computing Lab.
Computer Network
2009/Fall
158
Gihwan Cho
IPv6 Extension Headers
Mobile Computing Lab.
Computer Network
2009/Fall
159
Gihwan Cho
Virtual Private Network

Set of computers interconnected using an insecure
network


Using encryption & special protocols to provide security



e.g. linking corporate LANs over Internet
to stop eavesdropping & unauthorized users
Proprietary solutions are problematical
Hence development of IPSec standard
Mobile Computing Lab.
Computer Network
2009/Fall
160
Gihwan Cho
IPSEC


RFC 1636 (1994) identified security need
Encryption & authentication to be IPv6


Applications needing security include:




but designed also for use with current IPv4
branch office connectivity
remote access over Internet
electronic commerce security
Benefits




provides strong security for external traffic
resistant to bypass
can be transparent to applications as well as end users
can provide security for individual users if needed
Mobile Computing Lab.
Computer Network
2009/Fall
161
Gihwan Cho
IPSEC Functions

Authentication header


Encapsulating Security Payload (ESP)


for combined authentication/encryption
A key exchange function


for authentication only
manual or automated
VPNs usually need combined function
Mobile Computing Lab.
Computer Network
2009/Fall
162
Gihwan Cho
IPSEC Scenario
Mobile Computing Lab.
Computer Network
2009/Fall
163
Gihwan Cho
Chapter 19 : Internetwork Operation

Consider mechanisms for handing growth in network
traffic





from low-volume text based terminal/email
to high volume multi-media web/voice/video
Historically, IP protocols gave best-effort datagram
delivery to all services
Now, want variety of QoS in IP networks
Explore some new network services / functions
Mobile Computing Lab.
Computer Network
2009/Fall
164
Gihwan Cho
Multicasting


Multicast means the act of sending a packet from a
source to a number of members of a multicast group
Uses






multimedia “broadcast”
teleconferencing
database
distributed computing
real time workgroups
Have design issues in addressing / routing
Mobile Computing Lab.
Computer Network
2009/Fall
165
Gihwan Cho
LAN Multicast

LAN multicast is easy






send to IEEE 802 multicast MAC address
since broadcast all stations will see packet
those in multicast group will accept it
only single copy of packet is needed
But much harder in internetwork
IP includes addresses that refer to group of hosts on one
or more networks =: multicast address

cf) IP address refers to an individual host on a particular network
Mobile Computing Lab.
Computer Network
2009/Fall
166
Gihwan Cho
Multicast Example
Mobile Computing Lab.
Computer Network
2009/Fall
167
Gihwan Cho
Broadcast, Multiple Unicast, Multicast

Broadcast a copy of packet to each network


Multiple unicast



requires 13 copies of packet
send packet only to networks that have hosts in group
11 packets
True multicast




determine least cost path to each network that has host in group
gives a spanning tree configuration containing networks with
group members
transmit single packet along spanning tree
routers replicate packets at branch points of spanning tree
8 packets required
Mobile Computing Lab.
Computer Network
2009/Fall
168
Gihwan Cho
Traffic Generated by Various
Multicasting Strategies
Mobile Computing Lab.
Computer Network
2009/Fall
169
Gihwan Cho
Requirements for Multicasting


Router may have to forward more than one copy of packet
Need convention to identify multicast addresses (IPv4
Class D or IPv6 prefix)




nodes translate between IP multicast addresses and list of
networks containing group members
router must translate between IP multicast address and network
multicast address
Mechanism required for hosts to join/leave multicast group
Routers must exchange info


which networks include members of given group
sufficient info to work out shortest path to each network
Mobile Computing Lab.
Computer Network
2009/Fall
170
Gihwan Cho
Internet Group Management Protocol
(IGMP) (I)

RFC 3376 (IGMP version 3) to exchange multicast group
info between hosts & routers on a LAN



hosts send messages to routers to subscribe to and unsubscribe
from multicast group
routers check which multicast groups of interest to which hosts
Join operation


IGMP host wants to make itself known as group member to other
hosts and routers on LAN
to join send IGMP membership report message
 address field multicast address of group
 sent in IP datagram
 current group members receive & learn new member
 routers listen to all IP multicast addresses to hear all reports
Mobile Computing Lab.
Computer Network
2009/Fall
171
Gihwan Cho
Internet Group Management Protocol
(IGMP) (II)

Keeping list valid



routers periodically issue IGMP general query message
 in datagram with all-hosts multicast address
 hosts respond with report message
router don’t know every host in a group
 each host in group sets timer with random delay
 if timer expires, host sends report
 only one member of each group reports to router
Leave operation


host leaves group by sending leave group message to all-routers
static multicast address
router determines if it have any remaining group members using
group-specific query message
Mobile Computing Lab.
Computer Network
2009/Fall
172
Gihwan Cho
Routing Protocols




Routers receive and forward packets
Make decisions based on knowledge of topology and
traffic/delay conditions
Use dynamic routing algorithm
Autonomous Systems (AS)



a group of routers exchanging information via a common routing
protocol
set of routers and networks managed by single organization
form a connected network
there is at least one route between any pair of nodes
Mobile Computing Lab.
Computer Network
2009/Fall
173
Gihwan Cho
Interior Router Protocol (IRP)
Exterior Routing Protocol (ERP)

IRP




May be more than one AS in an internetwork



passes routing information between routers within AS
can be tailored to specific applications
needs detailed model of network to function
routing algorithms and tables may differ between different AS
Routers need information about networks outside their AS
Used exterior router protocol (ERP)

supports summary information on AS reachability
Mobile Computing Lab.
Computer Network
2009/Fall
174
Gihwan Cho
Application of IRP and ERP
Mobile Computing Lab.
Computer Network
2009/Fall
175
Gihwan Cho
Approaches to Routing : Distance-vector


Each node (router or host) exchange information with
neighboring nodes
First generation routing algorithm for ARPANET



Each node maintains vector of link costs for each directly
attached network, and distance and next-hop vectors for
each destination
Requires transmission of lots of information by each
router



used by Routing Information Protocol (RIP)
distance vector to all neighbors
contains estimated path cost to all networks in configuration
Changes take long time to propagate
Mobile Computing Lab.
Computer Network
2009/Fall
176
Gihwan Cho
Approaches to Routing : Link-state





Designed to overcome drawbacks of distance-vector
Each router determines link cost on each interface
Advertises set of link costs to all other routers in topology
If link costs change, router advertises new values
Each router constructs topology of entire configuration




can calculate shortest path to each destination
use to construct routing table with first hop to each destination
Do not use distributed routing algorithm, but any suitable
alg. to determine shortest paths, eg. Dijkstra's algorithm
Open Shortest Path First (OSPF) is a link-state protocol
Mobile Computing Lab.
Computer Network
2009/Fall
177
Gihwan Cho
Exterior Router Protocols :
Not Distance-vector, Not Link-state


Both are not effective for exterior router protocol
Not Distance-vector




assumes routers share common distance metric
but different ASs may have different priorities & needs
but have no info on AS’s visited along route
Not link-state


different ASs may use different metrics and have different
restrictions
flooding of link state information to all routers unmanageable
Mobile Computing Lab.
Computer Network
2009/Fall
178
Gihwan Cho
Exterior Router Protocols : Path-vector

Alternative path-vector routing protocol





provides info about which networks can be reached by a given
router and ASs crossed to get there
does not include distance or cost estimate
hence dispenses with concept of routing metrics
Have list of all ASs visited on a route
Enables router to perform policy routing



eg. avoid path to avoid transiting particular AS
eg. link speed, capacity, tendency to become congested, and
overall quality of operation, security
eg. minimizing number of transit ASs
Mobile Computing Lab.
Computer Network
2009/Fall
179
Gihwan Cho
Border Gateway Protocol (BGP)

Developed for use with TCP/IP internets




is preferred EGP of the Internet
uses messages sent over TCP connection
Current version is BGP-4 (RFC1771)
Functional procedures



neighbor acquisition - when agree to exchange info
neighbor reachability - to maintain relationship
network reachability - to update database of routes
Mobile Computing Lab.
Computer Network
2009/Fall
180
Gihwan Cho
OSPF

IGP of Internet



Uses Link State Routing Algorithm





documented with RFC 2328
replaced Routing Information Protocol (RIP)
each router keeps list of state of local links to network
transmits update state info
little traffic as messages are small and not sent often
Uses least cost based on user cost metric
Topology stored as directed graph


vertices or nodes (router, transit or stub network)
edges (between routers or router to network)
Mobile Computing Lab.
Computer Network
2009/Fall
181
Gihwan Cho
Sample AS


Topology stored as
directed graph
Vertices or nodes



router
network
Edges


connect two router
connect router to network
Mobile Computing Lab.
Computer Network
2009/Fall
182
Gihwan Cho
Directed
Graph of AS
Mobile Computing Lab.
Computer Network
2009/Fall
183
Gihwan Cho
Operation



SFP tree for router 6
Dijkstra’s algorithm
(Appendix 0A) used to find
least cost path to all other
networks
Next hop used in routing
packets
Mobile Computing Lab.
Computer Network
2009/Fall
184
Gihwan Cho
Integrates Services Architecture (ISA)

Changes in traffic demands require variety of quality of
service




eg. internet phone, multimedia, multicast
New functionality required in routers
New means of requesting QoS
IETF developing a suite of Integrated Services
Architecture (ISA) standards

RFC 1633 defines overall view of ISA
Mobile Computing Lab.
Computer Network
2009/Fall
185
Gihwan Cho
Internet Traffic Categories

Elastic traffic





can cope with wide changes in delay and/or throughput
traditional TCP/IP traffic
eg. FTP, email, telnet, SNMP, HTTP
different sensitivity to throughput, delay, congestion
Inelastic traffic


does not easily adapt to variations
e.g. real time traffic
requirements
throughput
delay
jitter
packet loss
Mobile Computing Lab.
Computer Network
2009/Fall
186
Gihwan Cho
ISA Approach

IP nets control congestion by




routing algorithms
packet discard
Provides enhancements to traditional IP
ISA functions:




admission control
routing algorithm
queuing discipline
discard policy
Mobile Computing Lab.
Computer Network
2009/Fall
187
Gihwan Cho
Resource Reservation: RSVP

Resource ReSerVation Protocol


Unicast applications can reserve resources in routers to
meet QoS


RFC 2205
if router can not meet request, application informed
Multicast is more demanding, its load may be reduced



some members of group may not require delivery from particular
source over given time
some group members may only be able to handle a portion of
the transmission
reservation means routers can decide in advance if can meet
requirements
Mobile Computing Lab.
Computer Network
2009/Fall
188
Gihwan Cho
Differentiated Services




Simple, easily implemented, low overhead tool to
support a range of differentiated network services
IP Packets labeled for differing QoS using existing IPv4
Type of Service or IPv6 DS field
Have service level agreement established between
provider and customer prior to use of DS
Built in aggregation


good scaling to larger networks and loads
Implemented by queuing / forwarding based on DS octet

no state information on packet flows stored
Mobile Computing Lab.
Computer Network
2009/Fall
189
Gihwan Cho
Chapter 20 : Transport Protocols



End-to-end data transfer service
Shield upper layers from network details
Reliable, connection oriented


Best effort, connectionless


has greater complexity, eg. TCP
Datagram, eg. UDP
Connection-oriented transport protocol mechanisms



provides establishment, maintenance & termination of a logical
connection
most common service for a wide variety of applications
is reliable, but complex
Mobile Computing Lab.
Computer Network
2009/Fall
190
Gihwan Cho
Reliable Sequencing Network Service

Assume virtually 100% reliable delivery by network
service of arbitrary length messages





eg. reliable packet switched network with X.25
eg. frame relay with LAPF control protocol
eg. IEEE 802.3 with connection oriented LLC service
Transport service is a simple, end to end protocol
between two systems on same network
Issues are: addressing, multiplexing, flow control,
connection establishment and termination
Mobile Computing Lab.
Computer Network
2009/Fall
191
Gihwan Cho
Addressing (I)

Target user specified by:





user identification (host, port)
a socket in TCP
port represents a particular transport service (TS) user
transport entity identification (on host)
specify transport protocol (TCP, UDP)
host address of attached network device
in the Internet, a global internet address
network number
Transport layer passes host to network layer
Mobile Computing Lab.
Computer Network
2009/Fall
192
Gihwan Cho
Addressing (II)
IP address identifies this machine
Protocol “06” is the TCP protocol
06
TCP
203.234.18.72
Network
IP
21
25
FTP
SMTP
Port determines
which application
gets incoming data
17
UDP
7
ECHO
Mobile Computing Lab.
Computer Network
2009/Fall
69
TFTP
193
Gihwan Cho
Finding Addresses

Four methods




know address ahead of time
e.g. collection of network device stats
well known addresses
eg. common servers like FTP, SMTP etc
name server
does directory lookup
sending request to well known address which spawns new
process to handle it
Mobile Computing Lab.
Computer Network
2009/Fall
194
Gihwan Cho
Multiplexing

Of upper layers (downward multiplexing)



so multiple users employ same transport protocol
user identified by port number or service access point
May also multiplex with respect to network services used
(upward multiplexing)

eg. multiplexing a single virtual X.25 circuit to a number of
transport service user
Mobile Computing Lab.
Computer Network
2009/Fall
195
Gihwan Cho
Flow Control

Issues:



Want TS flow control because:




longer transmission delay between transport entities compared
with actual transmission time
due to the delays communication of flow control information
variable transmission delay so difficult to use timeouts
receiving user can not keep up
receiving transport entity can not keep up
Which can result in buffer overflowing
Managing flow difficult because of gap between sender
and receiver
Mobile Computing Lab.
Computer Network
2009/Fall
196
Gihwan Cho
Coping with Flow Control Requirements

Do nothing



Refuse further segments



clumsy
multiplexed connections are controlled on aggregate flow
Use fixed sliding window protocol (see chapter 7)



segments that overflow are discarded
sending transport entity will fail to get ACK and will retransmit
thus further adding to incoming data
works well on reliable network
failure to receive ACK is taken as flow control indication
does not work well on unreliable network
can not distinguish between lost segment and flow control
Use credit scheme
Mobile Computing Lab.
Computer Network
2009/Fall
197
Gihwan Cho
Credit Scheme





Decouples flow control from ACK
Each octet has sequence number
Each transport segment has sequence number (SN),
ack number (AN) and window size (W) in header
Sends sequence number of first octet in segment
ACK includes (AN=i, W=j) which means


all octets through SN=i-1 acknowledged, want i next
permission to send additional window of W=j octets
Mobile Computing Lab.
Computer Network
2009/Fall
198
Gihwan Cho
cf) An Example of Sliding Window
Mobile Computing Lab.
Computer Network
2009/Fall
199
Gihwan Cho
Credit Allocation
Mobile Computing Lab.
Computer Network
2009/Fall
200
Gihwan Cho
Sending and Receiving Perspectives
Mobile Computing Lab.
Computer Network
2009/Fall
201
Gihwan Cho
Connection Establishment and
Termination

Need connection establishment and termination
procedures to allow:




each end to know the other exists
negotiation of optional parameters
triggers allocation of transport entity resources
By mutual agreement
Mobile Computing Lab.
Computer Network
2009/Fall
202
Gihwan Cho
Connection State Diagram
Mobile Computing Lab.
Computer Network
2009/Fall
203
Gihwan Cho
Connection Establishment
Mobile Computing Lab.
Computer Network
2009/Fall
204
Gihwan Cho
Connection Termination



Either or both sides by mutual agreement
Graceful or abrupt termination
If graceful, initiator must:




send FIN to other end, requesting termination
place connection in FIN WAIT state
when FIN received, inform user and close connection
Other end must:


when receives FIN must inform TS user and place connection in
CLOSE WAIT state
when TS user issues CLOSE primitive, send FIN & close
connection
Mobile Computing Lab.
Computer Network
2009/Fall
205
Gihwan Cho
Unreliable Network Service

More difficult case for transport protocol since



Examples include


segments may get lost
segments may arrive out of order
IP internet, frame relay using LAPF, IEEE 802.3 with
unacknowledge connectionless LLC
Issues:

ordered delivery, retransmission strategy, duplication detection,
flow control, connection establishment & termination, crash
recovery
Mobile Computing Lab.
Computer Network
2009/Fall
206
Gihwan Cho
Ordered Delivery




Segments may arrive out of order
Number segments sequentially
TCP numbers each octet sequentially
Segments are numbered by the first octet number in the
segment
Mobile Computing Lab.
Computer Network
2009/Fall
207
Gihwan Cho
Retransmission Strategy

Retransmission of segment needed because




Transmitter does not know of failure
Receiver must acknowledge successful receipt


segment damaged in transit
segment fails to arrive
can use cumulative acknowledgement for efficiency
Sender times out waiting for ACK triggers
re-transmission
Mobile Computing Lab.
Computer Network
2009/Fall
208
Gihwan Cho
Timer Value

Fixed timer






based on understanding of network behavior
can not adapt to changing network conditions
too small leads to unnecessary re-transmissions
too large and response to lost segments is slow
should be a bit longer than round trip time
Adaptive scheme




keeps track of the time taken to ack., and sets its retransmission
timer based on the average of the observed delays
may not ACK immediately – may be cumulative ack.
can not distinguish between ACK of original segment and retransmitted segment
network conditions may change suddenly
Mobile Computing Lab.
Computer Network
2009/Fall
209
Gihwan Cho
Duplication Detection



If ACK lost, segment is re-transmitted
Receiver must recognize duplicates
If duplicate received prior to closing connection




receiver assumes ACK lost and ACKs the duplicate
sender must not get confused with multiple ACKs
sequence number space large enough to not cycle within
maximum life of segment
Duplicate received after closing connection
Mobile Computing Lab.
Computer Network
2009/Fall
210
Gihwan Cho
Incorrect
Duplicate
Detection
Mobile Computing Lab.
Computer Network
2009/Fall
211
Gihwan Cho
Flow Control

Credit allocation quite robust with unreliable net




Have problem if AN=i, W=0 closing window




can ack data & grant credit
or just one or other
lost ACK recovers on next received
then send AN=i, W=j to reopen, but this is lost
sender thinks window closed, receiver thinks it open
Solution is to use persist timer
If timer expires, send something

could be re-transmission of previous segment
Mobile Computing Lab.
Computer Network
2009/Fall
212
Gihwan Cho
Connection Establishment

Two way handshake




A send SYN, B replies with SYN
lost SYN handled by re-transmission
can lead to duplicate SYNs
ignore duplicate SYNs once connected
Lost or delayed data segments can cause connection
problems



segment from old connections
start segment numbers far removed from previous connection
use SYN i, where i is the sequence # of the first data segment
need ACK to include i
so, three way handshake
Mobile Computing Lab.
Computer Network
2009/Fall
213
Gihwan Cho
Two Way Handshake: Obsolete Data
Segment
Mobile Computing Lab.
Computer Network
2009/Fall
214
Gihwan Cho
Two Way Handshake:
Obsolete SYN Segment
Mobile Computing Lab.
Computer Network
2009/Fall
215
Gihwan Cho
Three Way
Handshake:
State
Diagram
Mobile Computing Lab.
Computer Network
2009/Fall
216
Gihwan Cho
Three Way
Handshake:
Examples
Mobile Computing Lab.
Computer Network
So, piggybacking
2009/Fall
217
Gihwan Cho
Connection Termination


Like connection need 3-way handshake
Misordered segments could cause:





entity in CLOSE WAIT state sends last data segment, followed
by FIN
FIN arrives before last data segment
ceceiver accepts FIN, closes connection, loses data
Need to associate sequence number with FIN
Receiver waits for all segments before FIN sequence
number
Mobile Computing Lab.
Computer Network
2009/Fall
218
Gihwan Cho
Connection Termination : Graceful Close


Also have problems with loss of segments and obsolete
segments
Need graceful close which will:



send FIN i and receive AN i
receive FIN j and send AN j
Wait twice maximum expected segment lifetime
Mobile Computing Lab.
Computer Network
2009/Fall
219
Gihwan Cho
Crash Recovery


After restart all state info is lost
May have half open connection


Close connection using persistence timer




as side that did not crash still thinks it is connected
wait for ACK for (time out) * (number of retries)
when expired, close connection and inform user
Send RST i in response to any i segment arriving
User must decide whether to reconnect

problems with lost or duplicate data
Mobile Computing Lab.
Computer Network
2009/Fall
220
Gihwan Cho
TCP





Transmission Control Protocol (RFC 793)
Connection oriented, reliable communication
Over reliable and unreliable (inter)networks
Two ways of labeling data:
Data stream push




user requires transmission of all data up to push flag
receiver will deliver in same manner
avoids waiting for full buffers
Urgent data signal


indicates urgent data is upcoming in stream
user decides how to handle it
Mobile Computing Lab.
Computer Network
2009/Fall
221
Gihwan Cho
TCP Services

A complex set of primitives:




incl. passive & active open, active open with data, send, allocate,
close, abort, status
passive open indicates will accept connections
active open with data sends data with open
And parameters:

incl. source port, destination port & address, timeout, security,
data, data length, PUSH & URGENT flags, send & receive
windows, connection state, amount awaiting ACK
Mobile Computing Lab.
Computer Network
2009/Fall
222
Gihwan Cho
TCP Header
Mobile Computing Lab.
Computer Network
2009/Fall
223
Gihwan Cho
TCP and IP


Not all parameters used by TCP are in its header
TCP passes some parameters down to IP






precedence
normal delay/low delay
normal throughput/high throughput
normal reliability/high reliability
security
Min overhead for each PDU is 40 octets
Mobile Computing Lab.
Computer Network
2009/Fall
224
Gihwan Cho
TCP Mechanisms (I)

Connection establishment




three way handshake : SYN, SYN-ACK, ACK
connection determined by source and dest. sockets (host, port)
can only have a connection between any unique pairs of ports
but one port can connect to multiple different destinations
(different ports)
Mobile Computing Lab.
Computer Network
2009/Fall
225
Gihwan Cho
TCP Mechanisms (II)

Data transfer






data transfer a logical stream of octets
octets numbered modulo 223
flow control uses credit allocation of number of octets
data buffered at transmitter and receiver
sent when transport entity ready
unless PUSH flag used to force send
can flag data as URGENT, sent immediately
if receive data not for current connection, RST flag is set on next
segment to reset connection
Mobile Computing Lab.
Computer Network
2009/Fall
226
Gihwan Cho
TCP Mechanisms (III)

Connection termination


graceful close
TCP user issues CLOSE primitive
transport entity sets FIN flag on last segment sent with last of
data
abrupt termination by ABORT primitive
entity abandons all attempts to send or receive data
RST segment transmitted to other end
Mobile Computing Lab.
Computer Network
2009/Fall
227
Gihwan Cho
TCP Implementation Options (I)


TCP standard precisely specifies protocol
Have some implementation policy options:






send
deliver
accept
retransmit
acknowledge
Implementations may choose alternative options which
may impact performance
Mobile Computing Lab.
Computer Network
2009/Fall
228
Gihwan Cho
Implementation Policy Options (II)

Send




if no push or close, TCP entity transmits at its own convenience
in credit allocation
may construct segment per batch of data from user
quick response but higher overheads
may wait for certain amount of data
slower response but lower overheads
Deliver



in absence of push, can deliver data at own convenience
may deliver from each segment received
higher O/S overheads but more responsive
may buffer data from multiple segments
less O/S overheads but slower
Mobile Computing Lab.
Computer Network
2009/Fall
229
Gihwan Cho
Implementation Policy Options (IV)

Retransmit




TCP has a queue of segments transmitted but not acknowledged
will retransmit if not ACKed in given time
first only - single timer, send one segment only when timer
expires, efficient, has delays
batch - single timer, send all segments when timer expires,
has unnecessary transmissions
individual - timer for each segment, complex
effectiveness depends in part on receiver’s accept policy
Acknowledge


immediate
cumulative
Mobile Computing Lab.
Computer Network
2009/Fall
230
Gihwan Cho
TCP Congestion Control (I)

RFC 1122 & 2581 detail extensions


Two categories of extensions:



Tahoe, Reno & NewReno implementations
retransmission timer management
window management
Retransmission timer management


simple average
ARTT(k+1) = k*ARTT(k)/(k+1) + RTT(k+1)/(k+1) ARTT : Average RTT
exponential average : RFC 793
give greater weight to more recent instances because they are
more likely to reflect future behavior
SRTT(k+1) =  * SRTT(k) + (1- ) * RTT(k+1) SRTT : Smoothed RTT
Mobile Computing Lab.
Computer Network
2009/Fall
231
Gihwan Cho
TCP Congestion Control (II)

RTT variance estimation (Jacobson’s algorithm)



RTT exhibits a relatively high variance
traffic conditions may change abruptly due to other sources
the TCP peer may not ack. each segment immediately
with low variance of RTT, RTO is too high, whilst in an unstable
environment,  =2 may be inadequate with unnecessary retrans.
again, give greater weight to more recent instances because they
are more likely to reflect future behavior
SRTT(k+1) = (1- g ) * SRTT(k) + g * RTT(k+1)
SERR(k+1) = RTT(k+1) - SRTT(k)
SDEV(k+1) = (1- h ) * SDEV(k) + h * |SERR(k+1)|
RTO (k+1) = SRTT(k+1) + f * SDEV(k+1)
typically g = 0.125, h = 0.25, f = 4
Mobile Computing Lab.
Computer Network
2009/Fall
232
Gihwan Cho
Jacobson’s
RTO
Calculation
Mobile Computing Lab.
Computer Network
2009/Fall
233
Gihwan Cho
Exponential RTO Backoff

Timeout probably due to congestion



dropped packet or long round trip time
Hence maintaining RTO is not good idea
Better to increase RTO each time a segment is
re-transmitted



RTO = q*RTO
commonly q=2 (binary exponential backoff)
as in ethernet CSMA/CD
Mobile Computing Lab.
Computer Network
2009/Fall
234
Gihwan Cho
Karn’s Algorithm

If a segment is re-transmitted, the ACK arriving may be:






for the first copy of the segment
RTT longer than expected
for second copy
No way to tell
Do not measure RTT for re-transmitted segments
Calculate backoff when re-transmission occurs
Use backoff RTO until ACK arrives for segment that has
not been re-transmitted
Mobile Computing Lab.
Computer Network
2009/Fall
235
Gihwan Cho
Window Management (I)

Slow start




gradually expanding the window until ACKs are received
awnd = MIN[credit, cwnd]
start connection with cwnd=1
increment cwnd by 1 (actually 2) at each ACK, to some max
Mobile Computing Lab.
Computer Network
2009/Fall
236
Gihwan Cho
Window Management (II)

Dynamic windows sizing on congestion



Jacobson points out that “it is easy to drive a network into
saturation but hard for the net to recover”
with the slow start, cwnd keeps growing exponential until it
becomes equal to receiver window (credit)
however, for the congestion, the exponential growth of cwnd
may be too aggressive and may worsen the congestion
when a timeout occurs
set slow start threshold to half current congestion window
 ssthresh=cwnd/2
set cwnd = 1 and slow start until cwnd=ssthresh
 increasing cwnd by 1 for every ACK
for cwnd >=ssthresh, increase cwnd by 1 for each RTT
Mobile Computing Lab.
Computer Network
2009/Fall
237
Gihwan Cho
Illustration of Slow Start and
Congestion Avoidance
Mobile Computing Lab.
Computer Network
2009/Fall
238
Gihwan Cho
UDP

Connectionless service for application level procedures
specified in RFC 768





unreliable
delivery & duplication control not guaranteed
Reduced overhead
Least common denominator service
Uses:




inward data collection
outward data dissemination
request-response
real time application
Mobile Computing Lab.
Computer Network
2009/Fall
239
Gihwan Cho
Chapter 21 : Network Security

Security requirements




confidentiality
only be accessible for reading by authorized parties
can be achieved with conventional encryption
integrity
protect data accuracy
availability
ensure timely service
authenticity
protect data origin
Mobile Computing Lab.
Computer Network
2009/Fall
240
Gihwan Cho
Passive Attacks


Eavesdropping on transmissions
To obtain information




release of message contents outsider learns content of
transmission
traffic analysis by monitoring frequency and length of messages,
even encrypted, nature of communication may be guessed
Difficult to detect
Can be prevented using encryption
Mobile Computing Lab.
Computer Network
2009/Fall
241
Gihwan Cho
Active Attacks

Masquerade





Replay
Modification of messages
Denial of service
Easy to detect


pretending to be a different entity
detection may lead to deterrent
Hard to prevent

focus on detection and recovery
Mobile Computing Lab.
Computer Network
2009/Fall
242
Gihwan Cho
Symmetric Encryption

Terms





plaintext
encryption algorithm
secret key
ciphertext
decryption algorithm
Mobile Computing Lab.
Computer Network
2009/Fall
243
Gihwan Cho
Requirements for Security

Strong encryption algorithm



Key distribution


even if known, should not be able to decrypt or work out key
even if a number of cipher texts are available together with plain
texts of them
sender and receiver must obtain secret key securely
Once key is known, all communication using this key is
readable
Mobile Computing Lab.
Computer Network
2009/Fall
244
Gihwan Cho
Attacking Encryption

Crypt analysis



Brute force


relay on nature of algorithm plus some knowledge of general
characteristics of plaintext
attempt to deduce plaintext or key
try every possible key until plaintext is achieved
Encryption algorithms

block cipher
most common symmetric algorithms
process plaintext in fixed block sizes producing block of
cipher text of equal size
Data Encryption Standard (DES)
Advanced Encryption Standard (AES)
Mobile Computing Lab.
Computer Network
2009/Fall
245
Gihwan Cho
DES (Data Encryption Standard)

US standard

64 bit plain text blocks, 56 bit key
Mobile Computing Lab.
Computer Network
2009/Fall
246
Gihwan Cho
Strength of DES

Broken in 1998 by Electronic Frontier Foundation






special purpose US$250,000 machine
with detailed published description
less than three days
DES now worthless
alternatives include TDEA
Triple DEA






ANSI X9.17 (1985)
incorporated in DEA standard 1999
uses 2 or 3 keys and 3 executions of DEA algorithm
effective key length 112 or 168 bit
slow
block size (64 bit) now too small
Mobile Computing Lab.
Computer Network
2009/Fall
247
Gihwan Cho
AES (Advanced Encryption Standard)

NIST issued call for proposals in 1997






security strength equal to or better than 3DES
significantly improved efficiency
symmetric block cipher with block length 128 bits
key lengths 128, 192, and 256 bits
AES issued as FIPS 197 in 2001
Description



input a 128-bit block (square matrix of bytes)
128-bit key (square matrix of bytes)
byte ordering by column
Mobile Computing Lab.
Computer Network
2009/Fall
248
Gihwan Cho
AES Encryption
and Decryption
Mobile Computing Lab.
Computer Network
2009/Fall
249
Gihwan Cho
Key Distribution

Symmetric encryption needs key distribution



protected for access by others
changed frequently
Possibilities for key distribution
1.
2.
3.
4.
key selected by A and delivered to B
third party selects key and delivers to A and B
use old key to encrypt & transmit new key from A to B
use old key to transmit new key from third party to A and B
Mobile Computing Lab.
Computer Network
2009/Fall
250
Gihwan Cho
Message Authentication

Protection against active attacks with



It allows receiver to verify that message is authentic




falsification of data
falsification of source
message has not altered
message is from authentic source
message timeline
Authentication using symmetric encryption



assumes sender and receiver are only entities that know key
message must include one of error detection code, sequence
number, time stamp
only sender could have encrypted message for other party
Mobile Computing Lab.
Computer Network
2009/Fall
251
Gihwan Cho
Authentication Without Encryption



Authentication tag generated and appended to each
message
Message not encrypted
useful when don’t want encryption because:



messages broadcast to multiple destinations
have one destination responsible for authentication
one side heavily loaded
encryption adds to workload
can authenticate random messages
programs authenticated without encryption can be executed
without decoding
Mobile Computing Lab.
Computer Network
2009/Fall
252
Gihwan Cho
Message Authentication Code (MAC)



Generate authentication code based on shared key and
message
Common key shared between A and B
If only sender and receiver know key and code matches:



receiver assured message has not altered
receiver assured message is from alleged sender
if message has sequence number, receiver assured of proper
sequence
Mobile Computing Lab.
Computer Network
2009/Fall
253
Gihwan Cho
Message Authentication Using MAC
Mobile Computing Lab.
Computer Network
2009/Fall
254
Gihwan Cho
One Way Hash Function

Accepts variable size message and produces fixed size
tag (message digest)




but without use of a secret key
send digest with message
in manner that validates authenticity
Advantages of authentication without encryption





encryption is slow
encryption hardware expensive
encryption hardware optimized to large data
algorithms covered by patents
algorithms subject to export controls (from USA)
Mobile Computing Lab.
Computer Network
2009/Fall
255
Gihwan Cho
Public Key Encryption

Based on mathematical algorithms


Asymmetric : use two separate keys



infeasible to determine decryp. key given encryp. key and algorithm
public key is used for encryption
private key is used for decryption
steps:




user generates pair of keys
user places one key in public domain
to send a message to user, encrypt using public key
user decrypts using private key
Mobile Computing Lab.
Computer Network
2009/Fall
256
Gihwan Cho
Public Key
Encryption
Mobile Computing Lab.
Computer Network
2009/Fall
257
Gihwan Cho
Digital Signature




Sender encrypts message with private key
Receiver decrypts with senders public key
Authenticates sender
Does not give privacy of data


must send both original and encrypted copies
More efficient to sign authenticator


a secure hash of message
send signed hash with message
Mobile Computing Lab.
Computer Network
2009/Fall
258
Gihwan Cho
RSA Public-key Encryption

Developed in 1977 by Rivest, Shamir and Adleman
Mobile Computing Lab.
Computer Network
2009/Fall
259
Gihwan Cho
RSA Security

Brute force search of all keys



given size of parameters is infeasible
but larger keys do slow calculations
Factor n to recover p & q



a hard problem
well known 129 digit challenge broken in 1994
key size of 1024-bits (300 digits) currently secure for most apps
Mobile Computing Lab.
Computer Network
2009/Fall
260
Gihwan Cho