May 2007 - talks - lists.cs.princeton.edu

M Mahmoody Ghidary general exam
by Melissa M Lawson 17 May '07

17 May '07

Mohammad Mahmoody Ghidary will present his research seminar/general exam on Thursday May 24 at 2PM in Room 402. The members of his committee are: Boaz Barak (advisor), Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------- Abstract: ----------------------------------- I will show the first lower-bound on the efficiency of Signature Schemes in the random oracle Model. The lower-bound is tight up to a constant factor for one-time signatures. The current constructions of signatures are considered to be inefficient by practitioners, and the result shows that it is actually inherent. We will see some ideas of the proof. No background is assumed. Reading List: ----------------------------------- The list contains also some papers about another research direction: "Average-case vs Worst-case complexity". General Complexity Theory: The book: "Complexity Theory: A Modern Approach" (by Arora, Bara) Chapters 1 to 9 Advanced Complexity topics: The same book. Chapters: 16: Derandomization, Expanders and Extractors 17: Hardness amplification and error correcting codes 18: PCP and hardness of approximation. General Cryptography: Lecture notes of the Cryptography course by Barak available at: http://www.cs.princeton.edu/courses/archive/fall05/cos433/ Lectures 1-20 Research Papers: --Worst-Case vs Average-Case Complexity: *Feigenbaum, Fortnow. On the random-self-reducibility of complete sets. *Bogdanov, Trevisan. "On worst-case to average-case reductions for NP problems" *Gutfreund, Shaltiel, Ta-Shma. "If NP languages are hard on the worst-case then it is easy to find their hard instances." --The possibility and the efficiency of cryptographic reductions: *R. Impagliazzo and S. Rudich, "Limits on the Provable Consequences of One-Way Permutations" *Reingold, Trevisan, Vadhan "Notions of Reducibility between Cryptographic Primitives" *Katz, Gennaro, Gertner, "Lower Bounds on the Efficiency of Encryption and Digital Signature Schemes" *Gennaro, Trevisan, "Bounds on the Efficiency of Generic Cryptographic Constructions"

1 0

S Brahma general exam
by Melissa M Lawson 17 May '07

17 May '07

Siddhartha Brahma will present his research seminar/general exam on Wednesday May 23 at 10AM in Room 402. The members of his committee are Bob Tarjan (advisor), Moses Charikar, and Boaz Barak. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------- Abstract: Studies in Distribution Sensitive Data Structures A distribution senstitve data structure is one whose running time on a sequence of operations supported by the data structure depends on some distributional properties of the sequence. Although some work had been done before, distribution sensitive data structures became important after the seminal paper on Splay trees by Sleator and Tarjan [0]. In the paper several types of distributive properties were defined and it was proved that splay trees have several of these properties (eg. static optimality, working set property, dynamic finger property, etc) by using amortized analysis, and miraculously without storing any extra information about the sequence. Then the question naturally arises whether we can define similar properties for data structures other than binary search trees. There has been interesting work recently in terms of both defining new properties (unified property) and proving these properties for new or existing data stuctures (eg. planar point location data sturctures, priority queues, etc). We will give a broad survey of the whole area, mentioning some recent results in detail and discuss some interesting open problems. We will also show some preliminary results for data structures for the Max Priority Interval problem having some of the properties described above. Reading List: [0] D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J.ACM, 1985. [1] John Iacono. Distribution Sensitive Data Structures. Ph.D. Thesis. Rutgers, SUNY,2001. [2] Chengwen Chris Wang. Multi-Splay Trees. PhD thesis, CMU, Pittsburg, PA, 2006. [3] Introduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press, 2001.(Chapters 10-14, 17, 18-21). [5] J.Iacono and S.Langerman. Proximate planar point location. in SoCG 2003. [6] R. E. Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth., 1983. [6] Dion Harmon. New Bounds on Optimal Binary Search Trees. PhD thesis, MIT, Boston, MA, 2006. [7] M. T. Goodrich, M. Orletsky, K. Ramaiyer, Methods for achieving fast query times in point location data structures, in SODA 1997. [8] Data Structures and Network Algorithms. Robert E. Tarjan, 1983. [9] John Iacono: Optimal planar point location. SODA 2001. [10] Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality -- Almost. FOCS 2004. [11] C.C.Wang, J.Derryberry, D.D.Sleator: O(\log\log n)-competitive dynamic binary search trees. SODA 2006.

