Abstract
The Delay-constrained least-cost routing problem is to find the least cost path which satisfies a given delay constraint. There are two major difficulties to solve this problem. The first difficulty is the NP-Completeness of this routing problem. The second difficulty is that the networking information used for routing may be imprecise. The ticket-based routing (TBR) algorithm, aiming to find a sub-optimal solution, provides a heuristic approach to overcome the above difficulties and solve the routing problem. Although TBR proposes a detailed ticket forwarding method based on imprecise end-to-end information, it does not optimize the ticket probing process so as to find better paths. This paper proposes an Enhanced Ticket-based Routing (ETBR) algorithm. The ETBR improves the effectiveness of ticket probing by two techniques. The first technique uses color-based ticket distribution for tickets of different colors. The tracing information of green tickets and yellow tickets is kept separately to avoid unnecessary ticket dropping. The second technique uses historical probing results to optimize ticket probing, so that redundant probing paths are eliminated. Through extensive simulations, we demonstrate that the ETBR can find paths which have much lower cost than TBR, without decreasing the success ratio or increasing the message overhead.
Original language | English (US) |
---|---|
Pages (from-to) | 2222-2226 |
Number of pages | 5 |
Journal | IEEE International Conference on Communications |
Volume | 4 |
State | Published - 2002 |
Event | 2002 International Conference on Communications (ICC 2002) - New York, NY, United States Duration: Apr 28 2002 → May 2 2002 |
ASJC Scopus subject areas
- Computer Networks and Communications
- Electrical and Electronic Engineering