串流分享方法、串流分享装置与串流分享系统

技术领域

本发明关于对等网络（peer-to-peer network），特别关于对等网络上分享串流的方法、装置与系统。 

背景技术

传统的主从（client-server）架构伸缩性（scalability）不足，递送内容时只要用户一多便容易在伺服端形成瓶颈。在网际网络基础建设尚未普遍实作多播（multicast）的现况下，理论上可达到更大通量的对等网络俨然已成为即时串流分享的首选技术。 

用以提供串流服务的对等网络一般而言包括众多节点（node或peer），向彼此或某个内容源以区段（segment）为单位下载数据，并（在被要求时）上传给其他节点。具体而言，每个节点维护着一个排程窗（scheduling window），随着串流的各区段持续地被下载、处理（如影音串流的讯框［frame］被播放出来）和丢弃（或被移出下载数据的暂存区），排程窗会不停前移，指示节点需向外请求的区段。可惜的是，实务上节点常采取简单的贪婪策略，盲目加大自己的排程窗，以涵盖更即时的区段，并锁定某个节点抓取所有所需数据。整体而言这反而造成少数节点（通常是内容源）负荷过大、甚至网络陷入瘫痪的公地悲剧（tragedy of the commons），无异于主从架构固有的不效率。 

发明内容

本发明旨在提供一种串流分享方法、一种串流分享装置以及一种串流分享系统。 

为达到上述目的，本发明提供一种串流分享方法，包含：依据第一排程窗，开始接收串流；将串流的多个已接收区段储存至缓冲（buffer）模块，每一已接收区段对应一个接收时点；接收一分享请求，其包含第二排程窗；依据第二排程窗，传送一或多个被要求区段，每一被要求区段系该些已接收区段其中之 一且更对应一个传送时点；以及依据各被要求区段分别对应的接收和传送时点，选择性地调整前述第一排程窗，以持续接收串流。 

上述的串流分享方法，其中依据每一该被要求区段对应的该接收时点和该传送时点选择性地调整该第一排程窗的步骤包含：计算每一该被要求区段对应的该传送时点和该接收时点的一差值；依据该或该些差值，更新一平均值；以及依据该平均值，选择性地调整该第一排程窗。 

上述的串流分享方法，其中于依据该平均值选择性地调整该第一排程窗的步骤中，当该平均值小于一预设下限时，选择性地加大该第一排程窗，且当该平均值大于一预设上限时，选择性地减小该第一排程窗。 

上述的串流分享方法，其中于依据该平均值选择性地调整该第一排程窗的步骤中，当该平均值小于该预设下限且该第一排程窗小于一最大尺寸时，加大该第一排程窗，且当该平均值大于该预设上限且该第一排程窗大于一最小尺寸时，减小该第一排程窗。 

上述的串流分享方法，其中于依据该平均值选择性地调整该第一排程窗的步骤中，当该平均值不小于该预设下限且不大于该预设上限时，或当该平均值小于该预设下限且该第一排程窗已达该最大尺寸时，或当该平均值大于该预设上限且该第一排程窗已达该最小尺寸时，维持该第一排程窗。 

上述的串流分享方法，其中该平均值具有一初始值，该初始值关联于该缓冲模块的大小。 

为达到上述目的，本发明还提供一种串流分享装置，包含缓冲模块、分享模块和调整模块。分享模块用以依据第一排程窗，开始接收串流；用以将串流的多个已接收区段储存至缓冲模块，每一已接收区段对应一个接收时点；用以接收一分享请求，其包含第二排程窗；以及用以依据第二排程窗，传送一或多个被要求区段，每一被要求区段为该些已接收区段其中之一且更对应一个传送时点。调整模块用以依据各被要求区段分别对应的接收和传送时点，选择性地调整前述第一排程窗，以供分享模块持续接收串流。 

上述的串流分享装置，其中该调整模块用以依据每一该被要求区段对应的该接收时点和该传送时点选择性地调整该第一排程窗用以计算每一该被要求区段对应的该传送时点和该接收时点的一差值，用以依据该或该些差值，更新一平均值，以及用以依据该平均值，选择性地调整该第一排程窗。 

