Transcript ppt - Suraj @ LUMS

Transparent Bridging
Network Protocols and Standards
Autumn 2004-2005
Sept 09, 2004
CS573: Network Protocols and Standards
1
Reasons for Bridges

On a single LAN, there are limitations:




Number of stations
Size of segment
Bandwidth per segment
Bridges connect LAN segments to make
“extended” LANs

LANs, LAN Segments, Extended LANs
Sept 09, 2004
CS573: Network Protocols and Standards
2
Example: Bridging Benefits
Consider a LAN segment with average traffic R pkts/s
Divide it into two segments and connect with a Bridge
Average traffic on each segment is R/2 pkts/s
R/2 pkts/s
Stations
Sept 09, 2004
Bridge
R/2 pkts/s
Stations
CS573: Network Protocols and Standards
3
Example: Bridging Benefits

On average:





Each segment generates a traffic of R/2 pkts/s
Half of the traffic is for “local” stations
Half of the traffic is for “other” segment
Traffic on each segment is R/2+(1/2) R/2
Average traffic on each segment is 3R/4

This traffic must not exceed the capacity of the
segment
Sept 09, 2004
CS573: Network Protocols and Standards
4
Example: Bridging Benefits

Therefore 3R/4 < C


R < 4C/3



Effective R exceeds the capacity i.e. Rmax < 4C/3
rate on any segment must not exceed the capacity
What was the maximum rate allowed when the LAN
was not segmented?


C is the capacity of the physical link
(Rmax < C)
Does the maximum effective R (i.e., Rmax) increase
when three segments are used?

Depends how the segments are connected!
Sept 09, 2004
CS573: Network Protocols and Standards
5
Can we use a router instead?


The answer is “It depends”
Inter-segment traffic may be handled by routers if all
stations understand layer 3


Does this mean that with newer stations, we did not
need bridges?


Older machines did not understand layer 3, but new ones do
Not really! Bridges handle all layer 3 protocols while early
routers usually handled a single layer 3 protocol
Don’t multiprotocol routers do address this issue?
And what about convergence to IP? Does that not
eliminate the need for multiprotocol routers

An IP router can replace a bridge then, right?
Sept 09, 2004
CS573: Network Protocols and Standards
6
Do we still need a Bridge?

What if stations want to move on the
“extended” LAN without reconfiguring
their IP addresses?



Bridges can help!
Bridges have high performance
Bridges are simple
Sept 09, 2004
CS573: Network Protocols and Standards
7
Transparent Bridging
…
stations
Bridge
For stations, the two topologies are the same  transparent bridging
Sept 09, 2004
CS573: Network Protocols and Standards
8
Transparent Bridge Functions

Promiscuous Listening


Store and Forward


Every packet passed up to software
Based on a forwarding database
Filtering

Also based on forwarding database
Sept 09, 2004
CS573: Network Protocols and Standards
9
Can a Bridge act smart?


For the two segment-one bridge topology for
which the maximum rate was 4/3 of the link
capacity, was Bridge doing something smart?
Yes, the Bridge forwarded the traffic smartly




Manual entry of station addresses?
Stations use addresses from a range?
Station addresses are assigned such that a portion
indicates the LAN number?
Bridges can also “learn” on their own!!!
Sept 09, 2004
CS573: Network Protocols and Standards
10
Forwarding Database (FDB):
Creation and Maintenance



The bridge promiscuously listens to every
packet/frame received on each port
For each received frame, address in the
source field is stored together with the port
on which the frame is received. The FDB is
created in Station Cache.
Each entry in the FDB is deleted if no traffic is
received from that source address for a given
period of time (Aging time)
Sept 09, 2004
CS573: Network Protocols and Standards
11
Forwarding Frames

For each received frame, the bridge looks at
the destination address:


If the address is multicast or broadcast (all 1’s)
then the frame is forwarded to all the interfaces
(ports) except for the one on which it is received
For unicast addresses:


Sept 09, 2004
If the address is not found in FDB, the frame is
forwarded to all the ports except for the one on which it
is received
If the address is found in FDB, the frame is forwarded to
the port in FDB entry. If the FDB entry has same port on
which the frame is received, frame is dropped (filtered)
CS573: Network Protocols and Standards
12
Example 1: Learning and Forwarding

Transmission order

AD


Port 2
Port 1
QA


Port 3
B
Ports 2, 3
DA


Port 1
Filtered
ZC

A
Q
D
Ports 1, 3
Z
Sept 09, 2004
M
CS573: Network Protocols and Standards
C
13
Example 2: Two Bridges
Port 1
A
Q
B1
Port 2
Port 1
D
B2
Port 2
M
K
T
What are the Station Caches after “complete” learning?
Sept 09, 2004
CS573: Network Protocols and Standards
14
Topologies with Loops

Problems



Frames proliferate
Learning process unstable
Multicast traffic loops forever
A
LAN 1
B1
B2
B3
LAN 2
Sept 09, 2004
CS573: Network Protocols and Standards
15
Topologies with Loops

Solutions


Require that the topologies be loop-free through
careful deployment of segments and bridges
Design Bridges to detect loops and complain and,
perhaps, stop working


Not a good idea because loops provide redundancy
Design into the bridges an algorithm that prunes
the topology into a loop-free subset (a spanning
tree)


Sept 09, 2004
Blocking of some ports may be required
Automatically adapt to the changes in topology
CS573: Network Protocols and Standards
16
Reconfiguration Algorithm






Configures an arbitrary topology into a spanning
tree
Automatic reconfiguration in case of topology
changes
The algorithm should converge for any size LAN;
the stability should be achieved within a short,
bounded time
Active topology should be reproducible and
manageable
Transparency to end-stations is required
Must not use a lot of bandwidth
Sept 09, 2004
CS573: Network Protocols and Standards
17
Spanning Tree Algorithm

A distributed Algorithm



Elects a single bridge to be the root bridge
Calculates the distance of the shortest path from
each bridge to the root bridge (cost)
For each LAN segment , elects a “designated”
bridge from among the bridges residing on that
segment


The designated bridge for a LAN segment is the one
closest to the root bridge
And…
Sept 09, 2004
CS573: Network Protocols and Standards
18
Spanning Tree Algorithm

For each bridge


Selects ports to be included in spanning tree
The ports selected are:




The root port --- the port that gives the best path from
this bridge to the root
The designated ports --- ports connected to a segment
on which this bridge is designated
Ports included in the spanning tree are placed in
the forwarding state
All other ports are placed in the blocked state
Sept 09, 2004
CS573: Network Protocols and Standards
19
Forwarding frames along the spanning tree
Forward and Blocked States of Ports


Data traffic (from various stations) is
forwarded to and from the ports
selected in the spanning tree
Incoming data traffic is always
discarded (this is different from filtering
frames. Why?) and is never forwarded
on the blocked ports
Sept 09, 2004
CS573: Network Protocols and Standards
20
Root Selection: Bridge ID

Each port on the Bridge has a unique LAN
address just like any other LAN interface card.
Bridge ID is a single bridge-wide identifier
that could be:


A unique 48-bit address
Perhaps the LAN address of one of its ports
B

Port Address
Root Bridge is the one with lowest Bridge ID
Sept 09, 2004
CS573: Network Protocols and Standards
21