1 0

Q Xi general exam - rescheduled
by Melissa M Lawson 15 May '07

15 May '07

Qian Xi's general exam has been rescheduled for this Wednesday May 16 at 4PM in Room 402. Her committee is JP Singh (advisor), David August, and Vivek Pai.

1 0

C Toler-Franklin general exam
by Melissa M Lawson 15 May '07

15 May '07

Corey Toler-Franklin will present her research seminar/general exam on Monday May 21 at 2PM in Room 402. The members of her committee are: Szymon Rusinkiewicz (advisor), Adam Finkelstein, and Tom Funkhouser. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ------------------------------------------- Illustration of Complex Real-World Objects using Images with Normals Corey Toler-Franklin This project investigates the creation of non-photorealistic illustrations from a type of data lying between simple 2D images and full 3D models: images with both a color (albedo) and a surface normal stored at each pixel. Images with normals combine an acquisition process only mildly more complex than that for digital photographs (and significantly easier than 3D scanning) with the power and flexibility of tools similar to those originally developed for full 3D models. We investigate methods for signal processing on images with normals, developing algorithms for scale-space analysis, and segmentation. These are used to implement analogues of stylized rendering techniques including toon shading, line drawing and and exaggerated shading. We believe that images with normals or "RGBN images" may become an important and widely-used data type, because of the ease, flexibility, and quality with which they may be acquired, and because they contain enough information to permit sophisticated analysis and depiction.We show that our rendering pipeline can produce detailed yet understandable illustrations in medical, technical, and archaeological domains. Books WATT, A. 1996. 3D Computer Graphics Second Edition. WATT, A., AND WATT, M. 1998 Advanced Animation and Rendering Techniques. Papers DECARLO, D., FINKELSTEIN, A., RUSINKIEWICZ, S., AND SAN- TELLA, A. 2003. Suggestive Contours for Conveying Shape. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 22, No. 3, 848-855. DECARLO, D., FINKELSTEIN, A., AND RUSINKIEWICZ, S. 2004. In- teractive Rendering of Suggestive Contours with Temporal Coherence. In Proc. NPAR. DECAUDIN, P. 1996. Cartoon-Looking Rendering of 3D-Scenes. Tech. Rep. 2919, INRIA. FELZENSZWALB, P., AND HUTTENLOCHER, D. 2004. Efficient Graph- Based Image Segmentation. International Journal of Computer Vision, Vol. 59, No. 2 (Sept.). GOOCH, A., GOOCH, B., SHIRLEY, P., AND COHEN, E. 1998. A Non- Photorealistic Lighting Model for Automatic Technical Illustration. In Proc. ACM SIGGRAPH. LUFT, T., COLDITZ, C., AND DEUSSEN, O. 2006. Image Enhancement by Unsharp Masking the Depth Buffer. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 25, No. 3. MARKOSIAN, L., KOWALSKI, M., TRYCHIN, S., BOURDEV, L., GOLDSTEIN, D., AND HUGHES, J. 1997. Real-Time Nonphotore- alistic Rendering. In Proc. ACM SIGGRAPH, 415-420. RASKAR , R., TAN, K.-H., FERIS, R., YU, J., AND TURK, M. 2004. Non-Photorealistic Camera: Depth Edge Detection and Stylized Ren- dering using Multi-Flash Imaging. ACM Trans. Graphics (Proc. SIG- GRAPH), Vol. 23, No. 3. RUSHMEIER, H., TAUBIN, G., AND GUEZIEC, A. 1997. Applying Shape From Lighting Variation to Bump Map Capture. In Proc. Eurographics Rendering Workshop. RUSINKIEWICZ, S., BURNS, M., AND DECARLO, D. 2006. Exagger- ated Shading for Depicting Shape and Detail. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 25, No. 3. SAITO, T., AND TAKAHASHI, T. 1990. Comprehensible Rendering of 3-D Shapes. In Proc. ACM SIGGRAPH, 197-206. SLOAN, P.-P., MARTIN, W., GOOCH, A., AND GOOCH, B. 2001. The Lit Sphere: A Model for Capturing NPR Shading from Art. In Proc. Graphics Interface. THIRION, J.-P., AND GOURDON, A. 1996. The 3D Marching Lines Algorithm. Graphical Models and Image Processing, Vol. 58, No. 6 (Nov.), 503-509. TOMASI, C., AND MANDUCHI, R. 1998. Bilateral Filtering for Gray and Color Images. In Proc. ICCV. WINKENBACH, G., AND SALESIN, D. 1994. Computer-Generated Pen- and-Ink Illustration. In Proc. SIGGRAPH.

