The policing device verifies at a predetermined location of a communication system whether a cell stream transmitted over that communication system satisfies a negotiated cell interarrival time and a negotiated cell delay variation and takes adequate actions. The verification is performed according to an algorithm including the steps of comparing for each cell of the cell stream and at the predetermined location the current arrival time of the cell with a predicted arrival time and discarding the cell if that predicted arrival time is larger than the sum of the present arrival time and an additional time interval. When simultaneously the cell is discarded and the additional time interval is smaller than the negotiated cell interarrival time, the predicted arrival time is adapted and the additional time interval is increased to a value having an upper limit equal to the negotiated cell interarrival time, whereas when the predicted arrival time is smaller than or equal to the current arrival time the additional time interval is decreased to a value having a lower limit equal to the negotiated cell delay variation.