生物信息學課件英文原版課件 (70)

1、Mark W. Garrett14 February 2001J. Baron, D. ShallcrossC. Huitema, J. DesMarais, B. Siegell, P. Seymour, F. ChungAn SAIC CompanyFelix Project Inferential Topology Discovery:From Delay Data to Network Graph Darpa ITOIntrusion Detection ProgramEvaluate network status independently fromthe usual network

2、 management protocolsand data.E.g., no use of routing protocols, ping,traceroute, ICMP, SNMP, etcMeasure network by sending sparse probe packets among a set of monitors. Collect delay and loss data.From these data discover the network topology and evaluate the performance of all links in the network

3、.Small new field of research developing called “Inferential Topology Discovery (Kurose, Towsley, Paxson, McCanne, Caceras, Duffield, et al.)This talk presents a particular method based on modeling correlation across the observations.The Felix ProjectGoalsNetwork MonitoringFelix Data Analysis Approac

4、hDEFABCInternetSimulator898896670 145718 F A : Fri Jun 26 17:31:10 1998 Fri Jun 26 17:31:10 1998 1 0 0 0 0898896693 159087 D E : Fri Jun 26 17:31:33 1998 Fri Jun 26 17:31:33 1998 22 0 0 0 0898896707 184151 C D : Fri Jun 26 17:31:47 1998 Fri Jun 26 17:31:47 1998 6 0 0 0 0898896718 173311 B F : Fri Ju

5、n 26 17:31:58 1998 Fri Jun 26 17:31:58 1998 6 0 0 0 0898896762 195353 D E : Fri Jun 26 17:32:42 1998 Fri Jun 26 17:32:42 1998 22 0 0 0 0898896907 243507 F A : Fri Jun 26 17:35:07 1998 Fri Jun 26 17:35:07 1998 1 0 0 0 0898896923 252194 A C : Fri Jun 26 17:35:23 1998 Fri Jun 26 17:35:23 1998 8 0 0 0 0

6、898897096 315751 D C : Fri Jun 26 17:38:16 1998 Fri Jun 26 17:38:16 1998 9 0 0 0 0898897099 321974 E B : Fri Jun 26 17:38:19 1998 Fri Jun 26 17:38:19 1998 2 0 0 0 0898897101 326261 F C : Fri Jun 26 17:38:21 1998 Fri Jun 26 17:38:21 1998 3 0 0 0 0898897265 376966 E F : Fri Jun 26 17:41:05 1998 Fri Ju

7、n 26 17:41:05 1998 7 0 0 0 0898897280 371363 B C : Fri Jun 26 17:41:20 1998 Fri Jun 26 17:41:20 1998 6 0 0 0 0898897285 371371 B F : Fri Jun 26 17:41:25 1998 Fri Jun 26 17:41:25 1998 6 0 0 0 0898897333 401269 C E : Fri Jun 26 17:42:13 1998 Fri Jun 26 17:42:13 1998 14 0 0 0 0898897351 385009 A F : Fr

8、i Jun 26 17:42:31 1998 Fri Jun 26 17:42:31 1998 8 0 0 0 0898897355 389369 D B : Fri Jun 26 17:42:35 1998 Fri Jun 26 17:42:35 1998 5 0 0 0 0898897458 428081 C B : Fri Jun 26 17:44:18 1998 Fri Jun 26 17:44:18 1998 9 0 0 0 0898897511 470461 B D : Fri Jun 26 17:45:11 1998 Fri Jun 26 17:45:11 1998 2 0 0

9、0 0898897631 472162 E B : Fri Jun 26 17:47:11 1998 Fri Jun 26 17:47:11 1998 0 0 0 0 0898897782 558276 D F : Fri Jun 26 17:49:42 1998 Fri Jun 26 17:49:42 1998 9 0 0 0 0898897897 608592 C D : Fri Jun 26 17:51:37 1998 Fri Jun 26 17:51:37 1998 4 0 0 0 0898897925 605581 A F : Fri Jun 26 17:52:05 1998 Fri

10、 Jun 26 17:52:05 1998 8 0 0 0 0898897926 616708 E F : Fri Jun 26 17:52:06 1998 Fri Jun 26 17:52:06 1998 3 0 0 0 0898897938 614421 C B : Fri Jun 26 17:52:18 1998 Fri Jun 26 17:52:18 1998 13 0 0 0 0898898220 693504 C D : Fri Jun 26 17:57:00 1998 Fri Jun 26 17:57:00 1998 5 0 0 0 0raw dataABACADAEAFBCBD

