11Spanning Tree ProtocolEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Slides by Lisa Fowler2Overview• Networks need redundancy– Provide redundant paths between end stations to enable the Bridged LAN to continue to provide the Service in the event of component failure (of bridge or segment)• Loops can cause major problems– Ethernet does not provide any notion like TTL in order to eventually remove looping frames• Reduce bridge topology to a single spanning tree– Trees have no cycles ⇒ loop-free– Automatically reconfigure the spanning tree in a reproducible and predictable manner3Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3LAN ALAN BLAN CLAN DNetwork Diagram4Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCD• Each bridge has a unique Bridge ID = unique device ID + priority number• Within each bridge, each port has a unique ID11112222111122221111222233331111111122222222Spanning Tree ProtocolRequired Elements5• Assign a cost to the segments between any two bridges (can be custom, unlike in lecture, where we used uniform cost)Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCD11112222111122221111222233331111111122222222Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3cBcCcDcDcDcCcCcAcAcASpanning Tree ProtocolRequired Elements6111122221111222211112222333311111111222222221. Elect a root bridgea) Compare Bridge ID (compare priority number then compare unique ID)2. Each bridge selects a root port: the port with the least cost path to the rootBridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3cBcCcDcDcDcCcCcAcAcACostscA- 100cB- 19cC- 4cD- 100Bridge 1Spanning Tree Protocol27111122221111222211112222333311111111222222222. Each bridge selects a root port: the port with the least cost path to the roota) Break ties by picking neighbor w/ lowest IDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3cBcCcDcCcABridge 1CostscA- 100cB- 19cC- 4cD- 100BridgeRootPort12 13 34 25 1Spanning Tree Protocol8111122221111222211112222333311111111222222223. All bridges on the network segment collectively determine least cost path from network segment to roota) The port that connects the network segment to the bridge that provides this path is called the designated portBridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3cBcCcDcACostscA- 100cB- 19cC- 4cD- 100Bridge 1BridgeRootPortDesgn.Port12 13 34 25 1BridgeRootPortDesgn.Port1 1,22 1 23 34 25 1Spanning Tree Protocol9BridgeRootPortDesgn.Port1 1,22 1 23 34 25 1BridgeRootPortDesgn.Port1 1,22 1 23 3 24 25 111112222111122221111222233331111111122222222a) The port that connects the network segment to the bridge that provides this path is called the designated porti. Break ties by picking bridge w/ lowest IDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCDBridge 1Bridge 5Bridge 2Bridge 4Bridge 3cBcCcDcACostscA- 100cB- 19cC- 4cD- 100Bridge 1Spanning Tree Protocol10Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCD4. If there’s still a tie for any of the above, pick the lowest port #11112222111122221111222233331111111122222222BridgeRootPortDesgn.Port1 1,22 1 23 34 25 1BridgeRootPortDesgn.Port1 1,22 1 23 3 24 25 1CostscA- 100cB- 19cC- 4cD- 100Spanning Tree Protocol11Bridge 1Bridge 5Bridge 2Bridge 4Bridge 3ABCD5. Now any time frames require broadcasting, a bridge only accepts them from a designated or a root port …6. … and only floods to other root or designated ports11112222111122221111222233331111111122222222BridgeRootPortDesgn.Port1 1,22 1 23 34 25 1BridgeRootPortDesgn.Port1 1,22 1 23 3 24 25 1CostscA- 100cB- 19cC- 4cD- 100Spanning Tree
View Full Document
Unlocking...