Abstract
We consider adaptively finding congestion-free routes connecting specified two locations on a network. In many
practical scenarios, congestion on a network, or transmission time taken to send messages, changes
dynamically. Therefore, we need to effectively learn congestion using past congestion data and efficiently find a
congestion-free route each time we send a message. While there exist learning algorithms that can be used for
predicting congestion, they incur too much computation cost due to the presence of a huge number of possible
routes. We overcome this difficulty by using the zero-suppressed binary decision diagram (ZDD), which is a
compact representation of all possible routes. We develop a learning algorithm that can work on ZDDs without
examining all possible routes explicitly, which enbles us to find congestion-free routes far more efficiently than the
existing algorithms.
Shinsaku Sakaue, Linguistic Intelligence Research Group, Innovative Communication Laboratory
Email: