Differentiated service (DiffServ) architecture has become one of the research hotspots on computer networking in the last two years. Its intention is to provide quality of service for users at coarse granularity level. In contrast to integrated service architecture, DiffServ is not only more scalable, but also easier to be deployed in traditional packet switching networks. In this paper, the packet-marking algorithm, one of the key mechanisms in DiffServ is studied. A new packet-marking algorithm called FMPA (fair marking packet algorithm) is presented. The new algorithm is compared with the existing proportional pachet-marking algorithm by simulation. In addition, a packet remarking algorithm is proposed. By using it, the packet's original semantic can be kept to the largest degree. The simulation result shows it in this paper.