1 0

J Yoon general exam
by Melissa M Lawson 14 May '07

14 May '07

Janet Yoon will present her research seminar/general exam on Thursday May 17 at 10AM in Room 402. The members of her committee are Bob Tarjan (advisor), Andrea LaPaugh, and Bob Sedgewick. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------------------------------- Planarity testing is used for many real-world applications such as circuit design. The first linear time planar embedding algorithm was introduced in 1974 by Hopcroft and Tarjan. More than thirty years later there continues to be an interest in this area. Efficiency is an important factor in the applicability of an algorithm, but just as crucial is its simplicity. I will first briefly introduce past algorithms; more specifically the algorithms of Cederbaum Even and Lempel, Boothe and Lueker, and Boyer and Mervold. Then I will introduce a better abstracted, simpler algorithm based on these algorithms. References [1] K. S. Booth and G. S. Lueker. Testing the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Com-put. Syst. Sci., 13:335-379, 1976. [2] J. M. Boyer and W. Myrvold. Stop minding your p's and q's: A simplified o(n) planar embedding algorithm. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, volume 13, pages 140-146, 1999. [3] Z. Galil, G. F. Italiano, and N. Sarnak. Fully dynamic planarity testing. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4, Victoria, B.C., Canada., pages 495-506, New York, 1992. ACM. [4] J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM 21,pages 549-558, Oct. 1976. [5] W-L Hsu. An efficient implementation of the pc-tree algorithm of shih and hsu's planarity test. Tech. Report, Inst of Inf Science,Academia Sinica, 1993. [6] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005. [7] A. Lempel, A. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium, Rome, Italy., pages 215{232, New York, 1967. Gordon and Breach. [8] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM J. Appl. Math., 36:177-189, 1979. [9] R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. [10] Y. Makarychev. A short proof of kuratowski's graph planarity criterion. Journal of Graph Theory, 25:129-131, 1997. [11] J. M. Boyer P. F. Cortese M. Patrignani and G. Di Battista. Stop minding your p's and q's: Implementing a fast and simple dfs-based planarity testing and embedding algorithm. 2003. [12] W.-K. Shih and W.-L. Hsu. A new planarity test. Theoretical Computer Science, pages 179-191, 1999. [13] R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J.Comput., 1(2):146-160, 1972. [14] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1987. [15] R. M. McConnell W.-L. Hsu. Pq trees, pc trees, and planar graphs. Theoretical Computer Science, 296(1):59-74, 2003. [16] S. G. Williamson. Depth-first search and kurotowski subgraphs. Journal of the ACM, 31(4):681-693, 1984.

1 0

Q Xi generals - canceled today
by Melissa M Lawson 14 May '07

14 May '07

Due to a scheduling conflict, Qian's generals will not be held today. We will reschedule and reannounce. thanks.

1 0

N Heninger general exam
by Melissa M Lawson 11 May '07

