Network　latency　is　a　significant　indicator　for　the　evaluation　of　service　quality　in　real-time　network　applications.　However,　data　missing　and　data　anomaly　are　inevitable　when　measuring　network　latency,　which　degrades　the　performance　of　latency　estimation.　In　this　paper,　we　propose　a　robust　low-tubal-rank　tensor　completion　algorithm　with　graph-Laplacian　regularization　(RLTCGR),　which　handles　the　problem　of　network　latency　estimation　and　anomaly　detection　simultaneously.　Meanwhile,　by　exploiting　the　spatial　characteristics　of　the　network　latency,　we　develop　a　graph-Laplacian　regularization　for　improving　the　performance　of　latency　recovery　and　anomaly　detection.　Finally,　we　carry　out　extensive　experiments　by　using　the　real-world　dataset.　The　experimental　results　show　that　the　proposed　algorithm　outperforms　the　other　existing　algorithms　in　terms　of　both　latency　estimation　and　anomaly　detection.　©　2021　IEEE.