Time-division multiplexing over packet-switched network (TDMoPSN) is an intermediate phase of transition from current synchronous TDM to future all-optical converged network. TDMoPSN is exclusively used to transport interactive voice traffic transparently over a PSN (e.g., IP, MPLS or Ethernet). The goal of this paper is to reduce rate-jitter that is introduced into a stream of packets carrying TDM payload. We have proposed two online algorithms, algorithm-A and algorithm-B, to reduce the rate-jitter and shown analytically that the rate-jitter achieved by algorithm-A is strictly less than the rate-jitter of online algorithm proposed by Mansour et al. [1]. We have used three stochastic processes, namely Poisson, Markov-modulated Poisson process (MMPP) and an arrival process with Pareto-distributed inter-arrival times (see [2–4]) for modeling the arrival of TDM packets (say, IP packets with single or many TDM frames as payloads) at the destination. We undertook statistical analysis of the proposed algorithms by modeling the jitter-buffer as $$M/\widetilde{D}/1/\, B_{on}$$M/D~/1/Bon and $$MMPP/\widetilde{D}/1/B_{on}$$MMPP/D~/1/Bon queues, to derive steady-state queue-length distribution, mean waiting time and distribution of inter-departure times. We also simulate the most realistic queueing model $$Pareto/\widetilde{D}/1/B_{on}$$Pareto/D~/1/Bon of our study and evaluated its performance with respect to the metrics: rate-jitter, mean waiting time, packet loss probability and steady-state queue-length distribution. Simulation results show that our proposed algorithms far outperforms the scheme proposed in [1]. We also present simulation results to verify the correctness of analytical queueing models. The algorithms proposed here are more general (for TDMoPSNs) and can be used to study TDMoIP, pseudowire, CES over metro Ethernet network (MEN), etc. © 2015, Springer Science+Business Media New York.