11 May '07

Nadia Heninger will present her research seminar/general exam on Thursday May 17 at 2PM in Room 402. The members of her committee are; Bernard Chazelle (advisor), Boaz Barak, and Moses Charikar. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------------- Abstract: In 2004, Goemans and Vondrak showed that there is a sparse set of edges which covers the minimum spanning tree of a random subgraph of vertices or edges chosen independently with probability p. I improve the bounds for the case where edges can be chosen with arbitrary different probabilities and show that this result does not generalize to the case when vertices are chosen non-independently. I will also explain how their main lemma is actually an intriguing fact about reliability polynomials, which represent the probability that a network is connected under failure, a well-known #P-complete problem. I will discuss some natural open problems connected to this work. Reading list: N. Ailon, B. Chazelle, S. Comandur, and D. Liu Self-Improving Algorithms. SODA 2006 Holm, J., de Lichtenberg, K., and Thorup, M. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. STOC '98. Charikar, M. S. Similarity estimation techniques from rounding algorithms. STOC '02. Indyk, P. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (May. 2006), 307-323. M. Luby and A. Wigderson, "Pairwise independence and derandomization," Tech. Rep. 95-035, International Computer Science Institute (ICSI), Berkeley, 1995. A. Z. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher. Min-wise independent permutations. STOC '98 S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998. Motwani & Raghavan Randomized Algorithms Ch 5, 6, 8, 10 Mitzenmacher & Upfal Probability and Computing Ch 2, 3, 4, 5, 6, 7, 9 Vazirani Approximation Algorithms Ch 12, 13, 14, 15

1 0

A Halderman preFPO
by Melissa M Lawson 11 May '07

11 May '07

Alex Halderman will present his preFPO on Thursday, May 17 at 10 A.M. in CS 302. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Adam Finkelstein and Brian Kernighan, non-readers. Everyone is invited to attend his talk. The abstract follows below. ------------- Learning from Security Failures in Non-Traditional Computing Environments Decades of bitter experience with security failures in desktop computers and network environments have led to intuitions and engineering practices that help us build more robust systems. However, as computers are becoming smaller and cheaper, they are taking on new forms that challenge our intuitions. >From RFID tags embedded in sneakers and passports, to "smart" cell phones and car navigation systems, many new applications occupy environments that look little like those with which researchers are familiar, and the old rules increasingly do not apply. When security fails in such environments, it often fails spectacularly, with layers of vulnerabilities that, compounded, are costly or impossible to repair. By studying such security disasters, and asking why they are especially severe, we hope to develop new security techniques suitable for a world of ubiquitous computing. One traditional security intuition that is now being challenged is the distinction between data and software. When received from a trusted source, data files are considered a lower risk than software, since only software can contain security bugs that weaken the computer's defenses. Recent events cause us to question the value of this distinction. In a widely-publicized incident, the record label Sony-BMG sold several million music CDs (normally considered a data-only medium) that contained undisclosed software intended to thwart copying. We studied this software using a variety of analytical techniques and discovered that it contained serious defects that threatened consumers' security and privacy. Merely playing the CDs caused the installation of dangerous software that provided several routes for attackers to subvert the computer's security mechanisms. These problems were exacerbated by the non-traditional environment of a hybrid music and software CD, which allowed the discs to avoid scrutiny by the ecosystem of security software vendors that monitor for deviant behavior. Other security intuitions are being challenged in the realm of embedded computers. Once, such systems were though of as "dumb" appliances, protected from most security risks by their simple designs and lack of network connectivity, but as they have grown increasingly sophisticated, they have come to resemble full-blown computers, together with the attendant security problems. We found evidence of this trend in the United States' most widely used electronic voting machine, the Diebold AccuVote-TS. Using reverse-engineering and novel software analysis methods, we discovered that the machine suffers from many of the same security problems as desktop PCs, including the potential for attackers to install malicious software and spread viruses from machine to machine. Because of its embedded nature, the machine has none of the protections that are now standard on desktop computers. As a result, an attacker could exploit these problems to steal votes undetectably on a wide scale. In many ways, our approach to these and other examples can be compared to the systematic disaster investigations conducted after major transportation accidents or structural failures. We seek to learn what went wrong not only in each particular case but also in the broader context that allowed the problems to occur. Our findings highlight the need to extend existing protections to non-traditional environments, as well as to develop new security techniques that are suitable to these applications. We propose specific remedies in each case, such as cryptographic privacy protection protocols for camera phones, and efficient machine-assisted auditing techniques for voting. We also apply our theories to predict problems that may be discovered in the future: for instance, Internet worms that spread by exploiting weaknesses in the new generation of networked videogame consoles. Finally, we consider legislative and regulatory remedies, including policy measures that have already gained momentum in the wake of our findings concerning the Sony-BMG and Diebold systems.

