Transcript Example

Introduction to Communication
Networks
Lecture 5-6
LAN continuation +
Network Layer
1
Introduction to Communication Networks 2/2006
Extending Local Area Networks

Motivation
–
–




2
Distance limitation
Performance degradation as number of users
increases
Hub
Repeater
Bridge
Switch
Introduction to Communication Networks 2/2006
Hub



Hardware device
Creates one LAN segment
Each Ethernet frame received on one port will
be forwarded to all other ports
–

3
Logically operates on signals and propagates each
incoming signal to all connections
Creates one collision domain
Introduction to Communication Networks 2/2006
Repeaters
Ethernet segment
Ethernet segment
R




4
Direct connection
Hardware device
Repeater
Connects two LAN segments
Copies signal from one segment to the other
– Amplifies signals from one segment and sends to the other
– Propagates noise and collisions
Operates in two directions simultaneously
Introduction to Communication Networks 2/2006
Bridges



Hardware, Link Level device
Connects two LAN segments
Forwards frames
–
–
–





5
stores and forwards Ethernet frames
examines frame header and selectively forwards frame based
on MAC destination address
when frame is to be forwarded on segment, uses CSMA/CD to
access segment
Does not forward noise or collisions
Learns addresses and filters
Allows independent transmission
transparent
– hosts are unaware of presence of bridges
plug-and-play, self-learning
– bridges do not need to be configured
Introduction to Communication Networks 2/2006
Bridges: traffic isolation

Bridge installation breaks LAN into LAN segments

Bridges filter packets:
– same-LAN-segment frames not usually forwarded
onto other LAN segments
– segments become separate collision domains
collision
domain
bridge
LAN segment
6
Introduction to Communication Networks 2/2006
collision
domain
LAN segment
= hub
= host
Bridge Learning Algorithm





7
Listen in promiscuous mode (all frames are
copied & analyzed)
Watch source address in incoming frames
Make list of computers on each segment
Only forward if necessary
Always forward broadcast/multicast
Introduction to Communication Networks 2/2006
Bridge Learning cont.



8
A bridge has a bridge table
entry in bridge table:
– (Node LAN Address, Bridge Interface, Time Stamp)
– stale entries in table dropped (TTL can be 60 min)
bridges learn which hosts can be reached through
which interfaces
– when frame received, bridge “learns” location of
sender: incoming LAN segment
– records sender/location pair in bridge table
Introduction to Communication Networks 2/2006
Filtering/Forwarding
When bridge receives a frame:
index bridge table using MAC dest address
if entry found for destination
then{
if dest on segment from which frame arrived
then drop the frame
else forward the frame on interface indicated
}
else floodforward on all but the interface on which
the frame arrived
9
Introduction to Communication Networks 2/2006
Bridge example
Suppose C sends frame to D and D replies back with frame to C.
Bridge receives frame from C
–
–
notes in bridge table that C is on interface 1
because D is not in table, bridge sends frame into interfaces 2 and
3
frame received by D
10
Introduction to Communication Networks 2/2006
Bridge example

D generates frame for C, sends

bridge receives frame
–
–
11
notes in bridge table that D is on interface 2
bridge knows C is on interface 1, so selectively forwards frame
to interface 1
Introduction to Communication Networks 2/2006
Distributed Spanning Tree Algorithm
12
Introduction to Communication Networks 2/2006
Spanning Tree Algorithm

The network of bridges is a graph.
–
Usually built in hierarchical way




The Spanning Tree Protocol finds a a subgraph that
spans all the vertices without loops.
–
–

Spanning => all LAN segments are included.
Tree => the topology has no loops.
The distributed protocol runs:
–
–
13
If bridges at top hierarchy fails -> LAN can become
disconnected
Therefore LANs are usually connected in more than one point
(redundancy)
Can cause same information to be copied many times over the
LAN  can even crash the network.
To determine which bridge is the root of the tree, and
Each bridge turns off ports that are not part of the tree.
Introduction to Communication Networks 2/2006
Example Spanning Tree
B8
B3
B5
Protocol operation:
B7
B2
3.
B1
B6
14
1.
2.
B4
Introduction to Communication Networks 2/2006
Picks a root
For each LAN,
picks a designated bridge
that is closest to the root
All bridges on a LAN
send packets towards the
root via the designated
bridge.
Example Spanning Tree
B8
Spanning Tree:
B3
B5
B1
B7
B2
B2
B4
B5
B1
Root
B6
15
B8
B4
Introduction to Communication Networks 2/2006
B7
Switch



