Competitive On-line Routing (COL)

• Developed by Plotkin et al.

coste = m(ne / ce) - 1

ne = calls carried on edge e, ce = capacity of edge e

• Does not assume traffic information

• Motivated by competitive analysis

  • Variant of COL is O( log n ) competitive ( n = #edges)

Off-line alg accepts < O( log n) (# calls accepted by COL)

Previous slide

Next slide

Back to first slide

View graphic version