分布式系统中的通信.pptx

该【分布式系统中的通信 】是由【小屁孩】上传分享，文档一共【66】页，该文档可以免费在线阅读，需要了解更多关于【分布式系统中的通信 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第三章分布式系统中的通信§●发送策略固定策略虚拟线路策略动态发送策略固定策略简单,但不顾及网络负载;虚拟策略对此有所改进,亦能保证消息发送与到达次序一致,但不能最大限度利用带宽;动态策略可充分利用带宽,但不能严格保证消息发送与到达次序一致。2021/10/101第三章分布式系统中的通信●连接策略线路转换:永久物理链路,固定独占使用消息转换:物理链路动态分配,临时共享使用信包转换:物理链路与信包捆绑,消息拆分传输●冲突解决策略冲突检测令牌传递消息槽●保密单密钥技术公公密钥技术2021/10/102第三章分布式系统中的通信§●逻辑时钟:一个单调增长的计数器记号:顺序ab;并发a‖b;进程p的逻辑时钟记为Cp事件a在进程P中的时间邮戳为Cp(a),事件x在任何进程中的时间邮戳记为C(x),ab则C(a)<C(b)2021/10/103第三章分布式系统中的通信★Lamport时钟校正方法通过在本地物理时间上加上一个偏移量来实现进程本地逻辑时钟,进程按以下方式更新其逻辑时钟并在进程件传递逻辑时钟的值:■Cp在进程P上的每一事件之前增值并加盖邮戳:Cp=Cp+1;■当进程P发送消息m时,在m上携带逻辑时钟值t=Cp■当进程Q接收消息(m,t)时,计算Cq=max(Cq,t)+12021/10/104第三章分布式系统中的通信[例]三个备有自己不同频率物理时钟的进程相互发送消息000618122430364248546081624324048566472809182736455463728190ABCD000612182430364248657181624324048566472809182736455463728190ABCD未同步前各自的时钟同步后的时钟时钟同步事件f事件e2021/10/105第三章分布式系统中的通信注意:使用逻辑时钟,a->b可以保证C(a)<C(b),但反之不然。上图中事件e和f分别是进程3中的事件,虽然可以看出存在C(f)﹥C(e),但e‖f。使用逻辑时钟只能对事件作部分排序!可以通过对发生的事件加上进程标识符且对进程标识符进行排序,来实现对事件的完全排序。进程P上的事件a时间邮戳为Ta,进程Q上的事件b时间邮戳为Tb,定义:a、b的全局时间邮戳分别为(Ta,p),(Tb,q),(Ta,p)<(Tb,q)当且仅当Ta<Tb或者Ta=Tb但同时有p<q。进程P中的事件a先于进程Q中的事件b发生,用a﹦﹦>b表示。这里﹦﹦>表示全序关系。2021/10/106第三章分布式系统中的通信●物理时钟通常,使用协同宇宙时间UTC(UniversalCoordinatedTime)来代替国际原子时间TAI(InternationalAtomicTime),。时间服务器S配备接收卫星授时装置并根据请求提供标准时间。进程P在消息mr中请求时间,并在消息mt中接收时间t,原则上它应该将自身的时钟置为t+Ttrans,其中Ttrans为从S到P的消息传送时间。Ttrans是不确定的,容易受到网络传输竞争的变化。实际上,Ttrans=min+x,min是理想情况下的网络传输时间,而x随网络环境的变化而变化。2021/10/107第三章分布式系统中的通信★Cristian算法如果进程P的时钟刷新率很低,那么发送mr所需时间、时钟服务器处理请求的时间和接收mt所需时间的来回时间Tround可以以合理的精度地用进程P的本机时钟计算出来。如果从S接收的标准时间为t,近似地可以认为实际时间为t+。近似精度为±[(Tround/2)–min]。★Berkeley算法时间服务器周期性地向所有节点发送UTC并询问当地的时间,接收者返回各自本地时间与服务器时间的偏差信息,根据接收到的偏差信息、当时的服务器本机时间,计算出传输来回的平均时间,扣除后再计算出每台机器的时间偏差,向它们分别发送,供它们修正自己的本机时间。2021/10/108第三章分布式系统中的通信★平均算法将时间划分为定长的时间区间,大家约定一个起始时间T0,第i个区间为[T0+iR,T0+(I+1)R],这里R为系统参数。每个时间间隔开始时,每台计算机广播自己的本机时间。由于本机时间各不相同,这些广播并不精确地发生在同一时刻。每台机器也会收到其它机器的广播,仿照Berkeley算法,取一个可信时间间隔,在该区间内收到的广播为有效广播,计算平均值(或去掉一个最大值、一个最小值后平均),用估计传输时间做修正后,作为自己的本机时间。显然,这样得到的系统标准时间与UTC无关,仅仅为了系统内部同步使用。2021/10/109第三章分布式系统中的通信★网络时间协议(NTP)NTP定义了时间服务的体系结构和在各种互连网络上分布时间信息的协议,用作时钟同步的标准。服务器组成层次结构,形成同步子网。主服务器位于树根,与标准时间资源(如UTC接收机)相连,上级服务器对下级服务器进行同步控制。一般来说,由于每一层同步都会出现误差,较低层次的服务器比较高层次的服务器时间更不准确。在服务器不可达或出现故障时,可以重构同步子网。同步控制的方式大致有三种。2021/10/1010