11、BEBFCDCECFDEDFEFAB111111111111000AC111111111111000AD111110111111111AE111110111111111AF111110111111011BC110001111111000BD111111111111111BE111111111111111BF111111111111011CD111111111111111CE111111111111111CF111111111111011DE001100010110111DF001110111111111EF001110111111111measurement systeme1e2e3e4e5e

12、6e7e8e9AB111000000AC110100000AD100010101AE100010110AF100011000BC001100000BD011010101BE011010110BF011011000CD010110101CE010110110CF010111000DE000000011DF000001101EF000001110common component matrixpath component matrixIdentify linksCreate graphCBAFDEgraph specification(nodes and links)TopologyDiscover

13、yAEDCBFe1e2e4e3e5e8e6e7e9AEDCBFe1e2e4e3e5e8e6e7e9(NAP)(NAP)(backbonesite)Add geographicinformationnetwork graphnetwork mapGraphRenderingNetwork elementand link performanceintermediate resultsPerformanceAssessmentDelayLossLoadThroughputPr congNetwork DiscoveryTerminology for Network Topology and Moni

14、toringM1M2M3M4M5M6M7M8M9M10M11M15M14M13M12(Interior) NodeMonitorPathCloudFor m monitors, there are np = m(m-1) pathsThe number of links is between m (star) and m2 (full mesh)Links are unidirectional So a line in the graph usually represents two linksNetwork Discovery Reduced Graph ConceptM1M2M3M4M5L

15、inks Not Traversed by Monitor Packets“Series Equivalent Edges”Define Reduced Graph as the sub-graph within the network that is discoverable.Excludes links not traversed by monitor packetsCombines equivalent edges, i.e. edges traversed by exactly the same set of paths.Non-series equivalent edges can

16、occur when reducing a real graph, but they are very rare.3150 nodesWAN-MAN-LAN design100 monitors187 nodes698 (unidirectional) linksNetwork Discovery Example of Complete Network and Reduced GraphReduced graph tends to include more of backbone and less of edgesNetwork Discovery Reduced Graph Non-seri

17、es Equivalent EdgesHere is an (artificially) symmetrical graph with equivalent edges.We have seen non-series equivalent edges only once in reducing randomly generated graphs (out of 100+ examples)“Non-Series Equivalent Edges”ABNetwork Discovery Reduced Graph Related to PathsReduced graph determined

18、by n = 2 monitors is a successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2, 3 monitors is a successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 4 monitors is a

19、successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 5 monitors is a successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 6 monitors is a successive approximation

20、 to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 7 monitors is a successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 8 monitors is a successive approximation to the network.Network

21、Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 9 monitors is a successive approximation to the network.Network Discovery Reduced Graph Related to PathsReduced graph determined by n = 2 10 monitors is a successive approximation to the network. EtcThe delay along a path = su

22、m of delays for each linkDP = X dLX identifies topology (in terms of links on paths), and is always rank deficient.To illustrate, consider adding a constant delay to each link into a particular node, and subtracting from outgoing links.A variation on this general relationship can be formulated with

23、each performance metric: packet loss, link load, throughput, congestion probability.A Relationship Between Observable Path Metric, Topology and Link Performance+c+c-c-cFelix Data MeasurementsRouting Changes Apparent in DataData courtesy of Advanced Network Solutions Felix Data MeasurementsRouting Ch

24、anges Apparent in DataData courtesy of Advanced Network Solutions Felix Data MeasurementsRouting Changes Apparent in DataData courtesy of Advanced Network Solutions Felix Topology DiscoveryCorrelation Method: ConceptFelix Correlation Method Identifying Links By Correlation of Paths Group 1Group 1Gro

25、up 2Group 3Group 4Group 5Path APath BPath CPath D01010101Felix Correlation MethodAbstracting Congestion Event Sequence From DataOpen problem: how exactly to get from a delay measurement on a real network to a series of thresholded congestion “events.Several approaches:Average delay in a fixed-length

26、 sliding windowCross-correlation function (pair-wise between paths, but promising)Congestion decision can be complex combination of delay and loss in window probably most robust method, but needs some empirical experience to create useful methodology.We assume a solution and solve the next partFelix

