The algorithms in this category compute paths using one or more of the following oracles: contacts summary, contacts, and
queuing. Further, each message is routed independently of the future demand because the trac oracle is not used. These al-
gorithms are all based upon assigning costs to edges and computing a form of minimum-cost (\shortest") path. Costs are
assigned to edges (by consulting the available oracles) to reflect the estimated delay of the message in taking that edge. The
challenge and sophistication lies in assigning costs such that the assigned costs are close to the delay that will actually be
encountered when a message is forwarded across the DTN (delay tolerant network).
The reasons for considering only cost-based algorithms in this class are two-fold. First, they provide a convenient and common way to utilize the di erent knowledge oracles (thereby, identifying to what extent global knowledge is necessary). Second, they correspond naturally to traditional shortest-path based routing problems which are well-understood and for which simple computationally-efficient distributed algorithms are known. This simplicity, however, comes at the price of imposing certain restrictions on the nature of routing paths determined. One key limitation is that only a single path to a destination is derived. As argued earlier, for DTNs it may be important to use multiple paths (with splitting) to achieve near-optimal performance. Interestingly, the basic ideas introduced here can be used to find multiple routes and good split sizes. This is discussed briefly at the end of this section.
queuing. Further, each message is routed independently of the future demand because the trac oracle is not used. These al-
gorithms are all based upon assigning costs to edges and computing a form of minimum-cost (\shortest") path. Costs are
assigned to edges (by consulting the available oracles) to reflect the estimated delay of the message in taking that edge. The
challenge and sophistication lies in assigning costs such that the assigned costs are close to the delay that will actually be
encountered when a message is forwarded across the DTN (delay tolerant network).
The reasons for considering only cost-based algorithms in this class are two-fold. First, they provide a convenient and common way to utilize the di erent knowledge oracles (thereby, identifying to what extent global knowledge is necessary). Second, they correspond naturally to traditional shortest-path based routing problems which are well-understood and for which simple computationally-efficient distributed algorithms are known. This simplicity, however, comes at the price of imposing certain restrictions on the nature of routing paths determined. One key limitation is that only a single path to a destination is derived. As argued earlier, for DTNs it may be important to use multiple paths (with splitting) to achieve near-optimal performance. Interestingly, the basic ideas introduced here can be used to find multiple routes and good split sizes. This is discussed briefly at the end of this section.
RSS Feed