1. No category

Rbridges: Transparent Routing
Radia Perlman
[email protected]
Goals
• Glue a bunch of links together to appear to
be a single LAN to IP nodes
• No configuration of internal switches
• Compatible with existing bridges
• Compatible with existing IP nodes (v4 and
v6, endnodes and routers)
What’s wrong with bridges?
• They solve the problems on the previous
slide
• But:
– Routes not optimal
– Temporary loops a disaster
– Choice of meltdowns or conservative failover
Basic idea of transparent bridge
• Listen promiscuously
• Learn location of source address based on
source address in packet and port from
which packet received
• Forward based on learned location of
destination
• When in doubt, forward
Station learning
Q
V
V
A
A
X,F
X
X,A,V
C
F
F
G
But loops are a disaster
• No hop count
• Exponential proliferation
B1
B2
B3
Thus the Spanning Tree
Algorithm
I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree which must be sure to span
So packets can reach every LAN.
First the Root must be selected
By ID it is elected.
Least cost paths from Root are traced
In the tree these paths are placed.
A mesh is made by folks like me.
Then bridges find a spanning tree.
Path from a to c
a
2,1,6
2,3,3
11
2,3,3
3
6
c
7
2,2,7
9
2,2,4
2,0,2
2
10
5
2,0,2
4
14
2,2,4
2,1,5
2,1,14
Problems with Bridges
• Routes are not optimal (spanning tree)
– STA cuts off redundant paths
– If A and B are on opposite side of path, they
have to take long detour path
• Temporary loops really dangerous
– no hop count in header
– proliferation of copies during loops
– So, should be conservative in transition
Compare this to routing
•
•
•
•
•
Routers have temporary loops, too
Part of the life of distributed algorithms
But IP has a hop count (TTL)
An IP router only forwards in one direction
And the router specifies the next recipient
Why bridges are slow to start
forwarding
• Temporary loops might cause meltdown
• Can’t (except in certain special cases, like a
port to an endnode) know if turning on a
link might cause temporary loop
• Simple solution: wait before turning on link,
so other bridges can turn off links first
• People want instant failover (but they don’t
want meltdowns)
Bridge meltdowns
• They do occur (a Boston hospital)
• Lack of receipt of spanning tree msgs tells
bridge to turn on link
• So if too much traffic causes spanning tree
messages to get lost…
– loops
– exponential proliferation of looping packets
Why are there still bridges?
• Why not just use routers?
– Bridges plug-and-play
– Endnode addresses can be per-campus
• IP routes to links, not endnodes
– So IP addresses are per-link
– Need to configure routers
– Need to change IP address if change links
Using bridges with IP
• Bridging is used to create a campus in
which all nodes share the same prefix
• Looks to IP like a single link
• But bridging isn’t as good as routing
–
–
–
–
Suboptimal routes
Traffic concentration (onto spanning tree links)
Meltdowns
Slow failover
What we’d like: best of both
worlds
• Keep transparency to endnodes and zero
configuration
• Optimal paths
• Make temporary loops safe
– Fast failover
– No meltdowns
Rbridges
• Compatible with today’s bridges and routers
• Like routers, terminate bridged LAN
• Like bridges, glue LANs together to create
one IP subnet (or for other protocols, a
broadcast domain)
• Like routers, optimal paths, fast
convergence, no meltdowns
• Like bridges, plug-and-play
Basic Rbridge idea
• Link state protocol among Rbridges (so know how
to route to other Rbridges)
• “Somehow” learn location of endnodes (e.g., from
data traffic, or ARP replies)
• Report attached endnodes in link state info
• Need to encapsulate pkts
– To distinguish originating traffic from transit
– To specify next recipient
– To include a hop count
Rbridging
R7
R9
R1
R8
c
R5
R4
R3
R6
a
R2
Encapsulation Header
S=Xmitting Rbridge
D=Rcving Rbridge
pt=“transit”
hop count
original pkt (including L2 hdr)
• Outer L2 hdr must not confuse bridges
• So it’s just like it would be if the Rbridges were routers
• Need special layer 2 destination address
• for unknown or multicast layer 2 destinations
• can be L2 multicast, or any L2 address provided it
never gets used as a source address
Need spanning tree for flooding
• Need it for distributed ARP request
• Or for unknown layer 2 destinations (e.g.,
endnode knows the layer 2 address of the
exit router)
• Don’t need to use the bridge spanning tree
• Instead, compute it from the link state
database
Rbridges and Bridges
R4
R2
R7
Seems like:
R2
Actually can be:
bridged LAN
R4
R7
Example: IP nodes A and B
B
RB2
RB1
A
Example: A and B, Rbridges don’t
know B
• A issues ARP request for B
• RB1 doesn’t know, so issues distributed
ARP request (flooded through spanning
tree)
• Each Designated RBridge issues ARP
request on its LAN
• RB2 receives a reply (B,b)
• RB2 reports (B,b) in its link state info
Example: A and B, RBridges DO
know B
•
•
•
•
•
A issues ARP request for “B”
RB1 responds with an ARP reply (B=b)
A transmits to “b”
RB1 encapsulates
RBridges forward towards “b”, replacing
outer header on each hop, and decrementing
outer hdr TTL
• RB2 decapsulates
Example: A and off-campus B
R
RB2
RB1
A
B
A and off-campus B
• A will send to a router’s layer 2 address, say
R’s layer 2 address = x
• RBridges have to send to that IP router
• If x is in the forwarding table, then RB1
encapsulates and forwards to x
• Else (x unknown), RB1 encapsulates and
sends on spanning tree
• Each Designated RBridge decapsulates
Learning a layer 2 address
• Can learn from data packets
• Or if don’t want to for IP, listen to routing
messages in order to learn layer 2 addresses
of IP routers
Another optimization for IP
• Can have short endnode cache timer
• Designated RBridge pings to make sure
local IP nodes still there
Conclusions
• Looks to routers like a bridge
– invisible, plug-and-play
• Looks to bridges like routers
– terminates spanning tree, broadcast domain
Conclusions, cont’d
• Much better replacement for bridging
–
–
–
–
optimal paths
still plug and play and transparent
fast convergence
no meltdowns
• For IP
– allows plug-and-play single-prefix campus