Bridges

• Purpose of Bridges
  • Separate LANs and keep traffic local
  • Join LANs and support communication and resource sharing
• Two Approaches
  • Transparent (Spanning Tree) Bridges
  • Source Routing Bridges
  • Pros and cons
    • Transparent bridges: Simple for the host
    • Source routing: Fast bridges, because they are simple
    • Transparent bridges: May use bad route when a good one is available
    • Source routing: Always finds the best route
    • Source routing: floods the network with probes
• Distinctions between bridges and routers
  • Bridges are faster
  • Bridges cannot fragment and reassemble packets
  • Bridges cannot do full routing. They do no look at the Network Layer address.
  • Bridges are "protocol independent" -- they do not care what protocols are in use at the Network Layer and above. Routers are dependent on the network layer information, which usually implies something about the higher layer protocols as well.
• Similarities and Differences in LAN standards and their impact
  • The IEEE 802 LAN standards share a common address space
  • Nearly everything else is different
  • A device that moves packets from network to another must translate from one protocol to another if they are different. That impacts the speed and may imply the need to buffer packets.
  • Bridges could connect IEEE 802.x to IEEE 802.y in theory. In practice, that requires another kind of device

• Basic Philosophy: Put all the complexity needed in the bridges. Make life as easy as possible for the hosts that are on the networks.
• Method:
  • Bridge listens on the network interface
  • If the destination is unknown, the bridge forwards the packet to the other network interface and writes it out.
  • If the destination is known, the bridge forwards only if the destination is not on the same network as the sender.
• A little more to it than that.
  • A bridged network topology cannot include any loops (Why not?)
  • Bridges exchange messages with each other to make sure there is a path from every network to every other network, but there are no loops - a Spanning Tree
  • Bridges continue to exchange messages to react to changes in the networks, including bridge failures.
  • Redundant bridges can be used for backup purposes, but cannot share the load on a busy network.
• An Example Spanning Tree Bridge

• Basic Philosophy: Keep the bridges simple; put the complexity in the hosts' interface
• Method: The source host includes a path for the packet to follow in the packet header. The packet goes to a bridge that is on the LAN. The bridge looks at the header. If it finds its own address in the beginning of the path, it forwards the packet on the LAN indicated. Otherwise, it ignores the packet.
• How the host knows how to form a path:
  • The host uses its known path to the destination if it has one that is not old.
  • Otherwise, the host sends a probe message.
  • The probe will be forwarded by every bridge that sees it, on every LAN to which the bridge is attached (except the one the probe came in on).
  • If the bridge sees its own id already in the path the probe is accumulating, it will drop the probe without forwarding (preventing a loop).
  • The probe will eventually get to the destination by every possible path, including the shortest.
  • The destination will return the probe to the sender, using the best discovered route as its source routing path.
  • The source will then send its "real" message using the newly discovered route.

  Spanning Tree Algorithm

  • Spanning Tree Algorithm
  • Implementation

  ---

  Spanning Tree Algorithm For a graph, G=(V,E), a spanning tree is a subgraph, T=(v,E) where T is a tree and v are selected from V. The spanning tree connects all the vertices of the graph.

  The Dijkstra/Prim algorithm finds a minimum spanning tree by starting at an arbitrary vertex and branching out, picking up new vertices as it goes. Think of the vertices as partitioned into three sets:

  • Tree vertices: in the tree constructed so far
  • Fringe vertices: not in the tree but adjacent to a vertex that is in the tree
  • Unseen vertices: all others

  The Dijkstra/Prim algorithm constructs a minimum weight spanning tree. In the algorithm used in Spanning Tree bridges, there is no concept of weight. The task is somewhat simpler.

  Here is the algorithm:

  Select an arbitrary vertex to start the tree (the bridge with the
       lowest serial number)
  
  While there are fringe vertices do
     select an edge between a tree vertex and a fringe vertex and add
            the selected edge and vertex to the tree
  end
  

  We assume a connected graph. There cannot be a spanning tree if the graph is not connected. Assuming a connected graph, the algorithm above will find a spanning tree.

  ---

  Spanning Tree Implementation

  In the implementation of the spanning tree, all the bridges participate. The bridges send messages and receive replies to determine which bridge is the root. Once the root is identified, each bridge sends a message to the root from each port. The root replies to each of these messages. Each bridge determines which of its ports is "closest" to the root.