High performance multiple interface bridge!
Physically similar to a hub
Logically similar to a bridge
–
–
–
–

16
Operates on packets
Understands addresses
Only forwards when necessary
More fancy forwarding methods
Permits separate pairs of computers to
communicate at the same time (full duplex)
Introduction to Communication Networks 2/2006
Typical Configuration
17
Introduction to Communication Networks 2/2006
Network Layer
Protocol Stack
App
Transport
Network
IP + Routing
Link
18
Introduction to Communication Networks 2/2006
Data
Hdr
IP Datagram
Network Layer

Role of the Network Layer
–

Move packets from sending host to receiving host.
Main Functions:
–
Host-to-Host delivery:



Internetworking
Addressing
Routing
Path determination  Routing Algorithms
– Forwarding  select the correct outgoing port
–
–
Call Setup:

–
–
19
Some network layer architectures (ATM, RSVP) requires that
routers along a chosen path will agree on the path.
Packetizing
Fragmenting
Introduction to Communication Networks 2/2006
The Routing Problem
“B”
“A”
R2
R1
How does R1
choose a route
to host B?
20
Introduction to Communication Networks 2/2006
R4
R3
Switching
21
Introduction to Communication Networks 2/2006
Circuit Switching
A
Source


2.
3.

22
Destination
It’s the method used by the telephone network.
A call has three phases:
1.

B
Establish circuit from end-to-end (“dialing”),
Communicate,
Close circuit (“tear down”).
Originally, a circuit was an end-to-end physical
wire.
Nowadays, a circuit is like a virtual private wire:
each call has its own private, guaranteed data
rate from end-to-end.
Introduction to Communication Networks 2/2006
Circuit Switching
Telephone Network
Each phone call is allocated
64kb/s. So, a 2.5Gb/s trunk line
can carry about 39,000 calls.
Destination
“Callee”
Source
“Caller”
Central
Office
“C.O.”
Central
Office
“C.O.”
Trunk
Exchange
23
Introduction to Communication Networks 2/2006
Packet Switching


24
Virtual circuit approach – relationship
between all packets belonging to a
message is preserved – a single route is
chosen, and all packets take that route
Datagram approach – each packet is
treated independently of all others – thus,
packets in the same message can take
different routes, and possibly arrive out of
order
Introduction to Communication Networks 2/2006
Datagram approach





25
It’s the method used by the Internet.
Each packet is individually routed packet-by-packet, using
the router’s local routing table.
The routers maintain no per-flow state.
Different packets may take different paths.
Several packets may arrive for the same output link at the
same time, therefore a packet switch has buffers.
Introduction to Communication Networks 2/2006
Store-and-Forward


Basic paradigm used in packet switched
network
Packet
–
–
–

Router
–
–
–
26
Sent from source computer
Travels router/switch-to-router/switch
Delivered to destination
‘‘Stores’’ packet in memory
Examines packet’s destination address
‘‘Forwards’’ packet toward destination
Introduction to Communication Networks 2/2006
Routing Table Configuration

Manual
–
–
–

Automatic routing
–
–
–
27
Table created by hand
Useful in small networks
Useful if routes never change
Software creates/ updates table
Needed in large networks
Changes routes when failures occur
Introduction to Communication Networks 2/2006
Routing & Graph Theory

Graph
–
–
28
Node models switch
Edge models connection
Introduction to Communication Networks 2/2006
Reliable Flooding
An algorithm ensuring all nodes get a copy of an update packet
R1
Un update packet:
Node
id
sequence
number
update
data
Algorithm:
A source node sends out the packet on all ports
 Each node receiving the packet checks the sequence no. and if more

recent, stores it and sends it out on all ports but the ingress port
 Each node receiving the packet acks the directly node which sent it

29
A sending node, not receiving an ack within a T/O, retransmits
Introduction to Communication Networks 2/2006
Reliable Flooding
Advantages:
 Reliable transmission.
 Works also when network topology is unknown.
 If the network is connected, every node gets a copy
of the packet
Disadvantages:
 Some nodes receive multiple copies of the packet
 Packets can go round in loops forever.
 Waste of network resources
 To prevent looping for ever, a TTL is added to packet
Node
id
sequence
number
TTL
update
data
 Useful only for important updates – not for regular routing
30
Introduction to Communication Networks 2/2006
Routing Approaches

