Floodless in SEATTLE: A Scalable Ethernet Architecture for Large EnterprisesGoals of Today’s LectureQuick Review of EthernetEthernetEthernet Frame StructureEthernet Bridging: Routing at L2Ethernet Bridges Self-learn Host Info.Self Learning: Building the TableSelf Learning: Handling MissesFlooding Can Lead to LoopsSolution: Spanning TreesInteraction with the Upper Layer (IP)Broadcast Domain and IP SubnetNew Challenges to Ethernet, and SEATTLE as a solution“All-Ethernet” Enterprise Network?But, Ethernet Bridging Does Not ScaleState of the Practice: A Hybrid ArchitectureMotivationOverviewOverview: ObjectivesAvoiding FloodingRestraining BroadcastingKeeping Forwarding Tables SmallEnsuring Optimal Forwarding PathsBackwards CompatibilityOverview: ArchitectureSEATTLE in a SlideHow does it work?TerminologyResponding to Topology ChangesSingle Hop Look-upResponding to Host MobilityUnicast-based Bootstrapping: ARPUnicast-based Bootstrapping: DHCPOverview: EvaluationControl-Plane Scalability When Using RelaysData-Plane Efficiency w/o CompromiseLarge-scale Packet-level SimulationTuning the SystemStretch: Path OptimalityControl Overhead: Noisiness of ProtocolAmount of State: Conciseness of ProtocolPrototype ImplementationEmulation Using the PrototypeTable SizeControl OverheadOverview: Applications and BenefitsIdeal Application: Data Center NetworkDC Mechanisms to Ensure HA and Low CostConclusionsMore LessonsSlide 52Backup SlidesSolution: Sub-dividing Broadcast DomainsExample: Two Virtual LANsNeither VLAN is SatisfactoryMore Unique BenefitsFloodless in SEATTLE:A Scalable Ethernet Architecturefor Large EnterprisesChang Kim, and Jennifer Rexfordhttp://www.cs.princeton.edu/~chkimPrinceton University2Goals of Today’s LectureReviewing Ethernet bridging (Lec. 10, 11)Flat addressing, and plug-and-play networkingFlooding, broadcasting, and spanning treeVLANsNew challenges to EthernetControl-plane scalabilityAvoiding flooding, and reducing routing-protocol overheadData-plane efficiencyEnabling shortest-path forwarding and load-balancingSEATTLE as a solutionAmalgamation of various networking technologies covered so farE.g., link-state routing, name resolution, encapsulation, DHT, etc.Quick Review of Ethernet4EthernetDominant wired LAN technology Covers the first IP-hop in most enterprises/campusesFirst widely used LAN technologySimpler, cheaper than token LANs, ATM, and IPKept up with speed race: 10 Mbps – 10 Gbps Metcalfe’s Ethernetsketch5Ethernet Frame StructureAddresses: source and destination MAC addressesFlat, globally unique, and permanent 48-bit valueAdaptor passes frame to network-level protocolIf destination address matches the adaptorOr the destination address is the broadcast addressOtherwise, adapter discards frameType: indicates the higher layer protocol Usually IP6Ethernet Bridging: Routing at L2Routing determines paths to destinations through which traffic is forwardedRouting takes place at any layer (including L2) where devices are reachable across multiple hopsIP routing (Lec. 13 ~ 15)Overlay routing (Lec. 17)P2P, or CDN routing (Lec. 18)Ethernet bridging (Lec. 10, 11)IP LayerApp LayerLink Layer7Ethernet Bridges Self-learn Host Info.Bridges (switches) forward frames selectivelyForward frames only on segments that need themSwitch tableMaps destination MAC address to outgoing interfaceGoal: construct the switch table automaticallyswitchABCD8Self Learning: Building the TableWhen a frame arrivesInspect the source MAC addressAssociate the address with the incoming interfaceStore the mapping in the switch tableUse a time-to-live field to eventually forget the mappingABCDSwitch learns how to reach A.9Self Learning: Handling MissesFloods when frame arrives with unfamiliar dstor broadcast addressForward the frame out all of the interfaces… except for the one where the frame arrivedHopefully, this case won’t happen very oftenABCDWhen in doubt, shout!10Flooding Can Lead to LoopsFlooding can lead to forwarding loops, confuse bridges, and even collapse the entire networkE.g., if the network contains a cycle of switchesEither accidentally, or by design for higher reliability11Solution: Spanning TreesEnsure the topology has no loopsAvoid using some of the links when flooding… to avoid forming a loopSpanning treeSub-graph that covers all vertices but contains no cyclesLinks not in the spanning tree do not forward frames12Interaction with the Upper Layer (IP)Bootstrapping end hosts by automating host configuration (e.g., IP address assignment)DHCP (Dynamic Host Configuration Protocol)Broadcast DHCP discovery and request messagesBootstrapping each conversation by enabling resolution from IP to MAC addrARP (Address Resolution Protocol)Broadcast ARP requestsBoth protocols work via Ethernet-layer broadcasting (i.e., shouting!)13Broadcast Domain and IP SubnetEthernet broadcast domainA group of hosts and switches to which the same broadcast or flooded frame is deliveredNote: broadcast domain != collision domainBroadcast domain == IP subnetUses ARP to reach other hosts in the same subnetUses default gateway to reach hosts in different subnetsToo large a broadcast domain leads toExcessive flooding and broadcasting overheadInsufficient security/performance isolationNew Challenges to Ethernet, and SEATTLE as a solution15“All-Ethernet ” Enterprise Network?“All-Ethernet” makes network mgmt easierFlat addressing and self-learning enablesplug-and-play networkingPermanent and location independent addresses also simplifyHost mobilityAccess-control policiesNetwork troubleshooting16But, Ethernet Bridging Does Not ScaleFlooding-based deliveryFrames to unknown destinations are floodedBroadcasting for basic serviceBootstrapping relies on broadcastingVulnerable to resource exhaustion attacksInefficient forwarding pathsLoops are fatal due to broadcast storms; uses the STPForwarding along a single tree leads toinefficiency and lower utilization17State of the Practice: A Hybrid ArchitectureEnterprise networks comprised of Ethernet-based IP subnets interconnected by routersRRRREthernet Bridging - Flat addressing - Self-learning - Flooding - Forwarding along a treeIP Routing (e.g., OSPF) - Hierarchical addressing - Subnet configuration - Host configuration - Forwarding
View Full Document