-A-Pull-based-Cache-Invalidation

Introduction

To simulate a simple IR-based cache invalidation model using CSIM.

• Reference paper: A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments

Getting Started

Prerequisites

• install Code::Blocks and C Programming Language
• install CSIM

System Parameters

Number of clients	100
Database size	1000 items
Data item size	1024 bytes
Broadcast interval (L)	20 seconds
Broadcast bandwidth	10000 bits/s
Cache size	50 to 300 items
Mean query generate time (T_query)	25s to 300s
Mean update arrival time (T_update)	20s to 10000s
Hot data items	1 to 50
Cold data items	remainder of DB
Hot data access probability	0.8
Hot data update probability	0.33

Simulation Model and Functions

	Main Functions	Utility Functions
Server	void update_data_items()	int is_duplicated()
	void invalidation_report()	int get_list_size()
	void receive_request()	void clear_list()
		int get_list_size()
Client	void generate_query()	int is_cached()
	void receive_ir()	lnt get_oldest_valid()
		int is_cache_full()
		int get_oldest_invalid()

Compilation & Run

csim64.gcc project.c -o project
./project

To show the simulation is running correctly in the below section, I simplify the parameters according to:

• Number of clients is 3
• Mean update arrival time (T_update) is 20s
• Mean query generate time (T_query) is 100s
• Simulation time is 50000
• Cache size is 100 items

Run Simulation

• Specify T_update and T_query.

Enter Mean update arrival time (T_update) in seconds:
20
You've entered T_update: 20
Enter Mean query generate time (T_query) in seconds:
100
You've entered T_query: 100

References

• CSIM - Official Documents
• CSIM - Michigan State University
• CSIM - University of Pittsburgh
• CSIM - The Chinese University of Hong Kong
• CSIM - U of T
• VIM Tutorial
• Computer Architecture
• Arrays in C
• Organizing information in README.md with tables
• Markdown Cheatsheet