27、 Correlation MethodNetwork Model AssumptionsNode processing delay is negligible, so paths sharing nodes(but not links) do not show correlation. Queueing delay is associated with the link.Network links congest independently.Congestion is modeled asfixed-length discrete-time eventsCongestion rate is f

28、ixed for eachlink, but can vary over a range forthe set of links in the network.Routes are stable Monitor packets are exchangedfrequently enough that congestionevents will be recorded consistentlyacross all paths crossing a given link.Note, this does not require every event to be noticed, and real c

29、ongestion events do occur over a wide range of time scales.Felix Correlation MethodObservations and TriggersAn Observation is a measurement of congestion (however defined) on a path between two monitors.A Trigger is a hypothetical cause of congestion, such as a link, or a group of links, in the netw

30、ork. Method of solution:Based on joint observations across all paths, define a model that discriminates statistically between the true triggers, that represent links in the network, and the apparent (or false) triggers that are due to combinations of true links congesting simultaneously. Then reduce

31、 the triggers down to single links.Felix Correlation MethodObservations and TriggersDefinitions and Notation:An observation event occurs at time t, when a set of paths are congested and not congested as specified.For example,is the observation that paths a, b, d, k are congested and paths c, g are n

32、ot congested at time t. Paths not included in the subscript are “dont care for this observation variable.Illustration of observations, triggers, paths and links:Observation “a = path M1M3,Observation “b = path M2M4Trigger a = all links on path aTrigger ab = links in common between paths a and bM1M2M

33、3M4M5Felix Correlation MethodObservations and TriggersA trigger event occurs at time t, when at least one link congested that is a member (or not a member) of a set of paths as specified.For example,is the event that some link congests that is shared by paths a, b, d, k, and is not on path c, or pat

34、h g.We refer to paths in the specification as “included or “excludedIf all paths are included or excluded, the trigger is “fully specifiedObservation and Trigger Probabilities follow these examples:Felix Correlation MethodRelationship Between Observations and TriggersNow we can related the observati

35、on and trigger probabilities in several interesting ways. E.g., Ratnasamy & McCanneThis set says, considering only two paths, if we see congestion on both paths, then it is caused either by a link the two paths share in common, or one link on each of the paths (not in common) are congesting together

36、.Similarly, if we see congestion on only one path, it must be due to a link that is on that path, and not on the other.Note, this forces us to explicitly write the combinations of triggers that can cause an observation (not very scaleable).Felix Correlation MethodRelationship Between Observations an

37、d TriggersAnother interesting and useful relationship is this:This one says that we observe no congestion on a set of paths only when none of the triggers that are on those paths are active.We say a path (in the trigger specification) contradicts the observation when a path turned off in the observa

38、tion is included in the trigger. (It is easy to write down these combinations.)Inclusion of observations with multiple paths makes this model more powerful than an earlier method (DP = X dL) that relied on a rank-deficient matrix.Felix Correlation MethodOrganization of TriggersTree contains all pote

39、ntial triggers, i.e., all possible combinations of paths that can specify a link or group of links.Triggers on a level partition the set of (potential) links in the graphThe tree grows exponentially as we add paths, but the number of true triggers is bounded by the number of links in the network.Fel

40、ix Correlation MethodSome More Useful Stuff From the Model Observation of congestion on a path means some link on that path is congesting (single-path observation and trigger).Something must be happening, so the sum over all possible observations with n paths specified equals unity.Child triggers ar

41、e related to their parent.No congestion observed anywhere means all triggers are quiet. (The product of all inverse triggers on any level is constant.)Felix Correlation MethodSolving for Trigger Probabilities 3 Path ExampleObservation of no congestion on 3,2,1 paths implies no activity on any trigge

42、r that includes one of the named pathsTriangular form: each equation produces one PvtFelix Correlation MethodGeneralization of Solution to Any Number of PathsCount various things:n = number of paths in the triggers = level in tree diagramk = number of paths in the observation (varying from n down to

43、 1)j = number of paths excluded in the triggers (varying from 0 to n-1)j = 0j = 1j = n-1k paths in obsMaster equation has k = nn paths in trigclass 1 triggers 0 j kclass 2 triggers j = kclass 3 triggers k j n-1Divide “Master equation by each “Specific equation to find one trigger probabilityFelix Co