1 0

Y Zhu general exam
by Melissa M Lawson 10 May '07

10 May '07

Yaping Zhu will present her research seminar/general exam on Wednesday May 16 at 10AM in Room 402. The members of her committee are Jennifer Rexford (advisor), Larry Peterson, and Vivek Pai. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------------- Abstract Conventional wisdom has held that routing protocols can not achieve both scalability and high availability. Despite scaling rather well, today's Internet routing system does not react quickly to changing network conditions. Overlay networks, on the other hand, can respond quickly to changing network conditions, but their reliance on aggressive probing does not scale to large topologies. This project presents a resilient layered routing architecture called UFO (Underlay Friendly to Overlays), which achieves the best of both worlds by providing router support for overlay routing mechanisms. UFO comprises two changes to existing routers: (i) data-plane support for deflection packets at the behest of the overlay and (ii) explicit notification about significant changes in network conditions. We present these two mechanisms, and demonstrate how they facilitate the scalable deployment of overlay routing mechanisms at the network layer. Prototype is implemented based on PL-VINI platform, with preliminary evaluation results. Reading List 1. L.Peterson and B.Davie, "Computer Networks: A Systems Approach", 3rd Edition. 2. D.Clark, "Design Philosophy of the DARPA Internet Protocols", in Proc. ACM SIGCOMM, Aug 1988. 3. J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. 4. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. 5. D.Andersen, H.Balakrishnan, M.Kaashoek, and R.Morris, "Resilient Overlay Networks", in Proc. ACM SOSP, Oct 2001. 6. N.Feamster, D.Andersen, H.Balakrishnan, and F.Kaashoek, "Measuring the Effects of Internet Path Faults on Reactive Routing", in Proc. ACM SIGMETRECS, Jun 2003. 7. A.Nakao, L.Peterson, and A.Bavier, "A Routing Underlay for Overlay Networks", in Proc. ACM SIGCOMM, Aug 2003. 8. J.Jannotti, "Network Layer Support for Overlay Networks", in Proc. IEEE OPENARCH, 2002 9. T.Griffin, F.Shepherd, and G.Wilfong, "The Stable Paths Problem and Interdomain Routing", IEEE Transactions on Networking. Volume10, Issue2 p232-243. 10. R.Morris, E.Kohler, J.Jannotti, and M.Kaashoek, "The Click Modular Router", in Proc. ACM SOSP, Dec 1999.

1 0

Yi Wang general exam
by Melissa M Lawson 10 May '07

10 May '07