上述的串流分享装置，其中该调整模块用以依据该平均值选择性地调整该第一排程窗用以当该平均值小于一预设下限时，选择性地加大该第一排程窗，且用以当该平均值大于一预设上限时，选择性地减小该第一排程窗。 

上述的串流分享装置，其中当该平均值小于一预设下限且该第一排程窗小于一最大尺寸时，该调整模块加大该第一排程窗，且当该平均值大于一预设上限且该第一排程窗大于一最小尺寸时，该调整模块减小该第一排程窗。 

上述的串流分享装置，其中当该平均值不小于该预设下限且不大于该预设上限时，或当该平均值小于该预设下限且该第一排程窗已达该最大尺寸时，或当该平均值大于该预设上限且该第一排程窗已达该最小尺寸时，该调整模块维持该第一排程窗。 

上述的串流分享装置，其中该平均值具有一初始值，该初始值关联于该缓冲模块的大小。 

为达到上述目的，本发明还提供一种串流分享系统，包含用以播送串流的串流源装置和至少一个串流分享装置。串流分享装置包含缓冲模块、分享模块和调整模块。分享模块用以依据第一排程窗，开始接收串流；用以将串流的多个已接收区段储存至缓冲模块，每一已接收区段对应一个接收时点；用以接收一分享请求，其包含第二排程窗；以及用以依据第二排程窗，传送一或多个被要求区段，每一被要求区段为该些已接收区段其中之一且更对应一个传送时点。调整模块用以依据各被要求区段分别对应的接收和传送时点，选择性地调整前述第一排程窗，以供分享模块持续接收串流。 

上述的串流分享系统，其中该调整模块用以依据每一该被要求区段对应的该接收时点和该传送时点选择性地调整该第一排程窗用以计算每一该被要求区段对应的该传送时点和该接收时点的一差值，用以依据该或该些差值，更新一平均值，以及用以依据该平均值，选择性地调整该第一排程窗。 

上述的串流分享系统，其中该调整模块用以依据该平均值选择性地调整该第一排程窗用以当该平均值小于一预设下限时，选择性地加大该第一排程窗，且用以当该平均值大于一预设上限时，选择性地减小该第一排程窗。 

上述的串流分享系统，其中当该平均值小于一预设下限且该第一排程窗小于一最大尺寸时，该调整模块加大该第一排程窗，且当该平均值大于一预设上限且该第一排程窗大于一最小尺寸时，该调整模块减小该第一排程窗。 

上述的串流分享系统，其中当该平均值不小于该预设下限且不大于该预设上限时，或当该平均值小于该预设下限且该第一排程窗已达该最大尺寸时，或当该平均值大于该预设上限且该第一排程窗已达该最小尺寸时，该调整模块维持该第一排程窗。 

上述的串流分享系统，其中该平均值具有一初始值，该初始值关联于该缓冲模块的大小。 

以上之关于本发明内容之说明及以下之实施方式之说明用以示范与解释本发明之精神与原理，并且提供本发明之专利申请范围更进一步之解释。 

附图说明

图1为依据本发明一实施例串流分享系统与串流分享装置的高阶方块图； 

图2为依据本发明一实施例串流分享方法的流程图； 

图3A至图3C、图4A至图4B、图5A至图5B均为依据本发明一实施例两个串流分享装置与串流源装置间分享区段的示意图； 

图6为依据本发明一实施例选择性地调整第一排程窗的部分流程图 

其中，附图标记： 

10 串流源装置                 12、14 串流分享装置 

101a、121a、141a 缓冲模块     123a 分享模块 

125a 调整模块                 2 网络 

具体实施方式

以下在实施方式中详细叙述本发明之详细特征以及优点，其内容足以使任何本领域技术人员了解本发明的技术内容并据以实施，且依据本说明书所发明的内容、申请专利范围及附图，任何本领域技术人员可轻易地理解本发明相关的目的及优点。以下的实施例进一步详细说明本发明的观点，但非以任何观点限制本发明的范畴。 