Source Routing
–
–

Virtual Circuit
–
–

Path is setup in advance
Used in practice in ATM/MPLS/RSVP
Destination Routing
–
–
31
complete path in packet
Used in practice in ad hoc networks
Forwarding according to destination address
Used in practice in IP networks
Introduction to Communication Networks 2/2006
Routing Algorithm classification
Global or decentralized
information?
Global:
 all routers have complete
topology, link cost info
 “link state” algorithms
Decentralized:
 router knows physicallyconnected neighbors, link
costs to neighbors
 iterative process of
computation, exchange of
info with neighbors
 “distance vector” algorithms
32
Static or dynamic?
Static:
 routes change slowly over
time
Dynamic:
 routes change more quickly
– periodic update
– in response to link cost
changes
Introduction to Communication Networks 2/2006
Shortest Path Algorithms

Algorithms from graph theory
–
–


May be distributed (No central authority)
A Router
–
–
33
Dijkstra
Bellman-Ford
Must learn route to each destination
Only communicates with directly attached
neighbors
Introduction to Communication Networks 2/2006
Shortest Path


Label on edge represents ‘‘distance’’
Possible distance metric
–
–
–
34
Geographic distance
Economic cost
Inverse of capacity
Introduction to Communication Networks 2/2006
Algorithms For Computing
Shortest Paths

Distance Vector (DV)
–

Link-state
–
–

35
Routers exchange information in their routing
tables  Local
Routers exchange link status information  Global
Algorithm has complete information about the
network.
Both used in practice
Introduction to Communication Networks 2/2006
Distance Vector



Periodic, two-way exchange between
neighbors
Iterative, asynchronous and distributed
During exchange, switch sends
–
–

Receiver
–
–
36
List of pairs
Each pair gives (destination, distance)
Compares each item in list to local routes
Changes routes if better path exists
Introduction to Communication Networks 2/2006
Distance Vector Intuition

Let
–
–
–
–

If no local route to V or local route has cost greater than
C,
–
–
37
N be neighbor that sent the routing message
V be destination in a pair
D be distance in a pair
C = D + WN (WN the cost to reach the sender)
install a route with next hop N and cost C
else ignore pair
Introduction to Communication Networks 2/2006
Example Of Distance Vector
Routing





38
Consider transmission of one DV message
Node 2 sends to 3, 5, and 6
Node 6 installs cost 8 route to 2
Later 3 sends update to 6
6 changes route to make 3 the next hop for destination 2
Introduction to Communication Networks 2/2006
Bellman-Ford Algorithm
Objective: Finds the minimum cost path from every node to
every other node
Example: Determine the route from (R1, …, R7) to R8
that minimizes the cost.
Examples of link cost:
Distance, data rate, price,
congestion/delay, …
1
R1
R2
R3
4
4
R4
2
2
39
1
R6
3
R5
Introduction to Communication Networks 2/2006
2
R7
3
2
R8
B-F is a Distance Vector Algorithm
1
R1
R2
R4
2
2
R3

1
4
R5
2
4
R6
3
R7
2
3
R8
The solution is a spanning tree with R8 as the root
of the tree (link costs are cost in the direction to R8).
 The Bellman-Ford Algorithm finds all spanning trees.
40
Introduction to Communication Networks 2/2006
The Distributed Bellman-Ford
Algorithm
1. Let X n  (C1 , C2 , ..., C7 ) where : Ci  cost from Ri to R8 .
2. Set X 0  (, , ,..., ).
3. Every T seconds, router i sends Ci to
its neighbors.
4. If router j is told of a lower cost path
to R8, it updates Cj. Hence, X n 1  f ( X n )
where f (.) determines the next step improvemen t.
5. If X n 1  X n then goto step (3).
6. Stop.
41
Introduction to Communication Networks 2/2006
Bellman-Ford Algorithm - Example
R1


1
2
R3
R1
Inf
R2
Inf
R3
4, R8
R4
Inf
R5
2, R8
R6
42
R7
2, R8
3, R8
1
R2
2

R1
3


R7
2
R6
2
3
R8

1

4
R4
R5
4



