{"id":114577,"date":"2009-03-16T08:12:00","date_gmt":"2009-03-16T08:12:00","guid":{"rendered":"http:\/\/weblogs.madrimasd.org\/\/sociedadinformacion\/archive\/2009\/03\/16\/114577.aspx"},"modified":"2009-03-16T08:12:00","modified_gmt":"2009-03-16T08:12:00","slug":"dr-tim-griffin-an-algebraic-approach-to-internet-routing","status":"publish","type":"post","link":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/2009\/03\/16\/114577","title":{"rendered":"Dr. Tim Griffin: An Algebraic Approach to Internet Routing"},"content":{"rendered":"
Seminar<\/b>: An Algebraic Approach to Internet Routing
Instructor<\/b>: Prof. Dr. Tim Griffin, University of Cambridge
Location<\/b>: Room 4.1F03, Telematics Department, Torres Quevedo Building, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganes \u2013 Madrid
Dates<\/b>: 16th \u201318th March, 2009
16th & 17th March: 10:00 \u2013 13:30
18th: 10:00 \u2013 13:00
Organization<\/b>: NETCOM Research Group (Telematics Department, University Carlos III of Madrid, Spain); IMDEA Networks (Madrid, Spain)<\/p>\n

The seminar will be conducted in English<\/i><\/div>\n

<\/p>\n

Abstract<\/b>:<\/p>\n

An Algebraic Approach to Internet Routing<\/p>\n

Agreat deal of of interesting work was done in the 1970s in generalizingshortest path algorithms to a wide class of semirings also called \u00abpathalgebras\u00bb or \u00abdioids\u00bb. Although the evolution of Internet Routingprotocols does not seem to have taken much inspiration from this work,recent \u00abreverse engineering\u00bb efforts have demonstrated that analgebraic approach is very useful for both understanding existingprotocols and for exploring the design space of future Internet routingprotocols. This course is intended teach participants the basicconcepts needed to understand this approach. No previous backgroundwill be assumed. The course will start from scratch and end with openresearch problems. Many examples inspired by Internet Routing will bepresented along the way. The Metarouting Toolkit,currently beingdeveloped at Cambridge, will be introduced. This tool allows users togenerate a routing protocols implementation (in C code) from adeclarative, high-level specification based on the algebraic modelspresented in this course.<\/p>\n

Outline of Lectures:<\/b>
1. What is right and wrong with Internet Routing?
2. An overview of algebraic routing
3. Semigroups and orders
4. Semirings
5. Solving Path Problems in Graphs with semirings
6. What is the difference between routing and forwarding tables?
7. Modeling Interior Gateway Protocols (IGPs)
8. Modeling BGP-like routing
9. Constructing Routing Algebras for Internet Routing
10. Metarouting<\/p>\n

Recommended (but not required) reading:<\/b>
1. Graphs, Dioids, and Semirings : New Models and Algorithms. M. Gondran and M. Minoux. Springer 2008.
2. Regular Algebra Applied to Path-Finding Problems. R.C. Backhouse and B.A.Carr J.Inst.Maths.Applics (1975) 15, 161=96186.
3.J. L. Sobrinho, \u00abAlgebra and Algorithms for QoS Path Computation andHop-by-Hop Routing in the Internet,\u00bb IEEE\/ACM Transactions onNetworking, pp. 541-550, August 2002.
4. J. L. Sobrinho, \u00abNetworkRouting With Path Vector Protocols: Theory and Applications\u00bb in Proc.ACM SIGCOMM 2003, pp. 49-60, Karlsruhe, Germany, August 2003.
5. J. L. Sobrinho, \u00abAn Algebraic Theory of Dynamic Network Routing,\u00bb
IEEE\/ACM Transactions on Networking, pp. 1160-1173, October 2005.
6. Metarouting. Timothy G. Griffin and Joo Lus Sobrinho. SIGCOMM 2005.
7. Lexicographic Products in Metarouting. Alexander Gurney, Timothy
G. Griffin. ICNP, October 2007, Beijing.
8. Increasing Bisemigroups and Algebraic Routing. Timothy G. Griffin and Alexander Gurney, RelMiCS10, April 2008.<\/div>\n","protected":false},"excerpt":{"rendered":"

Seminar: An Algebraic Approach to Internet RoutingInstructor: Prof. Dr. Tim Griffin, University of CambridgeLocation: Room 4.1F03, Telematics Department, Torres Quevedo Building, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganes \u2013 MadridDates: 16th \u201318th March, 200916th & 17th March: 10:00 \u2013 13:3018th: 10:00 \u2013 13:00Organization: NETCOM Research Group (Telematics Department, University Carlos III of Madrid, Spain); IMDEA Networks (Madrid, Spain) The seminar will be conducted in English<\/p>\n","protected":false},"author":58,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[1],"tags":[],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":4}},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/posts\/114577"}],"collection":[{"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/users\/58"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/comments?post=114577"}],"version-history":[{"count":0,"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/posts\/114577\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/media?parent=114577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/categories?post=114577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/sociedadinformacion\/wp-json\/wp\/v2\/tags?post=114577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}