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 languageEnglish (US)
Pages (from-to)2222-2226
Number of pages5
JournalIEEE International Conference on Communications
StatePublished - 2002
Event2002 International Conference on Communications (ICC 2002) - New York, NY, United States
Duration: Apr 28 2002May 2 2002

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'The enhanced ticket-based routing algorithm'. Together they form a unique fingerprint.

Cite this