Peer-to-Peer (P2P) approaches are gaining increasing popularity for video streaming applications due to their potential for Internet-level scalability. P2P VoD (Video On-Demand) applications pose more technical challenges than P2P live streaming since the peers are less synchronized over time as the playing position varies widely across the total video length along with the requirement to support VCR operations such as random seek, Fast-Forward and Backward (FF/FB). We propose COCONET in this paper, which uses a distributed cache partly contributed by each participant thereby achieving a random content distribution pattern independent of the playing position. It also achieves an O(1) search efficiency for any random seek and FF/FB operation to any video segment across the total video stream with very low maintenance cost through any streaming overlay size. Performance evaluation by simulation indicates the effectiveness of COCONET to support our claim.