请参见图1。图1为依据本发明一实施例串流分享系统与串流分享装置的高阶方块图。如图1所示，一个简化的串流分享系统由串流源装置10和串流分享装置12、14组成，彼此通过网络2通讯。串流分享装置12和14可能是个人电脑、 平板电脑或移动电话等任何运算设备。实务上，串流分享系统可以有多个串流源装置和更多的串流分享装置，而这些串流分享装置间的对等网络覆盖（overlaid）于网络2上。网络2可以是区域网络（local area network）、广域网络（wide area network）或两者的混成，且不限于有线或无线的实体链结。对于串流分享装置来说，无论它们通过对等网络从何节点接收串流，最终都可以追溯到某个串流源装置。值得一提的是，在图1的例子中，真正产生串流的不一定是串流源装置10，而可能是通过网络2或实体耦接串流源装置10的摄影机、录音设备、屏幕撷取软件或多媒体数据库等等。在此情形下，串流源装置10扮演对等网络中追踪器（tracker）、种子（seed）和／或中继节点（relay）的角色，或为前述串流产生者提供内容递送（content delivery）或反向代理（reverse proxy）服务。 

以串流分享装置12为例，一个串流分享装置会包含缓冲模块121a、分享模块123a和调整模块125a，其分别的功能请参见图2。在图2串流分享方法的实施例中，串流分享装置12记录有一个第一排程窗，调整模块125a有权修改此数据结构，但分享模块123a只有权读取其值。于步骤S21中，分享模块123a依据第一排程窗，开始接收串流。此处假设由于某种对等选择（peer selection）机制，串流为接收自串流源装置10。于步骤S23中，分享模块123a将串流的多个区段储存至缓冲模块121a，同时记录接收每个区段的时点。在持续地接收串流（步骤S21）、记录区段接收时点和储存区段（步骤S23）期间，分享模块123a可能会于步骤S25中接收到来自串流分享装置14的分享请求，其中包含串流分享装置14所记录的第二排程窗。于步骤S27中，分享模块123a依据此第二排程窗的要求，传送前述已接收的区段中的一或多个，同时记录传送这些被要求的区段的时点。换句话说，串流分享装置14的分享模块依据第二排程窗，开始自串流分享装置12接收串流。于步骤S29中，调整模块125a依据传送给串流分享装置14的各区段分别对应的接收和传送时点，选择性地调整第一排程窗，而分享模块123a继续于步骤S21中，依据（调整后的）第一排程窗自串流源装置10接收串流。 

上述串流分享方法的详细说明请参见图3A至图5B。承前例，如图3A所示，在时间t=0时串流源装置10的缓冲模块101a储存有已经在进行的串流的多个区段，分别标号为21至35。此处假设每个区段对应1单位时间。串流分享装置12 的分享模块123a（开始）执行步骤S21和S23；由于这是从串流源装置10到串流分享装置12就此串流的初次递送，和第一排程窗等长（7单位时间）的多个区段（标号24至30）从缓冲模块101a被批次（batch）传送至缓冲模块121a。第一排程窗也可以确切地包含串流分享装置12要求的区段标号（如24至30），并随时间滑动，如图3B所示在t=1时串流分享装置12的前接收的七个区段在其处理队列里被往前推，第一排程窗现在指示缓冲模块121a中应有标号25至31的区段，其中分享模块123a只需要再和串流源装置10要求最后一个区段即可（或等待串流源装置10自动传送）。以此类推，只要对等网络没有变化，如新的节点加入并要求和递送此串流，每一单位时间第一排程窗都会往后滑动，一个新的区段从缓冲模块101a被传送而储存至缓冲模块121a，如在t=60时串流分享装置12接收标号为90的区段。 