1
R2
R4
2
2
4
R3
Introduction to Communication Networks 2/2006
4
R5
2
2
4
3
R7
3
R6
2
3
R8
2
Bellman-Ford Algorithm - Example
43
R1
6, R3
R2
4, R5
R3
4, R8
R4
6, R7
R5
2, R8
R6
2, R8
R7
3, R8
R1Z
5, R2
R2
4, R5
R3
4, R8
R4
5, R2
R5
2, R8
R6
2, R8
R7
3, R8
6
4
1
R1
R2
2
2
4
R1
R4
2
3
2
4
R6
3
R7
2
R5
4
R3
5
1
6
2
3
R8
Solution
4
1
1
R2
2
4
R3
4
Introduction to Communication Networks 2/2006
5
2
R4
3
2
R5
R6
2
R7 3
2
R8
Bellman-Ford Algorithm
Questions:
1.
2.
3.
44
How long can the algorithm take to run?
How do we know that the algorithm always
converges?
What happens when link costs change, or
when routers/links fail?
Introduction to Communication Networks 2/2006
Link-State Routing


Overcomes instabilities in DV
Pair of routers periodically
–
–

Router
–
–
–
45
Test link between them
Broadcast link status message
Receives status messages
Computes new routes
Uses Dijkstra’s algorithm
Introduction to Communication Networks 2/2006
Dijkstra’s Shortest Path First (SPF) Alg
Objective: Finds the minimum cost path from every node to
every other node
 Executed by every node based on the following complete
network topology and link costs
N - the set of nodes
l(k,n) - the cost of the link from k to n
C(n) - the cost of the path from say, R8 , to node n; or , if not connected
M - the set of nodes incorporat ed so far by the alg
 When completed at node, say R8, C(n) will contain the
minimum cost path from R8 to node n
46
Introduction to Communication Networks 2/2006
Dijkstra’s Shortest Path First (SPF) Alg


Each router calculates lowest cost path to all its neighbors,
starting from itself;
At each step of the algorithm, a router
o
adds a node to M to which it can reach with its current minimum
cost
o
For every node outside M, updates the minimum path cost to it
1. Let M  {R8 }
2. For each n  N  {R8 }
C(n)  l(R8 ,n)
3. While M  N
M  M  {k}, where C(k) attains the min over over all k  N  M
C(n)  min {C(n), C(k)  l(k,n)}
47
Introduction to Communication Networks 2/2006
Getting Network Topology for SPF

Done by the Reliable Flooding algorithm that sends the
following Link State Packet (LSP):
Node
id

48
sequence
number
TTL
attached links
and their costs
LSP are sent out whenever the state of an attached link
changes (up/down), or when an Interval Timer expires
Introduction to Communication Networks 2/2006
Dijkstra’s Shortest Path First AlgorithmExample
1
R1
R2
R3
4
4
R4
2
2
49
1
R6
3
R5
Introduction to Communication Networks 2/2006
2
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 1. Shortest path set : M  {R8 }
Candidate set (finite cost) : C  {R3 , R5 , R7 , R6 }
Step 2 : M  {R8 , R5 },
C  {R3 , R7 , R6 , R2 }.
1
R1
1
R2
R4
2
2
R3
4
4
3
R5
2
R7
C ( R5 ) is the minimum
50
R6
Introduction to Communication Networks 2/2006
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 3 : S  {R8 , R5 , R6 },
C  {R3 , R7 , R2 , R4 }.
1
R1
1
R2
R3
4
4
R4
2
2
51
C ( R6 ) is the minimum
R6
3
R5
Introduction to Communication Networks 2/2006
2
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 4 : S  {R8 , R5 , R6 , R7 },
C  {R3 , R2 , R4 }.
1
R1
1
R2
R3
4
4
R4
2
2
52
C ( R7 ) is the minimum
R6
3
R5
Introduction to Communication Networks 2/2006
2
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 5 : S  {R8 , R5 , R6 , R7 , R3 },
C  {R2 , R4 , R1}.
1
R1
1
R2
R4
2
2
R3
4
4
3
R5
2
C ( R3 ) is the minimum
53
R6
Introduction to Communication Networks 2/2006
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 6 : S  {R8 , R5 , R6 , R7 , R3 , R2 },
C  {R4 , R1}.
1
R1
1
R2
R4
2
2
R3
4
4
3
R5
2
C ( R2 ) is the minimum
54
R6
Introduction to Communication Networks 2/2006
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 7 : S  {R8 , R5 , R6 , R7 , R3 , R2 , R4 },
C  {R1}.
1
R1
1
R2
R4
2
2
R3
4
4
3
R5
2
C ( R4 ) is the minimum
55
R6
Introduction to Communication Networks 2/2006
R7
3
2
R8
Dijkstra’s Shortest Path First AlgorithmExample
Step 7 : S  {R8 , R5 , R6 , R7 , R3 , R2 , R4 , R1}
1
R1
1
R2
R4
2
2
R3
4
4
3
R5
2
C ( R1 ) is the minimum
56
R6
Introduction to Communication Networks 2/2006
R7
3
2
R8
Comparison of LS and DV algorithms
Message complexity


