수다닷컴

p2p 네트워크 구성을 위한 chord 프로토콜 시뮬레이터 구현
1. 개요
∙문제
서버나 트래커를 사용하지 않는 dht(distributed hash table) 프
로토콜인 chord 기반 p2p(peer-to-peer) 네트워크를 구성하고 원하
는 파일의 위치를 검색하여 가져오는 과정을 보여주는 시뮬레이션 프
로그램을 주어진 요구사항을 만족시키도록 구현하시오.
∙요구사항
1. key space는 자유롭게 줄 수 있도록 할 것
2. 각 노드와 파일은 각각 ip 주소와 파일명으로 식별하고 노드 id와
key를 생성하는 간단한 해싱 함수 사용할 것(해싱함수 제공). 단, 충
돌이 발생할 경우 다른 값으로 재생성할 것.
3. 최초 노드와 파일의 배치는 생성 개수를 입력 받아 랜덤하게 자동
생성할 것. 단, 노드는 ipv4 주소를 랜덤하게 부여하고(충돌시 재부
여), 파일명은 “f1”, “f2”, ... 와 같이 부여할 것.
4. 시뮬레이션은 다음의 단계로 진행되도록 할 것. 단, 1~2) 항은 시뮬
레이션 초기에 수행하고 3~5) 항은 이후 선택하여 수행하도록 할 것
1) 초기 노드 및 파일 생성 : 자동 생성
2) chord 테이블 및 파일 위치 정보 구성
3) 원하는 파일 찾기
4) 노드의 추가 및 삭제
5) 파일의 추가 및 삭제
∙참고자료
- 컴퓨터네트워크 교재 2.3.4 절 chord 설명 및 알고리즘
∙제공자료
1. 자료 구조 및 함수 프로토타입
2. 자료 함수(해싱함수, 모듈연산 함수 등)
3. 예시화면
2. 과제 고찰
∙데이터가 존재하는 서버에 클라이언트가 접속하는 방식인 client-server
기반 프로토콜이 서버에 부하가 집중되고 높은 서버관리 비용이 드는 반
면, peer-to-peer protocol은 데이터가 각 피어들에게 분산되므로 서버
의 부담이 없고 확장성이 높지만 원하는 데이터가 어느 피어에 위치하는
지 알기 어렵다는 단점을 가진다.
∙peer-to-peer 네트워크는 각 데이터의 위치정보를 관리하는 방법에 따라
다음과 같이 분류할 수 있다.
- centralized 네트워크: 위치정보를 저장하는 별도 서버를 둔다(hybrid
방식).
- decentralized 네트워크: 위치정보를 저장하는 별도 서버가 없다.
① unstructured 네트워크: 각 피어에도 위치정보가 없다. 랜덤한 방
식으로 데이터를 찾아야 하므로 확장성 문제를 갖는다.
② structured 네트워크: 데이터의 위치정보가 각 피어에 나뉘어 분산
되어있다. 이 분산된 정보를 distributed hash table(dht)이라고
한다. 각 피어들은 dht에 의해 구조적으로 연결된 상태로 볼 수 있
으며 이 연결정보를 통해 원하는 데이터(의 위치)를 찾아간다.
∙dht 방식의 p2p 프로토콜에는 chord, pastry, kademila 등이 있다.
∙dht 기반 네트워크는 2m의 주소공간을 가지며(m=주소비트수), 각 노드와
데이터(파일)은 이 주소공간 상에 각각 id와 key값을 갖는다. 노드의 id
와 파일의 key는 각각 자신의 ip 주소와 파일명으로부터 해싱함수을 통해
얻는다.
∙각 파일의 위치정보(reference)는 파일의 key 값과 동일한 id를 갖는 노
드가 존재할 경우 그 노드에 그렇지 않을 경우 파일의 key 값으로부터 반
시계방향으로 가장 가까운 거리에 위치하는 노드, 즉 key 값보다 처음으
로 커지는 id를 갖는 노드(successor)에 저장된다(다음 페이지 그림 참
조).
∙특정 key를 갖는 파일의 위치정보를 갖는 노드 찾기 함수 (lookup(key)).
(범위를 나타내는 (), [] 기호를 주의할 것)
∙최조 네트워크 구성 시 첫 번째 핑거(finger[1])를 제외한 다른 핑거값을
설정할 때 또는 주기적으로 핑거 테이블을 교정할 때 사용하는 함수:
fix_finger()
∙id가 n인 노드가 id가 x인 노드의 도움을 받아 네트워크에 가입할 때 사
용하는 함수: join(x)
∙어떤 노드가 네트워크에 가입하거나 탈퇴할 때 그 노드 및(또는) 주변 노
드의 predecessor와 successor를 정확히 재설정하여 기본 네트워크를
구성하도록 만들어주는 함수: stabilize() (즉, 이 함수는 pre와 finger[1]
을 설정하기 위한 함수이며 나머지 핑거(finger[2]~finger[m])를 설정하기
위해서는 fix_finger() 함수를 이용한다.)
(3) 예시화면
- 노드와 파일의 자동생성 및 id/key 부여
- 자동생성된 노드가 각각 join할 때 finger table 확인
4. 참고 사항
(1) 예시화면과 같이 자동 생성된 노드의 핑거테이블 생성시 join을 이용하
는 게 좋다.
(2) 주어진 자료구조와 함수 프로토타입은 참고용으로 필요시 변경하여 사용
할 수 있다.
(3) ip 주소 자동 생성 시 또는 해싱함수에 의한 id/key 생성 시 기존 값과
충돌할 경우 새로운 값을 부여될 때까지 생성과정을 반복한다.
(4) 각 함수의 정확한 구현을 위해 각 단계에서 printf() 함수 등을 이용한
중간 값 확인을 적극 활용한다.
(5) 노드의 join과 leave 시 chord 네트워크의 재구성을 위해 stabilize()
함수와 fix_finger() 함수를 연속하여 사용한다.
(6) 보다 효과적인 시각적 효과를 위해 윈도우프로그래밍을 이용할 수 있다.첨부파일을 보시면 제가 짜놓은 몇개의 틀과 코드가 있는데..
대체 어떻게 해야할지 모르겠습니다.
씨언어로만 짜서 제출할려고 하는데ㅠㅠ
수다님들 제발 도와주십쇼...

신청하기