Popular in Course
Joseph Merritt Ramsey
verified elite notetaker
Popular in Computer Information Technology
verified elite notetaker
This 76 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS700 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/215375/cis700-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for CIS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/28/15
Nice Quotation from the Tennenhouse Paper Active Networks Presented by Yun Mao slides in part from Jen Rexford Ion Stoica and Jonathan Smith There is presently a disconnect between what users consider ro be inside rhe network and rhe practitioner39s perspective which is somewhat res rric re For example web browsers allow users to interact with what they perceive to be the networkquot without distinguishing among rhe many routers domain name servers and web servers that conspire ro provide rhe service It may be rime for practitioners ro reevaluate rheir abstractions and start thinking about the network at a higher level Passive Networks Active Network Architecture 0 Dumb storeandforward network Smart end hosts implement key functions Simple routers store and forward packets Limited network processing etgt routing forwarding buffering and packet scheduling 0 Packet header used in a simple way Common standardized format Causes one of a small set of operations to occur Packet forwarded or dropped based on those rules Network largely ignores higher layer headers Add active nodes to infrastructure 39 DJ w mums DAclre nudes Active Networks Motivation for Active Networks 0 Packet data code Smart hosts as before Active nodes that can execute code on the data 0 Store gt translate gt forward Active packets that carry code to active nodes 0 Postscript analogy Contains both your data and the program the printer runs to print your data 0 De nition Active networks allow an individual user or groups of users to inject customized programs into the nodes of the network o Highlevel goal Leverage computation in the network 0 User pull Automatically adaptive streaming Data aggregation to reduce data volumes Computation closer to users to reduce latency 0 Industry push Ad hoc collection of middleboxes emerging Replace with generic multi purpose active nodes Otherwise proliferation of active components will happen anyway without any common framework Motivation for Active Networks Continued AN is expected Big mismatch in rates of innovation Extensibility Applications change quickly eg Web P2P IM Lots of efforts from extensible OS SPIN The network changes slowly EXOKEmEL e EC Deploying new network technology is hard How about extensible networks It39s kind of a distributed OS after all Delay for standardization at the IETF P p d39 rogramming ara lgm Additional delays for vendors to implement and service providers to deploy the new technology Assembly imPeratiVe39gt C mOdUIar39gt Datal09 0 Better to decouple services from hardware Eggmecmrat39ve Ocam39r JaVa funct39ona39 type M39n39m39ze the amount 01 QIObaI agreement Network Programming hand coded gt Click gt P2 Load new services on demand pLAN ANTS I Active Network Now Really I A Motivating Example Shhh Don t tell people you are working on AN This paper proposes a new active network architecturequot automatic rejection 0 Bad word of mouth Security Ef ciency g p 1 Killer applications LOSSy hlgh bW LOSSICSS 10W bW Motivating Examples Two Models of Active Networks ANs Customized packet drop policy 0 Active networks are active in two ways User watching video stream MPEG Switches run code on data owing through them Congestion leads to bandwidth limits Individuals can inject programs into the network Drop selectively the 3 frames Programmable switches discrete ANs Separation of program loading and execution Eg program loading only by network operator Packet is demultiplexed to the right program 0 Capsules integrated ANs Welb caChlngl I Every packet is a program and carries its code Rellable mUtlcaSt Or any mUtlcaSt Perhaps in a restricted programming language Support for mobility Eg ANTS PLAN Requires applicationspecific intelligence 0 Other examples TCPSYN filtering Where Is the Code Three Parts to an Active Network Packets carry the code Maximum exibility High overhead Packets carry reference to the code packet packet Reference is based on the code Meme ngerprint M05 128 bits Advantages Efficient M05 is quick to com ute P Prevents code spoofing verify without trust 0 Execution environment Virtual machine with access to node resources General Turing complete vsl restricted models 0 Active applications Provide an end to end customized service Load code on to the routers to program the VM Node operating system Support multiple execution environments at once Provide safety between execution environments Example Capsules Concerns Security Safety and Performance o Capsule code data Extension of IP packet format 0 Type that identi es the code that should handle the capsule Elgl may indicate a Java class 0 Code runs in transient execution environment Destroyed when the capsule evaluation ends 0 Active storage Capsules can leave information behind in a node39s non transient storage for subsequent capsules 0 External methods cached on the node 0 Protection Can my service damage yours Need to run code in a sandbox 0 Resource management Can my service consume arbitrary resources Need careful control over resource allocation 0 Performance Can my program complete quickly enough to avoid introducing excessive latency Need to limit the complexity of the programs or run them only on lower speed links Security and Resource Mgmt Node Level Protection Untrusted users gt need to isolate their actions Protection make sure that one program does not corrupt other program Node level protection Network level protection Relatively easy to solve Allocate resources among users and control their usage Fair Queueing per flow buffer allocation Use light weight mechanisms sandbox safetype languages Proof Carrying Code FCC an also provide timeliness guarantees e 9 can demonstrate that an operation cannot take more timespace than a predi ned constan Note fundamental tradeoff between protection and exibility Example if a node uses FQ to provide bandwidth protection it will constrain the delays experienced by a user Network Level Protection Ef ciency and Performance More difficult to achieve Challenge enforce global behavior of a program only with local checks and control Main problem programs very flexible Active nodes can Aftect routing behavior eg mobile 1P Generate new packets eg multicast 0 Running programs on packets Questionable on higherspeed links Eg where you have just a few nsec per packet Feasible at the edge eg 100 Mbps 1 Gbps Firewall NAT shaper proxy intrusion detection Feasible for control plane in the core Running routing protocols 0 Computer architecture advances help Faster conventional processors Network processors and FPGAs Multiprocessor cores Performance Case study ANTS Summary Enabling Technologies ANTS implemented in Java In common case little overhead Egtlttra steps over IP classi cation safe eval run very fas Enough cycles to run simple programs eg 16Hz 16bps 1000b packets 100 gt 1000 cycles 10 gt 10000 cycles PLAN P4 are notably faster o Component based software engineering Building blocks for composing software 0 Code mobility eg OCaml Java Though previously between end hosts not network nodes Innovation in safe and ef cient code mobility Performance vs marketin o Field programmable gate arrays FPGAs Enabling higher speed of packet processing 0 Research in programming languages And PL folks39 interest in networking Stepping Back Active Networks vs Overlay Networks 0 Was active network a success or failure General idea of computation and services inside the network Need for a principled approach to midd eboxes and a blurring of router vs general network node Speci c mechanism of packets carrying code 0 How much flexibility is flexible enough What granularity packets vs ows When is code loaded on demand vs in advance Who programs user vs network operator Key difference 7 Active nodes operate at the network layer overlay nodes operate at the application layer 7 Efficieno no need to tunnel packets no need to process packets at layers other than the network layer Overlay Network advantages 7 Easier to deploy no need to integrate overlay nodes in the network infrastructure Active nodes have to collaborated be trusted by the other routers in the same AS they need in exchange routing info Conclusions Active networks A revolutionary paradigm Explores a signi cant region of the networking architecture design space But is the network layer the right level to deploy it Maybe but only if all congested routers are active sensor networks Otherwise overlays might be good enough l ClS 700005 Networking Meets Databases Boon Thau Loo Spring 2007 Lecture 4 Nate semisiias sitemeswmm Huebsch minWritsersig Announcements 5 Paper summaries due at noon today 2 Office hours Wed 34 pm 605 Levine u Project proposal due Feb 12 v Student presenter u 2339d Jan A Scalable Distributed Information Management Systemquot SIGCOMM 2003 u Varun will present VIDB punch line What is Vety Large Depends on W110 You Are Single Site Distributed li itei i39iet Scale Clusters 10s 1005 0005 rMillioi is n cnaiienges u How to run database style queries at internet scale 1 Can DB concepts iniidencetne next internet architecture lioui Design Principles 1 m Relaxed Consistency a ACID transactions severely limits the scalability and availability of distributed databases 3 Besteffort results Organic Scaling 3 Applications may start small without a priori knowledge of size lioui Design Principles ll 2 Natural habitat 3 No CREATE TABLEINSERT No publish to web serverquot Wrappers or gateways allow the information to be accessed where it is created as Standard Schemas via Grassroots software a Data is produced by widespread so ware providing a de facto schema to utilize Application Space u Key properties u s naturally distributed u Centralized collection undesirable legal social performance etc U a m u Homogenous scnernas u Data is more useful Wnen viewed as a Whole u Tnis is tne design space PiER nas cncsen to investigate u Mostlysysternsalgontnrns cnaiienges u As opposed to a Enterprise lnfurrnatiun lntegratiun n SemanticWeb a Data semantics is cleaning challenges Who Needs Internet Scale Example 1 Filenames I L CI CI Simple ubiquitous schemas u Filenames Sizes ID3 tags Born from early P2P systems such as Napster Gnutella AudioGalaxy etc Content is shared by normal nonexpert users home users Systems were built by a few individuals in their garages Low barrier to entry I Example 2 Network Traces El Schemas are mostly standardized in IP SMTP H39I39I39P SNMP log formats a Network administrators are looking for patterns within their site AND with other sites a DoS attacks cross administrative boundaries 1 Tracking virusworm infections a Timeliness is very helpful a Might surprise you how useful it is a Network bandwidth on PlanetLab worldwide distributed research test bed is mostly lled with people monitoring the network status SELECT subnet port prom FROM traffic T unusual U WHERE source a source 3917 AND Up0rt lt1024 dr GROUP BY Tsuhnet I M HAWNG column gt 100 ORDER BY Tsubnet M Eel Declarative IA iii75 P 3 Quemes Query Plan Physical Network Core Network Monitoring Relational Execution Other User Catalog Engine APPS Manager Applications PIER DHT Network Review Distributed Hash Tables 3 What is a DHT in Take an abstract ID space and partition among a changing set of computers nodes D computer currently responsible for that ID Can store messages at the nodes o This is like a distributed hash table a Provides a putlget API Cheap maintenance when nodes come and go o Logarithmic network state and hop count D D Given a message with an ID route the message to the PIER s Three Uses for DHTs i Single elegant mechanism with many uses a Search Index a Like a hash index n Partitioning Value keybased routing e Like GammaNolcano 1 Routing Network routing for QP messages 3 Query dissemination a Bloom lters a Hierarchical QP operators aggregationjoin etc e Not clear there s another substrate that supports all these uses l Enhancements P2P Nelwalk 9 Additional API a localScan namespace retrieve all data items stored in local storage for a particular namespace El newData namespace receive a callback when new data is inserted into the local store for the namespace For each of my attackers how many sites did they attack and how many packets were involved ljoins t SELECT FsourcelP COUNTDISTNCT p COUNTDISTNCT pdesth FROM firewalls F packets P WHERE FsourcelP PsourcelP AND Fdesth ltmyPgt GROUP BY PsourcelP r Symmetric Hash Join a Everybody routes their F and P records to hashsourcelP u Forms a tree per sourcelP can combine tuples in each tree indepen entl u Automatically parallelizes the join algorithm No notion of parallelism in the code falls out the DHT l Recall Parallel Hashjoin Given two tables A and B partitioned across N machines a Amriidr Bmi0inKey c How can we join them i Hashbased repartitioning based on joinKey l Join Algorithms R Join S Symmetric Hash Join a localScan on tables R amp S Rehash tuples into DHT using the join attributes in Nodes receiving repartitioned R and S tuples perform joins locally and forwards results to requestor Fetch Matches u lfthere is an index on the join attributes for one table say R use localScan for other table say S and then issue a lookup for R matches l Symmetric Hash Join 6 rc gt 50 NStemp l N ra sa 39 PUT PUT 53 6rbconstant 6sbconstant l l R S NSr NSs l Fetch Matches 6 sbconstant AND rc gt 50 N rasa Srbconstant G E TS a l l R S NSr NSs I Recall Jom Optimizations I Symmetric Semijom 88 SELECT sname boatl D LONDON PARIS New FROM Sailors 8 Reserves R 6rcgtsc WHERE ssro RSID Reserves Both R and S are 500 pages 1000 pages N projected to save a SailorsSlD sname rating age bandwidth 3 ReservesRDSDboatD GETS GETk 3 Semijoins 39 y Q Tl The complete R and S a Let sjustship SailorsSD from London to Paris Nss PTTra PLI Tsa NB tuples are fetched in 1 Find all matches for Reserves at Paris 8 5 parallel to improve a Ship matching Reserves backto London to completejoin I l latency Bloompins 1 my 1cm stay 1 Same idea but use a bitvector bloom lter I I D l rbconstant l sbconstant I Query Execution in Dynamic I Aggregation in a DHT Environments l7 SELECT COUNT a No major change in logic for QP FROM rewalls One common approach a The state of query execution IS stored In the network D Everybody routes their rewa recordstoa particular collector r a When network reorganizes This forms a tree a EXIsting data repartitioned among eXIstIng and new nodes D Alongthe way count uptotals a New temporary data generated by query execution is a At root form final result automatically rerouted to the proper node Note the shapes of these trees depend on a New nodes will resume any ongoing queries the DHT tOPOIOQV binomial tree a Can reason about comm costs sensitivity to failure influence of malefactors etc I Some Fun Stuff with PIER Hybrid Peer Implementation a PlERGnutella Hybrid Search 7 Distributed WebGnutella Crawler Hybrid Ultrapeer Node PlERSearoh H a uerles and Traffic Search 3 g Limewlre nutella Engine Publisher 8 CE Ultrapeer etwo A E Results BrowseHost sauan 3 SIMS l may era 4 4 PlERQueryProcessor 1 PIERTwo ODHIl veray l PIanetLab Deployment Horizon of P1 4 Q 5 Query M P i5 PJEFiQuery 3 Publish Results Gnu39l39ellu Ultrapesr Gnu39l39ellu links PIER links 0 Hybrid Ultrapesr PIER Gnul39ellu Distributed Web Crawler with PIER 391 P2P users donate excess bandwidth and computation resources to crawl the web a Organized using Distributed Hash tables DHTs u DHT and Query Processor agnostic crawler u Designed to work over any DHT n Crawls can be expressed as declarative recursive queries El Easy for user customization ii Queries can be executed over PIER a DHTbased relational P2P Query Processor CI39EIWIEES Web Servers o liliilil l HiJHilil 1 is liiililwi lililiillii39 i Crawlers PIER nodes l Crawl as a Recursive Query Publish WebPageur Publish mum destUrl L kdstulsilu bp a i H In e r E 59 r I Rate Throttle 8L Reorderl 1 Redirect Filters l Crawler Thread Dup Dubout Links l JJ Cralerapper f m gt Input LJrls Seed Urls DupEnm kquot DHT Scan WebPageurl l Gnutella Network Crawler Oct 2003 Crawl o Popular opensource filesharing network a 450000 users today a Ultrapeer based Topology u Queries flooded among ultrapeers III Leaf nodes shielded from query traffic o Based on multiple crawlers from 30 vantage points on PIanetLab If Ft Ultrapeer nodes Leaf nodes gt100 Files 0 Files 0100 Files l Status of PIER today n At one time ran on 24x7 on PIanetLab continuously for more than a year El Written in Java El First to use Bamboo as DHT a Available for download httppiercsberkelevedu El Ryan Huebsch s PhD dissertation httpwwwrineracom s Some potential class projects El Applications applications applications a Multiquery optimizations a Stream semantics to Internetscale Query Processing in Adaptive query optimizations Eddy Operator El Sensor networks Query processing in GHT a Data integration to handle heterogeneous schemas PIER Lighthouse r GUI called Lighthouse for query entry and result display a Designed primarily for application developers a User inputs an optimized physical query plan Other Intemet Scale Query lingines a DHT based u SDIMS next week a NonDHT based u lrisNet httpViMNvintelirisnetj u Astrolabe Cornell uP2 Motivation of Knowledge l ktne Revisit tne EridrtorErid pnricipa r 84 J SaliZer D Reed and D Clark Eridrtorerid Arguments in system Design 3 Add something to a networklayer only Wnen absolutely required 3 wnat is good and bad aboutthe eridtoerid pnncrpan r Today s intemet nas prob iems Network carnes oata wo knowingwhat data is or its purpose intelligence edges not in core 3 simpie transparent network ieaos to user frustration when fails occur 3H igh management overhead 3 Manual conrrguratron diagnosis and design Proposed Objective u Build a fundamentally different sort of network that can assemble itself given high level instructions reassemble itself as requirements change automatically discover when something goes wrong an automatically fix a detected problem or explain why it cannot do so l Ideals m Selfsustaining network a Less lowlevel human involvement u Adapt to new traf c patterns a Allow the network to make lowlevel decisions when hi I 39fied u h evel goals are speci More effective interaction with end users and administrators 39l39mditional Router Routlng Protocol Control Plane Data Plane I v croissant War mung immature deb Traditional Router Where is the Knowledge Plane Knowledge mails t The Internet quot and its End Challenges vquot Lots and lots and lots of questions 1 How to represent and utilize knowledge 1 How to Scale u How to route knowledge u HOW to deal With malicious or untrustworthy incentives Research in the past 3 years 1 information Planes u A service urserviee eumpunent that emerentty delivers timely and relevant data abuutthe state ufthe systemtu all the dispersed umpunents Elf the system L RAD Lab http radlab cs berkeleveduWikiRAD Lab a Reliable Adaptive Distributed systems Laburatury Spunsured by Sun Bungle and Mierusuft Next lecture a Public Health for the Internet PHI 3 CIDR 07 paper on our reading list optional 3 httpopenphinet at Next Tuesday a AScalable Distributed Information Management Sstem SIGCOMM 04 1311 More on Benet Frames for HD Curves Given a curve f la b gt IE or f a b gt E of class 0 with p Z n it is interesting to consider families 6105 ent of orthonormal frames Moreover if for every k with 1 S k S n the kth derivative fkt of the curve f0 is a linear combination of 6105 6105 for everyt Ela b then such a frame plays the role of a generalized Henet frame This leads to the following de nition De nition 13111 Let f lab gt IE or f ab gt E be a curve of class 0 with p Z n A family 61tent of orthonormal frames where each 622 lab gt E is Cn i continuous for 139 1 n 1 and en is Cl continuous is called a moving frame along f Furthermore a moving frame 610 ent along f so that for every k with 1 S k S n the kth derivative fkt of f0 is a linear combination of 61t ekt for every t 6 la b is called a Frenet n frame or Frenet frame 1 More Un Frenet If e1t ent is a moving frame then eZt ejt 2 for all i7j 1 S i7j S n Lemma 13112 Let f ab gt IE or f db gt E be a curve of class 0 with p Z n so that the derivatives f1t f 1t of ft are linearly independent for all t E a b Then there is a unique Frenet n frame e1t ent satisfying the following conditions I The k frames f1tfkt and e1tekt have the same orientation for all k with 1 S k S n 1 2 The frame e1t ent has positive orientation 1 More Un Frenet Proof Since f1t f 1t is linearly independent we can use the Gram Schmidt orthonormalization procedure see lemma 427 to construct 6115 7 6711105 from f1t7 fm l We use the generalized cross product to de ne en Where 6n61gtltgtlt6n1 Fiom the Gram Schmidt procedure7 it is easy to check that ekt is 0714 for 1 S k S n 1 and since the components of en are certain determinants involving the components of 61 7 6711 it is also clear that en is Cl D The Fienet n frame given by Lemma 13112 is called the dis tinguished Frenet n fmme We can now prove a generalization of the Fienet Serret formula that gives an expression of the derivatives of a moving frame in terms of the moving frame itself 1 More Un Frenet Lemma 13113 Let f ab gt IE or f db gt E be a Mquotquot quotFquotquotquotquot quot39 curve of class 0 with p Z n so that the derivatives f1t f 1t 0fft are linearly independent for all t 6 ab Then for any moving frame e1t ent if we write cumt ext ejt we have 6205 20127 061107 with WU Wz39jt7 and there are some functions Oilt so that ft 20406415 Furthermore if 7 is the distinguished Frenet n frame associated math f then we also have 04106 f t 1091 0 for igt 2 More on Frenet 0 for gt 1 Proof Since 6105 ent is a moving frame it is an or thonormal basis and thus f0 and exit are linear combina tions of 6105 ent Also we know that 6205 26205 39 6139 Wei 0 j1 and since 615 615 62 by differentiating if we write 012705 6205 39 6139 07 We get Wit Wz39jt Now if 6105 ent is the distinguished Henet frame by construction 615 is a linear combination of f1t fit and thus exit is a linear combination of f2t fi1t hence of 6105 eZH I 1 More Un Frenet In matrix form when 61tent is the distinguished Fienet frame the row vector 6105 620 can be expressed in terms of the row vector 6115 767105 Via a skew sym metric matrix w as shown below More Un Frenet 630 7 6205 61t7 76ntwt7 where 0 W12 W12 0 W23 w U2 3 0 i wniln Un1 n 0 The next lemma shows the effect of a reparametrization and of a rigid motion Lemma 13114 Let f ab gt IE or f db gt E be a curve of class 0 with p Z n so that the derivatives f1t f 1t of ft are linearly independent for all t 6 ab Let h E gt E be a rigid motion and assume that the corresponding linear isometry is R Let f h o f The following properties hold 1 For any moving frame e1t 7 ent the n tvple 1tez where an ReZt is a moving frame along f and we have 52315 LUZAt and 1705 1 2 For any orientation preserving di eormorphism p cd gtab ie pt gt 0 for allt Ecd if we write f f o p then for any moving frame e1t 7 ent on f the n tvple e1t l 7510 where an eZpt is a moving frame on f 1 More Un Frenet Furthermore 0 than More on Frenet Mfg llf prt The proof is straighthrward and is omitted The above lemma suggests the de nition of the curvatures K177l n1 De nition 13115 Let f lab gt IE or fab gt E be a curve of class Op with p Z n so that the derivatives f1tf 1t of f0 are linearly independent for all t 6 la b If 6115 7 67105 is the distinguished Frenet frame associated with f7 we de ne the ith curvature IQ of f by 7 Wm 7 llft 7 withlSz Sn l l More Un Frenet Observe that the matrix wt can be written as W llftf t7 More Un Frenet Where 0 12 f 12 0 K23 K f 23 0 39 Kniln quot n71n 0 The matrix It is sometimes called the Cartan matrix Lemma 13116 Let f ab gt IE or f db gt E be a curve of class 0 with p Z n so that the derivatives f1t7 7f 1t 0fft are linearly independent for allt E a b Then for every i with 1 S i S n 2 we have Islt gt 0 Proof Lemma 13112 shows that 61 767111 are expressed in terms off1 fm l by a triangular matrix dzj whose diagonal entries a are strictly positive ie we have 6239 Zaijfj7 j1 fori177n 1 and thus fa 25276 j1 for 139 17n 1 with biz a231gt 0 Then since 6211 f0 0 forj S 239 we get 1 More Un Frenet Hle Wii1 6 39 i1 02414211 396i1 aiibi1i17 and since Wily1111 gt 0 we get KZ gt 0 17n 2 El We conclude by exploring to What extent the curvatures n1 K7111 determine a curve satisfying the nondegeneracy condi tions of Lemma 13112 Basically such curves are de ned up to a rigid motion 7 Lemma 13117 Let f lab gt 1E and lab gt IE or f cub gt E and cub gt E be two curves of class 0 with p Z n and satisfying the nondegeneracy conditions of Lemma 13112 Denote the distinguished Frenet frames asso ciated with f and f by e1t ent and 16 7510 If Islt for every i with 1 S i S n 1 and for all t 6 la b then there is a unique rigid motion h so that fhof 1 More Un Frenet Proof Fix to E lab First of all there is a unique rigid motion h so that 1 More Un Frenet hftofto and 36ito ito7 for all 239 with 1 S 139 S n where R is the linear isometry associated with h in fact a rotation Consider the curve 7 h o f The hypotheses of the lemma and Lemma 13114 imply that T2705 t wu 705 1705 llft7 and by construction 6 1050 ent0 31050 7050 and 7050 ft0 Let W 26705 3205 39 6705 3205 il Then we have 605 2 ZEN 6705 670 3205 it eZt et 2Ze7t 9 Using the Fienet equations we get 6 i1 j1 i1 j1 i1 j1 0 7 n n ej ZE E Luzjej i1 j1 n n ej ZE E awe i j1 i1 j2ZZWije i j1 21 since w is skew symmetric Thus 60 is constant the Benet frames at to agree we get 605 0 More Un Frenet and since Then7 6 215 3205 for all 2397 and since we have 70 IIWUIIEW llftlle1t we so tint 7052 icoristant Howeven 7 to ft07 and so flttgt ftgt7 and f f her a Lemma 13118 Let n1 nnn be functions de ned on some open la7b containing 0 with nz Cn i l continuous fori 17n 1 and with Islt gt 0 fori 17n 2 and all t E lab Then there is curue f lab gt E of class 0 with p Z n satisfying the nondegeneracy conditions of Lemma 13112 so that 1 and f has the n 1 curuatures K105 7Kn1t Proof Let X t be the matrix Whose columns are the vec tors e1t ent of the Fienet frame along fl Consider the system of ODE s Xt Xtf t7 with initial conditions X 0 I Where Mt is the skew sym metric matrix of curvatures By a standard result in ODE s there is a unique solution X 1 More Un Frenet We claim that X t is an orthogonal matrix For this note that More Un Frenet XXT XXTXXT XI XT XI TXT XI XTXI XT0 Since X0 I we get XXT I If Ft is the rst column of X t we de ne the curve f by M 8Flttgtdt7 with 5 Ela b It is easily checked that f is a curve parametrized by arc length with Henet frame X 5 and with curvatures Kils El I CIS 700005 Networking Meets Databases Boon Thau Loo Spring 2007 Lecture 15 Announcement 2 minute informal spiel on class project on Thursday Will miss class on 3 Apr 5 DARPA meeting 3 Apr 10 NetDBNSDI 2007 Era of change for the Internet quotin the Wittyodd years since its rnvention new uses and abuses are pushrng the Internet rnta reatns that is on39gr39nal design neither antrb39pated nor easri y accommodates coming Burris to D sruptive Innovation in networking IISF Workshop Report 05 Efforts at Internet Innovation LI Evolution Overlay Networks a Commercial Akamai VPN MS Exchange servers a P2P filesharing telephony a Research prototypes on testbed PIanetLab Revolution Ign a NSF Futur I tem esi DErogram a NSFGIoI vironme f r Thstigations GENI intiatix Internet Context of ROFL paper 52 Up to this point in class a Distributed Hash tables Network Data Independence gt Decouple location from identit a Overlay networks 391 Internet Indirection Infrastructure i3 a Active ne c Extreme solution a Declarative networks PLAN IANTs ri Safe languagesquot of active networks a Cleanslate radical architectural changes i TRAID IPNL LFNDOA HIP SNF ROFL PlanetLab P IN P labs have used PIanetLablo develop riewtectiriolbgies 1dr distributed storage network mapplng peerr torpeer systems distributed basri tables and query processing PIanetLab currently consists M754 nodes at 353 SIIES httpwwwplanetlaborgl G E N I Global EnVIronment for Network Innovations Q e 7 Wha 395 GEN Clean Slat Design foxtho internist Exams Global Emirerimerir for Xenmrk Innevaiioris GI3Y1 is 2 faciliq eeneepr being explored by the Us compim39ng s pp Pm h D e 1 cm The goal ofGEXI L to increase the queer and quanub of experimmnl researeh omcomes in so 39 39 39 39 39 39 7 39 quot 39 39 Emits neuvorking and distributed systems and lo accelerate the Lransidon of these outcomes into pmducls and senices 7 Chauenges that will enhance economic compeddx sues and secure the Xau39on39s xture Untimely research performed an overview anemone r I i J quot Weekly Seminars Success Past SeEnm 7 mums with me suppon of me xsr Direcmraie for Computer and Infannau39ou Science and Engineering L39CISE me i was Goa mymg 1 7 v A V quot 39 L quot I A Vquot L m H y Projects 7 2 mveminnsi b m my fan Reqmrerrienis already alien place and under the leadership of a planning group an initial stramnan design has been compleiei e V Snapsnog The design being shared broadly herein for eeremem use 111 support a number ufmwnhall meeringsinrhe V ear 39 s 397 39 39 1 39g W Discussion List MG 7 Meeungs csrig a eomperiiive merit re139e39process use is planning la suppan he esrsbiisimeni afa GEM Coordinating Contact Wewmuemea WWW GWUPS censnm um GCC in 1006 The sec mil represem the Computing cammunirys broad research iura39ests in me Reireais 39 Broad Pa lclpallun GE mm A NM s Design DMWENS This web site is currenth maintained bv me 231 planning Sump as a forum fur discussing GET which mm in httpwwwgeninet 300 million plan httpllcleanslatestanfordedu One ofthe Key Goals of Cleanslate Evolution of Networks How much of an architecture can evolve over time hypothesis no more quotone size fits allquot network El what must remain stable what is the least common denominator El 100 Mbps for 100 million American homes ie n x Ch mama the meta arch quot g h 39 ii T 32273 100x100 Clean Slate PrOJect DTN eivciiiiismce s H l Background sew emsnr vars Imeme DTNvl Larch instance Partnjpams researchers to e global infrastructure that onnects hundreds of millions of people iv the MGM I MANET arch instance M mim39n i magmaquot I I yaw 39 IUl 39 Sensors arch instance i Internal site and servicesTn rizr mm a ihi 39 needed or have no Chance of ever being deployed metaarch Cumnumeeiiuns i News Ro l Us W h We ask 39 L 39 39 e Projerr etreat i A quotwewerenot Common question must addresses be eXpIICItIy prisentam principiesa clean siaie designhowsimuin wedom de nedsupported by a network escapee 39 39 M r 39m o architecture should it be addresscentric httpWWW1oox1oonetwork rgl JelgerTschudin Dagsluhl Seminar OctNov 2006 I When Addresses rule the Net Internet Addressing Scheme Review In the AR PAN ET addresses were fixed and could actually be 3 Class based addressmg SChemeS used as quotlonglived namesquot e Address 1 is UCLANMC RFC597 1973 a 32 ms d39V39dEd 39quotto 28 parts 126 El IsIyOme39EITXTfile is mapping a static symbol into another static a Class A 0 network host N16M hoes Same with the early Internet 0 16 4616163 a 10008 is BBNPR RFC820 1982 a Class B Ii N65Khoss After the introduction of DNS in 1984 addresses are still very a Class C 0 24 Ions vat Ii El RFCs still contain the static list of assigned addresses 2541mm El estimated number of hosts 1000 a Classless Interdomain Routing CIDR RFC990 1986 is the last one to contain a list of aSSIgned addresses a Variable pre x prevents wastage D estimated number of hosts lt 10000 El Prefix aggregation lower overhead of Interdomain routing El Routers match to longest prefix a a r m JelgerTschudin Dagsluhl Seminar OctNov 2006 lScalabili Routin Table Size W g Without ClDR 2327100 2327100 2327110 2327110 2327120 2327120 5101 internet 232712550 232712550 With ClDR 2327100 232710016 What s wrong with Internet addressing today 1692290016 1692290016 4 gt 16922962 24 5 Hierarchical addressing allows excellent scaling properties 3 But forces addressing to conform to network topology 2 Since topology is not static addresses can t persistently identify hosts a Host can have multiple locations mobility a Host can have multiple identities multihoming W hat s wrong with Internet addressing today a When the Internet was rst invented a Nodes are mostly static so location identity 9 Easy to impose hierarchy But most network applications today require persistent identity in the presence of changingmultiple locations 397 It s hard to provide persistent identity in presence of hierarchical addressing 9 Need to decoupleidentity from addressing a Drastically complicates network con guration mobility address SSIgnmen a Seems difficult to achieve l TVO trends fl may URL ArklressEs gelling DN 1 d I ieywor s sllmlvlnul IllI glam w mmbmes global more and more NAT K pen protocol IP emails numbers global Ell 13945 AS numbers 16ml labels QDIV lpm39me I I I l I I I I sec 1 day I year 10 years JEIgErTschudln 7 Dagstuhl SEmInarr OctNuv mus Two trends 2 Nmmug becomes a quotsearchquot act1VlfV M f instead of 10011111 URL global pintprotocol numbers E17143 AS numbers 10ml labels F mm 13d ll quIcIIcy I I I I I I I I I see 1 day 1 year 10 years 34 m tniDAgmliSeminn 335 5 JEIgErTschudln 7 Dagstuhl SEmInarr OctNay mus Solutions we have studied 2 Level of indirection I Locationidentity split 3 Name resolution Route using a name a Name turns into location IP address a Location is ephemeral name is longterm identi er I Eg Mobile IP Internet Indirection Infrastructure ROFL ls there an alternative Why not route on af host identi ers 2 Assign addresses independently ofnetwork topology 2 Get rid orocation and hierarchy altogetherll 2 Be a Purist Architectural uniformity to the extreme 5 Benefits 2 No separate name resolution system required 2 Simpler network con glallocationmobility a Allocatlorl otloentlies neeo onlyensure uniqueness bout adherence to network topology 2 Simpler more meaningful networklayer access controls lderltl errbased lnstead of lPrbased Is it possible to route on flat identi ers a Challenge flat identifiers break aggregation a Is it possible to scalany route without aggregation 2 Paper is more about addressing the feasibility of flat naming without hierarchy and generating discussions 2 Postman delivers using SSN not addressquot a Not astraightforward application of DHTs 2 Assumes pointtopoint routing Cannot address the problem of building 39om scratchquot a network 2 Doesn t support routing policies l OS vst Internet 2 OSI conceptually de ne services interfaces protocols c Internet provide a successful implementation Application mnspon Int Application Net ess39v Physical Physical DSI formal Internet informal l Basic idea beh39moi ROFL m Scalable routing on flat identifiers n Goal 1 Scale to Internet topologies Goal 2 Support for BGP policies n Highly challenging problem but solution would arguably give a number of benefits Basic mechanisms beMd ROFL 39 Goal 1 Scale to Internet topologies 2 Mecharism DHT style routing maintain sourceroutes to successors ngers 2 Provides Scalable network routing without aggregation Goal 2 Support for BGP policies 2 Mecharism Intelligently choose successors ngers to con form to ISP relation ships 2 Provides Support for policies operational model of BGP l How ROFL works arscn xClBACE mam lnternet policies today hierarchy in prefer customer over peer ru 5 ii ierarc hy 2 Source De ination c Economic relationships peer providercustomer 5 Isolation routing contained within hierarchy i Canon DHT background Basis for Interdomain routing in ROFL erge rings in a bottomup fashion parenil with two conditions If For an identi er id ring 1 with external pointer to idI7 in ring 2 No identi ers haween 39id idh idh will he id s successor 39Exiemai 39 ringer 0log n nunber of pointers be lnlemal linger j 9 isolation in ROFL Canon External Successor erna email Successor Successor i Policy support in ROFL 39 Mechanism eenng relationships to V39rtual ASe 7 a Source r Peering 7 r oxA153 oxsaAc e 2 L i ox sa ox aasr oxr a oxaa Ai a Two extensions to improve locality D Maintain proximitybased ngers in a policysafe fashion D Pointer caching strategies prefer nearby popular pointers 0x355 More Routing Concerns Routing control D Interdomain endpointbased negotiation D lntradomain leverage the interdomain design Isolation rt PI39DPe 2 Enhanced delivery services D Anyca D Multicast pl urity D Default offHotnets 05 Hosts reachable only 39om ngers D Use capabilities a capability is a cryptographic token designating that a pa icular source is allowed to contact the destination I Evaluation Enterprise TSP simulations Load balance Distributed packetlevel simulations a Deployed on cluster across 62 machines scaled to 300 million os a Inferred Internet topology from Routeviews Rocketfuel C skitter traces Implementation a Ran on Planetlab as overlay covering 82 ASes a Configured interISP policies from Routeviews traces 39 Metrics stretch control overhead router memory Fraction of msns traversing router usage 0 50 100 150 200 250 300 Router number r No hot spots introduced by protocol Enterprise TSP simulations Internet scale simulations Reduction in chum 7 1E10 g 1E08 E I g 1E06 2 a g 1E04 E I g 1E02 1221 I inn inmn lEEI6 lEEIE IEI I inn mono iEEI6 lEEIE IEH 8 1E00 Numberufhusts Numberufhusts 1 10 100 1000 10000 I IDsperISP Jom overhead lt300 msgs stretch lt 14 37m181xless comm overhead Rootserver lookups in ate latency from n 341200xless memory requirements 54ms t0 134ms IDS has no penalty I Conclusmm a Routing On Elat Labels should not leave you 1 Bolling On the Eloor Laughing a Because performance is tolerable a Because it provides several benefits 7 ROFL is one point in the design space entries at a ROFL as lookup a ROFL forcontent routing u Better support for ONYX INS PIER P2 a The results are close enough to tempt but not enough to sa isfy failures have failures only t Later in the semester a Virtual Ring Routing DHT on wireless networks Similar to ROFL s Interdomain design 135ms 137m5 pointer cahes lookup 54ms a ge entlies at Edge million DNS entries at pointers 39 39 Modeldriven Tes r Genera rion Oleg Sokolsky September 22 2004 Outline and scope Classification of modeldriven testing Conformance testing for39 communication protocols Coveragebased testing Cover39age criteria Coveragebased test gener39ation Can we do more open questions Testing classification By component level Unit testing Integration testing System testing By abstraction level Black box White box Grey box we Testing classification By purpose Functional testing Performance testing Robustness testing Stress testing Who performs testing Developers Inhouse QA Thirdparty I Functional testing An implementation can exhibit a variety of behaviors For each behavior we can tell whether it is correct or not A fest can be applied to the implementation and accept or reject one or more behaviors The test fails if a behavior is rejected A fest suite is a finite collection of tests Testing fails if any test in the Suite fails we39re Formal methods in testing Testing can never demonstrate the absen errors only their presencequot Edsger W Dijkstra How can formal methods help Add rigor Reliany identify what should to be tested Provide basis for test generation Provide basis for test execution ce of we39re Modeldriven testing Rely on a model of the system Different interpretations of a model Model is a requirement Blackbox conformance testing QA or third party Model is a design artifact Greybox unitsystem testing QA or developers we39re Conformance testing A specificaTion prescribes legal behaviors Does The implementation conform To The specificaTion Need The noTion of conformance NoT inTeresTed in How The sysTem is implemenTed WhaT wenT wrong if on error is found WhoT else The sysTem can do am39 39e Test hypothesis How do we relate beasts of different species Implementation is a physical object Specification is a formal object A55ume there is a formal model that is faithful to implementation We do not know it Define conformance between the model and the specification Generate tests to demonstrate conformance we39re Conformance testing with LTS Requirement is specified as a labeled transition system Implementation is modeled as an inputoutput transition system Conformance relation is given by ioco Tretmans96 Built upon earlier work on testing preorders WT Historical reference Process equivalences Tr39ace equivalencepreor39der39 is Too coar39se Bisimula rionsimula rion is Too fine Middle ground Failures equivalence in CSP may and must resting by Hennessy Tes ring pr39eor39der39 by de Nicola They are all The same Righ r no rion but hard To compu re l 39 39 Testing architecture Implementation relation Test generation algorithm Test execution engine last suite Ta InputOutput Transition Systems 50 dime nicke 1 52 lcoffee H60 53 54 LI dime nicke LU lcoffee lfea arm s 0 dime nickel from user39 To machine inifia rive wi rh user39 machine canno r refuse inpuf LI LI LU Q coffee Tea fr39om machine ro user39 inifia rive wi rh machine user39 canno r r39efuse oufpuf Lu LIULU L InputOutput Transition Systems Inpu rOu rpu r Transition Systems IOTS LLLU Q LTS LIU LU dime nicke dime dime 39 39 nickel IOTS is LTS wi rh Inpu rOu rpu r quot39Ckel Icoffee l rea and always enabled inpu rs O O dime Mime nicke nicke for all s ra res s 9 LI dimenickel for all mpu rs a 6 LI 5 LU lcoffee l lea MWS RTE Preorders on IOTS imp environment 2 environment e i E S E imp g LILu X LIULu Observing IOTS where sys rem inpu rs in rer39ac r wi rh environment ou rpu rs and vice versa mm Z3 l 39 39 Preorders on IOTS imp environment 2 environment e i E 5 E iimps ltgt V e obs i g obs s am 39g InputOutput Testing Relation environment environmen r e e i E 5 E i sIm s lt2 V e e IOTSLULI obs e i g obs es obsep Traces eIIp q rr39aces eIIp q rr39acesp 6 e L p after 6 refuses LU Z3 l 39 39 Testing preorders a side note One of the reasons for using IOTS over LTS is that SM is computationally simpler than conventional testing preorder Testing preorder requires us to compare sets of pairs trace refusal set At the same time Sic allows us to use inclusion of weakly quiescent traces inputs can never be refused by i and outputs can never be refused by e iafterarefusesA gt A or ALU am39 39e Representing quiescence Extend IOTS with quiescent transitions deterministic 5tr39ace automata p dime nicke 9 39 39 gilgnkil dme 39 9 39 kael lcoffee ea 0 0 dime Mime nicke nicke AP 6 dime nicke dime O Mime nicke nICke lcoffee ea 0 O dime Mime 5 5 nicke nicke ITQ39FE Conformance relation ioconf Finally i sws 2 V oeLou r Ai after a g ou r As after 6 Allow under39specifica rion r39es rr39ic r To Traces of s i ioconf s def Vae rr39acesAsnLou rAi after a g ou rAs after a ioconfs use ar39bi rrary F ins read of Traces of s Conformance r39ela rion ioco accoun rs for repe f fI39ve quiescence mm Z3 l 39 39 Testcases A Tes r case is a de rerminis ric IOTSLULI wi rh fini re behaviors No re reversed inpu rs and ou rpu rs Do not allow choice be rween ou rpu rs or be rween inpu r and ou rpu r pass Verdic r func rion v S gt foilposs dime Tes r run i passes T def iI IT offer 6 deadlocks gt v r of rer csposs O foil icoffee H60 pass fail MWS am39 39e Test generation Tes r Sui re T3 for39 a specification 5 is comple re i ioconf 5 iff V reTs i passes r Tes r Sui re Ts is sound if i ioconf S gt V reTs i passes r Comple re Tes r Sui res ar39e u5uay infini re Aim of generating sound Tes r Sui res Test generation algorithm Gen As F Choose nondeterministically I stop and 1t pass 2 t a GenA39S Fafter a with A2 gt A39s 1t pass 3 IZxstopxeLUx 0utASZxIxxe0utAS Vtpass if 660u1AS vseF other39wise fail Vstopfai1if geF other39wise pass we39ve H Exampl e F dimecoffee 0 pass ou rp u r adime enabled Of lcoffee I pass I s not in Faf rer39 dime AP 8 dime nicke dime Mime mcke nICke lcoffee ea 0 0 dime Mime 5 5 nicke nicke WTE Test purposes Where does F come from Test purposes Requirements use cases Automata message sequence charts Test purposes represent quotinterestingquot or quotsignificantquot behaviors Define quotinterestingquot or significant Can we come up with test purposes automatically we39re Summary conformance testing AdvanTages Ver39y rigorous formal foundaTion Size of The TesT SuiTe is conTr39olled by use cases Disadvantages How much have we learned abouT The sysTem ThaT passed The TesT SuiTe Does noT guar39anTee cover39age we39ve Coveragebased testing Tr39adiTional TesTs are derived from The implementation sTr39ucTur39e code Modeldriven Cover39 The model insTead of code Model should be much closer39 To The implemenTaTion in sTr39ucTur39e Relies on coverage cr39iTer39ia l 39 39 Coverage criteria and tests HongLeeSokolskyUralOZ Con rr39ol flow alls ra res allTransitions Da ra flow alldefs alluses allinputs allou rpu rs Tes r is a linear sequence of inpu rs and ou rpu rs am39 39e Specifications EFSM Tr39ansi rion sys rems equipped with variables Tr39ansi rions have guards and upda re blocks t1 insertmxlt5 mmx I t2 coffeemgt1 mm1 t3 done t4 displayym t5 displayY3Zm am39 39e Coverage criteria Each coverage cri rerion is represen red by a se r of Temporal logic formulas WCTL a Subse r of CTL A romic proposi rions p1 7 Temporal opera rors EX EU EF Conjunctions a r mos r one nona romic conjunc r Nega rions is applied only To a romic proposi rions Unres rric red disjunctions Eg EFp1amp EFpZ WCTL formulas have linear wi rnesses l 39 39 Allstates coverage criterion Requires every s ra re be covered a r leas r once Wi rh ever39y s ra re s associate EFs amp EFexit t1 insertmxlt5 EFidle amp EFeXit 32m EFbusy amp EFeXit I t2 coffeemgt1 w mm1 t3 done t4 displayym t5 displayVan am39 39e Alltransitions coverage criterion Requires every Transition be covered a r leas r once Wi rh every Transition t associa re EFt amp EFexit t1 insertmxlt5 EFt1 amp EFexiz mmx EF1 2 amp EFeXiz t2 coffeemgt1 EFz 3 amp EFeXit mm1 EFt4 amp EFeXil EFt5 amp EFeXiz t3 done t4 displayym t5 displayY3Zm were Data flow definitions and uses 39 Definition a value is assigned to a variable Use a value of a variable is used in an expressmn Variables are defined and used in transitions 39 Definitionuse pair vtt v is defined by t v is used by t There is a path from tto t free from other definitions of v we39re Covering a dupair Wi rh a dupair39 v t t assoc e EFt Si EXEdefv U t Si EFexitjD defv disjunction of all Transitions Tha r define v t1 insertmxlt5 EFt1 amp EXEt1 t2 U t2 amp EFeXit mmx t2 coffeemgt1 mm1 t3 done t4 displayym t5 displayym am39 39g Dataflow coverage criteria Alldefs coverage cr39i rer39ion a definitionclear pa rh from everydefini rion To some use Alluses coverage cr39i rer39ion a defini rionclear39 pa rh from everydefini rion To every use t1 insertmxlt5 Alluses coverage criterion mmx EFt1amp EXEt7 t2 U H amp EFeXit t2 c0ffeemgt1 EFt7 amp EXEt1 t2 U t2amp EFeXit mm1 EFt1 amp EXEt7 t2 U t4 amp EFeXit EFt1 amp EXEt7 t2 U t5 amp EFeXit EFt2 amp EXEt7 t2 U H amp EFeXit t3 done EFt2 amp EXEt7 t2 U t2 amp EFeXit EFt2 amp EXEt7 t2 U t4 amp EFeXit EFt2 amp EXE H t2 U t5 amp EFeXit t4 1a 2554 p H l 39 39 Data flow chains AffecT pair39 v t v t The value of v used by t affecTs The value of v defined aT t EiTher39 zz vl dir39ecTIy affecTs v l or39 There is a dupair39 v ll sT vl dir39echy affecTs v l and v l affecTs v l t1 insertmxlt5 X t1 directly affects m t1 mmx t2 coffeemgt1 X t1 affeCtS Y t5 mm1 t3 done t4 displayyz t5 displayyII 111I lg Data flow chain coverage Affec r pair v t v t May consis r of an arbi rrary number of definitionuse pairs We ex rend CTL wi rh leas r fixpoin r opera rors Al rerna rively we can use alternationfree mu calculus Allinpu rs coverage cri rerion Requires a pa rh from every inpu r To some ou rpu r be covered a r leas r once Allou rpu rs coverage cri rerion Require pa rh from every zmpq ro every Test Generation System True or model false Model checker Logic Witness or formula counterexample System model Model checker Test Generation Generating a witness for a formula Cost the length of a witness A minimalcost witness for a formula Existing model checkers generate a minimalcost witness by breadthfirst search of state space E U 0 W