LS: with n nodes, E links,
O(nE) msgs sent
DV: exchange between
neighbors only
– larger msgs
– convergence time varies
Speed of Convergence


57
Robustness: what happens
if router malfunctions?
LS:
–
–
node can advertise
incorrect link cost
each node computes only
its own table
DV:
LS: requires O(nE) msgs
– may have oscillations
DV: convergence time varies
– may be routing loops
– count-to-infinity problem
Introduction to Communication Networks 2/2006
–
–
DV node can advertise
incorrect path cost
each node’s table used by
others

error propagate thru
network
Network Services Paradigms

Connection Oriented
–
–
Paradigm: phone calls
3 phase protocol:



–

Example: ATM (Asynchronous Transfer Mode)
Connectionless
–
–
–
58
connection establishment
data transmission
clearing
Paradigm: snap mail
1 Phase protocol
Example: IP (Internet Protocol)
Introduction to Communication Networks 2/2006
Connection-Oriented Networks
(CON)

Sender
–
–
–
–

Network
–
–
–
–
59
Requests ‘‘connection’’ to receiver
Waits for network to form connection
Leaves connection in place while sending data
Terminates connection when no longer needed
Receives connection request
Forms path to specified destination and informs sender
Transfers data across connection
Removes connection when sender requests
Introduction to Communication Networks 2/2006
Connectionless Networks (CLN)

Sender
–
–
–

Forms packet to be sent
Places address of intended recipient in packet
Transfers packet to network for delivery
Network
–
–
–
Uses destination address to forward packet
Each packet handled independently
One phase protocol


60
No setup required before transmitting data
No cleanup required after sending data
Introduction to Communication Networks 2/2006
Network layer service models:
Network
Architecture
Internet

Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
no
constant yes
rate
guaranteedyes
avg. rate
guaranteedno
minimum
none
no
no
no
yes
yes
yes
yes
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
yes
no
no
Internet model being extended: Intserv, Diffserv
–
61
Service
Model
More in the QoS lecture
Introduction to Communication Networks 2/2006
CLN vs CON

CON - Connection Oriented Networks
–
–
–
–

CLN - Connectionless
–
–
–
62
More intelligence in network
Can reserve bandwidth
Connection setup overhead
Well-suited to real-time applications
Less overhead
Permits asynchronous use
Allows broadcast/ multicast
Introduction to Communication Networks 2/2006
Routing in the Internet
The Internet uses hierarchical routing

The Internet is split into Autonomous Systems (AS’s)
 Examples of AS’s: Stanford (32), HP (71), MCI Worldcom
(17373)

Try (unix): whois –h whois.arin.net ASN “MCI
Worldcom”


63
Within an AS, the administrator chooses an Interior
Gateway Protocol (IGP)
 Examples of IGPs: RIP (rfc 1058), OSPF (rfc 1247).
Between AS’s, the Internet uses an Exterior Gateway
Protocol
 AS’s today use the Border Gateway Protocol, BGP-4
(rfc 1771)
Introduction to Communication Networks 2/2006
Interior Routing Protocols


64
RIP (Routing Information Protocol)

Uses distributed Bellman-Ford algorithm (DV).

Updates (in a RIP packet) are sent every 30 seconds.

No authentication in RIP ver. 1; password in ver. 2

Originally in BSD UNIX.
OSPF (Open Shortest Path First)

Link-state updates (LSU) sent (using reliable flooding) as and
when required.

Every router runs Dijkstra’s algorithm.

Authenticated updates.

Autonomous system may be partitioned into “areas”.

Allows multiple paths with the same cost to a destination
Introduction to Communication Networks 2/2006
Interior Routing Protocols

Authentication of LSU packets
To prevent, e.g., forged advertisement of zero cost
 Early OSPF uses 8-byte password
 Strong cryptography in newer versions


“Areas” as a further hierarchy layer
An AS can be partitioned into “areas”
 Adds scalability to the OSPF alg
 A router knows only how to reach the “areas” – not
to all networks

65
Introduction to Communication Networks 2/2006