假设串流分享装置12的调整模块125a周期性地每60单位时间执行一次步骤S29。由于t=0和t=60之间串流分享装置12没有上传任何的区段，其处理过的区段（标号24至90）皆未被记录有传送时点。在一实施例中，没有被要求或被分享的区段的传送时点可视为其最终离开缓冲模块的时点，也就是说这样的区段对应的传送和接收时点的差便是其停留于缓冲模块中的时间。在第3A和3B图的例子中，标号24的区段会在t=9时被挤出，以留出储存空间给新进的标号39的区段；由于标号24的区段是t=0时存入，调整模块125a计算其在缓冲模块121a停留了9单位时间。同样地，标号31至75的区段到目前为止都没有被串流分享装置14要求，且已离开缓冲模块121a进行后续处理或被丢弃，因此在缓冲模块121a中分别都停留了15单位时间。（这里假设缓冲模块101a、121a和下述的141a皆恰可存放十五个区段，而每个区段对应一单位时间。） 

由此可知，若假设了未被要求区段的传送时点，等同于假设了到目前为止这些区段分别对应的传送和接收时点的差和缓冲模块121a的大小有关，或者这些差值的平均等于缓冲模块121a能储存多少单位时间的数据，无论取多少个区段或给予它们怎样的权重。在t=61前，调整模块125a便观察到这个平均是15单位时间。在一实施例中，调整模块125a在这个平均高于某个上限时会着手缩短第一排程窗。假设取缓冲模块121a的大小的三分之二为上限（10单位时间），如图3C所示，在t=61时，第一排程窗已被减小了一个区段或1单位时间，因此串流分享装置12一时并没有需自串流源装置10取得的区段。实务上，每次排程 窗的调整不一定要是一个定值，或一定是串流的最小单位。举例而言，调整的量可以和前述平均超过上限或低于下限的程度呈比例关系。就对等网络的负载而言，高的平均代表节点网络状态不佳或有较多限制（如上传频宽被管控或防火墙阻挡外来连线），在对等选择上顺位较低而较不常分享区段，因此超过上限愈多，可被缩短（愈多的）第一排程窗，增加节点得到串流中最新数据的难度。 

从图3C中缓冲模块141a的存在，可以发现串流分享装置14也通过某种对等选择机制开始向串流分享装置12要求串流。如同图3A中的情形，和第二排程窗等长（七单位时间）的多个区段（标号84至90）从缓冲模块121a被批次传送至缓冲模块141a。从此时点t=61开始调整模块125a可较有意义地计算缓冲模块121a中区段分别对应的传送和接收时点差并时时更新这些时点差的平均。举例而言，由于标号90的区段是在t=60时被载入至缓冲模块121a，调整模块125a计算其传送和接收时点差为1，同理t=59时被载入的标号89的区段其传送和接收时点差为2，以此类推，而标号84的区段的时点差则为7。调整模块125a可只取迄今被要求的区段计算上述平均为单位时间，或取缓冲模块121a中尚存的所有区段计算出单位时间的算术平均，或给予自近至远被要求的区段或尚存所有区段渐减的权重以计算加权平均等等，方式不一而足。在图3C和后续的说明中，假设调整模块125a取迄今被要求的区段计算算术平均，因此t=63时，如图4A所示，标号84至92的区段是被分享过的，其中标号91和92的区段分别于t=62和t=63被分享模块123a接收并传送至串流分享装置14（时间差皆为0），使平均等于 单位时间。（当串流分享装置14从串流分享装置12接收了一段时间的串流后，显然缓冲模块121a中全部都会是被要求过的区段。） 

请注意前文中已假设调整模块125a每60单位时间调整一次第一排程窗，因此虽然平均已小于10单位时间的上限，t=63时第一排程窗仍是缩减的长度，但到了t=121前步骤S29会再次执行。在一实施例中，调整模块125a在平均低于某 个下限时会着手延长第一排程窗。假设取缓冲模块121a的大小的三分之一为下限（5单位时间），如图4B所示，在t=121时，平均已降至0单位时间（分享模块123a接收区段后立即传送），第一排程窗因此加大了一个区段或1单位时间，恢复成t=0时的7单位时间，使串流分享装置12批次自串流源装置10取得标号为150和151的区段。就对等网络的负载而言，低的平均代表节点网络状态良好，在对等选择上顺位较高而较常分享区段，因此低于下限愈多，可被延长（愈多的）第一排程窗，增加节点得到串流中最新数据的机会。类似串流分享装置12在图3C中的情形，由于迄今串流分享装置14未有任何分享（或缓冲模块141a中区段分别对应的传送和接收时点差的平均固定在15单位时间），其调整模块减小了第二排程窗，串流分享装置14一时不需自串流分享装置12接收区段。 

