The purpose of this study is to evaluate the quality of on-line departure time-based link travel time estimates. For this, accuracy (i.e. estimation error) and timeliness (i.e. degree of time lag) are proposed as MOE of the quality of on-line link travel time estimates. Then the relationship between quality of link travel time estimates and link length and level of congestion is analyzed. It was found that there is trade-off between the accuracy and timeliness of link travel time estimates. The estimation error was modeled to consist of two components: one is systematic error and the other is mean square error which reflects level of congestion. further, time lag was again segmented into three parts for the analysis purpose. There are minimum one, congestion-related one, and update interval-related one. From the real-world data using AVI system, it was revealed that regardless of the link length and level of congestion, 10 minutes of time lag occurs in general.