뭔가 내가 아는게 부족하기도 하고, 좀 제대로 알 필요가 생겨서 GPG 3권부터 시작해서 논문과 아티클을 훑어보는 중. 그 작업 중 일부로 읽었던 논문을 간략히 소개하겠다. ((INFOCOM 2001 논문은 웹 상으로 공개되어 있으며 IEEE/ACM Trans. on Net. 2007년 2월 분량은 ACM portal (유료 혹은 가입된 곳에서 사용 가능) 에서 볼 수 있다))
원제로
N. Baughman, M. Liberatore and B. Levine, “Cheat-Proof Playout for Centralized and Peer-to-Peer Gaming,” Feb. 2007, IEEE/ACM Transactions on Networking
실제로는 2001년 INFOCOM에도 냈던 논문의 연장선인데 ((참고로 IEEE/ACM Transcactions on Networking은 네트웍 쪽 최고의 저널, INFOCOM은 거의 저널급(..) 논문들이 자주나오는 상당히 급수가 높은(…) 컨퍼런스다. 무슨 컨퍼런스 페이퍼가 11장이야 Orz)) , 다루는 내용은 크게 세가지.
현존하는 동기화 방식의 문제
흔히 사용하게 되는 lock-step (frame-locking)과 bucket syncrhonization에 대해서 초점을 맞추고 얘기하고 있다.
락스텝 동기화의 경우 기본적으로,
- 프레임이 시작
- 개별 사용자가 프레임 패킷을 전송
- 모든 사용자의 프레임 패킷이 도착하면 새 프레임 시작
이라는 구존데, 특정 사용자가 2를 하지 않고 버티다가 다른 모든 사용자의 프레임 패킷을 받고 , 그걸 토대로 자신이 유리하게 움직이는 look-ahead 치팅이 가능해진다. (대신 버킷 동기화의 치팅은 피할 수 있다)
반대로 버킷 동기화의 경우
- 버킷의 시작
- 버킷 시간 동안(고정 길이 혹은 가변 길이) 패킷을 받는다
- 버킷 끝에서 받은 동작들을 수행
이런 식으로 도는데, 필연적으로(..) 데드 리커닝이 필요하고, 이를 속이는 치팅 — 업데이트 패킷을 안보내고 버티다가 자신이 유리해지게 조작하고 보내는 것 — 이 가능해진다.
치팅이 불가능한 동기화와 증명
치팅이 불가능하다는 동기화 방법으로 2-phase로 동작하는 lock-step을 제시한다.
- Phase 1 – frame packet의 1-way hash 함수 버젼을 보낸다 ((해슁된 값을 전송한단 소리. collision을 계산할 만큼 시간이 없으니 md5나 그 이전 variant들을 써도 될듯))
- Phase 2 – 실제로 frame packet 전송
각각의 phase에 대해서 lock-step 동기화가 이루어지면 2에서 보내는 패킷을 속이는 — 즉 다른 사람 패킷을 보고 행동을 취하는 — 행위가 불가능해진다는 것
성능 평가
사실 저 방법은 딜레이가 커지기 때문에, 저자는 월드 전체를 쪼개고 — MMORPG에서 흔히 취하는 셀 방식 — 각각의 셀에 대해 근처에 다른 유저가 있을 때만 2-phased lock-step을 쓰자! 라는 것 + 비동기 lock-step이라고 저자가 부르는 일종의 분산 clock을 쓰는 방식에 대한 제안과 시뮬레이션.
물론 성능이야 조금 올라가겠지. -_-;; 그렇지만 기본적으로 성능이 떨어질 다수의 사용자가 있는 상황에서는 비동기 클락이 큰 의미가 없기 쉽상이고, 그 상황에서 평균치도 아니고 제일 느린 사용자에 끌려갈 수 밖에 없는 lock-step이란건 -_-;;
논문 전체에 대한 내 평가는,
- 동기화 방법을 정리하고, 각각의 취약점을 설명해준 것은 좋다
- 2-phased lock-step 자체도 의미는 있다 — 치팅을 피하는 것
- 하지만 기본적으로 딜레이가 커지는 lock-step의 문제가 2배로 커진다
- 셀로 쪼개고 비동기 lock-step을 해도 근처에 있는 사람 중 가장 딜레이가 큰 사용자의 딜레이에 영향을 받고, 그 영향이 2배가 된다
라는 점 때문에, 높은 점수를 주기는 좀 힘들었다. 뭐 일단은 제목가 저널에 낚였으니 -_-a
그리고 상대적으로 널리 쓰이는 방법 중 하나인 event-locking에 대한 소개가 없는 것도 좀 감점(…). 근데 이 방법은 시간 속이기라는 잘 알려진 치팅이 있긴하니까…
여튼 동기화 방식 최근에 정리하면서 느낀건 세상엔 쉬운일이 없다…
이런 문제점도 있었네요. 재밌네요. 참고로 미국에선 저널에 논문을 바로 내는 경우는 적어도 제가 알고 있는 컴아키, 네트웍, OS, SE에서는 거의 없습니다. 대부분 탑 컨퍼런스에 일단 내요. 왜냐면 컨퍼런스는 아시다시피 굉장이 빠르게 돌아가니까 빨리빨리 자신의 아이디어를 내다팔죠. 그런 뒤에 extended work 형식으로 탑 저널 TOC 그런데다 내는 것 같습니다. 미국 CS 교수들은 한국과 달리 저널에는 많은 신경을 안 써요. 저널은 너무 시간이 오래 걸리니 별로 안 좋아하죠.
그래서 인포컴, 모비컴, 시그컴이 저널급 논문이라고 말하기는 그렇고 원래 거기는 엄청난 탑 컨퍼런스니까 (합격률이 20% 미만) 품질이 상당히 좋죠. 컨퍼런스 페이지가 11페이지인건 시스템, 아키 경우에는 일반적입니다. 보통 12페이지입니다. AI/비전 쪽은 6페이지로 작지만 보통 컨퍼런스들은 10 페이지가 충분히 넘죠. SOSP/OSDI는 14페이지가 보통인 것 같구요. 그 만큼 big work를 요구하죠.
미국 CS 대학원은 거의 탑 컨퍼런스 데드라인에 맞춰 돌아간다고 봐도 됩니다. 보통 분야마다 다르겠지만 한 해에 탑 컨퍼런스가 2~4개는 열리고 기간도 잘 배분이 되어있어서 떨어지면 다시 리싸이클해서 살리고 살리고… 그렇죠. 우리나라는 참 희한하게 SCI 어쩌고 그런데 여기서 SCI 이야기는 단 한 번도 들어본 적이 없어요. 얼마나 탑컨퍼런스에 논문 많이 냈냐 또 얼마나 임팩트가 있었냐가 훌륭한 리서처를 구분하는 기준이지 뭐 SCI 급 논문 몇 편… 이건 도통 이해가 불가능한 기준인 듯.
뭐 그렇긴한데, IEEE/ACM Transactions on Networking쯤 되면 대부분 논문 질이 매우 좋아서(…).
그리고 네트웍/통신 쪽은 컨퍼런스 페이퍼가 보통 6페이지 전후인데 인포콤만 좀 길게 허용하더라고요 -_-a
시그컴이나 보통 탑 컨퍼런스는 보통 12페이지입니다. 그래서 6페이지가 오히려 좀 짧은 것 같습니다. AI/비전 (AAAI, CVPR 같은..) 쪽은 6페이지이긴 한데 제가 아는 다른 컨퍼런스들은 주로 12페이지 정도입니다. 그래서 인포컴이 특별히 긴 건 아닙니다. 어쨌든 TOx에 올라오는 논문들 중 대부분은 다 컨퍼런스에 나왔던 것을 확장시켜서 내죠. 그러니 TOC나 TON은 당연히 좋을 수 밖에 없습니다. 그리고 거기보다 더 좋은 저널이 없잖아요 ㅎㅎ
암호학 수업 들었을 때 들었던 아이디어랑 비슷하네요. hash function이 아니라 역을 구하기 힘든 1:1 function을 이용하는 거였는데 …
object / 대학원 시절엔 통신쪽만 봐서(전공이;;; ) 다른 컨퍼런스는 잘 몰랐습니다;; 근데 컴퓨터 이론 하고 있는 애한테 물어보니 걔네는 사실상 제한이 없다네요(…).
TOC, TON 보다 좋은 저널이 있기는…좀 힘들죠. 원래 이름이 짧고(…) 그게 분야 이름이면 /먼산
피앙 / 거의 같은 아이디어 아닐까; 그냥 제한된 시간 (lock-step의 일반적인 간격) 안에만 못 풀면 그만이니까
락스텝/버킷 쓰는 경우가 전체 온라인 게임에서 그리 많은 비율을 차지하지 않을 것 같고, look-ahead 치팅이 심각한 문제가 되는 경우도 상상하기 힘들군. 구체적으로 어떤 케이스에서 그런 치팅이 문제가 되는지도 논문에 나와 있어?
논문에는 적당적당한 케이스만 나오고 FPS 정도의 업데이트 단위가 아니면 실제적으로 치팅으로 이득을 보긴 힘들듯…
어차피 MMORPG에 가까워지면 락스텝보다는 event-locking에 가까운걸 쓰니.
[…] 논문 읽기: C/S 혹은 P2P 구조에서 치팅을 막는 동기화 방법 […]