Yi Wang will present his research seminar/general exam on Wednesday May 16 at 2PM in Room 402. The members of his committee are Jennifer Rexford (advisor), Larry Peterson, and Kai Li. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------------- Morpheus: Making Routing Programmable Abstract: The Border Gateway Protocol (BGP) is used by Internet Service Providers (ISPs) to exchange reachability information with neighboring domains. Internet Service Providers (ISPs) express complex policies, affecting everything from business relationships with their neighbors to traffic engineering, scalability, and security, by configuring the BGP. However, the routing architecture within an ISP, coupled with the multi-step BGP route-selection algorithm running on the routers, imposes significant restrictions on the policies that can be realized in practice. These restrictions stand in the way of ISPs achieving policy objectives that are important in practice, such as enabling new services to customers. We argue that the limitations of BGP can be overcome by providing greater visibility into the candidate routes, a more flexible decision process, and support for for multipath routing and forwarding. We present Morpheus, a modular, open routing platform that enables network operators to realize many useful policies that are infeasible today through: (1) flexible composition of multiple (possibly third-party developed) policy modules, and (2) programming the route-selection algorithms. Morpheus also supports multipath routing, which is essential in enabling many new customizable routing services. Morpheus can be readily deployed without requiring changes in other domains. We've implemented an Morpheus prototype as an extension to XORP, the extensible open routing platform. Our evaluation of the prototype demonstrates that the system can scale to the large number of address blocks and BGP sessions present in large backbone networks. We are currently working on demonstrating the flexibility of the prototype in supporting new routing policies. Reading list: Textbook: L. Peterson and B. Davie, Computer Networks: A Systems Approach, Morgan Haulmann, 3e, 2003 Papers: [1] D. Clark, " <http://www.cs.utah.edu/classes/cs7941-001/papers/e2e88.pdf> The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 [2] N. Feamster, H. Balakrishnan, J. Rexford, A. Shaikh, and J. van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp.pdf> The Case for Separating Routing from Routers," ACM SIGCOMM workshop on Future Directions in Network Architecture, August 2004 [3] A. Greenberg, G. Hjalmtysson, D. Maltz, A. Meyers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang, " <http://www.cs.princeton.edu/%7Ejrex/papers/ccr05-4d.pdf> A Clean Slate 4D Approach to NetworkControl and Management," ACM SIGCOMM Computer Communications Review, October 2005 [4] M. Handley, E. Kohler, A. Ghosh, O. Hodson, P. Radoslavov, " <http://www.xorp.org/papers/xorp-nsdi.pdf> Designing Extensible IP Router Software," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [5] Matthew Caesar, Donald Caldwell, Nick Feamster, Jennifer Rexford, Aman Shaikh, and Jacobus van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp-nsdi.pdf> Design and implementation of a Routing Control Platform," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [6] B. Raghavan and A. Snoeren, " <http://www.cs.ucsd.edu/%7Ebraghava/papers/platypus-sigcomm04.pdf> A System for Authenticated Policy-Compliant Routing," ACM SIGCOMM, September 2004 [7] T. V. Lakshman, T. Nandagopal, R. Ramjee, K. Sabnani, and T. Woo, " <http://www.sigcomm.org/HotNets-III/HotNets-III%20Proceedings/lakshman.pdf> The SoftRouter Architecture," ACM Workshop on Hot Topics in Networks, November 2004 [8] G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin, " <http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/5.pdf> Working Around BGP: An Incremental Approach to Improving Security and Accuracy for Interdomain Routing," Symposium on Network and Distributed System Security, February, 2003 [9] T. Griffin, B. Shepherd, and G. Wilfong, " <http://www.stanford.edu/%7Erjohari/336/Griffin_SPP.pdf> The Stable Paths Problem and Interdomain Routing," IEEE Transactions on Networking, 10(2), April 2002 [10] M. Caesar and J. Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/policies.pdf> BGP Routing Policies in ISP Networks," IEEE Network Magazine, Special Issue on Interdomain Routing, November/December 2005 [11] Hong Yan, T. S. Eugene Ng, David Maltz, Hui Zhang, Hemant Gogineni and Zheng Cai, " <http://www.cs.rice.edu/%7Eeugeneng/papers/NSDI07-4D.pdf> Tesseract: A 4D Network Control Plane", USENIX Symposium on Networked Systems Design & Implementation, April 2007 [12] Wen Xu and Jennifer Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/multipath06.pdf> MIRO: Multi-path Interdomain ROuting," ACM SIGCOMM, September 2006

1 0