EndRE: An End-System Redundancy Elimination Service for Enterprises

EndRE: An End-System Redundancy Elimination Service for Enterprises

 

1. EndRE

- 스마트폰과 같은 자원이 제한된 클라이언트를 고려하여 설계됨

- 전산 작업이 대부분 서버에서 이루어지는 경우를 말함

- 기존 중복 제거 기법에 사용된 Rabin 알고리즘보다 더 빠른 Samplebyte로 불리는 새로운 Fingerprint 알고리즘을 사용

- EndRE는 기업에서 데이터 센터의 서버에서 클라이언트로 데이터 전송을 최적화 하기 위해 설계됨

    

2. EndRE Design

- RE모듈을 클라이언트와 원격 서버의 네트워크 스택에 도입한다.

- 서버 측 모듈은 이전 데이터의 캐쉬에 대하여 비교함으로서 중복을 확인 한다.

- 클라이언트 측 모듈은 FIFO log와 메타데이타를 디코딩 하기 위한 단순한 논리로 구성한다. 메타데이타는 클라이언트에 의해 계산된 튜플이다.

 

3. 동작

 

1) Fingerprinting

 

1.1) Fingerprinting

MODP, MAXP(Condent-based)의 Condent의 작은 변화에도 민감하게 적용되는 장점과와 FIXED(Condent-agonostic)의 효율성을 접목시킨 Samplebyte를 제안

 

 

1) SAMPLETABLE[] 미리 정의해 놓은 256-entry lookup table을 이용한다.

2) Line6에서 데이터 블록은 바이트대 바이트로 검색 된다. 바이트는 룩업 테이블의 상응하는 엔트리가 있으면 마커로 뽑힌다(Line7).

3) 마커가 선택되면 Fingerprint는 JekinsHash에 의해 계산되고, Content의 p/2 만큼 Skip된다. ( Samplebyte는 데이터 블록의 바이트가 똑 같은 내용으로 반복 될 때 oversample을 회피하기 위해 각각 마커를 선별할 때 p/2만큼 건너 뛴다)

 

1) 위 그림과 같이F(0) 과 F(5)가 256-entry lookup table에 있는 경우 이 둘은 마커로 선택된다.

2) 선택된 마커를 기준으로 w-byte만큼 잘라내어 Hash계산을 통해 Fingerprint를 만든다.

3) 이후 이후 p/2만큼 Skip하여 처리를 계속한다. (그림의 P는 4로처리 되었다.)