Error message

  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 362 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 400 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 362 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 400 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
Home > Node > An Algebraic Approach to Internet Routing
An Algebraic Approach to Internet Routing
16 March 2009 - 9:00am to 18 March 2009 - 12:00pm
Ponente(s): 
Prof. Dr. Tim Griffin, University of Cambridge
Lugar: 

Room 4.1F03, Telematics Department, Torres Quevedo Building, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganes – Madrid

Organización: 
NETCOM Research Group (Telematics Department, University Carlos III of Madrid, Spain); IMDEA Networks (Madrid, Spain)

Abstract:

An Algebraic Approach to Internet Routing

A great deal of of interesting work was done in the 1970s in generalizing shortest path algorithms to a wide class of semirings also called "path algebras" or "dioids". Although the evolution of Internet Routing protocols does not seem to have taken much inspiration from this work, recent "reverse engineering" efforts have demonstrated that an algebraic approach is very useful for both understanding existing protocols and for exploring the design space of future Internet routing protocols. This course is intended teach participants the basic concepts needed to understand this approach. No previous background will be assumed. The course will start from scratch and end with open research problems. Many examples inspired by Internet Routing will be presented along the way. The Metarouting Toolkit,currently being developed at Cambridge, will be introduced. This tool allows users to generate a routing protocols implementation (in C code) from a declarative, high-level specification based on the algebraic models presented in this course.

Outline of Lectures:

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

Recommended (but not required) reading:

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, "Algebra and Algorithms for QoS Path Computation and Hop-by-Hop Routing in the Internet," IEEE/ACM Transactions on Networking, pp. 541-550, August 2002.
4. J. L. Sobrinho, "Network Routing With Path Vector Protocols: Theory and Applications" in Proc. ACM SIGCOMM 2003, pp. 49-60, Karlsruhe, Germany, August 2003.
5. J. L. Sobrinho, "An Algebraic Theory of Dynamic Network Routing," 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.

Presentation 1 Download PDF in new window (576 KB)
Presentation 2 Download PDF in new window (459 KB)
Presentation 3 Download PDF in new window (1.833 KB)
Presentation 4 Download PDF in new window (139 KB)
Presentation 5 Download PDF in new window (570 KB)

 

Photograph of Prof. Dr. Tim Griffin
Photograph of Prof. Dr. Tim Griffin
 
Photograph of Prof. Dr. Tim Griffin
Photograph of Prof. Dr. Tim Griffin
 

The seminar will be conducted in English

Más información: 
  • 16th-18th March, 2009
  • 16th & 17th March: 10:00 – 13:30
  • 18th: 10:00 – 13:00