First In First Out (FIFO)

Very simple
Remove frame which has been in the cache for the longest time
Can think of the cache as a list/queue
New frames go at front
Old frames removed from back
Don't have to store it as a list/queue
Can store however you like
Choose an efficient method