The International Computer Science Institute
is pleased to present a talk:

"A Probing Problem Arising in Interdomain Routing"

Richard M. Karp ICSI
karp icsi.berkeley.edu

Friday, March 12, 2004 ICSI, Conference Room 6A 12:00 pm

A sender has a number of packets to be transmitted in each of several periods and must allocate these packets among a number of Internet service providers whose ability to deliver packets is initially unknown. We formulate the problem as a probing problem in which n channels are available for transmitting packets from a source to a destination. Each channel has a fixed, initially unknown, integer capacity c_i. The transmission process takes place in successive rounds. In each round the sender has D packets to transmit, where D does not exceed the sum of the channel capacities. The sender chooses integers q_i summing to at most D and for each i, attempts to send q_i packets through channel i. The number of packets actually transmitted through channel i is min(q_i,c_i). The throughput in the round is defined as \sum_i min(q_i,c_i) and the waste is defined as D minus the throughput. After each round the sender is informed, for each i, whether q_i, the number of packets she transmitted, is less than or equal to c_i. The process continues until the sender achieves throughput D in a single round. We derive upper and lower bounds on the number of rounds required and the amount of waste incurred by an optimal policy. This is joint work with Till Nierhoff and Till Tantau of ICSI, and grew out of a collaboration with several colleagues at AT&T Research.