파일 다운로드 및 스트리밍 시스템 document_id A220623042149

통신 채널을 통한 송신자(sender)와 수신자(recipient)간의 파일들 및 스트림들의 전송은 많은 문헌의 주제가 되어 왔다. 바람직하게도, 수신자는, 송신자에 의해 채널을 통해 전송되는 데이터의 정확한 사본을 어느 정도의 확실성을 가지고 수신하고자 한다. 채널이 (물리적으로 실현 가능한 거의 모든 시스템들을 커버하는) 완벽한 충실도(perfect fidelity)를 갖지 않을 경우, 관심사는 전송시에 손실되거나 왜곡된 데이터를 처리하는 방법이다. 대개는 손실된 데이터(이레이져(erasure)들)가 손상된 데이터(에러들)보다 다루기가 좀더 쉬운데, 수신자가, 언제 손상된 데이터가 잘못 수신된 데이터인지를 항상 분간할 수 있는 것은 아니기 때문이다. 이레이져들 및/또는 에러들을 정정하기 위해 다수의 에러-정정 코드들이 개발되어 왔다. 통상적으로, 사용되는 특정 코드는, 데이터가 전송 중인 채널의 비충실도들 및 전송 중인 데이터의 특징에 관한 소정 정보에 기초해 선택된다. 예를 들어, 채널이 긴 충실도 주기들을 갖는 것으로 공지되어 있을 경우, 그러한 애플리케이션을 위해서는 버스트 에러 코드(burst error code)가 가장 적합할 수 있다. 빈번하지 않은 단기 에러들만이 예상될 경우에는, 간이 패리티 코드(simple parity code)가 최선일 수 있다. 전송기(transmitter)와 수신기가 통신을 위해 필요한 연산력과 전력 모두를 가지며 전송기와 수신기간의 채널이 비교적 에러가 없는 통신을 허용하기에 충분할 정도로 순수할 경우, 데이터 전송은 간단하다. 채널이 불리한 환경에 있거나 전송기 및/또는 수신기가 한정된 능력을 가질 경우, 데이터 전송 문제는 좀더 어려워진다. 한가지 해결책은 FEC(forward error correcting) 기술들을 사용하는 것인데, 이 경우, 데이터는 전송기에서, 수신기가 전송 이레이져들 및 에러들로부터 복원할 수 있도록, 코딩된다. 가능하다면, 수신기로부터 전송기로의 역방향 채널(reverse channel)이, 수신기로 하여금 에러들에 관해 전송기로 통신할 수 있게 하는데, 전송기는 그에 따라 그것의 전송 프로세스를 조정할 수 있다. 그러나, 대개는, 역방향 채널이 이용 불가능하거나 실현 불가능하다. 예를 들어, 전송기가 대다수 수신기들로 전송 중일 경우, 그러한 모든 수신기들로부터의 역방향 채널들을 전송기가 핸들링할 수 없을 수도 있다. 그 결과, 통신 프로토콜들은 대부분 역방향 채널없이 설계되어야 하고, 그에 따라, 전송기는, 그러한 채널 조건들에 대한 완전한 검토없이, 광범위하게 변하는 채널 조건들을 다루어야 할 수도 있다. 수신기들이 휴대용이거나 이동형일 수 있는 저전력의 작은 장치들이어야 하며 데이터를 높은 대역폭들에서 수신해야 할 경우, 전송기들과 수신기들간의 데이터 전송 문제는 좀더 어려워질 수 있다. 예를 들어, 수신기들이 그들의 연산력, 메모리 사이즈, 이용 가능한 전력, 안테나 사이즈, 장치 사이즈 및 다른 설계 제한 사항들에서 제약받는 경우, 정적인 전송기로부터의 파일들 또는 스트림들을 다수의 또는 불확정 갯수의 휴대용 또는 이동형 수신기로 전달하기 위한 무선 네트워크는 브로드캐스트 또는 멀티캐스트로서 설정될 수 있다. 이러한 시스템에서, 다루어져야 할 고려사항들로는 적은 또는 무 역방향 채널, 한정된 메모리, 한정된 연산 주기들, 이동성 및 타이밍을 갖는 것을 들 수 있다. 바람직하게는, 본 설계가 데이터를 잠재적인 다수 수신기들로 전달하는데 필요한 전송 시간량을 최소화해야 하는데, 여기에서, 개개 수신기들은 예측할 수 없는 시점들에서 턴온 및 턴오프될 수 있고, 범위내로 그리고 범위 밖으로 이동할 수 있으며, 링크 에러들, 셀 변화들, 더 낮은 우선 순위의 파일 또는 스트림 패킷들이 일시적으로 누락될 것을 강제하는 셀들에서의 정체 등으로 인한 손실들을 발생시킬 수 있다. 데이터 전송을 위해 패킷 프로토콜이 사용될 경우, 패킷 네트워크를 통해 전송될 데이터의 파일, 스트림 또는 다른 블록은 동일 사이즈의 입력 심볼들로 분할되고 입력 심볼들은 연속적인 패킷들에 배치된다. 입력 심볼의 "사이즈"는, 입력 심볼이 실제로 비트 스트림으로 분할되는지에 관계없이, 비트로 측정될 수 있는데, 여기에서, 입력 심볼이 2M개 심볼들의 영문자로부터 선택될 경우, 입력 심볼은 M개 비트들의 사이즈를 가진다. 이러한 패킷-기반 통신 시스템에서는, 패킷 지향형 코딩 방식이 적합할 수 있다. 네트워크에서의 이레이져들에도 불구하고, 파일 전송이, 의도된 수신자로 하여금 원래 파일의 정확한 사본을 복원할 수 있게 한다면, 그 파일 전송은 신뢰할 수 있다고 한다. 네트워크에서의 이레이져들에도 불구하고, 스트림 전송이, 의도된 수신자로 하여금 시기적절한 방식으로 스트림 각 부분의 정확한 사본을 복원할 수 있게 한다면, 그 스트림 전송은 신뢰할 수 있다고 한다. 파일 또는 스트림의 일부분들이 복원 불가능하거나, 스트리밍의 경우, 스트림의 일부분들이 시기적절한 방식으로 복원 불가능하다는 점에서, 파일 전송 및 스트림 전송 모두가 어느 정도 신뢰할 수 없을 수도 있다. 패킷 손실은 흔히 발생하는데, 단발성 정체는, 입력 패킷들을 누락할 것을 라우터에 강제하는 라우터에서의 버퍼링 메커니즘을 통해 그것의 용량을 달성하기 때문이다. 전송 동안의 이레이져들에 대한 보호가 많은 연구의 주제가 되어 왔다. 파일 또는 스트림의 입력 심볼들로부터 임의 갯수의 출력 심볼 발생을 허용하기 위해 체인 리액션 코드들을 사용하는 것이 공지되어 있다. 이것은, 정보 중복 방식이 아닌, 정보 추가 방식으로 출력 심볼들을 발생시키는 것을 포함하여, 다수 용도들을 갖는데, 여기에서, 정보 중복 방식은, 수신기가 이미 인지하고 있는 데이터를 되풀이하는 추가 데이터를 수신기가 수신하는 경우이다. 체인 리액션 코드들을 발생시키고, 사용하며, 연산하기 위한 신규한 기술들이, 예를 들어, Luby에게 허가된 "Information Additive Code Generator and Decoder for Communication Systems"라는 명칭의 미국특허 제 6,307,487호("Luby I"), "Information Additive Group Code Generator and Decoder for Communication Systems"라는 명칭으로 Luby 등에게 허가된 미국특허 제 6,320,520호(이하 "Luby II"라고 함), 및 2003년 3월 27일 "Multi-Stage Code Generator and Decoder for Communication Systems"라는 명칭으로 공개된 Shokrollahi 등에 대한 미국특허 출원공개 제 2003/0058958호("Shokrollahi"라고 함)에 설명되어 있다. 허용되는 범위에서, 그들의 전체 개시들이 참조로써 여기에 포함되어 있다. 체인 리액션 인코더에 의해 발생되는 출력 심볼들의 일 특성은, 충분한 출력 심볼들이 수신되기만 하면, 수신기가 원래 파일 또는 원래 스트림의 블록을 복원할 수 있다는 것이다. 구체적으로, 높은 확률로 원래의 K 입력 심볼들을 복원하기 위해, 수신기는 대략 K+A개 출력 심볼들이 필요하다. A/K 비를 "상대적 수신 오버헤드(relative reception overhead)"라고 한다. 상대적 수신 오버헤드는 입력 심볼들의 수(K) 및 디코더의 신뢰도에 의존한다. 예를 들어, 구체적 일 실시예에서, K가 60,000일 경우, 5%의 상대적 수신 오버헤드는, 디코더가 적어도 1-10-8의 확률로 입력 파일 또는 스트림의 블록을 성공적으로 디코딩한다는 것을 보장하고, K가 10,000일 경우에는, 15%의 상대적 수신 오버헤드가 디코더의 동일한 성공 확률을 보장한다. 일 실시예에서, 체인 리액션 코드들의 상대적 수신 오버헤드는 (13*sqrt(K)+200)/K로서 계산될 수 있는데, 여기에서, sqrt(K)는 입력 심볼들의 수(K)에 대한 제곱근이다. 이 실시예에서, 체인 리액션 코드들의 상대적 수신 오버헤드는 K의 작은 값들에 대해 더 커지는 경향이 있다. Luby I, Luby II 및 Shokrollahi는 본 발명에 따른 소정 실시예들에서 이용될 수 있는 시스템들 및 방법들에 대한 내용들을 제공한다. 그러나, 이러한 시스템들 및 방법들이 본 발명의 요구 사항인 것은 아니며, 다수의 다른 변경들, 변형들, 또는 대안들이 사용될 수도 있다는 것을 알 수 있을 것이다. Shokrollahi에서 설명되고 "Raptor" 코드들이라는 상표명으로 Digital Fountain, Inc.에 의해 개발된 것들과 같은, "MSCR"(multi-stage chain reaction) 코드들을 사용하는 것도 공지되어 있다. MSCR 코드들은, 예를 들어, 소스 파일 또는 소스 스트림으로부터 입력 심볼들을 수신하고, 그로부터 중간 심볼들을 발생시키며, 체인 리액션 코드들을 사용해 중간 심볼들을 인코딩하는 인코더에서 사용된다. 좀더 구체적으로는, 전송될 입력 심볼들의 순서화된 세트로부터 복수개의 리던던트 (redundant) 심볼들이 발생된다. 입력 심볼들 및 리던던트 심볼들을 포함하는 심볼들의 조합 세트로부터 복수개의 출력 심볼들이 발생되는데, 이 경우, 가능한 출력 심볼들의 수는 심볼들의 조합 세트에서의 심볼들의 수보다 훨씬 크고, 심볼들의 조합 세트에서의 하나 이상의 심볼로부터 그러나 심볼들의 조합 세트에서의 모든 심볼들은 아닌 심볼들로부터, 그리고 입력 심볼들의 순서화된 세트가 소정 임의 갯수(N)의 출력 심볼들로부터 원하는 정확도로 재생될 수 있도록, 하나 이상의 출력 심볼이 발생된다. 일부 애플리케이션들을 위해서는, 코드들의 다른 변형들이 좀더 적합하거나 바람직할 수도 있다.