Abstract: Peer-to-peer streaming cache is employed widely as it can reduce the bandwidth usage and improve the utilization of objects efficiently, in which FIFO and LRU algorithms are often used to replace objects. However, media streaming is different from Web objects and the P2P network is also different from the client/server model and has its own features so that the system performance may be restricted when these algorithms are applied in distributed environment. To solve this problem, FIFO and LRU are analyzed and then two algorithms are presented, evaluated and compared with FIFO, LRU and LSB (least sent bytes). The SD algorithm makes its decision based on supply-demand relationship of media segments, and the REP algorithm ejects objects according to replicas count of segments respectively. By simulation, it is found that both algorithms performed better than FIFO and LRU in terms of initial buffer delay, movie replicas number and dependency on the root with various peers' arrival interval. In some scenarios, initial buffer delay of LSB is reduced by about 40% compared with SD while the REP has an advantage over LSB in aspect of replicas number. It is proved that the system performance could be improved when SD and REP algorithms are exploited for cache replacement in streaming media service on P2P network.