请配合图3C参见图5A。假设在t=62时，与第4A和4B图的情形不同，对等选择机制决定让串流源装置10直接传送数据给串流分享装置14，而串流分享装置12改自串流分享装置14接收此后的区段，因此标号91的区段自经过缓冲模块141a从缓冲模块101a被载入缓冲模块121a。这可能是因为串流分享装置14的网络状态变得较串流分享装置12为佳，譬如t=62时实作串流分享装置12的运算设备启动了某种大量耗用频宽或运算资源的程序。在t=121前缓冲模块121a中区段分别对应的传送和接收时点差的平均仍为关联于缓冲模块121a大小的大于上限的15单位时间（尽管在t=61时分享模块123a传送了七个区段），因此在图5B中可发现调整模块125a再度减小了第一排程窗。另一方面，串流分享装置14从t=62至121不停分享区段给串流分享装置12，因此第二排程窗得以被加大至8单位时间，且如同图4B中的情形，两个区段被批次载入缓冲模块141a。 

在一实施例中，排程窗无法无止境地被延长或缩短。显然在缓冲模块的大小有限或不可变的条件下，排程窗过大是没有意义的。观察图3A至图3C、图4A至图4B或图5A至图5B，可发现参与分享的串流分享装置的排程窗会愈来愈大，而被动接收的串流分享装置的排程窗会愈来愈小。换句话说，被动接收的串流分享装置会将参与分享者的缓冲进度推得愈来愈接近串流源装置10持有的串流进度，参与分享者的缓冲模块会愈来愈和缓冲模块101a平行。实务上，过小的排程窗会使串流体验恶化，缩短的同时发生影音播放中俗称的lag（落后）现象，因此排程窗的尺寸也应该有一个最小值。 

具体而言，在一实施例中，图2中的步骤S29包含如图6所示的流程。调整 模块125a在求得缓冲模块121a中区段分别对应的传送和接收时点差的平均后，于步骤S601和S603中判断平均是否小于前述下限或大于前述上限。若平均在上下限之间，则调整模块125a于步骤S605中单纯维持原来的第一排程窗尺寸。若小于下限，且调整模块125a更于步骤S607中判断第一排程窗尚未达某个最大尺寸，则于步骤S609中加大第一排程窗。若大于上限，且调整模块125a更于步骤S611中判断第一排程窗尚未达某个最小尺寸，则于步骤S613中减小第一排程窗。若于步骤S607或S611中第一排程窗已达最大或最小尺寸，则调整模块125a执行步骤S605。 

本发明的实施例具有多种样态，举凡串流源装置的数量、串流分享装置的数量、区段对应时间长短、各装置缓冲模块的大小、排程窗的表达方式、预设的排程窗长度和极值、差值的取用、差的平均值的计算方式（包括是否加权以及权重如何分配）、和平均值比较的上下限和每次调整排程窗的量等等，凡本领域技术人员应可轻易变化与设计。举例而言，当一个串流分享装置同时分享给多个其他串流分享装置时，其缓冲模块中某个区段可能对应多个传送时点，则其调整模块可以取用这些传送时点中最早的一个，或这些传送时点的某种平均值或中位数。 

综上所述，本发明的实施例中作为节点的串流分享装置依据所拥有区段的出入时间，独立（但间接地）衡量自身的网络状态，以在有所上传时加大排程窗，贴近串流源的进度，成为更适合分享的节点，或在无法分享或上传不顺利时缩小排程窗较保守地抓取，减少占用上游资源，并增加对等所拥有区段相对自己的可用性。排程窗加大或减小的具体实施方式有多种变化。总而言之，本发明旨在通过调整排程窗在提供串流服务的对等网络中鼓励分享并限制表现被动的节点，进而平衡整体对等网络的负载，且因为调整为自适性，对网络不会带来额外的运作成本（overhead），如控制封包的量。