Name
Abstract | ||
|---|---|---|
We consider the problem of endhost-based shortest path routing in a network with unknown, time-varying link qualities. Endhost-based routing is needed when internal nodes of the network do not have the scope or capability to provide globally optimal paths to given source-destination pairs, as can be the case in networks consisting of autonomous subnetworks or those with endhost-based routing restrictions. Assuming the source can probe links along selected paths, we formulate the problem as an online learning problem, where an existing solution achieves a performance loss (called regret) that is logarithmic in time with respect to (wrt) an offline algorithm that knows the link qualities. Current solutions assume coupled probing and routing; in contrast, we give a simple algorithm based on decoupled probing and routing, whose regret is only constant in time. We then extend our solution to support multi-path probing and cooperative learning between multiple sources, where we show an inversely proportional decay in regret wrt the probing rate. We also show that without the decoupling, the regret grows at least logarithmically in time, thus establishing decoupling as critical for obtaining constant regret. Although our analysis assumes certain conditions (i.i.d.) on link qualities, our solution applies with straightforward amendments to much broader scenarios where these conditions are relaxed. The efficacy of the proposed solution is verified by trace-driven simulations. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/INFCOM.2013.6567023 | 2013 PROCEEDINGS IEEE INFOCOM |
Keywords | Field | DocType |
routing,upper bound,learning artificial intelligence,cooperative learning,topology,dynamic network,time measurement | Equal-cost multi-path routing,Multipath routing,Mathematical optimization,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Path vector protocol,Destination-Sequenced Distance Vector routing,Computer network,Routing domain,Distributed computing | Conference |
ISSN | Citations | PageRank |
0743-166X | 4 | 0.41 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ting He | 1 | 716 | 44.82 |
| Dennis Goeckel | 2 | 1060 | 69.96 |
| Ramya Raghavendra | 3 | 284 | 23.15 |
| Don Towsley | 4 | 18693 | 1951.05 |