topology CUCL 20040408

50 %
50 %
Information about topology CUCL 20040408

Published on December 1, 2007

Author: Wen12


Topology Discovery without Network Assistance:  Topology Discovery without Network Assistance Austin Donnelly Joint work with Richard Black Motivation:  Motivation Networking problems some of the hardest to resolve Top 5 home user support issues: Can’t access files on remote PC Don’t know how to set up workgroup network Networking with older PCs (NETBEUI) is difficult Hard for support engineer to gather info from PC Firewall in the way Knowing the topology can help: give context to network errors performance optimisation admission control schemes Admission Control:  Admission Control H Media server bottleneck? Knowing the topology allows accurate determination of which resources in the home network are shared, and thus potential bottlenecks. Network Optimisation:  Network Optimisation Advice on improving network shape: Moving the switch reduces the number of packets flooded to all hosts. Context for Errors:  Context for Errors Current situation: H Study PC Kid’s PC But we’d like to see Knowing topology allows error messages to be more meaningful Our Approach:  Our Approach AP Is this Research?:  Is this Research? IBM’s Tivoli NetView, HP’s OpenView are SNMP-based mappers Network Element Behaviour:  Network Element Behaviour Ethernet is made of segments and switches Segments: Every packet goes everywhere Single collision domain Made of hubs and wires Switches Unicast packets only go towards the destination Switches learn from source addresses Unknown destinations get broadcast Must be arranged in a tree Wireless Bridges (eg Linksys WET11, Xbox wireless adapter): proxy ARP, L2 NAT rewrite frame src to own MAC, when sending on wireless side eg: A: AB B gets copy but so does C Distributed System:  Distributed System Mapper host discovers Responders on network Mapper broadcasts MapBegin packets, hosts reply with Hellos Mapper acks hosts in next MapBegin Hosts are now associated to Mapper, and accept RPCs: Emit(srchw, dsthw) Query() -> packets seen since last Query Mapper’s Topology Discovery algorithm decides where and when to Emit() packets into the network Security:  Security Problem: attacker could use the Responders to forge packets Yes, but attacker can do that anyway; a bad guy on your Ethernet is pretty bad! Our aim: allow no worse damage than directly connected attacker ie no amplification attacks, no man-in-the-middle forgery Security checks by Responder on Emit(srchw, dsthw): must be sent directly to Responder, not broadcast srchw must be Responder’s own MAC, or in special range dsthw must be unicast We’re not attempting Byzantine fault-tolerant mapping Demo:  Demo Discovery Algorithm Overview:  Discovery Algorithm Overview Algorithm proceeds in phases: Mapper discovers hosts & WET11s Mapper discovers segments Hosts enable promiscuous mode Hosts emit a packet to chosen collector Mapper Queries() hosts to find which other hosts they “see” Mapper discovers “shallow” switches Mapper forms “islands” of shallow switches and hubs Mapper finds “gaps” connecting islands Mapper probes gaps to discover deep switches and hubs Mapper places APs and legacy hosts Will discuss each in turn Limitations:  Limitations Can’t detect equipment with no effect on packet flow in network daisy-chained hubs, segment with only two hosts, deep switch with only two connections, or deep hub-stars Apply Occam’s Razor to infer simplest network which matches observed packet flow 802.1x port-based access control stops forging of source address usually enterprise switches, so support SNMP 2 / 7: Discover Segments:  2 / 7: Discover Segments M A B C D E F G 3 / 7: Shallow Switches:  3 / 7: Shallow Switches Shallow switch: has at least one host connected to it Which hosts share a switch? All segment leaders train their local switch with address X A : L  bcast A : X  L C gathers { A, B } or B gathers { A } Do this from root of Segment Tree downwards A B C X X X 4 / 7: Islands:  4 / 7: Islands A shallow hub between two switches causes problems But also has benefits: allow us to know which switches are next to each other transitive closure of shallow hubs and these switches we call an “island” M A B C D E F G Topology within an island is completely determined 5 / 7: Gaps Connecting Islands (1):  Where do the islands interconnect with each other? For each cross-island link in Segment Tree, where in parent island does child island connect? If parent segment has no switches below it in island: create a new switch (it must exist otherwise island would be larger) If parent has switches below it: which one does child island use? send probe from child island to each candidate switch: if packet not seen on parent segment, then child island connects through candidate switch. Where in child island does parent island connect? if child has parent switch, that’s the one, otherwise child is segment: there must be another switch above it 5 / 7: Gaps Connecting Islands (1) 5 / 7: Gaps Connecting Islands (2):  5 / 7: Gaps Connecting Islands (2) M A B C D E F G Where does this island connect? not seen at A: connects via B Where does this island connect? seen at A: no connect via B; must connect via A but A is a segment; must be another switch actually, this switch must exist too 6 / 7: Probe Gaps:  6 / 7: Probe Gaps Recap: we now know: shallow segments and switches, the islands they form island edges, and gaps between them Need to discover structure of the gaps (in last example, gaps had only 2 islands bordering them, so they were trivial wires) Eg, a “more complex” network: Introduce a Path Crossing test A B C 6 / 7: Probe Gaps (Path Crossing 1):  6 / 7: Probe Gaps (Path Crossing 1) Pick 4 switch leaders: A, B, P, Q want to answer: does path A → B cross path P → Q ? we write this test AB/PQ A B P Q 6 / 7: Probe Gaps (Path Crossing 2):  Possible outcomes: (Ø) only A sees probe: (H) both see probe: • (X) only P sees probe: Special case: P == Q, ie P steals address X locally 6 / 7: Probe Gaps (Path Crossing 2) A B P Q disjoint paths A B P Q 6 / 7: Probe Gaps:  6 / 7: Probe Gaps Split large gaps into smaller ones Pick each switch leader around edge of gap, use Path Crossing test with leader as P to see if it splits the gap Test AB/PP: if we get (X) or (H) then gap splits at P: Test each possible P, and assign As, Bs to any sub-gaps formed Continue until gaps can’t get any smaller Hopefully now have gaps with 2 members (ie wires) otherwise… P A B 6 / 7: Equivalence Classes:  6 / 7: Equivalence Classes Pick P, Q so the path P → Q goes through gap of interest Evaluate AB/PQ for all gap members, and group them into equivalence classes (ECs) Order the ECs along the path P → Q by sorting using AP/BQ ECs must have switches attaching them to P → Q, and now know their order Recurse: chose a Q inside each EC and use this to repeatedly subdivide the EC. Since at least one switch leader (Q) has been removed, guaranteed to make progress 7 / 7: APs & Legacy Hosts:  7 / 7: APs & Legacy Hosts Problem with both these: can’t issue training packets Soln: use non-legacy to train switch, then provoke AP or Legacy host to send a probe now can locate them to nearest switch with a Responder host For APs can use host behind the AP For Legacy host can use 3rd-party ARP trick Sample Topology:  Sample Topology Questions?:  Questions?

Add a comment

Related presentations