^ Top

NANOG Meeting Presentation Abstract

FIFA: Fast Incremental FIB Aggregation
Meeting: NANOG56
Date / Time: 2012-10-23 12:00pm - 12:30pm
This item is webcast
Room: Dallas Ballroom C-D
Presenters: Speakers:

Yaoqing Liu, The University of Memphis

Yaoqing Liu is a fifth-year PhD student in the Computer Science Department at The University of Memphis. He is expected to graduate in May of 2013. His research interests include Routing Scalability Problems, Network Measurement Techniques, Routing Protocol Design and Next Generation Networks. He has three years' software engineering working experience before joining the PhD program. He has published a few peer reviewed conference and journal papers such as in INFOCOM, JSAC and GlobeCom during his graduate studies (https://umdrive.memphis.edu/yliu6/web/YaoqingLiu.html).
Abstract: The fast growth of global routing table size has been causing concerns that the Forwarding Information Base (FIB) will not be able to fit in existing routers’ expensive line-card memory, and upgrades will lead to higher cost for network operators and customers. FIB Aggregation, a technique that merges multiple FIB entries into one, is probably the most practical solution since it is a software solution local to a router, and does not require any changes to routing protocols or network operations.

While previous work on FIB aggregation mostly focuses on reducing table size, this work focuses on algorithms that can update compressed FIBs quickly and incrementally. Quick update is critical to routers because they have very limited time to process routing updates without impacting packet delivery performance. We have designed three algorithms: FIFA- S for smallest table size, FIFA-T for shortest running time, and FIFA-H for both small tables and short running time, and operators can use the one best suited to their needs. These algorithms significantly improve over existing work in terms of reducing routers’ computation overhead and limiting impact on the forwarding plane while maintaining good compression ratio.
Files: pdfFIFA: Fast Incremental FIB Aggregation(PDF)
youtubeFIFA: Fast Incremental FIB Aggregation
Sponsors: None.

Back to NANOG56 agenda.

NANOG56 Abstracts

  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • The DNS Threats Track
    Panelists:
    Joe Abley, ICANN; David Fernandez, PLXsert; Terrence “Tuna” Gareau, Prolexic | PLXsert; Chris GansterComcast; .
    Patrick GilmoreAkamai Technologies; .
    Chip MarshallDyn; .
    Michael SinatraEDNet; .
    Speakers:
    Tom DalyDynamic Network Services, Inc. ; .
  • Traffic Accounting
    Moderators:
    Elisa Jasinska, Microsoft; Panelists:
    Paolo Lucente, Cariden/pmacct.net; Brent van Dussen, Limelight Networks; Arien Vijn, AMS-IX; Aaron Hughes, 6connect;
  • Traffic Accounting
    Moderators:
    Elisa Jasinska, Microsoft; Panelists:
    Paolo Lucente, Cariden/pmacct.net; Brent van Dussen, Limelight Networks; Arien Vijn, AMS-IX; Aaron Hughes, 6connect;
  • Traffic Accounting
    Moderators:
    Elisa Jasinska, Microsoft; Panelists:
    Paolo Lucente, Cariden/pmacct.net; Brent van Dussen, Limelight Networks; Arien Vijn, AMS-IX; Aaron Hughes, 6connect;
  • Traffic Accounting
    Moderators:
    Elisa Jasinska, Microsoft; Panelists:
    Paolo Lucente, Cariden/pmacct.net; Brent van Dussen, Limelight Networks; Arien Vijn, AMS-IX; Aaron Hughes, 6connect;
  • Traffic Accounting
    Moderators:
    Elisa Jasinska, Microsoft; Panelists:
    Paolo Lucente, Cariden/pmacct.net; Brent van Dussen, Limelight Networks; Arien Vijn, AMS-IX; Aaron Hughes, 6connect;
  • Peering Track
    Speakers:
    Vijay Gill, Microsoft; Bill WoodcockARIN; .
    Martin LevyHurricane Electric; .
  • Peering Track
    Speakers:
    Vijay Gill, Microsoft; Bill WoodcockARIN; .
    Martin LevyHurricane Electric; .
  • Peering Track
    Speakers:
    Vijay Gill, Microsoft; Bill WoodcockARIN; .
    Martin LevyHurricane Electric; .
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;
  • Internet Governance Update Panel
    Moderators:
    Cathy Handley, ARIN; Panelists:
    Sally Shipman Wentworth, ISOC; Vint Cerf, ARIN; Dan Alexander, Comcast; Chip Sharp, Cisco Systems, Inc.; Bill Graham, ISOC;

 

^ Back to Top