Transcript Network
CMPE 150 – Winter 2009
Lecture 10
February 10, 2009
P.E. Mantey
CMPE 150 -- Introduction to
Computer Networks
Instructor: Patrick Mantey
[email protected]
http://www.soe.ucsc.edu/~mantey/
Office: Engr. 2 Room 595J
Office hours: Tues 3-5 PM, Mon 5-6 PM*
TA: Anselm Kia [email protected]
Web site: http://www.soe.ucsc.edu/classes/cmpe150/Winter09/
Text: Tannenbaum: Computer Networks
(4th edition – available in bookstore, etc. )
Syllabus
Reading Assignment
Thursday, February 12
Chapter 5, sections 5.3, 5.4.1-5.4.3, 5.5
Today’s Agenda
Link Layer
Bridge Routing
Network Layer
Functions / IP
Routing
Text: Chapter 5, sections 5.1, 5.2.1-5.2.8
(pp. 343-370)
Internet Layering
Level 4
-- Application Layer
(rlogin, ftp, SMTP, POP3, IMAP, HTTP..)
-- Transport Layer(a.k.a Host-to-Host)
Level 3
Level 2
(TCP, UDP, ARP, ICMP, etc.)
-- Network Layer (a.k.a. Internet) (IP)
-- (Data) Link Layer / MAC sub-layer
Level 1
(a.k.a. Network Interface or
Network Access Layer)
-- Physical Layer
Level 5
Bridging (802.x)
Fixed Route Bridging
Source Route Bridging
Transparent Bridging
“Plug ‘n Play”:
Flooding algorithm
Backward Learning
Spanning Tree (avoids loops)
Ref: http://en.wikipedia.org/wiki/Bridging_%28networking%29
Spanning Tree Approach- Uses:
IEEE 802.1
Frame Forwarding
Each bridge maintains Forwarding Table
List of stations on the “side” of each port
Forwards to port and on to LAN
corresponding to Table
Unless blocked
Floods those whose MAC address not in
Table
Address Learning
Spanning Tree Algorithm
Address Learning
When frame arrives on a port, table
records source address as being on that
port. (Backward learning)
Timer set for each entry
Timer expires, entry is deleted
Timer reset if new frame gives same info.
Spanning Tree Algorithm
Algorithm to avoid Loops
(not needed if topology is a “tree”)
Root of tree is lowest serial number (all
bridges broadcast their serial number)
Tree constructed from root to every
bridge with shortest path
Algorithm runs “continually” to detect
topology changes (801.1D)
http://www.cisco.com/warp/public/473/lan-switch-transparent.swf
Network Layer Topics
Network Layer (Layer 3)
Services for the Transport Layer
Uses the Link Layer
Datagrams (Packets)
Internet Protocol (IP)
Addressing (IP Address)
Communication challenges
Information
Audio
Video
Text
Data
Images
Signals
Analog
Digital
Channels
Analog
Digital
Networks
Circuit
Datagram
Analog - continuously varying value
Digital - sequence of symbols from a finite set
Network challenge - transmission of
information across interconnected channels
Circuit - think telephone call
Datagram - think telegram
First networks
Which came first, analog or digital?
Digital(!)
Signal fires - 1200 BC
Optical telegraph - 1791
Electronic telegraph - 1836
First analog telecommunication was
telephone - 1875
Telephone network
Originally all analog
Internal links replaced with digital in 1962
Internal links shared with FDM
Allowed sharing with more efficient TDM
Circuit-switched
Simple, hierarchical (static) topology and routing
First done by human operators…
…then automatic relays
Provide guaranteed Quality-of-Service (QoS)
Dedicate resources to each connection
Packet-switched networks
Defining characteristics
Virtual-circuit
Data and addressing in packets
Statistical multiplexing
Dynamic topology and routing
X.25 (1974), Frame Relay (1984), ATM (1988)
Datagram
ARPAnet (1966), Internet (1977)
Virtual-circuit networks
Generalization of telephone model
“Smart net” architecture
Compute route on-demand at flow setup
Per-flow state in routers
Assumes need of resource reservation
for some flows
Datagram networks
Three inventors
Defining characteristics
Kleinrock (1961) - efficiency
Baran (1962) - survivability
Davies (1964) - commercial service
Controversy over who invented
Pre-compute routes to all destinations
No per-flow state
Assumes best-effort will be good enough
ARPAnet
First datagram network
Modified “smart net” architecture
1966 - project proposed
September, 1969 - first “IMP” installed
Built on reliable link technology
Hop-by-hop reliability, congestion and flow control
Some end-to-end flow control (“RFNM”)
Much redundant functionality
E.g. reliability and flow control
Led to the “end-to-end argument”
End-to-end argument
If a function can completely and correctly be
implemented only with the knowledge and help of
the application end-points of a communication
system, then the function should not be implemented
in the communication system itself (although
sometimes it may be useful to implement an
incomplete version of the function in the
communication system as a performance
enhancement). J. Saltzer, D. Reed and D. Clark: “End-to-end
arguments in system design”, ACM Trans. Comp. Sys., 2(4):277-88,
Nov. 1984
The Internet
Goal - encourage development of new
network technologies
Make minimal assumptions about links
Attach many computers
Transport datagrams
Quickly send datagrams to different destinations
Best-effort delivery (drop or out of order)
“Smart host” architecture
End-to-end argument
Network layer summary
Communication across interconnected
channels
Two styles: circuit vs packet-switched
Packet-switching characteristics
Data and addressing in packets
Statistical multiplexing
Dynamic topology and routing
Datagram - pre-compute routes, no flow state
VC - on-demand routing, per flow state
Datagram vs VC
Setup
Addressing
State
Routing
Router failure
QoS
Cong Control
Datagram
VC
No
Yes
Full source and
destination address
Virtual Circuit ID
All destination
Per flow and all
destination (why?)
Pre-compute
On-demand
Loss of buffered packets
Loss of buffered packets
and VC state
“Difficult”
Easy
“Difficult”
Easy
Network Layer Design Issues
Store-and-Forward Packet Switching
Providing Services to the Transport Layer
Implementation of Connectionless
Service
Implementation of Connection-Oriented
Service
Comparison of Virtual-Circuit and
Datagram Subnets
Routers (or Level 3 Switches)
Determing route
Run routing algorithms to build table
Routing tables determine packet path
= output line
Forwarding packets
Routing Algorithms
Attributes of Good algorithms for routing
Correct
Fair
Simple
Robust
Stable
Optimal
Routing “Flavors”
Non-Adaptive
“static”
Adaptive
“dynamic”
Static Algorithms
(Non-Adaptive)
Shortest-path routing.
2. Flooding.
1.
Non-adaptive Routing
Fixed routing, static routing.
Do not take current state of the network
(e.g., load, topology) into decision
Routes are computed in advance, off-line,
and downloaded to routers when booted.
Flooding Algorithm (Static)
Every incoming packet forwarded on
every outgoing link except the one it
arrived on.
Problem: duplicates.
Constraining the flood:
Hop count.
Keep track of packets that have been flooded.
Robust, shortest delay (picks shortest
path as one of the paths).
Flooding
Stallings Figure 12.4
(hop-count=3)
Adaptive Routing
Routes change dynamically as function
of current state of network.
Algorithms vary on how they get
routing information, metrics used, and
when they change routes.
Adaptive Routing
Dynamic Routing Algorithms
Distance vector routing.
Bellman – Ford (or Ford-Fulkerson)
Link state routing.
Adaptive routing
Needed in both datagram and VC networks
Based on Shortest-Path algorithms
When run in different architectures?
Find minimum cost of paths between src and dst
Dijkstra - search paths by increasing cost
Bellman-Ford - search paths by increasing hop
count
Dijkstra used for Link-State
Bellman-Ford basis of Distance-Vector
Optimality Principle
General statement about optimal
routes (topology, routing algorithm
independent).
If router J is on optimal path
between I and K, then the optimal
path from J to K also falls along the
same route.
Proof by contradiction.
Optimality Principle
Corollary:
Set of optimal routes from all sources to
destination form a tree rooted at destination.
Sink tree.
Shortest Path Routing 1
Dijkstra (1959).
Network represented by graph G(V, E), where V
is set of nodes and E is set of links connecting
nodes.
What is “shortest”?
Different metrics.
Example: number of hops (static), geographic distance
(static), delay, bandwidth (raw versus available),
combination of a subset of these.
Dijkstra’s Shortest Path
Nodes labeled with distance to source
through best known path.
At start, no known paths so all nodes
labeled with infinity.
As algorithm progresses, nodes are
labeled; “tentative” labels may change,
while “permanent” labels don’t change.
Label made permanent when it’s known to
be in the shortest path to source.
Dijkstra algorithm
Network represented by graph: G(V,E)
V contains vertices i,j,…
E contains edges (i,j), …
Algorithm data structures
“s” - source vertex
“dij” - cost of the edge (i,j); dij = ∞ if (i,j) E
“Di” - cost of the shortest path from s to i
“P” - set of routes with final (“permanent”) labels
Dijkstra algorithm
P = {s}
Ds = 0
Dj = dsj for all {j V | j s}
Do
Di = Min {Dj for all j P}
P = P {i}
For each {j | (i,j) E, j P}
Dj = Min {Dj, Di+dij}
Until (|P| = |V|)
Dijkstra illustrated
B(2,A)
2
A
6
7
2
2
1 E
G(6,A) 4
B (2,A)
3
B(2,A)
C
3
F 2
2
D
2
H
C (9,B)
2
3
3
(4,B) 2
2
(6,E) D
A
E
F 2
6 1
2
G (5,E) 4
H
7
B (2,A) 7
C (9,B)
2
3
3
(4,B) 2
2
A
(6,E)
D
E
F 2
6 1
2
H(8,F)
G(5,E) 4
A
6
2
1
7
(4,B) 2
E
G (6,A)
B (2,A)
4
3
C (9,B)
3
D
F2
2
H
C (9,B)
3 3
2
(4,B)
2
2 (6,E)
A
D
F2
1 E
6
2
G(5,E) 4
H(9,G)
7
B (2,A) 7
C (9,B)
3
2
3
(4,B) 2
2
A
(6,E) D(10,H)
F 2
1 E
6
2
H(8,F)
G(5,E) 4
Distance-Vector protocol
Initialize routing table with local links
Flood routing table to all routers
Do
Compute local routing table from graph
Wait for update or link cost change or timer
Update network graph
If link cost change
Flood updated link to all routers
Else if timer expired
Flood routing table to all routers
Forever
Distance Vector Routing
(a) A subnet. (b) Input from A, I, H, K, and the new
routing table for J.