44、rrelation MethodGeneralization of Solution to Any Number of PathsFor n paths there are 2n-1 equations and 2n-1 triggers.The “Master equation has all possible triggers, i.e., any active trigger contradicts the observation of no congestion anywhere.For class 1 triggers (0 j k):The j paths excluded in

45、the trigger cannot cover all k paths in the observation, so at least one path is included in the trigger that contradicts the observation.All triggers then occur in both the master and specific equations, and cancel out in the division.For class 2 triggers (j = k):The j paths excluded in the trigger

46、 can cover the k paths in the observation, but there is only one combination. Call this the target trigger. All other triggers contradict the observation and cancel out.There is one equation in which each such target trigger survives the division.Felix Correlation MethodGeneralization of Solution to

47、 Any Number of PathsFor class 3 triggers (k j n-1):There are such triggers.No class 3 triggers exist in the first two stages(k = n, and k = n1)All class 3 triggers are computed at previous stages, when they appear as class 2 triggers.For example, consider the case k = 8 j = 9. In the previous stage

48、when we had k = 9, the class 2 triggers with j = 9 were solved. Each “Quotient equation is left with one unknown triggerFelix Correlation MethodGeneralization of Solution to Any Number of PathsGeneral form of solution, for trigger probabilities with paths excluded (first case), and with no paths exc

49、luded (second case):Where:E is the set of excluded paths in the triggerI is the set of included paths in the triggerN is the set of all pathsw is the set of class-3 trigger probabilities in the master equation, but not in the specific equationu is the set of all trigger probabilities with at least o

50、ne path excluded.Felix Correlation MethodPruning Tree Reduces Computational ComplexityReturning to the tree of trigger probabilities For triggers that specify actual links in the network, the trigger probability is the (aggregate) congestion rate on that set of links.False triggers (for which no lin

51、k exists) are approximately zero(True) triggers on the last level identify single links and their associated paths (reduced graph).Therefore, a trigger prob. of zero can be pruned out along with all of its descendents.Number of triggers to compute is bounded by (paths links).Lets see some resultsFel

52、ix Correlation MethodResults18 monitors 23 nodes95 (unidirectional) linksFelix Correlation MethodResults19 monitors 27 nodes114 (unidirectional) linksFelix Correlation MethodResults20 monitors 29 nodes121 (unidirectional) linksFelix Correlation MethodResults50 monitors 61 nodes269 (unidirectional) l

53、inks Run with link congestion rate of 1% (best efficiency) Approx 12 hours to computeFelix Correlation MethodAlgorithm ComplexityComplexity of correlation algorithm is more than (paths links) because the computation of triggers increases with number of paths but it is polynomial: O(LPN + L2P) for L

54、links, P paths, N simulated time intervals.However, the overall run-time is apparently exponential, because it takes more data to discriminate the true and false triggers as the network gets larger.Felix Correlation MethodAlgorithm ComplexityRunning time of simulation and correlation code as functio

55、n of network size (number of links)Exponential increase if quality of result held constant.Link Congestion Rate = 10% (constant).Felix Correlation MethodResults With Variable Link CongestionConstant link congestion rate is artificial constraintAlgorithm works well with links congesting in a range,e.

56、g., tried 1% 5%, 1% 10%, 1% 15%, etc.Effect is to spread the distribution of true trigger probabilitiesLonger convergence timeProbably all of the simplifying assumptions in the model can be relaxed at the cost of increased convergence time.Correlation algorithm ran fastest with 1% link congestionPro

57、bably an artifact of implementationFelix Correlation MethodStatistical Discrimination ProblemNice scaling property of the algorithm depends on being able to discriminate true from false triggers.False triggers are approximately zero, but at edge of solvable parameter space, both populations are more

58、 noisyToo little data (from simulation or measurement)Too much variability in link loss ratesToo much dependence between link congestions, etc, etcNeed to set threshold, group triggers and evaluate “goodness of resulting topology.false triggers0true triggers0true triggersfalse triggers21Felix Projec

59、tGeneral DiscussionWe can make use of multicast idea (MINC project) to reduce load on network: each source multicasts packets to all receivers.This will improve coincidence of measurements in time across all paths.Felix Topology / Performance InferenceApplicabilityDoes not replace “traditional autod

60、iscovery methods (SNMP)May augment autodiscovery in difficult environment:Military network under physical attackMilitary or commercial network under cyber-attackNetwork with buggy software (e.g. routing implementation)Multiple protocol layers, not all included in autodiscoveryProtocols too old or ne