Successful management and control of wastewater and storm water systems requires accurate sewer flow measurements. Unfortunately, the harsh sewer environment and insufficient flow meter calibration often lead to inaccurate and biased data. In this paper, we improve sewer flow monitoring by creating redundant information on sewer velocity from natural wastewater tracers. Continuous water quality measurements upstream and downstream of a sewer section are used to estimate the travel time based on i) cross-correlation (XCORR) and ii) dynamic time warping (DTW). DTW is a modern data mining technique that warps two measured time series non-linearly in the time domain so that the dissimilarity between the two is minimized. It has not been applied in this context before. From numerical experiments we can show that DTW outperforms XCORR, because it provides more accurate velocity estimates, with an error of about 7% under typical conditions, at a higher temporal resolution. In addition, we can show that pre-processing of the data is important and that tracer reaction in the sewer reach is critical. As dispersion is generally small, the distance between the sensors is less influential if it is known precisely. Considering these findings, we tested the methods on a real-world sewer to check the performance of two different sewer flow meters based on temperature measurements. Here, we were able to detect that one of two flow meters was not performing satisfactorily under a variety of flow conditions. Although theoretical analyses show that XCORR and DTW velocity estimates contain systematic errors due to dispersion and reaction processes, these are usually small and do not limit the applicability of the approach.